Экспертные системы, основанные на данных.

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

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

Рассмотрим, например, задачу автомобильной диагностики на основе правил:

Правило 1: если

топливо поступает в двигатель и

двигатель вращается,

то

проблема в свечах зажигания.

Правило 2: если

двигатель не вращается и

фары не горят,

то

проблема в аккумуляторе или проводке.

Правило 3: если

двигатель не вращается и

фары горят,

то

проблема в стартере.

Правило 4: если

в баке есть топливо и

топливо поступает в карбюратор,

то

топливо поступает в двигатель.

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

Поиск в ширину на основе данных начинается из состояния, показанного на рис. 7.9. Оно очень напоминает состояние, изображенное на рис. 7.5. (см вопрос 15) Отличие состоит лишь в отсутствии информации в рабочей памяти. Предпосылки четырех правил проверяются на предмет "запрашиваемой" информации. Предпосылка топливо поступает в двигатель не является запрашиваемой, поэтому правило 1 применить нельзя, и управление переходит к правилу 2. Информация двигатель не вращается является запрашиваемой. Предположим, ответом на этот вопрос будет ложь, тогда в рабочую память заносится фраза двигатель вращается, как показано на рис. 7.10.

Но правило 2 применить нельзя, поскольку первая из двух конъюнктивных предпосылок является ложной. Управление переходит к правилу 3, в котором первая посылка снова принимает значение "ложь". В правиле 4 обе предпосылки являются запрашиваемыми. Предположим, ответом на оба вопроса будет "истина", тогда предложения в баке есть топливо и топливо поступает в карбюратор помещаются в рабочую память. Туда же заносится и заключение правила — топливо поступает в двигатель.

Итак, по первому разу все правила рассмотрены, и начинается повторное рассмотрение правил с учетом нового содержания рабочей памяти. Как показано на рис. 7.11, при сопоставлении правила 1 с данными в рабочей памяти его заключение — проблема в свечах зажигания — помещается в рабочую память. Больше никаких правил применить нельзя, и сеанс решения задачи завершается. На рис. 7.12 показан граф поиска, узлы которого содержат информацию, находящуюся в рабочей памяти (РП).

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

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

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

Во-вторых, и это является прямым результатом только что сказанного, пояснения, выдаваемые пользователю в процессе поиска, весьма ограничены. В системах на основе правил в ответ на вопрос "почему?'' пользователю представляется рассматриваемое правило. Однако, если последовательность правил точно не отслеживается (например, с помощью оппортунистического поиска), это объяснение нельзя развить. "Расплывчатость" поиска на основе данных затрудняет подобные объяснения. И, наконец, при достижении цели системе трудно дать исчерпывающее объяснение в ответ на вопрос "как?". В качестве частичного или полного объяснения можно лишь использовать содержимое рабочей памяти или список активизированных правил. Но опять-таки эти пояснения не дают полного согласованного обоснования, которое мы наблюдали в рассуждениях на основе цели.

Поиск в глубину и ширину.

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

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

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

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

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

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