Constraint Learning for Non-confluent Proof Search

Dit paper introduceert een methode voor het leren van constraints in de klassieke eerste-orde connectie-calculus om de excessieve terugkoppeling bij niet-confluente bewijszoekprocessen te verminderen zonder de volledigheid te verliezen.

De kern

De Kunst van het Niet vastlopen: Slimmer Zoeken in de Wiskunde

Stel je voor dat je een gigantisch, donker labyrint moet doorkruisen om een schat te vinden (in dit geval: het bewijzen van een wiskundig theorema). Je hebt een kaart (een wiskundige regel) die je vertelt welke paden je mag nemen.

Het Probleem: De "Dode Hoek"

In sommige soorten labyrinten (die in de paper "niet-confluente" calculi worden genoemd) loop je vaak vast. Je denkt: "Ik ga hierheen," maar na een paar stappen merk je dat je in een doodlopende straat zit.

• De oude manier: Je loopt terug naar de laatste kruising, probeert een ander pad, en loopt weer vast. Je doet dit keer op keer. Dit noemen we teruglopen (backtracking).
• Het probleem: Soms loop je vast om precies dezelfde reden als de vorige keer. Je loopt dus terug, probeert iets anders, en landt weer in dezelfde valkuil. Je verspillt enorm veel tijd aan het herhalen van fouten.

De Oplossing: "Leren van je Fouten"

De auteurs van dit paper (Michael Rawson, Clemens Eisenhofer en Laura Kovács) hebben een slimme truc bedacht, gebaseerd op een idee uit de computerwetenschap dat Constraint Learning (beperkingsleren) heet.

Stel je voor dat je een reisinstructeur hebt die bijhoudt waar je bent geweest.

1. Je loopt vast in een doodlopende straat.
2. In plaats van alleen maar terug te lopen, vraagt de instructeur: "Waarom zaten we hier vast?"
3. Hij analyseert de situatie en zegt: "Ah, we zaten vast omdat we bij kruising A linksaf zijn gegaan én bij kruising B rechtsaf. Als we die twee combinaties ooit weer proberen, lopen we gegarandeerd vast."
4. Hij schrijft dit op in een zwartboek (de "constraint database").
5. De volgende keer dat je bij kruising A linksaf gaat, kijkt hij in het zwartboek en zegt: "Nee, wacht! Als je dan bij B rechtsaf gaat, lopen we vast. Probeer iets anders."

Dit voorkomt dat je in dezelfde valkuil valt. Je "leert" van je eerdere mislukkingen.

Hoe werkt dit in de wiskunde?

In de wiskundige wereld van dit paper gebruiken ze een methode genaamd Connection Tableaux.

• De zoektocht: Ze bouwen een boom van mogelijke bewijzen.
• De blokkade: Soms kan een stap niet worden gezet omdat eerdere keuzes (zoals het toewijzen van een variabele aan een specifiek getal) de weg blokkeren.
• De leer-methode: Als de computer vastloopt, analyseert hij welke eerdere stappen de blokkade veroorzaakten. Hij maakt een nieuwe regel: "Je mag nooit deze specifieke combinatie van stappen doen." Deze regel wordt toegevoegd aan de lijst met verboden combinaties.

Waarom is dit zo belangrijk?

Zonder deze truc zou de computer urenlang rondrennen in dezelfde cirkels, net als een muis in een molenwiel die steeds dezelfde muur aan het rennen is. Met deze truc:

• Minder teruglopen: De computer hoeft minder vaak zijn stappen ongedaan te maken.
• Sneller resultaat: Omdat hij niet in dezelfde valkuilen valt, komt hij sneller bij het echte antwoord (of merkt hij sneller op dat er geen oplossing is).
• Volledigheid: Belangrijk detail: ze hebben een manier gevonden om dit te doen zonder de zekerheid te verliezen dat ze alle mogelijke oplossingen vinden. Ze zijn niet "slordig" (zoals sommige snellere methoden die soms fouten maken), maar ze zijn wel veel slimmer.

De Vergelijking met een Puzzel

Stel je voor dat je een enorme Legpuzzel probeert te maken.

• Oude methode: Je probeert stukje A in vakje B. Het past niet. Je haalt het eruit, probeert stukje C in vakje B. Past ook niet. Je haalt het eruit... Je probeert dit duizenden keren.
• Nieuwe methode (Constraint Learning): Zodra je merkt dat stukje A niet in vakje B past als stukje D al in vakje E zit, schrijf je op: "Stukje A past nooit in vakje B als D in E zit." De volgende keer dat je D in E legt, weet je direct: "Ah, dan kan ik A niet in B proberen." Je slaat duizenden pogingen over.

Conclusie

Deze paper introduceert een manier om wiskundige bewijsmachines "slimmer" te maken door ze te laten leren van hun eigen vastlopers. Het is alsof je een GPS hebt die niet alleen de route aangeeft, maar ook onthoudt waar je eerder vastliep, zodat je die routes in de toekomst direct kunt vermijden. Dit maakt het oplossen van complexe wiskundige problemen veel efficiënter, zonder de nauwkeurigheid te verliezen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Constraint Learning for Non-Confluent Proof Search" in het Nederlands.

Probleemstelling

Het artikel adresseert het probleem van excessieve backtracking (terugzoeken) bij het zoeken naar bewijzen in niet-confluent tableau-calculi, zoals de connection tableau calculus.

• Niet-confluëntie: In tegenstelling tot confluent systemen (waar de volgorde van keuzes geen invloed heeft op de eindresultaten), kunnen bij niet-confluent systemen eerdere keuzes leiden tot een "dode hoek" (stuck state). Als een tak van het tableau niet gesloten kan worden vanwege een eerdere substitutie of keuze, moet de zoektocht terugkeren (backtracken) en een alternatieve route proberen.
• Inefficiëntie: Traditionele methoden om dit te beperken, zoals het gebruik van "cuts" (zoals in leanCoP), zijn vaak onvolledig (missen geldige bewijzen) of leiden tot pathologisch veel backtracking. Het probleem is dat de zoekmachine vaak dezelfde doelen opnieuw probeert te sluiten, terwijl de onderliggende oorzaak van de mislukking (bijvoorbeeld een variabelebinding) niet is veranderd.
• Doel: De auteurs willen de backtracking verminderen zonder de volledigheid van het bewijssysteem te verliezen.

Methodologie

De auteurs passen een techniek over uit het domein van constraint satisfaction (te weten Constraint Learning of Clause Learning), zoals gebruikt in moderne SAT- en SMT-oplossers, toe op de connection tableau calculus.

1. Constraint Learning Mechanisme:

   • Tijdens het zoeken naar een gesloten tableau komt de zoektocht soms vast te zitten (stuck).
   • In plaats van simpelweg terug te springen, analyseert het systeem waarom er geen verdere inferenties mogelijk zijn.
   • Het systeem leert een constraint (beperking) die de combinatie van eerdere beslissingen (inference steps) vastlegt die hebben geleid tot deze dode hoek.
   • Deze constraint wordt toegevoegd aan een database en voorkomt dat de zoektocht later opnieuw dezelfde fout maakt.

2. Zoekalgoritme (Algorithm 1):

   • Het algoritme onderhoudt een "trail" van waarheidswaarden (inference steps) en een set van geleerde constraints.
   • Als een inferentie niet kan worden toegepast (of leidt tot een conflict met een geleerde constraint), wordt een reden (reason) berekend.
   • Bij een conflict wordt er backjumping uitgevoerd: het systeem springt niet slechts één stap terug, maar terug naar het punt waar de conflicterende constraint nog niet van toepassing was, en past de trail aan.
   • Het proces stopt wanneer het tableau gesloten is of wanneer een lege constraint (bewijs van onoplosbaarheid binnen de huidige dieptelimiet) wordt geleerd.

3. Verfijning van de Constraint-taal (Section 5):

   • De initiële taal (gebaseerd op specifieke inferentiestappen) bleek te specifiek.
   • De auteurs verfijnden de taal naar twee soorten atomen:
     • L@p: Een literaal $L$ op positie $p$ in het tableau.
     • x -> t: Een binding van variabele $x$ naar term $t$.
   • Er werden ook "No-Connection Atoms" ($p \not\sim q$) toegevoegd om aan te geven dat twee posities nooit verbonden kunnen worden, ongeacht de substitutie. Dit maakt de constraints generaler en krachtiger.

Belangrijkste Bijdragen

• Volledige Constraint Learning voor Connection Tableaux: Het is de eerste toepassing van constraint learning die de volledigheid van de connection tableau calculus behoudt, in tegenstelling tot eerdere onvolledige "cut"-methoden.
• Nieuwe Constraint-taal: De ontwikkeling van een taal die niet alleen specifieke inferentiestappen blokkeert, maar algemene patronen van variabelebindingen en literaalposities, waardoor de zoekruimte effectiever wordt ingeperkt.
• Prototype Implementatie (hopCoP): De auteurs hebben een nieuw systeem, hopCoP, gebouwd dat deze techniek implementeert. Dit systeem is ontworpen om vergelijkbaar te zijn met bestaande tools (zoals meanCoP) maar met de toegevoegde constraint learning functionaliteit.
• Theoretische Garanties: Het artikel bewijst dat het algoritme terminateert binnen een vaste dieptelimiet en dat het volledig is (als er een gesloten tableau bestaat binnen de limiet, zal het worden gevonden).

Resultaten

De auteurs hebben hopCoP geëvalueerd tegenover meanCoP (een state-of-the-art connection tableau solver) op verschillende benchmarks (TPTP, MPTP, Miz40).

• Aantal stappen: Op het probleem PUZ005-1 toonde hopCoP een drastische reductie in het aantal geteste extensiestappen in hogere diepten (bijvoorbeeld bij diepte 7: meanCoP deed 6.445.008 stappen, hopCoP slechts 48.517).
• Opgeloste problemen: Hoewel hopCoP per seconde minder inferenties uitvoert (door de overhead van constraint management), lost het binnen een tijdslimiet van 10 seconden meer problemen op dan zowel de standaard meanCoP als de onvolledige versie (!meanCoP).
  • Op de M2k benchmark: hopCoP (1.050) vs meanCoP (795).
  • Op de Miz40 benchmark: hopCoP (13.040) vs meanCoP (7.592).
• Conclusie: De reductie in backtracking weegt ruimschoots op tegen de rekenkosten van het beheren van constraints.

Betekenis en Toekomstperspectief

• Efficiëntie in Niet-Confluent Systemen: Het werk toont aan dat technieken uit de SAT/SMT-wereld (zoals CDCL en constraint learning) succesvol kunnen worden overgebracht naar first-order theorem proving, zelfs in systemen die van nature niet-confluent zijn.
• Toepasbaarheid: De methode is niet beperkt tot connection tableaux; het concept kan nuttig zijn voor andere niet-confluent tableau calculi.
• Synergie met Machine Learning: De auteurs wijzen op een interessante interactie met machine learning: constraint learning kan de zoekruimte voor een ML-gebaseerde heuristiek verkleinen, terwijl een goede heuristiek op zijn beurt nuttige constraints sneller kan leren.
• Beperkingen: Huidige beperkingen zijn het geheugengebruik (hoewel dit in de praktijk beheersbaar bleek) en de afhankelijkheid van expliciete posities in het tableau, wat de generalisatie van constraints beperkt. Toekomstig werk richt zich op het elimineren van deze positiesafhankelijkheid.

Kortom, dit artikel biedt een robuust theoretisch en praktisch kader om de inefficiëntie van backtracking in geavanceerde bewijssystemen op te lossen door intelligent leren van de oorzaken van mislukkingen.