Self-Supervised Inductive Logic Programming

Die Arbeit stellt Poker vor, ein neues selbstüberwachtes Induktives Logikprogrammierungssystem, das ohne negative Beispiele oder maßgeschneiderte Hintergrundtheorien auskommt, indem es automatisch neue Trainingsbeispiele generiert und eine zweite Ordnung Definite Normal Form (SONF) als allgemeine Hintergrundtheorie verwendet, um rekursive Logikprogramme zu erlernen.

Das Wesentliche

Das große Problem: Der Lehrer, der keine Antworten hat

Stell dir vor, du möchtest jemandem beibringen, wie man ein bestimmtes Rätsel löst. In der klassischen Welt des maschinellen Lernens (genannt Inductive Logic Programming oder ILP) müsstest du normalerweise zwei Dinge tun:

1. Beispiele zeigen: Du gibst dem Schüler ein paar Lösungen (z. B. "Dies ist ein gültiges Wort").
2. Regeln aufstellen: Du musst dem Schüler eine detaillierte Anleitung geben, welche Werkzeuge er benutzen darf (z. B. "Du darfst nur diese Buchstaben verwenden und nur in dieser Reihenfolge").
3. Fehler zeigen: Du musst ihm auch sagen, was falsch ist ("Dies ist kein gültiges Wort").

Das Problem ist: Das ist extrem mühsam. Ein Experte muss Stunden damit verbringen, die Regeln zu schreiben und die falschen Beispiele auszusortieren. Wenn der Experte vergisst, ein wichtiges "falsches" Beispiel zu nennen, lernt der Schüler die falsche Regel und denkt, alles sei erlaubt.

Die Lösung: Poker (das System, nicht das Kartenspiel)

Der Autor, Stassa Patsantzis, hat ein neues System namens Poker entwickelt. Der Name ist eine Anspielung auf den Philosophen Wittgenstein, nicht auf das Kartenspiel.

Poker funktioniert wie ein selbstständiger Detektiv, der nicht auf einen strengen Lehrer angewiesen ist. Hier ist das Konzept mit einer Analogie:

1. Der Anfang: Nur ein paar positive Beispiele

Stell dir vor, du gibst Poker nur drei Beispiele für eine Sprache: "1100", "111000" und "10". Du sagst: "Das sind die richtigen Wörter." Du gibst ihm aber keine Liste von falschen Wörtern.

2. Die Magie: Poker erfindet seine eigenen Fehler

Da Poker keine Liste von "falschen" Wörtern hat, fängt er an, selbst zu raten. Er generiert tausende von neuen Beispielen.

• Er denkt sich Wörter aus wie "111100" (vielleicht falsch?) oder "1010" (vielleicht falsch?).
• Dann testet er seine aktuelle Theorie gegen diese neuen Wörter.

3. Der "Widerspruchs-Test" (Das Herzstück)

Hier kommt die geniale Idee: Poker schaut sich seine eigenen Theorien an.

• Wenn eine Theorie sagt: "Das Wort '111100' ist korrekt", aber eine andere Theorie sagt: "Nein, das ist falsch", dann hat Poker einen Widerspruch.
• Poker nutzt diesen Widerspruch, um zu lernen: "Aha! Wenn ich '111100' als falsch markiere, passt meine Theorie besser zu den ursprünglichen Beispielen."
• Er markiert also selbstständig neue Wörter als "falsch" (negativ), um seine Theorie zu verfeinern.

Die Analogie: Stell dir vor, du versuchst, die Regel für "gerade Zahlen" zu lernen, indem du dir nur die Zahlen 2, 4 und 6 zeigst.

• Ein normaler Schüler denkt vielleicht: "Alle Zahlen, die mit 1 oder 2 beginnen, sind gerade." (Das ist zu allgemein).
• Poker generiert selbst die Zahl "12" und "14". Er merkt: "Moment, wenn ich '12' als gerade akzeptiere, passt das nicht zu meiner Regel für '2'." Also markiert er "12" selbst als falsch und passt seine Regel an. Er lernt durch Selbstkorrektur.

Was ist das Besondere an "Poker"?

1. Kein manueller Regelkatalog nötig: Früher musste ein Mensch eine komplizierte Liste von Regeln (eine "Hintergrundtheorie") schreiben. Poker braucht nur eine sehr allgemeine, fast leere Liste. Er füllt sie selbst auf.
2. Er lernt aus dem Nichts: Er braucht keine negativen Beispiele vom Menschen. Er erstellt sie selbst, indem er seine Theorien testet und Widersprüche findet.
3. Er wird besser, je mehr er raten darf: Je mehr selbstgenerierte Beispiele Poker hat, desto genauer wird er. Es ist wie beim Lernen eines neuen Spiels: Je mehr Runden du selbst spielst (und Fehler machst), desto besser wirst du.

Die Experimente: Von Fraktalen zu Wortspielen

Der Autor hat Poker getestet, indem er ihm beibrachte, zwei Dinge zu lernen:

• Sprachmuster (wie $1^n0^n$): Also Wörter, bei denen die Anzahl der Einsen genau der Anzahl der Nullen entspricht.
• L-Systeme (Fraktale): Das sind Regeln, die komplexe Muster wie Schneeflocken oder Drachenkurven erzeugen (wie in der Natur bei Pflanzen).

Das Ergebnis:

• Poker hat die Muster perfekt gelernt, besonders wenn er viele selbstgenerierte Beispiele hatte.
• Ein anderes, bekanntes System namens Louise (das keine eigenen negativen Beispiele erfinden kann) hat versagt. Es hat sich zu sehr auf die wenigen Beispiele verlassen und dachte, fast alles sei erlaubt (es hat "übergeneralisiert").

Zusammenfassung in einem Satz

Poker ist ein KI-System, das nicht darauf wartet, dass ihm jemand sagt, was falsch ist, sondern das selbstständig durch Ausprobieren und Finden von Widersprüchen lernt, wie die Welt (oder eine Sprache) funktioniert – ganz ohne mühsame manuelle Anleitung.

Es ist wie ein Kind, das nicht nur die Wörter "Hund" und "Katze" lernt, sondern selbst herausfindet, dass ein "Elefant" kein "Hund" ist, indem es die Unterschiede selbst analysiert, anstatt dass ihm jemand eine Liste von "Nicht-Hunden" gibt.

Technische Zusammenfassung

1. Problemstellung

Das Inductive Logic Programming (ILP) und insbesondere das Meta-Interpretive Learning (MIL) sind in der Lage, aus wenigen Beispielen rekursive Logikprogramme mit erfundenen Prädikaten zu lernen, die sich gut auf neue Instanzen verallgemeinern. Derzeitiger Standard setzt jedoch zwei kritische, manuell erstellte Komponenten voraus:

1. Eine problem-spezifische Hintergrundtheorie (Background Theory), die oft von Expertenwissen abhängt.
2. Eine Menge an negativen Beispielen, die sorgfältig ausgewählt werden müssen, um Übergeneralisierung zu vermeiden.

Das Hauptproblem ist, dass diese manuelle Vorbereitung in der Praxis eine enorme Belastung darstellt und die Anwendbarkeit von ILP in realen Szenarien einschränkt, in denen keine negativen Beispiele oder maßgeschneiderte Hintergrundtheorien verfügbar sind. Die Fragestellung lautet: Wie kann ILP lernen, wenn nur positive gelabelte Beispiele, ungelabelte Daten und eine maximale, nicht ziel-spezifische Hintergrundtheorie vorliegen?

2. Methodik: Self-Supervised ILP und das System Poker

Der Autor führt ein neues Setting für Self-Supervised ILP ein und stellt Poker, ein neues MIL-System, vor, das dieses Setting implementiert.

Kernkonzept: Selbstüberwachtes Lernen durch Widerspruchserkennung

Poker lernt aus einer Mischung aus:

• Gelabelten positiven Beispielen ($E^+$).
• Ungelabelten Beispielen ($E^?$).
• Keinen manuell vorgegebenen negativen Beispielen.

Der Algorithmus funktioniert iterativ durch Widerspruchserkennung (Contradiction Detection):

1. Initialisierung: Poker generiert eine Menge $T$ von Hypothesen, die alle gelabelten positiven Beispiele akzeptieren, basierend auf einer sehr allgemeinen Hintergrundtheorie.
2. Generierung: Das System nutzt die aktuellen Hypothesen, um neue Beispiele zu generieren (oder nutzt die vorhandenen ungelabelten Daten).
3. Annahme und Prüfung: Es wird angenommen, dass ein ungelabeltes Beispiel negativ ist. Poker entfernt alle Hypothesen aus $T$, die dieses Beispiel akzeptieren.
4. Widerspruchserkennung: Wenn das Entfernen dieser Hypothesen dazu führt, dass nun auch ein positives Beispiel ($E^+$) abgelehnt wird, liegt ein Widerspruch vor. Dies bedeutet, dass das angenommene „negative" Beispiel eigentlich positiv sein muss.
5. Labeling und Verfeinerung: Das Beispiel wird als positiv neu gelabelt und zu $E^+$ hinzugefügt. Der Prozess wiederholt sich, bis die Hypothesenmenge konsistent mit allen (jetzt gelabelten) positiven Beispielen ist und keine negativen Beispiele mehr akzeptiert.

Hintergrundtheorie: Second-Order Definite Normal Form (SONF)

Ein entscheidender Beitrag ist die Einführung von Second-Order Definite Normal Forms (SONFs). Anstatt eine theorie-spezifische Metaregeln-Menge zu verwenden, nutzt Poker eine maximal allgemeine zweite Ordnung Hintergrundtheorie.

• SONF: Eine Menge von Metaregeln mit Constraints, die ausreichen, um alle Programme einer bestimmten Klasse (z. B. kontextfreie Grammatiken oder L-Systeme) zu lernen.
• Vorteil: Dies eliminiert die Notwendigkeit, die Hintergrundtheorie für jede neue Lernaufgabe manuell anzupassen.
• Beispiele: Das Paper definiert spezifische SONFs für Chomsky-Greibach Normal Form (C-GNF) für kontextfreie Grammatiken und Lindenmayer Normal Form (LNF) für L-Systeme.

3. Wichtige Beiträge

1. Neues Setting: Formalisierung von Self-Supervised ILP (SS-ILP), das ohne negative Beispiele auskommt und ungelabelte Daten nutzt.
2. Algorithmus Poker: Ein neuer MIL-Algorithmus, der automatisch positive und negative Beispiele generiert und labelt, um Übergeneralisierung zu verhindern.
3. SONF-Definition: Einführung und Formalisierung von Second-Order Definite Normal Forms als universelle, zielunabhängige Hintergrundtheorien.
4. Theoretischer Beweis: Ein Beweis (Theorem 1), dass die Wahrscheinlichkeit, eine korrekte Hypothese zu finden, monoton mit der Anzahl der ungelabelten Beispiele steigt.
5. Implementierung: Ein neues Prolog-System namens Poker, das auf dem Top Program Construction (TPC) Algorithmus und dem Meta-Interpreter Vanilla aufbaut.

4. Experimente und Ergebnisse

Die Autoren verglichen Poker mit dem State-of-the-Art MIL-System Louise (basierend auf Vanilla). Die Experimente konzentrierten sich auf das Lernen von Grammatiken für:

• Kontextfreie Sprachen (CFLs): z. B. $a^n b^n$, Palindrome, Parität.
• L-Systeme: Fraktale wie die Dragon Curve, Hilbert Curve, Koch Curve.

Ergebnisse:

• Einfluss automatisch generierter Beispiele: Die Leistung von Poker verbessert sich signifikant mit der Anzahl der automatisch generierten Beispiele ($k$). Sowohl die True Positive Rate (TPR) als auch die True Negative Rate (TNR) steigen, bis sie ihr Maximum erreichen.
• Vermeidung von Übergeneralisierung: Ohne negative Beispiele neigt Louise zu starker Übergeneralisierung (sie lernt oft die trivialste Lösung, die alle Eingaben akzeptiert). Poker vermeidet dies durch die automatische Generierung negativer Beispiele und das iterative Labeling.
• Generative Genauigkeit: Bei L-Systemen (die als Generatoren fungieren) steigt die Genauigkeit von Poker mit mehr generierten Beispielen, während die von Louise sinkt.
• Hypothesengröße: Poker lernt kompaktere Hypothesen, während Louise mit mehr Beispielen tendenziell größere, übergeneralisierte Programme erzeugt.

5. Bedeutung und Ausblick

Das Paper adressiert eine der größten Hürden für den praktischen Einsatz von ILP: die Abhängigkeit von manueller Expertenarbeit für Hintergrundwissen und negative Beispiele.

• Praktische Relevanz: Poker ermöglicht es, komplexe logische Programme (wie Grammatiken) zu lernen, ohne dass ein Experte eine maßgeschneiderte Hintergrundtheorie entwerfen oder negative Beispiele sammeln muss.
• Theoretischer Fortschritt: Die Einführung von SONFs bietet einen prinzipiellen Weg, um allgemeine Hintergrundtheorien für ganze Klassen von Problemen zu definieren, anstatt sie für jedes Problem neu zu erfinden.
• Zukunft: Die Autoren planen, die Anwendung von Poker auf weitere Domänen jenseits der Grammatiklernen zu erweitern und die theoretischen Beweise für verschiedene Mengen an gelabelten/unlabelierten Daten weiter zu verfeinern.

Zusammenfassend stellt Poker einen Paradigmenwechsel dar, der ILP von einem stark manuell gesteuerten Prozess hin zu einem selbstüberwachten, skalierbaren Lernverfahren führt, das die Vorteile von ungelabelten Daten nutzt, um die Generalisierungsfähigkeit zu maximieren.