Логическое программирование

1.

Сошников Дмитрий Валерьевич
к.ф.-м.н., доцент
[email protected]
Факультет Прикладной математики и физики
Кафедра Вычислительной математики и программирования
Московский авиационный институт (государственный технический университет)

2.

Экспертные системы
2

3.

©2009 Сошников Д.В.
Системы, способные заменить или
упростить работу специалиста в какой-то
конкретной предметной области
Примеры
MYCIN
PROSPECTOR
CYC
Яндекс-Гуру
3

4.

©2009 Сошников Д.В.
пользователь
Механизм
логич.
вывода
База знаний
(множество правил)
Рабочая память
(пары атрибутзначение)
эксперт
Инженер
по знаниям
В классической продукционной экспертной системе
База знаний представляет собой множество правил ЕСЛИ-ТО (продукций)
Рабочая память представляет собой множество пар атрибут-значение (троек объект-атрибутзначение), описывающих состояние решаемой задачи
Процесс логического вывода – это поиск в пространстве состояний множества комбиаций рабочей
памяти, переходы в котором задаются правилами.
4

5.

6.

©2009 Сошников Д.В.
Дерево И-ИЛИ
Каждый узел дерева транслируется в
продкукционное правило
ЕСЛИ цвет - рыжевато-коричневый И узор –
тёмные пятна И класс – млекопитающее И
отряд – хищник ТО животное - обезьяна
Листья дерева соответствуют
элементарным фактам, которые являются
исходными для решения задачи
6

7.

Разрешение
конфликта
Отбор
применимых
правил
Применяемое
правило
©2009 Сошников Д.В.
Конфликтное
множество
Цель
получена?
База знаний
Рабочая память
Применение
правила
7

8.

©2009 Сошников Д.В.
Первое по тексту правило
Система приоритетов
Правило с максимальным (минимальным)
числом посылок
Правило с максимальным числом
заключений
...
8

9.

©2009 Сошников Д.В.
Прямой вывод (управляемый фактами)
• Движение по дереву снизу вверх (от фактов)
• Необходимо знание начальных фактов
Обратный вывод (управляемый целями)
• Движение по дереву сверху вниз
• Выдвигаем гипотезу, пытаемся ее доказать
• Пользователю задаются вопросы для уточнения фактов
Комбинированный вывод
9

10.

©2009 Сошников Д.В.
Какой механизм поиска (в глубину/в
ширину/эвристический) используется в
прямом и обратном выводе?
Рассмотренные алгоритмы вывода использовали
простейший метод поиска без возвратов (полуслучайным спуском)
Возможно использовать алгоритмы поиска в
глубину и в ширину с обоими методами вывода
Но нужно помнить про размер пространства
состояний и отдельного состояния!
10

11.

©2009 Сошников Д.В.
Естественное представление правил –
правила могут формулироваться даже
экспертами самостоятельно
Возможность контроля
непротиворечивости базы знаний на этапе
добавления правил
Прозрачный и простой механизм
логического вывода
Очевидный механизм объяснений
11

12.

©2009 Сошников Д.В.
2 варианта реализации:
Напрямую кодирование правил на Прологе
Создание «оболочки» экспертной системы со
специализированным языком представления
знаний
12

13.

©2009 Сошников Д.В.
animal(обезьяна) :class(млекопит), type(хищник), color(рыжкор), pattern(темпятна).
animal(тигр) :class(млекопит), type(хищник), color(рыжкор), pattern(темполосы).
...
class(млекопит) :- has(волосы); prop(даетмолоко).
type(хищник) :- prop(ест_мясо).
type(хищник) :- has(острые_зубы), has(когти), has(вперед_см_глаза).
has(X) :- write(‘У животного есть ‘), write(X), read(yes).
color(X) :- write(‘Цвет: ‘), read(X).
...
?- animal(X).
Проблема:
При выводе вопросы задаются многократно
(предыдущие ответы пользователя не сохраняются)
13

14.

©2009 Сошников Д.В.
animal(обезьяна) :class(млекопит), type(хищник), color(рыжкор), pattern(темпятна).
animal(тигр) :class(млекопит), type(хищник), color(рыжкор), pattern(темполосы).
...
class(млекопит) :- has(волосы); prop(даетмолоко).
type(хищник) :- prop(ест_мясо).
type(хищник) :- has(острые_зубы), has(когти), has(вперед_см_глаза).
has(X) :- fact(has(X)), !.
has(X) :- nfact(has(X)), !, fail.
has(X) :- write(‘У него есть ‘), write(X), read(Z), assert_fact(Z,has(X)).
assert_fact(yes,X) :- asserta(fact(X)).
assert_fact(no,X) :- asserta(nfact(X)).
color(X) :- fact(color(Z)), !, Z=X.
color(X) :- write(‘Цвет ‘), read(Z), asserta(fact(color(Z))), !, Z=X.
Проблема:
При выводе многие факты выводятся повторно, т.е. промежуточные результаты вывода
не сохраняются в рабочей памяти
14

15.

©2009 Сошников Д.В.
animal(обезьяна) :class(млекопит), type(хищник), color(рыжкор), pattern(темпятна).
animal(тигр) :class(млекопит), type(хищник), color(рыжкор), pattern(темполосы).
...
class(млекопит) :- has(волосы), asserta((class(млекопит):-!)).
class(млекопит) :- prop(даетмолоко), asserta((class(млекопит):-!)).
type(хищник) :- prop(ест_мясо), asserta((type(хищник):-!)).
type(хищник) :- has(острые_зубы), has(когти),
has(вперед_см_глаза), asserta((type(хищник):-!)).
has(X) :- fact(has(X)), !.
has(X) :- nfact(has(X)), !, fail.
has(X) :- write(‘У него есть ‘), write(X), read(Z), assert_fact(Z,has(X)).
assert_fact(yes,X) :- asserta(fact(X)).
assert_fact(no,X) :- asserta(nfact(X)).
color(X) :- fact(color(Z)), !, Z=X.
color(X) :- write(‘Цвет ‘), read(Z), asserta(fact(color(Z))), !, Z=X.
15

16.

©2009 Сошников Д.В.
Известно свойство, что прямой вывод
эмулируется при помощи обратного
перестановкой посылок и заключений
правил
Для реализации на Прологе:
В качестве рабочей памяти будем
использовать базу фактов Пролога
▪ (хотя можно делать и более «правильно»)
Вывод нового факта – модификация базы
Исходно все факты заносятся в базу фактов
16

17.

©2009 Сошников Д.В.
solve(X) :- repeat, rule(_), animal(X).
rule(1) :- class(млекопит), type(хищник),
color(рыжкор), pattern(темпятна), asserta(animal(обезьяна)).
rule(2) :- class(млекопит), type(хищник),
color(рыжкор), pattern(темполосы), asserta(animal(тигр)).
rule(3) :- has(волосы), asserta(class(млекопит)).
rule(4) :- prop(даетмолоко), asserta(class(млекопит)).
rule(5) :- prop(ест_мясо), asserta(type(хищник)).
rule(6) :- has(острые_зубы), has(когти),
has(вперед_см_глаза), asserta(type(хищник)).
…
color(рыжкор).
pattern(темполосы).
prop(даетмолоко).
has(острые_зубы).
has(когти).
has(вперед_см_глаза).
?- solve(X).
17

18.

©2009 Сошников Д.В.
solve(X) :- repeat, rule(_), animal(X).
rule(1) :- class(млекопит), type(хищник),
color(рыжкор), pattern(темпятна), !,
retract((rule(1):-_)), asserta(animal(обезьяна)).
rule(2) :- class(млекопит), type(хищник),
color(рыжкор), pattern(темполосы), !,
retract((rule(2):-_)), asserta(animal(тигр)).
rule(3) :- has(волосы), !,retract((rule(3):-_)), asserta(class(млекопит)).
rule(4) :- prop(даетмолоко), !,
retract(rule(4):-_)), asserta(class(млекопит)).
rule(5) :- prop(ест_мясо), !,retract((rule(5):-_)), asserta(type(хищник)).
rule(6) :- has(острые_зубы), has(когти),
has(вперед_см_глаза), !,
retract((rule(6):-_)), asserta(type(хищник)).
…
18

19.

©2009 Сошников Д.В.
:-op(60,xfx,'--->').
[class(млекопит), type(хищник), color(рыжкор), pattern(темпятна) ] --->
animal(обезьяна).
[class(млекопит), type(хищник), color(рыжкор), pattern(темполосы) ] --->
animal(тигр).
[has(волосы)] ---> class(млекопит).
[prop(дает_молоко)] ---> class(млекопит).
[prop(ест_мясо)] ---> type(хищник).
[has(зубы),has(когти), has(вперед_см_глаза)] ---> type(хищник).
...
run :- animal(X), write(X), !.
run :Cond ---> Act,
test(Cond),
retract(Cond--->Act),
asserta(Act),
run.
test([]).
test([A|T]) :- call(A), test(T).
19

20.

©2009 Сошников Д.В.
rule anumal eq обезьяна
if class eq млекопит and type eq хищник
and color eq рыжкор and pattern eq темпятна.
rule anumal eq тигр
if class eq млекопит and type eq хищник
and color eq рыжкор and pattern eq темполосы.
rule type eq млекопит
if gives_milk eq y or has_hair eq y.
…
gives_milk ask ‘Оно даёт молоко? '.
eats_meat ask ‘Оно ест мясо? '.
color ask ‘Цвет? '.
::::-
op(10,yfx, and), op(15,yfx,or), op(5,xfx,eq), op(5,xfx,neq).
op(20,xfx, if).
op(25,fx, rule).
op(20,xfx, ask).
20

21.

©2009 Сошников Д.В.
frule(Atr,Val,Todo) :- rule(if(eq(Atr,Val),Todo)).
frule(Atr,Val,[]) :- rule(eq(Atr,Val)).
infer(Atr,Val,AVL,[av(Atr,V)|AVL]) :- asked(Atr,V), !, V=Val.
infer(Atr,Val,AVL,[av(Atr,V)|AVL]) :- ask(Atr,Q), write(Q), read(V),
asserta(asked(Atr,V)), !, V=Val.
infer(Atr,Val,AVL,AVL) :- member(av(Atr,V),AVL), !, Val=V.
infer(Atr,Val,AVL,[av(Atr,Val)|AVR]) :- frule(Atr,Val,Todo),
inferl(Todo,AVL,AVR).
inferl([],AVL,AVL):-!.
inferl(and(A,B),AVL,AVR) :- inferl(A,AVL,AV1), inferl(B,AV1,AVR), !.
inferl(or(A,B),AVL,AVR) :- inferl(A,AVL,AV1); inferl(B,AV1,AVR), !.
inferl(eq(A,V),AVL,AVR) :- infer(A,Val,AVL,AVZ), !, Val=V, AVR=AVZ.
infer(A,V) :- infer(A,V,[],R),write(R).
21

22.

©2009 Сошников Д.В.
Продукционные экспертные системы являются
достаточно эффективным классом экспертных
систем, применимым на практике (как
реляционные базы данных).
На Прологе легко реализуются прототипы
экспертных систем и оболочки для создания
экспертных систем
Можно использовать непосредственно Пролог как
язык представления знаний, для продукционных
систем оказывается более эффективным
реализация специализированных ЯПЗ поверх
синтаксиса Пролога
22