Материал: 2488

ция способов отказа от таких гипотез в ходе правдоподобных рассуждений.

1.3.4. Вывод на предикатах

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

Основные формы логического вывода:

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

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

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

Процесс, демонстрирующий, что некоторое множество F ППФ неудовлетворимо (невыполнимо), начинается с превращения каждой ППФ из множества F в предложение. В результате возникает некоторое множество S предложений. Можно показать, что если множество S неудовлетворимо, то неудовлетворимо и множество F. Далее ис-

36

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

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

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

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

1.3.5.Методы вывода и поиска решений

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

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

Сопоставление частей ЕСЛИ правил с фактами создает цепочку вывода. Цепочка вывода показывает, как система применяет правила для получения заключения. Для иллюстрации метода вывода на основе цепочки рассмотрим простой пример.

Допустим, БЗ первоначально включает факты А, В, С, D и Е, а БЗ

37

содержит только три правила: Правило 1: Y&D → Z. Правило 2: X&B&E→Y. Правило 3: A→X.

Цепочка вывода на рис. 6 показывает, как применяются правила для вывода факта Z.

Сначала срабатывает правило 3 для вывода нового факта Х из данного факта A. Затем правило 2 выполняется для вывода факта Y из первоначальных фактов В и Е, а также уже известного факта Х. И, наконец, правило 1 применяет первоначально известный факт D и только что полученный факт Y для прихода к заключению Z.

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

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

Рассмотренный пример использует прямую цепочку вывода. Продукционные системы, в которых сначала анализируется антецедентная часть (условия), имеют так называемую условно-выводимую архитектуру.

Альтернативным типом архитектуры, которая достаточно часто используется в СППР, являются целе-выводимые (действиевыводимые или консеквент-выводимые) продукционные системы. Например, правило вида

А&В&С→D

может быть интерпретировано как «Логическая конъюнкция А, В и С влечет D» или «Чтобы доказать D, необходимо установить А, В, С».

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

Рассмотрим упрощенный пример продукционной системы с кон-

38

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

БЗ: А, F

Правило 1: A&B&C→D.

Правило 2: D&F→G.

Правило 3: A&J→G. Правило 4: В→С. Правило 5: F→B. Правило 6: L→J. Правило 7: G→H.

Предположим, цель состоит в том, чтобы вывести истинность Н. В первую очередь проверяется, находится ли Н в БЗ? Так как в данном случае это не так, то система пытается вывести истинность Н, используя правила, имеющие Н в правой части. Таким является правило 7. Теперь система пытается вывести истинность G, так как истинность последнего влечет за собой истинность Н. Снова проверяется БЗ: в ней нет G, следовательно, организуется поиск правила, содержащего G в правой части. Таких правил несколько. В качестве стратегии «разрешения конфликта» будем считать, что правила упорядочены по приоритету, причем правилу с наименьшим номером соответствует больший приоритет.

Вданном случае выбирается правило 2, поэтому целью теперь становится вывести истинность D и F. Для этого достаточно показать, что А – истинно (так как находится в БЗ), В – истинно (согласно правилу 5), С – истинно (согласно правилу 4). Так как истинность D и F доказана, то из правила 2 следует истинность G, а из истинности G следует истинность Н (правило 7). Таким образом, цель достигнута. Элементы, истинность которых доказана, добавляются в БЗ. В данном случае это элементы Н, G, D, С. В.

1.3.6.Вывод во фреймовой системе

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

39

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

Таким образом, можно выделить три основных процесса, происходящих во фреймовых системах:

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

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

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

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

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

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

–В каком случае считать, что данный фрейм неадекватен ситуации и что в этом случае делать? Фрейм мог бы, например, ав-

40