Машина логического вывода продукционной экспертной системы

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

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

Машина вывода (интерпретатор правил) выполняет две функции:

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

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

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

Действие компонента вывода основано на применении правила, называемого modusponens:

«Если известно, что истинно утверждение А и существует правило вида «ЕСЛИ А, ТО В», тогда утверждение В также истинно».

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

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

Сопоставление —правила сопоставляются с имеющимися фактами, полученными от пользователя или в результате срабатывания правила.

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

Срабатывание — выполнение части «ТО» выбранного правила.

Машина вывода (Интерпретатор продукций) работает циклически. Цикл работы интерпретатора схематически представлен на рисунке 5.4.

— хранение: I I — действие: С ?- результат действия.

Рис. 5.4 Цикл работы машины вывода

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

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

в изменении критерия выбора конфликтующих правил,

в воздействии на что- либо (например, отключение аварийного блока).

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

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

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

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

Вопросы для самоконтроля:

Источник

Продукционная модель экспертных систем

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

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

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

Широкое применение систем, основанных на продукционных правилах, обусловленное наличием в них следующих особенностей:

Структура экспертной системы

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

Рис.1. Общая структура экспертной системы, основанной на правилах

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

Средство получения знаний. Средство получения знаний представляет собой автоматизированный способ, который позволяет пользователю вводить знания в систему, не применяя явного кодирования знаний с помощью инженера по знаниям. Этот инструментальное средство, в некоторых экспертных системах способен обучаться, осуществляя автоматическое формирование правил на основании примеров. Для формирования правил в машинном обучении применяются такие методы и алгоритмы, как ID3, С4.5, С5.1, искусственные генетические алгоритмы, нейронные сети.

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

Машина логического вывода. Машина логического вывода является программным компонентом, который определяет антецеденты правил (если таковые имеются), которые выполняются согласно фактам. Для этого машина логического вывода выполняет следующие действия:

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

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

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

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

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

Средство объяснения. Главной особенностью экспертной системы является предусмотренный в ней средство объяснения, который отображает информацию о том, как система пришла определенному выводу. В системах, основанных на правилах, несложно организовать объяснения, каким образом был получен определенный вывод, поскольку хронология активизации правил и содержание рабочей памяти можно хранить в стеке. Развитые средства объяснения могут дать пользователю возможность задавать вопросы, вроде, «что?», «Если?» И изучать альтернативные пути формирования выводов по принципу гипотетических рассуждений.

Источник

Представления знаний в интеллектуальных системах, экспертные системы

Введение

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

Экскурс в историю экспертных систем

История экспертных систем берет свое начало в 1965 году. Брюс Бучанан и Эдвард Фейгенбаум начали работу над созданием информационной системы для определения структуры химических соединений.

Результатом работы была система под названием Dendral. В основе системы формировалась последовательность правил подобных к «IF – THEN». Информационная система не перестала развиваться и получила множество наследников, таких как ONCOIN – информационная система для диагностики раковых заболеваний, MYCIN – информационная система для диагностики легочных инфекционных заболеваний.

Следующим этапом стали 70-е годы. Период не выделялся особыми разработками. Было создано множество разных прототипов системы Dendral. Примером служит система PROSPECTOR, областью деятельности которой являлась геологические ископаемые и их разведка.
В 80-ых годах появляются профессия – инженер по знаниям. Экспертные системы набирают популярность и выходят на новый этап эволюции интеллектуальных систем. Появились новые медицинские системы INTERNIS, CASNE.

С 90-ых годов развитие интеллектуальных систем приобретает новые и новые методы и особенности. Нововведением становится парадигма проектирования эффективных и перспективных систем. Гибкость, четкость решения поставленных задач дало новое название – мультиагентных систем. Агент – фоновый процесс который действует в целях пользователя. Каждый агент имеет свою цель, «разум» и отвечает за свою область деятельности. Все агенты в совокупности образуют некий интеллект. Агенты вступают в конкуренцию, настраивают отношения, кооперируются, все как у людей.

В 21 век, интеллектуальной системой уже не удивишь никого. Множество фирм внедряет экспертные системы в области своей деятельности.

Быстродействующая система OMEGAMON разрабатывается c 2004 года с IBM, цель которой отслеживание состояния корпоративной информационной сети. Служит для моментального принятия решений в критических или неблагоприятных ситуациях.

G2 – экспертная система от фирмы Gensym, направленная на работу с динамическими объектами. Особенность этой системы состоит в том, что в нее внедрили распараллеливание процессов мышления, что делает ее быстрее и эффективней.

Структура экспертной системы

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

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

3. Модель представления данных
Самая интересная часть экспертной системы.
Модель представления знаний (далее по тексту — МПЗ) — это способ задания знаний для хранения, удобного доступа и взаимодействия с ними, который подходит под задачу интеллектуальной системы.

4. Механизм логического вывода данных(Подсистема вывода)
Механизм логического вывода(далее по тексту — МЛВ) данных выполняет анализ и проделывает работу по получению новых знаний исходя из сопоставления исходных данных из базы данных и правил из базы знаний. Механизм логического вывода в структуре интеллектуальной системы занимает наиболее важное место.
Механизм логического вывода данных концептуально можно представить в виде :
А — функция выбора из базы знаний и из базы данных закономерностей и фактов соответственно
B — функция проверки правил, результатом которой определяется множество фактов из базы данных к которым применимы правила
С — функция, которая определяет порядок применения правил, если в результате правила указаны одинаковые факты
D — функция, которая применяет действие.

Какие существуют модели представления знаний?

Распространены четыре основных МПЗ:

Продукционная МПЗ

Пример

Пример продукции:
IF Температура = 39 AND Кашель = Есть AND Давление = 110-130 THEN Бронхит

Продукционная модель представления знаний нашла широкое применение в АСУТП

Среды разработки продукционных систем(CLIPS)

CLIPS (C Language Integrated Production System) — среда разработки продукционной модели разработана NASA в 1984 году. Среда реализована на языке С, именно потому является быстрой и эффективной.
Пример:

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

Семантическая сеть МПЗ

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

По количеству типов отношений выделяют однородные и неоднородные семантические сети. Однородные имею один тип отношения между всеми понятиями, следовательно, не однородные имею множество типов отношений.

Все типы отношений:

Пример

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

Фреймовая МПЗ

Предложил Марвин Мински в 1970 году. В основе фреймовой модели МПЗ лежит фрейм. Фрейм — это образ, рамка, шаблон, которая описывает объект предметной области, с помощью слотов. Слот — это атрибут объекта. Слот имеет имя, значение, тип хранимых данных, демон. Демон — процедура автоматически выполняющаяся при определенных условиях. Имя фрейма должно быть уникальным в пределах одной фреймовой модели. Имя слота должно быть уникальным в пределах одного фрейма.

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

Пример

Пример вырождающейся в сеть фреймов

На своей практике, мне доводилось встречать системы на основе фреймовой МПЗ. В университете в Финляндии была установлена система для управления электроэнергией во всем здании.

Языки разработки фреймовых моделей (Frame Representation Language)

FRL (Frame Representation Language) — технология создана для проектирования интеллектуальных систем на основе фреймовой модели представления знаний. В основном применяется для проектирования вырождающихся в сеть фреймовой модели.

Запись фрейма на языке FRL будет иметь вид:

Существуют и другие среды: KRL (Knowledge Representation Language), фреймовая оболочка Kappa, PILOT/2.

Формально логическая МПЗ

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

Пример

A1 = A2 = A3 = ; IF A1 AND A2 THEN
Банальней примера и не придумаешь.
Важно: Стоит заметить, что формально логическая МПЗ схожа с продукционной. Частично это так, но они имеют огромную разницу. Разница состоит в том, что в продукционной МПЗ не определены никакие связи между хранимыми объектами предметной области.

Важно

Любая экспертная система должна иметь вывод данных и последовательность «мышления» системы. Это нужно для того чтобы увидеть дефекты в проектировании системы. Хорошая интеллектуальная система должна иметь право ввода данных, которое реализуется через интеллектуальный редактор, право редактора на перекрестное «мышление» представлений при проектировании системы и полноту баз знаний(реализуется при проектировки закономерностей предметной области между инженером по знаниям и экспертом).

Заключение

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

Источник

Вывод в продукционных моделях. Механизм логического вывода и рекурсия

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

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

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

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

Прямым выводам (прямой цепочке рассуждений) соответствует движение от посылок к следствиям.

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

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

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

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

Рекурсия (лат. «recurso» – бегу назад, спешу обратно, возвращаюсь) – способ решения задач, заключающийся в разбиении исходной задачи на подзадачи. Если подзадача есть уменьшенный вариант исходной задачи, то способ ее разбиения и решения идентичен примененному к исходной задаче. Последовательное разбиение приводит к задаче, решаемой непосредственно. Это решение служит основанием для решения подзадачи верхнего уровня и т. д., пока первоначальная задача не будет решена.

Пример рекурсивных рассуждений:

Как найти льва в пустыне? Для этого следует выполнить следующие шаги:

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

Источник