Лекции - Интеллектуальные системы

Подождите немного. Документ загружается.

показатель достоверности, тогда получается управление при

помощи «четверки»:

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

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

Любое правило состоит из условной части и заключения.

Условная часть проверяет все данные из рабочей памяти на

истинность (используется И). Если несколько правил, то выполнив

операцию ИЛИ над всеми заключениями этих правил, получаем

заключение.

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

Таким графом И/ИЛИ можно представить процесс вывода в

системе продукции. В самом верхнем узле – заключения,

выводимые системой, в самом низу – факты. А  В – это ядро

продукции.

заключение

условная часть

правила

И И И

д1 д2 д3 д4 правило 1 правило 2

ИЛ

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

детерминированн

ые

недетерминированны

правая часть ядра

обязательно выполнена.

не обязательно, может и

не выполняться

однозначные

если А, то В

альтернативные

если А, то чаще

, реже В

если А, то

возможно В.

если А, то с

вероятностью р

реализовать В.

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

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

серии правил и данных. Обратный вывод можно представить как

нахождение пути на данном графе, то есть для подтверждения

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

подтвердить все узды, являющиеся предусловиями этой цели.

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

последовательностью применения правил. Кроме того надо решать

вопрос о минимизации переборов правил и объема запрашиваемых

данных – это тоже управление выводом.

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

управление при обратном выводе.

При прямом повторяется цикл поиска данных в рабочей

памяти, генерации множества правил, разрешение конфликта и

применение правил.

Для управления выводом используются 2 метода:

 либо установка ряда ограничений на генерацию конфликтного

набора правил;

 либо алгоритм разрешения конфликта.

Для реализации первого подхода используются методы с

применением МЕТАПРАВИЛ – правил, в условной части которых

содержится условие, касающиеся содержания правил и

содержимого рабочей памяти.

Во втором случае правила предварительно группируются по

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

содержимого рабочей памяти и исследуется возможность

использования правила только из этой группы.

При управлении обратным выводом к этим проблемам

добавляется еще одна, связанная с последовательностью оценки

условий в условной части правила.

Контрольные вопросы:

1. Какие функции выполняет рабочая память?

2. Пополняется ли рабочая память в обратной цепочке

рассуждений?

3. Какой алгоритм более эффективный в прямой или обратной

цепочке рассуждений?

4. Как представляются факты в продукционных системах?

5. Как представляются правила в продукционных системах?

6. Как неточные знания учитываются в продукционных

моделях.

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

СИСТЕМЕ.

План лекции:

1. структура управляющего механизма.

2. классификация методов поиска.

3. методы повышения эффективности поиска.

4. примеры продукционных систем.

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

Интерпретатор, дерево целей, компонент вывода, компонент

управления, сопоставления, выбор, срабатывание.

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

стратегию поиска решения.

Управляющий механизм включает 2 компонента:

 один реализует собственно вывод;

 другой управляет этим процессом.

Компонент вывода просматривает существующие факты из

рабочей памяти и правила из базы знаний и подтверждает

истинность или ложность правила. Данный компонент должен

уметь функционировать в условиях недостатка информации, так

как не всегда можно извне дать значения недостающих фактов.

Управляющий компонент определяет порядок применения

правил, а также устанавливает, имеются ли еще факты, которые

могут быть учтены в случае продолжения работы.

Управляющий компонент выполняет 4 функции:

 сопоставление – образец правила сопоставляется с

имеющимися фактами;

 выбор – если в конкретной ситуации могут быть применены

сразу несколько правил, то из них выбирается одно, наиболее

подходящее по заданному критерию. Это называется

разрешение конфликта;

 срабатывание – если образец правила при сопоставлении

совпал с фактами из рабочей памяти, то срабатывает правило;

 действие – рабочая память подвергается изменению путем

добавления в нее заключения сработавшего правила (при

прямой цепочке рассуждений).

Интерпретатор работает циклически. В каждом цикле он

просматривает все правила, чтобы выявить те посылки, которые

совпадают с известными на данный момент фактами из рабочей

памяти. После выбора правило срабатывает и заключение

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

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

Действие заключения правила может менять критерий выбора

правил. Если это, например, игра в шахматы, то на основании

статических эвристик (правило игры) и динамических эвристик

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

выбора правил.

Выбор метода поиска решения зависит от следующих

параметров:

 размер ПО;

 изменяемость области;

 полнота модели, описывающей область;

 определенность данных о решаемой задаче;

 количество необходимых решений;

 ограничения на результат и способ его получения.

Цикл работы интерпретатора.

Конфли

кт

множес

тва

правил

сопост

авлени

Разреше

ние

конфлик

та

Критери

выбора

правил

Выполняем

ое правило

действи

Рабоч

ая

памят

База

прави

В зависимости от этих параметров используются следующие

методы:

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

статические области, точные и полные данные);

 поиск в иерархических пространствах (работа в больших

статических областях);

 поиск при неточных и неполных данных;

 поиск в динамических проблемных областях;

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

области (с разных точек зрения).

Рассмотрим один из простых методов. Имеется несколько

способов его реализации.

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

Граф G задает пространство состояний, в котором

осуществляется поиск решения. Берется некоторая вершина х

 Х

и проверяются все правила, порождающие все дочерние вершины.

Этот процесс называется раскрытием вершин. Процесс построения

заканчивается, когда все нераскрытые вершины являются

целевыми или терминальными (для которых нет правил).

Надежным способом обеспечения полноты является полный

перебор всех вершин. Для задания процесса перебора необходимо

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

способа: поиск в глубину и поиск в ширину.

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

1 1

2 5 7 2 3 4

3 4 6 8 9 5 6 7 8 9

ц т т ц ц т т т т ц

поиск в глубину поиск в ширину

Поиск можно осуществлять от данных (прямой поиск) и от

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

направлениях.

2. Эвристический поиск.

Методы поиска в глубину и ширину называются слепыми, так

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

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

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

«перспективности вершины». В некоторых случаях удается

оценить перспективность вершины, в других используется способ

выбора более «информированного» правила, не приводящего к

построению вершин, не относящихся к делу, в простейшем случае

выбирается вершина, от которой меньше расстояние до цели. Но

недостатком этих эвристик является потеря полноты информации.

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

счет сокращения пространства поиска.

Но если использовать специализированные структуры знаний,

то это также приведет к увеличению эффективности ЭС. В

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

знаний.

Другой идеей, способствующей повышению эффективности

ЭС, является компиляция знаний. Это процесс преобразования

одного способа представления знаний в другой более

эффективный.

Эти разработки получили свое признание в последнее время, но

исследования в этой области еще продолжаются.

Основные методы повышения эффективности поиска правил:

 поиск в глубину;

 поиск в ширину;

 разбиение на подзадачи (кл. доска);

 - - алгоритм.

Поиск в глубину: диагностическая система на основе

симптомов делает предположение о наличии определенного

заболевания и будет расспрашивать о признаках и симптомах этой

болезни, пока не опровергнет выдвинутую гипотезу.

Поиск в ширину: диагностическая система анализирует все

симптомы, находящиеся на одном уровне пространства состояний,

даже если они относятся к разным заболеваниям, а потом перейдет

к следующему уровню детальности.

Принцип классной доски (рис.23). Основан на идее спусковых

функций. При реализации принципа «классной доски» в ИС

выделяется рабочее поле памяти – аналог классной доски – на

которой пишут объявления и при необходимости стирают тряпкой.

На это «доске» параллельно выполняющиеся процессы и заносят

информацию о своей работе, что интересуют другие процессы. На

доске объявлений расположены в иерархическом порядке

гипотезы. На верхнем уровне – заключения, на нижнем – факты, на

промежуточных – промежуточные гипотезы. Вокруг доски

объявлений расположены сгруппированные правила, называемые

источниками знаний ИЗ. Группировка ИЗ по уровням позволяет

сократить время поиска фактов (ограничиваясь определенной

группой ИЗ

на каждом уровне) по сравнению со всей базой

данных.

- - алгоритм. Сводится к уменьшению пространства путей

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

решения. Поэтому просматривают только те вершины, в которых

можно попасть в результате следующего шага, после чего

неперспективны исключаются. Например, если цвет предмета «не

красный», то его бессмысленно искать среди предметов красного

цвета. Он находит широкое применение в различных играх

(шахматах и т. д.).

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

ИЗ

Рассмотрим стратегии выбора продукции из фронта готовых

продукций.

1. Принцип «стопки книг». Основан на идее, что наиболее часто

использующаяся продукция является наиболее полезной. На

самом верху «стопки» находится продукция, которая

использовалась чаще всех. При актуализации некоторого

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

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

принципу стопки удобно применять, если продукции

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

вида «ситуация А  действие В». Поэтому они используются в

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

2. Принцип наиболее длинного условия. Заключается в выборе из

фронта готовых продукций той, у которой стало истинным

наиболее длинное условие выполнимости ядра. Этот принцип

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

правила, относящиеся к узкому классу ситуации, важнее общих

правил, так как учитывается больше информации о ситуации.

Управление по этому принципу целесообразно в тех случаях,

когда знания и сами продукции хорошо структурированы

привязкой к типовым ситуациям, на которых задано отношение

типа «частное – общее».

3. Принцип метапродукций. Основан на идее ввода в систему

продукций специальных метапродукций, задачей которых

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

возможности неоднозначного выбора из фронта готовых

продукций (используется в MYCIN при диагностике

инфекционных заболеваний).

4. Принцип приоритетного выбора. Связан с введением

статических или динамических приоритетов на продукции.

Статические приоритеты могут формировать априори на

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

данной предметной области. Это обычно информация,

получаемая от экспертов. Динамические приоритеты

вырабатываются в процессе функционирования системы

продукций.

5. Управление по именам. Основано на задании для имен

продукции, входящих в некоторую систему, некоторой

формальной грамматики или другой процедуры, ссужающей

фронт готовых продукций и выбор из нее очередной

продукции.

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

 простота создания и понимания отдельных правил;

 простота пополнения и модификации;

 простота механизма логического вывода.

Недостатки:

 неясность взаимных отношений между правилами;

 сложность оценки целостного образа знаний;

 низкая эффективность обработки;

 отсутствие гибкости в логическом выводе.

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

OPS-5 широко известна как инструментальная система для

разработки самих ЭС (США). Факты в ней представлены в виде

триплетов. OPS-5 – это специализированная система с прямым

выводом, эффективность выполнения выводов увеличивается за

счет согласования RETE при генерации конфликтного набора.

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

заболеваний и лечения.

Рабочая память управляется в виде «четверки» – «объект –

атрибут – значение – к дост», т. е. учитывается нечеткость

информации.

пациент

инфекция

- культура

вирус

Рис. 24. Иерархические отношения между объектами в системе

MYCIN