Обратная цепочка
Обратная цепочка (или обратное рассуждение ) — это метод вывода, который в просторечии описывается как работа в обратном направлении от цели. Он используется в автоматизированных средствах доказательства теорем , машинах вывода , помощниках по доказательству и других искусственного интеллекта . приложениях [1]
В теории игр исследователи применяют его к (более простым) подиграм , чтобы найти решение игры, в процессе, называемом обратной индукцией . В шахматах это называется ретроградным анализом , и он используется для создания баз таблиц шахматных эндшпилей для компьютерных шахмат .
Обратная цепочка реализуется в логическом программировании с помощью разрешения SLD . Оба правила основаны на правиле вывода modus ponens . Это один из двух наиболее часто используемых методов рассуждения с правилами вывода и логическими выводами ; второй — прямая цепочка . Системы обратной цепочки обычно используют стратегию поиска в глубину , например Пролог . [2]
Как это работает
[ редактировать ]Обратная цепочка начинается со списка целей (или гипотезы ) и работает в обратном направлении от консеквента к антецеденту , чтобы увидеть, поддерживают ли какие-либо данные какой-либо из этих консеквентов. [3] Механизм вывода, использующий обратную цепочку, будет искать правила вывода , пока не найдет одно с последовательным выражением ( предложение then ), которое соответствует желаемой цели. Если антецедент ( предложение If ) этого правила не является истинным, то он добавляется в список целей (для подтверждения цели необходимо также предоставить данные, подтверждающие это новое правило).
Например, предположим, что новый питомец Фриц доставлен в непрозрачной коробке вместе с двумя фактами о Фрице:
- Фриц каркает
- Фриц ест мух
Цель состоит в том, чтобы решить, зеленый ли Фриц, на основе базы правил , содержащей следующие четыре правила:
- Если X квакает и X ест мух, то X — лягушка .
- Если X щебечет и X поет, то X — канарейка.
- Если X — лягушка, то X — зеленый.
- Если X — канарейка, то X желтый.
С помощью обратного рассуждения машина вывода может определить, зеленый ли Фриц, за четыре шага. Для начала запрос формулируется как утверждение цели, которое необходимо доказать: «Фриц зеленый».
1. Фриц заменяется на X в правиле №3, чтобы проверить, соответствует ли его последовательность цели, поэтому правило №3 становится следующим:
If Fritz is a frog – Then Fritz is green
Поскольку консеквент соответствует цели («Фриц — зеленый»), механизму правил теперь необходимо проверить, можно ли доказать антецедент («Фриц — лягушка»). Таким образом, антецедент становится новой целью:
Fritz is a frog
2. Снова заменив X на Fritz, правило №1 будет выглядеть следующим образом:
If Fritz croaks and Fritz eats flies – Then Fritz is a frog
Поскольку консеквент соответствует текущей цели («Фриц — лягушка»), механизм вывода теперь должен проверить, можно ли доказать антецедент («Фриц квакает и ест мух»). Таким образом, антецедент становится новой целью:
Fritz croaks and Fritz eats flies
3. Поскольку эта цель представляет собой объединение двух утверждений, машина вывода разбивает ее на две подцели, обе из которых должны быть доказаны:
Fritz croaks Fritz eats flies
4. Чтобы доказать обе эти подцели, машина вывода видит, что обе эти подцели были заданы как исходные факты. Следовательно, союз верен:
Fritz croaks and Fritz eats flies
следовательно, антецедент правила № 1 истинен, и консеквент должен быть истинным:
Fritz is a frog
следовательно, антецедент правила №3 истинен, и консеквент должен быть истинным:
Fritz is green
Таким образом, этот вывод позволяет машине вывода доказать, что Фриц зеленый. Правила №2 и №4 не использовались.
Обратите внимание, что цели всегда соответствуют подтвержденным версиям последствий импликаций (а не отрицаемым версиям, как в modus tollens ), и даже в этом случае их антецеденты тогда рассматриваются как новые цели (а не выводы, как при подтверждении консеквента ). которые в конечном итоге должны соответствовать известным фактам (обычно определяемым как последствия, антецеденты которых всегда верны); таким образом, используемое правило вывода — это modus ponens .
Поскольку список целей определяет, какие правила выбираются и используются, этот метод называется целенаправленным , в отличие от на основе данных прямого вывода . Подход обратной цепочки часто используется экспертными системами .
Языки программирования, такие как Prolog , Knowledge Machine и ECLiPSe, поддерживают обратную цепочку в своих механизмах вывода. [4]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Фейгенбаум, Эдвард (1988). Возникновение экспертной компании . Книги Таймс. п. 317 . ISBN 0-8129-1731-6 .
- ^ Мишель Шейн; Мари-Лор Мюнье (2009). Представление знаний на основе графов: вычислительные основы концептуальных графов . Спрингер. п. 297. ИСБН 978-1-84800-285-2 .
- ^
Определение обратной цепочки как метода поиска в глубину:
- Рассел и Норвиг 2009 , с. 337
- ^
Языки, поддерживающие обратную цепочку:
- Рассел и Норвиг 2009 , с. 339
Источники
[ редактировать ]- Рассел, Стюарт ; Норвиг, Питер (2009). Искусственный интеллект: современный подход . Прентис Холл. ISBN 978-0-13-604259-4 .