Logo GenDocs.ru

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

Загрузка...

Лекции по базам знаний и экспертным системам - файл 1.doc


Лекции по базам знаний и экспертным системам
скачать (1259 kb.)

Доступные файлы (1):

1.doc1259kb.24.11.2011 09:16скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10
Реклама MarketGid:
Загрузка...
^

Методы дедукции на семантических сетях


Существует 4 основных класса методов:

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

  2. ^ Метод наложений: утверждение считается истинным, если в исходной сети существует фрагмент, в который изоморфно вкладывается посылка. Пример: классификация молотка.

  3. Специальные методы, основанные на свойствах используемых отношений. Например, транзитивность.

; modus tollens, Л – ложь.

  1. Методы, основанные на получении пустого дизъюнкта.

Идея дедуктивного вывода на СС состоит в следующем: все утверждения записываются в клаузальной форме. При этом истинные высказывания имеют вид: Bi←, а ложные: Aj→.

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

Пустому дизъюнкту соответствует пустая семантическая сеть.
^

Алгоритм унификации


Сорт – имя, данное совокупности известных элементов в предметной области. Понятие «сорт» является аналогом понятия «тип» в предметной области.

Алгоритм унификации сводим к определению пересечений поддеревьев в СС.

В обз=щем виде алгоритм унификации может быть сформулирован следующим образом:

Есть 2 терма: vk, tk.

Возможны следующие случаи:

  1. vk и tk – переменные, области их значений заданы перечислениями. Унификация возможна, если пересечение множеств не пусто.

  2. vk и tk – переменные, области значений заданы в виде сортов: vk /Sk и tk /S2k. Унификация возможна, если пересечение сортов не пусто.

  3. vk – переменная, tk – функция. Пересечение области значения функции и переменной не пусто. Унификация возможна, если вместо переменной подставляется функция, область определения которой сужается таким образом, чтобы область значений функции было подмножеством области значений переменной.

  4. vk и tk – функции, область значения одной из них является подмножеством области значения другой.

  5. vk – переменная, tk – константа того же сорта. В этом случае имеет место подстановка константы вместо переменной.

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

Наличие контрарной пары означает наличие предикатов вершины, к которой ведут стрелки двух типов.

Данный алгоритм является примером алгоритма дедуктивного вывода на неизменяющейся СС. Однако алгоритм не является полным, т.к. он не гарантирует получение пустого дизъюнкта для невыполнимого исходного множества дизъюнктов.
^

Алгоритм дедукции с использованием операторов удаления и расщепления вершин


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

Замечания к предыдущему алгоритму


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

Оператор удаления вершины


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

Пусть с предикатной вершиной Р связаны дизъюнкты g1,g2,…,gn. После вычисления всех возможных резольвент, дизъюнкты вершины g1,g2,…,gn удаляются и к сети добавляются новые вершины, являющиеся результатом резольвирования вершин gi.

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

Последовательно применяя операторы расщепления и удаления вершин, можно прийти к пустой сети.

Формально оператор расщепления вершины определяется следующим образом:

Пусть имеется множество дизъюнктов S={PГ, Ф}, где Р – некая предикатная литера, Г – дизъюнкт, соединяющий предикат Р, Ф – множество некоторых дизъюнктов.

В результате расщепления вершины Р получается множество дизъюнктов S={P1Г1, Ф[P1], Ф}, где запись Ф[P1] – замена всех вхождений литеры Р в формуле Ф литерой Р1.

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

^ Алгоритм вывода состоит из следующих шагов:

  1. Если в СС присутствуют вершины, которые могут быть удалены, они удаляются.

  2. Если в СС имеются вершины с мультидугами, то выполняется операция расщепления вершин. После этого снова переходим к пункту 1.

На практике данный алгоритм является весьма эффективным, однако в общем случае не является полным.

^ Пример 1: пусть множество дизъюнктов имеет вид:

g1: Q(x, y), M(y, a)  → .

g2: M(u, v), H(v, w) → Q(u, w).

g3: F(x, y), M(z, y)   → H(x, z).

g4:                            → M(b, a).

g5:                            → F(c, a).

g6:                            → M(d, c).

Соответствующая логическая сеть показана на рисунке:



Пример 2:



Пример 3: имеем невыполнимое множество дизъюнктов:

  1. N → P.

  2. P → S.

  3. S → M.

  4. M → T.

  5. → MR.

  6. T & R → Q.

  7. Q → N.

  8. M → .

  9. → T.

  10. N →  .



Пример 4: имеем множество дизъюнктов:

  1. Q(x,y) → Q(f(x),y);

  2. P(u,v) → Q(a,x);

  3.  →P(f(x),y)  P(a,z);

  4. Q(u,v) → .



Пример 5: имеем множество дизъюнктов:

  1. M(c,a) & R(a,u) → Q(f(x),z);

  2. M(z,y) & F(x,y) → H(x,z);

  3. M(u,v) & H(v,w) → Q(u,w);

  4. T(y,v) → R(a,x)  M(u,v);

  5. → S(w,c)  T(x,u)  R(b,v);

  6. F(c,y) & H(x,c) & S(u,d) → .

  7. Q(x,y) & M(y,a) → .

  8. → M(b,a);

  9. → M(d,c);

  10. → F(c,a).



1   2   3   4   5   6   7   8   9   10



Скачать файл (1259 kb.)

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

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru