Формирование выборок с исключением в байесовских сетях
Формирование выборок с исключением представляет собой общий метод получения выборок на основании распределения, для которого трудно получить выборки, если дано распределение, позволяющее легко сформировать выборки. В своей простейшей форме этот метод может использоваться для вычисления условных вероятностей, т.е. для определения вероятностей Р(х\в). Алгоритм Rejection-Sampling приведен в листинге 14.4. Вначале он формирует выборки из априорного распределения, определяемого сетью, а затем исключает все те выборки, которые не соответствуют свидетельству. Наконец, формируется оценка Р(Х=х\е) путем подсчета того, насколько часто событие х=х встречалось в оставшихся выборках.
Листинг 14.4. Алгоритм формирования выборок с исключением для получения ответов на запросы, если даны свидетельства в байесовской сети
function Rejection-Sampling(X, е, Ьп, N) returns оценка значения Р(Х\е) inputs: X, переменная запроса
е, свидетельство, определяемое как некоторое событие Ьп, байесовская сеть
N, общее количество выборок, которые должны быть сформированы local variables: N, вектор результатов подсчетов по X, первоначально равный нулю
for j = 1 to N do
x <— Prior-Sample{Ьп)
if выборка x согласуется со свидетельством е then
N[x] <— N[x]+1, где х представляет собой значение переменной X в множестве х
return Normalize(N[X] )
Допустим, что Р(Х\е) — оцениваемое распределение, которое возвращено алгоритмом. Из определения алгоритма получаем следующее:
*U|e) = сс NPS(X,e) = N*ef
С помощью уравнения 14.5 это соотношение может быть преобразовано в следующее:
Р(Х,е)
*(Xle) e Р(е) = р<*1е>
Таким образом, алгоритм формирования выборок с исключением вырабатывает согласованную оценку истинной вероятности.
Продолжая пример, приведенный на рис. 14.9, я, предположим, что необходимо оценить вероятность Р (Rain | Sprinkler true) с использованием 100 выборок. Допустим, что из 100 сформированных выборок 73 соответствуют событию
Sprinkler= false и исключаются, а для 27 имеет место Sprinkler=true; из 27 выборок в 8 наблюдается событие Rain=true, а в 19 — Rain= false. Поэтому получаем следующее:
P(Rain\Sprinkler=true) ~ Normalize(<8,19>) = <0.296, О.704>
Правильным ответом является <0 . 3 , 0 . 7>. В ходе дальнейшего накопления все большего количества выборок эта оценка сходится к правильному ответу. Среднеквадратичное отклонение ошибки в каждой оценке вероятности будет пропорционально l/sjn, где п — количество выборок, используемых для получения оценки.
Самым большим недостатком алгоритма формирования выборок с исключением является то, что в нем приходится исключать слишком много выборок! Доля выборок, согласованных со свидетельством е, уменьшается экспоненциально по мере увеличения количества переменных свидетельства, поэтому данная процедура становится неприменимой для решения сложных задач.
Обратите внимание на то, что процесс формирования выборок с исключением весьма напоминает процесс оценки условных вероятностей непосредственно по данным, полученным из реального мира. Например, чтобы оценить вероятность дождя после того, как накануне вечером наблюдался красный закат, P{Rain | RedSkyAtNight=true), можно подсчитать, насколько часто наблюдался дождь после красного заката, игнорируя данные о тех вечерах, когда закат не был красным. (Поэтому в данном случае роль алгоритма формирования выборок играет сама природа.) Безусловно, для проведения таких наблюдений может потребоваться много времени, если закат бывает красным очень редко, и в этом состоит недостаток процедуры формирования выборок с исключением.