Калабухов Е.В. Курс лекций по дисциплине Базы данных, знаний и экспертные системы
Подождите немного. Документ загружается.
«намерение – отдых»
«место отдыха – горы»
«дорога – ухабистая»
«использовать джип»
Шаг 3) третий просмотр базы правил – нет сработавших правил – останов
вывода:
«намерение – отдых»
«место отдыха – горы»
«дорога – ухабистая»
«использовать джип»
Шаг 4) вывод и интерпретация результатов – рекомендовано
«использовать джип», т.к. «дорога – ухабистая», т.к. задано «намерение –
отдых» и «место отдыха – горы».
II) Обратный вывод (подтверждение заданной цели при определенных
начальных условиях, т.е. вывод в данном случае управляется целью) в простом
варианте состоит из следующих шагов:
•
в рабочую память заносятся предпосылки (некоторые исходные условия
(явления)) и цель, для которой необходимо найти подтверждение;
•
выполняется цикл просмотра базы правил и для каждого целевого
правила (т.е. правила, в результирующей части которого записана
текущая цель) производится сопоставление образцов из условной части
этого правила с образцами, хранимыми в рабочей памяти, по следующим
правилам:
- если все необходимые образцы целевого правила имеются в
рабочей памяти, то условная часть правила считается истинной
(подтверждение цели), в противном случае – ложной (переход к
следующей цели);
- если выполняется переход к следующей цели, то условная часть
(за исключением тех её фрагментов, которые уже находятся в рабочей
251
памяти) неподтвержденного целевого правила добавляется в рабочую
память как новая цель, а текущий цикл просмотра базы правил
завершается и начинается следующий;
- если произошло подтверждение текущей цели, то в качестве цели
выбирается предыдущая неподтвержденная цель из рабочей памяти;
- если нет изменений в рабочей области или не осталось
неподтвержденных целей, то работа вывода завершается;
•
все результаты, которые содержатся в рабочей памяти по останову
вывода, в порядке времени записи в рабочую память выдаются
пользователю, если осталась хоть одна цель, значит подтверждение
первоначальной цели на текущих данных невозможно.
Пример №1 обратного вывода на продукциях:
Исходная база правил состоит из следующих правил, пронумерованных в
порядке размещения в БЗ:
1) если «вода в реке поднимается», то «рыба выходит на мель»;
2) если «вода в реке опускается», то «рыба уходит в глубину»;
3) если «лето влажное», то «вода в реке поднимается»;
4) если «лето сухое», то «вода в реке опускается»;
5) если «рыба выходит на мель», то «следует применять легкую блесну»;
6) если «рыба уходит в глубину», то «следует применять тяжелую
блесну».
Необходимо подтвердить рекомендацию «следует применять легкую
блесну», если лето выдалось влажное. Рассмотрим состояние рабочей памяти
на каждом шаге работы вывода:
Шаг 0) в рабочую память помещаются исходные условия и цель (цель
помечена «?»):
«лето влажное»
«следует применять легкую блесну»?
Шаг 1) первый просмотр базы правил – попытка подтверждения целевого
правила №5 (подтверждение невозможно, задание новой цели):
252
«лето влажное»
«следует применять легкую блесну»?
«рыба выходит на мель»?
Шаг 2) второй просмотр базы правил – попытка подтверждения целевого
правила №1 (подтверждение невозможно, задание новой цели):
«лето влажное»
«следует применять легкую блесну»?
«рыба выходит на мель»?
«вода в реке поднимается»?
Шаг 3) третий просмотр базы правил – попытка подтверждения целевого
правила №3 (подтверждение возможно, возврат к предыдущей цели):
«лето влажное»
«следует применять легкую блесну»?
«рыба выходит на мель»?
«вода в реке поднимается»
Шаг 4) четвертый просмотр базы правил – попытка подтверждения
целевого правила №1 (подтверждение возможно, возврат к предыдущей цели):
«лето влажное»
«следует применять легкую блесну»?
«рыба выходит на мель»
«вода в реке поднимается»
Шаг 5) пятый просмотр базы правил – попытка подтверждения целевого
правила №5 (подтверждение возможно, больше целей нет – останов вывода):
«лето влажное»
«следует применять легкую блесну»
«рыба выходит на мель»
«вода в реке поднимается»
Шаг 6) вывод и интерпретация результатов – целей после останова
вывода нет – значит «следует применять легкую блесну» подтверждено,
остальные значения рабочей памяти показывают ход рассуждений при
253
подтверждении цели.
Пример №2 обратного вывода на продукциях:
Исходная база правил состоит из следующих правил, пронумерованных в
порядке размещения в БЗ:
1) если «намерение – отдых» и «дорога ухабистая», то «использовать
джип»;
2) если «место отдыха – горы», то «дорога – ухабистая».
Необходимо подтвердить рекомендации «использовать джип», если место
отдыха – горы. Рассмотрим состояние рабочей памяти на каждом шаге работы
вывода:
Шаг 0) в рабочую память помещаются исходные условия и цель (цель
помечена «?»):
«намерение – отдых»
«место отдыха – горы»
«использовать джип»?
Шаг 1) первый просмотр базы правил – попытка подтверждения целевого
правила №1 (подтверждение невозможно, задание новой цели):
«намерение – отдых»
«место отдыха – горы»
«использовать джип»?
«дорога ухабистая»?
Шаг 2) второй просмотр базы правил – попытка подтверждения целевого
правила №2 (подтверждение возможно, возврат к предыдущей цели):
«намерение – отдых»
«место отдыха – горы»
«использовать джип»?
«дорога ухабистая»
Шаг 3) третий просмотр базы правил – попытка подтверждения целевого
правила №1 (подтверждение возможно, больше целей нет – останов вывода):
«намерение – отдых»
254
«место отдыха – горы»
«использовать джип»
«дорога ухабистая»
Шаг 4) вывод и интерпретация результатов – целей после останова
вывода нет – значит «использовать джип» подтверждено, остальные значения
рабочей памяти показывают ход рассуждений при подтверждении цели.
В целом обратный вывод аналогичен прямому, но возникают
дополнительные проблемы ограничения конфликтных наборов правил и
выбора алгоритма разрешения конфликтов. Есть и другие проблемы, например,
оценки условий в условной части. Все эти проблемы решаются по-разному в
рамках соответствующих инструментальных систем продукционного типа.
Процесс вывода можно рассматривать как поиск решения в пространстве
состояний. Такое пространство может быть задано в виде графа состояний,
тогда, в общем виде, различают стратегии поиска в глубину и ширину.
Поиск в глубину основан на полном исследовании одного варианта до
изучения других вариантов. Поиск выполняется по несложной методике (см.
рисунок 43), например:
•
всегда первой исследуется неизвестная левая ветвь дерева состояний;
•
если процесс поиска заходит в тупик, то происходит возврат наверх в
последний пункт выбора, где имеются неизученные альтернативные
варианты движения;
•
поиск повторяется для нового варианта;
Поиск в глубину лучше всего работает при решения проблемы, где все
пути поиска от вершины дерева до его основания имеют одинаковую длину.
Стратегия поиска в ширину предусматривает переход в первую очередь к
вершинам, ближайшим к стартовой вершине (т.е. отстающим от нее на одну
связь), затем к вершинам, отстающим на две связи, затем на три и т. д., пока не
будет найдена целевая вершина (см .рисунок 44).
255
Рисунок 43. Поиск в глубину.
Рисунок 44. Поиск в ширину.
Программа поиска продвигается по дереву решений слева направо,
расширяя каждый из маршрутов, и отбрасывая те из них, которые являются
тупиковыми. Поиск в ширину пригоден при решении проблем, где ветви
поиска в дереве (от вершины до основания) имеют неодинаковую длину, и не
256
существует указаний на то, какая именно дорога приводит к цели.
Обе приведенные выше стратегии поиска предполагают
последовательный перебор возможных вариантов, однако поиск будет более
эффективным, если некоторый механизм в пунктах выбора сам сможет делать
наиболее желательный выбор, как правило такой выбор основывается на
эвристиках поиска.
Поскольку в общем случае в продукционной системе невозможно
построить сразу все пути решения задачи (проблема выбора (активизации)
правил), движение в пространстве состояний осуществляется в соответствии с
эвристиками, составляющими содержание критериев:
•
принцип ″стопки книг″ - наиболее часто используемые продукции
актуализируются первыми; этот принцип целесообразно применять, если
продукции относительно независимы друг от друга;
•
принцип наиболее длинного условия - первыми выбирается продукция, у
которой наиболее ″длинное″ условие выполнимости ядра; этот принцип
целесообразен, когда продукция хорошо структурированы по отношению
″частное-общее″;
•
принцип метапродукций - в систему продукций вводятся специальные
правила метапродукции, задачей которых является разрешение ситуаций
в условиях конфликтного набора правил;
•
принцип приоритетного выбора - на продукции вводятся статические
(формируются заранее, чаще всего на основе экспертных оценок) или
динамические (вырабатываются в самом процессе функционирования
продукционной системы) приоритеты.
Популярность продукционных моделей определяется следующими
факторами:
•
подавляющая часть человеческих знаний может быть записана в виде
продукций;
•
за небольшим исключением удаление или добавление продукций не
приводит к изменениям в основных продукциях;
257
• при необходимости системы продукций могут реализовать любые
алгоритмы и, следовательно, способно отражать любое процедурное
знание, доступное ЭВМ;
•
наличие в продукциях указателей на сферу применения продукций
позволяет эффективно организовывать память, сократив время поиска в
ней необходимой информации; классификация сфер может быть
многоуровневой, что еще более повышает эффективность поиска знаний,
т.к. позволяет наследовать информацию о базе знаний;
•
при объединении систем продукций и сетевых представлений получаются
средства, обладающие большой вычислительной мощностью (могут
использоваться также композиции с другими представлениями знаний
(фреймы, объектно-ориентированные модели));
•
естественный параллелизм в системе продукций, асинхронность их
реализации делают продукционные системы удобной моделью ЭВМ
новой архитектуры, в которой идеи параллельности и асинхронности
является центральной.
Продукционные модели имеют и недостатки:
•
при большом числе продукций становится сложной проверка
непротиворечивости системы продукций, и это заставляет при
добавлении новых продукций тратить много времени на проверку
непротиворечивости новой системы;
•
из-за присущей системе недетерминированности (неоднозначного выбора
выполняемой продукции из множества активизированных продукций)
возникают принципиальные трудности при проверке корректности
работы системы; считается, что если число продукций достигает тысячи,
то вероятность нормальной работы системы невелика, поэтому число
продукций, с которым, как правило, работают современные
интеллектуальные системы, не превышает тысячи (если их требуется
больше, то осуществляется декомпозиция предметной области и задача
разбивается не более мелкие).
258
• продукционные модели – неформальные модели, в них нет строгой
теории, и в основном используются эвристики; причина неудач создания
теории кроется в расплывчатости самого понятия продукции;
•
при переходе от статических систем к динамическим (адаптивным или
системам продукций реального времени, т.е. меняющим состав
продукций в системе или перестраивающих алгоритм управления
выбором продукций из фронта готовых продукций в зависимости от
текущих ситуаций) теряется быстрота срабатывания (решение этой
проблемы видят в специальные средствах аппаратной поддержки).
8.2. Приобретение знаний
Приобретением знаний называется выявление знаний из источников
знаний и преобразование их в необходимую форму, а также перенос в БЗ.
Источниками знаний для систем ИИ могут быть:
•
объективизированные знания – знания, переведенные в такую форму
(книги, архивные документы, содержимое других баз знаний и т. п.),
которая делает их доступными для потребителя;
•
экспертные знания - знания, которые имеются у специалистов, но не
зафиксированы во внешних по отношению к нему хранилищах;
экспертные знания являются субъективными;
•
эмпирические знания – знания, которые могут добываться системой ИИ
путем наблюдения за окружающей средой (если есть подходящие
средства наблюдения); эмпирические знания также являются
субъективными.
Ввод в БЗ объективизированных знаний не представляет особой
проблемы, а выявление и ввод субъективных (особенно экспертных) знаний
достаточно трудны.
Чтобы разработать методологию приобретения субъективных знаний,
259
получаемых от эксперта, надо понимать две формы репрезентации
(представления) знаний:
•
первая форма связана с тем, как и в каких моделях хранятся эти знания у
человека-эксперта (при этом следует учитывать, что эксперт не всегда
осознает полностью, как репрезентированы у него знания);
•
вторая форма связана с тем, как инженер по знаниям, проектирующий
некоторую систему ИИ, собирается описывать и представлять знания.
Когнитивные структуры знаний характерные для человека:
•
представление класса понятий через его элементы (например, понятие
"птица" репрезентируется рядом чайка, воробей, скворец, и т.д.);
•
представление понятий класса с помощью базового прототипа,
отражающего наиболее типичные свойства объектов класса (например,
понятие "птица" репрезентируется прототипом нечто с крыльями,
клювом, летает и т.п.) представление с помощью признаков (для понятия
"птица", например, наличие крыльев, клюва, двух лап, перьев).
Кроме понятий репрезентируются и отношения между ними. В
большинстве случаев, отношения между понятиями определяются
процедурным способом, а отношения между составляющими понятий (т.е.
определяющими структуру понятия) - декларативным способом.
При приобретении знаний важную роль играют так называемое поле
знаний, в котором содержатся основные понятия, используемые при описании
предметной области, и свойства всех отношений, используемых для
установления связей между понятиями. Поле знаний связано с концептуальной
моделью проблемной области, в которой еще не учтены ограничения, которые
неизбежно возникают при формальном представлении знаний в БЗ. Получение
формального представления знаний в БЗ без этапа концептуального описания в
поле знаний существенно замедляет процесс формирования БЗ и может
привести к ошибкам. Фактически, переход от описания некоторой области в
поле знаний к описанию в БЗ аналогичен переходу от концептуальной модели
БД к ее логической схеме.
260