Преимущества эс. Задачи эс

Вид материалаРеферат
Правило 322 Тип Правило Описание Сообщить пользователю об опасности для здоровья
Способы применения цепочек рассуждения.
Поиск в ширину
Принцип классной доски
Разработка эс.
Подобный материал:
1   2   3   4   5   6   7   8

Правило 322


Тип Правило

Описание Сообщить пользователю об опасности для здоровья


Если потенц. релев.: Химическая активность высока?

Если истин. релев.: Близость к хим. активному месту

ТО сказать пользователю: «не дышать»

ТО добавить: <соответствующие указания>

- приоритет: высокий
  • среднее время выполнения: 0.1 секунды
  • частота использования: рассм. 985 раз, использовалось 4
  • обобщения: правила 899 и 45
  • специализация: правило 366
  • оправдания: дыхание  сценарий смерти
  • автор: Джонсон
  • дата создания: 17.30 9.08.81

Особенность представления:
  1. много описательных слотов
  2. наличие нескольких условий и действий.



Контрольные вопросы:
  1. Какой способ управления во фреймах является обязательным?
  2. Какие основные типы «демонов» используются во фреймах?
  3. Когда используются присоединенные процедуры?
  4. Какие функции реализуются в языках представления фреймовых моделей?
  5. Каковы недостатки фреймовых моделей?
  6. Когда используются присоединенные процедуры?



Лекция 8 СИСТЕМЫ ПРОДУКЦИЙ.


План лекции:

  1. компоненты продукционной системы.
  2. прямая цепочка рассуждений.
  3. обратная цепочка рассуждений
  4. представление фактов и правил


Ключевые слова:

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


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





Рассмотрим, как взаимно действуют эти элементы на простом примере.

Пусть в рабочей памяти хранятся образцы в виде набора символов. Например, «намерение – отдых», «место отдыха – горы» и т. п.

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

Например:

Правило 1: ЕСЛИ «намерение – отдых» И «дорога ухабистая»,

ТО «использовать машину».

Правило 2: ЕСЛИ «место отдыха – горы»,

ТО «дорога ухабистая».

Сначала механизм вывода сопоставляют образцы из условной части правила с образцами из рабочей памяти. Если все образцы имеются в рабочей памяти, то условная часть считается ИСТИННОЙ, иначе ЛОЖНОЙ.

В данном примере «дорога ухабистая» из первого правила отсутствует в рабочей памяти. Поэтому его условная часть первого правила считается ложной. Что касается правила 2, то его условная часть истинна, и образец «дорога ухабистая» заносится в рабочую память.

При попытке вторично применить эти правила получается, что можно применить только правило 1, поскольку правило 2 уже применено и исключается из числа кандидатов. К этому времени содержимое рабочей памяти пополнилось результатом правила 2, и первое правило становится истинным, и содержимое рабочей памяти пополняется образцом заключительной части первого правила – «использовать машину». В итоге правил больше не остается, и система останавливается.

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

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

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

СПОСОБЫ ПРИМЕНЕНИЯ ЦЕПОЧЕК РАССУЖДЕНИЯ.


Любую продукцию можно представить в виде дерева целей (рис. 16.)




Рис.16. Дерево целей


  1. Прямой способ рассуждения.

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




Рис. 17. Реализация прямой цепочки рассуждений.


«А» в базе есть. Значит согласно 1 правилу есть и «D». И «D» помещается в базу знаний. Это приводит к выполнению 2 правила.

C  D F, и факт «F» помещается в базу знаний. Тогда опять проверяются правила из базы. Первое правило выполняется F  B  Z , вследствие этого Z заносится в базу знаний. Этот метод называется прямой цепочкой рассуждений, поскольку поиск новой информации происходит в направлении стрелок, разделяющих левые и правые части правил.

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

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

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

На рис. 18 показано, как обратная цепочка рассуждений работает.

На шаге 1 системе говорится, чтобы она установила, что ситуация Z существует. Она ищет Z в базе, а если его нет, будет искать правило, приводящее к установлению Z. Она находит правило F  B  Z и решает, что надо установить F и B.

На шаге 2 система пытается найти факт F или в базе данных или среди правил. Находит правило C  D F и решает, что необходимо установить существование фактов C и D.

На шагах 3-5 система находит C, затем находит А прежде, чем получит заключение о D.

На шагах 6-8 система выполняет третье правило, чтобы установить D, затем исполняет второе правило, чтобы установить F и наконец – первое правило, чтобы установить основную цель – факт существования Z.

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

конфликтным набором, а выбор одного из этих правил – разрешение конфликта.


Рис.18. Обратная цепочка рассуждений

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

Если имеется правило, пригодное для любого объекта собаки независимо от клички, то «атрибут» и «значение» не используются. Однако, когда существует несколько объектов, для которых применимо одно правило, то оно может быть использовано для каждого объекта, но не более 1 раза. (в первом случае – только один раз, так как «атрибут» и «значение» не используются).

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

объект – атрибут – значение – показатель достоверности.

Например: грипп – температура – высокая 39 - 0.8 достоверность.

Любое правило состоит из условной части и заключения. Условная часть проверяет все данные из рабочей памяти на истинность (используется И). Если несколько правил, то выполнив операцию ИЛИ над всеми заключениями этих правил, получаем заключение.




Рис.19. Процесс представления вывода в виде графа


Таким графом И/ИЛИ можно представить процесс вывода в системе продукции. В самом верхнем узле – заключения, выводимые системой, в самом низу – факты. А  В – это ядро продукции.




Рис.20. Классификация ядер продукции

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

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

Управление прямым выводом организуется проще, чем управление при обратном выводе.

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

Для управления выводом используются 2 метода:
  • либо установка ряда ограничений на генерацию конфликтного набора правил;
  • либо алгоритм разрешения конфликта.

Для реализации первого подхода используются методы с применением МЕТАПРАВИЛ – правил, в условной части которых содержится условие, касающиеся содержания правил и содержимого рабочей памяти.

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

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


Контрольные вопросы:
  1. Какие функции выполняет рабочая память?
  2. Пополняется ли рабочая память в обратной цепочке рассуждений?
  3. Какой алгоритм более эффективный в прямой или обратной цепочке рассуждений?
  4. Как представляются факты в продукционных системах?
  5. Как представляются правила в продукционных системах?
  6. Как неточные знания учитываются в продукционных моделях.



Лекция 9 УПРАВЛЕНИЕ ВЫВОДОМ В ПРОДУКЦИОННОЙ СИСТЕМЕ.


План лекции:

  1. структура управляющего механизма.
  2. классификация методов поиска.
  3. методы повышения эффективности поиска.
  4. примеры продукционных систем.


Ключевые слова:

Интерпретатор, дерево целей, компонент вывода, компонент управления, сопоставления, выбор, срабатывание.


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

Управляющий механизм включает 2 компонента:
  • один реализует собственно вывод;
  • другой управляет этим процессом.

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

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

Управляющий компонент выполняет 4 функции:
  • сопоставление – образец правила сопоставляется с имеющимися фактами;
  • выбор – если в конкретной ситуации могут быть применены сразу несколько правил, то из них выбирается одно, наиболее подходящее по заданному критерию. Это называется разрешение конфликта;
  • срабатывание – если образец правила при сопоставлении совпал с фактами из рабочей памяти, то срабатывает правило;
  • действие – рабочая память подвергается изменению путем добавления в нее заключения сработавшего правила (при прямой цепочке рассуждений).

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





Рис. 21. Работа интерпретатора

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

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

В зависимости от этих параметров используются следующие методы:
  • поиск решения в одном пространстве состояний (малые статические области, точные и полные данные);
  • поиск в иерархических пространствах (работа в больших статических областях);
  • поиск при неточных и неполных данных;
  • поиск в динамических проблемных областях;
  • поиск с использованием нескольких моделей рассмотрения области (с разных точек зрения).

Рассмотрим один из простых методов. Имеется несколько способов его реализации.
  1. Метод поиска в пространстве состояний.

Граф G задает пространство состояний, в котором осуществляется поиск решения. Берется некоторая вершина х0  Х0 и проверяются все правила, порождающие все дочерние вершины. Этот процесс называется раскрытием вершин. Процесс построения заканчивается, когда все нераскрытые вершины являются целевыми или терминальными (для которых нет правил). Надежным способом обеспечения полноты является полный перебор всех вершин. Для задания процесса перебора необходимо определить порядок перебора. Обычно используют 2 основных способа: поиск в глубину и поиск в ширину.





Рис.22 Методы поиска в пространстве состояний.


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

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

Нужно отметить, все названные методы ускоряют работу ЭС за счет сокращения пространства поиска.

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

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

Эти разработки получили свое признание в последнее время, но исследования в этой области еще продолжаются.

Основные методы повышения эффективности поиска правил:
  • поиск в глубину;
  • поиск в ширину;
  • разбиение на подзадачи (кл. доска);
  • - - алгоритм.

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

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

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

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




Рис.23. Принцип классной доски.


Рассмотрим стратегии выбора продукции из фронта готовых продукций.
  1. Принцип «стопки книг». Основан на идее, что наиболее часто использующаяся продукция является наиболее полезной. На самом верху «стопки» находится продукция, которая использовалась чаще всех. При актуализации некоторого фронта готовых продукций для пополнения выбирается та продукция, у которой частота максимальна. Управление по принципу стопки удобно применять, если продукции относительно независимы, когда каждая из них есть правило вида «ситуация А  действие В». Поэтому они используются в планирующих системах для роботов.
  2. Принцип наиболее длинного условия. Заключается в выборе из фронта готовых продукций той, у которой стало истинным наиболее длинное условие выполнимости ядра. Этот принцип опирается на соображение здравого смысла, что частные правила, относящиеся к узкому классу ситуации, важнее общих правил, так как учитывается больше информации о ситуации. Управление по этому принципу целесообразно в тех случаях, когда знания и сами продукции хорошо структурированы привязкой к типовым ситуациям, на которых задано отношение типа «частное – общее».
  3. Принцип метапродукций. Основан на идее ввода в систему продукций специальных метапродукций, задачей которых является организация управления в системе продукций при возможности неоднозначного выбора из фронта готовых продукций (используется в MYCIN при диагностике инфекционных заболеваний).
  4. Принцип приоритетного выбора. Связан с введением статических или динамических приоритетов на продукции. Статические приоритеты могут формировать априори на основании сведений о важности продукционных правил в данной предметной области. Это обычно информация, получаемая от экспертов. Динамические приоритеты вырабатываются в процессе функционирования системы продукций.
  5. Управление по именам. Основано на задании для имен продукции, входящих в некоторую систему, некоторой формальной грамматики или другой процедуры, ссужающей фронт готовых продукций и выбор из нее очередной продукции.

Преимущества продукционных систем:
  • простота создания и понимания отдельных правил;
  • простота пополнения и модификации;
  • простота механизма логического вывода.

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

Примеры реализации продукционных систем:

OPS-5 широко известна как инструментальная система для разработки самих ЭС (США). Факты в ней представлены в виде триплетов. OPS-5 – это специализированная система с прямым выводом, эффективность выполнения выводов увеличивается за счет согласования RETE при генерации конфликтного набора.

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

Рабочая память управляется в виде «четверки» – «объект – атрибут – значение – к дост», т. е. учитывается нечеткость информации.




Фактор достоверности изменяется от –1 до +1. (-1 - полное отрицание факта, +1 – полное подтверждение факта).

В MYCIN используется обратный вывод. Условная часть правил в MYCIN принимает значение ИСТИНА с некоторым коэффициентом CF. Тогда достоверность условной части меньше достоверности заключительной части правила с четким условием.

В системе MYCIN не предусмотрены методы увеличения эффективности поиска.


Контрольные вопросы:
  1. Для чего нужен компонент вывода продукционной системы?
  2. Какие функции выполняет управляющий компонент?
  3. Какие методы «слепого поиска» используются при управлении в продукционных системах?
  4. Какие методы эффективного поиска используются?
  5. В чем суть стратегии выбора правил из альтернативного ряда?
  6. Недостатки продукционной модели.

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


РАЗРАБОТКА ЭС.

Лекция 10 ЭТАПЫ РАЗРАБОТКИ ЭС.


План лекции:

  1. этапы разработки ЭС.
  2. оценка качества ЭС.
  3. 5 уровней развития ЭС.


Ключевые слова:

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


Разработку ЭС можно считать состоящей из пяти сильно взаимодействующих и перекрывающихся этапов:
  • Идентификация
  • Концептуализация
  • Формализация
  • Реализация
  • Тестирование.

На рис.25 представлена схема построения ЭС.




Рис.25. Этапы разработки ЭС


Рассмотрим эти этапы.
  1. На этапе ИДЕНТИФИКАЦИИ разработчик и эксперт определяют существенные особенности задачи. К ним относятся тип задачи, широта постановки, а также требуемые ресурсы (сроки и компьютерные мощности), цели и задачи создания ЭС (повысить компетентности или тиражировать редко встречающие способности и навыки). Из всех этих проблем наиболее трудоемкой является определение задачи и широты постановки, т.е. ограничение области исследования.
  2. На этапе КОНЦЕПТУАЛИЗАЦИИ инженер по знаниям и эксперт решают, какие понятия, отношения и механизмы управления используются для описание решения задачи в избранной области. Исследуются также подзадачи, стратегии и ограничения, связанные с деятельностью по решению задач. На этой стадии обычно требуется рассмотреть вопрос о степени подробности представления знаний. Сначала выбирается наиболее абстрактный уровень детализации, (крупные гранулы) который обеспечивает четкое выделение ключевых понятий. После первой реализации ЭС придется детализировать отдельные гранулы и уточнять понятия.
  3. На этапе ФОРМАЛИЗАЦИИ ключевые понятия и отношения между ними формируются в рамках выбранной схемы и языка построения ЭС. Поэтому инженер по знаниям должен иметь представление о том, какие языки подходят для рассматриваемой задачи. Например, если задачу можно решить с помощью подхода, ориентированного на правила, то он может выбрать ROSIE в качестве языка описания системы и собирать знания в форме правил ЕСЛИ-ТО. Если подходит фреймовая модель представления знаний, то можно выбрать язык SRL и выразить знания предметной области в виде большой сети.
  4. На этапе РЕАЛИЗАЦИИ разработчик превращает формализованное знание в работающую компьютерную программу. Написание программы требует содержания, формы, согласования. Содержание берется из предметных знаний, сделанных явными в ходе формализации, т.е. структур данных, правил вывода и стратегий управления, необходимых для решения задачи.Форма задается языком, выбранным для разработки системы. Согласование включает в себя комбинирование и реорганизацию порций знаний с целью устранения неувязки между структурами данных, правилами и схемами управления.
  5. ТЕСТИРОВАНИЕ включает оценивание качества работы и полезности программы-прототипа, если это необходимо. При таком оценивании могут обнаруживаться ошибки. Например, ”отсутствие нужных понятий”, и тогда необходимо вернуться на этап идентификации и концептуализации.

При оценке качества работы ЭС необходимо ответить на следующие вопросы:
  1. Получаемые решения признаются экспертами правильными или нет?
  2. Являются ли правила вывода безошибочными, непротиворечивыми и полными?
  3. Позволяет ли стратегия управления рассматривать обстоятельства в естественном порядке, как предпочитает эксперт?
  4. Адекватно ли объяснения системы описывают, как, почему были получены те или иные заключения?
  5. Охватывают ли тестовые задачи всю запланированную область компетентности системы, покрывая классические случаи и нащупывая границы трудных случаев?

При оценке полезности возникает другой набор вопросов:
  1. Помогает ли решение задачи пользователю существенным образом?
  2. Являются ли заключения системы разумно организованными?
  3. Удовлетворяет ли пользователя скорость работы системы?
  4. Является ли интерфейс дружественным?

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

ЭС развиваются как и их средства построения от экспериментальных до коммерческих. Но разделяют 5 уровней разработки ЭС (таблица 3.).
  1. Демонстрационный прототип решает некоторую основную часть задачи. Создается для двух целей: 1. Убедить финансирующую организацию, что данная ЭС может эффективно использована для решения данных задач. 2. Проверить концепции постановки задачи, и представление данных из предметной области. Обычно содержит 50-100 правил, работает на 2-3 пробных случаях и требует до 3 месяцев на его разработку.
  2. Большинство ЭС доведены до уровня исследовательского прототипа. Это программы среднего размера, способные показать качество работы ЭС на ряде пробных случаев. Но они легко уязвимы, терпят провал, когда задача находится вблизи границы ее разрешения. Могут возникать и ошибки из-за недостаточного тестирования. Типичный исследовательский прототип содержит 200-500 правил, хорошо работает на большом числе пробных случаев, требует на разработку 1-2 года.

Таблица 3.


  1. Уровень разработки

    Характеристика
    1. Демонстрационный прототип

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

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

    Система проявляет высокое качество работы при обширном тестировании в реальных условиях
    1. Промышленный прототип

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

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