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

1. Продукционные модели представления знаний

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

i: S; L; A  ® B; Q

где i — индивидуальный номер продукции; S — описание класса ситуаций, в котором данная структура может использоваться; L — условие, при котором продукция активизируется; А—>В — ядро продукции, например: «ЕСЛИA₁, А₂ ..., А_n ТО В». Такая запись означает, что «если все условия от А₁, до А_п являются истиной, то В также истина»;(Q— постусловие продукционного правила, описывает операции и действия (процедуры), которые необходимо выполнить после выполнения В.

В левой части  правила продукции ставится некоторое  условие, а в правой части — действие. Если все условия истинны, то выполняется действие, заданное в правой части продукции.

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

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

*  модульность — отдельные продукционные правила могут быть 
добавлены, удалены или изменены в базе знаний независимо от 
других;

*  каждое продукционное правило является самостоятельным элементом знаний;

*  простота смысловой интерпретации;

*естественность  с точки зрения здравого смысла.

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

2.Семантические сети

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

В качестве понятий  обычно выступают абстрактные или  конкретные объекты, а отношения — это связи типа: «это» («АКО — А-Кind-Of»,«is») «имеет частью» («has part») «принадлежит». Характерной особенностью семантических сетей является обязательное наличие трех типов отношений:

*  класс—элемент класса;

*  свойство—значение;

*пример элемента класса.

Наиболее часто  в семантических сетях используются следующие отношения :

* связи типа «часть—целое»;

*   функциональные связи (определяемые обычно глаголами «производит», «влияет» и др.);

*   количественные (больше, меньше, равно и т. д.);

*   пространственные (далеко от, близко от и др.);

*   временные (раньше, позже и др.);

* атрибутивные  связи (иметь свойство, иметь значение);

*   логические связи (И, ИЛИ, НЕ);

*   лингвистические связи и др.

 

Пример семантической сети

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

Достоинства сетевых моделей:

*  большие выразительные возможности;

*  наглядность системы знаний, представленной графически;

*  близость структуры сети, представляющей систему знаний, семантической структуре фраз на естественном языке;

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

Недостатки сетевых моделей:

*  сетевая модель не дает ясного представления о структуре предметной области, которая ей соответствует, поэтому формирование и модификация такой модели затруднительны;

*  сетевые модели представляют собой пассивные структуры, для обработки которых необходим специальный аппарат формального вывода и планирования;

*  сложность поиска вывода на семантических сетях.

Структура, режимы функционирования, классификация экспертных систем

Структура

· Интерфейс пользователя (Интерфейс (от англ. interface -- поверхность раздела, перегородка) -- совокупность средств и методов взаимодействия между элементами системы.)

· Пользователь

· Интеллектуальный редактор базы знаний

· Эксперт (Эксперт (от лат. expertus -- опытный) -- специалист, дающий заключение при рассмотрении какого-нибудь вопроса.)

· Инженер

· Рабочая (оперативная) память

· База знаний

· Решатель (механизм вывода)

· Подсистема объяснений

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

Как правило, база знаний ЭС содержит факты (статические сведения о предметной области) и правила - набор инструкций, применяя которые  к известным фактам можно получать новые факты.

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

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

Обычно факты в базе знаний описывают те явления, которые  являются постоянными для данной предметной области. Характеристики, значения которых зависят от условий конкретной задачи, ЭС получает от пользователя в  процессе работы, и сохраняет их в рабочей памяти. Например, в  медицинской ЭС факт «У здорового  человека 2 ноги» хранится в базе знаний, а факт «У пациента одна нога» -- в рабочей памяти.

База знаний ЭС создается  при помощи трех групп людей:

1. эксперты той проблемной  области, к которой относятся  задачи, решаемые ЭС;

2. инженеры по знаниям,  являющиеся специалистами по  разработке ИИС;

3. программисты, осуществляющие  реализацию ЭС.

Режимы функционирования Экспертных систем

ЭС может функционировать  в 2-х режимах.

1. Режим ввода знаний -- в этом режиме эксперт с помощью инженера по знаниям посредством редактора базы знаний вводит известные ему сведения о предметной области в базу знаний ЭС.

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

Классификация Экспертных систем по решаемой задаче

· Интерпретация данных

· Диагностирование

· Мониторинг

· Проектирование

· Прогнозирование

· Сводное Планирование

· Обучение

· Управление

· Ремонт

· Отладка

Классификация Экспертных систем по связи с реальным временем

· Статические ЭС

· Квазидинамические ЭС

· Динамические ЭС

Этапы разработки Экспертных систем

· Этап идентификации проблем -- определяются задачи, которые подлежат решению, выявляются цели разработки, определяются эксперты и типы пользователей.

· Этап извлечения знаний -- проводится содержательный анализ проблемной области, выявляются используемые понятия и их взаимосвязи, определяются методы решения задач.

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

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

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

· Этап тестирования -- производится оценка выбранного способа представления знаний в ЭС в целом.

Наиболее известные/распространённые ЭС

· CLIPS -- весьма популярная ЭС (public domain)

· OpenCyc -- мощная динамическая ЭС с глобальной онтологической моделью и поддержкой независимых контекстов

3.МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ

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

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

1) количеством решений : одно решение, несколько решений, все решения.

2) свойствами результата: ограничения, которым должен удовлетворять  полученный результат

3) и (или) способом его  получения.

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

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

3.1. ПОИСК РЕШЕНИЙ  В ОДНОМ ПРОСТРАНСТВЕ

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

1) поиск в пространстве состояний (рассмотрим подробно),

2) поиск методом редукции,

3) эвристический поиск

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

3.1.1. Поиск в пространстве состояний

Задача поиска в пространстве состояний обычно формулируется  в теоретико-графовой интерпретации.

Пусть задана тройка (S0, F, SТ), где S0 - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, SТ - множество конечных (целевых) состояний

(решений задачи).

Цель: определять такую последовательность операторов, которая преобразует  начальные состояния в конечные.

Процесс решения в виде графа G=(Х, Y), где X={х0, х1,...} - множество

(в общем случае бесконечное)  вершин графа, состояний, а  Y - множество, содержащее пары  вершин (xi, xj), (xi, xj)(X. Если каждая пара (xi, xj) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (xi, xj) задан порядок (направление), то пару (xi, xj) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (xi, xj) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (xi, xj) свидетельствует о существовании некоторого оператора f (f(F), преобразующего состояние, соответствующее вершине xi, в состояние xj. Для некоторой вершины xi выделяем множество всех направленных пар (xi, xj)(Y, т.ь. множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин

(называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине хi.

В множестве вершин X выделяют подмножество вершин Х0(Х, соответствующее множеству начальных состояний (So),, и подмножество вершин Хт(X, соответствующее множеству конечных (целевых) состояний (SТ).

Множество Хт может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

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

Итак, граф G задает пространство состояний, т.е. пространство, в котором  осуществляется поиск решения. Построение пространства осуществляется с помощью  следующего процесса. Берется некая  вершина х0(Х, к ней применяются все возможные операторы, порождающие все дочерние вершины.

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

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