Wissenskompilierung ist eine Familie von Ansätzen in der künstlichen Intelligenz, die sich mit der rechnerischen Unhandhabbarkeit des Schließens mit propositionalen Modellen befasst. Anstatt Abfragen direkt an einem potenziell komplexen Modell zu beantworten, wird das Modell in einer Offline-Phase in eine kompilierte Repräsentation überführt, die bestimmte Abfragen in polynomieller Zeit unterstützt. Dieser zweistufige Prozess - Kompilierung gefolgt von der Abfragebeantwortung - tauscht anfänglichen Rechenaufwand gegen schnellere, vorhersehbarere Inferenz zur Laufzeit.
Die zentrale Herausforderung liegt in der Wahl einer geeigneten kompilierten Repräsentation, da verschiedene Repräsentationen unterschiedliche Abwägungen bieten. Die drei Haupteigenschaften, die eine kompilierte Repräsentation charakterisieren, sind ihre Kompaktheit (wie prägnant sie das ursprüngliche Modell darstellt), die Menge der Abfragen, die sie in polynomieller Zeit unterstützt, und die Transformationen, die in polynomieller Zeit an ihr durchgeführt werden können. Keine einzelne Repräsentation übertrifft in allen drei Bereichen, daher wählen Praktiker eine Repräsentation basierend auf den Abfragen, die sie beantworten müssen, und den Größenbeschränkungen ihrer Anwendung.
Klassen von Repräsentationen
Kompilierte Repräsentationen fallen in mehrere breite Kategorien. Diagrammklassen umfassen Entscheidungsbäume, geordnete binäre Entscheidungsdiagramme (OBDDs), freie binäre Entscheidungsdiagramme (FBDDs), nicht-deterministische OBDDs und mehrwertige Entscheidungsdiagramme (MDDs). Diese grafischen Strukturen repräsentieren Boolesche Funktionen als gerichtete azyklische Graphen, wobei jeder Pfad einer Belegung von Variablen entspricht.
Formelklassen umfassen disjunktive Normalform (DNF) und konjunktive Normalform (CNF). Während CNF ein gängiges Eingabeformat für viele Denkaufgaben ist, unterstützt sie nicht alle Abfragen effizient, was die Kompilierung in andere Formen motiviert. Schaltkreisklassen umfassen Negationsnormalform (NNF), zerlegbare NNF (DNNF), deterministische DNNF (d-DNNF) und sententielle Entscheidungsdiagramme (SDD). Diese Schaltkreise legen strukturelle Einschränkungen auf, die polynomielle Operationen für bestimmte Abfragen wie Konsistenzprüfung oder Modellzählung ermöglichen.
Wissenskompilierer
Mehrere Softwarewerkzeuge wurden entwickelt, um Wissenskompilierung automatisch durchzuführen. Der c2d-Compiler unterstützt die Kompilierung zu d-DNNF, einer Repräsentation, die polynomielle Modellzählung und Konsistenzprüfung ermöglicht. Der d4-Compiler zielt ebenfalls auf d-DNNF ab und ist für seine Effizienz bei großen Instanzen bekannt. miniC2D kompiliert zu SDD, einer neueren Repräsentation, die eine breitere Palette von Abfragen und Transformationen unterstützt. KCBox unterstützt die Kompilierung zu OBDD, OBDD[AND] und CCDD und bietet Flexibilität über verschiedene Diagrammklassen hinweg.
Diese Kompilierer werden in Anwendungen wie probabilistischem Denken, Planung und Konfigurationsmanagement eingesetzt, wo wiederholte Abfragebeantwortung erforderlich ist. Durch die einmalige Kompilierung eines Modells können Systeme viele Abfragen schnell beantworten, was in Echtzeit- oder interaktiven Umgebungen entscheidend ist.
Abwägungen und Auswahlkriterien
Die Wahl einer kompilierten Repräsentation hängt von den spezifischen Anforderungen der Anwendung ab. Beispielsweise sind OBDDs für viele praktische Funktionen kompakt und unterstützen polynomielle Äquivalenzprüfung, können aber für einige Funktionen exponentiell aufblähen. DNNF und d-DNNF sind im Allgemeinen prägnanter, unterstützen jedoch weniger Abfragen. SDD bietet einen Mittelweg, unterstützt sowohl Modellzählung als auch Konditionierung in polynomieller Zeit und behält strukturelle Eigenschaften bei, die die Kompilierung erleichtern.
Transformationen sind ebenfalls wichtig. Einige Anwendungen erfordern die Modifikation der kompilierten Repräsentation, wie Konditionierung auf Evidenz oder Verknüpfung mit zusätzlichen Einschränkungen. Repräsentationen, die diese Transformationen in polynomieller Zeit unterstützen, werden in dynamischen Umgebungen bevorzugt, auch wenn sie weniger kompakt sind als Alternativen.
Beziehung zum maschinellen Lernen
Wissenskompilierung ist konzeptionell verschieden von maschinellem Lernen und tiefem Lernen, die sich auf das Lernen von Mustern aus Daten konzentrieren, anstatt logische Modelle zu transformieren. Kompilierte Repräsentationen wurden jedoch als eine Möglichkeit untersucht, gelernte Modelle interpretierbarer zu machen oder symbolisches Denken mit neuronalen Ansätzen zu integrieren. Beispielsweise können Entscheidungsdiagramme verwendet werden, um die Entscheidungsgrenzen eines trainierten neuronalen Netzes in einer Form darzustellen, die formale Verifikation unterstützt.
Neuere Arbeiten haben auch Verbindungen zum Denken mit großen Sprachmodellen untersucht, wo kompilierte Wissensbasen strukturiertes Hintergrundwissen zur Ergänzung generativer Modelle bereitstellen könnten. Obwohl diese Bemühungen noch in den Anfängen stecken, unterstreichen sie die anhaltende Relevanz der Wissenskompilierung als Werkzeug zur Überbrückung von symbolischer und subsymbolischer KI.
Aktuelle Richtungen
Die Forschung in der Wissenskompilierung konzentriert sich weiterhin auf die Entwicklung neuer Repräsentationsklassen mit besseren Abwägungen, die Verbesserung der Skalierbarkeit von Kompilierern und die Erweiterung der Kompilierung auf reichere logische Sprachen jenseits der propositionalen Logik. Es gibt auch Interesse daran, kompilierte Repräsentationen direkt aus Daten zu lernen, was die Grenze zwischen Kompilierung und maschinellem Lernen verwischen würde. Da KI-Systeme komplexer werden, bleibt die Fähigkeit, effizient über strukturiertes Wissen zu schließen, eine kritische Herausforderung, und Wissenskompilierung bietet einen prinzipiellen Rahmen, um diese zu adressieren.
Referenzen
- Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229-264.
- Huang, J., & Darwiche, A. (2007). On compiling system models to faster SAT solvers. In Proceedings of the National Conference on Artificial Intelligence.
- Muise, C., McIlraith, S., Beck, J. C., & Hsu, E. (2012). Dsharp: Fast d-DNNF compilation with sharpSAT. In Canadian Conference on Artificial Intelligence.