Формирование выборок с исключением в байесовских сетях

Формирование выборок с исключением представляет собой общий метод получения выборок на основании распределения, для которого трудно получить выборки, если дано распределение, позволяющее легко сформировать выборки. В своей простейшей форме этот метод может использоваться для вычисления условных вероятностей, т.е. для определения вероятностей Р(х|е). Алгоритм Rejection-Sampling приведен в листинге 14.4. Вначале он формирует выборки из априорного распределения, определяемого сетью, а затем исключает все те выборки, которые не соответствуют свидетельству. Наконец, формируется оценка Р(Х=х|е) путем подсчета того, насколько часто событие х=х встречалось в оставшихся выборках.

Листинг 14.4. Алгоритм формирования выборок с исключением для получения ответов на запросы, если даны свидетельства в байесовской сети

Допустим, что Р(Х|е) — оцениваемое распределение, которое возвращено алгоритмом. Из определения алгоритма получаем следующее:

С помощью уравнения 14.5 это соотношение может быть преобразовано в следующее:

Таким образом, алгоритм формирования выборок с исключением вырабатывает согласованную оценку истинной вероятности.

Продолжая пример, приведенный на рис. 14.9, а, предположим, что необходимо оценить вероятность с использованием 100 выборок.

Допустим, что из 100 сформированных выборок 73 соответствуют событию

Sprinkler= false и исключаются, а для 27 имеет место Sprinkler=true; из 27 выборок в 8 наблюдается событие Rain=true, а в 19 — Rain= false. Поэтому получаем следующее:

Правильным ответом является <0 . 3 , 0 . 7>. В ходе дальнейшего накопления все большего количества выборок эта оценка сходится к правильному ответу. Среднеквадратичное отклонение ошибки в каждой оценке вероятности будет пропорционально, где η — количество выборок, используемых для получения оценки.

Самым большим недостатком алгоритма формирования выборок с исключением является то, что в нем приходится исключать слишком много выборок! Доля выборок, согласованных со свидетельством е, уменьшается экспоненциально по мере увеличения количества переменных свидетельства, поэтому данная процедура становится неприменимой для решения сложных задач.