In de wereld van machine learning leren computers voorspellingen te doen door het bestuderen van voorbeelden. Stel je een student voor die probeert het antwoord op een toetsvraag te raden. In de standaard manier van leren, de zogenaamde "PAC-learning", oefent de student met een set flashcards, en maakt vervolgens een toets met nieuwe, ongeziene kaarten. Het doel is om gemiddeld goed te presteren over vele mogelijke toetsen. Maar er is een andere, specifiekere manier van leren, genaamd "transductief leren". Hierbij krijgt de student vooraf de volledige toets, inclusief elke vraag, waarbij het antwoord op slechts één specifieke vraag verborgen blijft. De student ziet alle andere antwoorden en moet het enkele ontbrekende antwoord voorspellen. Deze opzet is strenger omdat de student niet kan vertrouwen op gemiddelde prestaties; de student moet het goed hebben voor die specifieke, vaste set vragen.

Voor eenvoudige problemen met slechts twee mogelijke antwoorden, zoals "ja" of "nee", hebben onderzoekers lang geweten dat deze twee manieren van leren in essentie hetzelfde zijn wat betreft hoeveel data er nodig is om te slagen. Wanneer de antwoorden echter een van de vele mogelijkheden kunnen zijn—zoals het identificeren van duizenden verschillende vogelsoorten of het diagnosticeren van honderden ziekten—veranderen de regels. In deze complexe, "multiclass"-situaties hangt de moeilijkheid van het leren af van twee verschillende wiskundige maten van complexiteit. Eén maat, vaak de DS-dimensie genoemd, heeft betrekking op hoe goed de leerder kan omgaan met situaties waarin een perfect antwoord bestaat. De andere, de Natarajan-dimensie, heeft betrekking op hoeveel onzekerheid er overblijft wanneer er geen perfect antwoord beschikbaar is. Het was jarenlang een open vraag of de strikte "transductieve" regels de leerder zouden dwingen om meer data nodig te hebben dan de standaard "PAC"-regels, vooral wanneer het aantal mogelijke antwoorden enorm groot of zelfs oneindig is.

Een onderzoeker aan de Johns Hopkins University heeft deze vraag nu opgelost door aan te tonen dat de strikte transductieve regels voor multiclass-problemen niet daadwerkelijk meer data vereisen dan de standaardregels, tot zeer kleine aanpassingen aan toe. Zij bewezen dat de hoeveelheid informatie die nodig is om te leren in deze strikte setting wordt beheerst door dezelfde twee complexiteitsmaten die de standaard setting beheersen. Hun werk laat zien dat zelfs wanneer de leerder een enkele verborgen label moet voorspellen uit een vaste groep voorbeelden, zij hetzelfde niveau van nauwkeurigheid kunnen bereven als wanneer zij zouden leren van een willekeurige stroom gegevens. Deze bevinding is significant omdat het twee verschillende modellen van leren verenigt, waarbij bevestigd wordt dat de fundamentele grenzen van het leren worden bepaald door de aard van het probleem zelf, en niet door de specifieke manier waarop de data wordt gepresenteerd.

Om tot deze conclusie te komen, moest de onderzoeker een grote hindernis overwinnen. In de strikte transductieve setting kan een leerder niet simpelweg naar alle zichtbare antwoorden kijken en de beste regel kiezen, omdat dit kan leiden tot een soort instabiliteit. Als een leerder probeert de zichtbare data perfect aan te passen, kan hij per ongeluk een regel creëren die voor elk zichtbaar voorbeeld werkt, maar volledig faalt op het verborgen voorbeeld. Dit is vergelijkbaar met een student die de antwoorden op elke oefenvraag uit het hoofd leert, maar de toets niet haalt omdat hij het onderliggende patroon niet heeft begrepen. De onderzoeker ontdekte dat de leerder, om deze valstrik te vermijden, bewust een deel van de zichtbare data moet negeren.

De oplossing die zij bedachten, omvat een strategie van "random reservation" (willekeurige reservering). In plaats van alle zichtbare voorbeelden te gebruiken om een voorspelling te bouwen, zet de leerder een groot deel van de zichtbare data willekeurig opzij, en behandelt deze alsof het de verborgen testpunt is. Door deze gereserveerde labels te negeren, creëert de leerder een grote, ongeziene blok data die statistisch onafhankelijk is van de regel die zij construeren. Dit stelt hen in staat om krachtige wiskundige instrumenten te gebruiken die berusten op het idee van generalisatie—het goed voorspellen van data die niet is gebruikt om het model te bouwen. De leerder gebruikt vervolgens een driestappenproces om hun voorspelling te verfijnen. Eerst gebruiken zij een kleine steekproef van de zichtbare data om een eindige lijst van mogelijke voorspellingsregels te maken. Vervolgens gebruiken zij een gewogen stemsysteem om de lijst van mogelijke antwoorden voor elke vraag in te perken, wat effectief de complexiteit van het probleem vermindert. Ten slotte gebruiken zij de resterende zichtbare data om de beste regel uit deze ingeperkte lijst te selecteren.

Deze aanpak rust op een nieuw wiskundig inzicht over hoe om te gaan met data die zonder teruglegging wordt gesampled. In veel leerscenario's wordt aangenomen dat datapunten onafhankelijk zijn, zoals het trekken van een kaart uit een deck en het terugleggen ervan. Maar in de transductieve setting geldt: zodra een datapunt gezien is, kan het niet meer gezien worden. De onderzoeker bewees dat zelfs met deze beperking, een specifiek type gewogen stemsysteem nog steeds effectief werkt. Zij toonden aan dat de "experts" of regels in hun systeem een voorspelbare hoeveelheid "beloningen" verdienen op basis van hoe goed zij de ongeziene delen van de data dekken. Dit zorgt ervoor dat de leerder geen nauwkeurigheid verliest bij de overgang van de zichtbare data naar de verborgen voorspelling.

De onderzoeker bewees ook dat hun resultaat het best mogelijke is door specifieke voorbeelden te construeren waar leren moeilijk wordt. Zij toonden aan dat als een probleem een hoog niveau van complexiteit heeft in de zin van een "perfect antwoord", de foutmarge proportioneel is aan die complexiteit gedeeld door het aantal voorbeelden. Als een probleem een hoog niveau van onzekerheid heeft in de zin van "geen perfect antwoord", is de foutmarge proportioneel aan de vierkantswortel van die complexiteit gedeeld door het aantal voorbeelden. Beide factoren zijn noodzakelijk; het verwijderen van één van beide zou de leer taak in bepaalde gevallen onmogelijk maken. Dit bevestigt dat de twee dimensies van complexiteit die in de standaard learning theory zijn geïdentificeerd, inderdaad de juiste maten zijn voor de strikte transductieve setting eveneens.

De implicaties van dit werk zijn dat de kloof tussen de twee leermodellen is gedicht. Voor iedereen die leeralgoritmen ontwerpt voor complexe, multiclass-problemen, betekent dit dat dezelfde theoretische grenzen gelden, of de data nu wordt gepresenteerd als een willekeurige stroom of als een vaste set met één verborgen antwoord. De onderzoeker heeft geen specifiek algoritme geleverd dat gegarandeerd snel is op een computer, aangezien hun bewijs gebaseerd is op informatietheorie in plaats van computationele efficiëntie. Echter, zij hebben vastgesteld dat de fundamentele barrière voor het leren hetzelfde is in beide werelden. Door aan te tonen dat een gestructureerde aanpak met behulp van random reservation en compressie de successen van standaard learning kan overdragen naar de strikte transductieve setting, hebben zij een duidelijk pad gebaand voor het begrijpen van de grenzen van voorspelling in complexe omgevingen.

Dit werk verheldert ook de rol van verschillende soorten complexiteit in het leren. Het laat zien dat het vermogen om een perfecte regel te leren en het vermogen om een goede regel te leren in de aanwezigheid van ruis, verschillende uitdagingen zijn, die elk een andere hoeveelheid data vereisen. De onderzoeker heeft aangetoond dat deze uitdagingen niet op een manier samenkomen die de transductieve setting moeilijker maakt dan de standaard setting. In plaats daarvan kan de leerder door de vaste populatie van data navigeren door strategisch delen ervan te negeren, waardoor een moeilijke, instabiele situatie wordt omgezet in een beheersbare een. Het resultaat blijft overeind, zelfs wanneer het aantal mogelijke antwoorden oneindig is, een scenario waar eerdere methoden vaak faalden.

Uiteindelijk bevestigt de studie dat de wetten die bepalen hoe machines leren robuust zijn. Of de leerder nu oefent op een willekeurige set voorbeelden of een specifieke puzzel oplost met één ontbrekend stukje, de hoeveelheid informatie die nodig is om te slagen, wordt bepaald door dezelfde onderliggende structuur van het probleem. De onderzoeker heeft aangetoond dat door zorgvuldig te beheren hoe data wordt gebruikt en door het specifieke dimensies van complexiteit te begrijpen, het mogelijk is om optimale prestaties te behalen in de striktste leeromgevingen. Dit biedt een solide theoretische basis voor toekomstige ontwikkelingen in machine learning, waarbij wordt gewaarborgd dat naarmate algoritmen geavanceerder worden, zij geworteld blijven in een helder begrip van wat mogelijk is.