Контрольная работа по "Экспертным системам"

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

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

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

3.1.2. Поиск методом редукции

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

Процесс решения задачи разбиением ее на подзадачи можно представить  в виде специального направленного  графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставитсяв соответствие описание некоторой задачи

(подзадачи). В графе выделяют  два типа вершин: конъюнктивные  вершины и дизъюнктивные вершины.

Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.

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

1. Конечные (целевые) вершины  разрешимы, так как их решение  известно по исходному предположению.

1. Вершина ИЛИ разрешима  тогда и только тогда, когда  разрешима по крайней мере одна из ее дочерних вершин.

1. Вершина И разрешима тола и только тогда, когда разрешима каждая из ее дочерних вершин.

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

Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом, так и в обратном направлении. На рис. 3.4. приведен пример поиска в ширину (рис. 3.4., а) и поиска в глубину (рис. 3.4., б). На рисунке вершины пронумерованы в том порядке, в котором они раскрывались, конечные вершины обозначены квадратами, разрешимые вершины зачернены, дуги решающего графа выделены двойными линиями.

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

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

3.1.4.Поиск методом "генерация-проверка"

Процесс поиска может быть сформулирован в терминах "генерация-проверка".

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

3.2. ПОИСК В ИЕРАРХИИ  ПРОСТРАНСТВ

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

Пространство поиска представлено иерархией пространств.

Методы поиска решения  в иерархических пространствах  обычно делятся на:

1) поиск в факторизованном  пространстве,

2) поиск в фиксированном  множестве пространств

3) поиск в изменяющемся  множестве пространств.

3.2.1. Поиск в факторизованном  пространстве

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

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

3.2.2. Поиск в фиксированном множестве пространств

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

3.2.3. Поиск в изменяющемся  множестве иерархических пространств

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

№6. Схема функционирования управляющей компоненты

В данной главе будет рассмотрена  работа управляющей компоненты, т.е. вопросы о том, как осуществляет решение задачи сама ЭС. Необходимость  использовать в ЭС нетрадиционные методы управления вызвана в первую очередь  неформализованностью решаемых ими задач. Особенности неформализованных задач с точки зрения организации управления приводят к тому, что процесс решения таких задач не удается представить в виде детерминированной последовательности программных модулей. Здесь в некоторый текущий момент к исполнению пригодно несколько модулей (или один модуль, но над разными данными), причем не существует надежной информации, позволяющей предпочесть один модуль другому. Задача управляющей компоненты состоит в том, чтобы обеспечить функционирование системы в подобных условиях. Неформализованную задачу можно характеризовать двумя величинами: 1) средним числом модулей, готовых к исполнению в текущий момент; 2) средней мощностью каждого модуля, готового к исполнению. Степень неформализованности задачи прямо пропорциональна среднему числу модулей, готовых в текущий момент к исполнению, и обратно пропорциональна средней мощности. В традиционном программировании модули (программы) вызываются по имени, поэтому программист в ходе составления и отладки программы должен выявить множество всех мыслимых ситуаций, которые возникнут в ходе работы общей программы при различных входных данных; и в каждой точке, где завершается работа одного модуля, в явном виде (указав имя модуля и перечень используемых им данных) запрограммировать однозначный переход к очередному модулю. Такая организация управления не позволяет решать неформализованные задачи.

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

Классическая схема управления экспертной системой

Общая схема функционирования управляющей компоненты экспертной системы приведена на рис.

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

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

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

С точки зрения теории работа интерпретатора зависит только от состояния  рабочей памяти и от состава базы знаний. На практике обычно учитывается  история работы интерпретатора, т.е. поведение интерпретатора в предшествующих циклах. Информация о поведении интерпретатора запоминается в так называемой памяти состояний интерпретатора. Обычно память состояний содержит в том или  ином виде протокол работы системы. В  общем случае каждый из этапов использует в своей работе три источника  знаний: 1) рабочую память; 2) базу знаний; 3) память состояний интерпретатора. Каждый из этапов направляет свою работу с помощью стратегий, т.е. с помощью  определенного набора эвристических  правил. Возможности стратегий по управлению процессом функционирования зависят от того, какие функции  интерпретатора встроены в него жестко, а какие могут изменяться. Встраивание  определенных функций в интерпретатор  повышает эффективность его работы, но ограничивает степень воздействия  на процесс функционирования. Как  правило, в интерпретатор встраивают общую схему поиска решения (т.е. метод), а через стратегии управляют  деталями поиска.

Для более глобального  влияния на процесс управления необходимо иметь возможность выбирать ту или  иную схему интерпретации. Общая  схема работы интерпретатора в процессе его работы может изменяться.

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

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

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

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

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

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

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