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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

1. Продукционная модель представления знаний

Определение: продукционная модель или модель, основанная на правилах, позволяет представлять знания в виде правил

«Если А, то В».

Сложные продукции

«Если А₁ и А₂, то В»

«Если А₁ или А₂, то В»

«Если не А, то В»

«Если А₁ и А₂ или А₃, то В»

«Если А₁ и (А₂ или А₃), то В»

«Если А, то В₁ и В₂»

«Если А, то В₁ ИЛИ В₂»

Связанные продукции

«Если А, то В»

«Если В, то С»

Функционирование продукций

Набор продукций

1. «Если А, то С»
2. «Если В и С, то D»

Начальные данные: А, В

Вывод

1
А	С	2
В		D

Пример: сортировка строки из трех символов a, b и c.

Набор продукций

1. «Если ba, то ab»
2. «Если ca, то ac»
3. «Если cb, то bc»

Начальные данные: cbca

Вывод

	2	cbca	3
	cbac		bcca
1		3	2
cabc		bcac	bcac
2		2	2
acbc		bacc	bacc
3		1	1
abcc		abcc	abcc

Представление данных и правил

Пример: диагностика инфекционных заболеваний

Представление данных

Объект - атрибут - значение

Объект	Атрибут	Значение
культура	место	кровь
микроорганизм	реакция	грамотрицательная
микроорганизм	форма	палочка
пациент	принадлежит к группе риска	истина

Словарь предметной области!

(object, attribute, value)

(object, (attribute1, value), (attribute2, value))

Представление правил

Если … , то название микроорганизма - pseudomonia aeruginosa

Объект	Атрибут	Значение
микроорганизм	название	pseudomonia aeruginosa

Представление правил зависит от представления данных!

Имя продукции.

Входные данные.

Логическая функция.

Выходные данные.

(RuleName

Data1(object, attribute, value): boolean,

Data2(object, attribute, value): boolean,

DataN(object, attribute, value): boolean,

LogicFunction(Data1, Data2, …,DataN): boolean

NewData1 = (object, attribute, value),

NewData2 = (object, attribute, value),

NewDataM = (object, attribute, value)

Конфликты

Набор продукций

1. «Если А и В, то Е»
2. «Если В и С, то D»

Начальные данные: А, В, С

Какую продукцию выбрать?

Правила разрешения конфликтов:

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

Принцип «стопки книг» - каждой продукции сопоставляется частота ее использования (динамический приоритет).

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

Поиск «в глубину» - приоритет у продукций, реагирующих на самые «свежие» данные.

Поиск «в ширину» - приоритет у продукций, реагирующих на самые «старые» данные.

Принцип разнообразия - каждая продукция запускается только один раз.

Обычно используют несколько правил.

Порядок применения правил фиксирован.

Процесс вывода

Направление поиска. Прямой и обратный вывод

Прямой вывод (от данных к цели)

Исходные факты в рабочей памяти.

Циклический процесс вывода.

Останов: нет запускаемых продукций или достигнуто целевое утверждение.

Обратный вывод (от цели к данным)

Цель и исходные факты в рабочей памяти.

Ищем продукции, подтверждающие цель.

Останов: продукции подтверждают или опровергают цель.

Достоинства продукционных моделей

Универсальность (может быть представлена практически любая область знаний).

Модульность (удаление и добавление продукций выполняется независимо).

Декларативность (знания отделены от механизма вывода). Ант. Процедурные.

Естественность вывода (аналог процесса рассуждений эксперта).

Асинхронность (перспективность реализации на параллельных ЭВМ).

Недостатки

Низкая эффективность процесса вывода (много времени уходит на проверку условий применения правил).

Метод борьбы - метапродукции. Объединять продукции в группы и, исходя из состояния рабочей памяти, выбирать сначала группу.

Проверка непротиворечивости (при случайном выборе продукции).

Часто пишут

А В

Знак «логического следования». Нет никаких ограничений на смысл символов А и В. Это не формулы! Не надо доказывать!

Надо выяснить, можно ли уточнить этот переход?

А А₁ А₂ А₃ В

Будет проще объяснить пользователю, как получилось решение.

Правила-продукции соответствуют знаниям в долговременной памяти человека.

Рабочая память аналогична кратковременной памяти человека.

Нельзя навязывать форму представления знаний!

Интуиция. Принятия решения на основе данных, которые мы не осознаём.

На каждую интеллектуальную систему можно навесить ярлык: это знания эксперта Иванова на текущий момент времени в понимании инженера по знаниям Сидорова.

2. Семантическая модель представления знаний

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

Три вида объектов

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

Например, «изделие», «предприятие», «сотрудник» - классы предметной области.

Индивидный объект - экземпляр класса.

Например, «инспектор Петренко П.П.»

Агрегатный объект - составной объект, образованный из других объектов.

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

Основные виды связей

Отношение «род - вид» - связь между обобщенными объектами А и В, означающая, что понятие А более общее, чем понятие В.

Например, «животное» - это родовое понятие для объекта «птица».

Объект В наследует свойства объекта А.

Отношение «является представителем» - связь между обобщенным и индивидным объектом, когда индивидный объект является представителем некоторого класса.

Например, «хомячок Хома» экземпляр класса «хомяк».

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

Условные обозначения

Отношение «род - вид» - AKO (от англ. a kind of - разновидность)

Отношение «является представителем» - IS-A (от англ. is a member of the class - быть представителем класса)

Отношение «является частью» - PART-OF

Обратное отношение «имеет» - HAS

Другие виды связей

Причина - следствие

Количественные (>, <, =)

Пространственные (далеко от, близко от, за, под, над …)

Временные (раньше, позже, в течение)

Атрибутивные (иметь свойство, иметь значение)

Логические (И, ИЛИ, НЕ)

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

Три вида лингвистических объектов

Объекты-понятия - сведения о физических и абстрактных объектах предметной области

Объекты-события - абстрактные или конкретные действия, которые могут привести к изменению состояния предметной области

Объекты-свойства - уточняют понятия и события.

Указывают характеристики понятий (цвет, форма, размеры).

Фиксируют параметры событий (место, время, продолжительность)

Пять видов лингвистических отношений

Агент - отношение между событием и тем кто (что) его совершает

Объект - отношение между событием и тем, над чем выполняется действие

Инструмент - объект, с помощью которого совершается действие

Место - место совершения события

Время - время совершения события

Пример: «Иван закрепил деталь клеем»

	агент
		Иван
	объект
		Деталь
Закрепил	инструмент
		Клей
	время
		Прошедшее

Концептуальные графы

Вершины - объекты и отношения

Ребра связывают объекты и отношения

Пример: «Мяч имеет красный цвет»

Преимущество - просто представлять n-арные отношения:

				Множитель 1
Результат		Произведение
				Множитель 2

Предложения в виде концептуального графа

Пример: «Иван закрепил деталь стула клеем»

Числовой маркер - различает экземпляры объектов с одинаковыми именами

Обобщенные маркеры - когда две различные вершины графа представляют один и тот же объект. «Маляр испачкал свою руку краской»

Выводы на семантических сетях

Сопоставление с образцом.

Проблема: сформулировать вопрос на языке сети.

«Существует ли такая птица, которая умеет петь и имеет желтый цвет?» продукционный семантический фреймовый знание



Задача: найти соответствующий фрагмент в сети.

Дедуктивный вывод - исходя из имеющихся данных, получить заключение

Пример: решение математических и физических задач

Дано: знания человека о прямоугольном треугольнике

Требуется: по двум катетам a и b определить радиус r вписанной окружности

Как это делает человек: из (3) найдем гипотенузу c, затем из (6) - полупериметр p, потом из (7) - площадь S, наконец, из (8) - радиус r вписанной окружности.

Как научить делать это компьютер?

Элемент знаний в виде фрагмента семантической сети

Отношение может вычислить значение объекта, если известны значения всех остальных объектов

База знаний в виде семантической сети

Запишем исходные значения в объекты a и b.

Отношения , и могут вычислить значение объектов c, и S.

Отношения , и могут вычислить значение объектов p, R и .

Отношение может вычислить значение объекта r.

3. Фреймовая модель представления знаний

Определение (М. Минский, 1975): фреймы - это структуры данных, предназначенные для представления стереотипных ситуаций

(ИмяФрейма:

ИмяСлота1(ЗначениеСлота1);

ИмяСлота2(ЗначениеСлота2);

…

ИмяСлотаN(ЗначениеСлотаN);)

Слот - подструктура фрейма

(Служащий:

Фамилия(Иванов);

ГодРождения(1974);

Специальность(Программист);

Стаж(3);)

Фрейм - объект со свойствами

Фреймы-прототипы (классы) - обобщенные объекты предметной области

Фреймы-примеры (экземпляры) - индивидные объекты предметной области

Фрейм - подграф семантической сети

Сети фреймов

Специальные слоты для задания отношений

AKO - связь фрейма-подкласса с фреймом-суперклассом

IS-A - связь фрейма-примера с фреймом-прототипом

Процедура, присоединенная к слоту (процедура-демон) - вычисляет значение слота, учитывая определенные условия

if-needed («если-нужно») - активизируется при запросе значения слота

Пингвин		Пингвин
Вид()		Вид(императорский)
Рост(Length(Вид))		Рост(100-120 см)

Если не «императорский», то Рост(40-50 см)

if-added - активизируется при записи значения слота

if-removed - активизируется при удалении значения слота

if-modified - активизируется при изменении значения слота

Пингвин		Пингвин
Вид()		Вид(галапагосский)
Красная книга(Red(Вид))		Красная книга(да)

Указатели наследования

Указатель наследования - определяет значение слота, которое передается от фрейма верхнего уровня к фрейму нижнего уровня

unique - слоты могут иметь различные значения

same - слоты должны иметь одинаковые значения

range - значение слота фрейма нижнего уровня должно находится в определенном диапазоне

override (unique+same) - если значение отсутствует, то оно наследуется из верхнего уровня

Особенности механизма наследования

Порядок наследования определяется списком предшествований

Линейная иерархия



Список предшествований соответствует направлению связей IS-A и АКО

(Нео, пингвины, птицы)

«Пингвин Нео летать не может»

Множественное наследование

Фрейм имеет несколько связей IS-A и АКО

Список предшествований формируется сначала в глубину, а затем слева - направо

Могут возникнуть проблемы:

«Пингвин Нео обитает на морском побережье»

Более сложная взаимосвязь фреймов

Список предшествований формируется:

в глубину

слева - направо

исключение повторяющихся элементов (остается последний)

(ЭК, С2, С1, УК, С4, С3, С1, УК, С5, С1, УК)

(ЭК, С2, С1, УК, С4, С3, С1, УК, С5, С1, УК)

(ЭК, С2, С4, С3, С5, С1, УК)

Любой класс появляется раньше, чем его суперкласс

Передача наиболее специфичных данных

Могут возникнуть проблемы:

Проблема: суперкласс 2 следует после суперкласса 3, хотя суперкласс 3 расположен правее суперкласса 2

Что делать?

Процедура топологической сортировки

Шаг 1. Составляется список экземпляров и суперклассов

Элемент
экземпляр
супер5
супер2
супер1
супер3
супер6
супер4
универ

Шаг 2. Для каждого элемента списка формируется список пар по принципу «рыболовецкого крючка»

Шаг 3. Добавление элемента в список предшествований

В таблице выделяют элемент, который встречается только с левой стороны пары

Добавляют этот элемент в список предшествований

Удаляют из таблицы все пары с этим элементом

Элемент	Пары	Пары	Пары	Пары	Пары
экземпляр	Э-5, 5-6	5-6
супер5	5-2, 2-3	5-2, 2-3	2-3	2-3
супер2	2-1	2-1	2-1	2-1
супер1	1-У	1-У	1-У	1-У	1-У
супер3	3-1	3-1	3-1	3-1	3-1
супер6	6-2, 2-4	6-2, 2-4	6-2, 2-4	2-4
супер4	4-1	4-1	4-1	4-1	4-1
универ	У	У	У	У	У

Конфликт в пункте 1: следующими могут быть суперклассы 3 или 4.

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

Для каждого конфликтующего элемента находим в списке предшествований непосредственные подклассы

Приоритет у того суперкласса, чей непосредственный подкласс самый правый в списке предшествований

С-3 - непосредственный подкласс 5

С-4 - непосредственный подкласс 6

Приоритет у С-4

Элемент	Пары	Пары	Пары	Пары	Пары	Пары	Пары
экземпляр	Э-5, 5-6	5-6
супер5	5-2, 2-3	5-2, 2-3	2-3	2-3
супер2	2-1	2-1	2-1	2-1
супер1	1-У	1-У	1-У	1-У	1-У	1-У	1-У
супер3	3-1	3-1	3-1	3-1	3-1	3-1
супер6	6-2, 2-4	6-2, 2-4	6-2, 2-4	2-4
супер4	4-1	4-1	4-1	4-1	4-1
универ	У	У	У	У	У	У	У

Размещено на Allbest.ru