Планирование, текущий контроль Диагностика
От настоящего к будущему От настоящего к прошлому
От антецедента к консеквенту От консеквента к антецеденту
Управляемые данными (восходящие рассужд) Управляемые целями (нисходящие)
Поиск решения из фактов Поиск фактов доказывающих гипот
Поиск в ширину Поиск в глубину
Не способствует объяснению Способствует объяснению
Структура продукционной системы. БП – База Правил есть набор правил, используемый как база знаний. РП – Рабочая Память (или память для кратковременного хранения), в ней хранятся предпосылки, касающиеся конкретных задач предметной области, и результаты выводов, полученных на их основании.
Механизм логического вывода – использует правила в соответствии с содержанием РП (рис.1).
1). Пример работы для прямого вывода. Предположим, что записываемые в РП данные представляют собой образцы в виде наборов символов (таблица 1). В представленном в таблице 1 простейшем случае условные части правил из БП содержат либо одиночные образцы, либо несколько условий, соединенных союзом “И”. В заключительной части содержатся образцы, которые в процессе вывода регистрируются в РП.
Таблица 1.
1). Образец “намерение - экспедиция” существует в РП, а “дорога - плохая”
отсутствует, поэтому условная часть первого правила - ложна.
2). Условие второго правила истинно, поэтому механизм вывода выполняет его
заключительную часть и образец “дорога - плохая” заносится в РП.
3). Делается попытка вторичного применения правил. Поскольку второе правило уже было применено, то оно выпадает из числа кандидатов на применение. Но условная часть первого правила становится истинной, поскольку РП уже дополнена образцом “дорога - плохая”. Поэтому содержимое РП пополняется образцом заключительной части первого правила – “средство передвижения - джип”.
В итоге применимых правил не остается и система останавливается.
2). Пример работы для обратного вывода. Предположим, что наша цель состоит в доказательстве того, что “средство передвижения - джип”. Исследуем сначала возможность применения первого правила для подтверждения этого факта. Поскольку образец “намерение - экспедиция” из условной части первого правила уже занесен в РП, то для достижения цели достаточно подтвердить факт “дорога - плохая”.
Однако если принять образец “дорога - плохая ” за новую цель, то потребуется правило, подтверждающее этот факт. Поэтому исследуем возможность применения второго правила. Условная часть этого правила истинна, поэтому РП пополняется образцом “дорога - плохая”. Здесь появляется возможность применения первого правила и исходная цель подтверждается. В случае обратного вывода система останавливается либо при достижении первоначальной цели, либо по исчерпанию применимых для достижения цели правил.
Разрешение конфликтов при прямом выводе. В общем случае прямого вывода на каждом этапе имеется несколько правил, которые можно было бы применить, и возникает проблема выбора наиболее подходящего. Для иллюстрации дополним рассмотренный нами пример следующим правилом: ЕСЛИ “намерение - экспедиция” (3) ТО “требуется выбрать средство передвижения”. Кроме того, введем еще одно условие останова системы: появление в рабочей памяти образца “средство передвижения - джип”. Вследствие добавления правила (3) на первом этапе прямого вывода появляется возможность применить и правило (2), и правило (3). Если сначала применить правило (2), то на следующем этапе можно будет применить и правило (1), и правило (3). Если на этом этапе применить правило (1), то выполняется условие останова системы, но если сначала применить правило (3), то потребуется еще один этап вывода перед тем, как система остановится. Исходя из этого соображения, выбор делается в пользу правила (1). Таким образом, выбор применяемого правила оказывает прямое влияние на эффективность вывода. При большом количестве продукций возникает проблема разрешения конфликта.
Определение. Конфликтным набором называется множество правил, которые в одинаковой мере могут быть применены на одном и том же этапе логического вывода. Выбор одного из этих правил называется разрешением конфликта.
Разрешение конфликтов при обратном выводе. Дополним рассмотренный пример следующим правилом: ЕСЛИ “место экспедиции - тайга” ТО “дорога - плохая” (4). Если на основании этого условия подтверждается цель “средство передвижения – джип”, то для ее достижения достаточно применить только одно правило (1), но для подтверждения новой цели “дорога - плохая”, которая в конъюнкции с целью “намерение - экспедиция” открывает возможность применения правила (1), нужно выбрать либо правило (2), либо правило (4).
Если сначала применить правило (2), то сразу же можно будет применить и правило (1). При попытке применить правило (4) в РП не будет найдено образца “место экспедиции - тайга”, не будет также найдено и правил, которые подтверждали бы необходимость занесения этого образца в РП. Поэтому выбор правила (4) приведет к неуспеху, а цель “дорога - плохая” будет подтверждена лишь путем применения правила (2).
Заметим, что в рассматриваемом случае обратного вывода не принималась во внимание возможность применения правила (3). Это позволяет заключить, что для обратных выводов характерна тенденция исключения из рассмотрения правил, не имеющих прямого отношения к заданной цели, что позволяет повысить эффективность самого вывода.
Анализ контекста применения правила. В ряде задач требуется уточнение смысла образцов, которые заносятся в РП. Для управления данными, уточняющими смысл образцов при выполнении вывода, в таких задачах используется представление данных триплетами “объект - значение”. Например, данные (учеб. дисциплина 1, название, “Физика”) показывают тот факт, что существует некоторая (учебная) дисциплина и название этой дисциплины (например, в учебном плане) – “Физика”.
Основное преимущество – уточнение контекста, в котором применяется правило. Например, единое для всех объектов ”учеб. дисциплина” правило должно быть пригодным для применения вне зависимости от рассматриваемой учебной дисциплины.
Если существует несколько объектов, для которых пригодно одно и то же правило, то оно может быть применено для каждого объекта не более одного раза!
Эта проблема – проблема контекста применения правила. Объект применения правила есть контекст применения правила.
Преимущество контекстного описания. Представление данных с помощью триплета “объект-атрибут-значение” может быть расширено для описания данных, включающих показатели нечеткости. Пример: в системе MYCIN применяется показатель нечеткости, который называется фактором достоверности CP. Данные, для которых задан этот показатель, управляются при помощи ассоциативной четверки “объект-атрибут-значение-фактор достоверности”. Главный момент – проверка наличия в РП специальных данных, касающихся условной части правила. Здесь могут иметь место ряд проблем:
– Формализация сравнений численных значений по величине в условиях, содержащих требования к численным значениям атрибутов (требуется вычисление значения атрибута).
– Проблема определения принадлежности численного значения к определенной категории. Для описания подобных условий вводятся предикаты.
– Необходима функция запроса пользователем информации фактов-предпосылок из РП
при организации диалога “человек-машина”.
Представление системы продукций “И/ИЛИ” графом. На практике при использовании систем продукций в соответствии с необходимостью производят расширения продукционных правил, в частности, путем введения связей типа “ИЛИ” в условной части, использованием в условной части вычислений на основе содержимого РП, либо путем использования заключительной части правила с указанием на заключение без дополнения содержимого РП. Визуально отношение между содержимым РП, на которое делается ссылка из условной части правила, и дополнением содержимого РП, указываемым в заключительной части, представляет ся в вид е дерева (рис.2).
Если существует множество правил, из которых выводится одно и то же заключение, то отношение между результатом отдельного вывода и данными, на основании которых делается вывод, можно представить с помощью одного графа “И/ИЛИ” (рис.3).
В самом нижнем узле этого графа будут располагаться основные системные данные, а в самом верхнем узле – выводимые системой заключения. Рис.3.
Заключение на основе нескольких правил. Рис.2. Представление правила графом “И.ИЛИ”. Вывод при наличии нечеткой информации. Различают две категории нечеткостей: нечеткость непосредственных данных и нечеткость вывода. При выводе заключения с помощью нескольких правил, среди которых имеются нечеткие, возникает проблема определения степени нечеткости всего заключения. Пусть заключение C выводится с помощью множества альтернативных правил R1, R2, …, Rn (рис.4) и нечеткость заключения C характеризуется степенью достоверности, которая представляется численным значением. Обозначим степень достоверности заключения C для каждого из правил R1, R2, …,Rn как CM1, CM2, …, CMn и рассмотрим функцию КОМБ синтеза степеней достоверности в качестве метода определения степени достоверности CMT, передаваемой на заключительном этапе в C: CMT = КОМБ(CM1, CM2, …, CMn).
Способы поиска на графе, представляющем систему продукций, для случая наличия нечеткостей зависят от вида функции КОМБ. В общем случае считается, что если хотя бы одна из степеней CMi, i∈{1, …,n} отрицает нечеткость, то и CMT отрицает нечеткость, а соответствующее правило Ri следует использовать раньше других. Фактически, если степень достоверности отрицает нечеткости, то поиск нужно прекратить. Если же такого Ri не существует, либо, несмотря на его существование, невозможно получить достоверный вывод, не содержащий нечеткостей, либо нельзя опровергнуть достоверность всего заключения вследствие неопределенности степени достоверности для всех правил в силу свойств функции КОМБ, тем не менее, вывести итоговое заключение можно, но для этого необходимо попытаться применить все правила R1, R2, …,Rn. Рис.4.
Синтез степеней достоверности при обращении с нечеткой информацией. Суть проблемы управления выводом. Управление последовательностью применения правил (управление выводом) необходимо для решения следующих задач:
– Разрешение конфликтов, которое влияет, в конечном счете, на эффективность системы в целом.
– Минимизация объема запрашиваемых данных и учет естественного порядка запросов в системах с запросом данных пользователем.
При прямом выводе управление сводится к следующему циклу:
1). Поиск данных в РП.
2). Генерация конфликтного набора.
3). Разрешение конфликта в соответствии с выбранной стратегией.
4). Применение правил.
Известно два метода управления выводом:
– Установка ограничений на генерацию конфликтного набора.
– Определение алгоритма разрешения конфликта.
Установка ограничений на генерацию конфликтного набора. Способ установки ограничений на генерацию конфликтного набора зависит от содержания правил. В качестве этого способа может использоваться:
– Метод, по которому поиск условной части правил определенной категории не осуществляется.
– Метод с предварительным разбиением правил на отдельные категории и в определенных ситуациях исследуется возможность применения правил, принадлежащих только к некоторой категории.
Для реализации первого подхода рассматриваются методы с использованием метаправил
– правил, в условной части которых содержится условие, касающееся содержания правила (условной и заключительной частей) и содержимого РП, или правил, имеющих условную часть, указывающую атрибуты (как условные, так и заключительные), не подлежащие поиску или исследуемые на этот предмет.
Во втором случае правила предварительно группируются по атрибутам, для каждой группы указывается условие (его форма аналогична условной части правила), касающееся содержимого РП, и исследуется возможность применения правила только из той группы, в пределах которой выполняется это условие, либо группа указывается с помощью заключительной части правила и допускается/запрещается применение правил этой группы.
Вывод по приоритету глубины. Используется в случаях, когда явно задано условие останова системы. Вывод по приоритету глубины фактически соответствует попытке приоритетного применения правила со ссылкой на последнюю информацию, которой была дополнена РП. Рис.5.
Применение правил при выполнении вывода по приоритету глубины. При сравнении правил 2 и 3 на рис.5 предпочтение отдается Правилу 3. Достоинство: минимальность пути логического вывода, реализуется понятный пользователю путь логического вывода. Если же существует множество правил со ссылкой на последнюю занесенную в РП информацию, то приоритет может быть отдан правилу с более жесткой условной частью (с большим количеством условий).
В системах, в которых пользователь по ходу вывода запрашивает данные, м.б. применены алгоритмы разрешения конфликтов, использующие знания предметной области для оптимизации последовательности запросов.