Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks

Dit paper introduceert Polynomial Surrogate Training (PST), een methode die de training van differentieerbare ternaire logische netwerken mogelijk maakt door het gebruik van polynoombenaderingen, waardoor de berekeningskosten drastisch worden verlaagd en netwerken met een 'onbekend'-toestand efficiënter kunnen worden getraind voor betere onzekerheidsafweging en selectieve voorspelling.

De kern

De "Onzekere" Computer: Hoe een Nieuwe Wiskundige Truc Logische Netwerken Laat Dromen

Stel je voor dat je een computerprogrammeert om beslissingen te nemen, zoals een dokter die een diagnose stelt of een zelfrijdende auto die een kruispunt bekijkt. Normaal gesproken werken computers in een wereld van zwart en wit: een antwoord is ofwel "JA" (waar) ofwel "NEE" (onwaar).

Maar wat als de wereld niet zo simpel is? Wat als je niet zeker bent? Wat als je moet zeggen: "Ik weet het nog niet"?

Dit is precies het probleem dat de auteurs van dit paper (Sai Sandeep Damera en collega's) oplossen. Ze hebben een nieuwe manier bedacht om computers te laten leren met drie waarden in plaats van twee: Waar, Onwaar, en Ik weet het niet.

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen.

1. Het Oude Probleem: De "Kies-uit-een-lijst" Moeilijkheid

Stel je voor dat je een robot wilt bouwen die logische poortjes gebruikt (zoals de schakelaars in een computer).

• De oude methode: Voor elke schakelaar in de robot moest je een lijstje maken met alle mogelijke manieren waarop die schakelaar zou kunnen werken.
  • Voor een simpele "JA/NEE" schakelaar waren er maar 16 mogelijkheden. Dat was makkelijk te leren.
  • Maar voor een "JA/NEE/IK WEET HET NIET" schakelaar? Dan zijn er 19.683 mogelijke manieren waarop die schakelaar zou kunnen werken!
• Het probleem: Als je de robot probeert te leren door uit die enorme lijst van 19.683 opties te kiezen, wordt het proces zo traag en zwaar dat het onmogelijk wordt. Het is alsof je probeert een naald te vinden in een berg van 19.000 hooibergen, terwijl je blind bent.

2. De Oplossing: De "Wiskundige Schets" (Polynomial Surrogate Training)

De auteurs hebben een slimme truc bedacht. In plaats van de robot te laten kiezen uit die enorme lijst van 19.683 opties, laten ze de robot een wiskundige formule leren.

• De Analogie: Stel je voor dat je een schilderij wilt maken.
  • De oude manier: Je hebt een doos met 19.683 kant-en-klare schilderijen. Je moet er één kiezen en hopen dat het de juiste is.
  • De nieuwe manier (PST): Je geeft de schilder 9 potloden en een canvas. Hij leert hoe hij met die 9 potloden elke mogelijke vorm kan tekenen.
• Waarom is dit beter? In plaats van 19.683 keuzes te maken, leert de computer slechts 9 getallen (coëfficiënten) om de hele formule te beschrijven. Het is alsof je van een gigantische bibliotheek overstapt naar één slimme formule. Dit maakt het trainen 2 tot 3 keer sneller.

3. Het Magische "IK WEET HET NIET" Signaal

Dit is het coolste deel. Omdat de computer nu drie waarden kent (Ja, Nee, Ik weet het niet), kan hij op een heel menselijke manier omgaan met twijfel.

• De Dokter-Analogie:
  • Een gewone computer (alleen Ja/Nee) zegt altijd: "Je hebt griep!" of "Je hebt kanker!", zelfs als de symptomen vaag zijn. Hij maakt vaak fouten door te raden.
  • De nieuwe computer (met "Ik weet het niet") zegt: "De symptomen zijn vaag. Ik kan het niet zeggen."
• Het Resultaat: Als je alleen kijkt naar de momenten dat de computer wel een zeker antwoord geeft, blijkt hij veel accurater te zijn dan de oude computers. Hij slaat geen verkeerde diagnoses uit angst om niets te zeggen. Hij "stapt af" (abstention) wanneer hij onzeker is.

4. De "Hardening" (Van Droom naar Werkelijkheid)

Tijdens het leren droomt de computer in zachte, vloeibare getallen (bijvoorbeeld 0.8). Maar een echte computerchip werkt alleen met harde schakelaars (1 of 0 of -1).

• Het probleem: Vaak werkt de droom (de training) heel goed, maar als je de schakelaars op "harde" stand zet, crasht de prestatie.
• De oplossing: De auteurs ontdekten dat als je de computer groter maakt (meer neuronen), de kloof tussen droom en werkelijkheid kleiner wordt. Het is alsof je een grote groep mensen vraagt om een tekening te maken; als je er maar genoeg hebt, komt het eindresultaat perfect overeen met wat ze in gedachten hadden.

Samenvatting in één zin

De auteurs hebben een slimme wiskundige methode bedacht die computers toelaat om niet alleen "Ja" en "Nee" te zeggen, maar ook eerlijk "Ik weet het niet" te zeggen, waardoor ze sneller leren en betrouwbaardere beslissingen nemen in onzekere situaties.

Waarom is dit belangrijk?
Voor toepassingen waar fouten dodelijk kunnen zijn (zoals medische diagnoses of zelfrijdende auto's), is het beter om te zeggen "Ik weet het niet, check het nog eens" dan om een foutief antwoord te geven. Deze techniek maakt dat mogelijk voor de computers van de toekomst.

Technische samenvatting

Titel: Polynoom-Surrogaat Training voor Differentieerbare Ternaire Logische Poortnetwerken

Auteurs: Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras (Universiteit van Maryland)
Publicatie: Proceedings of Machine Learning Research (PMLR), 2025

---

1. Het Probleem

Bestaande Differentieerbare Logische Poortnetwerken (DLGNs) leren compacte en interpreteerbare Boolese circuits door gradienten te gebruiken. Echter, deze methoden hebben twee fundamentele beperkingen:

1. Beperkte Expressiviteit: Ze zijn beperkt tot 16 twee-ingang Boolese poorten (binair: TRUE/FALSE). Dit maakt het onmogelijk om onzekerheid of onbepaalde uitkomsten (zoals "nog niet bepaald") uit te drukken, wat essentieel is voor taken zoals classificatie bij sensoruitval of medische diagnose op basis van onvolledige gegevens.
2. Schaalbaarheid en Train-Test Kloof: Om uit te breiden naar Ternaire Kleene $K_3$ logica (waarbij de waarden FALSE, UNKNOWN en TRUE bestaan), zou de "softmax-over-poorten"-benadering moeten worden gebruikt. Voor twee-ingang ternaire poorten zijn er echter $3^{3^2} = 19.683$ mogelijke waarheidstabellen. Een categorische verdeling over deze enorme ruimte is onpraktisch (intractable) en leidt tot een grote kloof tussen het zachte trainingsgedrag en het harde inferentiegedrag (waarbij een enkele poort wordt geselecteerd).

2. Methodologie: Polynoom-Surrogaat Training (PST)

De auteurs introduceren Polynomial Surrogate Training (PST), een nieuw trainingskader dat de categorische parameterisatie volledig vervangt door directe polynoomparameterisatie.

• Directe Polynoomrepresentatie: In plaats van een verdeling over poorten te leren, leert elke neuron de coëfficiënten van een laaggraadig polynoom dat direct de functie over de ternaire domein $\{-1, 0, +1\}^2$ representeert.
  • Voor ternaire logica is dit een polynoom van graad (2, 2) met precies 9 leerbare coëfficiënten.
  • Dit dekt de volledige vocabulaire van 19.683 ternaire poorten, maar reduceert het aantal parameters met een factor 2.187 ten opzichte van de softmax-benadering.
• Differentieerbaarheid: Het polynoom is overal differentieerbaar ($C^\infty$), wat het gebruik van Gumbel-ruis of straight-through schattingen overbodig maakt.
• Commitment Loss (Toewijzingsverlies): Om de kloof tussen het continue trainingspolynoom en het discrete circuit te minimaliseren, wordt een data-onafhankelijke regularisatieterm toegevoegd. Deze "commitment loss" straft afwijkingen van de polynoomuitvoer van de geldige ternaire waarden $\{-1, 0, 1\}$ af.
• Hardening (Verharding): Tijdens inferentie wordt het polynoom van elke neuron geëvalueerd op het ternaire rooster en afgerond naar de dichtstbijzijnde geldige waarheidstabel. Dit resulteert in een puur digitaal ternair circuit.
• Fourier-analyse: De auteurs ontwikkelen een Fourier-raamwerk voor ternaire logica met een orthogonaal basis. Een unieke kwadratische term ($\varphi_2(x) = x^2 - 2/3$) vangt de gevoeligheid voor de "UNKNOWN"-toestand op, wat geen equivalent heeft in Boolese logica.

3. Belangrijkste Bijdragen

1. PST Framework: De eerste trainingsmethode voor logische poortnetwerken die de functieruimte direct parameteriseert (via 9 coëfficiënten) in plaats van via een verdeling over poorten. Dit maakt ternaire logica trainbaar op schaal.
2. Theoretische Garantie: Bewijs dat de discretisatiefout per neuron begrensd is door de commitment loss, wat een principiële mechanisme biedt om de train-test kloof te verkleinen.
3. Spectral Analysis: Een Fourier-analytisch raamwerk voor Kleene $K_3$ logica dat complexe maatstaven biedt voor regularisatie en post-hoc analyse van de geleerde poorten.
4. Selectieve Voorspelling: Demonstratie dat ternaire netwerken "principiële abstentie" (het uitblijven van een beslissing) kunnen toepassen via de UNKNOWN-uitgang, wat leidt tot Bayes-optimale onzekerheidsproxy's.

4. Resultaten

De methode werd getest op CIFAR-10 en synthetische taken:

• Schaalbaarheid op CIFAR-10:
  • PST traint ternaire circuits 2-3 keer sneller dan binaire DLGNs.
  • De "hardening gap" (het verlies aan nauwkeurigheid bij het overschakelen van zacht naar hard) neemt af naarmate het netwerk groter wordt (van 14,1% bij 96K neuronen naar 3,7% bij 512K neuronen). Dit suggereert dat overparameterisatie helpt bij het oplossen van de train-test kloof.
  • Ternaire netwerken bereiken vergelijkbare zachte nauwkeurigheid als binaire netwerken, maar genereren circuits met een veel rijkere poortvocabulaire.
• Selectieve Voorspelling en Onzekerheid:
  • Op synthetische taken (zoals Moons en Gaussians) gebruiken ternaire netwerken de UNKNOWN-uitgang om onzekere invoeren te filteren.
  • Wanneer onzekere voorspellingen worden verwijderd, overtreffen ternaire circuits de binaire netwerken aanzienlijk in nauwkeurigheid (bijv. 98,1% nauwkeurigheid bij 50% dekking op de Moons-dataset, versus 91,8% voor binaire netwerken met volledige dekking).
  • De dichtheid van UNKNOWN-uitgaven correleert sterk met de Bayes-optimaal onzekerheid, wat aantoont dat het netwerk correct leert om zich te onthouden bij moeilijke gevallen.
• Poortdiversiteit: In tegenstelling tot binaire netwerken die vaak dezelfde poorten herhalen, ontdekken ternaire netwerken een enorme diversiteit aan functioneel verschillende poorten (duizenden unieke waarheidstabellen).

5. Betekenis en Toekomstperspectief

Dit werk opent de deur naar meervoudige differentieerbare logica (niet alleen binair of ternair, maar ook quaternair, etc.).

• Efficiëntie: De parameterisatiekosten van PST groeien alleen kwadratisch met de logica-valsheid ($q^2$ coëfficiënten), terwijl de softmax-benadering super-exponentieel groeit ($q^{q^2}$).
• Toepassingen: Ternaire logica is ideaal voor veiligheidskritieke systemen waar "onbekend" een geldig antwoord is (bijv. runtime verificatie, medische AI, sensorfusie).
• Hardware: De gegenereerde circuits zijn volledig interpreteerbaar en kunnen direct worden geïmplementeerd op ultra-efficiënte ASIC's (Application-Specific Integrated Circuits).

Kortom, PST lost het schaalbaarheidsprobleem van differentieerbare logica op en maakt ternaire logica een praktisch en krachtig instrument voor onzekerheidsbewuste AI.