4 Скрытые марковские модели (1162172), страница 2
Текст из файла (страница 2)
Часть 1ВетровЛикбезОсновыпримененияСММОпределениеСММОбучение СММс учителемАлгоритмВитерби1 ЛикбезМетод динамического программирования2 Основы применения СММОпределение СММОбучение СММ с учителемАлгоритм ВитербиЕМ-алгоритм3 ЕМ-алгоритмГрафические модели с неполными даннымиРазделение гауссовской смесиСегментация сигналаЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММОпределениеСММОбучение СММс учителемАлгоритмВитербиЕМ-алгоритм• Пусть известна некоторая последовательностьнаблюдений X и набор параметров СММ Θ. Требуетсяопределить наиболее вероятную последовательностьсостояний T, т.е. найти arg maxT p(T|X, Θ)• Заметим, что p(X|Θ) не зависит от T, поэтомуp(X, T|Θ)=p(X|Θ)= arg max p(X, T|Θ) = arg max log p(X, T|Θ)arg max p(T|X, Θ) = arg maxTTTT• Но это же классическая задача динамическогопрограммирования!Аналогия с задачей объезда странЛекция 3.Скрытыемарковскиемодели.
Часть 1Ветров• В самом деле логарифм совместной плотности поопределениюЛикбезОсновыпримененияСММОпределениеСММОбучение СММс учителемАлгоритмВитербиЕМ-алгоритмlog p(X, T|Θ) = +K XKN XXn=2 i=1 j=1KXt1j log πj +j=1tn−1,i tnj log Aij +ÃN XKX!tnk log p(xn |φk )n=1 k=1• Первое слагаемое определяет «пункт отбытия», второеслагаемое — стоимость перезда из города страны n − 1в город в стране n, а третье слагаемое отражает«стоимость ночлега» в выбранном городе страны nАлгоритм ВитербиЛекция 3.Скрытыемарковскиемодели. Часть 1Ветровlog p(X, T|Θ) = ЛикбезОсновыпримененияСММОпределениеСММОбучение СММс учителемАлгоритмВитербиЕМ-алгоритм+N XK XKXKXt1j log πj +j=1tn−1,i tnj log Aij +n=2 i=1 j=1à N KXX!tnk log p(xn |φk )n=1 k=1Функция Беллмана V1j = log πj + log p(x1 |φj )£¤Vnj = max Vn−1,i + log Aij + log p(xn |φj )iФункция Snj определяется аналогично: S1j = ∅£¤Snj = arg max Vn−1,i + log Aij + log p(xn |φj )iАлгоритм ВитербиЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММОпределениеСММОбучение СММс учителемАлгоритмВитербиЕМ-алгоритм£¤Vnj = max Vn−1,i + log Aij + log p(xn |φj )i£¤Snj = arg max Vn−1,i + log Aij + log p(xn |φj )iВыполнив прямой проход по сигналу, мы оцениваем Vnj и Snj , авыполнив обратный проход, мы получаем оптимальные номераоптимальных состояний (i∗ (1), . . . , i∗ (N)): i∗ (N) = arg maxi VNii∗ (n) = Sn+1,i∗ (n+1)Легко видеть, что значения переменных tn определяются так:tn,i∗ (n) = 1, tni = 0, ∀i 6= i∗ (n)• Алгорим Витерби позволяет быстро проводить сегментациюочень длинных сигналов• Существует версия алгоритма Витерби, позволяющаяосуществлять сегментацию в реальном времени (точнее, снебольшой задержкой)Пример использованияЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММОпределениеСММОбучение СММс учителемАлгоритмВитербиЕМ-алгоритмПример разметки сигнала на три состояния с помощьюалгоритма Витерби21.510.50−0.5−1−1.501002003004005006007008009001000ПланЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси1 ЛикбезМетод динамического программирования2 Основы применения СММОпределение СММОбучение СММ с учителемАлгоритм Витерби3 ЕМ-алгоритмГрафические модели с неполными даннымиРазделение гауссовской смесиМаксимум неполного правдоподобияЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси• Предположим имеется графическая модель, в которойизвестна только часть значений переменных• Атомарные распределения известны с точностью довектора параметров θ• Требуется оценить параметры по наблюдаемымвеличинам с помощью метода максимальногоправдоподобия, т.е. найтиθ ML = arg max p(X|θ)t1x1t2t3x3x2t4Трудности оптимизации неполногоправдоподобияЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси• По правилу суммирования вероятностей неполное правдоподобиеможет быть получено в виде суммирования по скрытымпеременным полного правдоподобияXp(X|θ) =p(X, T|θ)T• Во многих случаях (в частности, в байесовских сетях) подсчетполного правдоподобия тривиален• При оптимизации правдоподобия удобно переходить клогарифму, в частности выше мы получили явные формулы дляarg maxθ p(X, T|θ) = arg maxθ log p(X, T|θ) в СММ• Прямая оптимизация логарифма неполного правдоподобияочень затруднительна даже в итерационной форме, т.к.функционал имеет вид «логарифм суммы», в то время какудобно оптимизировать «сумму логарифмов»Xlog p(X|θ) = logp(X, T|θ)TСхема ЕМ-алгоритмаЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси• На входе: выборка X, зависящая от набора параметровθ• Инициализируем θ некоторыми начальнымприближением• Е-шаг: Оцениваем распределение скрытой компонентыпри фиксированном значении параметров θ oldp(X, T|θ old )p(T|X, θ old ) = PT p(X, T|θ old )• М-шаг: ОптимизируемET|X,θold log p(X, T|θ) =Xp(T|X, θ old ) log p(X, T|θ) → maxTЕсли бы мы точно знали значение T = T0 , то вместо мат.ожидания по всевозможным (с учетом наблюдаемых данных)T|X, θ old , мы бы оптимизировали log p(X, T0 |θ)• Переход к Е-шагу, пока процесс не сойдетсяθЗамечанияЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси• Оптимизация проводится итерационно методомпокоординатного спуска: на каждой итерациипоследовательно уточняются возможные значения T(Е-шаг), а потом пересчитываются значения θ (М-шаг)• Во многих случаях на М-шаге можно получить явныеформулы, т.к. там происходит оптимизация выпуклойкомбинации логарифмов полных правдоподобийXp(T|X, θ old ) log p(X, T|θ) → max,Tθимеющей вид взвешенной «суммы логарифмов»ПланЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси1 ЛикбезМетод динамического программирования2 Основы применения СММОпределение СММОбучение СММ с учителемАлгоритм Витерби3 ЕМ-алгоритмГрафические модели с неполными даннымиРазделение гауссовской смесиСмесь гауссовских распределенийЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмеси• Имеется выборка X ∼Plj=1Plj=1wj N (x|µj , Σj )) ∈ Rd , wj ≥ 0,wj = 1• Требуется восстановить плотность генеральнойсовокупностиЕМ-алгоритмЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбез• Выбираем начальное приближение µj , wj , Σj• Е-шаг: Вычисляем распределение скрытыхPпеременных zi ∈ {0, 1}, j zij = 1, которые определяют,к какой компоненте смеси принадлежит объект xiОсновыпримененияСММγ(zij ) = PlЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмесиwj N (xi |µj , Σj ))k=1wk N (xi |µk , Σk ))• М-шаг: С учетом новых вероятностей на zi ,пересчитываем параметры смесиµnew=jn1 Xγ(zij )xiNji=1Σnew=jwnew=jNjnNj =nXγ(zij )i=1n1 Xnew Tγ(zij )(xi − µnewj )(xi − µj )Nji=1• Переход к Е-шагу, пока не будет достигнута сходимостьВывод формул на М-шагеЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровВыражение для мат. ожидания логарифма правдоподобия поапостериорному распределению имеет видEZ|X,θ log p(X, Z|θ) =n XlXγ(zij ) (log wj + log N (xi |µj , Σj ))i=1 j=1ЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмесиДифференцирование по µj и Σj (точнее по Σ−1j ) выполняетсяаналогично случаю одной многомерной гауссианы, только объектытеперь берутся с весом γ(zij ).PОптимизация по wj проводится с учетом органичения lj=1 wj = 1 поправилу множителей Лагранжаn XllXXγ(zij ) log wj + λ wj − 1i=1 j=1j=1Дифференцируя лагранжиан по wj получаем уравненияPnPnγ(zij )i=1 γ(zij )+ λ = 0, wj = − i=1wjλPУчитывая, что lj=1 wj = 1 окончательно получаемPnNji=1 γ(zij )λ = −n, wj ==nnПример работы ЕМ-алгоритмаЛекция 3.Скрытыемарковскиемодели.
Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмесиПрименение ЕМ-алгоритма для разделения смеси двухгауссиан. Итерация 0.Пример работы ЕМ-алгоритмаЛекция 3.Скрытыемарковскиемодели. Часть 1ВетровЛикбезОсновыпримененияСММЕМ-алгоритмГрафическиемодели снеполнымиданнымиРазделениегауссовскойсмесиПрименение ЕМ-алгоритма для разделения смеси двухгауссиан. Итерация 1.Пример работы ЕМ-алгоритмаЛекция 3.Скрытыемарковскиемодели.