Оболочка IMP

1

ОБОЛОЧКА ЭКСПЕРТНОЙ СИСТЕМЫ IMP

Содержание

1. Приближенные рассуждения в экспертной системе IMP …………….	2
1.1. Общие сведения о приближенных рассуждениях ………………………………..	2
1.2. Импликация с простой посылкой …………………………………………………	3
1.3. Импликация с составной посылкой ………………………………………………	4

1.4.Поддержка заключения несколькими импликациями ………………………….. 4

1.5.Биполярные КО ……………………………………………………………………. 5

1.6. Представление набора правил с неопределенностью ……………………………	6
1.7. Выполнение обратной цепочки рассуждений в условиях неопределенности ….	8
1.8. Программная реализация схемы приближенных рассуждений на языке Prolog	10

воболочке ЭС IMP ……………………………………………………………….

2.Механизм объяснения экспертной системы IMP …………………….. 15

2.1. Общие сведения о механизме объяснения ЭС ……………………………………	16
2.2. Принцип работы блока ответа на вопросы “почему” ……………………………	15
2.3. Принцип работы блока ответа на вопросы “как” ………………………………..	18
2.4. Программная реализация механизма объяснений в оболочке ЭС IMP …………	19
3. Реализация оболочки ЭС IMP	23

3.1.Компоновка блоков ЭС IMP ………………………………………………………. 23

3.2.Добавление формул в импликации………………………………………………... 25

4.Пример разработки экспертной системы в оболочке IMP …………... 25

Список литературы …………………………………………………….…. 28

2

Здесь подробно обсуждаются конструкция и функции учебной оболочки экспертной системы (ЭС), названной IMP в связи со словом implication, которое обозначает импликацию, т.е. правило вида “если … то …” как средство представления знаний. В оболочке IMP реализованы схема приближенных рассуждений, механизм объяснения, редактор знаний и другие служебные функции на языке программирования Prolog [1].

1. Приближенные рассуждения в экспертной системе IMP

1.1. Общие сведения о приближенных рассуждениях

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

Пример:

При диагностике болезни врач сталкивается с неопределенностью двух видов:

1)нечеткость проявления симптомов;

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

Несмотря на наличие этих неопределенностей 1-го и 2-го рода, врачи обычно успешно ставят диагноз и назначают лечение.

Вопросы, возникающие при реализации нечетких рассуждений в ЭС:

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

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

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

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

Для ответа на эти вопросы возможны два подхода:

•точный подход на базе теории вероятностей (байесовские рассуждения);

•приближенный подход на базе факторов уверенности.

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

•основная формула условной вероятности

P(A|B) = P(AB)/P(B)

•правило Байеса

P(A)P(B|A) = P(B)P(A|B)

•правило И/ИЛИ

P(A+B) = P(A) + P(B) – P(AB)

•правило композиции

P(A) = P(A|B)P(B) + P(A|¬B)P(¬B),

3

где

P(A)	– априорная вероятность события A;
P(B)	– априорная вероятность события B;
P(AB)	– совместная вероятность событий A и B;
P(A|B)	– вероятность события A при условии, что произошло событие B;
P(B|A)	– вероятность события B при условии, что произошло событие A;
P(A+B)	– вероятность того, что произошло событие A или B;
P(¬B)	– вероятность события, противоположного событию B;
P(A|¬B)	– вероятность события A при условии, что произошло событие,
	противоположное событию B.

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

вычисляемые по простым формулам, полученным с помощью экспертов. Ниже подробно рассматривается одна из удачных схем приближенных рассуждений на базе коэффициентами определенности, впервые реализованная в известной ЭС MYCIN [1, 2].

1.2. Импликация с простой посылкой
Импликация (или правило) с простой посылкой имеет вид:
если E то С ,	(1.1)

где E – посылка, состоящая из единственного условия; С – заключение.

Для учета неопределенности в импликациях вида (1.1) разработчики ЭС MYCIN предложили использовать коэффициенты определенности (КО) следующим образом. Посылке E назначается КО ct(E), а импликации в целом – КО ct(IMP), и затем КО заключения C вычисляется по формуле

ct(C) = ct(E) ct(IMP).

(1.2)

Это означает, что если мы верим в истинность посылки на 80% (т.е. посылка считается истинной с КО = 0.8) и верим, что лежащая в основе импликации идея выполняется в 90% случаев (т.е. импликация считается истинной с КО = 0.9), то КО заключения принимается равным 0.8·0.9 = 0.72, т.е. степень нашей веры в истинность заключения признается равной 72%. Здесь КО посылки учитывает неопределенность 1-го рода, а КО импликации – неопределенность 2-го рода. Поясним источники неопределенности 1-го и 2-го рода на простом примере.

Пример:

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

если это новая модель автомобиля то в нем имеется каталитический преобразователь

1)Пусть механик на вопрос ЭС “Это новая модель автомобиля” ответил “Да”. Однако его представление о новой модели автомобиля может совпадать с представлением эксперта, создавшего ЭС, допустим, лишь в 80 случаях из 100, т.е. с относительной частотой 0.8. Это источник неопределенности 1-го рода. Для ее учета надо посылку импликации при положительном ответе механика признать истинной с КО = 0.8.

4

2)С другой стороны, даже если посылка импликации признана истинной с КО = 1.0, не факт, что заключение импликации абсолютно истинно, т.к. сама импликация не является абсолютно истинной. Действительно, даже если это новая модель автомобиля, то в нем имеется каталитический преобразователь, допустим, лишь в 98 случаях из 100, вследствие того, что некоторые водители самовольно снимают его. Это источник неопределенности 2-го рода. Для ее учета надо считать импликацию истинной с КО = 0.8

Можно заметить, что по смыслу КО похожи на вероятности, хотя и не являются ими с точки зрения теории вероятностей. В частности, КО посылки ct(E) похож на априорную вероятность p(E) того, что посылка E истинна, а КО импликации ct(IMP) – на условную вероятность p(C|E) того, что заключение C истинно при условии, что посылка E истинна.

1.3.Импликация с составной посылкой

Вобщем случае посылка импликации состоит из нескольких простых условий, соединенных логическими связками И ( ), ИЛИ ( ) и НЕ (¬), причем каждое из этих условий имеет свой КО.

Пример:

Импликация с составной посылкой:

если (e1 e2 (¬ e3) e4)) то c ,

или в эквивалентной записи

c ← e1 e2 (¬ e3) e4

Если известны КО составной посылки и КО импликации, то КО заключения, по-прежнему, вычисляется по формуле (1.2). Для вычисления КО составной посылки по известным КО простых условий разработчики ЭС MYCIN предложили следующий метод. Составная посылка представляется как последовательность бинарных посылок, имеющих форму конъюнкции ( ) или дизъюнкции ( ) двух условий или их отрицаний (¬).

Пример:

Составная посылка

e = e1 e2 (¬ e3) e4

представляется как последовательность следующих бинарных посылок: e = e1 c1, c1 = e2 c2, c2 = (¬ e3) e4.

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

1)	КО конъюнкции:
	ct(e1 e2)	= min(ct(e1), ct(e2)).	(1.3)
2)	КО дизъюнкции:
	ct(e1 e2)	= max(ct(e1), ct(e2)).	(1.4)

1.4. Поддержка заключения несколькими импликациями

Пусть две импликации c ← e1 и c ← e2 поддерживают заключение c и дают для него КО ct1 и ct2 соответственно. В этом случае разработчики ЭС MYCIN предлагают вычислять общее КО заключения определяется как

ct = ct1 + ct2 – ct1 · ct2.

(1.5)

5

Очевидно, что если ct1, ct2 [0; 1], то ct ≥ ct1 и ct ≥ ct2, что соответствует нашему интуитивному ожиданию, что второе свидетельство в пользу заключения никак не может уменьшить нашу уверенность в истинности заключения по сравнению с уверенностью, основанной на первом свидетельстве.

Если три импликации поддерживают заключение и дают для него КО ct1, ct2 и ct3 соответственно, то общее КО заключения определяется как

ct = ct1 + ct2 + ct3 – ct1 · ct2– ct1 · ct3– ct2 · ct3 + ct1 · ct2 · ct3.

(1.6)

Легко обобщить формулу (1.6) на случай n импликаций.

1.5.Биполярные КО

Внекоторых ЭС, включая ЭС MYCIN, область допустимых значений КО равна [–1; 1]. При этом +1 означает полную уверенность в истинности объекта, –1 означает полную уверенность в ложности объекта, 0 – отсутствие информации об объекте, а промежуточные значения – степень веры или отсутствия веры в истинность объекта.

Такие биполярные КО имеют две особенности:
1) КО отрицания простого условия определяется как
		ct(¬e) = – ct(¬e),			(1.7)
2) КО заключения, поддерживаемого двумя импликациями, определяется как
ct1		+ct2	−ct1 ct2, еслиct1иct2 положительны
		+ct2	+ct1 ct2, еслиct1иct2 отрицательны		(1,8)
ct = ct1
		ct1	+ct2
				востальныхслучаях,
1 −min(| ct1 |,| ct2 |)

где ct1 и ct2 – частные КО заключения, вычисленные по первой и второй импликациям.

Важно учитывать, что использование биполярных КО может иногда приводить к нереальным результатам. Рассмотрим это на примерах.

Пример 1:

Пусть ЭС содержит импликацию:

если это новая модель автомобиля то в нем имеется каталитический преобразователь.

Пусть импликация имеет КО = 0.9. Применим эту импликацию к старой модели автомобиля, для которого посылка импликации имеет КО = – 0.8. Тогда заключение импликации имеет КО = – 0.8·0.9 = – 0.72. Это означает большую уверенность в ложности заключения о том, что в автомобиле имеется каталитический преобразователь, и этот результат согласуется с реальностью.

Пример 2:

Пусть ЭС содержит импликацию:

если это новая модель автомобиля то в нем имеется радиоприемник.

Пусть импликация имеет КО = 0.9. Применим эту импликацию к старой модели автомобиля, для которого посылка импликации имеет КО = – 0.8. Тогда заключение импликации имеет КО = – 0.8·0.9 = – 0.72.

6

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

если это НЕ новая модель автомобиля то в нем НЕ имеется радиоприемник.

Выводы:

1)Правило из примера 1 остается верным при одновременном отрицании посылки и заключения. Такие правила называются обратимыми. Правило из примера 2 является

необратимым.

2)Обратимые правила применимы при любых значениях КО посылки, а необратимые правила – только при положительных КО посылки.

3)Эксперт должен указать для каждого правила не только значение КО импликации, но значение признака обратимости импликации.

1.6.Представление набора правил с неопределенностью

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

Пример:

	Набор правил с неопределенностью
ЕСЛИ	у вас грипп И
ТО	вы в критическом возрасте	ct = 0.9
	вызовите врача
ЕСЛИ	у вас острый фарингит	ct = 1.0
ТО	вызовите врача
ЕСЛИ	у вас простуда	ct = 0.4
ТО	примите аспирин
ЕСЛИ	у вас грипп И
ТО	вы НЕ в критическом возрасте	ct = 0.4
	примите аспирин
ЕСЛИ	у вас лихорадка И
ТО	болят мышцы	ct = 0.7
	у вас грипп
ЕСЛИ	у вас насморк И
	болят мышцы И
ТО	НЕТ лихорадки	ct = 0.7
	у вас простуда
ЕСЛИ	у вас нарывы в горле И
ТО	лихорадка	ct = 0.8
	у вас острый фарингит

7

ЕСЛИ	моложе 7 лет ИЛИ
ТО	вы старше 60 лет	ct = 0.7
	вы в критическом возрасте

Набор правил с неопределенностью можно представить графически в виде сети вывода.

Сеть вывода

Принять

аспирин

0.4		0.9
0.4		Критический
	Грипп
		возраст

Простуда 0.7

0.7

0.7

Мышечные

боли

Насморк

Лихорадка		Моложе		Старше
		7 лет		60 лет

Сети вывода состоят из фрагментов следующих шести типов:

Вызвать

врача

1.0

Острый

фарингит

0.8

Нарывы в горле

Импликация с		Импликация с		Импликация с		Импликация с
простой посылкой		конъюнкцией		дизъюнкцией		отрицанием
c			c		c		c
			0.9		0.7			0.7
	0.8
e		e1	e2	e1	e2		e
c ← e		c ← e1 e2		c ← e1 e2		c ← (¬ e)

Заключение, поддерживаемое двумя импликациями

c

0.8

0.7

e1 e2 e3

c ← e1 e2 c ← e3

8

Посылка, входящая в две импликации

c1 c2

0.9

0.8

e1 e2

c1 ← (¬ e1) c2 ← e1 e2

На этих рисунках десятичные дроби означают КО соответствующих импликаций.

1.7. Выполнение обратной цепочки рассуждений в условиях неопределенности

Принцип выполнения обратной цепочки рассуждений (ОЦР) в условиях неопределенности поясняется на примере сети вывода, показанном на рисунке.

				Сеть вывода
				c5	0
				0.8
				(n)
	c1		0				c4			0
0.8						0.9
(n)						(r)
			c2				c3			0
	e1			0
0.9
				0.7	0.6			0.5
				(r)	(n)
			0.9						(n)
			(r)
			e2	e3	e4		e5
			0.9	– 0.3	– 0.4	– 0.3

Здесь узел высшего уровня представляет целевую гипотезу, узлы низшего уровня (терминальные узлы) – условия внешнего мира, которые ЭС должна запрашивать у пользователя, и, наконец, внутренние узлы – промежуточные заключения ОЦР.

9

Значения КО внутренних узлов первоначально равны нулю, а затем последовательно вычисляются в ходе выполнения ОЦР, в зависимости от заданных импликаций и значений КО терминальных узлов, вводимых пользователем по запросам ЭС. Значения КО внутренних и терминальных узлов записываются на сети вывода рядом с соответствующими узлами.

Каждый внутренний узел представляет заключение одной или нескольких импликаций. Для каждой импликации на сети вывода указываются значение КО и значение признака обратимости (r – обратима, n – необратима).

Чтобы выполнить ОЦР для целевого узла c5, надо рассмотреть импликации для узлов c1 и c4, и при этом, чтобы выполнить ОЦР для узла c4, надо рассмотреть импликации для узлов c2 и c3. Таким образом, выполнение ОЦР для узла c5 сводится к рассмотрению импликаций для узлов в следующей последовательности: c1, c2, c3, c4, c5.

Выполнение ОЦР в условиях неопределенности

1) Узел c1

Этот узел поддерживается необратимым правилом. КО посылки положительно, поэтому правило применимо и согласно формуле (1.2) дает КО узла ct(c1) = 0.8 · 0.9 = 0.72.

2) Узел c2

Этот узел поддерживается двумя правилами. Они оба обратимы и поэтому применимы независимо от знака КО посылки. Левое правило согласно формуле (1.2) дает КО узла ct(c2) = 0.9 · 0.9 = 0.81, а правое правило – КО узла ct(c2) = – 0.3 · 0.7 = – 0.21. Общее значение КО узла согласно формуле (1.8) равно ct(c2) = (0.81 + (– 0.21)) / (1 – 0.21) = 0.74.

3) Узел c3

Этот узел поддерживается двумя правилами. Левое правило необратимо и потому неприменимо, т.к. КО его посылки отрицательно. Правое правило тоже необратимо, но применимо, т.к. элементарное условие его посылки имеет отрицательный КО ct(e5) = – 0.3, но вся посылка с учетом отрицания согласно формуле (1.7) имеет положительный КО ct(¬ e5) = – (– 0.3) = 0.3. Это правило согласно формуле (1.2) дает КО узла ct(c3) = 0.3 · 0.5 = 0.15.

4) Узел c4

Этот узел поддерживается правилом с конъюнкцией в посылке, где согласно формуле (1.3) КО посылки равно min(0.15, 0.74) = 0.15. Это правило обратимо, поэтому применимо независимо от знака КО посылки и согласно формуле (1.2) дает КО узла ct(c4) = 0.15 · 0.9 = 0.13.

5) Узел c5

Этот узел поддерживается правилом с дизъюнкцией в посылке, где согласно формуле (1.4) КО посылки равно max(0.72, 0.13) = 0.72. Это правило необратимо, но применимо, т.к. КО его посылки положительно, и согласно формуле (1.2) дает КО узла ct(c5) = 0.72 · 0.8 = 0.58. Таким образом, КО целевой гипотезы c5 вычислен и на этом наша ОЦР в условиях неопределенности успешно завершена!

10

1.8. Программная реализация схемы приближенных рассуждений на языке Prolog в оболочке ЭС IMP

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

1) с простой посылкой:

c ← e, c ← ¬ e

2) с посылкой в форме конъюнкции:

c← e1 e2, c ← (¬ e1) e2, c ← e1 (¬ e2), c ← (¬ e1) (¬ e2),

3)с посылкой в форме дизъюнкции:

c← e1 e2, c ← (¬ e1) e2, c ← e1 (¬ e2), c ← (¬ e1) (¬ e2),

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

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

Сеть вывода с двумя
конкурирующими гипотезами
c8	c7
0.8
(r)	0.8
	(r)
c6	0.9
0.7	(r)
(r)

0.6 (r)

c1

c2

e4

c3

c4

c5

			0.8	0.6	0.8
	0.9		(r)	(r)	(r)
					0.5
		(r)
					(r)

e1

e2

e3

e5

e6

e7

e8