Обратная цепочка - Backward chaining

Не путать с Обратная цепочка (прикладной анализ поведения) или же Обратная цепь.

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

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

Обратная цепочка реализована в логическое программирование к Разрешение SLD. Оба правила основаны на modus ponens правило вывода. Это один из двух наиболее часто используемых методов рассуждение с правила вывода и логические следствия - другой прямая цепочка. Системы обратной цепочки обычно используют поиск в глубину стратегия, например Пролог.[2]

Как это устроено

Обратная цепочка начинается со списка цели (или гипотеза ) и работает в обратном направлении от последующий к предшествующий чтобы увидеть, есть ли данные поддерживает любой из этих консеквентов.[3] An Механизм логического вывода использование обратной цепочки приведет к поиску вывод правил, пока не найдет одно с следствием (потом пункт), который соответствует желаемой цели. Если антецедент (Если пункт) этого правила, как известно, истинность, затем он добавляется в список целей (для подтверждения цели необходимо также предоставить данные, подтверждающие это новое правило).

Например, предположим, что новое домашнее животное, Фриц, доставлено в непрозрачной коробке вместе с двумя фактами о Фрице:

  • Фриц каркает
  • Фриц ест мух

Цель состоит в том, чтобы решить, зеленый ли Фриц, на основе база правил содержащий следующие четыре правила:

Пример обратной цепочки.
Пример обратной цепочки.
  1. Если X каркает, а X ест мух - потом X - лягушка
  2. Если Х щебечет и Х поет - потом X - канарейка
  3. Если Х - лягушка - потом X зеленый
  4. Если Х - канарейка - потом X желтый

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

1. Фриц заменяется на X в правиле № 3, чтобы увидеть, соответствует ли его консеквент цели, поэтому правило № 3 становится:

 Если Фриц - лягушка - потом Фриц зеленый

Поскольку консеквент соответствует цели («Фриц - зеленый»), механизму правил теперь необходимо проверить, можно ли доказать антецедент («Фриц - лягушка»). Следовательно, антецедент становится новой целью:

 Фриц - лягушка

2. Снова заменяя Х на Фрица, правило №1 становится следующим:

 Если Фриц каркает, а Фриц ест мух - потом Фриц - лягушка

Поскольку консеквент соответствует текущей цели («Фриц - лягушка»), механизму вывода теперь необходимо проверить, может ли быть доказано предшествующее («Фриц каркает и ест мух»). Следовательно, антецедент становится новой целью:

 Фриц каркает, а Фриц ест мух

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

 Фриц каркает, Фриц ест мух

4. Чтобы доказать обе эти подцели, машина вывода видит, что обе эти подцели были заданы как исходные факты. Следовательно, соединение истинно:

 Фриц каркает, а Фриц ест мух

следовательно, антецедент правила № 1 истинен, а следствие должно быть истинным:

 Фриц - лягушка

следовательно, антецедент правила № 3 истинен, а следствие должно быть истинным:

 Фриц зеленый

Таким образом, этот вывод позволяет механизму вывода доказать, что Фриц зеленый. Правила №2 и №4 не использовались.

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

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

Языки программирования, такие как Пролог, Машина знаний и Затмение поддерживают обратную цепочку в своих машинах вывода.[4]

Смотрите также

Рекомендации

  1. ^ Фейгенбаум, Эдвард (1988). Расцвет экспертной компании. Times Books. п.317. ISBN  0-8129-1731-6.
  2. ^ Мишель Чейн; Мари-Лор Мюнье (2009). Графическое представление знаний: вычислительные основы концептуальных графов. Springer. п. 297. ISBN  978-1-84800-285-2.
  3. ^ Определение обратной цепочки как метода поиска в глубину:
  4. ^ Языки, поддерживающие обратную цепочку:

внешняя ссылка