Ю. А. Григорьев, Г. И. Ревунков - Банки данных

5. Модели представления знаний

адрес: Адрес XI отдел: агрегат (ВЦ) есть-нек: Служащий XI

имя: Программист есть-нек: Служащий

определение-понятия: специалист по программированию

имя: Адрес X есть-нек: Адрес

город: агрегат (Москва) улица: агрегат (Уральская) номер-дома: агрегат (44) номер-корпуса: номер-квартиры: агрегат (58)

имя: Адрес есть-часть: Служащий

определение-понятия: местонахождение, местожительство

имя: Зарплата X почасовая-зарплата:...

код-налога: агрегат (1) начисление: вычислить (Оплата) есть-нек: Зарплата

имя: Зарплата есть-часть: Служащий

определение-понятия: плата за работу

имя: Служащий X фамилия: агрегат (Иванов)

имя: агрегат (Петр)

отчество: агрегат (Николаевич) табельный-номер: агрегат (5566) есть-нек: Служащий

имя: Служащий фамилия: есть-часть, наследуется

имя: есть-часть, наследуется отчество: есть-часть, наследуется

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

Для указания факта, что слот данного фрейма наследуется базовым фреймом, имеющим связь ЕСТЬ-НЕК с данным фреймом, в примере использовано ключевое слово «наследуется». Это означает, что управляющая профамма при организации базового фрейма одновременно организует в нем слоты с именами Фамилия, Имя, Отчество, Та­ бельный номер (речь идет о фреймах РуководительХ,..., Профаммист XI,...).

130

5.3. Фреймы

ЕСТЬ-НЕК ЕСТЬ-НЕК

- ЕСТЬ-НЕК.

-ЕСТЬ-НЕК-

Рис. 5.2. Пример фрагента фреймовой семантической сети

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

Пример фрагмента сети, построеной с помощью фреймов, приведен на рис. 5.2.

Фреймоподобные структуры, получившие название «сценариев», ши­ роко используются в системах для представления стереотипной последова­ тельности событий.

Например, типичным сценарием может служить посещение библио­ теки, включающее следующие сцены.

1.Приход в библиотеку.

2.Нахождение свободного места.

3.Заказ литературы.

4.Получение литературы.

5.Работа с литературой.

6.Возвращение литературы.

7.Уход из библиотеки.

Каждая сцена, в свою очередь, может быть описана своим фреймом.

131

5. Модели представления знаний

Для программирования систем, использующих фреймы, как и для других видов СЕМС, широко используют алгоритмический язык ЛИСП. Существует также ряд разработанных специально систем, облегчающих конструирование на основе фреймов различных процедур обработки зна­ ний. Примером СЕМС является гипертекстовая структура.

Идея фреймов используется для решения разнообразных задач в ин­ теллектуальных системах.

5.4. Представление знаний с помощью логики предикатов

Данный подход к представлению классов объектов и отношений меж­ ду ними базируется на использовании понятий исчисления предикатов. Суть заключается в следующем: взаимосвязи между различными объектами опи­ сываются с помощью предикатов. Если Р есть w-местная предикатная пере­ менная, а Х), ^2? .., ^/7 — предметные переменные (аргументы предиката), то, по определению, выражение есть атомарная (элементарная) формула. Со­ держательно эта формула означает высказывание, гласящее, что объекты Хь Х2,..., Jc„ связаны отношением Р.

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

Например, факт «Петров работает программистом» можно предста­ вить следующим образом:

Работает (Петров, Программист)

Причем теперь в системе все предикаты такого типа должны в списке аргументов на первом месте содержать фамилию служащего, а на втором месте — название должности, например:

Работает (Иванов, Лаборант) Работает (Кузнецов, Слесарь) и т.п.

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

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

Ввысказывании, записанном в нотации исчисления предикатов, неко­ торый объект может быть представлен как КОНСТАНТА, т.е. как конкрет­ ный индивидуум или класс индивидуумов, или как ПЕРЕМЕННАЯ, в ре-

132

5.4. Представление знаний с помощью логики предикатов

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

Является (X, Специалист по ЭВМ).

Одна из возможных интерпретаций этого предиката может быть та­ кой: имеется некоторый объект X, который является специалистом по ЭВМ.

Когда переменной ставится в соответствии определенное имя некото­ рого объекта (т.е. некоторой константы), то говорят, что происходит порож­ дение экземпляра этой переменной.

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

И (and, л, &), ИЛИ (or, V,), НЕ (not, -i),

ИМПЛИКАЦИЯ (-^). Импликация читается как:

ЕСЛИ ..., ТО ....

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

V — квантор общности; 3 — квантор существования.

Например, пользуясь кванторами, предложение «все специалисты по ЭВМ являются операторами» можно представить следующим образом:

(VX) (Специалист по ЭВМ (X) -> ОПЕРАТОР (X)),

а предложение «некоторые специалисты по ЭВМ являются операторами»: (ЗХ (Специалист по ЭВМ (X) -> ОПЕРАТОР (X)).

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

(VX) (3Y) (Служащий (X) -> Руководит (Y, X))

может быть интерпретировано как «каждым служащим X руководит неко­ торое лицо Y». А утверждению

(ЗУ) (VX) (Служащий (X) -> Руководит (Y, X))

соответствует интерпретация «есть такое лицо Y, которое руководит всеми». Конструирование сложных высказываний из элементарных с помо­

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

133

5. Модели представления знаний

так называемых, правильно построенных формул (ППФ), строить новые правильно построенные формулы. Рассмотрим определение ППФ (далее будем говорить логическая формула).

1.Атомарный предикат является логической формулой.

2.Если А^ В — логические формулы, то Л л

В-^ А также являются логическими формулами.

3.Если С{Х) — логическая формула, то и (VX)C(X), и (ЗХ) С(Х) так­ же являются логическими формулами.

4.Все формулы, полученные повторением конечного числа раз фор­ мул 1, 2, и 3, являются логическими формулами.

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

Рассмотрим некоторые правила вывода.

1.Из двух логических формул А иА -^ В выводится новая логическая формула В (Modus ponens). Для описания правил вывода во многих случаях используется нотация, когда над чертой записывается группа выражений, выступающих в качестве посылки, а под чертой записывается выражение, которое из них выводится:

В, А

В

Например: «Если моя программа правильна, то она будет работать; моя программа правильна; следовательно, она будет работать».

2. Modus tollens (отрицательный способ рассуждений):

-А

Например: «Если моя программа правильна, то она будет работать;

моя программа небудет работать;следовательно,она неправильна».

3. Двойное отрицание:

А

-(-А)'

Например: «Моя программа работала; следовательно, моя программа не не работала».

4. Введение конъюнкции:

А, В

ААВ'

134

5.4. Представление знании с по.мощью логики предикатов

Например: «Моя программа работала, она правильна; следовательно, моя программа работала и она правильна».

5. Заключение истинности суждения независимо от посылки:

А->В\-^А-^В

В

Например: «Если моя программа правильна, то она будет работать; если моя программа неправильна, то она будет работать; моя программа будет работать».

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

{'iX)W{X\A

W{A)

Например: «Все предметы, являющиеся ЭВМ, надежны; IBM PC — ЭВМ; следовательно, IBM PC надежна».

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

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

1) установить соответствие между константами логики предикатов и сущностями описываемой ПО (в качестве констант выступают имена сущ­ ностей);

2)установить соответствие между атомарными предикатами и отно­ шениями, между сущностями, имеющими место в ПО;

3)выполнить описание функциональных отношений ПО с помощью формул логики предикатов;

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

Пример. БД представлена совокупностью трех фактов:

1:Руководит (Петров, Иванов) — интерпретация: Петров руководит Ивановым;

2:Руководит (Иванов, Кузнецов) — интерпретация: Иванов руководит Куз­ нецовым;

3:Руководит (Кузнецов, Яковлев) — интерпретация; Кузнецов руководит Яковлевым.

Эти факты истинны, поскольку имеют место в данной ПО, и потому их пред­ ставляют в базе данных.

Далее описывают два прикладных правила (т.е. функциональных отношения), которые имеют место в рассматриваемой ПО.

135

5. Модели представления знаний

Правило 1: V(X, Y) (Руководит (X, Y) -^ Отчитывается (Y, X)) — интерпре­ тация: «Для всех значений X и У, если X руководит У, то У отчитывается перед X».

Правило 2: V(X, У, Т) (Руководит (X, У) л Отчитывается (Т, У) -> Отчитыва­ ется (Т, X)), где X, У, Т — переменные; интерпретация: «Для всех значений X, У, Т, если X руководит У и Т отчитывается перед У, то Т отчитывается перед X».

Теперь посмотрим, как в такой модели можно обрабатывать запросы пользо­ вателей. Например, поступает следующий запрос: «Проверить, имеет ли место в ПО факт «Яковлев отчитывается перед Ивановым» (т.е. иначе сделать заключение, что «Яковлев отчитывается перед Ивановым».

Итак, в данной базе данных непосредственно такого факта нет. Однако пре­ дикат, описывающий интересующее нас отношение, встречается в правилах 1 и 2. Применим правило 1 к факту 3. Выполнив подстановку значения констант из факта 3 на позиции соответствующих переменных в правиле 1, получим следующую логиче­ скую формулу:

Руководит (Кузнецов, Яковлев) -> Отчитывается (Яковлев, Кузнецов).

Применяя к ней и факту 3 правило вывода Modus ponens, получим логиче­ скую формулу

Отчитывается (Яковлев, Кузнецов),

описывающую тот факт, что Яковлев отчитывается перед Кузнецовым. Так как применялось правило вывода и исходные выражения были истинными, то, следова­ тельно, и данное заключение является истинным. Итак, данный факт имеет место в данной ПО, хотя в явном виде он в базе и не представлен.

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

Руководит (Иванов, Кузнецов) л Отчитывается (Яковлев, Кузнецов) -^ -> Отчитывается (Яковлев, Иванов).

Применяя к факту 2 и к факту (Отчитывается Яковлев, Кузнецов) правило вывода «введение конъюнкции», получим логическую формулу Руководит (Иванов, Кузнецов) л Отчитывается (Яковлев, Кузнецов).

Применяя к ней и к формуле

Руководит (Иванов, Кузнецов) л Отчитывается (Яковлев, Кузнецов) -> -» Отчитывается (Яковлев, Иванов)

правило вывода Mondus ponens, получим логическую формулу Отчитывается (Яковлев, Иванов),

описывающую тот факт, что Яковлев отчитывается перед Ивановым.

Так как применялось правило вывода и исходные посылки были истинными, то данное заключение является истинным. Теперь можно дать утвердительный ответ на запрос, действительно ли в ПО имеет место факт, что Яковлев отчитывается пе­ ред Ивановым.

136

5.5.Системы продукций

5.5.Системы продукций

Этот класс моделей при представлении в системе знаний базируется на использовании так называемых продукций. Продукция — это правило вида:

ЕСЛИ левая — часть — правила, ТО — правая — часть — правила.

Если левая часть правила является посылкой, а правая — заключе­ нием, то имеют дело с элементарным логическим актом (логической операцией).

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

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

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

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

имеющих место в предметной области; управляющую структуру (УС) (или, как ее еще называют программа-

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

Заметим, что база правил и БД в совокупности образуют БЗ.

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

Используя нотацию исчисления предикатов, продукцию ЕСЛИ А ТО В можно записать в виде Av В,иъ этом случае база знаний системы описыва­ ется в виде совокупности предложений:

137

5. Модели представления знаний

Г4

факты

правила

4 л А. -> В.

Управляющая структура является третьим необходимым компонен­ том процесса обработки знаний в данной модели. Она определяет порядок и последовательность применения правил. Основной задачей в модели систем продукций является проверка наличия в БЗ фактов, касающихся условной (левой) части правила.

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

Варианты управляющих структур в реальных системах разнообразны. Есть УС, которые перебирают правила последовательно, т.е. работают по принципу: поочередно опробовать правила, которые заданы последователь­ ным списком, пока одно из них не сработает; затем следовать к началу спи­ ска правил и начать процесс опробования сначала; процесс закончить при встрече оператора «стоп». Такая УС независима от ПО и является универ­ сальной. Но правила в ней должны быть независимы от порядка расположе­ ния в базе.

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

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

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

138