Обратная цепочка (или обратное рассуждение ) - это метод вывода, который в просторечии описывается как работа в обратном направлении от цели. Он используется в автоматических средствах доказательства теорем , механизмах вывода , помощниках по доказательству и других приложениях искусственного интеллекта . [1]
В теории игр исследователи применяют ее к (более простым) подиграм, чтобы найти решение игры, в процессе, называемом обратной индукцией . В шахматах это называется ретроградным анализом , и он используется для создания основ таблиц для шахматных окончаний для компьютерных шахмат .
Обратная цепочка реализуется в логическом программировании с помощью разрешения SLD . Оба правила основаны на правиле вывода modus ponens . Это один из двух наиболее часто используемых методов рассуждений с использованием правил вывода и логических следствий - второй - это прямая цепочка . В системах с обратной цепочкой обычно используется стратегия поиска в глубину , например Prolog . [2]
Как это работает
Обратная цепочка начинается со списка целей (или гипотезы ) и работает в обратном направлении от консеквента к антецеденту, чтобы увидеть, поддерживают ли какие-либо данные какие-либо из этих следствий. [3] Механизм вывода, использующий обратную цепочку, будет искать правила вывода, пока не найдет одно с последующим ( предложением Then ), которое соответствует желаемой цели. Если известно, что предшествующее ( условие If ) этого правила истинно, то оно добавляется в список целей (для подтверждения цели необходимо также предоставить данные, подтверждающие это новое правило).
Например, предположим, что новое домашнее животное, Фриц, доставлено в непрозрачной коробке вместе с двумя фактами о Фрице:
- Фриц каркает
- Фриц ест мух
Цель состоит в том, чтобы решить, является ли Фриц зеленым, на основе базы правил, содержащей следующие четыре правила:
- Если X каркает и X ест мух - Тогда X - лягушка.
- Если X щебечет и X поет - Тогда X - канарейка
- Если X - лягушка - тогда X зеленый
- Если X - канарейка - тогда X желтый
При обратном рассуждении машина логического вывода может определить, является ли Фриц зеленым, за четыре шага. Для начала, запрос сформулирован как утверждение цели, которое необходимо доказать: «Фриц зеленый».
1. Фриц заменяется на X в правиле № 3, чтобы увидеть, соответствует ли его консеквент цели, поэтому правило № 3 становится:
Если Фриц лягушка - Значит Фриц зеленый
Поскольку консеквент соответствует цели («Фриц - зеленый»), механизму правил теперь необходимо проверить, можно ли доказать антецедент («Фриц - лягушка»). Следовательно, антецедент становится новой целью:
Фриц - лягушка
2. Снова заменяя Х на Фрица, правило №1 становится следующим:
Если Фриц каркает, а Фриц ест мух - Значит, Фриц лягушка
Поскольку консеквент соответствует текущей цели («Фриц - лягушка»), механизму вывода теперь необходимо проверить, можно ли доказать предшествующее («Фриц каркает и ест мух»). Следовательно, антецедент становится новой целью:
Фриц каркает, а Фриц ест мух
3. Поскольку эта цель является комбинацией двух утверждений, механизм вывода разбивает ее на две подцели, обе из которых необходимо доказать:
Фриц каркает Фриц ест мух
4. Чтобы доказать обе эти подцели, машина вывода видит, что обе эти подцели были заданы как исходные факты. Следовательно, соединение истинно:
Фриц каркает, а Фриц ест мух
следовательно, антецедент правила № 1 истинен, а следствие должно быть истинным:
Фриц - лягушка
следовательно, антецедент правила № 3 истинен, а следствие должно быть истинным:
Фриц зеленый
Таким образом, этот вывод позволяет механизму вывода доказать, что Фриц зеленый. Правила №2 и №4 не использовались.
Обратите внимание, что цели всегда соответствуют утвержденным версиям следствий импликаций (а не отвергнутым версиям, как в modus tollens ), и даже в этом случае их антецеденты рассматриваются как новые цели (а не выводы, как при подтверждении следствия ), которые в конечном итоге должны соответствовать известным фактам (обычно определяемым как следствия, антецеденты которых всегда верны); таким образом, используемое правило вывода - это modus ponens .
Поскольку список целей определяет , какие правила выбираются и используются, этот метод называется целью управляемым , в отличии от данных , ориентированных на вперед-цепочке умозаключений. Подход с обратной цепочкой часто используется в экспертных системах .
Такие языки программирования, как Prolog , Knowledge Machine и ECLiPSe, поддерживают обратную цепочку в своих механизмах вывода. [4]
Смотрите также
Рекомендации
- Перейти ↑ Feigenbaum, Edward (1988). Расцвет экспертной компании . Times Books. п. 317 . ISBN 0-8129-1731-6.
- ^ Мишель Чейн; Мари-Лор Мюнье (2009). Графическое представление знаний: вычислительные основы концептуальных графов . Springer. п. 297. ISBN. 978-1-84800-285-2.
- ^ Определение обратной цепочки как метода поиска в глубину:
- Рассел и Норвиг 2009 , стр. 337
- ^ Языки, поддерживающие обратную цепочку:
- Рассел и Норвиг 2009 , стр. 339
Внешние ссылки
- Пример обратной цепочки