Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 187
Текст из файла (страница 187)
Предположим, что общее количество выборок равно в), а также допустим, что в)(х,, ..., х„) — частота конкретного события х,, ..., х„. Следует полагать, что эта частота сойдется в пределе к ее ожидаемому значению, соответствующему вероятности сформированной выборки: №р(х, ...,х ) 11т — Ярк(хр,...,х ) = Р(«и.,.,хк) к-:, ар (14.4) Например, рассмотрим событие, полученное ранее: (гхие,ха1ее, схие, Охи е] . Вероятность формирования выборки для этого события такова: Ярр(схие, ха1ее, ехие, Сгие) = 0.5«0. 9«0.
8«0.9 = 0.324 Поэтому следует полагать, что в пределе, при очень больших значениях и, около 32,4% выборок будут относиться к этому событию. В последующем изложении мы будем использовать знак приближенного равенства (=) для обозначения соотношения, имеющего именно этот смысл, — что оцениваемая вероятность становится точной при больших пределах количества выборок.
Такая оценка называется 'ъ. согласованной, Например, может быть получена согласованная оценка вероятности любого частично заданного события х,, ...,х„, где рв < и, следующим образом: Р(хр,...,х ) = №к(«ы...,х )!И (14.5) Это означает, что вероятность события можно оценить с помощью деления количества выборок частично заданного события на количество всех событий, получен- 4. Выборка из распределения Р( р(егохаее~ Брх1п)с1ех=1а1ее, яаха=гхие) =< О . 9, О .
1>; предположим, что она возвращает сгие. В данном случае алгоритм Рг1ог-яагвр1е возвращает событие (схие, Еа1ее, схие, схие]. Можно легко показать, что алгоритм Рг1ог-яарвр1е формирует выборки на основе априорного совместного распределения, которое задано рассматриваемой сетью. Прежде всего предположим, что Ярк(х,, ...,х„) представляет собой вероятность того, что конкретное событие сформировано алгоритмом Рг1ог-Бавр1е.
Достаточно лишь проанализировать сам процесс формирования выборки, чтобы убедиться в справедливости следующего соотношения, поскольку каждый этап формирования выборки зависит только от значений родительских переменных: 686 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности ных в процессе формирования выборок. Например, если на основании сети с описанием опрыскивателя (см. рис. 14.9, а) сформирована 1000 выборок и для 511 из них справедливо выражение дауд= слое, то оценка вероятности дождя, которая записывается как р (найп= сгие), равна 0,5! 1.
Формирование выборок с исключением в байесовских сетях ск Формирование выборок с исключением представляет собой общий метод получения выборок на основании распределения, для которого трудно получить выборки, если лано распределение, позволяющее легко сформировать выборки. В своей простейшей форме этот метод может использоваться для вычисления условных вероятностей, т е.
для определения вероятностей Р(х!е) . Алгоритм кейесвйопоатр11пд приведен в листинге 14.4. Вначале он формирует выборки из априорного распределения, определяемого сетью, а затем исключает все те выборки, которые не соответствуют свидетельству. Наконец, формируется оценка р (х=х!е) путем подсчета того, насколько часто событие Х=х встречалось в оставшихся выборках. Листинг 14.4.
Алгоритм формирования выборок с исключением длк получения ответов ка запро- сы, если даны свидетельства в байесовской сети Емпссьоп Кеэесоьоп-эащр11пд(Х, е, )оп, И) кесцкпк оценка значения Р(Х]е) 1зчкзее: х, переменная запроса е, свидетельство, определяемое как некоторое событие .Ьп, байесовская сеть т(, общее количество выборок, которые должны быть сформированы 1оса1 чек1аЬ1ее: И, вектор результатов подсчетов по Х, первоначально равный нулю Еок 5 = 1 Ео (у бо х ь- РгЕОà — Бащр1е()оп) ЕЕ выборка х согласуется со свидетельством е Епеп И[к] <†И(х)е1, где х представляет собой значение переменной Х в множестве х кесмкп Ноппа11ке(И[Х]) Допустим, что й ( х! е) — оцениваемое распределение, которое возвращено алгоритмом.
Из определения алгоритма получаем следующее: И„(Х, е) Р(х(е) = а и, (х,е) н~~ (е) С помощью уравнения 14.5 это соотношение может быть преобразовано в следующее: Р(х,е) в(х]е) =, ' = в(х(е) Таким образом, алгоритм формирования выборок с исключением вырабатывает согласованную оценку истинной вероятности. Продолжая пример, приведенный на рис. 14.9, а, предположим, что необходимо оценить вероятность и (найп! Бргйп]с1ег=сгце) с использованием 100 выборок.
Допустим, что из 100 сформированных выборок 73 соответствуют событию 687 Глава 14. Вероятностные рассуждения яртуп)<1ет=йа1зе и исключаются, а для 27 имеет место ярт1п7с1ет=стие; из 27 выборок в 8 наблюдается событие кауп=стие, а в )9 — лауп=Еа1зе. Поэтому получаем следуюшее: Р(надя)дртйп)с1ет=етие) = Нотта1зте(<8,19>) = <0.298,0.704> Правильным ответом является <О. 3, О. 7>. В ходе дальнейшего накопления все большего количества выборок эта оценка сходится к правильному ответу.
Среднеквадратичное отклонение о)либки в каждой оценке вероятности будет пропорционально 1/т)п, где п — количество выборок, используемых для получения оценки. Самым большим недостатком алгоритма формирования выборок с исключением является то, что в нем приходится исключать слишком много выборок! Доля выборок, согласованных со свидетельством е, уменылается экспоненциально по мере увеличения количества переменных свидетельства, поэтому данная процедура становится неприменимой для решения сложных задач.
Обратите внимание на то, что процесс формирования выборок с исключением весьма напоминает процесс оценки условных вероятностей непосредственно по данным, полученным из реального мира. Например, чтобы оценить вероятность дождя после того, как накануне вечером наблюдался красный закат, Р(пайп) лег19мулс)чйрлс=стие), можно подсчитать, насколько часто наблюдался дождь после красного заката, игнорируя данные о тех вечерах, когда закат не был красным. (Поэтому в данном случае роль алгоритма формирования выборок играет сама природа.) Безусловно, для проведения таких наблюдений может потребоваться много времени, если закат бывает красным очень редко, и в этом состоит недостаток процедуры формирования выборок с исключением.
Оценка веса с учетом правдоподобия В методе 'ск оценки веса с учетом правдоподобия преодолен указанный недостаток метода формирования выборок с исключением благодаря тому, что в нем вырабатываются только события, согласованные со свидетельством е. Начнем с описания того, как работает алгоритм, затем покажем, что он работает правильно, т.е. вырабатывает согласованные оценки вероятности. В алгоритме Ь1)<е11Лоос(-(чеьдЛсйпд, приведенном в листинге 14.5, значения для переменных свидетельства ц фиксируются и формируются выборки только для оставшихся переменных х и ц Это позволяет гарантировать, что каждое выработанное событие будет согласованным со свидетельством. Но не все события являются равноправными.
Поэтому перед подведением итогов подсчетов в распределении для переменной запроса каждое событие взвешивается с учетом правдоподобия того, что событие согласуется со свидетельством. Такое правдоподобие измеряется с помощью произведения условных вероятностей для каждой переменной свидетельства, если даны ее родительские переменные. Интуитивно ясно, что события, в которых фактическое свидетельство кажется маловероятным, должны получать меньший вес. Листинг 14.5.
Аагорнтм оценки веса с учетом правдоподобия, предназначенный для вероятност- ного вывода в байесоаскнх сетях тцпстйоп Ьйке1збоой-пеьдЫЫд(Х, а, Ьп, ЗЛ теситпн опенка значения Р(Х)е) Ьпрцсп: Х, переменная запроса е, свидетельство, определяемое как некоторое событие 688 Часть у'. Неопределенные знания и рассуждения в условиях неопределенности Ьп, байесовская сеть М, обшее количество выборок, которые должны быть сформированы 1ооа1 чагьеЪ1евс И, вектор взвешенных результатов подсчетов по Х, первоначально равный нулю Еог 1 = 1 Со В) с(о х, ы ь- Ие19ЬСеб-валр1е(Ьп) М(х) с- И[х)еы, где х представляет собой значение переменной Х в множестве х гегигп Ноттпа1).ве(И(Х)) Еипоевоп Ыетдисес(-эашр1е(Ьп, е) геепгпе событие х и вес ы х +- событие с и элементами; и с в 1 Еог 1 = 1 Со и ао ЕЕ Х, имеет значение х, Еп свидетельство е еьеп и с- ы<Р(х,=хПратепсз(х.) ) езее х, с в случайная выборка из Р(Хс[ратепез(Х,)) гевигп х, ь Применим этот алгоритм к сети, показанной на рис.
14.9, а, на примере получения ответа на запрос и (дадю ~ Брг1п)с1ег= сгие, )уессгааа= сгие) . Этот процесс происходит следующим образом: вначале вес ы устанавливается равным 1,О, затем вырабатывается событие, как описано ниже. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
