Hybrid MKNF with Classical Negation in the Rule Component

Stellen Sie sich vor, Sie versuchen, einen superintelligenten Roboter zu bauen, der die Welt versteht. Um dies zu erreichen, müssen Sie ihm zwei sehr unterschiedliche Arten des Denkens beibringen. Die erste Art ist wie ein strenger Bibliothekar, der jeden Fakt in einer riesigen Enzyklopädie kennt; wenn im Buch nicht steht, dass ein Drache existiert, geht der Bibliothekar davon aus, dass er nicht existiert, aber er ist vorsichtig, nur das zu sagen, was explizit geschrieben steht. Die zweite Art ist wie ein Detektiv, der Geheimnisse löst, indem er nach Hinweisen sucht; wenn der Detektiv keine Beweise für einen Verdächtigen findet, nimmt er vielleicht an, dass der Verdächtige unschuldig ist, aber nur bis neue Beweise auftauchen.

Jahrelang haben Wissenschaftler versucht, diese beiden Denker in einem Gehirn zu vereinen. Dieses Feld wird als „Wissensrepräsentation“ bezeichnet und ist das Rückgrat, mit dem Computer über komplexe Dinge schlussfolgern, von medizinischen Diagnosen bis hin zu selbstfahrenden Autos. Die spezifische Methode, die dieses Paper betrachtet, heißt „Hybrid MKNF“. Betrachten Sie dies als eine Ehe zwischen der Enzyklopädie des Bibliothekars (genannt Description Logics) und dem Regelbuch des Detektivs (genannt Logic Programming). Das Ziel ist es, dem Computer zu ermöglichen, das Regelbuch zu nutzen, um die Struktur der Welt durch die Enzyklopädie zu verstehen, während er das Regelbuch nutzt, um wechselnde Situationen wie Verkehr oder Wetter zu handhaben. Es gibt jedoch einen Haken: Das Regelbuch des Detektivs hat einen blinden Fleck. Es kann sagen: „Ich weiß nicht, ob es regnet“ (weil es keinen Bericht gibt), aber es hat Schwierigkeiten zu sagen: „Ich weiß mit Sicherheit, dass es nicht regnet“ (weil ein Bericht vorliegt, dass der Himmel klar ist). Dies ist ein großes Problem für sicherheitskritische Systeme, wie etwa Flughafenlandebahnen, wo das Wissen darüber, dass etwas definitiv nicht defekt ist, genauso wichtig ist wie das Wissen, dass es defekt ist.

Dieses Paper führt ein Upgrade für dieses Detektiv-Regelbuch ein, das es ermöglicht, „klassische Negation“ zu handhaben – die Fähigkeit, explizit zu erklären, dass etwas falsch ist, anstatt nur anzunehmen, dass es falsch ist, weil Informationen fehlen. Die Autoren Sheela, Rey und De Grancey schlagen ein neues System namens hMKNF¬ vor. Sie haben diese Idee nicht nur vorgeschlagen; sie haben einen vollständigen mathematischen Rahmen geschaffen, um zu beweisen, dass sie funktioniert. Sie zeigten, wie man die Regeln für dieses neue System definiert, und entwickelten ein schrittweises Rezept (einen Algorithmus), damit der Computer die „beste“ Antwort findet, bekannt als das „well-founded model“. Sie bewiesen, dass diese neue Methode jede Mischung aus Fakten und Regeln handhaben kann, selbst wenn diese knifflig werden, und sie lieferten einen Weg, die Antwort in drei distinkten Phasen zu berechnen, um sicherzustellen, dass der Roboter niemals durch fehlende Informationen oder widersprüchliche Hinweise verwirrt wird.

Die neue Superkraft des Detektivs

Stellen Sie sich vor, Sie leiten einen geschäftigen Flughafen. Sie haben eine riesige Datenbank (die „Ontologie“), die jede Landebahn, jeden Flughafen und jedes Flugzeug auflistet. Diese Datenbank ist der „Bibliothekar“. Sie weiß, dass Landebahn 4 zum Flughafen X gehört. Aber die Datenbank weiß nichts über das aktuelle Wetter. Hier kommt der „Detektiv“ ins Spiel. Der Detektiv nutzt einen Satz von Regeln, um zu entscheiden, ob eine Landebahn sicher zu nutzen ist.

Im alten System sah die Regel des Detektivs für eine sichere Landebahn so aus: „Wenn die Landebahn an einem Flughafen liegt, und wir nicht wissen, dass sie geschlossen ist, und wir nicht wissen, dass ein Hindernis vorhanden ist, dann ist die Landebahn offen.“

Hier liegt das Problem: Was ist, wenn der Wetterbericht verspätet eintrifft? Der Detektiv weiß nicht, ob ein Hindernis vorhanden ist. Im alten System, weil der Detektiv keinen Bericht über ein Hindernis finden kann, nimmt er vielleicht an, dass keines vorhanden ist, und sagt: „Landebahn ist offen!“ Aber was ist, wenn sich ein riesiger Felsbrocken auf der Landebahn befindet und der Bericht einfach noch nicht eingetroffen ist? Das alte System würde einen gefährlichen Fehler machen, weil es „fehlende Information“ als „Beweis für Abwesenheit“ behandelt.

Das Paper argumentt, dass wir in sicherheitskritischen Situationen brauchen, dass der Detektiv in der Lage ist zu sagen: „Ich habe überprüft, und ich weiß, dass es kein Hindernis gibt.“ Dies wird „klassische Negation“ genannt. Es ist der Unterschied zwischen zu sagen „Ich habe kein Gespenst gesehen“ und zu sagen „Ich habe verifiziert, dass es keine Gespenster gibt“.

Der dreiphasige Detektiv-Workflow

Die Autoren erkannten, dass das Hinzufügen dieser Kraft des „Wissens, dass etwas falsch ist“, die Mathematik viel schwieriger macht. Man kann die Antwort nicht einfach erraten; man muss sicher sein. Deshalb entwarfen sie einen dreiphasigen Prozess, um diese Rätsel zu lösen, vergleichbar mit einem Detektiv, der einen Fall mit zunehmender Gründlichkeit bearbeitet.

Phase 1: Der schnelle Scan (Fixpunkt-Berechnung)
Zuerst führt das System einen schnellen, automatischen Scan durch. Es betrachtet alle Regeln und Fakten und fragt: „Was können wir gerade sicher beweisen?“ Es erstellt eine Liste von Dingen, die definitiv wahr sind, und Dingen, die definitiv falsch sind. Wenn das Rätsel einfach ist, löst diese Phase es sofort. Das System verwendet einen „well-founded operator“, was wie eine Maschine ist, die ständig neue Fakten hinzufügt, bis sie keine weiteren mehr hinzufügen kann. Wenn die Maschine stoppt und die Antwort Sinn ergibt, sind wir fertig!

Phase 2: Die Logikkette (Unit Propagation)
Manchmal bleibt der schnelle Scan stecken. Er findet eine Regel, die besagt: „Wenn A wahr ist, dann ist B falsch“, aber er weiß noch nicht, ob A wahr ist. Er könnte jedoch wissen, dass es eine Regel verletzen würde, wenn A wahr wäre. Also erzwingt das System eine Entscheidung. Es sagt: „Okay, wenn A wahr wäre, würde dies zu einem Widerspruch führen, also muss A falsch sein.“ Dies nennt man „Unit Propagation“. Es ist wie ein Detektiv, der erkennt: „Wenn der Butler es war, wäre die Uhr kaputt. Die Uhr ist nicht kaputt, also war es nicht der Butler.“ Diese Phase zwingt das System zu logischen Deduktionen, die die erste Phase übersehen hat.

Phase 3: Das Raten und Prüfen (Die letzte Instanz)
Manchmal ist das System selbst nach dem schnellen Scan und der Logikkette noch immer festgefahren. Es gibt zu viele Möglichkeiten und die Regeln sind zu komplex verschlungen. Hier geben die Autoren zu, dass man manchmal einfach raten muss. Sie schlagen eine „Guess-and-Check“-Phase vor. Das System probiert alle möglichen Kombinationen von „Wahr“ und „Falsch“ für die verbleibenden Unbekannten aus. Es prüft jede Vermutung darauf, ob sie eine stabile, konsistente Geschichte ergibt. Wenn es eine Geschichte findet, die funktioniert und die „sicherste“ ist (das heißt, die am wenigsten undefinierte Elemente hinterlässt), dann ist das die Antwort. Das Paper stellt fest, dass diese Phase die rechenintensivste ist – es ist, als würde man jeden Schlüssel an einem riesigen Schlüsselbund ausprobieren – aber sie ist notwendig, um sicherzustellen, dass das System niemals eine gültige Lösung übersieht.

Warum das wichtig ist

Die Autoren haben nicht nur ein neues Spiel erfunden; sie haben einen strengen mathematischen Beweis erbracht, dass ihr System funktioniert. Sie haben gezeigt, dass ihre Methode, hMKNF¬, jede Mischung aus Fakten und Regeln handhaben kann, selbst die chaotischen, bei denen sich Dinge widersprechen könnten. Sie haben bewiesen, dass ihr dreiphasiger Prozess immer das „well-founded model“ finden wird – die zuverlässigste und risikoärmste Antwort, die möglich ist.

Sie haben ihr Verfahren auch mit früheren Versuchen verglichen. Ältere Methoden konnten nur einfache Fälle handhaben oder erforderten, dass die Regeln sehr spezifisch waren (wie zum Beispiel nur mit einzelnen Objekten zu arbeiten, statt mit komplexen Gruppen). Ihre neue Methode ist flexibler und leistungsfähiger. Sie sind jedoch ehrlich über den Kompromiss: Da sie diese zusätzliche Kraft (klassische Negation) zulassen, kann die „Guess-and-Check“-Phase bei sehr komplexen Problemen lange dauern. Aber für sicherheitskritische Anwendungen, wie etwa die Sicherstellung, dass ein Flugzeug nicht von einer blockierten Landebahn abhebt, ist der Preis, etwas länger zu brauchen, um zu 100 % sicher zu sein, ein absolut lohnenswerter.

Kurz gesagt gibt dieses Paper Computern eine neue Superkraft: die Fähigkeit, explizit zu wissen, was nicht wahr ist, und nicht nur zu wissen, was fehlt. Durch die Kombination eines schnellen Scans, einer Logikkette und eines sorgfältigen Ratens und Prüfens haben sie ein System gebaut, das mit weitaus größerer Präzision und Sicherheit über die Welt schlussfolgern kann.