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

Классификация моделей представления знаний

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

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

Рассмотрим классификацию моделей представления знаний на основе следующих признаков классификации:

• Степень структурированности модели.

• Степень формализованности модели.

• Степень динамичности модели.

Приведем краткие характеристики изучаемых моделей.

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

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

3. Семантическая сеть отображает разнообразные отношения объектов.

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

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

Эти соображения будут пояснены при последующем изложении.

Логическая модель

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

Высказыванием называется предложение, относительно которого можно сказать – истинно оно или ложно.

Примеры. Математические высказывания:

2 = 2 – истинно,

2 = 3 – ложно.

Нематематическое высказывание: «Эрмитаж находится в Санкт-Петербурге» – истинно.

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

Название	Обозначение	Тип	Другие обозначения
Отрицание		Унарный	, ~, not, не
Конъюнкция	&	Бинарный	, and, и
Дизъюнкция		Бинарный	|, or, или
Импликация		Бинарный	,
Эквивалентность		Бинарный	,

Правила составления и преобразования высказываний называются исчислением высказываний.

Логические операции могут быть описаны с помощью так называемых таблиц истинности:

x1 x2	&
00	0	0	1	1
10	0	1	0	0
01	0	1	1	0
11	1	1	1	1

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

y = x1 x2.

Если переменные x1 и x2 интерпретировать как некоторые высказывания, то приведенная запись прочитывается так: из высказывания x1 следует высказывание x2. Действительно, данная функция ложна только тогда, когда нарушается причинно-следственная связь между x1 и x2 (истинность x1 не сопровождается истинностью x2). Операция импликации некоммутативна (x1 и x2 нельзя менять местами). Ее первый операнд называется посылкой (условием), а второй – заключением.

Пример. Обозначим через x1 высказывание «Идет дождь», а через x2 высказывание «Дорога мокрая». Тогда можно записать: x1 x2. Обратное несправедливо, т.к. дорога может быть мокрой после полива.

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

«Все люди смертны».

«Сократ – человек».

«Сократ – смертен».

Это рассуждение правильное, но оно выходит за рамки исчисления высказываний. Действительно, если приведенные высказывания обозначить соответственно через p, q и r, то получим формулу: (p & q) r. Очевидно, что истинность этого высказывания невозможно доказать формально, т.к. r не выражено через p и q. Для доказательства необходимо анализировать структуру высказывания, что невозможно, поскольку высказывание неделимо.

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

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

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

Другое определение.

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

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

Пример. Математический предикат: x > y (предикат неравенства).

Нематематический предикат: Столица (x). Этот предикат истинен, если x = «Москва», и ложен, если x = «Вологда».

При использовании исчисления предикатов объектная и функциональная модели описываются унифицированным образом с помощью предикатов первого порядка. Отличие этих описаний заключается в том, что объекты описываются отдельными соответствующими предикатами, а отношения (функциональная модель) описываются импликацией, т.е. логической формулой вывода одних фактов их других. Эти импликации называют правилами. При этом и данные (факты) и знания размещаются вместе в БЗ. Истинность предиката можно установить либо в результате отождествления его с фактом, либо в результате срабатывания правила, где он является заключением.

Достоинством логической модели является строгость формального аппарата получения решения, а именно, общей процедуры логического вывода. Однако ей свойственен и недостаток, заключающийся в ее неструктурированности. В результате для сбора информации по одному объекту приходится просматривать всю БЗ, что может приводить к большому перебору или, как говорят, к комбинаторному взрыву. По этой причине поставленные задачи могут решаться недопустимо большое время. Кроме того, работа с неопределенностями знаний должна быть запрограммирована в виде самостоятельных метаправил, что на практике затрудняет разработку баз знаний. К недостаткам логической модели следует отнести также ее монотонность – свойство, проявляющееся при работе с неполными знаниями. Напомним, что принятие решения в условиях отсутствия части информации достаточно типично для экспертных задач. Поясним это свойство монотонности.

Пусть A, B и C суть некоторые высказывания. Тогда в монотонной модели если B выводится из A, то B будет выводиться и из A C. В немонотонной модели из AC может выводитьсяB, т.е. при появлении дополнительной информации в виде C мы приходим к противоположному выводу. Таким образом, при использовании немонотонной модели существует возможность отказа от ранее сделанных выводов в целях разрешения противоречия и получения окончательного адекватного решения.

Продукционная модель

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

В продукционной модели основной единицей знаний служит правило в виде:

"Если <посылка>, то <заключение>",

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

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

"Если <посылка со степенью уверенности P1>, то <заключение со степенью уверенности P2>".

Правилами могут быть описаны сами объекты: "объект  свойство" или "набор свойств  объект", хотя чаще описания объектов фигурируют только в качестве переменных внутри правил. В основном продукционная модель предназначена для описания последовательности различных ситуаций или действий и в меньшей степени для структурированного описания объектов. В качестве характеристики, отражающей степень уверенности в данных или знаниях, могут использоваться либо вероятность, либо число в интервале [0, 10] или [0, 100]. В качестве заключения могут фигурировать либо заключительное (целевое) действие, либо промежуточный вывод, выступающий как условие в других правилах.

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

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

< А, В, С -> D, Е >,

где - импликация С -> D представляет собственно правило; А - предусловие выбора класса правил; В - предусловие выбора правила в классе; Е - постусловие правила, определяющее переход на следующее правило.

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

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

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

Семантическая сеть - это ориентированный граф, вершины которого понятия, а дуги –отношения между ними.

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

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

Пример. На рис. П2.2 приведена семантическая сеть со знаниями об автомобиле Иванова. Важной особенностью семантических сетей является наследование объектами свойств через связи типа «это». В рассматриваемом примере имеем. «Автомобиль» «имеет частью» «Двигатель», но «Волга» «это» «Автомобиль». Значит, «Волга» «имеет частью» «Двигатель».

Проблема поиска решения в БЗ типа семантической сети сводится к поиску подсети, соответствующей поставленному вопросу. Достоинство семантической сети заключается в способности эффективно описывать объектные модели предметной области. Недостаток – в отсутствии для общего случая процедуры логического вывода.

Фреймы

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

Фрейм – это структурированное представление знаний по принципу «объект -свойства». Свойства в теории фреймов называются слотами. Причем в качестве значений слотов могут выступать как обычные значения данных, так и действия, направленные на получение этих значений. Это свойство фреймов называется инкапсуляцией. Действия реализуются в виде присоединенных процедур, вызываемых по определенным условиям. По этой причине фреймовая модель более операционно-ориентирована, нежели семантическая сеть. Структуру фрейма можно представить так:

Имя фрейма (объект, ситуация)

Имя 1-го слота: значение 1-го слота.

Имя 2-го слота: значение 2-го слота.

…

Имя N-го слота: значение N-го слота.

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

Пример. Сеть фреймов.

Человек	Ребенок	Ученик
Это: млекопитающее. Умеет: мыслить.	Это: человек. Возраст: 0-16 лет. Рост: 50-180 см. Любит: сладкое.	Это: ребенок. Учится: в школе. Возраст: 7-17 лет. Носит: форму.

Понятие «Ученик» наследует свойства понятий «Ребенок» и «Человек». В результате на вопрос «Любит ли «Ученик» сладкое?» последует ответ: «Да», т.к. этим свойством обладают все дети. Наследование свойств может быть частичным. Так фреймом «Ученик» значение слота «Возраст» не наследуется, поскольку указан явно в своем фрейме.

Объектно-ориентированная модель

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

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

Пример. Объектно-ориентированная модель для задачи учета заказов “Заказ”. Модель включает четыре объекта: «Заказ», «Продукт», «Получатель», «Производитель».

	ЗАКАЗ	ПРОДУКТ	ПОЛУЧАТЕЛЬ	ПРОИЗВОДИТЕЛЬ
Атрибуты	Код покупателя Код продукта Дата составления Заказ. Количество	Код продукта Дата Остаток	Код получателя Дата Состояние р/с	Код производителя Код продукта Дата Наличие
Методы	Оформить Отложить Выполнить Оплатить Создать Уничтожить	Выдать остаток Изменить остаток	Перечислить с р/с	Отгрузить