Оценка веса с учетом правдоподобия
В методе оценки веса с учетом правдоподобия преодолен указанный недостаток метода формирования выборок с исключением благодаря тому, что в нем вырабатываются только события, согласованные со свидетельством е. Начнем с описания того, как работает алгоритм, затем покажем, что он работает правильно, т.е. вырабатывает согласованные оценки вероятности.
В алгоритме Likelihood-Weighting, приведенном в листинге 14.5, значения для переменных свидетельства Е фиксируются и формируются выборки только для оставшихся переменных Хи Y. Это позволяет гарантировать, что каждое выработанное событие будет согласованным со свидетельством. Но не все события являются равноправными. Поэтому перед подведением итогов подсчетов в распределении для переменной запроса каждое событие взвешивается с учетом правдоподобия того, что событие согласуется со свидетельством. Такое правдоподобие измеряется с помощью произведения условных вероятностей для каждой переменной свидетельства, если даны ее родительские переменные. Интуитивно ясно, что события, в которых фактическое свидетельство кажется маловероятным, должны получать меньший вес.
Листинг 14.5. Алгоритм оценки веса с учетом правдоподобия, предназначенный для вероятностного вывода в байесовских сетях
function Likelihood-Weighting{X, е, bn, N) returns оценка значения Р{Х\е) inputs: X, переменная запроса
е, свидетельство, определяемое как некоторое событие
bn, байесовская сеть
N, общее количество выборок, которые должны быть сформированы local variables: W, вектор взвешенных результатов подсчетов по X, первоначально равный нулю
for j = 1 to N do
x, w
x
Применим этот алгоритм к сети, показанной на рис. 14.9, я, на примере получения ответа на запрос В (Rain | Sprinkler=true, WetGrass=true). Этот процесс происходит следующим образом: вначале вес w устанавливается равным 1,0, затем вырабатывается событие, как описано ниже.
1. Выборка из распределения Р (Cloudy) =<0 . 5, 0 . 5>; предположим, что она возвращает значение true.
2. Sprinkler — переменная доказательства со значением true. Поэтому мы устанавливаем:
w <— WX.P(Sprinkler= true | Cloudy= true) =0 .1
3. Выборка из распределения P(Rain\Cloudy=true) =<0 .8, 0 .2>; предположим, что она возвращает значение true.
4. WetGrass — переменная доказательства со значением true. Поэтому мы устанавливаем:
w <— WXP(WetGrass=true|Sprinkler=true,Rain=true)=0.099
Теперь алгоритм Weighted-Sample возвращает событие [true, true, true, true] с весом 0,099, и данные об этом событии подытоживаются с учетом условия Rain= true. Этот вес является низким потому, что событие описывает пасмурный день, в который вероятность применения опрыскивателя является весьма небольшой.
Чтобы понять, как работает алгоритм оценки веса с учетом правдоподобия, начнем с изучения сформированного с помощью выборок распределения Ss для функции Weighted-Sample. Напомним, что переменные свидетельства Е зафиксированы со значениями е. Обозначим все прочие переменные как Z, иными словами, z={X}uY. В алгоритме выборки для каждой переменной из z, если даны ее родительские значения, формируются следующим образом:
Обратите внимание на то, что в число переменных Parents (z±) могут входить и скрытые переменные, и переменные свидетельства. В отличие от априорного распределения P(z), в распределении Ss некоторое внимание уделено свидетельству: на значения сформированных выборок для каждой переменной zL, кроме других предков zi} оказывает влияние само свидетельство. С другой стороны, в распределении Sws свидетельству уделяется меньше внимания, чем в истинном апостериорном распределении Р (z | е), поскольку в значениях сформированных выборок для каждой переменной zL игнорируются свидетельства6, относящиеся к переменным, которые не являются предками zL.
Весовое значение правдоподобия w представляет собой разность между фактическим и желаемым распределениями вероятностей сформированных выборок. Такой вес для данной конкретной выборки х, состоящий из значений z и е, является произведением значений правдоподобия каждой переменной свидетельства, если даны ее родительские переменные (причем некоторые или все эти переменные могут находиться среди переменных zL):
m
w{z,e) = J~J P(ei \parents{Ei) ) (14.7)
i = l
Умножая уравнения 14.6 и 14.7, можно определить, что соотношение для взвешенной вероятности выборки имеет следующую особенно удобную форму, поскольку эти два произведения охватывают все переменные, заданные в сети:
1 m
Јws (z,e) w(z,e) = J~J P (zi | parents (Zi) ) J~J P {ei\parents {Ei) )
i=l i=l
= P(z,e) (14.8)
Это позволяет использовать для вычисления совместной вероятности уравнение 14.1.
Теперь можно легко показать, что оценки весов, полученные с учетом правдоподобия, являются согласованными. Для любого конкретного значения х переменной X оценка апостериорной вероятности может быть рассчитана следующим образом:
Поэтому алгоритм оценки веса с учетом правдоподобия возвращает согласованные оценки.
Поскольку в алгоритме оценки веса с учетом правдоподобия используются все сформированные выборки, он может оказаться гораздо более эффективным по сравнению с алгоритмом формирования выборок с исключением. Тем не менее его недостатком является снижение производительности по мере увеличения количества переменных свидетельства. Это связано с тем, что в таком случае большинство выборок имеет очень низкие веса, поэтому в составе взвешенной оценки доминирует крошечная доля выборок, которые согласуются со свидетельством с правдоподобием, большим бесконечно малого. Эта проблема усугубляется, если переменные свидетельства расположены на последних местах в упорядочении переменных, поскольку в таком случае процесс формирования выборок представляет собой процесс моделирования, имеющий мало сходства с реальностью и имитируемый с помощью свидетельства.