Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 189

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 189)

Назовем это стационарное распределение и; итак, его определяющим уравнением является следующее: п(х' ) = ~ п(х) гу(х — зк' ) для всех к' х (14.9) При некоторых стандартных допущениях', касающихся распределения вероятностей перехода гу, существует одно и только одно распределение и, удовлетворяющее этому уравнению при каждом конкретном значении су.

Уравнение 14.9 можно трактовать как утверждение, что в установившемся режиме ожидаемый "отток" из каждого состояния (т.е. его текущее "население") равен ожидаемому "притоку" из всех других состояний. Один из очевидных способов удовлетворения этого отношения состоит в достижении того, чтобы ожидаемый поток между любыми парами состояний был одинаковым в обоих направлениях. В этом состоит свойство 'в. детализированного равновесия, которое показано ниже.

п(х) су(к — гм' ) = п(х' ) су(к' — гк) для всех х, х' (14.10) п(х)гу(х — >к') = ,) п(х')су(к' †) = (х') ,~) о(к' — гк) = п(х') Х где возможен последний этап преобразования, поскольку гарантировано выполне- ние перехода из состояния х '. Г Цепь Маркова, определяемая значением су, должна быть эргоднчной; это означает, что каждое состояние должно быть достижимо из любого другого состояния и не должно быть строго периодических циклов. Можно показать, что из этого свойства детализированного равновесия можно вывести свойство стационарности, получив суммы по х в уравнении 14.10. Получаем следующее соотношение: Глава 14.

Вероятностные рассуждения 693 Теперь мы покажем, что вероятность перехода () (х — )х' ), определяемая на этапе формирования выборки в алгоритме МСмС-)(з)с, удовлетворяет уравнению детали- ЗнрОВаННОГО раВНОВЕСИя СО СтацИОНарНЫМ раСПрЕЛЕЛЕНИЕМ, раВНЫМ р (х ) Е ) (истинному апостериорному распределению по скрытым переменным). Мы проведем это доказательство в два этапа. Вначале определим цепь Маркова, в которой формирование выборки по каждой переменной обусловлено текущими значениями всех прочих переменных, и покажем, что это условие соответствует свойству детализированного равновесия.

Затем мы просто констатируем, что для байесовских сетей формирование такой условной выборки эквивалентно условному формированию выборки по марковскому покрытию переменной (см. с. 1). Допустим, что хь — переменная, для которой должна быть сформирована выборка, и предположим, что ٠— все скрытые переменные, отличные от Х,. Их значениями в текущем состоянии являются х„и й,.

Если будет выполнена выборка нового значения хь ' для переменной хь, обусловленного всеми прочими переменными, включая переменные свидетельства, то будет получено следующее: ц(х-ис') = ч((хь,х,)-+(х,',х.)) = Р(х,')хь,е) Это выражение для переходной вероятности называется 'в. формирователем выборок Гиббса (ЫЬЬз вагпр!ег) и служит основой особенно удобной формы алгоритма МСМС.

Теперь мы покажем, что формирователь выборок Гиббса находится в детализированном равновесии с истинной апостериорной вероятностью: п(х) Ч(х -а х' ) = Р(х)е) Р(х,' )х,, е) = Р(х„х,)е) Р(х,' )х„е) — Р(хь)х.,е)Р(х,)е) Р(х,')х„е) (использование цепного правила после первого терма) Р(х,)хь, е) Р(х, ',х,) е) (использование цепного правила для перехода в обратном направлении) = п(х') ц(х'-+х) Как указано на с, 1, переменная независима от всех других переменных, если дано ее марковское покрытие, поэтому имеет место следующее соотношение: Р(х,')х„е) = Р(х;')пЬ(Хь) ) где жЬ(х,) обозначает значения переменных в марковском покрытии хь, )чв(хь) .

Как показано в упр. 14.10, вероятность переменной, если дано ее марковское покрытие, пропорциональна вероятности переменной, если даны ее родительские переменные, умноженной на вероятность каждой дочерней переменной, если даны ее соответствующие родительские переменные: Р(х,' )пьб(Х~) ) а Р(х,' )рагепсе(Х,) ) х П у нСЬ11с)геп (К1) Поэтому для изменения значения каждой переменной Хь необходимо выполнить такое количество операций умножения, которое равно количеству дочерних переменных переменной Х,. В этом разделе рассматривался только один простой вариант алгоритма МСМС вЂ” вариант, основанный на использовании формирователя выборок Гиббса.

694 Часть ч'. Неопределенные знания и рассуждения в условиях неопределенности В своей наиболее общей форме алгоритм МСМС представляет собой мощный метод вычислений с помощью вероятностных моделей, поэтому было разработано много вариантов этого алгоритма, включая алгоритм эмуляции отжига (см. главу 4), алгоритмы стохастической выполнимости (см. главу 7) и формирователь выборок Метрополиса — Гастингса, рассматриваемый в главе ) 5. 14.6.

РАСПРОСТРАНЕНИЕ ВЕРОЯТНОСТНЪ|Х МЕТОДОВ НА ПРЕДСТАВЛЕНИЯ В ЛОГИКЕ ПЕРВОГО ПОРЯДКА В главе 8 описывалось, какими преимушествами с точки зрения возможностей представления обладает логика первого порядка по сравнению с пропозициональной логикой. В логике первого порядка учитывается существование объектов и отношений между ними, и она позволяет выражать факты о некоторых или обо всех объектах в проблемной области. Это часто приводит к созданию представлений, намного более кратких, чем эквивалентные пропозициональные описания.

Теперь отметим, что байесовские сети по существу являются пропозициональными: множество переменных в них является фиксированным и конечным, а каждая переменная имеет постоянную область определения, состоящую из возможных значений. В связи с этим применимость байесовских сетей становится ограниченной, ог- Если бы можно было найти способ применения теории вероятпостеи в сочетании с выразительными возможностями представлений в логике первого порядка, то можно было бы рассчитывать на существенное расширение спектра задач, решаемы таким образом. Основная идея, которая может привести к достижению этой цели, состоит в следуюшем: в пропозициональном контексте байесовская сеть задает распределения вероятностей по атомарным событиям, каждое из которых определяет значение для каждой переменной в сети. Таким образом, атомарное событие является моделью, или одним из возможных миров, в терминологии пропозициональной логики.

А в контексте логики первого порядка модель (с ее интерпретацией) задает область определения объектов, отношения, которые имеют место между этими объектами, и отображения из констант и предикатов базы знаний в объекты и отношения модели. Поэтому ~- вероятностная база знаний первого порядка должна задавать вероятности для всех возможных моделей первого порядка. Допустим, что )ь(м) — вероятность, присвоенная модели )чс помощью базы знаний. Для каждого высказывания в логике первого порядка ф вероятность Р(ф) задается обычным образом, путем суммирования по всем возможным мирам, где высказывание ф является истинным: ~) ))ь (н) Р(ф) (14.12) Мсф является исьинным ь Н До сих пор все, казалось бы, шло хорошо. Тем не менее есть одна проблема: множество моделей первого порядка является бесконечным.

Это означает, что, вопервых, суммирование может быть неосуществимым, и, во-вторых, задача определения полного, согласованного распределения на бесконечном множестве миров может оказаться очень трудной. 695 Глава 14. Вероятностные рассуждения Поэтому мы должны умерить наши амбиции, по крайней мере, на время. В частности, определим ограниченный язык, для которого интересующими становятся только модели, количество которых является конечным.

Для этого можно использовать несколько способов. В этом разделе будут описаны 'ж реляционные вероятностные модели, или КРМ (Ке1агюпа! РгоЬаЬгрцу Мог)е)), идея которых заимствована из семантических сетей (см. главу ! 0) и из объектно-реляционных баз данных. Другие подходы обсуждаются в библиографических и исторических заметках в конце настоящей главы.

Модели КРМ допускают использование константных символов, которыми именуются обьекты. Например, допустим, что РхоГБгл1 гь — имя профессора, а гопея — имя студента. Каждый объект представляет собой экземпляр некоторого класса; например, РкоГБюйс)т относится к классу Рхойеяяох (профессор), допея — к классу Бгыдепс (Студент). Предполагается, что класс каждого константного символа известен. Применяемые нами функциональные символы будут подразделяться на два типа. Функции первого типа, еь простые функции, отображают объект не на лругой структурированный объект, а на некоторое значение из фиксированной области значений, полностью аналогично случайной переменной.

Например, значениями функций 1псе111депее(допея1 (интеллект Джонса) и Рипжпд(ркоГБюбсь) (Финансирование профессора Смита) могут быть Л1 (высокий) или 1о (низкий), азначениями функций Биссеяя(топая) (Успех Джонса) и Рате(рхойБглхс)г) (Известность профессора Смита) могут быть схие (истинный) или Га1яе (ложный). Функциональные символы не лолжны применяться к таким значениям, как ехце и Еа1яе, поэтому вложение простых функций невозможно.

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

Список файлов книги