Zpětné řetězení - Backward chaining

Nesmí být zaměňována s Zpětné zřetězení (aplikovaná analýza chování) nebo Zpětné řetězení.

Zpětné řetězení (nebo zpětné uvažování) je odvození metoda popsaná hovorově jako práce dozadu od cíle. Používá se v automatizované věty provers, odvozovací motory, důkazní asistenti, a další umělá inteligence aplikace.[1]

v herní teorie, vědci to aplikují na (jednodušší) podhry najít řešení hry v procesu zvaném zpětná indukce. V šachu se tomu říká retrográdní analýza a používá se ke generování databázových základen pro šachové koncovky pro počítačové šachy.

Zpětné řetězení je implementováno v logické programování podle Rozlišení SLD. Obě pravidla jsou založena na modus ponens pravidlo odvození. Je to jedna ze dvou nejčastěji používaných metod uvažování s odvozovací pravidla a logické důsledky - druhý je dopředu řetězení. Systémy zpětného řetězení obvykle používají a hloubkové vyhledávání strategie, např. Prolog.[2]

Jak to funguje

Zpětné řetězení začíná seznamem cíle (nebo a hypotéza ) a funguje zpětně od následný do předchůdce zjistit, jestli vůbec data podporuje kterýkoli z těchto důsledků.[3] An odvozovací stroj použití zpětného řetězení by prohledalo odvození pravidla, dokud nenajde jeden s následkem (Pak klauzule), která odpovídá požadovanému cíli. Pokud předchůdce (Li klauzule) tohoto pravidla je známo, že je pravdivá, poté je přidána do seznamu cílů (pro potvrzení cíle člověka je nutné uvést také údaje, které toto nové pravidlo potvrzuje).

Předpokládejme například, že nový mazlíček Fritz je dodáván v neprůhledné krabici spolu se dvěma fakty o Fritzovi:

  • Fritz skřečí
  • Fritz jí mouchy

Cílem je rozhodnout, zda je Fritz zelený, na základě a základna pravidel obsahující následující čtyři pravidla:

Příklad zpětného řetězení.
Příklad zpětného řetězení.
  1. Li X škrekání a X jí mouchy - Pak X je žába
  2. Li X pípne a X zpívá - Pak X je kanárek
  3. Li X je žába - Pak X je zelená
  4. Li X je kanárek - Pak X je žlutá

Zpětným uvažováním může odvozovací stroj určit, zda je Fritz zelený ve čtyřech krocích. Pro začátek je dotaz formulován jako tvrzení cíle, které má být prokázáno: „Fritz je zelený“.

1. Fritz nahradí X v pravidle # 3, aby zjistil, zda jeho následná shoda odpovídá cíli, takže pravidlo # 3 se stane:

 Li Fritz je žába - Pak Fritz je zelený

Jelikož následek odpovídá cíli („Fritz je zelený“), musí modul pravidel nyní zjistit, zda lze předchůdce („Fritz je žába“) dokázat. Předchůdce se proto stává novým cílem:

 Fritz je žába

2. Opět nahrazením Fritze za X bude pravidlo # 1:

 Li Fritz kváka a Fritz jí mouchy - Pak Fritz je žába

Vzhledem k tomu, že následek odpovídá aktuálnímu cíli („Fritz je žába“), je třeba v odvozovacím stroji zjistit, zda lze předchůdce („Fritz škrekuje a jí mouchy“) dokázat. Předchůdce se proto stává novým cílem:

 Fritz skřečí a Fritz jí mušky

3. Jelikož tento cíl je spojením dvou výroků, odvozovací modul jej rozděluje na dva dílčí cíle, které je nutné prokázat:

 Fritz skřečí Fritz jí mouchy

4. Aby bylo možné prokázat oba tyto dílčí cíle, odvozovací modul vidí, že oba tyto dílčí cíle byly uvedeny jako počáteční fakta. Proto je spojení pravdivé:

 Fritz skřečí a Fritz jí mouchy

proto je předchůdce pravidla č. 1 pravdivý a musí platit i následník:

 Fritz je žába

proto je předchůdce pravidla č. 3 pravdivý a musí platit i následník:

 Fritz je zelený

Tato derivace proto umožňuje odvozovacímu modulu dokázat, že Fritz je zelený. Pravidla # 2 a # 4 nebyla použita.

Cíle se vždy shodují s potvrzenými verzemi důsledků implikací (a nikoli s negovanými verzemi jako v modus tollens ) a dokonce i poté jsou jejich předchůdci považováni za nové cíle (a nikoli za závěry jako v potvrzující důsledky ), který nakonec musí odpovídat známým faktům (obvykle definovaným jako důsledky, jejichž předchůdci jsou vždy pravdiví); použité pravidlo odvození je tedy modus ponens.

Protože seznam cílů určuje, která pravidla jsou vybrána a použita, nazývá se tato metoda řízený cílem, na rozdíl od řízeno daty dopředné řetězení odvození. Přístup zpětného řetězení často používá expertní systémy.

Programovací jazyky jako Prolog, Stroj znalostí a Zatmění podporovat zpětné zřetězení v jejich odvozovacích strojích.[4]

Viz také

Reference

  1. ^ Feigenbaum, Edward (1988). Vzestup expertní společnosti. Times Books. p.317. ISBN  0-8129-1731-6.
  2. ^ Michel Chein; Marie-Laure Mugnier (2009). Grafická reprezentace znalostí: výpočetní základy koncepčních grafů. Springer. p. 297. ISBN  978-1-84800-285-2.
  3. ^ Definice zpětného řetězení jako metody hledání do hloubky:
  4. ^ Jazyky, které podporují zpětné zřetězení:

externí odkazy