Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 262
Текст из файла (страница 262)
Но проблема состоит в том, что не известны ни присваивания, ни параметры. Основная идея алгоритма ЕМ, рассматриваемого в данном контексте, состоит в том, что необходимо принять допущение, будто нам известны параметры этой модели, а затем вычислить вероятность того, что каждая точка данных принадлежит к тому или иному компоненту. После этого нужно снова согласовать компоненты сданными таким образом, чтобы каждый компонент согласовывался со всем набором данных, каждой точке которого назначен вес, соответствуюгций вероятности того, что она принадлежит к данному компоненту. Такой процесс продолжается итерационно до достижения сходимости.
По сути при этом происходит "дополнение" данных путем вычисления распределений вероятностей по скрытым переменным (определяющим, какому компоненту принадлежит каждая точка данных) на основании текущей модели. При использовании смешанного гауссова распределения модель смешанного распределения инициализируется произвольными значениями параметров, а затем осуществляются итерации по описанным ниже двум шагам. 1. Е-шаг. Вычислить вероятности ргз=р(С=1)х,) того, что данные х, были сформированы компонентом 2.
Согласно правилу Байеса, справедливо соотношение рз)=ар(хз(С=2) Р(С=1). Терм р(к,(С=2) представляет собой вероятность значений данных х,. в )-м гауссовом распределении, а терм р( с=у) — это параметр определения веса )-го гауссова распределения; по определению р;-2' р„. 2. М-шаг. Вычислить новые значения математического ожидания, ковариаций и весов компонента следующим образом: т, с — ~ р„х,/р, Э ей с — ~> р,,х,х;/ре Е-шаг, или шаг ожидания (ехрес(а(юп), может рассматриваться как вычисление ожидаемых значений р„, скрытых ж индикаторных переменных Л„, где значение яс, равно 1, если данные хз были сформированы )-м компонентом, и 0 — в противном случае. В М-шаге, или шаге максимизации (тахнп(хайоп), осуществляется поиск Глава 20.
Статистические методы обучения 965 -' -!975 3 -1980 о 3 -1985 о -1990 я~ -!995 -2000 о б -2005 % -2010 Э -2015 Пче -2020 о щ -2025 20 0 200 юи бОО с 8) 500 а 400 й зоо 3 200 В 100 Й о Б с. -100 о -200 о 20 40 60 80 100 120 Количество итераций О) 5 !О !5 Количество итераций а) Рис. 20.9. Графики, показывающие изменение логарифмического правдоподобия данньш, ь, как функции от количества итераций ЕМ. Горизонтальная линия соответствует логарифмическому правдоподобию истинной модели: график для модели смешанного гауссова распре деления, показан- ной но рис. 20 8 (а)1 график для байесовской сети, приведенной на рис.
20 /О, а (б2 Но события не всегда развиваются так удачно, как можно было бы судить на основании рис. 20.9, а. Например, может случиться так, что один компонент гауссова распределения сузится настолько, что будет охватывать лишь единственную точку данных. В таком случае его дисперсия достигнет нуля, а правдоподобие увеличится до бесконечности! Е!це одна проблема состоит в том, что может произойти "слияние" двух компонентов, в результате чего они примут одинако- новых значений параметров, которые максимизируют логарифмическое правдоподобие данных с учетом ожидаемых значений скрытых индикаторных переменных.
Окончательная модель, параметры которой определены в процессе обучения с помощью алгоритма ЕМ, применяемого к данным, приведенным на рис. 20.8, а, показана на рис. 20.8, в; она практически не отличается от первоначальной модели, на основе которой были сформированы данные. На рис. 20.9, а показан график изменения логарифмического правдоподобия данных, соответствуюших текушей модели, которое изменяется в процессе выполнения алгоритма ЕМ. На этом графике заслуживают внимания две особенности. Во-первых, логарифмическое правдоподобие модели, окончательно полученной в процессе обучения, немного превышает соответствующее значение для первоначальной модели, на основании которой были сформированы исходные данные. Это явление может на первый взгляд показаться удивительным, но оно просто отражает тот факт, что данные были сформированы случайным образом, поэтому существует вероятность того, что они не являются точным отражением самой базовой модели.
Во-вторых, любопытно то, что с)р в алгоритме ЕМ логирифмическое правдоподобие динных повышается после каждой итерации. Можно доказать, что такова общая особенность данного алгоритма. Кроме того, можно доказать, что при определенных условиях алгоритм ЕМ достигает локального максимума правдоподобия (а в редких случаях он может достичь точки перегиба или даже локального минимума).
В этом смысле алгоритм ЕМ напоминает алгоритм восхождения к вершине с учетом градиента, но заслуживает внимания то, что в нем уже не применяется параметр со "ступенчатым изменением величины"! 9бб Часть \Ч. Обучение вые значения срелних и дисперсий, а точки данных станут для них общими. Вырожденные локальные максимумы такого рода представляют собой серьезную проблему, особенно в случае большого количества измерений. Одно из решений состоит в наложении распределений априорных вероятностей на параметры модели и применении версии МАР алгоритма ЕМ.
Еше одно решение состоит в перезапуске вычислений для некоторого компонента с новыми случайно выбранными параметрами, если он становится слишком малым или слишком близким к другому компоненту. Иногда имеет также смысл выбирать для инициализации параметров более обоснованные значения. Обучение байесовских сетей со скрытыми переменными Чтобы определить в процессе обучения параметры байесовской сети со скрытыми переменными, можно применить такие же подходы, которые позволили добиться успеха в случае смешанных гауссовых распределений.
На рис. 20.10 показана ситуация, в которой имеются два пакета конфет, смешанных друг с другом. Для описания конфет применяются три характеристики; кроме разновидности р2ат оти обертки вгтаррел, в некоторых конфетах находятся леденцы с отверстиями но2е в середине, а в некоторых — леденцы без отверстий. Распределение конфет в каждом пакете описано с помощью наивной байесовской модели: в каждом конкретном пакете характеристики являются независимыми, но распределение условных вероятностей каждой характеристики зависит от пакета.
Применяются следующие параметры; 0 — априорная вероятность того, что конфета взята из пакета лад 1; 0„, и 0„,— вероятности того, что конфета относится к разновидности вишневых леденцов, при условии, что эта конфета взята из пакета дар 1 и дао 2 соответственно; Оя„и 0„ задают вероятности того, что обертка имеет красный цвет; а 0„, и 0„— вероятности того, что леденец имеет отверстие. Обратите внимание на то, что вся эта модель в целом представляет собой модель смешанного распределения (в действительности это смешанное гауссово распределение можно также промоделировать в виде байесовской сети, как показано на рис.
20.!О, б!. На этом рисунке скрытая переменная соответствует пакету, поскольку после смешивания конфет мы больше не имеем возможности определить, из какого пакета взята каждая конфета. Можно ли в таком случае восстановить описание этих двух пакетов, наблюдая за характеристиками конфет, взятых из этой смеси? Проведем одну итерацию алгоритма ЕМ для решения этой залачи. Вначале рассмотрим данные. Сформировано 1000 выборок из модели, истинными параметрами которой являются следующие: 0 = О.
з, 0„= 0„, = 0„, = 0.в, 0„, = 0„, = 0„, = 0.2 (20.7) Это означает, что равновероятно получение конфет из одного или другого пакета; в первом пакете в основном находятся вишневые леденцы в красных обертках и с отверстиями, а во втором — в основном лимонные леденцы в зеленых обертках и без отверстий. Количество восьми возможных разновидностей конфет определено в табл. 20.1. Гчз~::! ~() Г~зтиг~~~чегкр ч~1а:~ч ~Й1 о ~~им ОГ.
7 968 Часть |(1. Обучение лобной той, что рассматривается в данном примере, этот вероятностный вывод можно выполнить "вручную", используя правило Байеса и применяя выражение для условной независимости; И 0(гг Шсзансг Вау=1)Р(ага ес Ва =1)ЩЛсзеа Ва =1)Р(Ва =1) гг Р( 61ачсгг ) над=1) Р(нкаррег, ) вау=г) Р(лс1еа, ) вау=г) Р(вау=г) 1 1=1 (Обратите внимание на то, что нормализующая константа также зависит от параметров.) Применяя эту формулу, например, к данным о 273 конфетах в красной обертке, среди которых находятся вин(невые леденцы с отверстиями, определим, какой вклад они вносят в распределение вероятностей: 273 0(о> 0(ог 0(о> 0<ог 1000 ' 0(о) 0(о( 0(о( 0(о(, 0(о( О~о( Оап . 0(о( = О ° 22797 Продолжая эти расчеты для семи других видов конфет, количество которых указано втабл. 20.1, получим, что0(ы = О.
6124. Теперь рассмотрим другие параметры, такие как Оно В полностью наблюдаемом случае это значение можно было бы оценить непосредственно на основе наблюдаемых значений количества вишневых и лимонных леденцов из пакета 1. Ожидаемое количество вишневых леденцов из пакета! задается с помощью следукнцего выражения: Р(вар=1)Р1аиок,=олексу,(окаррекг,ло1ев,) Х зои1аЧОК =СЛЕСНу 3 Эти вероятности также можно вычислить с помощью любого алгоритма для байесовской сети. Продолжая этот процесс, получим новые значения для всех параметров: 0' ' = 0.
6124, 0'ог' = 0. 6684 Оинг~ 0 6483, 0 нг' = 0 ° 6558 0(ог = 0 ° 3887, Онг = 0 ° 3817, Оно( = 0 ° 3827 Логарифмическое правдоподобие данных возрастает от первоначального значения, примерно равного -2044, приблизительно до -2021 после первой итерации, как показано на рис. 20.9, б. Это означает, что в данном обновлении само значение правдоподобия улучшается примерно на коэффициент ег(=10го. К десятой итерации модель, полученная в процессе обучения, лучше согласуется с данными, чем первоначальная модель (1=-1982. 214).
Но дальнейший прогресс очень сильно замедляется. Такая ситуация в приложениях алгоритма ЕМ встречается весьма часто, поэтому во многих практически применяемых системах алгоритм ЕМ на последнем этапе обучения используется в сочетании с таким алгоритмом на основе градиента, как алгоритм Ньютона — Рафсона (см. главу 4). Общий вывод, который может быть сделан на основании данного примера, состоит в том, что ол обновления параметров при обучении байесовской сети со скрытыми переменными являются непосредственно доступными из результатов вероятностного вывода по каждому примеру.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
