Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 188
Текст из файла (страница 188)
Выборка из распределения Р(апис(у) =<О. 5, О. 5>; предположим, что она возвращает значение сгие. 2. Яргуп)с1ег — переменная доказательства со значением сгие. Поэтому мы устанавливаем: ы С- ьХР(ярттп)с1ет=етие[С1оис)у=етое) =О. 1 3. Выборка из распределения Р(кауп[С1оис)у=бгие) =<0.8, 0.2>; предположим, что она возвращает значение сгие. 4. и(есугаев — переменная доказательства со значением сгие. Поэтому мы устанавливаем; ы ь- ыхр(асееотаез=стие) Бртдпм1ет=етие, латп=стие) =О. 099 Теперь алгоритм Ь)ефд)зсес[-Яавзр1е возвращает событие [ сгие, сгие, сгие, сгие) с весом 0,099, и данные об этом событии подытоживаются с учетом условия даЕп= сгие.
Этот вес является низким потому, что событие описывает пасмурный день, в который вероятность применения опрыскивателя является весьма небольшой. Чтобы понять, как работает алгоритм оценки веса с учетом правдоподобия, начнем с изучения сформированного с помощью выборок распределения Ян, для функции (яефд)зсес[-Яаспр1е. Напомним, что переменные свидетельства и зафиксированы со значениями е. Обозначим все прочие переменные как и, иными словами, и=(х)с ге.
В алгоритме выборки для каждой переменной из х, если даны ее родительские значения, формируются следующим образом: 1 Яяя(в,е) = ПР(гс[ратепеа(аз) ) (14.6) 1=1 бе9 Глава 14. Вероятностные рассуждения гн ъ(а,е) = П Р(е,(рагепса(яз) ) 1=1 (14.7) Умножая уравнения 14.б и 14.7, можно определить, что соотношение для взве- шенной вероятности выборки имеет следующую особенно удобную форму, по- скольку эти два произведения охватывают все переменные, заданные в сети: 1 т Ягн(н,е)и(в,е) = П Р(н,(рагепеа(Я,) ) П Р(е,(рагепея(вг) ) з=1 1=1 Р(н,е) (14.8) Это позволяет использовать для вычисления совместной вероятности уравнение 14.1.
Теперь можно легко показать, что оценки весов, полученные с учетом правдоподобия, являются согласованными. Для любого конкретного значения х переменной х оценка апостериорной вероятности может быть рассчитана следующим образом: Р(х(е) = а,) н(гн(х,у, е) ы(х, у, е) иэ алгоритма ьь)се11)гоос)-н)еьо)зстлд у а' ~ Яав(х У,е) ь(х,у, е) для больших И У н Желательно было бы использовать распределение вероятностей сформированных выборок, равное истинному апостериорному распределению Р (а ) е), чтобы в расчет приниматнсь все снидетельства.
Но такой подход не может быть осуществлен эффектинно, поскольку если бы существовала такая возможность, то мы могли бы оценивать желаемую вероятность с любой заданной точностью, применяя полиномиальное количество выборок. Тем не менее можно показать, что существование такой полипом иальной схемы аппроксимации невозможно. ОбратИтЕ ВНИМаНИЕ НатО, ЧтО В ЧИСЛО ПЕРЕМЕННЫХ Рагепба (я,) МОГут ВХОдИтЬ И скрытые переменные, и переменные свидетельства. В отличие от априорного рас- ПРЕДЕЛЕНИЯ Р(а), В РаСПРЕДЕЛЕНИИ .Я„н НЕКОТОРОЕ ВНИМаНИЕ УДЕЛЕНО СВИДЕтЕЛЬСтВУ: на значения сформированных выборок для каждой переменной я„кроме других предков г„, оказывает влияние само свидетельство.
С другой стороны, в распределении ~нн свидетельству уделяется меньше внимания, чем в истинном апостериорном распределении Р (и ~ е), поскольку в значениях сформированных выборок для каждой переменной гз игнорируются свидетельства', относящиеся к переменным, которые не являются предками ям Весовое значение правдоподобия ы представляет собой разность между фактическим и желаемым распределениями вероятностей сформированных выборок. Такой вес для данной конкретной выборки х, состоящий из значений в и е, является произведением значений правдоподобия каждой переменной свидетельства, если даны ее родительские переменные (причем некоторые или все эти переменные могут находиться среди переменных 2,); 690 Часть 'у'.
Неопрелеленные знания н рассуждения в условиях неопределенности = а' ~) Р(х,у,е) У и' Р(х,е) = Р(х)е) согласно уравнению З4.В Поэтому алгоритм оценки веса с учетом правдоподобия возвращает согласованные оценки. Поскольку в алгоритме оценки веса с учетом правдоподобия используются все сформированные выборки, он может оказаться гораздо более эффективным по сравнению с алгоритмом формирования выборок с исключением.
Тем не менее его недостатком является снижение производительности по мере увеличения количества переменных свидетельства. Это связано с тем, что в таком случае большинство выборок имеет очень низкие веса, поэтому в составе взвешенной оценки доминирует крошечная доля выборок, которые согласуются со свидетельством с правдоподобием, большим бесконечно малого. Эта проблема усугубляется, если переменные свилетельства расположены на последних местах в упорядочении переменных, поскольку в таком случае процесс формирования выборок представляет собой процесс моделирования, имеющий мало сходства с реальностью и имитируемый с помощью свидетельства. Вероятностный вывод по методу моделирования цепи Маркова В этом разделе описан алгоритм ев Монте-Карло с применением цепи Маркова (Маг)гоч спа)п Моп(е Саг1о — МСМС), предназначенный для вероятностного вывода в байесовских сетях.
Вначале опишем, какие действия выполняются в этом алгоритме, затем объясним, благодаря чему он работает и почему имеет такое сложное название. Алгоритм МСМС В отличие от других двух алгоритмов формирования выборок, которые вырабатывают каждое событие с нуля, в алгоритме МСМС каждое событие вырабатывается путем внесения случайного изменения в предыдущее событие. Поэтому сеть целесообразно рассматривать как находящуюся в конкретном текущем состоянии, заданном с помощью присваивания значения каждой переменной.
Переход в следующее состояние осуществляется путем случайного формирования выборки значения для одной из переменных Хз, отличных от переменных свидетельства, причем это значение обусловлено текущими значениями переменных в марковском покрытии переменной йп (Напомним, что, как было сказано на с. 1, марковское покрытие переменной состоит из ее родительских переменных, дочерних переменных и родительских переменных дочерних переменных.) Поэтому в алгоритме МСМС предусмотрено случайное блуждание по пространству состояний (пространству возможных полных присваиваний), в котором каждый раз изменяется значение одной переменной, но значения переменных свидетельства остаются зафиксированными.
Рассмотрим запрос Р(латп~ Бргтп)с1ег=сгие, иесагаее=сгие), примененный к сети, которая показана на рис. 14.9, а. Для переменных свидетельства аргун)г1ег и итесйгаэе зафиксированы их наблюдаемые значения, а скрытые переменные апис)у и яатп инициализированы случайным образом; допустим, что им присвоены значения сгие и га1эе соответственно. Таким образом, начальным 69! Глава 14. Вероятностные рассуждения состоянием является [ сгце, сгце, Га1зе, с гце]. После этого повторно выполня- ются описанные ниже этапы. 1. Формируется выборка для переменной С1оцс]у с учетом текущих значений переменных марковского покрытия: в данном случае выборка берется из Р ( С1 оцс1у] Яргйп]г1ег= сгце, дайн= га1зе) .
(Вскоре мы покажем, как рассчитать это распределение.) Предположим, что результатом является С1оцс[у=га1зе. В таком случае новым текущим состоянием становится [Еа1зе, сгце, Га1зе, сгце]. 2. Формируется выборка для переменной пайп с учетом текущих значений переменных марковского покрытия: в данном случае выборка берется из Р(дауп] с1оцс]у=йа1зе, Брг1п)г1ег=сгпе, й)ессгазз=сгце). Предположим, что эта операция приводит к получению пайп= сг пе. Новым текущим состоянием становится [га1зе, сгце, сгце, сгце]. Каждое состояние в пространстве состояний, посещенное в ходе этого процесса, представляет собой выборку, которая вносит свой вклад в оценку вероятности переменной запроса пайп.
Если в данном процессе посещаются 20 состояний, в которых переменная дабл принимает истинное значение, и 60 состояний, в которых переменная кайл становится ложной, то ответом на запрос становится Могзпа112е (<20, 60>) =<О. 25, О. 75>, Полный алгоритм показан в листинге 14 6. Листинг 14.6. Алгоритм МСМС приближенного вероятностного вывода в байесовскнх сетях бнпсввоп МСМо-язх(Х, е, Ьп, и) гегчгпв оценка значения Р(Х[е) 1оса1 чаг1аЬ1евг Б[Х], вектор результатов подсчетов по Х, первоначально равный нулю 2, переменные в сети Ьп, отличные от переменных свидетельства х, текуыее состояние сети, первоначально скопированное из е инициализировать х случайными значениями переменных из 2 гог У = 1 Ео )Ч ао гог еаси 2, ап Я ао выполнить выборку значения переменной Я, в векторе х из Р(Я,]юЬ(яь)), если даны значения мв(аь) в векторе х и[х] ь- и[х]+1, где х представляет собой значение переменной х в множестве х гевсгп Могиа11зе(Б[Х]) Обоснование правильности работы алгоритма МСМС В этом разделе будет показано, что алгоритм МСМС возвращает согласованные оценки для апостериорных вероятностей.
Материал, изложенный в данном разделе, является весьма формальным, но основное утверждение в нем несложно: са процесс формирования выборок переходит в "динамическое равновесие", в котором в конечном итоге доля времени, проведенного в кахгдам состоянии, точно пропорциональна алостериоряои вероятности этого состояния. Такое замечательное свойство является следствием конкретной сь переходной вероятности, с которой данный процесс переходит из од- 692 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности ного состояния в другое и которая определена условным распределением, заданным с учетом марковского покрытия переменной, для которой формируется выборка. Предположим, что с((х — >х' ) — вероятность того, что в этом процессе произойдет переход из состояния х в состояние х'. Эта переходная вероятность определяет информационную структуру, заданную на пространстве состояний, которая называется 'з.
цепью Маркова. (Цепи Маркова играют также важную роль в главах 15 и 17.) Теперь предположим, что мы развернули цепь Маркова на с этапов, и допустим, что и, (х) — вероятность того, что система находится в состоянии х во время С. Аналогичным образом, допустим, что псы (х ' ) — вероятность пребывания системы в состоянии х' во время с+1. Если дано значение и, (х), то значение псы (х' ) можно рассчитать путем суммирования по всем состояниям, в которых система может находиться во время с, вероятностей пребывания в этом состоянии, умноженных на вероятности осуществления перехода в состояние х ', следующим образом: псы(к') = ~~) п,(х)гу(х — гк') х Цепь называется достигшей своего ох стационарного распределения (гпайопагу г()з(пЬц(1оп), если и, = и„,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
