Главная » Просмотр файлов » 4 Скрытые марковские модели

4 Скрытые марковские модели (1162172), страница 2

Файл №1162172 4 Скрытые марковские модели (Д.П. Веторв, Ю.И. Журавлёв - Лекции) 2 страница4 Скрытые марковские модели (1162172) страница 22019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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=1KXt1j 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 XKXKXt1j 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 − 1i=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.Скрытыемарковскиемодели.

Характеристики

Тип файла
PDF-файл
Размер
722,6 Kb
Тип материала
Высшее учебное заведение

Список файлов лекций

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6510
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее