План

Семантические сети

Фреймы

Правила продукций

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

Семантические сети

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

Базовый элемент семантической сети – это, например, конструкция вида:

работает в

СМИТ производственный отдел,

где «СМИТ, производственный отдел» – это узлы (некоторые понятия), а «работает в» – дуга (отношение между парами понятий).

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

В рассмотренной схеме представлен факт:

«смит работает в производственном отделе».

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

Дуга имеет направленность, благодаря чему между понятиями в рамках определенного факта выражается отношение «субъект-объект». Более того, любой из узлов может быть соединен с любым числом других узлов, в результате этого обеспечивается формирование сети фактов.

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

Наиболее распространенными являются:

БЫТЬ ЭЛЕМЕНТОМ КЛАССА (ЯВЛЯТЬСЯ) – означает, что объект входит в состав данного класса, например

является

СМИТ руководитель,

что обозначает «СМИТ является членом класса руководителей».

ИМЕТЬ (ЕСТЬ) – позволяет задавать свойства объектов, отражает общие представления о них или указывает, что одно понятие представляет часть другого. Изобразим с помощью группу сложных фактов:

“СМИТ является руководителем”;

“СМИТ работает в производственном отделе, расположенном в здании 1”;

“СМИТУ 40 лет”;

“У СМИТА голубые глаза”.

Здание 1

местонахождение

производственный отдел

работает в

голубые глаза СМИТ руководитель

есть

40 лет

Рис.1.

ЯВЛЯТЬСЯ СЛЕДСТВИЕМ – отражает причинно-следственные связи между двумя объектами в семантической сети, например:

“Увольнение Смита является следствием нарушения им трудовой дисциплины”.

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

Например, если нужно представить следующую фразу:

«СМИТ1 проработал на СМИТА2 с апреля 2001 по май 2002»,

то ее невозможно представить при помощи введенных ранее допущений.

В этом случае нужно разработать представление относительно глаголов в дополнение к существительным.

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

работа

действие

до от

май 2002 <раб1> апрель2001

датив (dative) агент

<см1> <см2>

Рис.2

Конкретное событие, заключающееся в работе у кого-то, обозначено <раб1>. Его происхождение от узла прообраза «работа» указывается при помощи дуги «действие», в угловых скобках – узел события.

После идентификации события <раб1> можно произвести привязку других отношений, с помощью которых представляются понятия о работе:

дата начала (через связь «с») и дата окончания работы (через связь «до»).

Для отдельных ЭС были разработаны полные непротиворечивые наборы вербальных отношений – падежных отношений (Ч. Филмор).

Примерный набор «падежных» отношений может включать:

Агент – исполнитель (инициатор) действия, выражаемого глаголом;

Объект – имя существительное, на которое распространяется действие или состояние, выражаемые глаголом;

Местоположение – место действия или состояния, выражаемое глаголом;

Датив – лицо, к которому имеет отношение действие или состояние, выражаемые глаголом.

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

2. Фреймы

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

С этой целью было введено представление знаний, основанное на использовании фреймов, что позволяет отражать родовидовую иерархию понятий в БЗ в явной форме.

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

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

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

Имя: РУКОВОДИТЕЛЬ

имя: __________________

возраст:________________

адрес: __________________

отдел:__________________

зарплата:________________

дата начала:______________

до: _____________________

Рис.3 – «скелетный» фрейм.

Проанализируем рис.3 – во-первых, фрейм имеет имя для идентификации описываемого им понятия; во-вторых, он состоит из слотов (на рис.3 слева) – тут все слоты пустые. Заполним слоты – рис.4:

Имя: РУКОВОДИТЕЛЬ

имя: агрегат (фамилия, имя, отчество)

возраст: агрегат (годы)

адрес: АДРЕС

отдел: диапазон (производство, администрация)

зарплата: ЗАРПЛАТА

дата начала: агрегат (месяц, год)

до: агрегат (месяц, год) (по умолчанию: теперь)

Рис.4

Тут присутствуют различные типы заполнителей слов:

константы,

имена других фреймов системы, на которые делается ссылка (АДРЕС, ЗАРПЛАТА)

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

Заполним фрейм "ЗАРПЛАТА", относящийся к фрейму «РУКОВО-ДИТЕЛЬ», содержащий 4 слота, один из которых требует двойного заполнения.

Имя: ЗАРПЛАТА

почасовая заработная плата: агрегат (у.е. в час)

код налога: агрегат: (код налога) (по умолчанию: непредвиденный)

налог на дату: агрегат (месяц, год)

вычислить ((ОПЛАТА НАЛОГА) (код налога))

Рис.5

Здесь демонстрируется возможности вставления во фреймы обычных программ – заполнение слота «налог на дату» (вычислить ((ОПЛАТА НАЛОГА) (налог)). Чтобы связать все фреймы системы воедино, они обычно организуются в сети. Когда скелетный фрейм заполняется конкретной информацией, то ему присваивается уникальное имя.

Заполним фрейм, изображенный на рис.3. – его уникальное имя «см-1»:

Имя: см-1

имя: смит, джон

возраст: 40

адрес: адр-1

отдел: производственный

зарплата: зар-1

дата начала: апрель 20001

до: теперь

Рис.6

В рассматриваемом примере имя «см-1» используется совместно с именами общего вида фреймов «зар-1» и «адр-1», служащих для идентификации сведений о зарплате и адресе субъектов «смит, джон».

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

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

Недостатки фреймовых систем:

высокая сложность, что сказывается в снижении скорости работы механизма ввода-вывода и в увеличении трудоемкости внесений изменений в родовидовую иерархию;

большая стоимость ЭС, где для представления знаний используются фреймы.

3.Правила продукций

Это один из самых распространенных форматов для представления знаний, основанный на продукционных правилах типа:

"ЕСЛИ условие, ТО действие",

причем первая их часть – антецедент (посылка правил) – состоит из элементарных предложений, соединенных логическими связками И, ИЛИ, НЕ;

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

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

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

ЭС, базирующиеся на продукциях, состоят из трех компонентов:

БЗ, которая содержит правила продукций;

БД, которая отображает текущее состояние задачи;

Управляющей структуры – механизм вывода (интерпретатор правил), решающая, какое из правил продукции следует применить следующим.

Механизм вывода выполняет две функции:

во-первых – просмотр существующих фактов из рабочей памяти и правил из БЗ и добавление в рабочую память новых фактов;

во-вторых – определение порядка просмотра и применения правил.

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

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

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

истина или ложь.

Например, у нас есть высказывания: «цена высокая», «цена низкая», «в отделе работает 15 человек». Из них можно получить:

Цена высокая или низкая.

Цена высокая и в отделе работает 15 человек.

Если Цена не высокая, то Цена низкая.

И наоборот, любое высказывание может быть разделено на несколько высказываний при помощи выделенных слов-связок.

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

Обозначим элементарные высказывания символами А и В, а для обозначения выделенных слов-связок применим следующие символы:

щ – «не», Ъ – «или», Щ – «и», Й – «если».

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

Разобьем данное предложение на части – Сидоров (субъект), бухгалтер (свойства субъекта):

бухгалтер (Сидоров).

Или «Василий – начальник Петра»: тут два субъекта, и отношение между ними «.... – начальник .....», получаем:

начальник (Василий, Петр).

Вместо имен можно подставить переменные х, у, z, тогда:

бухгалтер (х),

начальник (у, z).

Рассмотрим предложение: У каждого бухгалтера есть начальник. Для формального представления этого предложения необходимо использовать конструкции вида:

«существует такой х, что ...», «для любого х ....».

Введенные допущения называются кванторами общности и существования:

"х( ),$у( ).

Тогда предложение можно записать: "х$у(бухгалтер(х) Й начальник(х,у)).

Важна последовательность постановки кванторов: если переменим местами: $у"х (бухгалтер(х) Й начальник(х,у)),

то это будет обозначать:

У всех бухгалтеров общий начальник.

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

Введем понятие предиката.

Функцию от буквенных переменных , принимающую логические значения y (0 или 1), назовем n-местным предикатом или просто предикатом. Любой конечный предикат можно задать с помощью таблицы его значений, где каждому набору значений аргументов ставится в соответствие значение предиката у.

Алгебра предикатов характеризуется алфавитом букв А, состоящим из k различных символов и алфавитом переменных b, состоящим из n различных символов .

Для построения любой формулы будем пользоваться символами:

– буквами –

– переменными –

– знаками дизъюнкции – ‘Ъ ’ и конъюнкции – ‘Щ’;

– скобками – ‘(’ и ‘)’;

– логическими константами – ‘0’ и ‘1’.

Под любой формулой алгебры конечных предикатов будем понимать:

а) формула может быть символом ‘0’ или ‘1’;

б) все выражения вида ai(xj), где индекс i изменяется от 1 до k, а индекс j – от 1 до n, также считаем формулами;

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

г) если выражения А и В – формулы, то выражение (логическое умножение А и В) – называем формулой.

Рассмотрим тождества алгебры предикатов:

Законы идемпотентности:

, .

Законы коммутативности:

,

Законы ассоциативности:

,

Законы элиминации (или поглощения):

,

Законы дистрибутивности:

A (BЪC) є AB Ъ AC,

A Ъ BC є (AЪB) (AЪC).

Тождества для констант:

, .

, .

Тождества для констант с отрицанием:

Закон двойного отрицания:

Закон исключенного третьего:

Закон противоречия:

Когда мы рассматривали пример:

Если цена не высокая, то цена низкая, то мы обратили внимание на связку: Если ...., то...., которую обозначили значком Й.

Эта операция называется импликацией, и определяется как:

А Й В є щ А Ъ В,

где А и В – произвольные формулы алгебры предикатов,

є – операция, обозначающая тождественное равенство правой и левой части.

Читается так: «А влечет В», где А – посылка, В – заключение.

Рассмотрим свойства импликации:

Рефлективность импликации: .

Транзитивность импликации: .

Докажем данное тождество:

Свойства логических констант для импликации

, .

.

4.Закон дедукции:

.

Закон контрапозиции:

Закон импортации:

.

Закон экспортации:

.

Закон приведения к абсурду:

.

Законы дистрибутивности:

.