5. Контрольные вопросы

1. Что понимается под решением задачи при разбиении ее на подзадачи?

2. Что означает понятие "дерево решений"?

3. Что такое покрывающие деревья?

4. Охарактеризуйте основные типы поиска по дереву решений.

5. Объясните, какой тип поиска реализован в данной экспертной системе.

6. Процедуры повышения эффективности поисковых методов.

7. Расскажите о методе ветвей и границ.

8. Сформулируйте преимущества и недостатки реализованной экспертной системы.

9. Как внести изменения в базу знаний?

10. Каким образом взаимодействуют подготовительная и исполнительная программы экспертной системы?

Лабораторная работа №2 Экспертная система на основе байесовского подхода

1. Цель работы

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

2. Теоретическая часть

2.1 Вероятности, события, гипотезы

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

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

Пусть Н - событие, заключающееся в том, что, данная гипотеза верна. Пусть Е - событие, заключающееся в том, что наступило определенное доказательство (свидетельство), которое может или не может подтвердить правильность указанной гипотезы.

Тогда Р(Н) - априорная вероятность того, что событие Н истинно при отсутствии каких-либо свидетельств.

Р(Е) - вероятность того, что событие Е произошло.

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

Р(не Н) или P(H) = 1 - P(H) - вероятность того, что событие H ложно.

Тогда B(H/Е) или P(Н/Е) – апостериорная вероятность гипотезы Н при наличии или отсутствии свидетельства E.

По определению

и .

После некоторой перегруппировки согласно теореме Байеса получаем

.

Или, если мы нашли, что событие Е не наступило:

.

Задача заключается в том, что Р(Н/Е) необходимо рассчитать для какого свидетельства (признака) и выбрать наиболее вероятное решение.

Сделаем некоторые пояснения к теореме Байеса. Предположим, что имеется пациент, больной гриппом, (или не больной, что нам и нужно определить). Мы представляем себе, какова априорная вероятность того, что пациенты болеют гриппом, то есть мы знаем Р(Н). Но нам необходимо знать вероятность гриппа у данного, конкретного пациента.

Мы обнаруживаем, что у него жар (данные налицо), и хотим узнать P(H/E) – вероятность того, что у пациента грипп, при условии, что у него есть температура. Это не очень простой вопрос. Немного легче ответить на вопрос противоположного свойства: если у больного грипп, какова вероятность, что у него высокая температура? Эта вероятность равна единице. Дальнейшие вычисления производятся по байесовской формуле.

Но предварительно необходимо прояснить значение P(E) - вероятности самого свидетельства, в нашем случае вероятности, что у человека имеется высокая температура. Если у каждого всегда повышенная температура, то тот факт, что у нашего пациента жар, ничего не объясняет. У нашего пациента жар, но является ли такое состояние в общем случае редким событием?

Для вычисления P(E) используется формула:

.

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

Мы имеем для некоторого события Н определенное число отдельных свидетельств (признаков), подтверждающих его или не подтверждающих, которые выделяются по мере их значимости (как подсчитать цену свидетельства рассмотрим в следующем подразделе). Назовем их соответственно Ек ,…, Еn. Используя априорные и апостериорные вероятности, построим алгоритм вычисления вероятностей методикой принятия апостериорной вероятности для каждого последующего признака, как за априорную.

1. Р(Н) - априорная вероятность события Н.

2. Для каждого, события Е_i, имеющего цену большую, чем у E_i+1 имеем: Р(Е_i/Н) и Р(Е_i/Н).

3. C учетом теоремы Байеса подсчитываем Р(Н/Е_i) или Р(Н/Е_i) в зависимости от исхода Е_к , то есть вычисляем апостериорную вероятность события Н.

4. Теперь, не обращая внимания на все наступившие Е_i, преобразуем текущую апостериорную вероятность события Н, как новую априорную вероятность Н. Итак, пусть Р(Н) равна Р(Н/Е_i) или Р(Н/Е_i) в зависимости от значения Е_i.

5. Выбираем новое свидетельство Е_i для рассмотрения и переходим к пункту 1.

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

В отношении этого метода можно высказать два критических замечания. Первое касается вычисления Р(Е). Представленное вычисление является точным и очень простым, т.е.- оно является точным, если мы знаем P(E/H), а это значение не всегда может быть точно известно. Например, у кого-то высокая температура, если известно, что у этого человека нет гриппа. Как правило, мы будем знать очень точное значение для P(Е/Н), вероятности высокой температуры при условии, что у больного - грипп, но не всегда для .

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

с учетом того, что формула, использованная нами ранее, является частным случаем этого выражения.

Если Р(Н) постоянно уточняется в ходе работы, то Р(Е) теоретически также может уточняться с течением времени.

Это естественная мысль, поскольку формула гласит, что вероятность свидетельства Е есть вероятность Е при учете каждой данной ситуации, которая может повлечь за собой появление Е, умноженная на вероятность такой ситуации. Эта формула учитывает все. Разумеется, если в нашей базе знаний хранится каждая ситуация, с которой может быть связано появление высокой температуры, и указаны текущие вероятности таких ситуаций, то мы могли бы иметь точную оценку Р(Е), которая будет постоянно обновляться по мере изменения Р(H_i). оставаясь всегда точной. Но трудность состоит в том, что наша система в некотором смысле всегда будет далека от совершенства. Скажем, такая болезнь, как ласская лихорадка, также вызывает жар, но если этой болезни нет в базе знаний, тогда это приведет к соответствующей ошибке при вычислении P(E), точно так же, как и при формировании окончательного результата. Аналогично обстоит дело и для каждого элемента, который отсутствует в базе знаний . С практической точки зрения использование грубых оценок для P(E/H) и для вполне допустимо, т.к. экономится объём необходимых вычислений, благодаря чему ответ получается быстро. Второе критическое замечание, которое может быть выдвинуто, касается того, что в этом методе используется предположение о независимости переменных. Предположим, что в нашей базе знаний имеется два симптома. Одним является "высокая температура", а вторым - "жар". Конечно, неразумно иметь оба эти симптома, поскольку они означают одно и то же состояние. Эти элементы полностью коррелируют друг с другом. Но если оба они уже попали в базу знаний, тогда мы фактически включили одно свидетельство дважды, следовательно, увеличили или уменьшили вероятность гриппа по сравнению с тем, что должно было быть, так что апостериорные вероятности будут ошибочными.

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

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

Шансы и вероятности связаны следующей формулой:

.

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