Скрытые Марковские Модели H1H1 H2H2 H L-1 HLHL X1X1 X2X2 X L-1 XLXL HiHi XiXi 1 2 K … 1 2 K … 1 2 K … … … … 1 2 K … x1x1 x2x2 x3x3 xLxL 2 1 K 2 00

Вероятности и вероятностные модели p1,p2,….p6 pi =1 i=1 6 Вероятностная модель с множеством дискретных исходов Вероятность последовательности выпадения значений P[5,3,2] = p1 p3 p2 1. Бросание кости 2. Случайные последовательности (аминокислоты или нуклеотиды) q1,q2,.qn – вероятности символов в последовательности Вероятность последовательности P(q1q2….qn) = П qi

Условные, совместные и полные вероятности Две кости D1 и D2. Одна кость – честная, другая - нечестная P(i|Dj) – вероятность выпадения i при условии, что была выбрана кость j P(Dj) – вероятность выбора кости P(i,Dj)=P(i|Di)P(Dj) условная вероятность или в общем виде - P(X,Y)=P(X|Y) P(Y) Продемонстрировать на доске на примере пирога жизни совместная вероятность P(X) = P(X,Y) = P(X|Y)P(Y) Y Y полная вероятность

Вероятность и правдоподобие Вероятность (probability) и правдоподобие (likelihood) Функция правдоподобия L( x) – это совместное распределение выборки из параметрического распределения, рассматриваемая как функция параметра. Сравните два вопроса: «Какова вероятность выпадения подряд трех шестерок из трех бросков?» «Насколько правдоподобно, что кости не шулерские, если из трех бросков выпало три шестерки?» Вероятность позволяет нам предсказывать неизвестные результаты, основанные на известных параметрах Правдоподобие позволяет нам оценивать неизвестные параметры, основанные на известных результатах. Здесь параметр – шулерская или не шулерская кость Правдоподобие – это всегда условная вероятность

Теорема Байеса и нечестное казино P(честная кость) =0.99 p1=p2=p3=p4=p5=p6=1/6 P(нечестная кость) =0.01 P6=1/2 p1=p2=p3=p4=p5=1/10 Как проверить, какая кость была здесь взята, честная или нет? Какова вероятность гипотезы о том, что в данном случае кость нечестная? P(3 шестерки|D нечестная) -? Эта вероятность и есть правдоподобность гипотезы

Теорема Байеса и нечестное казино Более правдоподобно, что мы выбрали честную кость, несмотря на то, что получили три шестерки

Цепи Маркова Основное свойство – состояние системы в момент времени t+1 зависит ТОЛЬКО от состояния системы в момент t. X t=1 X t=2 X t=3 X t= 4 X t=5

8 дождь сегодня дождь завтра p rr = 0.4 дождь сегодня нет дождя завтра p rn = 0.6 нет дождя сегодня дождь завтра p nr = 0.2 нет дождя сегодня нет дождя завтра p rr = 0.8 Пример с погодой Матрица переходов rain no rain Стохастическая матрица Ряд суммируется в 1

Пример с погодой X(0)=(1,0) X(1)=X(0)*P = (1,0) x = (0.4, 0.6) X(2)=X(1)*P= X(0) x P = ( 1,0) x = (1,0) x = (0.28,0.72) X(3) = ……………………………………………………………………………………………= (0.256, 0.744) X(n)= X(0) x P = (1,0) x = ……………………………………….= (0.25, 0.75) n n Предсказание – 25% дней с дождем, 75% без дождя rain no rain

10 Coke vs. Pepsi Если посетитель последний раз купил кока-колу, то вероятность того, что в следующий раз он опять купит кока-колу составляет 90%. Если же этот посетитель в последний раз купил пепси, то вероятность того, что в следующий раз он опять купит пепси составляет 80%. coke pepsi

11 Coke vs. Pepsi Вопрос: исходя из того, что человек постоянно покупает пепси, какова вероятность того, что он начиная с настоящего времени два раза купит кока-колу? Матрица переходов: (это значение соответствует вероятности 1 покупки вперед) coke pepsi

12 Coke vs. Pepsi Вопрос: исходя из того, что человек постоянно покупает пепси, какова вероятность того, что он начиная с настоящего времени три раза купит кока-колу

13 Coke vs. Pepsi Предположим, что каждый человек один раз в неделю покупает кока-колу. Предположим, что в настоящее время 60% всех людей пьет кока-колу, и 40% пьют пепси. Какой процент людей будет пить кока-колу через три недели? Пусть (Q 0,Q 1 )=(0.6,0.4) начальные вероятности. кока-кола = 0 пепси = 1

14 Equilibrium (Stationary) Distribution Предположим, что в настоящее время 60% всех людей пьет кока-колу, и 40% пьют пепси. Какой процент людей будет пить кока-колу через 10,100,1000,10000 недель? Для каждой недели вероятности хорошо определены. Сходятся ли они к какому-то равновесному распределению [p 0,p 1 ] Если да, то должно иметь место 9p 0 +.2p 1 =p 0,.8p 1 +.1p 0 =p 1 Решение: p 0 = 2/3, p 1 =1/3

15 Simulation: Markov Process Coke vs. Pepsi Example (cont) week - i Pr[X i = Coke] 2/3 stationary distribution coke pepsi

16 Равновесное (Стационарное) Распределение Является ли распределение стационарным, и является ли оно при этом единственным, определяется некоторыми свойствами процесса. Неприводимость - любое состояние достижимо из любого другого состояния Апериодичность – существует хотя бы одно состояние для которого возможен переход в самого себя. Положителная рекуррентность – для каждого состояния существует конечное число переходов. coke pepsi

17 Равновесное (Стационарное) Распределение Если Цепь Маркова положительно рекуррентная, то существует стационарное распределение Если Цепь Маркова положительно рекуррентная и неприводимая, то существует единственное стационарное распределение. Более того, если процесс был построен таким образом, что стационарное распределение было взято в качестве начального, то такой процесс является эргодическим.

18 Равновесное (Стационарное) Распределение Пусть P – матрица переходов, а стационарное распределение – это вектор π, удовлетворяющий уравнению – Pπ = π. В данном случае стационарное распределение π есть собственный вектор матрицы переходов, соответствующий собственному значению 1. собственный вектор

СКРЫТЫЕ Модели Маркова Hidden Markov Models

20 Скрытые Марковские Модели (вероятностные конечные автоматы) Очень часто у нас возникают ситуации, когда состояния не наблюдаются непосредственно. Поэтому: Hidden Markov Models (HMM) a 11 a 22 a 33 a 44 a 12 a 23 a 34 b 11 b 14 b 12 b Наблюдаемые a ij вероятности переходов для состояний. b ik - вероятности наблюдаемых (выходные вероятности). b 11 + b 12 + b 13 + b 14 = 1, b 21 + b 22 + b 23 + b 24 = 1, etc.

21 Hidden Markov Models - HMM H1H1 H2H2 H L-1 HLHL X1X1 X2X2 X L-1 XLXL HiHi XiXi Hidden variables Observed data

22 Пример: Нечестное казино Собственно, что скрыто в данной модели?

23 H1H1 H2H2 H L-1 HLHL X1X1 X2X2 X L-1 XLXL HiHi XiXi L tosses Fair/Loade d Head/Tail 0.9 Fair loaded head tail /2 1/4 3/4 1/2 Start 1/2 Пример подбрасывания монеты Вопрос 1: Какова вероятность наблюдать такую последовательность (например, HHHTHTTHHT), при условии выбора данной моделиl?

Nucleotide frequencies in the human genome ACTG

25 CpG Островки Regular DNA C-G island CpG islands: части ДНК, обогащённые C и G A C G T change A C G T (1-P)/4 P/6 q/4 P P q q q qP P (1-q)/6 (1-q)/3 p/3 p/6

26 Example: CpG islands In human genome, CG dinucleotides are relatively rare – CG pairs undergo a process called methylation that modifies the C nucleotide – A methylated C mutate (with relatively high chance) to a T Promotor regions are CG rich – These regions are not methylated, and thus mutate less often – These are called CpG islands

27 CpG Islands We construct Markov chain for CpG rich and poor regions Using maximum likelihood estimates from 60K nucleotide, we get two models

28 Ratio Test for CpC islands Для конкретной последовательности X 1,…,X n мы рассчитываем логарифм отношения правдоподобия

Empirical Evalation Гистограмма распределения весов, нормированных на длину. CpG островки – темно- серые, а не. CpG островки – светло-серые Биты – так как логарифм по основанию 2

30 Finding CpG islands Simple Minded approach: Pick a window of size N ( N = 100, for example) Compute log-ratio for the sequence in the window, and classify based on that Problems: How do we select N ? What do we do when the window intersects the boundary of a CpG island?

31 A Different C-G Islands Model A C G T change A C G T H1H1 H2H2 H L-1 HLHL X1X1 X2X2 X L-1 XLXL HiHi XiXi C-G island? A/C/G/T Отличие скрытой от обычной

32 Alternative Approach Build a model that include + states and - states A state remembers last nucleotide and the type of region A transition from a - state to a + describes a start of CpG island маленькая вероятность перехода из одной цепи в другую

Формальное определение HMM Различаем последовательности состояний и последовательности символов x – это последовательность символов, испускаемая моделью – X i – это символ, испущенный в момент времени i Пусть путь π - путь последовательности состояний. Сам путь проходит по обычной цепи Маркова. - i-ое состояние на пути - это i Цепь характеризуется параметрами вероятности перехода между состояниями вероятность, что символ b возникает (испущен) в состоянии k, или эмиссионные вероятности

34 Пример: Нечестное казино Часто говорят, что P(x) – вероятность того, что x сгенерирован данной моделью p1=p2=p3=p4=p5=p6=1/6 P6=1/2 p1=p2=p3=p4=p5=1/10 P6=1/2 p1=p2=p3=p4=p5=1/10 Известно: – Структура модели – Вероятности переходов Скрыто: Что делает казино – FFFFFLLLLLLLFFFF... Наблюдаемые: последовательность бросков кости – Что нам нужно вычислить?: – Когда использовалась честная кость? – Когда использовалась нечестная кость? Ответ представляет собой последовательность FFFFFFFLLLLLLFFF...

Модель присваивает вероятность каждому объяснению наблюдений: P(326|FFL) = P(3|F)·P(F F)·P(2|F)·P(F L)·P(6|L) = 1/6 · 0.99 · 1/6 · 0.01 · ½ Максимальное правдоподобие: нахождение более вероятного объяснения – Найти путь, который с наибольшей вероятностью сгенерирует наблюдаемую последовательность Полная вероятность: вероятность, что наблюдаемая последовательность была сгенерирована HMM – Рассмотреть все пути, которые могли бы сгенерировать наблюдаемую последовательность Имея модель, мы можем сгенерировать последовательность: первое состояние выбирается из распределения вероятностей состояний - a, в этом состоянии наблюдение генерируется (испускается, emitted) по вероятностям e

A parse of a sequence 1 2 K … 1 2 K … 1 2 K … … … … 1 2 K … x1x1 x2x2 x3x3 xLxL 2 1 K 2 00 Совместная вероятность последовательности наблюдений x и последовательности состояний π

The occasionally dishonest casino

The most probable path The most likely path * satisfies To find *, consider all possible ways the last symbol of x could have been emitted Let Then

The Viterbi Algorithm Initialization(i = 0) Recursion (i = 1,..., L): For each state k Termination: To find *, use trace-back, as in dynamic programming

Viterbi: Example 1 x (1/6) (1/2) = 1/12 0 (1/2) = 1/4 (1/6) max{(1/12) 0.99, (1/4) 0.2} = (1/10) max{(1/12) 0.01, (1/4) 0.8} = 0.02 B F L 00 (1/6) max{ , } = (1/2) max{ , } = 0.08

The Viterbi Algorithm sequence states (i,k)(i,k) k k-1k-1... k-2k-2 k +1...

Viterbi: Traceback T( T( T(... T( T(i, L - 1), L - 2)..., 2), 1), 0) = 0

Viterbi gets it right more often than not

GpC islands (С +,G +,C +,G + ) (С -,G -,C -,G - ) – меньше, чем первая, так как переход из С в G меньше в -состоянии, чем в +. (С +,G -,C -,G + ) – будет произведение маленьких вероятностей переключения туда и обратно (10 -4 ). Нужно найти

An HMM for CpG islands A+A+ T+T+ G+G+ C+C+ A-A- T-T- G-G- C-C- A: 0 C: 0 G: 1 T: 0 A: 1 C: 0 G: 0 T: 0 A: 0 C: 1 G: 0 T: 0 A: 0 C: 0 G: 0 T: 1 A: 0 C: 0 G: 1 T: 0 A: 1 C: 0 G: 0 T: 0 A: 0 C: 1 G: 0 T: 0 A: 0 C: 0 G: 0 T: 1 Emission probabilities are 0 or 1. E.g. e G- (G) = 1, e G- (T) = 0 + объединяем

An HMM for CpG islands стрелки - переходы из состояние в состояние

Алгоритм Витерби для CpG

Полная вероятность Для HMM – много различных путей может приводить к наблюдению последовательности x. Вероятность, что наша модель испустит x Полная Вероятность Для обычных цепей Маркова вероятность последовательности - Суммируем по всем путям Суммируем по всем путям Количество возможных путей экспоненциально растет с ростом длины последовательности

Полная вероятность Пусть Тогда r rk r i kk aifxeif)1()()( Полная вероятность Pr(x) может быть вычислена таким же способом, как и наиболее вероятный путь, заменив процедуру взятия максимума суммированием. и Алгоритм просмотра вперед

Алгоритм просмотра вперед The Forward Algorithm Инициализация (i = 0) Рекурсия (i = 1,..., L): Для каждого состояния k Завершение:

The Forward Algorithm : Probability of a Sequence sequence states (i,k)(i,k) k k-1k-1... k-2k-2 k Viterbi:Viterbi: Forward:Forward: the single most probable path sum over all paths i.e.,

Апостериорная вероятность состояний Сгенерированная последовательность известна – x 1 …..x L Какова вероятность того, что наблюдение x i появилось в состоянии k при данной последовательности наблюдений? Вероятность генерации всей последовательности, причем символ i сгенерирован в состоянии k Все, что сгенерировано после состояния k, зависит только от того, что сгенерировано в состоянии k

Апостериорная вероятность состояний Вероятность генерации всей последовательности, причем символ i сгенерирован в состоянии k Все, что сгенерировано после состояния k, зависит только от того, что сгенерировано в состоянии k Этот множитель вычисляется с помощью алгоритма просмотра вперед Этот множитель вычисляется с помощью алгоритма просмотра назад

Алгоритм просмотра назад

Апостериорное дешифрование Используется в добавление к дешифрованию Витерби Применяется, когда множество разных путей имеют практически ту же вероятность, что и наиболее вероятный путь.