shkolakz.ru 1

Имя

слота


Тип

Значение

ISA

Frame

A

Объект 1

Integer

125

Объект 2

Real

8.5
















Расчет

LISP

CALC

Фрейм АА

Имя слота

Тип

Значение

ISA

Frame

В

X

Integer

10,20,30

У

Real

8.0, 12.6














Среднее

LISP

MEAN

Фрейм ВВ


MSG


Ответ

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

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


Value

MSG

MSG

MSG

Рис. 15. Средства управления выводом в ЭС фреймового типа. ЛЕКЦИЯ 6. Методы приобретения знаний.

Рис. 14. Обмен информацией между фреймами АА и ВВ.


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

LISP proc CALC (result) MSG (Cpednee, ВВ, X) end.

Команда MSG имеет три параметра:

  • имя слота, к которому происходит обращение (в данном случае значением слота «Среднее» является присоединенная процедура MEAN);
  • имя фрейма, в котором содержится необходимая информация (ВВ);


  • имя слота - параметра, в котором находятся данные для расчета (X).

Запуск процедуры CALC вызовет исполнение следующих действий: передача сообщения во фрейм ВВ на запуск процедуры MEAN, которая найдет среднее арифметическое чисел, записанных в слоте X; вычисленное значение будет записано в переменную result и передано в CALC как ответ на сообщение MSG.

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



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


Обработка знаний в ЭС с фреймовым представлением. В ЭС с фреймовой моделью представления знаний используются три способа управления логическим выводом:

  • демоны,

  • присоединенные процедуры

  • механизм наследования.

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

Рассмотрим обработку знаний в ЭС на примере структуры фрейма «Научная конференция» (табл. 4.).

Главное назна-чение этой процедуры состоит в проверке возможности заказа аудитории на нужное время. Такая процедура на языке LISP может выглядеть примерно так:

LISP proc «Заказ» (название конференции, место проведения, дата)

if возможно (место проведения, дата)

then заказать (название конференции, место проведения, дата) else сообщение («Заказ невозможен», название конференции) end.


Демон «Кто?» автоматически запускается при обращении к слоту «Докладчик», если значение этого слота не определено. Основное содержание данной процедуры заключается в генерации запроса к пользователю типа «Кто выступает?», получение ответа и его запись в качестве значения слота. Реализация вывода с помощью присоединенных процедур требует наличия механизма обмена информацией между фреймами. В качестве такого механизма обычно используется механизм сообщений. На рис. 14 схематично показан обмен информацией между фреймами АА и ВВ во время исполнения присоединенной процедуры CALC, при этом вызывается процедура MEAN, расположенная во фрейме ВВ.


Имя слота

Значение слота

If-needed

If-added

If- removed

Дата

25.02. 10:00










Место проведения

Аудитория 6 - 332




Заказ




Тема доклада

Алгоритм отжига










Докладчик

Семенов А.И.

Кто?






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


Таблица 4

Демон «Заказ» - это процедура, которая автоматически запускается при попытке подстановки значения в слот с именем место проведения.


7?

74


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


Рис. 12. Поиск в глубину при обратном выводе.


Стратегия поиска в ширину. При поиске в ширину сначала анализируются все симптомы (факты), находящиеся на одном уровне пространства состояний задачи, даже если они относятся к разным целям (подцелям), и только после этого происходит переход к поиску симптомов следующего уровня. На рис. 13 показаны шаги поиска в ширину, обозначенные номерами, указанными в вершинах. На рисунке представлена стратегия обратного вывода на том же И-ИЛИ-графе, который приведен и на рис. 12 Алгоритм поиска в глубину более эффективен в отношении времени поиска и обработки знаний, однако он характеризуется более высоким риском потери перспективных решений по сравнению с поиском в ширину.


Факты Заключения


Рис. 13. Поиск в ширину при обратном выводе.

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


а - (3 - алгоритм.

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



Рис. 10. Простейший фрагмент структуры И-ИЛИ-графа.

Заключения

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



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


Стратегия поиска в глубину.


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


Пример обратного вывода. Предположим, что в БП имеется два правила (правило 1 и правило 2), а в РП - те же факты, что в предыдущих примерах с прямым выводом.

Алгоритм обратного вывода содержит следующие шаги.


  1. Выдвигается гипотеза окончательного диагноза - сел аккумулятор.

  2. Отыскивается правило, заключение которого соответствует выдвинутой гипотезе, в нашем примере - это правило 1.

  3. Исследуется возможность применения правила 1, то есть решается вопрос о том, может ли оно сработать. Для этого в рабочей памяти должны присутствовать факты, совпадающие с образцом этого правила. В рассмат-риваемом примере правило 1 не может сработать из-за отсутствия в РП образца «двигатель не заводится». Этот факт становится новой целью на следующем шаге вывода.

  4. Поиск правила, заключение которого соответствует новой цели. Такое правило есть - правило 2.

  5. Исследуется возможность применения правила 2 (сопоставление). Оно срабатывает, так как в РП присутствует факт, совпадающий с его образцом.

  6. Действие правила 2, состоящее в занесении заключения «двигатель не заводится» в РП.

  7. Условная часть правила 1 теперь подтверждена фактами, следовательно, оно срабатывает, и выдвинутая начальная гипотеза подтверждается.

  8. Конец работы.

При сравнении этого примера с примером прямого вывода нельзя заметить преимуществ обратных выводов перед прямыми выводами.

Пример обратного вывода с конфликтным набором. Предположим, что в БП записаны правило 1, правило 2, правило 3 и правило 4: «если засорился бензонасос, то двигатель не заводится». В РП присутствуют те же самые факты: «фары не горят и указатель бензина находится на нуле».

В данном случае алгоритм обратного вывода с конфликтным набором включает следующие шаги.

  1. Выдвигается гипотеза сел аккумулятор.
  1. Поиск правила, заключение которого совпадает с поставленной целью. Это правило 1.


  2. Исследуется возможность применения правила 1. Оно не может сработать, тогда выдвигается новая подцель «двигатель не заводится», соответству-ющая недостающему образцу.

  3. Поиск правил, заключения которых совпадают с новой подцелью. Таких правил два: правило 2 и правило 4. Если выберем правило 2, то дальнейшие шаги совпадают с примером без конфликтного набора. Если выберем правило 4, то оно не сработает, так как в РП нет образца: «засорился бензонасос». После этого будет применено правило 2, что приведет к успеху, но путь окажется длиннее на один шаг.

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

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

В ЭС продукционного типа все множество знаний обычно хранится в виде древовидной структуры, называемой И-ИЛИ-графом. Фрагменты такой структуры приведены на рис. 10, 11.

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



Критерий выбора правила


Разрешение кон(Ьпиктя

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



Сопоставление




Конфликтный




набоп



Рабочая




База




память




ппавил





Действие

Срабатывание


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


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

  • разрешение конфликтного набора - выбор одного из нескольких правил в том случае, если их можно применить одновременно;

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


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

Рассмотрим простейшие примеры прямого и обратного вывода в системах продукционного типа.

Пример прямого вывода. Пусть в БП имеются следующие правила: Правило 1. «если двигатель не заводится, и фары не горят, то сел аккумулятор».

Правило 2. «если указатель бензина находится на нуле, то двигатель не заводится».

Предположим, что в рабочую память от пользователя ЭС поступили факты: фары не горят и указатель бензина находится на нуле. Рассмотрим основные шаги алгорит-ма прямого вывода.

  1. Сопоставление фактов из РП с образцами правил из БП. Правило 1 не может сработать, а правило 2 срабатывает, так как "образец, совпадающий с его антецедентом, присутствует в РП.

  2. Действие сработавшего правила 2. В РП заносится заключение этого правила, то есть образец: двигатель не заводится.

  3. Второй цикл сопоставления фактов в РП с образцами правил. Теперь срабатывает правило 1, так как совпадение условий в его антецеденте становится истинной.

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

  5. Конец работы (БП исчерпана).

Пример прямого вывода с конфликтным набором. Теперь допустим, что в БП кроме правила 1 и правила 2 присутствует правило 3: «если указатель бензина находится на нуле, то нет бензина». В РП находятся те же факты, что в предыдущем примере. В результате сопоставления в первом же цикле возможно применение двух правил - правила 2 и правила 3, то есть возникает конфликтный набор и встает задача выбора: какое из этих правил применить первым. Если выберем правило 2, то в РП добавится факт «двигатель не заводится» и на следующем шаге опять возник-нет конфликтный набор, так как можно будет применить правило 1 и правило 3. Если будет выбрано правило 1, то к заключению «сел аккумулятор» придем за два шага. При любом другом выборе порядка применения пра


76