Self-Supervised Inductive Logic Programming

Dit paper introduceert Poker, een nieuw zelftoezichtend ILP-systeem dat zonder vooraf gedefinieerde achtergrondtheorie of negatieve voorbeelden recursieve logica-programma's kan leren door automatisch nieuwe voorbeelden te genereren en te labelen, wat leidt tot betere generalisatie dan bestaande systemen zoals Louise.

De kern

De Kern: Een Taalleraar zonder Antwoordenboek

Stel je voor dat je een kind wilt leren een nieuwe taal spreken. In de traditionele manier van leren (wat onderzoekers "Inductive Logic Programming" of ILP noemen), moet je als leraar twee dingen doen:

1. Een woordenboek en grammatica-regels geven: Je vertelt het kind welke woorden er bestaan en hoe ze aan elkaar geplakt kunnen worden.
2. Oefeningen met antwoorden geven: Je geeft het kind zinnen die wel kloppen (positieve voorbeelden) en zinnen die niet kloppen (negatieve voorbeelden), zodat het kind leert wat fout is.

Het probleem is dat dit veel werk voor de leraar is. Je moet voor elk nieuw onderwerp een heel specifiek woordenboek maken en zelf bedenken welke zinnen fout zijn. Als je dit vergeet, leert het kind misschien dat "alle woorden in de wereld" een geldige zin zijn, en dat is niet wat je wilt.

De Oplossing: Poker (De Slimme Leraar)

De auteur, Stassa Patsantzis, introduceert een nieuw systeem genaamd Poker. Poker is een "zelflerende" AI die het werk van de leraar overneemt.

Hoe werkt Poker?
Stel je voor dat Poker een detective is die een geheim codeboek probeert te kraken.

1. De Start: Poker krijgt een paar voorbeelden van zinnen die wel kloppen (bijvoorbeeld: "1100" is goed). Maar het krijgt geen lijst met foutieve zinnen en het heeft geen specifiek woordenboek. Het heeft alleen een heel algemeen idee van wat een woord is (bijvoorbeeld: "1" en "0" bestaan).
2. Het Gokspel (De Naam): De naam "Poker" is een knipoog naar de filosoof Wittgenstein en zijn "pokerface", maar ook naar het spel. Poker moet gissen. Het maakt een hypothese (een gok) over hoe de taal werkt.
3. Het Zelf-creëren van Voorbeelden: Omdat Poker geen lijst met fouten heeft, verzonnt het die zelf.
   • Het denkt: "Oké, als mijn theorie klopt, dan zou '111000' ook moeten werken."
   • Het probeert die zin te maken. Als het lukt, maar de zin eigenlijk niet in de echte taal hoort, dan heeft Poker een probleem.
   • Poker kijkt dan: "Wacht, mijn theorie zegt dat dit goed is, maar mijn andere theorieën zeggen dat dit fout is." Hierdoor ontdekt het een tegenstrijdigheid.
4. Het Leren van Fouten: Door deze tegenstrijdigheden te vinden, kan Poker zichzelf zeggen: "Ah, deze zin is eigenlijk fout!" en het voegt die toe aan zijn lijst van fouten. Zo leert het langzaam wat niet mag, zonder dat een mens het ooit heeft verteld.

De Magische Regel: De "Alles-dekkende" Grammatica

Een ander groot probleem bij AI is dat je vaak een heel specifiek boekje nodig hebt voor elke taak. Poker gebruikt echter een SONF (Second Order Definite Normal Form).

• De Metafoor: Stel je voor dat je een sleutel hebt die niet voor één deur is gemaakt, maar voor elke deur in het hele huis.
• In plaats van dat jij voor elke nieuwe taal een nieuw woordenboek moet schrijven, geeft Poker een universeel, heel algemeen raamwerk. Dit raamwerk is zo breed dat het elke mogelijke grammatica kan bevatten.
• Omdat dit raamwerk zo breed is, zou je denken dat de AI alles goed zou vinden. Maar dankzij het zelf-creëren van fouten (zoals hierboven beschreven), weet Poker precies welke deuren niet open gaan, en leert het de specifieke taal.

Wat hebben ze bewezen?

De auteurs hebben Poker getest op twee dingen:

1. Fractals (L-systemen): Denk aan de takken van een boom of een sneeuwvlok. Poker leerde hoe je deze patronen moet tekenen door alleen positieve voorbeelden te zien en zelf fouten te bedenken.
2. Talen (Context-Free Grammars): Denk aan het patroon van evenveel enen als nullen (zoals 1100 of 111000).

Het resultaat:

• Poker werd steeds slimmer naarmate het meer voorbeelden (zowel de gegeven als de zelfbedachte) kreeg. Het leerde de juiste regels.
• Louise (een bestaand, geavanceerd systeem) faalde. Omdat Louise geen negatieve voorbeelden kreeg en die ook niet zelf kon bedenken, werd het te vrijblijvend. Het dacht dat alles goed was (over-generalisatie) en leerde geen specifieke regels.

Samenvatting in één zin

Poker is een slimme AI die, net als een detective, niet wacht op een lijst met fouten, maar zelf "misdaadplekken" bedenkt om zo de regels van een taal of patroon te leren, zonder dat een mens daarvoor een specifiek handboek hoeft te schrijven.

Dit maakt het veel makkelijker om AI toe te passen op nieuwe, complexe problemen waar we nog geen antwoordenboekje voor hebben.

Technische samenvatting

Titel: Self-Supervised Inductive Logic Programming

Auteur: Stassa Patsantzis (German University of Digital Sciences)

---

1. Het Probleem

Inductieve Logische Programmering (ILP), en specifiek Meta-Interpretive Learning (MIL), staat bekend om het kunnen leren van recursieve logische programma's met uitvindingen van predicaten (predicate invention) uit slechts een paar voorbeelden. Traditionele ILP-systemen vereisen echter drie kritieke, handmatig samengestelde componenten:

1. Een achtergrondtheorie ($B$): Vaak specifiek toegespitst op het leerprobleem.
2. Positieve voorbeelden ($E^+$): Gelabelde data.
3. Negatieve voorbeelden ($E^-$): Cruciaal om overgeneralisatie te voorkomen.

De afhankelijkheid van experts om deze componenten handmatig te selecteren en te programmeren vormt een grote barrière voor de toepassing van ILP in de praktijk. Zonder negatieve voorbeelden neigen systemen ertoe om te overgeneraliseren (bijvoorbeeld het leren van een taal die alle mogelijke strings accepteert in plaats van de specifieke doeltaal). De vraag die dit artikel beantwoordt is: Hoe kunnen we ILP toepassen zonder negatieve voorbeelden en zonder een doel-specifieke achtergrondtheorie?

2. Methodologie: Poker en Self-Supervised ILP

De auteur introduceert een nieuw kader: Self-Supervised ILP (SS-ILP). Het centrale algoritme, geïmplementeerd in het nieuwe MIL-systeem Poker, lost het probleem op door tijdens het leerproces automatisch nieuwe voorbeelden te genereren en te labelen.

Kernconcepten:

• Invoer: Het systeem krijgt alleen gelabelde positieve voorbeelden ($E^+$), ongelabelde voorbeelden ($E?$), en een maximaal algemene achtergrondtheorie ($T = B \cup M$). Er zijn geen negatieve voorbeelden gegeven.
• Second-Order Definite Normal Form (SONF): In plaats van een doel-specifieke achtergrondtheorie, gebruikt Poker een SONF. Dit is een verzameling van metaregels (metarules) met beperkingen (constraints) die voldoende algemeen is om alle programma's binnen een bepaalde klasse (bijv. Context-Free Grammars of L-Systemen) te kunnen leren. Dit elimineert de noodzaak voor handmatige aanpassing per taak.
• Het Leerproces (Detectie van Contradicties):
  1. Initialisatie: Poker bouwt een verzameling $T$ van initiële hypothesen die alle gelabelde positieve voorbeelden accepteren.
  2. Generatie: Het systeem voert de huidige hypothesen uit als generatoren om nieuwe, ongelabelde voorbeelden te creëren.
  3. Labeling & Contradictie-detectie: Poker veronderstelt dat een nieuw gegenereerd voorbeeld $e$ negatief is. Het verwijdert vervolgens alle hypothesen uit $T$ die $e$ accepteren.
     • Als de resterende hypothesen $T'$ geen van de oorspronkelijke positieve voorbeelden meer accepteren, is er een contradictie. Dit betekent dat $e$ eigenlijk een positief voorbeeld was. $e$ wordt dan verplaatst naar $E^+$ en de hypothesen die $e$ accepteren worden hersteld.
     • Als $T'$ nog steeds positieve voorbeelden accepteert, wordt $e$ bevestigd als negatief en worden de hypothesen die $e$ accepteren permanent verwijderd.
  4. Iteratie: Dit proces herhaalt zich totdat een consistente hypothese is gevonden die alle positieve voorbeelden accepteert en geen enkele (nu gelabelde) negatieve voorbeelden.

3. Belangrijkste Bijdragen

• Nieuw Kader (SS-ILP): Een formeel kader voor ILP dat werkt zonder negatieve voorbeelden en met een niet-doel-specifieke achtergrondtheorie.
• Het Poker-algoritme: Een nieuw MIL-algoritme dat zelf-supervised leert door automatisch positieve en negatieve voorbeelden te genereren en te labelen via contradictiedetectie.
• Second-Order Definite Normal Forms (SONFs): Een nieuwe definitie van achtergrondtheorieën die voldoende algemeen zijn om een hele klasse van programma's te dekken. De auteur presenteert twee specifieke SONFs:
  • C-GNF (Chomsky-Greibach): Voor het leren van Context-Free Grammars (CFG).
  • LNF (Lindenmayer Normal Form): Voor het leren van L-System grammars.
• Theoretisch Bewijs: Een bewijs dat de nauwkeurigheid van Poker monotoon toeneemt naarmate het aantal ongelabelde (en automatisch gegenereerde) voorbeelden toeneemt.
• Implementatie: Een Prolog-implementatie van Poker die uitbreidt op bestaande TPC (Top Program Construction) algoritmen.

4. Resultaten

De auteurs hebben Poker vergeleken met de state-of-the-art MIL-systeem Louise (die geen negatieve voorbeelden kan genereren) in experimenten met:

1. L-Systemen: (Fractals zoals de Dragon Curve en Hilbert Curve).
2. Context-Free Languages (CFL): (Binaire talen zoals palindromen, even pariteit, en $a^n b^n$).

Vindingen:

• Poker: De prestaties (True Positive Rate en True Negative Rate voor CFL; Generative Accuracy voor L-Systemen) verbeteren significant naarmate het aantal automatisch gegenereerde voorbeelden ($k$) toeneemt. Poker leert correcte hypothesen en labelt onbekende voorbeelden nauwkeurig.
• Louise: Zonder de mogelijkheid om negatieve voorbeelden te genereren, overgeneraliseert Louise consistent. De hypothesen worden groter en accepteren te veel strings, wat leidt tot een daling in de generatieve nauwkeurigheid bij L-Systemen.
• Conclusie: De automatisering van het genereren van negatieve voorbeelden is essentieel om overgeneralisatie te voorkomen wanneer geen handmatige negatieve voorbeelden beschikbaar zijn.

5. Betekenis en Toekomstperspectief

Dit werk is significant omdat het een van de eerste stappen is om de "last" van handmatige kennisengineering in ILP te verlichten.

• Toepasbaarheid: Het maakt ILP toepasbaar op domeinen waar negatieve voorbeelden moeilijk te definiëren zijn of waar de achtergrondtheorie niet vooraf bekend is.
• Generaliteit: Door SONFs te gebruiken, hoeft de gebruiker niet langer een theorie te schrijven die specifiek is voor één taak; één algemene theorie kan worden hergebruikt voor een hele klasse van problemen.
• Toekomst: De auteurs plannen om de theorie uit te breiden naar andere domeinen dan grammatica-leren en de computationele efficiëntie verder te optimaliseren.

Samenvattend introduceert Poker een paradigmaverschuiving in ILP: van een afhankelijkheid van handmatig geselecteerde negatieve voorbeelden naar een zelf-supervised aanpak die het leerproces dynamisch verrijkt met gegenereerde data, waardoor robuuste en generaliseerbare logische programma's kunnen worden geleerd.