Байесовский метод

 

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

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

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

Если существует только одна применимая эвристика, то проблем нет. Но что делать, если два эвристических метода ориентируют программу в двух разных направлениях? А когда две эвристики указывают одно и то же направление поиска, должно ли это вызывать большее доверие, чем, если бы была только одна из них?

Существуют четыре важные проблемы, которые необходимо обсудить применительно к понятию неопределенности в автоматических системах вывода:

1. Как количественно выразить степень определенности при установлении истинности (или ложности) некоторой части данных?

2. Как выразить степень поддержки заключения конкретной посылкой?

3. Как использовать совместно две (или более) посылки, независимо влияющие на заключение?

4. Как быть в ситуации, когда нужно обсудить цепочку вывода для подтверждения заключения в условиях неопределенности?

Во всех рассуждениях в условиях неопределенности используются четыре основных правила [21].

Условная вероятность события А при данном В – это вероятность того, что событие А наступит при условии, что наступило событие В. Например, вероятность того, что пациент действительно страдает заболеванием А, если у него обнаружен только симптом В:

р(А|В)=р(А и В)/р(В) или р(В|А)=р(А и В)/р(А).

Это - основная формула условной вероятности.

Если для каждой формулы вычислить величину р(А и В) и прировнять результаты, то получится:

р(A)*р(В|А)=р(В)*р(А|В)

Эта формула известна как правило Байеса.

Следующее правило И/ИЛИ:

р(А или В)-р(А)+ р(В)—р(А и В).

Еще одно правило называется правилом композиции. В нем утверждается, что вероятность события А есть среднее взвешенное двух других вероятностей:

р(А)-р(А|В)*р(В)+ р(А|не В)*р(не В).

Рассмотрим первую ситуацию, в которой используется правило типа

если (А), то (В)

Предположим, что никакие другие правила не имеют отношения к данной ситуации. Разберемся, когда можно сделать вывод, что В истинно.

Где возникает неопределенность? В системах вывода она бывает двух видов. Так, неопределенность возникает при попытке количественно оценить, насколько мы уверены, что предыдущее условие истинно. Например, если степень уверенности того, что А истинно, составляет только 90%, то какое значение тогда примет В?

Другой вариант - неопределенность в самой импликации. Например, можно сказать, что в большинстве случаев, но не всегда, если есть А, то есть также и В. Должно быть числовое выражение этого факта (скажем, на 95% уверены, что, имея А, имеем и В).

Как можно все эти отношения выразить в терминах вероятности? Если бы была абсолютная гарантия, что предшествующее событие А истинно, то можно записать:

р(А)=1.

Когда полной определенности нет, установленное значение вероятности отражает эту информацию таким образом:

р(A) = .9.

При неопределенности второго типа утверждение с вероятностью в 95%, что будет В, если есть А, записывается в форме

р(В|А)-.95.

Здесь использована условная вероятность. Эта формулировка достаточно ясна сама по себе, но она не дает никакой информации о том, может ли быть В, если нет А. В ряде случаев такая возможность есть, и тогда нужно получить значение В при отсутствии А:

Рассмотрим теперь типичную проблему, включающую простую импликацию. Импликация представляет собой выражение типа:

если (А), то (В)

Проблему можно выразить таким образом: мы на 90% уверены в том, что А истинно. Мы верим в это правило на 95%. Какова вероятность, что В истинно?

Известно следующее:

р(А)-.9;

р(В|А)-.95;

р(В) — искомый результат.

Как вычислить р(В)? Можно применить правило композиции и с его помощью получить р(В) на основе известных вероятностей:

р(В)=р(В |А) *р(А)+ р(В |не А) *р(не А).

Три величины известно. Обратите внимание на то, что:

р(не А) = (1—р(А)) = 0.1.

Поэтому после преобразования уже известных величин получается равенство:

Р(В)=.95*.9+ р(В|не А)*.1-.855+ р(В |не А)*.1.

До этого места вычисления проводились без дополнительной информации. Так как не известный фактор заключен между 0 и 1, то ответом на основной вопрос будет утверждение, что:

.855<-р(В)<-.955.

Если при постановке проблемы имелось в виду (но не сообщалось), что В никогда не присутствует без А, то

р(В | не а) = 0,

и можно точно сказать, что

р(В) - .85.

В другой ситуации для получения заключения могут присутствовать две посылки:

если (А и В), то (С).

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

Вот типичная проблема. Например, уверены на 95%, что А и В влекут за собой С. При этом с вероятностью в 80% известно, что А истинно, и с вероятностью в 70% - что В истинно. Какова вероятность С?

Известно следующее:

р(А)-.8;

Р(В)-.7;

р(С|А и В)-.95;

р(В) - искомый результат.

Если следовать формулировкам предыдущей задачи, то при использовании правила композиции получатся такие выражения для С:

р(С) = р(С|А и В)*р(С| не(А и В))*р(не(А и В)),

р(С) = .95*р(А и В)+ р(С |не(А и В))*(1—р(А и В)).

Теперь имеем две неизвестные величины вместо одной.

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

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

Если на этой основе нужно сделать вывод, причем нельзя получить дополнительную информацию, тогда, вероятно, наилучшими окажутся следующие предположения:

р(С I не (А и В))=0,

и р(А и В) имеет среднее значение в допустимом интервале.

Однако заметьте, что начали рассуждать эвристически, отказавшись от математической точности.

Существует еще один тип импликации, обычно встречаемый в системах вывода

если (А или В), то (С)

Если параметры выражения не определены, то что можно сказать о С?

Типичную задачу можно сформулировать следующим образом:

Если истинно только А, в 70% случаев С также будет истинным.

Если истинно только В, в 80% случаев С также будет истинным.

Если истинно и А, и В, в 95% случаев С также будет истинным.

Кроме того, в данной конкретной ситуации на 80% уверены, что А истинно, и на 80% уверены, что В истинно.

Какова вероятность истинности С?

Cформулируем в терминах теории вероятности:

р(С | А и (неВ)) =.7;

р(С | (не А) и В) = .8;

р(С I А и В))=.95;

р(А) = .8;

р(В) = .8.

Пользуясь решениями предыдущих задач, запишем выражения для р(С), перечислив все условия, когда может произойти событие С (обращаемся к правилу композиции):

р(С) = р(С | А и В)*р(А и В)

+ р(С | А и (не В))*р(А и (не В))

+ р(С | (не А) и В) * р((не А) и В)

+ р(С | (не А) и (не В)) *р((не А) и (не В)).

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

Если на основе этих формальных выкладок все-таки необходимо сделать вывод, то остается лишь надеяться, что следующее равенство справедливо:

р(С | (не А) и (не В))=0.

Есть еще четыре не известные вероятности, для которых можно вычислить интервалы. Наилучшей оценкой такой величины разумно считать середину допустимого для нее интервала.

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

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

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

Рассмотрим простой тип импликации:

если (Е), то (С)

Эффективный способ решения - присвоить коэффициент определенности как посылке, так и всей импликации. Тогда можно совместно использовать эти две величины для вычисления коэффициентов определенности всего заключения.

Что такое коэффициент определенности? Его часто применяют вместо понятия вероятности. Если обозначить коэффициент определенности как ct, а вероятность как р, то в простейшем случае получим:

коэффициент определенности посылки - ct (Е) ~ р (Е),

коэффициент определенности импликации - ct (С) ~ р(С/Е).

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

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

ct (заключение) = ct (посылка) *ct (импликация).

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

ct (заключение) = .8 * .9 = .72.

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

если(е1 или (е2 и е3)), то (с)

или

если (е1 и е2 и ((не еЗ) или е4)), то (с)

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

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

Простейшей логической комбинацией является конъюнкция (И) между двумя элементарными свидетельствами:

если (е1 и е2), то (с)

Согласно оценке, сделанной в EMYCYN, коэффициент определенности посылки равен коэффициенту определенности наименее надежной из посылок, т.е.

ct(el ие2) = min (ct(el),ct(e2))

Другой простой формой является правило, в котором используется дизъюнкция (ИЛИ), связывающая две части свидетельств:

если (е1 или е2), то (с)

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

С(е1 или е2) = mах (с1(е1),с1(е2))

Хотя правила иногда и записываются с помощью дизъюнкции, если есть выбор, то принято разбивать дизъюнкцию на две части, например:

если (е1),то (с)

если (е2), то (с)

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

Рассмотрим ситуацию, когда используются два правила и оба они поддерживают одно и то же заключение, например:

Правило 1:

если (е 1), то (с) ct (заключение) = .9

Правило 2:

если (е2) то (с) сt (заключение) = .8

Допустим, обе посылки верны, и вычислили вероятность заключения для каждого правила по отдельности.

Если использовалось правило 1, то коэффициент определенности в заключении окажется равным 0.9. Ясно, что, имея еще и правило 2, получим больший коэффициент определенности, но какова будет его величина?

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

ctotal = коэффициент определенности из правила 1

+ коэффициент определенности из правила 2

— (коэффициент определенности из правила 1)

* (коэффициент определенностииз правила 2)

Подставив числа, заданные в примере, получим

ctolal = .9 + .8 — (.9) * (.8) = .98.

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

Правило 1:

если (el), то (с) ct (заключение) = ctl

Правило 2:

если (е2), то (с) ct (заключение) = ct2

Правило 3:

если (еЗ), то (с) сt (заключение) = ct3

Совокупный коэффициент определенности заключения с учетом всей возможной поддержки может быть вычислен так:

ctotal =ctl+ct2+cl3— ctl * ct2 — ct2 * ct3 — ctl * ct3 + ctl * ct2 * ct3

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

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

Рассмотрим пример. Допустим, известно, что заключение поддерживается двумя правилами со следующими коэффициентами определенности:

Правило 1:

если (е1), то (с) ct (заключение) =•ctl.

Правило 2:

если (е2), то (с) ct (заключение) = ct2.

При применении двух правил совокупный коэффициент определенности

ctotal -= ctl + ct2 — ctl *ct2.

Теперь предположим, что появилось третье правило, поддерживающее тоже заключение:

Правило 3:

если (еЗ), то (с) сt(заключение) = ct3

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

cnewtotal = ct3 + ctotal — ct3 * ctotal.

В любом случае при использовании механизма дополнения порядок поступления правил, поддерживающих заключение, не имеет значения.

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

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