2010 Лекции МОТП (Ветров) (1185317), страница 13
Текст из файла (страница 13)
. , xn , tn )p(xn+1 , . . . , xN |tn )α(tn )β(tn )=p(X)p(X)Подставляя в формулу значение n = N, получаемγ(tN ) = p(tN |X) =Таким образом, β(tN ) = 1.p(X, tN )β(tN )p(X)Нормировочная константа p(X)Лекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерЗначение γ(tn ) определено с точностью до нормировочнойконстанты p(X). Однако, на М-шаге значение γ(tn ), какправило, входит в числитель и в знаменатель. Такимобразом, нормировочная константа сокращается.Например, при вычислении центра нормальногораспределения:PNPNα(tnk )β(tnk )xkn=1 γ(tnk )xnµk = PN= Pn=1Nn=1 γ(tnk )n=1 α(tnk )β(tnk )Тем не менее, сама нормировочная константа p(X) — этозначение правдоподобия, которое может представлятьотдельный интерес (например, можно отслеживатьвозрастание правдоподобия при итерациях ЕМ-алгоритма).Зная α(tn ) и β(tn ), правдоподобие может быть легковычислено какXXp(X) =α(tn )β(tn ), ∀n ⇒ p(X) =α(tN )tntNФормула для ξ(tn−1 , tn )Лекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпримерξ(tn−1 , tn ) = p(tn−1 , tn |X) =p(X|tn−1 , tn )p(tn−1 , tn )=p(X)p(x1 , . . . , xn−1 |tn−1 )p(xn |tn )p(xn+1 , . . . , xN |tn )p(tn |tn−1 )p(tn−1 )==p(X)α(tn−1 )p(xn |tn )p(tn |tn−1 )β(tn )=p(X)=Итоговый ЕМ-алгоритм для случая, когдаp(xn |tn ) — нормальные распределенияЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Модельныйпример• Начальная инициализация параметров Θ = (π, A, φ).Параметры π и A можно инициализировать случайно,а φ с помощью кластеризации данных.• Е-шаг. Вычисление α(tn ) и β(tn ) с помощьюрекуррентного алгоритма «вперед-назад». Вычислениевеличин γ(tnj ) и ξ(tn−1,i , tnj ) и, возможно, правдоподобияp(X).• М-шаг.
Вычисление новых значений параметров:πjnewγ(t1j )= PKi=1PN= Pn=1µnewkNγ(t1i )PN,γ(tnk )xnn=1γ(tnk )Anewijn=2 ξ(tn−1,i tnj )PNk=1n=2 ξ(tn−1,i tnk )PNn=1 γ(tnk )(xn − µk )(xnPNn=1 γ(tnk )= PK, Σnew=k− µk )T• Повторять шаги Е и М до сходимости (пока значениеp(X) или Θ не стабилизируется).Задача прогнозированияЛекция 4.Скрытыемарковскиемодели. Часть 2.p(xN+1 |X) ==Методмаксимальногоправдоподобиядля СММУстойчивыеформулы дляалгоритма«вперед-назад»Модельныйпримерp(xN+1 , tN+1 |X) =tN+1ВетровАлгоритм«вперед-назад»XXÃp(xN+1 |tN+1 )tN+1=XÃp(xN+1 |tN+1 )tN+1Xp(xN+1 |tN+1 )p(tN+1 |X) =tN+1X!p(tN+1 , tN |X)tNX=!p(tN |X)p(tN+1 |tN )=tNÃX!p(tN , X)p(xN+1 |tN+1 )p(tN+1 |tN )==p(X)tN+1tNÃ!X1 X=p(xN+1 |tN+1 )p(tN+1 |tN )α(tN )p(X) ttXN+1NЭто фактически смесь распределений с компонентамиP1p(xN+1 |tN+1 ) и весами wk = p(X)tN p(tN+1 |tN )α(tN ).
Для полученияточечного прогноза x∗N+1 можно воспользоваться MCMC.План лекцииЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»1 Метод максимального правдоподобия для СММ2 Алгоритм «вперед-назад»3 Устойчивые формулы для алгоритма «вперед-назад»Модельныйпример4 Модельный примерНеобходимость устойчивых вычислений дляα(tn ) и β(tn )Лекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерФормулы пересчета для α(tn ) и β(tn ):Xα(tn ) =p(xn |tn )α(tn−1 )p(tn |tn−1 )β(tn ) =Xtn−1β(tn+1 )p(tn+1 |tn )p(xn+1 |tn+1 )tn+1На практике значения вероятностей p(tn |tn−1 ) и p(xn |tn )могут быть существенно меньше единицы.
В процессепересчета эти вероятности умножаются друг на друга, иполучающиеся значения перестают укладываться вмашинную точность.Устойчивые формулы для α(tn ) IЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерПредлагается вместо α(tn ) рассмотреть следующуювеличину:α̂(tn ) = p(tn |x1 , .
. . , xn ) =α(tn )p(x1 , . . . , xn )Можно надеяться, чтоPзначения α̂(tn ) будут существенноотличны от нуля, т.к. tn α̂(tn ) = 1.Рассмотрим также величиныcn = p(xn |xn−1 , . . . , x1 ).Вычисление этих величин также будет устойчивым, т.к. ониимеют смысл одномерных вероятностных распределений.Устойчивые формулы для α(tn ) IIЛекция 4.Скрытыемарковскиемодели.
Часть 2.Очевидно, чтоp(x1 , . . . , xn ) =ВетровМетодмаксимальногоправдоподобиядля СММnYcii=1Ã n !Yciα(tn ) = p(tn |x1 , . . . , xn )p(x1 , . . . , xn ) = α̂(tn )i=1Алгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерПодставляя это выражение в формулу пересчета для α(tn )Xα(tn ) = p(xn |tn )α(tn−1 )p(tn |tn−1 ),tn−1получаемcn α̂(tn ) = p(xn |tn )Xα̂(tn−1 )p(tn |tn−1 )tn−1Значение cn определяется из условия нормировки для α̂(tn ).Устойчивые формулы для β(tn )Лекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»Рассмотрим следующую величинуβ̂(tn ) =p(xn+1 , . . . , xN |tn )β(tn )= QNp(xn+1 , . . . , xN |x1 , . . . , xn )i=n+1 ciВычисление данной величины будет устойчивым, т.к. β̂(tn )является отношением двух распределений на (xn+1 , . . . , xN ).Подставляя выражение для β̂(tn ) в формулу пересчетаXβ(tn ) =β(tn+1 )p(tn+1 |tn )p(xn+1 |tn+1 ),Модельныйпримерtn+1получаемcn+1 β̂(tn ) =Xβ̂(tn+1 )p(tn+1 |tn )p(xn+1 |tn+1 )tn+1Значения cn определяются из формул пересчета для α̂(tn ).Окончательные выражения для Е-шагаЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерПравдоподобие p(X) вычисляется какp(X) =NYcnn=1Другие необходимые величины вычисляются какγ(tn ) =α̂(tn )β̂(tn )1ξ(tn−1 , tn ) = α̂(tn−1 )p(xn |tn )p(tn |tn−1 )β̂(tn )cnПлан лекцииЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»1 Метод максимального правдоподобия для СММ2 Алгоритм «вперед-назад»3 Устойчивые формулы для алгоритма «вперед-назад»Модельныйпример4 Модельный примерМодельный пример IЛекция 4.Скрытыемарковскиемодели. Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерВ качестве иллюстрации работы ЕМ-алгоритма обученияСММ рассмотрим простой модельный пример. X ∈ R,K = 3, данные сгенерированы из нормальныхраспределений со следующими параметрами:µ1 = 0,µ2 = 0,σ12σ22= 0.1,µ3 = 1= 0.5, σ32 = 0.1Априорные вероятности и матрица перехода выбраныследующим образом:0.98 0.01 0.01π = [0.3, 0.2, 0.5],A = 0.01 0.97 0.020.01 0.01 0.9821.510.50−0.5−1−1.501002003004005006007008009001000Модельный пример II2Лекция 4.Скрытыемарковскиемодели.
Часть 2.1.511.50.501−0.5Ветров−10.5−1.5Методмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»010020030040050060070080090010000−3−2−10123−2−10123−2−10123−2−10123−2−1012321.5Ит. 1:10.50−31.51Ит. 5:Модельныйпример0.50−31.51Ит. 20:0.50−31.51Ит. 54:0.50−3Модельный пример IIIЛекция 4.Скрытыемарковскиемодели.
Часть 2.ВетровМетодмаксимальногоправдоподобиядля СММАлгоритм«вперед-назад»Устойчивыеформулы дляалгоритма«вперед-назад»МодельныйпримерПосле 54-ой итерации ЕМ-алгоритма значения параметровбыли следующие:0.984 0.004 0.012π = [10−190 , 10−125 , 1],A = 0.013 0.949 0.0380.011 0.011 0.978µ1 = −0.01, σ12 = 0.11µ2 = 0.1, σ22 = 0.51µ3 = 1, σ32 = 0.11Лекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентЛекция 6. Снижение размерности вданных. Метод главных компонент.Другие моделиКурс «Математические основы теориипрогнозирования»План лекцииЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.1 Метод главных компонент (PCA)Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие модели2 Вероятностный метод главных компонентВероятностная формулировка методаEM-алгоритм для PCAВыбор числа главных компонент с помощью байесовского п3 Другие моделиПрактический пример: распознаваниерукописных цифрЛекция 6.Снижениеразмерности вданных.
Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиЗадача: выбор адекватного признакового описанияизображения x = (x1 , . . . , xD ) для дальнейшегоиспользования алгоритмов распознавания.Выбор признакового пространстваЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Метод главныхкомпонент (PCA)Вероятностныйметод главныхкомпонентДругие моделиПрямой способ: вытянуть матрицу интенсивностей ввектор.Такой способ описания данных не является адекватным всилу ряда причин:• Слишком большое число признаков (для картинки28 × 28 получается 784 признака). Как следствие,большое время обработки, проблемы переобучения ит.д.• Близкие в признаковом пространстве объекты несоответствуют одному классу.
Гипотеза компактностиявляется одним из основных предположенийбольшинства методов распознавания.ИллюстрацияЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.Близкие в признаковом пространстве объекты несоответствуют одному классу.300Метод главныхкомпонент (PCA)250Вероятностныйметод главныхкомпонент200Feature 343Другие модели150’1’’2’’3’100500050100150Feature 342200250300Преобразование признакового пространстваЛекция 6.Снижениеразмерности вданных. Методглавныхкомпонент.После преобразования признакового описания (с помощьюметода главных компонент) количество признаковуменьшается (с 784 до нескольких десятков), причемобъекты одного класса образуют компактные области впризнаковом пространстве.Метод главныхкомпонент (PCA)1500Вероятностныйметод главныхкомпонент’1’’2’’3’1000Другие моделиFeature 25000−500−1000−1500−2000−2000−1500−1000−5000Feature 150010001500Сокращение размерности в данныхЛекция 6.Снижениеразмерности вданных.