Rete-Algorithmus - Rete algorithm

Der RETE - Algorithmus ( / r í t Ï / REE -tee , / r eɪ t Ï / RAY -tee , selten / R í t / REET , / r ɛ t eɪ / reh- TAY ) ist ein Mustervergleich Algorithmus zur Implementierung regelbasierter Systeme . Der Algorithmus wurde entwickelt, um viele Regeln effizient anzuwendenoder Muster zu vielen Objekten oder Fakten in einer Wissensdatenbank . Es wird verwendet, um zu bestimmen, welche Regeln des Systems basierend auf seinem Datenspeicher, seinen Fakten, ausgelöst werden sollen. Der Rete-Algorithmus wurde von Charles L. Forgy von der Carnegie Mellon University entworfen , zuerst 1974 in einem Arbeitspapier veröffentlicht und später 1979 in seinem Ph.D. Dissertation und ein Papier von 1982.

Überblick

Eine naive Implementierung eines Expertensystems könnte jede Regel anhand bekannter Tatsachen in einer Wissensdatenbank überprüfen , diese Regel bei Bedarf auslösen und dann zur nächsten Regel übergehen (und nach Abschluss zur ersten Regel zurückkehren). Selbst für Wissensdatenbanken mit Regeln und Fakten von mittlerer Größe ist dieser naive Ansatz viel zu langsam. Der Rete-Algorithmus liefert die Grundlage für eine effizientere Implementierung. Ein Expertensystem auf Rete-Basis baut ein Netz von Knoten auf , wobei jeder Knoten (außer der Wurzel) einem Muster entspricht, das auf der linken Seite (dem Bedingungsteil) einer Regel auftritt. Der Pfad vom Wurzelknoten zu einem Blattknoten definiert eine vollständige Regel auf der linken Seite. Jeder Knoten hat ein Gedächtnis von Tatsachen, die diesem Muster entsprechen. Diese Struktur ist im Wesentlichen ein verallgemeinerter Trie . Wenn neue Tatsachen geltend gemacht oder modifiziert werden, breiten sie sich entlang des Netzwerks aus, wodurch Knoten mit Anmerkungen versehen werden, wenn diese Tatsache mit diesem Muster übereinstimmt. Wenn eine Tatsache oder eine Kombination von Tatsachen bewirkt, dass alle Muster für eine gegebene Regel erfüllt werden, wird ein Blattknoten erreicht und die entsprechende Regel wird ausgelöst.

Rete wurde zuerst als Kernmotor der Produktionssystemsprache OPS5 verwendet, die verwendet wurde, um frühe Systeme einschließlich R1 für die Digital Equipment Corporation zu bauen. Rete ist zur Basis für viele beliebte Regel-Engines und Expertensystem-Shells geworden, darunter Tibco Business Events, Newgen OmniRules, CLIPS , Jess , Drools , IBM Operational Decision Management , OPSJ, Blaze Advisor, BizTalk Rules Engine , Soar , Clara und Sparkling Logic SMARTS . Das Wort „Rete“ ist lateinisch für „Netz“ oder „Kamm“. Das gleiche Wort wird im modernen Italienisch für Netzwerk verwendet . Charles Forgy hat Berichten zufolge erklärt, dass er den Begriff "Rete" wegen seiner Verwendung in der Anatomie verwendet hat, um ein Netzwerk von Blutgefäßen und Nervenfasern zu beschreiben.

Der Rete-Algorithmus wurde entwickelt, um Speicher für höhere Geschwindigkeit zu opfern . In den meisten Fällen beträgt die Geschwindigkeitssteigerung gegenüber naiven Implementierungen mehrere Größenordnungen (da die Rete-Performance theoretisch unabhängig von der Anzahl der Regeln im System ist). In sehr großen Expertensystemen neigt der ursprüngliche Rete-Algorithmus jedoch dazu, auf Speicher- und Serververbrauchsprobleme zu stoßen. Inzwischen wurden andere Algorithmen, sowohl neuartige als auch Rete-basierte, entwickelt, die weniger Speicher benötigen (zB Rete* oder Collection Oriented Match).

Beschreibung

Der Rete-Algorithmus liefert eine verallgemeinerte logische Beschreibung einer Implementierung einer Funktionalität, die für das Abgleichen von Datentupeln ("Fakten") mit Produktionen (" Regeln ") in einem Musterabgleich-Produktionssystem (einer Kategorie von Regelmaschinen ) verantwortlich ist. Eine Produktion besteht aus einer oder mehreren Bedingungen und einer Reihe von Aktionen, die für jeden vollständigen Satz von Tatsachen durchgeführt werden können, der die Bedingungen erfüllt. Bedingungen testen Faktattribute , einschließlich Fakttypspezifizierer/-identifizierer. Der Rete-Algorithmus weist die folgenden Hauptmerkmale auf:

  • Es reduziert oder eliminiert bestimmte Arten von Redundanz durch die Verwendung von Node-Sharing.
  • Es speichert teilweise Übereinstimmungen bei der Durchführung schließt sich zwischen verschiedenen Arten der Tat. Dies wiederum ermöglicht es Produktionssystemen, eine vollständige Neubewertung aller Fakten bei jeder Änderung des Arbeitsspeichers des Produktionssystems zu vermeiden. Stattdessen muss das Produktionssystem nur die Änderungen (Deltas) des Arbeitsspeichers auswerten.
  • Es ermöglicht ein effizientes Entfernen von Speicherelementen, wenn Fakten aus dem Arbeitsgedächtnis zurückgezogen werden.

Der Rete-Algorithmus wird häufig verwendet, um Matching-Funktionalität in Pattern-Matching-Engines zu implementieren, die einen Match-Resolve-Act-Zyklus nutzen, um Vorwärtsverkettung und Inferenz zu unterstützen .

  • Es bietet ein Mittel für viele-viele-Matching, ein wichtiges Merkmal, wenn viele oder alle möglichen Lösungen in einem Suchnetzwerk gefunden werden müssen.

Retes sind gerichtete azyklische Graphen , die Regelsätze höherer Ebene darstellen. Sie werden im Allgemeinen zur Laufzeit unter Verwendung eines Netzwerks von speicherinternen Objekten dargestellt. Diese Netze gleichen Regelbedingungen (Muster) mit Fakten (relationalen Datentupeln) ab. Rete-Netzwerke fungieren als eine Art relationaler Abfrageprozessor, der Projektionen , Auswahlen und Verknüpfungen bedingt auf einer beliebigen Anzahl von Datentupeln durchführt.

Produktionen (Regeln) werden normalerweise von Analysten und Entwicklern erfasst und definiert , die eine höhere Regelsprache verwenden. Sie werden in Regelsätzen gesammelt, die dann, oft zur Laufzeit, in ein ausführbares Rete übersetzt werden.

Wenn Fakten an das Arbeitsgedächtnis "behauptet" werden, erstellt die Engine Arbeitsgedächtniselemente (WMEs) für jeden Fakt. Fakten sind n-Tupel und können daher eine beliebige Anzahl von Datenelementen enthalten. Jede WME kann ein ganzes n-Tupel enthalten, oder alternativ kann jeder Fakt durch einen Satz von WMEs dargestellt werden, wobei jede WME ein Tupel fester Länge enthält. In diesem Fall sind Tupel typischerweise Tripletts (3-Tupel).

Jede WME tritt an einem einzelnen Root-Knoten in das Rete-Netzwerk ein. Der Wurzelknoten leitet jede WME an seine Kindknoten weiter, und jede WME kann dann durch das Netzwerk verbreitet werden, möglicherweise in Zwischenspeichern gespeichert, bis sie an einem Endknoten ankommt.

Alpha-Netzwerk

Die "linke" ( alpha ) Seite des Knotengraphen bildet ein Unterscheidungsnetzwerk, das für die Auswahl einzelner WMEs auf der Grundlage einfacher bedingter Tests verantwortlich ist, die WME-Attribute mit konstanten Werten abgleichen. Knoten im Unterscheidungsnetzwerk können auch Tests durchführen, die zwei oder mehr Attribute derselben WME vergleichen. Wenn eine WME erfolgreich mit den Bedingungen eines Knotens abgeglichen wird, wird sie an den nächsten Knoten weitergegeben. In den meisten Engines werden die unmittelbar untergeordneten Knoten des Root-Knotens verwendet, um die Entitätskennung oder den Faktentyp jeder WME zu testen. Daher durchlaufen alle WMEs, die denselben Entitätstyp darstellen, typischerweise einen gegebenen Knotenzweig in dem Unterscheidungsnetzwerk.

Innerhalb des Unterscheidungsnetzwerks endet jeder Zweig von Alpha-Knoten (auch 1-Eingangs-Knoten genannt) an einem Speicher, der Alpha-Speicher genannt wird . Diese Speicher speichern Sammlungen von WMEs, die jeder Bedingung in jedem Knoten in einem gegebenen Knotenzweig entsprechen. WMEs, die mindestens eine Bedingung in einem Zweig nicht erfüllen, werden im entsprechenden Alpha-Speicher nicht materialisiert. Alphaknotenverzweigungen können sich verzweigen, um die Bedingungsredundanz zu minimieren.

Beta-Netzwerk

Die "rechte" ( Beta ) Seite des Graphen führt hauptsächlich Joins zwischen verschiedenen WMEs durch. Es ist optional und wird nur bei Bedarf mitgeliefert. Es besteht aus 2-Eingangsknoten, wobei jeder Knoten einen "linken" und einen "rechten" Eingang hat. Jeder Betaknoten sendet seine Ausgabe an einen Betaspeicher .

In Beschreibungen von Rete ist es üblich, sich auf Token-Passing innerhalb des Beta-Netzwerks zu beziehen. In diesem Artikel werden wir jedoch die Datenweitergabe in Form von WME-Listen und nicht in Form von Token beschreiben, um die verschiedenen Implementierungsoptionen und den zugrunde liegenden Zweck und die Verwendung von Token zu erkennen. Wenn eine beliebige WME-Liste das Beta-Netzwerk passiert, können neue WMEs hinzugefügt werden, und die Liste kann in Beta-Speichern gespeichert werden. Eine WME-Liste in einem Beta-Speicher stellt eine teilweise Übereinstimmung mit den Bedingungen in einer bestimmten Produktion dar.

WME-Listen, die das Ende eines Zweigs von Betaknoten erreichen, stellen eine vollständige Übereinstimmung für eine einzelne Produktion dar und werden an Endknoten weitergegeben. Diese Knoten werden manchmal als p-Knoten bezeichnet , wobei "p" für Produktion steht . Jeder Endknoten repräsentiert eine einzelne Produktion, und jede WME-Liste, die an einem Endknoten ankommt, repräsentiert einen vollständigen Satz übereinstimmender WMEs für die Bedingungen in dieser Produktion. Für jede empfangene WME-Liste "aktiviert" ein Produktionsknoten eine neue Produktionsinstanz auf der "Agenda". Agenden werden normalerweise als priorisierte Warteschlangen implementiert .

Beta-Knoten führen typischerweise Verknüpfungen zwischen WME-Listen durch, die in Beta-Speichern gespeichert sind, und einzelnen WMEs, die in Alpha-Speichern gespeichert sind. Jeder Beta-Knoten ist mit zwei Eingabespeichern verbunden. Ein Alpha-Speicher hält WM und führt jedes Mal "richtige" Aktivierungen auf dem Beta-Knoten durch, wenn er eine neue WME speichert. Ein Beta-Speicher hält WME-Listen und führt jedes Mal "linke" Aktivierungen auf dem Beta-Knoten durch, wenn er eine neue WME-Liste speichert. Wenn ein Join-Knoten rechtsaktiviert wird, vergleicht er ein oder mehrere Attribute der neu gespeicherten WME aus seinem Eingabe-Alpha-Speicher mit gegebenen Attributen spezifischer WMEs in jeder WME-Liste, die im Eingabe-Beta-Speicher enthalten ist. Wenn ein Join-Knoten linksaktiviert wird, durchläuft er eine einzelne neu gespeicherte WME-Liste im Beta-Speicher und ruft spezifische Attributwerte von gegebenen WMEs ab. Es vergleicht diese Werte mit Attributwerten jeder WME im Alpha-Speicher.

Jeder Beta-Knoten gibt WME-Listen aus, die entweder in einem Beta-Speicher gespeichert oder direkt an einen Endknoten gesendet werden. WME-Listen werden in Beta-Speichern gespeichert, wenn die Engine zusätzliche Linksaktivierungen auf nachfolgenden Beta-Knoten durchführt.

Logischerweise ist ein Beta-Knoten an der Spitze eines Zweigs von Beta-Knoten ein Sonderfall, da er keine Eingaben von einem höher im Netzwerk befindlichen Beta-Speicher entgegennimmt. Verschiedene Engines handhaben dieses Problem auf unterschiedliche Weise. Einige Engines verwenden spezialisierte Adapterknoten, um Alpha-Speicher mit dem linken Eingang von Beta-Knoten zu verbinden. Andere Engines ermöglichen Beta-Knoten, Eingaben direkt von zwei Alpha-Speichern zu übernehmen, wobei einer als "linker" Eingang und der andere als "rechter" Eingang behandelt wird. In beiden Fällen beziehen "Kopf"-Beta-Knoten ihre Eingabe von zwei Alpha-Speichern.

Um Knotenredundanzen zu eliminieren, kann ein beliebiger Alpha- oder Beta-Speicher verwendet werden, um Aktivierungen auf mehreren Beta-Knoten durchzuführen. Neben Join-Nodes kann das Beta-Netzwerk weitere Node-Typen enthalten, von denen einige im Folgenden beschrieben werden. Wenn ein Rete kein Beta-Netzwerk enthält, füttern Alpha-Knoten Token, die jeweils eine einzelne WME enthalten, direkt an P-Knoten. In diesem Fall besteht möglicherweise keine Notwendigkeit, WMEs in Alpha-Speichern zu speichern.

Konfliktlösung

Während eines jeden Match-Resolve-Act-Zyklus findet die Engine alle möglichen Übereinstimmungen für die aktuell im Arbeitsspeicher geltend gemachten Fakten. Nachdem alle aktuellen Übereinstimmungen gefunden wurden und entsprechende Produktionsinstanzen auf der Agenda aktiviert wurden, bestimmt die Engine eine Reihenfolge, in der die Produktionsinstanzen "gefeuert" werden können. Dies wird als Konfliktlösung bezeichnet , und die Liste der aktivierten Produktionsinstanzen wird als Konfliktsatz bezeichnet . Die Reihenfolge kann auf der Regelpriorität ( Salienz ), der Regelreihenfolge , dem Zeitpunkt, zu dem die jeweils enthaltenen Tatsachen im Arbeitsgedächtnis festgehalten wurden, der Komplexität jeder Produktion oder anderen Kriterien basieren . Viele Engines ermöglichen es Regelentwicklern, zwischen verschiedenen Konfliktlösungsstrategien auszuwählen oder eine Auswahl mehrerer Strategien zu verketten.

Die Konfliktlösung ist nicht als Teil des Rete-Algorithmus definiert, sondern wird neben dem Algorithmus verwendet. Einige spezialisierte Produktionssysteme führen keine Konfliktlösung durch.

Produktionsdurchführung

Nachdem die Konfliktlösung durchgeführt wurde, "feuert" die Engine nun die erste Produktionsinstanz und führt eine Liste von Aktionen aus, die mit der Produktion verbunden sind. Die Aktionen wirken sich auf die Daten aus, die durch die WME-Liste der Produktionsinstanz dargestellt werden.

Standardmäßig feuert die Engine jede Produktionsinstanz der Reihe nach weiter, bis alle Produktionsinstanzen gefeuert wurden. Jede Produktionsinstanz wird während eines Match-Resolve-Act-Zyklus höchstens einmal ausgelöst. Diese Eigenschaft wird als Refraktion bezeichnet . Die Abfolge von Produktionsinstanzfeuerungen kann jedoch jederzeit unterbrochen werden, indem Änderungen am Arbeitsspeicher vorgenommen werden. Regelaktionen können Anweisungen zum Aktivieren oder Zurückziehen von WMEs aus dem Arbeitsspeicher der Engine enthalten. Jedes Mal, wenn eine einzelne Produktionsinstanz eine oder mehrere solcher Änderungen durchführt, tritt die Engine sofort in einen neuen Match-Resolve-Act-Zyklus ein. Dies schließt "Updates" von WMEs ein, die sich derzeit im Arbeitsspeicher befinden. Aktualisierungen werden durch Zurückziehen und anschließendes erneutes Bestätigen der WME dargestellt. Die Engine übernimmt den Abgleich der geänderten Daten, was wiederum zu Änderungen in der Liste der Produktionsinstanzen auf der Agenda führen kann. Daher können, nachdem die Aktionen für eine bestimmte Produktionsinstanz ausgeführt wurden, zuvor aktivierte Instanzen deaktiviert und aus der Agenda entfernt worden sein und können neue Instanzen aktiviert worden sein.

Als Teil des neuen Match-Resolve-Act-Zyklus führt die Engine eine Konfliktlösung auf der Agenda durch und führt dann die aktuelle erste Instanz aus. Die Engine feuert weiterhin Produktionsinstanzen ab und tritt in neue Match-Resolve-Act-Zyklen ein, bis keine weiteren Produktionsinstanzen auf der Tagesordnung stehen. An diesem Punkt wird davon ausgegangen, dass die Regelmaschine ihre Arbeit abgeschlossen hat und hält an.

Einige Engines unterstützen erweiterte Refraktionsstrategien, bei denen bestimmte Produktionsinstanzen, die in einem vorherigen Zyklus ausgeführt wurden, im neuen Zyklus nicht erneut ausgeführt werden, obwohl sie möglicherweise noch auf der Tagesordnung stehen.

Es ist möglich, dass die Engine in endlose Schleifen gerät, in denen die Agenda nie den leeren Zustand erreicht. Aus diesem Grund unterstützen die meisten Engines explizite "Halt"-Verben, die aus Produktionsaktionslisten aufgerufen werden können. Sie können auch eine automatische Schleifenerkennung bereitstellen, bei der endlose Schleifen nach einer bestimmten Anzahl von Iterationen automatisch angehalten werden. Einige Engines unterstützen ein Modell, bei dem die Engine nicht anhält, wenn die Agenda leer ist, sondern in einen Wartezustand wechselt, bis neue Fakten von außen geltend gemacht werden.

Was die Konfliktlösung betrifft, so ist das Auslösen von aktivierten Produktionsinstanzen kein Merkmal des Rete-Algorithmus. Es ist jedoch ein zentrales Merkmal von Engines, die Rete-Netzwerke verwenden. Einige der von Rete-Netzwerken angebotenen Optimierungen sind nur in Szenarien nützlich, in denen die Engine mehrere Match-Resolve-Act-Zyklen durchführt.

Existenzielle und universelle Quantifizierungen

Bedingte Tests werden am häufigsten verwendet, um Auswahlen und Verknüpfungen für einzelne Tupel durchzuführen. Durch die Implementierung zusätzlicher Beta-Knotentypen ist es für Rete-Netzwerke jedoch möglich, Quantifizierungen durchzuführen . Bei der existentiellen Quantifizierung wird geprüft, ob mindestens ein Satz übereinstimmender WMEs im Arbeitsgedächtnis vorhanden ist. Die universelle Quantifizierung beinhaltet das Testen, dass ein ganzer Satz von WMEs im Arbeitsgedächtnis eine bestimmte Bedingung erfüllt. Eine Variation der universellen Quantifizierung könnte testen, ob eine bestimmte Anzahl von WME, die aus einer Reihe von WME stammt, bestimmte Kriterien erfüllt. Dabei kann es sich um Tests auf eine genaue Anzahl oder eine Mindestanzahl von Übereinstimmungen handeln.

Die Quantifizierung ist in Rete-Engines nicht universell implementiert, und wo sie unterstützt wird, gibt es mehrere Variationen. Eine Variante der existentiellen Quantifizierung, die als Negation bezeichnet wird, wird weithin, wenn auch nicht universell, unterstützt und in wegweisenden Dokumenten beschrieben. Existentiell negierte Bedingungen und Konjunktionen beinhalten die Verwendung von spezialisierten Beta-Knoten, die testen, ob übereinstimmende WMEs oder Gruppen von WMEs nicht vorhanden sind. Diese Knoten geben WME-Listen nur dann weiter, wenn keine Übereinstimmung gefunden wird. Die genaue Implementierung der Negation variiert. Bei einem Ansatz unterhält der Knoten eine einfache Zählung für jede WME-Liste, die er von seinem linken Eingang empfängt. Die Anzahl gibt die Anzahl der gefundenen Übereinstimmungen mit WMEs an, die von der rechten Eingabe empfangen wurden. Der Knoten verbreitet nur WME-Listen, deren Zählung null ist. Bei einem anderen Ansatz unterhält der Knoten einen zusätzlichen Speicher auf jeder WME-Liste, die vom linken Eingang empfangen wird. Diese Speicher sind eine Form von Beta-Speicher und speichern WME-Listen für jedes Spiel mit WMEs, die am rechten Eingang empfangen wurden. Wenn eine WME-Liste keine WME-Listen in ihrem Speicher hat, wird sie im Netzwerk verbreitet. Bei diesem Ansatz aktivieren Negationsknoten im Allgemeinen weitere Beta-Knoten direkt, anstatt ihre Ausgabe in einem zusätzlichen Beta-Speicher zu speichern. Negationsknoten bieten eine Form der ' Negation als Fehler '.

Wenn Änderungen am Arbeitsspeicher vorgenommen werden, kann eine WME-Liste, die zuvor keinen WMEs entsprach, jetzt mit neu bestätigten WMEs übereinstimmen. In diesem Fall müssen die verbreitete WME-Liste und alle ihre erweiterten Kopien aus Beta-Speichern weiter unten im Netzwerk zurückgezogen werden. Der oben beschriebene zweite Ansatz wird häufig verwendet, um effiziente Mechanismen zum Entfernen von WME-Listen zu unterstützen. Beim Entfernen von WME-Listen werden alle entsprechenden Produktionsinstanzen deaktiviert und aus der Agenda entfernt.

Existenzielle Quantifizierung kann durch Kombinieren von zwei Negations-Beta-Knoten durchgeführt werden. Dies repräsentiert die Semantik der doppelten Negation (zB "Wenn KEINE übereinstimmenden WMEs, dann..."). Dies ist ein gängiger Ansatz, der von mehreren Produktionssystemen verwendet wird.

Speicherindizierung

Der Rete-Algorithmus schreibt keinen spezifischen Ansatz zur Indexierung des Arbeitsgedächtnisses vor. Die meisten modernen Produktionssysteme bieten jedoch Indizierungsmechanismen. In einigen Fällen werden nur Beta-Speicher indiziert, während in anderen Fällen die Indizierung sowohl für Alpha- als auch für Beta-Speicher verwendet wird. Eine gute Indexierungsstrategie ist ein wichtiger Faktor bei der Entscheidung über die Gesamtleistung eines Produktionssystems, insbesondere bei der Ausführung von Regelsätzen, die zu einem stark kombinatorischen Mustervergleich führen (dh intensiver Einsatz von Beta-Join-Knoten) oder bei einigen Engines bei der Ausführung von Regeln Sets, die während mehrerer Match-Resolve-Act-Zyklen eine signifikante Anzahl von WME-Retraktionen durchführen. Speicher werden oft unter Verwendung von Kombinationen von Hash-Tabellen implementiert, und Hash-Werte werden verwendet, um bedingte Joins für Teilmengen von WME-Listen und WMEs durchzuführen, anstatt für den gesamten Inhalt von Speichern. Dies wiederum reduziert oft die Anzahl der Auswertungen durch das Rete-Netzwerk erheblich.

Entfernung von WMEs und WME-Listen

Wenn eine WME aus dem Arbeitsspeicher gezogen wird, muss sie aus jedem Alpha-Speicher entfernt werden, in dem sie gespeichert ist. Außerdem müssen WME-Listen, die die WME enthalten, aus Beta-Speichern entfernt werden und aktivierte Produktionsinstanzen für diese WME-Listen müssen deaktiviert und aus der Agenda entfernt werden. Es gibt mehrere Implementierungsvarianten, einschließlich baumbasierter und rematch-basierter Entfernung. In einigen Fällen kann eine Speicherindizierung verwendet werden, um das Entfernen zu optimieren.

Umgang mit ODER-Bedingungen

Beim Definieren von Produktionen in einem Regelsatz ist es üblich, die Gruppierung von Bedingungen mit einer ODER- Verknüpfung zuzulassen . In vielen Produktionssystemen wird dies gehandhabt, indem eine einzelne Produktion, die mehrere ODER-verknüpfte Muster enthält, als Äquivalent mehrerer Produktionen interpretiert wird. Das resultierende Rete-Netzwerk enthält Sätze von Endknoten, die zusammen einzelne Produktionen darstellen. Dieser Ansatz verbietet jegliche Form des Kurzschließens der ODER-Bedingungen. Es kann in einigen Fällen auch dazu führen, dass doppelte Produktionsinstanzen auf der Agenda aktiviert werden, wenn dieselbe Gruppe von WMEs mehreren internen Produktionen entspricht. Einige Engines bieten eine Agenda-Deduplizierung, um dieses Problem zu lösen.

Diagramm

Das folgende Diagramm veranschaulicht die grundlegende Rete-Topographie und zeigt die Assoziationen zwischen verschiedenen Knotentypen und Speichern.

Image
Veranschaulicht die grundlegende Rete.
  • Die meisten Implementierungen verwenden Typknoten, um die erste Auswahlebene an n-Tupel-Arbeitsspeicherelementen durchzuführen. Typknoten können als spezialisierte Auswahlknoten betrachtet werden. Sie unterscheiden zwischen verschiedenen Tupelbeziehungstypen.
  • Das Diagramm veranschaulicht nicht die Verwendung spezialisierter Knotentypen wie negierte Konjunktionsknoten. Einige Engines implementieren mehrere verschiedene Knotenspezialisierungen, um die Funktionalität zu erweitern und die Optimierung zu maximieren.
  • Das Diagramm bietet eine logische Ansicht des Rete. Implementierungen können sich in physikalischen Details unterscheiden. Insbesondere zeigt das Diagramm Dummy-Eingaben, die Rechtsaktivierungen am Kopf von Betaknotenzweigen bereitstellen. Maschinen können andere Ansätze implementieren, wie etwa Adapter, die es Alpha-Speichern ermöglichen, direkt Rechteaktivierungen durchzuführen.
  • Das Diagramm zeigt nicht alle Möglichkeiten der Knotenfreigabe.

Eine detailliertere und vollständige Beschreibung des Rete-Algorithmus finden Sie in Kapitel 2 von Production Matching for Large Learning Systems von Robert Doorenbos (siehe Link unten).

Alternativen

Alpha-Netzwerk

Eine mögliche Variation besteht darin, zusätzliche Speicher für jeden Zwischenknoten im Unterscheidungsnetzwerk einzuführen. Dies erhöht den Overhead des Rete, kann jedoch in Situationen, in denen Regeln dynamisch zum Rete hinzugefügt oder daraus entfernt werden, Vorteile haben, wodurch es einfacher wird, die Topologie des Unterscheidungsnetzwerks dynamisch zu variieren.

Eine alternative Implementierung wird von Doorenbos beschrieben. In diesem Fall wird das Unterscheidungsnetzwerk durch einen Satz von Speichern und einen Index ersetzt. Der Index kann unter Verwendung einer Hash-Tabelle implementiert werden . Jeder Speicher enthält WMEs, die einem einzelnen bedingten Muster entsprechen, und der Index wird verwendet, um Speicher anhand ihres Musters zu referenzieren. Dieser Ansatz ist nur praktisch, wenn WMEs Tupel fester Länge darstellen und die Länge jedes Tupels kurz ist (zB 3-Tupel). Darüber hinaus gilt der Ansatz nur für bedingte Muster, die Gleichheitstests gegen konstante Werte durchführen. Wenn eine WME das Rete betritt, wird der Index verwendet, um einen Satz von Speichern zu lokalisieren, deren Bedingungsmuster mit den WME-Attributen übereinstimmt, und die WME wird dann direkt zu jedem dieser Speicher hinzugefügt. An sich enthält diese Implementierung keine 1-Eingangsknoten. Um jedoch Nicht-Gleichheitstests zu implementieren, kann das Rete zusätzliche 1-Eingangsknotennetzwerke enthalten, durch die WMEs geleitet werden, bevor sie in einem Speicher platziert werden. Alternativ können Ungleichheitstests in dem unten beschriebenen Beta-Netzwerk durchgeführt werden.

Beta-Netzwerk

Eine gängige Variante besteht darin, verknüpfte Listen von Token zu erstellen, wobei jedes Token eine einzelne WME enthält. In diesem Fall werden Listen von WMEs für eine teilweise Übereinstimmung durch die verknüpfte Liste von Token dargestellt. Dieser Ansatz ist möglicherweise besser, da er das Kopieren von WME-Listen von einem Token auf ein anderes überflüssig macht. Stattdessen muss ein Beta-Knoten nur einen neuen Token erstellen, um eine WME aufzunehmen, die er mit der Teilübereinstimmungsliste verbinden möchte, und dann den neuen Token mit einem im Eingabe-Beta-Speicher gespeicherten Eltern-Token verknüpfen. Der neue Token bildet nun den Kopf der Token-Liste und wird im Ausgabe-Beta-Speicher abgelegt.

Betaknoten verarbeiten Token. Ein Token ist eine Speichereinheit innerhalb eines Speichers und auch eine Austauscheinheit zwischen Speichern und Knoten. In vielen Implementierungen werden Token innerhalb von Alpha-Speichern eingeführt, wo sie verwendet werden, um einzelne WMEs zu halten. Diese Token werden dann an das Beta-Netzwerk übergeben.

Jeder Beta-Knoten verrichtet seine Arbeit und kann als Ergebnis neue Token erstellen, um eine Liste von WMEs zu enthalten, die eine teilweise Übereinstimmung darstellen. Diese erweiterten Token werden dann in Betaspeichern gespeichert und an nachfolgende Betaknoten weitergegeben. In diesem Fall leiten die Beta-Knoten typischerweise Listen von WMEs durch das Beta-Netzwerk, indem sie vorhandene WME-Listen von jedem empfangenen Token in neue Token kopieren und dann als Ergebnis des Ausführens eines Joins oder einer anderen Aktion weitere WMEs zu den Listen hinzufügen. Die neuen Token werden dann im Ausgabespeicher abgelegt.

Sonstige Überlegungen

Obwohl nicht durch den Rete-Algorithmus definiert, bieten einige Engines erweiterte Funktionen, um eine bessere Kontrolle der Wahrheitspflege zu unterstützen . Wenn beispielsweise eine Übereinstimmung für eine Produktion gefunden wird, kann dies zur Geltendmachung neuer WMEs führen, die wiederum die Bedingungen für eine andere Produktion erfüllen. Wenn eine nachträgliche Änderung des Arbeitsspeichers dazu führt, dass die erste Übereinstimmung ungültig wird, kann dies bedeuten, dass die zweite Übereinstimmung ebenfalls ungültig ist. Der Rete-Algorithmus definiert keinen Mechanismus, um diese logischen Wahrheitsabhängigkeiten automatisch zu definieren und zu handhaben . Einige Engines unterstützen jedoch zusätzliche Funktionen, in denen Wahrheitsabhängigkeiten automatisch gepflegt werden können. In diesem Fall kann das Zurückziehen einer WME zum automatischen Zurückziehen weiterer WMEs führen, um logische Wahrheitsbehauptungen aufrechtzuerhalten.

Der Rete-Algorithmus definiert keinen Begründungsansatz. Begründung bezieht sich auf Mechanismen, die üblicherweise in Experten- und Entscheidungssystemen erforderlich sind, bei denen das System im einfachsten Fall jede der inneren Entscheidungen meldet, die verwendet werden, um zu einer endgültigen Schlussfolgerung zu gelangen. Zum Beispiel könnte ein Expertensystem die Schlussfolgerung, dass ein Tier ein Elefant ist, rechtfertigen, indem es berichtet, dass es groß, grau ist, große Ohren, einen Rüssel und Stoßzähne hat. Einige Engines bieten in Verbindung mit ihrer Implementierung des Rete-Algorithmus eingebaute Rechtfertigungssysteme.

Dieser Artikel bietet keine erschöpfende Beschreibung aller möglichen Variationen oder Erweiterungen des Rete-Algorithmus. Andere Überlegungen und Neuerungen existieren. Zum Beispiel können Engines innerhalb des Rete-Netzwerks spezialisierte Unterstützung bereitstellen, um eine Mustervergleichsregelverarbeitung auf bestimmte Datentypen und Quellen wie programmatische Objekte , XML- Daten oder relationale Datentabellen anzuwenden . Ein weiteres Beispiel betrifft zusätzliche Zeitstempeleinrichtungen, die von vielen Engines für jede WME, die in ein Rete-Netzwerk eintritt, bereitgestellt werden, und die Verwendung dieser Zeitstempel in Verbindung mit Konfliktlösungsstrategien. Engines weisen erhebliche Unterschiede in der Art und Weise auf, wie sie den programmatischen Zugriff auf die Engine und ihren Arbeitsspeicher ermöglichen, und können das grundlegende Rete-Modell erweitern, um Formen der parallelen und verteilten Verarbeitung zu unterstützen.

Optimierung und Leistung

Mehrere Optimierungen für Rete wurden identifiziert und in der wissenschaftlichen Literatur beschrieben. Einige davon gelten jedoch nur in sehr spezifischen Szenarien und haben daher oft keine oder nur geringe Anwendung in einer Regel-Engine für allgemeine Zwecke. Darüber hinaus wurden alternative Algorithmen wie TREAT, entwickelt von Daniel P. Miranker LEAPS, und Design Time Inferencing (DeTI) formuliert, die zusätzliche Leistungsverbesserungen bieten können.

Der Rete-Algorithmus eignet sich für Szenarien, in denen Forward-Chaining und "Inferencing" verwendet werden, um neue Fakten aus bestehenden Fakten zu berechnen oder Fakten zu filtern und zu verwerfen, um zu einer Schlussfolgerung zu gelangen. Es wird auch als ein einigermaßen effizienter Mechanismus zum Durchführen hochkombinatorischer Auswertungen von Fakten genutzt, bei denen eine große Anzahl von Verknüpfungen zwischen Faktentupeln ausgeführt werden muss. Andere Ansätze zur Durchführung einer Regelauswertung, wie die Verwendung von Entscheidungsbäumen oder die Implementierung von sequentiellen Engines, können für einfache Szenarien besser geeignet sein und sollten als mögliche Alternativen in Betracht gezogen werden.

Die Leistung von Rete ist auch weitgehend eine Frage der Implementierungsentscheidungen (unabhängig von der Netzwerktopologie), von denen eine (die Verwendung von Hash-Tabellen) zu großen Verbesserungen führt. Die meisten im Internet verfügbaren Leistungsbenchmarks und -vergleiche sind auf die eine oder andere Weise verzerrt. Um nur eine häufige Voreingenommenheit und eine unfaire Art des Vergleichs zu erwähnen: 1) die Verwendung von Spielzeugproblemen wie den Beispielen Manners und Waltz; solche Beispiele sind nützlich, um spezifische Eigenschaften der Implementierung abzuschätzen, aber sie spiegeln möglicherweise nicht die tatsächliche Leistung bei komplexen Anwendungen wider; 2) die Verwendung einer alten Implementierung; zum Beispiel vergleichen die Referenzen in den folgenden beiden Abschnitten (Rete II und Rete-NT) einige kommerzielle Produkte mit völlig veralteten Versionen von CLIPS und behaupten, dass die kommerziellen Produkte um Größenordnungen schneller sind als CLIPS; dabei wird vergessen, dass CLIPS 6.30 (mit der Einführung von Hash-Tabellen wie in Rete II) um Größenordnungen schneller ist als die für die Vergleiche verwendete Version (CLIPS 6.04).

Varianten

Rete II

In den 1980er Jahren entwickelte Charles Forgy einen Nachfolger des Rete-Algorithmus namens Rete II . Im Gegensatz zum ursprünglichen Rete (das gemeinfrei ist) wurde dieser Algorithmus nicht bekannt gegeben. Rete II behauptet eine bessere Leistung für komplexere Probleme (sogar Größenordnungen) und ist offiziell in CLIPS/R2, einer C/++-Implementierung, und in OPSJ, einer Java-Implementierung von 1998, implementiert Leistungsverbesserung bei komplexeren Problemen, wie die Benchmarks der KnowledgeBased Systems Corporation zeigen.

Rete II kann durch zwei Verbesserungsbereiche charakterisiert werden; spezifische Optimierungen in Bezug auf die allgemeine Leistung des Rete-Netzwerks (einschließlich der Verwendung von Hash-Speichern, um die Leistung bei größeren Datenmengen zu erhöhen) und die Aufnahme eines Rückwärtsverkettungsalgorithmus , der darauf zugeschnitten ist, auf dem Rete-Netzwerk zu laufen. Allein die Rückwärtsverkettung kann die extremsten Veränderungen der Benchmarks in Bezug auf Rete vs. Rete II erklären. Rete II ist im kommerziellen Produktberater von FICO implementiert, früher Fair Isaac . genannt

Jess (zumindest Version 5.0 und höher) fügt dem Rete-Netzwerk auch einen kommerziellen Rückwärtsverkettungsalgorithmus hinzu, aber es kann nicht gesagt werden, dass Rete II vollständig implementiert wird, teilweise aufgrund der Tatsache, dass keine vollständige Spezifikation öffentlich verfügbar ist.

Rete-III

In den frühen 2000er Jahren wurde der Rete III-Motor von Charles Forgy in Zusammenarbeit mit FICO-Ingenieuren entwickelt. Der Rete III-Algorithmus, der nicht Rete-NT ist, ist das FICO-Warenzeichen für Rete II und wird als Teil der FICO Advisor-Engine implementiert. Es ist im Grunde die Rete II-Engine mit einer API, die den Zugriff auf die Advisor-Engine ermöglicht, da die Advisor-Engine auf andere FICO-Produkte zugreifen kann.

Rete-NT

2010 hat Forgy eine neue Generation des Rete-Algorithmus entwickelt. In einem InfoWorld-Benchmark wurde der Algorithmus als 500-mal schneller als der ursprüngliche Rete-Algorithmus und 10-mal schneller als sein Vorgänger Rete II eingestuft. Dieser Algorithmus ist jetzt an Sparkling Logic, dem Unternehmen, zu dem Forgy als Investor und strategischer Berater kam, als Inferenz-Engine des SMARTS-Produkts lizenziert.

ReteOO

Rete unterstützt nur boolesche Logik erster Ordnung .

Siehe auch

Verweise

Externe Links