Типы неточного вывода

PROSPECTOR. Вероятностные методы принятия решений основаны на байесовском подходе. Для задач вывода в ИС этот подход был развит при работе над системой PROSPECTOR JDuda et al., 1976]. В системе PROSPEC-106

TOR в качестве весов, приписанных высказываниям, выступают вероятности соответствующих событий. Множества событий организованы в сети вывода, по которым производится пересчет априорных вероятностен высказываний в апостериорные. Правила в системе имеют вид «если Е, то Я» и «если Е, то #>, причем в сети вывода для каждой пары высказываний {£, Н} эти правила присутствуют или отсутствуют одновременно. Вид функции пересчета /(•) по­стулируется, т. е. для конъюнкции и дизъюнкции используются формулы не­четкой логики: Р(А\/В)=т&х(Р(А), Р{В)), Р(А&В)=тЩР(А), Р{В)). По­пытки формального обоснования функций h(-) и g(-) связаны с принятием предположений о независимости: а) Р(Н\Е&Е')=Р(И\Е) и Р(Н\Е&Е') = в=Р(Н\Е), где £'— свидетельство, «опосредованно» (через Е) связанное пра­вилами с Я;_ б) Р{Е_Х&Е₂\Н)=Р{Е₁\Н)Р(Е₂\Н) и Р(Е₁&Е₂\Я) = =P{Ei\H)P(E₂\H). Однако предположения б) [Хачатрян, 1987] являются слишком сильными, фактически сводя объединение свидетельств к выбору од­ного из них. Таким образом, механизм неточного вывода в системе PROSPEC­TOR несмотря на свой вероятностный характер является, по сути, эвристиче­ским.

Схема Пиэрла. Байесовские методы, неточного вывода получили более глу­бокое и формально обоснованное развитие в [Kim et al., 1983; Pearl, 1986].

Согласно этим работам знания людей о проблемной области (проблеме) можно представить в виде совместного распределения вероятностей Р(х_и~-..,х_п) на множестве пропозиционных переменных (т. е. переменных, значения­ми которых являются высказывания) х\,...,x_n- Интерес представляет вычисление условных вероятностей Р(Н\Е), где Я(гипотеза) и £ (свидетельство)—некото­рые композиционные высказывания, составленные из элементарных (т. е. типа {значение xt есть Vj'}). Все условные вероятности такого типа можно полу­чить из совместного распределения вероятностей Р{х\,..., х_п), однако такое направление преобразования информации не соответствует поведению челове­ка, который не оперирует полным совместным распределением или маргиналь­ными вероятностями высокого порядка (например, Р(х_и...,х_п~}))- Элементар­ными блоками, из которых строится общее знание человека, являются марги­нальные вероятности низкого порядка (например, P(xi), P(xi, Xj)) и условные вероятности, определенные на небольших множествах высказываний.

Пусть фиксирован некоторый произвольный порядок d переменных Х\,......,*«, каждой из которых соответствует вершина в графе. Тогда Р(х_и..., х_п) = = P{Xn\x_n-\,:.,X\)...P(x₂\xi)P(xi}. Пусть Si^{xu..., Xi-i) —минимальное под­множество вершин множества {х\,..., xi-i), удовлетворяющее условию P(xi\Si) =P(Xi\xi~u..., xi}. Можно показать, что такое подмножество единст­венно. Проведем от вершин множества S, направленные дуги к вершине хи Осуществив эту операцию для всех вершин xt, получим ориентированный ацик­лический граф, в котором отражены многие соотношения независимости, не­явно содержащиеся в P(xi,...,x_n). Наоборот, порядок d переменных и ориен­тированный ациклический граф с совокупностью условных распределений вероятностей однозначно определяют распределение Р(х_и...,х_п)- Такой «локаль­ный» способ определения Р(хи..., х_п) соответствует заданию системы вероят­ностных суждений, которыми наиболее естественно оперируют эксперты. Графы (а точнее, гиперграфы), построенные описанным способом, носят название се­тей доверия или байесовских сетей.

Процесс рассуждения (вывода) в системе знаний сопровождается распро­странением по сети влияния вновь поступивших свидетельств. Введение в си­стему знаний новых данных приводит к возникновению переходного процесса распространения по сети влияния вновь поступившего свидетельства. После завершения переходного процесса каждому высказыванию (ассоциированному с вершинами графа) оказывается приписана апостериорная вероятность

Bel (Vj^l) = P(Vj^l | D), где D — объединение всех поступивших на данный -момент в систему данных. Механизм пересчета вероятностей имеет следующую структуру. С каждой вершиной в сети ассоциирован процессор, который полу­чает сообщение от соседних (связанных с ним дугами) процессоров, осущест-

вляет пересчет апостериорных вероятностей ВЕЦК/) для всех возможных зна­чений Vj' данной переменной xi и посылает соседним вершинам ответные сообщения. Деятельность процессора инициируется нарушением условий согласо­ванности с состояниями соседних процессоров и продолжается до восстановле­ния этих условий. Правомочность данной процедуры строго обоснована для односвязных сетей, т. е. сетей, в которых от одной вершины к другой ведет не более одного ненаправленного пути. Обобщение метода пересчета на много­связные сети осуществляется преобразованием их структуры в древовидную и требует выполнения ряда ограничительных условий [Pearl, J986J.

MYCIN (EMYCIN). К байесовским методам неточного вывода примыкают механизмы пересчета весов, разработанные в системах MYCIN и EMYCIN [Shortliffe et al., 1975; Buchanan et a]., 1984]. Любое высказывание (а не толь­ко правило) в этих системах полагается условным по форме, причем в каче­стве условия высказывания, не являющегося правилом, принимается вся имею­щаяся на данный момент в базе данных информация. Высказываниям припи­сываются веса, называемые факторами уверенности. Фактор уверенности (CF) определяется в виде разности CF[H, Е]—МВ[Н, Е] — MD[H, E], где МВ[Н, E](MD[H, E]) —мера возросшей веры (возросшего неверия) в гипоте­зу Н на основе свидетельства Е. Меры MB и MD определяются через вероят­ности Р{Н\Е) и Р(Н), причем 0<MB,MD<\. — l^CF^l. В зависимости от того, является ли вновь поступившее свидетельство подтверждающим или оп­ровергающим гипотезу, производится пересчет приписанной гипотезе меры MB или MD. Вид функции пересчета /(•) для конъюнкции и дизъюнкции аналоги­чен используемой в системе PROSPECTOR, а вера в отрицание гипотезы оп­ределяется из соотношения МВ[Й, E]=MD[H, E]. Функция п(-) определяет­ся произведением фактора уверенности, приписанного правила и веры в истин­ность свидетельства. Объединение свидетельств посредством функции g(-) осуществляется по формулам, неявно опирающимся на предположения услов­ной независимости свидетельств либо по гипотезе, либо по ее отрицанию [Ха-чатрян, 1987]. В системе EMYCIN разделение фактора уверенности на две меры MB и MD устранено, что приводит к изменению функций пересчета.

Механизмы неточных рассуждений систем MYCIN и EMYCIN не требуют: 1) априорной жесткой фиксации сетей вывода: правила вместе с приписанны­ми им факторами уверенности можно модифицировать, удалять или добавлять в базу знаний, не заботясь об обеспечении необходимой для пересчета инфор­мации; 2) задания априорных вероятностей, так как меры CF, MB и MD акку­мулируют как априорную, так и апостериорную информацию; однако отказ от явного использования в процессе пересчета априорных вероятностей может приводить к таким нежелательным последствиям, как принятие гипотезы с меньшей апостериорной вероятностью.

Теория Демпстера—-Шефера (ТДШ). Эта теория [Shafer, I976] была разработана с целью обобщения вероятностного подхода к описанию неопре­деленности и связана с попыткой освободиться от догмата аксиом теории ве­роятностей при описании субъективной веры людей.

Рассмотрим конечное множество 0 взаимно исключающих друг друга воз­можностей, именуемое в ТДШ фреймом различения. На множестве всех под­множеств 8 как на множестве элементарных событий зададим базисное распре­деление вероятностей m: 2Р->[0 1] m(0)O J

(Л)

Лее

понимается как мера доверия, приписанная А. Мера общего доверия* припи­санная Л, определяется соотношением Ве1(Л) = ^т(В), где Bel: 2 -*-[0, I]—

B(ZA

функция доверия, характеризующая веру субъекта в истинность события Ле8. Наряду с величиной Bel (А) существенную информацию о событии А несет значение 1—Ве1(Л"), определяющее его меру правдоподобия (Р1(Л). Меры Bel (Л) и Р1(Л) называют соответственно нижними и верхними вероятностями, 108

что оправдано, в частности, неравенством ВеЦА) <Р1(Л). Таким образом, неоп­ределенность (неточность) знаний субъекта об А выражается интервалом [Bel(Л). Р1(А)].

Важнейшим элементом ТДШ является операция объединения свидетельств (т. е. функция £(■)). задаваемая правилом Демпстера [Dempster, 1967]. Пра­вило является эвристическим и основывается на интуитивных соображениях о разумном способе объединения не связанных друг с другом (независимых) свидетельств.

Несмотря на интуитивную привлекательность многих аспектов ТДШ, она до последнего времени не^- находила широкого применения в процедурах неточ­ного вывода из-за вычислительной сложности операции объединения, экспонен­циальной по мощности 8. Наметившиеся в последнее время возможности по преодолению этих трудностей [Barnett, 1981; Gordon et al., 1985; Shenoy et al., 1986] позволяют рассчитывать на более широкое использование ТДШ в рас­суждающих системах.

INFERNO. Механизм неточного вывода INFERNO [Quinlon, 1983] разрабатывался исходя из следующих критериев: 1) система вы­вода не должна зависеть от каких-либо предположений о ве­роятностном распределении на множестве высказываний; 2) имеющаяся об этом раеттрдрлении информация (например, данные о независимости событий) должна быть легко вводима в систему; 3) высказывания не должны быть жестко разделены на свидетельства и гипотезы — должна иметься возможность гибкого изменения направления вывода; 4) при наличии противоречий в исход­ных данных система должна их обнаруживать и предлагать пути устранения. В INFERNO каждому высказыванию Л ставится в соответствие вероят­ностный интервал [/(Л), 1—/(Л)], где /(Л)—оценка снизу вероятности Р(А), а }{А) —оценка вероятности Р(А). Таким образом, /(Л)<Р(Л)<1—/(Л). В процессе пересчета оценка t(A) аккумулирует подтверждающую Л информа­цию, a f{A) —опровергающую. Релевантные высказыванию Л данные считают­ся противоречивыми, если /(Л)4-/(Л)>1. Изначально каждому высказыванию Л приписаны значения /(Л)=/(Л) =0. Процессом пересчета управляют огра­ничения на t(A) и f(A) типа неравенства О», полученные хотя и из слабого, но справедливого во всех случаях неравенства maxP (S*)=CP (Si Х/^гУ ■•• V-Sn)^ <.PZjP(Si). Например, с отношением «Л влечет В с силой S* (P(B\A) = S)

связано два ограничения: t(B)^t(A)S и ДЛ)>1—(1— f(B))/S, которые приво­дят к увеличению t{B) и /(Л) с ростом t(A) и f(B) соответственно. Пересчет продолжается до тех пор, пока все ограничения не будут удовлетворены. Если по окончании пересчета для каких-либо высказываний At имеют место нера­венства t(Ai)+f(Ai)>l, т. е. исходные условия противоречивы, то INFERNO с помощью специальных ограничений осуществляет обратный пересчет и фор­мирует множества возможных исправлений, внесение которых в исходные дан­ные делает их совместными. Выбор конкретного из этих множеств осуществля­ет пользователь, обращаясь при необходимости к интегральному показателю «существенности» вносимых исправлений.

Исчисление инцидентов. В данном случае [Bundy, 1985; 1986] каждому высказыванию А ставится в соответствие подмножество i(A) множества w; 1(А) называется инцидентом Л и интерпретируется как соответствующее выска­зыванию Л событие из вероятностного пространства элементарных событий w. Инцидент ЦА) принимается в качестве меры неопределенности, приписанной Л. При таком введении меры неопределенности логические связки оказываются функционально-истинностными по отношению к инцидентам, например i(A&B) = =i(A)(]i(B). Если для всех высказываний Л известны их инциденты, то, как следствие, известны не только вероятности всех Л (элементарные высказыва­ния из w обычно полагают равновероятными), но и зависимости между ними. При этом инциденты (а значит, и вероятности) сложных высказываний могут быть вычислены по инцидентам высказываний, их составляющих.

Процессом вывода в исчислении инцидентов управляет механизм обнару­жения допустимых присвоений (МОДП). На вход ЛЮДП поступает специфи­цированное пользователем исходное присвоение F, т. е. совокупность пар оце­нок сверху и снизу {sup?(A), inf_F(A)\ инцидентов высказываний А. Пользуясь специальными правилами вывода, МОДП строит все допустимые сужения {С_к} присвоения F (\ni_F(Aj) с inf_G/f (А,-), &лр_а (A,) csup_F(A_f)),

определенные на всем множестве интересующих пользователя высказываний. Если допустимых суждений присвоения / не существует, т. е. исходное присвое­ние содержит противоречия, то результатом МОДП является установление факта наличия противоречия. Основные трудности применения исчисления инци­дентов сводятся к спецификации исходного присвоения (в частности, по ве­роятностям высказываний). Возможный подход к решению этой проблемы предлагается в [Corlett et al., 1986].

Проблематика неточного вывода вместе с теорией возможностей и прибли­женными рассуждениями объединены в направлении «Рассуждения в условиях неопределенности», которое интенсивно развивается [Cohen, 1985- Gupta et al 1985; Konolige, 1985; Nguyen et al., 1985; Kanal et al., 1986]. Однако на сегод­няшний день имеется набор (постоянно пополняющийся) взаимовлияющих ме­тодов и опыт их применения в ряде задач [Gordon et al., 1985; Shenoy et al., 1986], причем в одних задачах наблюдается объединение механизмов неточ­ных и приближенных рассуждений fPrade, 1985L я в других —прстпБоборстьи [Hisdai, 1986; Zadeh, i98bj. В перспективе можно надеяться на сближение под­ходов [Kyburg, 1987] и разработку теории рассуждений в условиях неопреде­ленности при участии когнитивных психологов [Shafer, 1985].

Вторым перспективным" направлением является разработка методики вы­бора (синтеза) механизмов вывода в условиях неопределенности исходя из специфики задачи и характера мышления эксперта [Tong et al., 1985].

По-видимому, весьма плодотворным окажется сближение методов немоно­тонного и индуктивного (правдоподобного) вывода [Bobrow, 1980J (см. § 2.6) с методами рассуждения в условиях неопределенности.

Поиск по сайту: