logo

Vorwärtsverkettung und Rückwärtsverkettung in der KI

In der künstlichen Intelligenz ist die Vorwärts- und Rückwärtsverkettung eines der wichtigen Themen, aber bevor wir die Vorwärts- und Rückwärtsverkettung verstehen, sollten wir zunächst verstehen, woher diese beiden Begriffe stammen.

windows.open Javascript

Inferenz-Engine:

Die Inferenzmaschine ist die Komponente des intelligenten Systems der künstlichen Intelligenz, die logische Regeln auf die Wissensbasis anwendet, um aus bekannten Fakten neue Informationen abzuleiten. Die erste Inferenzmaschine war Teil des Expertensystems. Die Inferenzmaschine arbeitet üblicherweise in zwei Modi:

    Vorwärtsverkettung Rückwärtsverkettung

Hornklausel und bestimmte Klausel:

Hornsatz und bestimmter Satz sind Formen von Sätzen, die es der Wissensbasis ermöglichen, einen eingeschränkteren und effizienteren Inferenzalgorithmus zu verwenden. Logische Inferenzalgorithmen verwenden Vorwärts- und Rückwärtsverkettungsansätze, die KB in Form von erfordern Definitivsatz erster Ordnung .

Bestimmter Satz: Eine Klausel, die eine Disjunktion von Literalen mit ist genau ein positives Literal ist als bestimmte Klausel oder strenge Hornklausel bekannt.

Hornklausel: Eine Klausel, die eine Disjunktion von Literalen mit ist höchstens ein positives Literal ist als Hornsatz bekannt. Daher sind alle bestimmten Sätze Hornsätze.

Beispiel: (¬ p V ¬ q V k) . Es gibt nur ein positives Literal k.

Es ist äquivalent zu p ∧ q → k.

A. Vorwärtsverkettung

Die Vorwärtsverkettung wird bei Verwendung einer Inferenzmaschine auch als Vorwärtsdeduktions- oder Vorwärtsschlussfolgerungsmethode bezeichnet. Vorwärtsverkettung ist eine Form des Denkens, die mit atomaren Sätzen in der Wissensbasis beginnt und Inferenzregeln (Modus Ponens) in Vorwärtsrichtung anwendet, um mehr Daten zu extrahieren, bis ein Ziel erreicht ist.

Der Vorwärtsverkettungsalgorithmus geht von bekannten Fakten aus, löst alle Regeln aus, deren Prämissen erfüllt sind, und fügt ihre Schlussfolgerung den bekannten Fakten hinzu. Dieser Vorgang wiederholt sich, bis das Problem gelöst ist.

Eigenschaften der Vorwärtsverkettung:

  • Es handelt sich um einen Down-Up-Ansatz, der von unten nach oben verläuft.
  • Dabei handelt es sich um einen Prozess, bei dem auf der Grundlage bekannter Fakten oder Daten eine Schlussfolgerung gezogen wird, indem man vom Anfangszustand ausgeht und den Zielzustand erreicht.
  • Der Vorwärtsverkettungsansatz wird auch als datengesteuert bezeichnet, da wir das Ziel mithilfe verfügbarer Daten erreichen.
  • Der Vorwärtsverkettungsansatz wird häufig in Expertensystemen wie CLIPS, Geschäfts- und Produktionsregelsystemen verwendet.

Betrachten Sie das folgende berühmte Beispiel, das wir in beiden Ansätzen verwenden werden:

Beispiel:

„Laut Gesetz ist es für einen Amerikaner ein Verbrechen, Waffen an feindliche Nationen zu verkaufen. Land A, ein Feind Amerikas, verfügt über einige Raketen, und alle Raketen wurden ihm von Robert, einem amerikanischen Staatsbürger, verkauft.

Beweise das „Robert ist kriminell.“

Um das obige Problem zu lösen, werden wir zunächst alle oben genannten Fakten in bestimmte Klauseln erster Ordnung umwandeln und dann einen Vorwärtsverkettungsalgorithmus verwenden, um das Ziel zu erreichen.

Faktenumrechnung in FOL:

  • Für einen Amerikaner ist es ein Verbrechen, Waffen an feindliche Nationen zu verkaufen. (Sagen wir, p, q und r sind Variablen)
    Amerikaner (p) ∧ Waffe(q) ∧ verkauft (p, q, r) ∧ feindlich(r) → Verbrecher(p) ...(1)
  • Land A hat einige Raketen. ?p Owns(A, p) ∧ Missile(p) . Es kann in zwei bestimmten Klauseln geschrieben werden, indem die existentielle Instanziierung verwendet wird und die neue Konstante T1 eingeführt wird.
    Besitzt(A, T1) ......(2)
    Rakete(T1) ......(3)
  • Alle Raketen wurden von Robert an Land A verkauft.
    ?p Raketen(p) ∧ Besitzt (A, p) → Verkauft (Robert, p, A) ......(4)
  • Raketen sind Waffen.
    Rakete(p) → Waffen (p) .......(5)
  • Der Feind Amerikas wird als feindselig bezeichnet.
    Feind(p, Amerika) →Feind(p) ........(6)
  • Land A ist ein Feind Amerikas.
    Feind (A, Amerika) .........(7)
  • Robert ist Amerikaner
    Amerikaner(Robert). ..........(8)

Beweis der Vorwärtsverkettung:

Schritt 1:

Im ersten Schritt beginnen wir mit den bekannten Fakten und wählen die Sätze aus, die keine Implikationen haben, wie zum Beispiel: Amerikaner (Robert), Feind (A, Amerika), Besitzt (A, T1) und Rakete (T1) . Alle diese Fakten werden wie folgt dargestellt.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Schritt 2:

Im zweiten Schritt werden wir diejenigen Fakten sehen, die aus verfügbaren Fakten und mit erfüllten Prämissen abgeleitet werden können.

Regel-(1) erfüllt die Prämissen nicht und wird daher in der ersten Iteration nicht hinzugefügt.

Regel (2) und (3) wurden bereits hinzugefügt.

Regel-(4) erfüllt die Substitution {p/T1}, so verkauft (Robert, T1, A) hinzugefügt, was sich aus der Verbindung von Regel (2) und (3) ergibt.

Regel-(6) ist mit der Substitution (p/A) zufrieden, daher wird Hostile(A) hinzugefügt, was aus Regel-(7) folgt.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Schritt 3:

In Schritt 3 können wir überprüfen, ob Regel (1) mit der Ersetzung zufrieden ist {p/Robert, q/T1, r/A}, also können wir Criminal(Robert) hinzufügen was auf alle verfügbaren Fakten schließen lässt. Und damit haben wir unser Ziel erreicht.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Somit ist bewiesen, dass Robert ein Krimineller ist, indem der Vorwärtsverkettungsansatz verwendet wird.

B. Rückwärtsverkettung:

Die Rückwärtsverkettung wird bei Verwendung einer Inferenzmaschine auch als Rückwärtsdeduktion oder Rückwärtsschlussfolgerungsmethode bezeichnet. Ein Rückwärtsverkettungsalgorithmus ist eine Form des Denkens, die mit dem Ziel beginnt und rückwärts arbeitet, indem sie Regeln verkettet, um bekannte Fakten zu finden, die das Ziel unterstützen.

Eigenschaften der Rückwärtsverkettung:

  • Es ist als Top-Down-Ansatz bekannt.
  • Die Rückwärtsverkettung basiert auf der Modus-Ponens-Inferenzregel.
  • Bei der Rückwärtsverkettung wird das Ziel in Teilziele unterteilt, um zu beweisen, dass die Fakten wahr sind.
  • Man spricht von einem zielorientierten Ansatz, da eine Liste von Zielen darüber entscheidet, welche Regeln ausgewählt und angewendet werden.
  • Der Rückwärtsverkettungsalgorithmus wird in der Spieltheorie, in automatisierten Beweiswerkzeugen für Theoreme, Inferenzmaschinen, Beweisassistenten und verschiedenen KI-Anwendungen verwendet.
  • Die Rückwärtsverkettungsmethode verwendet meist a Tiefensuche Strategie zum Beweis.

Beispiel:

Bei der Rückwärtsverkettung verwenden wir dasselbe obige Beispiel und schreiben alle Regeln neu.

    Amerikaner (p) ∧ Waffe(q) ∧ verkauft (p, q, r) ∧ feindlich(r) → Verbrecher(p) ...(1)
    Besitzt(A, T1) ........(2) Rakete (T1) ?p Raketen(p) ∧ Besitzt (A, p) → Verkauft (Robert, p, A) ......(4) Rakete(p) → Waffen (p) .......(5) Feind(p, Amerika) →Feind(p) ........(6) Feind (A, Amerika) .........(7) Amerikaner(Robert). ..........(8)

Beweis der Rückwärtsverkettung:

Bei der Rückwärtsverkettung beginnen wir mit unserem Zielprädikat, nämlich Krimineller (Robert) und leiten Sie dann weitere Regeln ab.

Schritt 1:

Im ersten Schritt gehen wir von der Zielfakten aus. Und aus der Zieltatsache werden wir andere Tatsachen ableiten und schließlich beweisen, dass diese Tatsachen wahr sind. Unser Ziel ist also „Robert ist kriminell“, daher ist Folgendes das Prädikat davon.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Schritt 2:

Im zweiten Schritt werden wir andere Fakten aus der Zieltatsache ableiten, die den Regeln entspricht. Wie wir in Regel 1 sehen können, ist das Zielprädikat Criminal (Robert) mit der Substitution {Robert/P} vorhanden. Daher werden wir alle konjunktiven Fakten unterhalb der ersten Ebene hinzufügen und p durch Robert ersetzen.

Hier können wir sehen, dass American (Robert) eine Tatsache ist und daher hier bewiesen wird.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Schritt 3: t In Schritt 3 extrahieren wir weitere Fakten Missile(q), die aus Weapon(q) abgeleitet werden, da sie Regel-(5) erfüllen. Waffe (q) gilt auch mit der Ersetzung einer Konstanten T1 bei q.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Schritt 4:

In Schritt 4 können wir die Fakten Missile(T1) und Owns(A, T1) aus Sells(Robert, T1, r) ableiten, was die Anforderungen erfüllt Regel 4 , mit der Ersetzung von A anstelle von r. Diese beiden Aussagen werden hier also bewiesen.

Vorwärtsverkettung und Rückwärtsverkettung in der KI

Schritt 5:

In Schritt 5 können wir die Tatsache ableiten Feind (A, Amerika) aus Feindlich (A) was Regel 6 erfüllt. Und daher werden alle Aussagen durch Rückwärtsverkettung als wahr bewiesen.

Vorwärtsverkettung und Rückwärtsverkettung in der KI