Интеллектуальные информационные системы

КемИ РГТЭУ

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

В системах продукций знания представляются с помощью наборов
ЕСЛИ А1,А2,… Аn ТО В
Такая запись означает, что «если выполняются все условия от А1 до Аn (являются истинными), тогда следует выполнить действие В» Продукции также могут пониматься как «ситуация – действие», «причина – следствие», «условие – заключение». Условия А1,А2,… Аn обычно называют фактами. С помощью фактов обычно описывается текущее состояние предметной области. Действие В может трактоваться как добавление нового факта в описание текущего состояния предметной области.
Множество продукционных правил образует базу правил, которая представляет обособленный фрагмент знаний о решаемой проблеме. Психологи называют такие фрагменты чанками. Считается, что чанк – это объективно – существующая единица знаний, выделяемая человеком в процессе познания окружающего мира.

83

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

базы знаний экспертной системы MYCIN, предназначенной для диагностики инфекционных заболеваний крови.
ЕСЛИ:
Место выделения культуры – кровь И
Реакция микроорганизма – грамоотрицательтная И
Форма микроорганизма – палочка И
Пациент относится к группе риска
ТО
С уверенностью 0,6 название микроорганизма pseudomonia aeruginosa.

84

Продукционные модели
С каждым правилом связывается некоторое число, принимающее значение от

–1 до 1.
Число выражает степень достоверности следствия и называется коэффициентом уверенности. Это означает, что система имеет дело с неточными и ненадежными фактами.
В базе знаний MYCIN факты представляются с помощью триплета: объект-атрибут-значение, «культура – место – кровь» для факта 1. Если в процессе активации правила первые четыре факта окажутся истинными, то в базу знаний поступит новый факт, представляемый триплетом объект-атрибут-значение.

85

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

неисправности электрической плиты. Одно из правил экспертной системы может иметь вид:

ЕСЛИ:
лампа светится И
плита холодная

ТО нагреватель неисправен

86

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

Rnj : (Pr, Bc, AB, Ac), где
Rnj - идентификатор j – той продукции в n-ном наборе продукций;
Pr - приоритет правила продукции;
Bc – предусловие применимости ядра продукции, представляющее предикат, при выполнении которого активизируется ядро продукции;
AB –ядро продукции;
Ac – постусловия продукции, определяющее действия и процедуры, которые необходимо выполнить после выполнения ядра продукции.

87

Продукционные модели
В общем случае, продукционная система включает компоненты:
Базу продукционных правил
Базу

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

88

Продукционные модели













Рисунок 2.7 Продукционная система
89

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

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

90

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

четырех шагов:
выбор образа;
сопоставление образа с образцом и формирование конфликтного набора правил;
разрешение конфликтов (выбор конкретного правила);
выполнение правила.

91

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

примере сортировки строки, состоящей из букв a,b,c.
Задана строка cbca (образ) и задано множество продукций:
ba ab
ca ac
cbbc
Необходимо провести сортировку по трем заданным правилам.
Если образец, заданный предпосылкой правила, сопоставим с частью сортируемой строки, то правило активизируется.
В результате этого подстрока, которая совпала с условием правила, замещается подстрокой из заключительной части правила. Конфликтное множество на первом шаге состоит из правил 2 и 3. Процесс завершается, когда не оказывается правил, предпосылки которых сопоставимы с подстроками (к строке abcc нельзя применить ни одно из указанных правил).

92

Продукционные модели











Рисунок 2.8 Сортировка строки с помощью правил-продукций
93

Продукционные модели
Рассматривая исходную и отсортированную строки как начальное и конечное

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

94

Продукционные модели
Интересные результаты были получены А. Ньюэллом и Г. Саймоном

при разработке системы GPS. Они установили, что продукции соответствуют элементам знаний, накапливаемым в долговременной памяти человека.
Такие элементы знаний активизируются, если возникает соответствующая ситуация (по образцу).
Новые элементы знаний могут накапливаться в памяти без необходимости перезаписывания уже существующих элементов.
Рабочая память продукционных систем аналогична кратковременной памяти человека, который удерживает в центре внимания только текущую ситуацию. Содержимое рабочей памяти, как правило, не сохраняется после решения задач.
Благодаря указанной аналогии продукционные модели представления знаний получили широкое распространение в экспертных системах, моделирующих решение задач человеком – экспертом в той или иной области.

95

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

машина вывода (интерпретатор) выполняет две задачи - собственно логический вывод и управление выводом.
Логический вывод достаточно простой и реализуется на основе процедуры поиска по образцу.
Управление выводом предполагает решение двух вопросов:
с чего следует начать процесс вывода?
как поступить, если на некотором шаге вывода возможен выбор вариантов его продолжения?
Ответ на первый вопрос приводит к прямой и обратной цепочке рассуждений.
А на второй вопрос - к механизму разрешения конфликтов в продукционной системе.

96

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

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

97

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

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

98

Продукционные модели
Достоинства продукционных моделей
Универсальность: практически любая область знаний может быть

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

99

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

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

100

Представление нечетких знаний
При формализации знаний часто требуется осуществлять вывод в

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

101

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

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

102

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

В задачах, решаемых интеллектуальными системами, часто приходится пользоваться неточными знаниями, которые не могут быть интерпретированы как полностью истинные или ложные (0/1).
Существуют знания, достоверность которых выражается некоторой промежуточной цифрой между 0 и 1, например, 0,7
Термин «нечёткая логика» был впервые введен профессором Латфи Заде в 1965 году. Понятие множества было расширено допущением, что функция принадлежности элемента к множеству может принимать любые значения в интервале [0...1], а не только 0 или 1. Такие множества были названы нечёткими. Также автором были предложены различные логические операции над нечёткими множествами и предложено понятие лингвистической переменной, в качестве значений которой выступают нечёткие множества.
Заде ввел понятие лингвистической переменной.

103

Представление нечетких знаний
Лингвистическая переменная (ЛП) – это переменная, значение которой

определяется набором вербальных, то есть словесных характеристик некоторого свойства.
Например, лингвистическая переменная «Рост» определяется через набор нечетких множеств(карликовый, низкий, средний, высокий, очень высокий).
Значение ЛП определяется через нечеткие множества (НМ), которые определены на базовом наборе значений, или базовой числовой шкале (носителе), имеющей размерность.
Каждое значение ЛП определяется как нечетное множество («низкий рост» – это НМ).
НМ задается через некоторую базовую шкалу В и функцию принадлежности М(х), х В, принимающую значение на интервале [0,1].
Таким образом нечеткое множество В – это совокупность пар вида (х, М(х)), хВ.
В= {M(Х1)/X1; M(Х2)/X2; …M(Хi)/Xi);…. M(Хn)/Xn }, где Хi – i -тое значение базовой шкалы.
Пример Нечеткое множество для понятия 'горячий чай' может выглядеть следующим образом:
C={0/0; 0/10; 0/20; 0,15/30; 0,30/40; 0,60/50; 0,80/60; 0,90/70; 1/80; 1/90; 1/100}.
Функция принадлежности М(х) определяет субъективную степень уверенности эксперта в том, что данное конкретное значение базовой шкалы соответствует определяемому нечеткому множеству.
М(х) не следует путать с вероятностью, которая носит объективный характер и подчиняется другим законам.

104

Представление нечетких знаний
Например, для двух экспертов определение НМ «высокая» для

ЛП «цена автомобиля» в условных единицах может существенно отличаться в зависимости от их социального и финансового положения.
«высокая_ цена_1»= {1/50000;0.8/25000;0.6/10000;0.4/5000}
«высокая_ цена_2»= {1/25000;0.8/10000;0.7/5000;0.4/3000}

105

Представление нечетких знаний
Для операций с нечеткими знаниями, выраженными при помощи

ЛП, существует много различных способов вычисления сложных выражений .
Например, операция «ИЛИ» часто задается так:
М(х)=max(М1(х), М2(х)) (так называемая логика Заде)
Операция «И»
М(х)=min(М1(х), М2(х)) или (М1(х)* М2(х)) /100
Операция «не»
┐М(х)=1- М (х)
или операция «ИЛИ»:
М(х)=М1(х)+М2(х)- М1(х)хМ2(х) (вероятностный подход)

106

Представление нечетких знаний
Одним из первых применений теории НМ стало использование

коэффициентов уверенности для вывода рекомендаций медицинской системы MYCIN. Этот метод использует несколько эвристических приемов, он стал примером обработки нечетких знаний, повлиявшим на последующие системы.
Факторы (коэффициенты) уверенности измеряются по некоторой относительной шкале, например, от 0 до 1 (100).
В отличие от теории вероятностей сумма факторов уверенностей некоторых альтернативных значений необязательно составляет 1. Предполагается, что оценка факторов уверенностей исходных данных задается пользователем при описании конкретной ситуации, а факторы уверенности применения правил определяются инженерами знаний совместно с экспертами при наполнении базы знаний.
Факторы уверенности правил в системе GURU задаются после служебного слова cf. Например,
Если Предприятие = «малое»
То Надежность = «есть» cf 30

107

логики на примере оценки надежности поставщика, в котором кроме фактора

финансового состояния учитывается и фактор формы собственности.
Пусть государственное предприятие не имеет задолженность с уверен-
ностью 60 и предполагается, что его рентабельность удовлетворительна с уверенностью 80. Фрагмент множества правил имеет следующий вид:
Правило 1: Если Задолженность = «нет» и Рентабельность = «удовл.»
То Финансовое_состояние = «удовл.» cf 100
Правило 2: Если Финансовое_состояние = «удовл.»
То Надежность += «есть» cf 90
Правило 3: Если Предприятие = «государств.»
То Надежность+ = «есть» cf 50

108

(посылки) = min(60,80) = 60,
cf (Фин_сост.=«удовл.») = 60*100/100 = 60.
Результат

выполнения второго правила:
cf (Надежность=«есть») = 60*90/100 = 54
Результат выполнения третьего правила:
cf (Надежность=«есть») = 100*50/100 = 50

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

109

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

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

110

считать интеллектуальной, если в ней реализованы три группы основных функций:


функции

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

функции рассуждений

функции общения с пользователем

111

первой группы:

Накопление знаний о предметной области
Классификация знаний по критерию полезности

и непротиворечивости
Структурирование знаний в направлении их использования в конкретной области.
Автоматическое поддержание базы знаний при ее пополнении.

112

второй группы:

Инициализация процессов получения новых знаний
Соотнесение новых знаний со старыми.
Пополнение

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

113

третьей группы:

Общение на естественном языке (подмножество профессионального языка)
Обучение
Адаптация к специалистам

разной квалификации
Формирование по запросу пользователя объяснения своей деятельности
Документирование информации в форме, необходимой пользователю.

114

Обобщенная структурно-функциональная схема систем ИИ
115

фактов хранятся факты, носящие конкретный характер: факты, характеризующие текущую ситуацию,

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

116

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

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

117

реализует в целом первую группу функций, вторую группу имитирует решатель.

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

118

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

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

119

разработки СИИ
Инструментальные средства можно разделить на следующие типы:
1) Системы программирования

на языках высокого уровня, такие как С, С++, Паскаль, Фортран, Бейсик, Forth, Refal, SmallTalk , LISP, не содержат средств для представления и обработки знаний. Тем не менее, достаточно большая доля СИИ разработана с помощью языков традиционного программирования. Наиболее используемые - SmallTalk и LISP.
LISP разработан в 1960 г. Дж. Маккарти для доказательства теорем и использовался первоначально в проекте «Принимающий советы» для управления сложной системой, в которой данные задавались фразами на английском языке. Широкое использование языка LISP объясняется наличием развитых средств работы со списками и поддержкой механизма рекурсии, важных для характерной в СИИ обработки символьной информации. Заложенные в языке LISP идеи, способ описания данных оказали влияние на ряд языков ИИ: CONNIVER, PLANNER, PROLOG. С помощью языка LISP разработан ряд распространенных экспертных систем, таких как MYCIN, DENDRAL, PROSPECTOR

120

разработки СИИ
Инструментальные средства можно разделить на следующие типы:
2) Системы программирования

на языках представления знаний содержат собственные средства представления знания (в соответствии с определенной моделью) и поддержки логического вывода.
Языки представления знаний
в логических моделях - CONNIVER, PLANNER, PROLOG,
во фреймовых моделях - KRL, FRL,
в продукционных моделях - OPS5, KEE, KAPPA, CLIPS.

121

разработки СИИ
Инструментальные средства можно разделить на следующие типы:
3) Оболочки систем

искусственного интеллекта или «пустые экспертные системы» представляют собой готовые ЭС без базы знаний. Технология создания оболочки заключается в том, что из готовой ЭС удаляются знания из базы знаний.
4) Средства автоматизированного создания экспертных систем представляют собой гибкие программные системы, допускающие несколько моделей представления знаний, способов логического вывода и видов интерфейса.

122