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

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

Модели представления знаний.

Лекция 2.

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

В настоящее время существует множество моделей представления знаний. Выбор одной из них для какого-либо приложения ЭС очень важен, поскольку может значительно облегчить построение логического вывода, а также выборку, обновление и поддержание самих БЗ.

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

Типичными моделями представления знаний являются:

- модель, основанная на использовании правил (продукционная модель);

- модель, основанная на использовании фреймов;

- модель семантической сети;

- логическая модель.

В математике моделью называется некоторое множество М с заданным на нем набором отношений {r₁,r₂,…,r_n}. N-местное отношение определяется как множество n-ок объектов (n≥1). Например, одноместное отношение prim(x), определяющее свойство числа бать простым, характеризуется бесконечным множеством

M=prim(1), prim(2), prim(3), prim(5), prim(7), prim(11).

Отношение математически представляется в следующей форме имя_отношения (список_аргументов). В общем случае отношение предполагает некоторую процедуру (называемую разрешающей процедурой), которая устанавливает истинность или ложность отношения. Такая процедура может задаваться алгоритмом, правилами, таблицами и иными способами. Например, разрешающей процедурой для отношения prim(x), является алгоритм разложения числа x на простые множители.

Систему продукций можно считать наиболее распространенной моделью представления знаний (ПЗ). Продукционная система состоит из трех основных компонентов: базы правил, рабочей памяти и механизма логического вывода. База правил состоит из набора продукций (правил ввода типа <ЕСЛИ-ТО>). В рабочей памяти хранятся предпосылки, касающиеся конкретных задач предметной области, и результаты выводов, полученные на их основании. Механизм логического вывода использует правила в соответствии с содержимым рабочей памяти и решает какое правило следует применить следующим.

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

Таким образом схема ЭС продукционного типа имеет вид, представленный на рисунке 4.

Рис.4. ЭС продукционного типа.

Рассмотрим более подробно основные компоненты системы продукций.

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

Следующая основная часть системы - рабочая память. Содержимое памяти со временем изменяется, увеличиваясь в объеме по мере срабатывания правил.

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

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

- определение порядка просмотра и применения правил.

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

МЕТКА: R26 Использование зонтика

УСЛОВИЕ: ЕСЛИ (идет дождь)

ДЕЙСТВИЕ: ТО (возьмите зонтик)

ОБЪЯСНЕНИЕ: (зонтик предохраняет от дождя).

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

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

‹ S⁰, S^f-?› (1)

‹ S⁰-? , S^f› (2)

‹ S⁰, S^f ,А-?› (3)

‹ S⁰, S^f-?,А-?› (4)

где: S⁰ – начальная ситуация

S^f - конечная (желаемая, требуемая ситуация)

А – алгоритм (последовательность выполняемых продукций), переводящий систему из состояния S⁰ в состояние S^f.

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

Задача (2) является обратной по отношению к предыдущей.

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

Задача (4) представляет обобщение задач (1) и (3).

Различают продукционные системы с прямыми и обратными выводами. Системы продукций с прямыми выводами имеют наиболее давнюю историю. Рассмотрим пример.

Пример 1: База правил содержит следующие правила.

Правило 1.

ЕСЛИ "намерение - отдых" и "дорога ухабистая"

ТО "использовать джип"

Правило 2.

ЕСЛИ "место отдыха - горы"

ТО "дорога ухабистая"

После того, как в рабочую память записываются образцы "намерение - отдых" и "место отдыха - горы", рассматривается возможность применения этих правил. Сначала механизм вывода сопоставляет образцы из условной части правила с образцами, хранимыми в рабочей памяти. Если все образцы, соединенные "и", имеются в рабочей памяти, то условная часть считается истинной, в противном случае - ложной. Условная часть правила 1 - ложна, а правила 2 - истинна. Заключительная часть правила 2 выполняется механизмом вывода и образец "дорога ухабистая" заносится в рабочую память. При попытке вторично применить эти правила получается, что можно применить лишь правило 1, поскольку правило 2 было уже применено и выбыло из числа кандидатов. К этому времени содержимое рабочей памяти было дополнено новым образцом - результатом применения правила 2, поэтому условная часть правила 1 становится истинной, и содержимое рабочей памяти пополняется образцом его заключительной части - "использовать джип". В итоге правил, которые можно было бы применять, не остается, и система останавливается.

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

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

Пример 2. База правил имеет тот же состав правил. В рабочую память занесены те же образцы. Для доказательства выбрана цель: "Использовать джип". Исследуем сначала возможность применения правила 1, подтверждающего этот факт. Поскольку образец "намерение - отдых" из условной части правила 1 уже занесен в рабочую память, то для достижения цели достаточно подтвердить факт "дорога ухабистая". Следовательно, необходимо правило, подтверждающее этот факт. Условная часть правила2 истинна. Следовательно, правило выполняется и рабочая память при этом пополняется образцом "дорога ухабистая". Таким образом, в результате возможности применения правила 1 подтверждается цель "использовать джип".

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

- отсутствие применимых правил;

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

В случае обратного вывода имеется два условия останова:

- достигается первоначальная цель;

- заканчиваются правила, применимые для достижения цели в ходе вывода.

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

Пример 3: Дополним базу правил примера 1 еще одним правилом.

Правило 3.

ЕСЛИ "намерение - отдых"

ТО "нужна скорость".

И введем условие останова: появление в рабочей памяти образца "использовать джип".

Этап1. Возможно применения правил 2 и 3. Применяем 2.

Этап2. Возможно применение правил 1 и 3. Применяем 1 и выполняется условие останова системы. Но если применить на этапе 2 правило3, то потребуется еще один этап вывода. Следовательно, выбор правила влияет на эффективность.

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

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

объект - атрибут - значение.

(собаки - клички - Джон)

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

Кроме этого, при использовании систем продукций расширяют возможности представления правил. С этой целью:

- используют связь И, ИЛИ в условной части;

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

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

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

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

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

- простота пополнения и модификации базы правил;

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

Слабые стороны:

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

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

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

- отличие от человеческой структуры знаний;

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

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

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

- обнаружения сигналов с голосовых детекторов;

- вычисления фонем;

- составления слогов;

- распознавания слов;

- построения предложения;

- понимания предложения.

В американском университете Карнеги-Меллона разработана система HEARSAY-2, которая решает эту проблему. Характерной ее особенностью является использование “доски объявлений”. Основной принцип организации модели доски объявлений заключается в разбиении продукций по уровням иерархии. При этом заключения продукций на нижних уровнях используются как входные условия для продукций более высокого уровня. На самом нижнем уровне модели доски объявлений представлены факты, на самом верхнем – результирующее заключение. То есть для каждой отдельной проблемы, которые в совокупности составляют единое целое, имеется соответствующее множество знаний, которое называется источником знаний (ИЗ). Каждый ИЗ сам по себе строится как продукционная система. Управление ИЗ осуществляется через общую рабочую область памяти, называемую доской объявлений. При этом все знания используются согласовано, как единое целое.

В системе HEARSAY-2 доска объявлений состоит из семи иерархических уровней, и данные на каждом уровне сохраняются до тех пор, пока обработка не достигнет этого уровня. Обработка на каждом из этих уровней осуществляется не детерминированно: соответствующие результаты показывают только одну из возможностей понимания, и в этом смысле они называются гипотезами. Когда, используя определенную гипотезу, конструируется гипотеза для более высокого уровня, то она переносится на уровень, на который и переходит обработка данных. Некоторый источник знаний, имеющий отношение к гипотезе соответствующего уровня, принимает гипотезу нижнего уровня за посылку и с помощью механизма восходящих выводов генерирует гипотезу для более высокого уровня. Приняв гипотезу верхнего уровня, как заключение, этот источник знаний осуществляет нисходящий вывод и проводит проверку результата обработки, передавая его как обратную связь на более низкий уровень.

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

1. В чем заключается проблема представления знаний?

2. Из каких компонентов состоит система продукций?

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

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

5. Что такое конфликтный набор?

6. В чем заключаются сильные и слабые стороны продукционных систем?

7. Как используется в продукционных системах “доска объявлений”?

Дата добавления: 2014-01-07