2.2.5. Вывод на знаниях

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

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

База правил (БП) — формализованные с помощью правил продукций знания о конкретной предметной области.

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

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

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

Действие компоненты вывода основано на применении правила вывода, называемого Modus Ponendo Ponens (правило отделения), которое звучит в продукционных системах так: «если верно A и верно, что из A следует B, то верно B». То есть если в РП присутствует факт A, и в БП существует правило вида «ЕСЛИ A, ТО B», то факт B признается истинным и заносится в рабочую память. Такой вывод легко реализуется на ЭВМ.

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

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

Рисунок 2.3. Цикл работы механизма вывода.

В цикле выполняются следующие операции:

1) сопоставление — образец правила сопоставляется с имеющимися в РП фактами;

2) выбор — если в конкретной ситуации может быть применено сразу несколько правил, то из них выбирается одно, наиболее подходящее по заданному критерию, т. е. происходит разрешение конфликтного выбора;

3) срабатывание — если образец правила при сопоставлении совпал с какими-либо фактами из РП, то правило срабатывает, оно отмечается в БП;

4) действие — рабочая память подвергается изменению путем добавления в нее заключения сработавшего правила.

Условием окончания цикла является либо исчерпание всех правил из БП, либо выполнение некоторого условия, которому удовлетворяет содержимое рабочей памяти (например, появление в ней какого-то образца), либо комбинация этих способов.

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

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

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

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

Рассмотрим пример:

Фрейм «Научная конференция»

Имя слота	Значение слота	IF-NEDDED	IF-ADDED	IF-REMOVED
Дата Место проведения Тема доклада Докладчик	1.06. 10:10 Аудитория 437 Генетические алго-ритмы при поиске Сидоров И.И.	КТО?	ЗАКАЗ

При попытке вставить значение в слот Место проведения автоматически запускается демон ЗАКАЗ, который является процедурой. Демон КТО? автоматически запускается при обращении к слоту Докладчик. Если значение этого слота не определено, то происходит генерация запроса «Кто выступает?», получение ответа и его запись в качестве значения слота.

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

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

Для рассмотрения вывода в логических моделях необходимо ввести следующие определения.

Неравнозначностью (исключающим «или», сложением по модулю 2) двух высказываний A и B называется высказывание, истинное, когда истинностные значения A и B не совпадают, и ложное в противном случае. Обозначение: , читается «или A, или B», «или» понимается в разделительном смысле. Составное высказывание «Сегодня понедельник или вторник» состоит из двух простых: A = «Сегодня понедельник»; B = «Сегодня вторник». Эти высказывания соединены связкой «или» в разделительном смысле. Таким образом, данное высказывание представимо формулой

.

Если описание системы представлено совокупностью сложных высказываний —логических формул, истинных для данной системы, то с помощью логических преобразований могут быть получены новые представления, характеризующие данную систему (истинные для данной системы). Таким образом, появляется возможность вывода новых знаний из имеющихся с помощью допустимых в логике преобразований. Итак, операция, называемая выводом, — это получение заключения из группы заданных представлений; вывод является формулой, полученной из некоторой группы описанных формул. Как правило, эти формулы истинны при каких бы то ни было допустимых интерпретациях.

Действие компоненты вывода в логических моделях основано на применении следующих правил вывода:

1. Modus Ponens «если верно A и верно, что из A следует B, то верно B»:

2. Modus Tollens «если верно, что из A следует B и B ложно, то ложно A»:

3. Modus Ponendo Tollens «если верно или A, или B (в разделительном смысле) и верно одно из них, то другое ложно»:

4. Modus Tollendo Ponens

а) «если верно A или B (в разделительном смысле) и ложно одно их них, то верно другое»:

б) «если верно A или B (в неразделительном смысле) и ложно одно из них, то верно другое»:

5. Правило транзитивности «если из A следует B, а из B следует C, то из A следует C»:

6. Закон противоречия «если из A следует B и , то ложно A»:

7. Правило контрапозиции (или метод резолюций) «если из A следует B, то из того, что ложно B, следует, что ложно A»:

Примеры

2.2. Студент сдал экзамен на «хорошо» или «отлично». Он не получил отличной оценки. Следовательно, он сдал экзамен на «хорошо».

Введем обозначения: A = «студент сдал экзамен на хорошо», B = «студент сдал экзамен на отлично», тогда приведенное рассуждение описывается схемой

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

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

Выделим простые высказывания и введем обозначения: A = «Фирма приглашает на работу крупного специалиста в области новейшей технологии»; B = «Фирма считает данную новейшую технологию привлекательной»; C = «Фирма разворачивает работу по изменению технологии производства своего традиционного продукта»; D = «Фирма начинает разработку нового продукта».

С учетом принятых обозначений умозаключение имеет вид: «Если A, то B и (C или D), A. Следовательно, C или D)».

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

Проверим методом эквивалентных преобразований:

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

2.4. Простой пример работы продукционной системы представлен на рис. 2.4. Данная продукционная система сортирует строку, состоящую из символов а, Ь и с. В этом примере продукция является допустимой, если ее условие соответствует части строки в рабочей памяти. При выполнении правила подстрока, которая соответствовала его условию, заменяется Рис. 2.4. строкой из правой части правила.

Вопросы

2.1. Перечислите основные актуальные в настоящее время проблемы в области искусственного интеллекта.

2.2. Что такое знания с точки зрения систем искусственного интеллекта?

2.3.Что такое представление знаний?

2.4. Перечислите процедурные и декларативные модели представления знаний. Чем отличаются знания в процедурных и декларативных методах представления знаний?

2.5. В чем состоит метод представления знаний с помощью продукций?

2.6. Как осуществляется вывод на знаниях в продукционной модели?

2.7. На чем основано представление знаний с помощью семантической сети?

2.8. Как фреймовые системы могут использоваться для представления знаний?

2.9. Дайте характеристику логическим моделям.

2.10. Опишите синтаксис исчисления высказываний.

2.11. В чем заключается семантика исчисления высказываний?

2.12. Что значит понятие «предикат»?

2.13. Каких типов могут быть термы?

2.14. Приведите рекурсивное определение формулы логики предикатов.

2.15. Дайте определение связанной и свободной переменной.

2.16. В чем заключается метод резолюций?

2.17. Что такое база знаний? Чем она отличается от базы данных?

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

2.19. В чем существенное различие фреймов от разделенных семантических сетей?

2.20. Приведите пример представления знаний с помощью фреймовой модели.

Упражнения

2.1. Используя таблицы истинности, докажите следующие тождества для логических выражений P, Q и R:

(закон контрапозиции импликации);

(законы де Моргана);

(законы коммутативности);

(ассоциативные законы)

(дистрибутивные законы)

2.2. Оператор («исключающее ИЛИ») можно определить следующей таблицей истинности (И —ИСТИНА, Л —ЛОЖЬ):

P	Q	P Q
И И Л Л	И Л И Л	Л И И Л

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

Докажите их эквивалентность с помощью таблиц истинности.

2.3. Логический оператор означает «тогда и только тогда». Выражение эквивалентно выражению Базируясь на этом определении, докажите, что выражение логически эквивалентно выражению а) используйте при этом таблицы истинности; б) воспользуйтесь последовательностью подстановок с учетом тождеств, приведенных в упражнении 2.1.

2.4. Докажите, что в исчислении высказываний импликация транзитивна, т. е. что

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

2.6. Я женился на вдове (назовем ее W), которая имеет взрослую дочь (давайте назовем ее D). Мой отец (F), который весьма часто навещал нас, влюбился в мою падчерицу и женился на ней. Поэтому мой отец стал моим зятем, а моя падчерица стала моей мачехой. Спустя несколько месяцев моя жена родила сына , который стал шурином (зятем) моему отцу, а потому моим дядей. Жена моего отца, т. е. моя падчерица, тоже родила сына . Используя исчисление предикатов, создайте набор выражений, описывающих данную ситуацию. Добавьте выражения, определяющие основные отношения в семье, в том числе определение тестя (или свекра), и, используя правило modus ponens, докажите заключение «Я сам себе дедушка».

2.7. Пусть есть предикат ЛЮБИТ(x, y), который описывает отношение «х любит у». Считая, что порядок связывания переменных кванторами определяется при чтении предиката слева направо, найдите соответствие между предложениями и описываемыми ими отношениями:

№	Предложение	№	Отношение
1		a	Существует человек, который кого-нибудь любит
2		b	Для всех х существует человек у, которого любит х
3		c	Для каждого человека существует человек, который его любит
4		d	Существует такой человек у, что его любят все х
5		e	Существует человек, который любит всех людей
6		f	Все люди любят все люди