Обратная цепочка
Метод формирования выводов

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

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

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

Как это работает

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

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

  • Фриц хрипит
  • Фриц ест мух

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

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

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

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

 Если Фриц лягушка – Тогда Фриц зеленый

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

Фриц — лягушка.

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

 Если Фриц каркает и ест мух – Тогда Фриц – лягушка.

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

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

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

Фриц хрипит Фриц ест мух

4. Чтобы доказать обе эти подцели, машина вывода видит, что обе эти подцели были даны как начальные факты. Поэтому конъюнкция истинна:

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

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

Фриц — лягушка.

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

Фриц зеленый

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

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

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

Такие языки программирования, как Prolog , Knowledge Machine и ECLiPSe, поддерживают обратную цепочку в своих механизмах вывода. [4]

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

Ссылки

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

Источники

  • Пример обратной цепочки
Взято с "https://en.wikipedia.org/w/index.php?title=Обратная_цепочка&oldid=1197229624"