2010 Лекции МОТП (Ветров) (1185317), страница 12
Текст из файла (страница 12)
. . , xN } и латентных (скрытых) переменныхT = {t1 , . . . , tN }.• Латентные переменные T являются дискретными,поэтому их иногда называют переменными состояния.• Значение наблюдаемого вектора в момент времени n xnзависит только от скрытого состояния tn , которое всвою очередь зависит только от скрытого состояния впредыдущий момент времени tn−1 .Спецификация вероятностной модели IЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерПусть имеется K возможных состояний. Закодируемсостояние в каждый момент времени n бинарным векторомtn = (tn1 , . . . , tnK ), где½1, если в момент n модель находится в состоянии jtnj =0, иначеТогда распределение p(tn |tn−1 ) можно задать матрицейпереходаA размера K × K, где Aij = p(tnj = 1|tn−1,i = 1),PA=1,т.е.ijjp(tn |tn−1 ) =K YKYttAijn−1,i nji=1 j=1Пусть в первый момент времени p(t1j = 1) = πj . Тогдаp(t1 ) =KYj=1tπj 1jСпецификация вероятностной модели IIЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Пусть для каждого состояния k ∈ {1, . . . , K} в моментвремени n известна модель генерации наблюдаемых данныхxn p(xn |φk ), задаваемая с помощью набора параметров φk .ТогдаKYp(xn |tn ) =(p(xn |φk ))tnkj=1Обозначим полный набор параметров СММ черезΘ = {π, A, φ}. Тогда правдоподобие в СММ вычисляетсякакМодельныйпримерp(X, T|Θ) = p(t1 ,π )=KYj=1tπj 1jNYp(tn |tn−1 ,A )n=2N YK YKYn=2 i=1 j=1NYp(xn |tn ,φ ) =n=1ÃttAijn−1,i nj N YKYn=1 k=1!(p(xn |φk ))tnkЗадачи в СММЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпример• Распознавание (предыдущая лекция). Известнанекоторая последовательность X и набор параметровΘ. Задача состоит в получении наиболееправдоподобной последовательности состояний T какarg maxT p(T|X, Θ) (алгоритм Витерби).• Обучение с учителем (предыдущая лекция). Известнанекоторая последовательность X, для которой заданыT. Задача состоит в оценке по обучающей выборкенабора параметров Θ.• Обучение без учителя. Известна некотораяпоследовательность X и число состояний K.
Задачасостоит в оценке параметров Θ (ЕМ-алгоритм).• Нахождение маргинального распределения p(tn |X, Θ)компоненты tn по заданым X и Θ• Прогнозирование. Известна некотораяпоследовательность X. Задача состоит в оценкенаблюдаемого вектора в следующий момент времениN + 1 — p(xN+1 |X).План лекцииЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»1 Метод максимального правдоподобия для СММ2 Алгоритм «вперед-назад»3 Устойчивые формулы для алгоритма «вперед-назад»Модельныйпример4 Модельный примерПлан лекцииЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»1 Метод максимального правдоподобия для СММ2 Алгоритм «вперед-назад»3 Устойчивые формулы для алгоритма «вперед-назад»Модельныйпример4 Модельный примерМетод максимального правдоподобияЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерДля оценки параметров СММ Θ воспользуемся методоммаксимального правдоподобия:XΘ∗ = arg max p(X|Θ) = arg maxp(X, T|Θ)ΘΘTПрямая максимизация правдоподобия затруднительна, т.к.оптимизируемая функция не является выпуклой и, крометого, для вычисления функции требуется суммирование N Kслагаемых. Можно воспользоваться итерационнымЕМ-алгоритмом.EM-алгоритм в общем видеЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерТребуется найти максимум правдоподобия в вероятностноймодели со скрытыми переменными:Ã!XXp(X|Θ) =p(X, T|Θ) → max ⇔ logp(X, T|Θ) → maxTΘTΘ• E-шаг. Фиксируется значение параметров Θold .Оценивается апостериорное распределение на скрытыепеременные p(T|X, Θold ), и полное правдоподобиеусредняется по полученному распределению:XET|X,Θold log p(X, T|Θ) =log p(X, T|Θ)p(T|X, Θold )T• М-шаг. Фиксируется апостериорное распределениеp(T|X, Θold ), и производится поиск новых значенийпараметров Θnew :Θnew = arg max ET|X,Θold log p(X, T|Θ)Θ• Шаги E и M повторяются до сходимости.E-шагЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Обозначимγ(tnj ) = ET|X,Θ tnj = p(tnj = 1|X, Θold ),ξ(tn−1,i , tnj ) = ET|X,Θ (tn−1,i tnj ) = p(tn−1,i = 1, tnj = 1|X, Θold ).Тогдаlog p(X, T|Θ) =KXt1j log πj +j=1Устойчивыеформулы дляалгоритма«вперед-назад»N XK XKXМодельныйпримерn=2 i=1 j=1tn−1,i tnj log Aij +ET|X,Θold log p(X, T|Θ) =N XKXtnj log p(xn |φk )n=1 j=1KXγ(t1j ) log πj +j=1N XK XKXn=2 i=1 j=1ξ(tn−1,i , tnj ) log Aij +N XKXn=1 j=1γ(tnj ) log p(xn |φk )M-шагЛекция 4.Скрытыемарковскиемодели. Часть 2.Ветровπ:KXKXγ(t1j ) log πj + λ πj − 1 → extrj=1Методмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпримерπ,λj=1γ(t1j )γ(t1j )+ λ = 0 ⇒ πj = −πjλKXj=1πj = 1 ⇒ λ = −KXγ(t1i )i=1γ(t1j )πjnew = PKi=1 γ(t1i )Действуя аналогично для A, принимая во внимание, чтоPKj=1 Aij = 1 ∀ i, получаем:PNξ(tn−1,i tnj )newAij = PK n=2PNk=1n=2 ξ(tn−1,i tnk )M-шаг для компонент φЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СМММ-шаг для компонент генерации данных p(xn |φk )абсолютно аналогичен М-шагу для оценки параметров привосстановлении смесей распределений. В частности, если вкачестве компонент выступают многомерные нормальныераспределенияp(xn |φk ) = N (xn |µk , Σk ),Алгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»то задача оптимизации для параметров µk , Σk может бытьрешена в явном виде:МодельныйпримерPNµk = Pn=1NPNΣk =n=1γ(tnk )xnn=1γ(tnk )γ(tnk )(xn − µk )(xn − µk )TPNn=1 γ(tnk )Инициализация параметров ΘЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерДля начала работы ЕМ-алгоритма необходимо задатьначальные значения параметров Θ = (π, A, φ).
Заметим,что если какой-нибудь параметр инициализирован нулем,то в процессе итераций ЕМ его значение не изменится.• Значения параметров π и A обычно выбираютсяPслучайными при соблюдении ограничений j πj = 1 иPj Aij = 1 ∀i.• Инициализация φ зависит от формы распределенийp(x|φ). В случае нормальных распределений можнопровести кластеризацию данных на K кластеров ивыбрать в качестве µk и Σk центр и разброссоответствующего кластера.План лекцииЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»1 Метод максимального правдоподобия для СММ2 Алгоритм «вперед-назад»3 Устойчивые формулы для алгоритма «вперед-назад»Модельныйпример4 Модельный примерВычисление апостериорных распределенийна скрытые компонентыЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерНа Е-шаге алгоритма обучения СММ требуется вычислениеапостериорных распределений на скрытые компонентыγ(tnj ) = p(tnj = 1|X, Θ),ξ(tn−1,i , tnj ) = p(tn−1,i = 1, tnj = 1|X, Θ)Алгоритм «вперед-назад» (Баума-Уэлша) позволяетэффективно вычислять эти величины для всех n, i, j залинейное по N время.В дальнейшем для удобства будем опускать Θ во всехформулах, считая набор параметров фиксированным.Свойства условной независимости для СММЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпримерp(X|tn ) =p(x1 , . . . , xn |tn )p(xn+1 , . . . , xN |tn )p(x1 , . . . , xn−1 |xn , tn ) =p(x1 , . . . , xn−1 |tn )p(x1 , . . . , xn−1 |tn−1 , tn ) =p(x1 , . . . , xn−1 |tn−1 )p(xn+1 , . . . , xN |tn , tn+1 ) =p(xn+1 , . . . , xN |tn+1 )p(xn+2 , . . .
, xN |tn+1 , xn+1 ) =p(xn+2 , . . . , xN |tn+1 )p(X|tn−1 , tn ) =p(x1 , . . . , xn−1 |tn−1 )p(xn |tn )×× p(xn+1 , . . . , xN |tn )p(xN+1 |X, tN+1 ) =p(xN+1 |tN+1 )p(tN+1 |tN , X) =p(tN+1 |tN )Вычисление γ(tnj )Лекция 4.Скрытыемарковскиемодели. Часть 2.По формуле Байесаγ(tn ) = p(tn |X) =ВетровМетодмаксимальногоправдоподобиядля СММПользуясь свойствами условной независимости для СММ,получаемАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпримерp(X|tn )p(tn )p(X)γ(tn ) =p(x1 , .
. . , xn , tn )p(xn+1 , . . . , xN |tn )α(tn )β(tn )=p(X)p(X)Здесьα(tn ) = p(x1 , . . . , xn , tn )β(tn ) = p(xn+1 , . . . , xN |tn )Алгоритм «вперед-назад» позволяет быстро рекуррентновычислять значение α(tn ) через α(tn−1 ) (проход вперед) иβ(tn ) через β(tn+1 ) (проход назад).Рекуррентная формула для α(tn )Лекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»α(tn ) =p(x1 , . . . , xn , tn ) ==p(x1 , . .
. , xn |tn )p(tn ) ==p(xn |tn )p(x1 , . . . , xn−1 |tn )p(tn ) ==p(xn |tn )p(x1 , . . . , xn−1 , tn ) =X=p(xn |tn )p(x1 , . . . , xn−1 , tn−1 , tn ) =tn−1=p(xn |tn )Xp(x1 , . . . , xn−1 , tn |tn−1 )p(tn−1 ) =tn−1Модельныйпример=p(xn |tn )Xp(x1 , . . . , xn−1 |tn−1 )p(tn |tn−1 )p(tn−1 ) =tn−1=p(xn |tn )Xp(x1 , . . . , xn−1 , tn−1 )p(tn |tn−1 ) =tn−1=p(xn |tn )Xtn−1α(tn−1 )p(tn |tn−1 )Вычисление α(tn )Лекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерДля запуска рекуррентного процесса необходимовычислитьα(t1 ) = p(x1 , t1 ) = p(t1 )p(x1 |t1 ) =KY(πj p(x1 |φj ))t1jj=1На каждом шаге рекурсии вектор α(tn ) длины Kумножается на матрицу p(tn |tn−1 ) размера K × K.
Поэтомусложность всего рекуррентного процесса составляетO(NK 2 ).Рекуррентная формула для β(tn )Лекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММβ(tn ) =p(xn+1 , . . . , xN |tn ) =X=p(xn+1 , . . . , xN , tn+1 |tn ) =tn+1Алгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпример=Xp(xn+1 , .
. . , xN |tn+1 )p(tn+1 |tn ) =tn+1=Xp(xn+2 , . . . , xN |tn+1 )p(xn+1 |tn+1 )p(tn+1 |tn ) =tn+1=Xtn+1β(tn+1 )p(xn+1 |tn+1 )p(tn+1 |tn )Инициализация рекуррентного процесса дляβ(tn )Лекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерВспомним формулу, связывающую значение γ(tn ) с α(tn ) иβ(tn ):γ(tn ) =p(x1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
