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

Imaginez que vous soyez le capitaine d'un vaisseau spatial tentant de naviguer à travers un labyrinthe complexe d'astéroïdes pour atteindre une planète lointaine. Dans le monde de l'informatique, cela ressemble à l'« ordonnancement pédagogique », où une IA ou un enseignant essaie de déterminer le meilleur ordre pour enseigner de nouveaux concepts à un étudiant. Le labyrinthe possède des règles : vous ne pouvez pas apprendre les « moteurs de fusée » avant d'avoir maîtrisé la « physique de base ». C'est ce qu'on appelle une « dépendance de prérequis ».

Habituellement, nous pensons que la partie la plus difficile de cette navigation est l'incertitude. L'étudiant comprendra-t-il la leçon ? Va-t-il échouer et devoir réessayer ? Nous supposons souvent que parce que l'apprentissage est imprévisible (stochastique), nous avons besoin d'ordinateurs complexes et ultra-rapides pour deviner l'avenir et planifier pour chaque scénario de type « et si ». Mais et si la véritable difficulté n'était pas du tout le jeu des devinettes ? Et si le vrai problème était simplement le nombre colossal de chemins possibles à travers le labyrinthe, même si nous connaissions exactement la réaction de l'étudiant ? Ce document explore cette question, demandant : l'aléa de l'apprentissage est-il le véritable méchant, ou est-ce la complexité pure de la carte elle-même ?

Les auteurs de ce document, une équipe de chercheurs en informatique, ont décidé de s'attaquer à cela en construisant un modèle mathématique d'un étudiant apprenant un ensemble de concepts. Ils ont traité le processus d'apprentissage comme un jeu où l'on tente de passer d'un point de départ (ne rien savoir) à une ligne d'arrivée (tout savoir) avec le moins d'efforts possible. Dans leur modèle, chaque fois qu'un étudiant tente d'apprendre un nouveau concept, il y a une chance qu'il réussisse et une chance qu'il échoue. S'il échoue, il reste exactement là où il en était ; il ne perd pas ce qu'il sait déjà, il doit juste réessayer.

Voici la grande surprise découverte par l'équipe : le hasard n'est pas la partie difficile. Ils ont prouvé mathématiquement que vous pouvez éliminer toute l'incertitude. Vous pouvez transformer ce jeu d'apprentissage imprévisible, ce « va-t-on réussir ou non », en une carte complètement prévisible et déterministe. C'est comme réaliser que même si un lancer de pièce est aléatoire, si vous connaissez les probabilités, vous pouvez calculer le coût moyen de lancer la pièce jusqu'à obtenir pile, et traiter ce coût moyen comme un prix fixe. Une fois cela fait, le problème ne consiste plus à « deviner », mais à trouver le chemin le plus court sur une grille géante et rigide.

Cependant, même si le hasard a disparu, cela ne signifie pas que le problème est facile. En fait, les auteurs ont découvert que même sans l'aléa, trouver l'ordre parfait pour enseigner ces concepts reste incroyablement difficile pour un ordinateur dans les pires scénarios. Ils ont montré que cette difficulté provient de la manière dont les concepts se « transfèrent » les uns aux autres — apprendre une chose peut en rendre une autre plus facile, mais si ces connexions bénéfiques forment un réseau emmêlé, l'ordinateur s'enlise en essayant de trouver la meilleure route. C'est ce qu'ils appellent la « complexité combinatoire ». Ce n'est pas que l'ordinateur est confus par l'humeur de l'étudiant ; c'est que la carte des chemins d'apprentissage possibles est simplement trop vaste pour en vérifier tous les détails.

Mais ne vous inquiétez pas, tout n'est pas négatif. Le document a également révélé que, pour de nombreuses situations réelles, la carte n'est pas si emmêlée. Ils ont développé un « outil de diagnostic » simple (une sorte de test mathématique) qui peut examiner un cours et vous dire, avant même de commencer la planification, si l'ordre des leçons importe réellement. Si l'outil indique que la carte est « acyclique » (pas de boucles de dépendances confuses), alors n'importe quel ordre logique que vous choisirez fonctionnera parfaitement, et vous n'aurez pas besoin d'un supercalculateur pour trouver le meilleur.

Pour tester cela, les chercheurs ont examiné des données réelles provenant d'un cours d'introduction à l'informatique comprenant plus de 70 000 interactions étudiantes. Leur outil de diagnostic a confirmé que pour ce cours spécifique, l'« ordre parfait » n'avait pas beaucoup d'importance ; le cours se situait dans ce qu'ils appellent un « régime doublement facile ». Les étudiants pouvaient apprendre dans presque n'importe quel ordre, et le coût d'un mauvais choix était minime. Cependant, ils ont également construit des exemples artificiels et complexes où les dépendances étaient désordonnées. Dans ces cas, choisir le mauvais ordre entraînait un regret énorme (temps et efforts gaspillés), prouvant que si beaucoup de cours réels sont faciles à naviguer, les plus difficiles existent bel et bien.

L'équipe a également montré que lorsque la carte est difficile, vous n'avez pas besoin de vérifier chaque chemin. Ils ont utilisé une méthode de recherche intelligente appelée A* (pensez à un GPS qui connaît la destination et ne vérifie que les routes les plus prometteuses) pour trouver la meilleure séquence. Même dans leurs exemples les plus complexes et les plus difficiles, ce GPS intelligent n'a eu qu'à examiner une infime fraction des chemins possibles pour trouver le gagnant.

Alors, quelle est la conclusion ? Si vous construisez une application pour enseigner aux enfants, vous n'avez pas besoin de paniquer face au fait que les étudiants sont imprévisibles. Vous pouvez simplifier mathématiquement le problème pour éliminer la partie « devinette ». Le véritable défi est de vérifier si votre programme possède une structure désordonnée et emmêlée. Si c'est le cas, utilisez un outil de recherche intelligente pour trouver le meilleur chemin. Si ce n'est pas le cas (comme dans beaucoup de cours réels), vous pouvez vous détendre, car l'ordre des leçons n'aura probablement pas d'impact majeur. Le document prouve que la « magie » de l'apprentissage ne réside pas dans la prédiction de l'avenir, mais dans la compréhension de la forme de la carte.