Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 263
Текст из файла (страница 263)
Более того, для каждого парометра требуются только локальные апостериорные вероятности Для общего случая, в котором в процессе обучения определяются параметры условной вероятности для каждой переменной х„если даны ее роди- 970 Часть ЪЗ. Обучение Опять-таки эти ожидаемые количества могут быть вычислены с помощью любого алгоритма вероятностного вывода для скрытой марковской модели. Для вычисления необходимых вероятностей можно очень легко модифицировать прямой — обратный алгоритм, приведенный в листинге 15.1.
Заслуживает внимание одно важное замечание, что требуются вероятности, полученные путем сглаживания, а не фильтрации; это означает, что при оценке вероятности того, что произошел конкретный переход, необходимо учитывать полученное впоследствии свидетельство. Например, как было указано в главе ! 5, свидетельство в случае убийства обычно может быть получено только после этого преступления (т.е. после перехода из состояния х в состояние 7).
Общая форма алгоритма ЕМ Выше было описано несколько вариантов применения алгоритма ЕМ. Каждый из них сводился к тому, что вычислялись ожидаемые значения скрытых переменных для каждого примера, а затем повторно вычислялись параметры с использованием ожидаемых значений так, как если бы они были наблюдаемыми значениями. Допустим, что х — все наблюдаемые значения во всех примерах, и предположим, что 2 обозначает все скрытые переменные для всех примеров, а 8 представляет собой все параметры для модели вероятности.
В таком случае алгоритм ЕМ можно представить с помощью следующего уравнения: агдтах ~> Р1а=х1х,О~'~1 Ъ(х,аса101 е Это уравнение составляет саму суть алгоритма ЕМ. При этом Е-шаг сводится к вычислению выражения для суммы, которая представляет собой ожидаемое значение логарифмического правдоподобия "дополненных" данных по отношению к распределению Р(х=я1х, Всо), т е.
распределение апостериорных вероятностей по скрытым переменным при наличии полученных данных. С другой стороны, Мхщаг представляет собой максимизацию этого ожидаемого логарифмического правдоподобия по отношению к параметрам. При использовании смешанного гауссова распределения скрытыми переменными являются яг„где ам равна 1, если пример 7' был сформирован компонентом з.
При использовании байесовских сетей скрытые переменные представляют собой значения ненаблюдаемых переменных для каждого примера. При использовании скрытых марковских моделей скрытые переменные являются переходами 4 — э 75 Начиная с этой общей формы, можно вывести алгоритм ЕМ для конкретного приложения, как только определены соответствующие скрытые переменные. Поняв основную идею алгоритма ЕМ, можно легко вывести все возможные его варианты и усовершенствования. Например, во многих случаях Е-шаг (вычисление распределений апостериорных вероятностей по скрытым переменным) является трудновыполнимым, как при использовании больших байесовских сетей.
Оказалось, что в этом случае можно применить приближенный Е-шаг и все еще получить эффективный алгоритм обучения. А если используется такой алгоритм формирования выборки, как МСМС (см. раздел 14.5), то процесс обучения становится полностью интуитивно понятным: каждое состояние (конфигурация скрытых и наблюдаемых переменных), посещенное алгоритмом МСМС, рассматривается точно так 971 Глава 20.
Статистические методы обучения же, как если бы оно было полным наблюдением. 11оэтому параметры могут обновляться непосредственно после каждого перехода из состояния в состояние в алгоритме МСМС. Для определения с помощью обучения параметров очень больших сетей показали свою эффективность и другие формы приближенного вероятностного вывода, такие как вариационные и циклические методы. Определение с помощью обучения структур байесовских сетей со скрытыми переменными В разделе 20.2 обсуждалась задача определения с помощью обучения структур байесовских сетей на основе полных данных. А если приходится учитывать скрытые переменные, то задача осложняется. В простейшем случае скрытые переменные могут быть включены в общий список наряду с наблюдаемыми переменными; хотя их значения не наблюдаются, алгоритм обучения получает сведения о том, что они существуют, и должен найти для них место в структуре сети.
Например, с помошью алгоритма может быть предпринята попытка определить в процессе обучения структуру, показанную на рис. 20.7, а, на основе той информации, что в модель должна быть включена переменная неатсЖэеаэе (трехзначная переменная). Если же алгоритму обучения не предоставлена эта информация, то в процессе обучения возникают два варианта: либо исходить из того, что данные действительно являются полными (что вынуждает алгоритм определить в процессе обучения модель с гораздо большим количеством параметров, показанную на рис. 20.7, б), либо изобрести новые скрытые переменные для упрощения модели.
Последний подход можно реализовать путем включения новых вариантов операций модификации в процедуру поиска структуры — предусмотреть в алгоритме возможность не только модифицировать связи, но и добавлять или удалять скрытые переменные либо менять их арность. Безусловно, в таком алгоритме нельзя предусмотреть возможность назвать вновь изобретенную переменную, допустим неатсШэеаэе, а также присваивать ее значениям осмысленные имена. Но, к счастью, вновь изобретенные скрытые переменные обычно связываются с ранее существовавшими переменными, поэтому человек — специалист в данной проблемной области часто может проверять локальные распределения условных вероятностей, касающиеся новой переменной, и устанавливать ее смысл.
Как и в случае полных данных, процесс определения структуры с помошью обучения с учетом максимального правдоподобия в чистом виде приводит к созданию полносвязной сети (более того, сети без скрытых переменных), поэтому требуется ввести какую-то форму штрафования за сложность.
Для аппроксимации байесовского обучения можно также применить алгоритм МСМС. Например, можно предусмотреть определение в процессе обучения параметров смешанного гауссова распределения с неизвестным количеством компонентов, осуществляя выборки по такому количеству; приближенное распределение апостериорных вероятностей для количества заданных гауссовых распределений определяется частотами выборки в процессе применения алгоритма МСМС. До сих пор рассматриваемый процесс обучения состоял из внешнего цикла, который представлял собой процесс поиска структуры, и внутреннего цикла, представляющего собой процесс оптимизации параметров.
В случае полных данных внутренний цикл выполняется очень быстро, поскольку при этом достаточно лишь 972 Часть У!. Обучение извлечь информацию об условных частотах из набора данных. Если же имеются скрытые переменные, то для выполнения внутреннего цикла может потребоваться применить много итераций алгоритма ЕМ или алгоритма на основе градиента, а каждая итерация потребует вычисления распределений апостериорных вероятностей в байесовской сети, что само представляет собой ХР-трудную задачу. К настоящему времени доказано, что такой подход является практически не применимым для определения в процессе обучения сложных моделей. Одно из возможных усовершенствований состоит в использовании так называемого алгоритма 'ж структурного ЕМ, который действует во многом таким же образом, как и обычный (параметрический) алгоритм ЕМ, за исключением того, что этот алгоритм может обновлять не только параметры, но и структуру. Так же как в обычном алгоритме ЕМ используются текущие параметры для вычисления ожидаемых количеств в Е-шаге, а затем эти количества применяются в М-шаге для выбора новых параметров, так и в алгоритме структурного ЕМ используется структура для вычисления ожидаемых количеств, после чего эти количества применяются в М-шаге для оценки правдоподобия потенциальных новых структур (в этом состоит отличие данного метода от метода внешнего цикла/внутреннего цикла, в котором вычисляются новые ожидаемые количества для каждой потенциальной структуры).
Таким образом, структурный алгоритм ЕМ позволяет вносить в сеть несколько структурных изменений без каких-либо повторных вычислений ожидаемых количеств и обладает способностью определять в процессе обучения нетривиальные структуры байесовских сетей. Тем не менее необходимо проделать еще очень много работы, прежде чем можно будет утверждать, что задача определения структуры в процессе обучения окончательно решена. 20.4.
ОБУЧЕНИЕ НА ОСНОВЕ ЭКЗЕМПЛЯРА До сих пор приведенное в данной главе описание статистического обучения сосредоточивалось в основном на задаче подгонки параметров ограниченного семейства вероятностных моделей к неограниченному набору данных. Например, в методе неконтролируемой кластеризации используются смешанные гауссовы распределения на основании того предположения, что структуру рассматриваемых данных можно объяснить, трактуя их как сумму постоянного количества гауссовых распределений. Авторы настоящей книги называют такие методы 'в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
