Европа и Россия XVIII век Архитектура Рококо Скульптура Франсуа Буше Декоративно-прикладное искусство Севрский фарфор Бытовой жанр Собор Святого Павла Палладианство Пейзажный (английский) парк Британский музей в Лондоне Летний сад Зимний дворец

Рекомендуемая литература

В своей книге [Pearl, 1988] Перл уделяет основное внимание методам, основанным на Байесовском подходе, демонстрируя их возможности на множестве примеров, взятых из различных областей искусственного интеллекта. Эту книгу можно рекомендовать в качестве отправной точки для детального изучения проблемы обработки неопределенности в задачах искусственного интеллекта, поскольку изложенный в ней материал является самодостаточным. Структура книги позволяет читателям с разным уровнем подготовки выбирать нужный для себя материал. Более поздняя работа [Pearl, 1997] содержит описание последних исследований в этой области, включая и теорию сетей доверия. Среди других книг на эту тему я бы выделил [Jensen, 1996] и [Shafer and Pearl, 1990].

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

От эксперта также требуется выделить множество гипотез S, на которые непосредственно распространяется определенное множество свидетельств Е. Если свидетельства из Е непосредственно влияют на гипотезы из S, то должен существовать какой-то причинный механизм, связывающий каждый член множества S со свидетельствами, причем он является уникальным для каждого из них. Однако сами по себе свидетельства в множестве Е не несут никакой информации, которая позволила бы нам отдать предпочтение одному из членов S перед другими.

Это отображение множеств друг на друга позволяет ввести понятие условной независимости между свидетельствами и отдельными гипотезами hi:

Р(Е | S, hi) = Р(Е | S, h1), для всех hi S.

С помощью отношения вероятностей можно количественно оценить степень, с которой свидетельства подтверждают или опровергают множество гипотез S:

лS=[P(E|S)] / [P(E|-S)].

Влияние свидетельств Е на множество S вычисляется следующим образом. Каждая отдельная гипотеза hi, принадлежащая множеству S, получает вес Wi = лS , в то время как каждая гипотеза из дополняющего множества SC получает вес Wi = 1. Все это выполняется на фазе распределения весов.

Затем, когда наступает фаза обновления, вычисляется новое значение функции доверия ВЕL'(hi) по ее прежнему значению ВЕL(hi):

BEL'(hi) = P(hi | Е) = asWiВЕL(hi),

где as — коэффициент нормализации, заданный соотношением

as=( i[WiBEL'(hi))-1.]

Таким образом, степень доверия, назначенная множеству гипотез, распределяется между членами этого множества как функция их априорных вероятностей. В то же время степень доверия, назначенная группе гипотез, является суммой соответствующих показателей элементов этой группы. Обновление значений показателей доверия может выполняться рекурсивно, т.е. апостериорные оценки, полученные на основании одних свидетельств, могут использоваться в качестве априорных оценок для следующего цикла обновления при получении новых свидетельств.

Вся схема вычислений основана на предположении об условной независимости и соблюдении симметричности множеством SC, дополняющим S. Из соотношения

Р(Е | SC, hi) = Р(Е | SC, hi)

для всех

hi SC следует,

что Р(Е | hi) = Р(Е | S), если hi, hi S, иначе Р(Е | SC).

Из этого соотношения и правила Байеса следует, что P(h,| Е) = asXsP(h,), если Л, е S, иначе asP(h,).

Но, хотя Перл использует формализм Байеса, частичное свидетельство в пользу какой-либо гипотезы не может быть истолковано и как частичная поддержка отрицания этой гипотезы. Свидетельство в пользу подмножества гипотез S не может быть истолковано как свидетельство в пользу дополнения к этому подмножеству 5е.

Распределение свидетельств в пользу подмножества между отдельными гипотезами восстанавливает точечное распределение вероятностей на пространстве гипотез, но это происходит за счет точности оценок для отдельных гипотез. Перл утверждает, что нет необходимости распределять общий показатель, взятый для всего подмножества S, на его элементы до тех пор, пока не будут получены дополнительные свидетельства (или все возможные). Нормализацию также можно отложить до тех пор, пока полученные свидетельства не подтолкнут систему к выделению определенных гипотез (возможно, разных). Например, если получены свидетельства Е1, ..., Еn соответственно в пользу гипотез S1, ..., Sn, то веса будут комбинироваться мультипликативно

Wi(E1,...,En)=W1,i,W2,i... Wn,i

где

Wk,i Sk если hi Sk,

иначе 1 .

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

21.1. Байесовские сети

В работе [Pearl, 1988] описан формализм, которому автор присвоил название Байесовские сети. Этот механизм можно рассматривать как обобщение описанных в данном разделе иерархических сетей доверия. В Байесовской сети дуги между узлами также представляют причинные зависимости, но допускается ситуация, когда некоторые узлы имеют множество родителей, причем структура сети может содержать петли. Обновление оценок доверия выполняется с помощью передачи сообщений, как и в случае строгой иерархической организации, хотя действие этого механизма очевидно только для полидеревьев, т.е. сетей, в которых между любыми двумя узлами существует единственный путь.

Представляет интерес сравнение формализма Перла и теории Демпстера — Шефера.

В своей книге [Pearl, 1988] Перл совершенно справедливо отмечает, что теория Демпстера—Шефера основана на неполной вероятностной модели, а потому может дать только частичные ответы. Вместо того чтобы непосредственно оценить, насколько близка гипотеза к тому, чтобы ее можно было считать истинной, эта теория говорит, как сильно полученное свидетельство должно продвинуть нас к убеждению, что данная гипотеза истинна. В этом отношении теория Демпстера—Шефера значительно больше напоминает объективистские методы проверки значимости с использованием доверительных интервалов, чем субъективистские методы на основе Байесовского подхода [Neapolitan, 1990].

Но, несмотря на отмеченные различия, в обоих подходах есть много общего, почему мы и рассматриваем их совместно в рамках одной главы. Ассоциирование свидетельств с подмножествами гипотез в рамках метода Перла не противоречит отображению одного множества на другое в теории Демпстера—Шефера. Оба варианта можно рассматривать как использование метафоры "массового распределения" в том смысле, что основное внимание уделяется распределению полученных свидетельств в контексте структурированного пространства альтернатив, причем оба метода позволяют вычислять значения функции доверия на основе простых вероятностных оценок.

Шаг 4. выполнить анализ пар множества K по правилу:
"если существуют дизъюнкты Di и Dj, один из которых (Di) содержит литеру А, а другой (Dj) - контрарную литеру 1а, то соединить эту пару логической связкой дизъюнкции (Di v Dj) и сформировать новый дизъюнкт - резольвенту, исключив контрарные литеры А и 1А;
Шаг5. если в результате соединения дизъюнктов, содержащих контрарные литеры, будет получена пустая резольвента - П, то конец (доказательство подтвердило противоречие), в противном случае включить резольвенту в множество дизъюнктов K и перейти к шагу 4.
Пример : Работа автоматического устройства, имеющего три клапана А, В и С, удовлетворяет следующим условиям: если не срабатывают клапаны А или В или оба вместе, то срабатывает клапан С; если срабатывают клапаны А или В или оба вместе, то не срабатывает клапан С. Следовательно, если срабатывает клапан С, то не срабатывает клапан А Решение типовых задач по математике и физике