Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs

Stel je voor dat je de kapitein bent van een ruimteschip dat probeert door een complex doolhof van asteroïden te navigeren om een verre planeet te bereiken. In de wereld van de informatica is dit vergelijkbaar met "instructional sequencing" (instructievolgorde), waarbij een AI of een docent probeert de beste volgorde te bepalen om een student nieuwe concepten aan te leren. Het doolhof heeft regels: je kunt niet leren over "raketmotoren" totdat je "basisfysica" beheerst hebt. Dit wordt een "prerequisite dependency" (vooraanstaande afhankelijkheid) genoemd.

Normaal gesproken denken we dat het moeilijkste deel van deze navigatie de onzekerheid is. Zal de student de les begrijpen? Zal hij falen en opnieuw moeten proberen? We nemen vaak aan dat omdat leren onvoorspelbaar is (stochastisch), we complexe, snelle computers nodig hebben om de toekomst te raden en voor elke "wat als"-situatie een plan te maken. Maar wat als de echte moeilijkheid helemaal niet het gokspel is? Wat als de echte moeilijkheid eigenlijk het enorme aantal mogelijke paden door het doolhof is, zelfs als we precies zouden weten hoe de student zou reageren? Dit artikel duikt in die vraag en vraagt zich af: is de willekeur van het leren de echte schurk, of is het de enorme complexiteit van de kaart zelf?

De auteurs van dit artikel, een team van computerwetenschappers, besloten dit aan te pakken door een wiskundig model te bouwen van een student die een reeks concepten leert. Ze behandelden het leerproces als een spel waarbij je probeert van een startpunt (niets weten) naar een finishlijn (alles weten) te bewegen met de minste inspanning. In hun model is er telkens wanneer een student een nieuw concept probeert te leren een kans dat hij slaagt en een kans dat hij faalt. Als hij faalt, blijft hij precies waar hij is; hij verliest niet wat hij al weet, hij moet het gewoon opnieuw proberen.

Hier is de grote verrassing die het team ontdekte: de willekeur is niet het moeilijke deel. Ze hebben wiskundig bewezen dat je alle onzekerheid kunt weghalen. Je kunt dit onvoorspelbare, "gaat-hij-het-wel-of-niet"-leerspel veranderen in een volledig voorspelbare, deterministische kaart. Het is also kind dat je, ook al is een muntworp willekeurig, als je de kansen kent, kunt berekenen wat de gemiddelde kosten zijn om de munt te blijven werpen tot je kop krijgt, en die gemiddelde kosten als een vaste prijs kunt behandelen. Zodra je dat doet, gaat het probleem niet meer over "raden" en gaat het over het vinden van het kortste pad op een gigantisch, star raster.

Maar alleen omdat de willekeur weg is, betekent dit niet dat het probleem makkelijk is. Sterker nog, de auteurs ontdekten dat zelfs met de willekeur verwijderd, het vinden van de perfecte volgorde om deze concepten te onderwijzen nog steeds ongelooflijk moeilijk is voor een computer in de slechtste scenario's. Ze lieten zien dat deze moeilijkheid voortkomt uit de manier waarop concepten naar elkaar "overdragen"—het leren van het ene ding kan een ander ding makkelijker maken, maar als die behulpzame verbindingen een verstrengeld web vormen, raakt de computer verstrikt in de poging om de beste route te vinden. Dit noemen ze "combinatorische complexiteit". Het is niet dat de computer in de war is door de stemming van de student; het is dat de kaart van mogelijke leerpaden simpelweg te groot is om elk pad te controleren.

Maar maak je geen zorgen, het is niet alleen maar slecht nieuws. Het papier vond ook dat voor veel realistische situaties de kaart niet zo verstrengeld is. Ze ontwikkelden een eenvoudig "diagnostisch hulpmiddel" (een soort wiskundige test) dat naar een cursus kan kijken en je kan vertellen, nog voordat je begint met plannen, of de volgorde van lessen er echt veel toe doet. Als het hulpmiddel zegt dat de kaart "acyclisch" is (geen verwarrende lussen van afhankelijkheden), dan zal elke logische volgorde die je kiest prima werken, en heb je geen supercomputer nodig om de perfecte een te vinden.

Om dit te testen, keken de onderzoekers naar echte gegevens van een introductiecursus informatica met meer dan 70.000 studentinteracties. Hun diagnostische hulpmiddel bevestigde dat voor deze specifieke klas de "perfecte volgorde" er niet veel toe deed; de cursus bevond zich in wat zij een "dubbel gemakkelijke regime" noemen. De studenten konden in bijna elke volgorde leren, en de kosten van het iets verkeert doen waren minimaal. Echter, ze bouwten ook kunstmatige, lastige voorbeelden waarbij de afhankelijkheden rommelig waren. In die gevallen veroorzaakte het kiezen van de verkeerde volgorde enorme spijt (verspilde tijd en moeite), wat bewees dat hoewel veel echte klassen gemakkelijk te navigeren zijn, de moeilijke wel degelijk bestaan.

Het team liet ook zien dat wanneer de kaart wel moeilijk is, je niet elke pad hoeft te controleren. Ze gebruikten een slimme zoekmethode genaamd A* (denk aan een GPS die het doel kent en alleen de meest veelbelovende wegen controleert) om de beste sequentie te vinden. Zelfs in hun lastigste, meest complexe voorbeelden hoefde deze slimme GPS slechts een fractie van de mogelijke paden te bekijken om de winnaar te vinden.

Dus, wat is de belangrijkste les? Als je een app bouwt om kinderen te onderwijzen, hoef je niet in paniek te raken over het feit dat studenten onvoorspelbaar zijn. Je kunt het probleem wiskundig vereenvoudigen om het "raden" te verwijderen. De echte uitdaging is controleren of je curriculum een rommelige, verstrengelde structuur heeft. Als dat het geval is, gebruik dan een slimme zoektool om het beste pad te vinden. Als dat niet zo is (zoals in veel echte klassen), kun je ontspannen, want de volgorde van lessen zal waarschijnlijk niet veel verschil maken. Het artikel bewijst dat de "magie" van leren niet zit in het voorspellen van de toekomst, maar in het begrijpen van de vorm van de kaart.