Hackathon FUN POEM ManHill Optimization

Présentation du sujet=

Un très grand nombre de contenus pédagogiques numériques (pas forcément des vidéos, mais aussi des présentations powerpoint, des pdf, des QCM, des feuilles d’exercice, etc…) sont disponibles dans les universités mais aussi sur internet. Si les contenus existants (possiblement déjà en ligne via Youtube, Dailymotion, Wikipedia, Wikiversity ou tout simplement sur les plateformes MOODLE et serveurs des universités), ne sont pas organisés et structurés en parcours pédagogique (avec une progression, des niveaux, etc..), ils sont quasiment inexploitables pour des apprenants qui voudraient progresser par eux-mêmes (comment savoir ce qui existe, où le trouver, et dans quel ordre faire les choses ? L’objectif de ce projet est de mettre en œuvre un algorithme de colonie de fourmis connu pour ses capacités émergentes à élaborer un plus court chemin entre la fourmilière et des points de nourriture. Transposé dans le monde de l’éducation numérique, cet algorithme sera capable de relier des contenus pédagogiques pour créer des trajectoires d’apprentissage optimales vers des objectifs pédagogiques déterminés. Il s’agit pour ce hackathon de transposer dans edX l’hommilière actuellement implémentée en PHP-MySQL de la plateforme POEM (poem.unistra.fr), dans le cadre de l’UniTwin CS-DC de l’UNESCO (http://cs-dc.org) regroupant actuellement 115 universités dans le monde. Ce travail fera l’objet de publications internationales. L’équipe gagnante du hackathon aura l’opportunité de continuer avec l’équipe de développement de POEM (et de co-publier dans le prochain papier international soumis sur le sujet) et de voir son travail utilisé sur la plate-forme de France Université Numérique, si le travail est suffisamment abouti.

Description du projet

Historique

Lorsqu’elles collaborent, les fourmis sont connues pour trouver le plus court chemin entre leur fourmilière et un point de nourriture. Le mécanisme derrière cette performance a été compris par Jean-Louis Deneubourg et son équipe, au début des années 1980. Très rapidement, Bernard Manderick et son étudiant, Frans Moyson proposent en 1988 une implémentation de fourmis artificielles sur ordinateur montrant le même comportement. Pour bien voir le mécanisme à l’œuvre, Antoine Dutot (Université du Havre) développe une petite applet montrant comment les fourmis trouvent le plus court chemin entre la fourmilière et les points de nourriture : http://litis.univlehavre.fr/~dutot/MiscResearch.html (noter qu’on peut déplacer les nœuds du graphe à l’aide de la souris et voir les fourmis trouver le plus court chemin). Ensuite, dans sa thèse publiée en 1992, Marco Dorigo utilise des fourmis artificielles pour résoudre le problème du plus court chemin, en proposant l’Optimisation par Colonie de Fourmis (Ant Colony Optimization).

En 2001, la société Paraschool (numéro 1 de l’e-learning en France) cherche un moyen de gérer de manière automatique les 50 000 élèves utilisant leur logiciel. Un premier papier est publié en 2003 sur l’utilisation de colonies de fourmis dans le cadre de l’e-learning et une thèse est financée qui aboutira à la modification du paradigme de l’OCF pour l’adapter au comportement humain, aboutissant au concept d’hommilière.

Lire http://www.epi.asso.fr/revue/articles/a0603b.htm pour un résumé du projet.

Concept derrière les hommilières

La grande idée derrière les hommilières consiste à faire émerger de manière automatique des trajectoires pédagogiques optimales entre des items pédagogiques variés, (comme des vidéos sur edX) en utilisant le parcours de l’apprenant, suivant ses échecs ou ses succès.

À la suite d’une vidéo visionnée (ou d’un contenu numérique), on peut poser des questions à l’apprenant. Si l’apprenant répond bien aux questions, cela signifie qu’il a bien compris le cours, mais cela signifie bien plus aussi, car il est rare qu’on puisse valider un cours indépendamment d’un cursus : pour comprendre un cours sur des équations différentielles, il faut comprendre ce que sont les dérivées. Pour comprendre ce que sont les dérivées, il faut comprendre ce que sont les fonctions, etc... Ainsi, c’est une succession de cours suivant une bonne progression qui permet de comprendre des choses qui auraient été incompréhensibles sans cette accumulation de connaissances.

Les hommilières visent à trouver de bonnes progressions dans une série d’éléments pédagogiques numériques en vrac. Ainsi, si l’on valide un item pédagogique, on en déduit que c’est la conséquence d’une bonne suite d’items pédagogiques suivis précédemment.

Les items pédagogiques sont les nœuds d’un graphe : le graphe de la connaissance, où tous les nœuds sont reliés entre eux par des arcs, mais pas forcément de manière directe. Il s’agit de trouver les bons chemins de progression entre les nœuds du graphe de la connaissance.

Pour faire émerger des bons chemins de progression, on va rétribuer les arcs reliant les différents nœuds comme le font les fourmis, c.-à-d. en déposant sur les arcs reliant les vidéos des phéromones volatiles qui permettent une reconfiguration dynamique, si de nouveaux nœuds apparaissent.

Si, dans les fourmilières, l’évaporation des phéromones se fait sur une base temporelle, dans une hommilière, l’évaporation des phéromones doit se faire suivant l’activité dans le graphe. Le mécanisme à implémenter ne sera pas un mécanisme d’évaporation temporelle mais un mécanisme d’érosion (expliqué plus bas) lié à l’activité dans le graphe.

Implémentation en tant que plugin edX

L’équipe pourra s’inspirer d’une implémentation existante en PHP-mySQL, dont les sources seront mis à disposition. Dans un premier temps, on prévoira d’implémenter le mécanisme suivant :

1. Chaque item pédagogique (lien vers une vidéo) est le nœud d’un graphe (qu’on pourra stocker en mémoire sous forme d’une matrice). Ce nœud doit pouvoir contenir :
   1. Un lien vers une vidéo ou un document.
   2. Un lien vers une base de questions avec réponses simples dans un premier temps (QCM) : on propose deux réponses pour chaque question et seule une réponse est correcte.
   3. Une liste (de taille illimitée) de liens vers d’autres items pédagogiques avec, associé à chaque lien :
      1. un nombre de phéromones positives (nom de variable réelle proposé : dAPosPh s’expliquant comme cela : d pour double (type), A pour Additive (c’est une phéromone additive contrairement aux phéromones multiplicatives), Pos pour Positive, et Ph pour Phéromone)
      2. un nombre de phéromones négatives (dANegPh).

La somme entre phéromones négatives et positives permet de déterminer l’activité du lien.

1. Lorsqu’un apprenant arrive sur un nœud (un item pédagogique), le système lui propose de consulter la vidéo ou le document associé au noeud.
2. Le système pose un QCM à l’apprenant qui doit y répondre (il suffira d’une question dans le contexte du hackathon : l’évaluation est un autre des défis proposés).
3. La réponse à chacune des questions permet de rétribuer le lien vers le nœud sous forme de phéromones positives ou négatives. Comme on veut privilégier l’apparition de chemins, on rétribue les trois liens précédents ayant amené l’apprenant à faire l’item pédagogique courant. Pour chaque question réussie, on incrémente la variable dAPosPh du lien précédent de 3 points, la variable dAPosPh du lien pénultième de 2 points, et la variable dAPosPh de l’antépénultième de 1 point. Pour chaque question où l’apprenant a mal répondu, on incrémente la variable dANegPh du lien précédent de 3 points, la variable dANegPh du pénultième de 2 points et la variable dANegPh de l’antépénultième de 1 point. Cela veut dire qu’il faut garder en mémoire les trois derniers items par lequel l’apprenant est passé pour pouvoir les rétribuer correctement, mais aussi qu’il faut gérer l’amorçage. Lorsqu’il s’agit du premier item pédagogique, on ne rétribuera que le lien précédent. Lorsqu’il s’agit du deuxième, on ne rétribue que les 2 liens précédents.
4. Lorsque l’item est terminé (consultation de la vidéo ou du document associé et réponse aux questions effectuée), deux cas sont possibles :
   1. L’apprenant sélectionne lui-même un nouvel item pédagogique parmi ceux disponibles dans l’hommilière, ou
   2. L’apprenant suit l’une des trois propositions faites par l’hommilière.

Si l’apprenant a sélectionné lui-même un nouvel item pédagogique, alors un nouvel arc est créé entre l’item pédagogique courant et le nouvel item choisi (il faudra ajouter un nouveau lien dans la liste des liens, et c’est pour cela que cette liste ne doit pas être limitée en taille). Si l’apprenant veut se faire guider par l’hommilière, alors, des liens sont choisis en probabilité suivant les phéromones laissées sur les arcs. Pour conserver son caractère dynamique à l’hommilière (la possibilité de trouver de nouveaux chemins), le choix doit être stochastique et non déterministe (sans, ça, c’est toujours le meilleur chemin qui est suivi, et de nouveaux chemins ne pourront pas être trouvés). Le choix stochastique se fera de la manière suivante :

1. 1. Si 1 à trois liens sortent de l’item, ils sont présentés dans l’ordre suivant :
   2. S’il n’y a qu’un lien, on présente le lien.
      1. S’il y a deux liens, on calcule pour chaque lien la valeur dAPosPhdANegPh et on présente en premier le meilleur lien (valeur dAPosPhdANegPh la plus élevée) avec une probabilité de 80%.
      2. S’il y a trois liens on fait un tournoi binaire pour déterminer quel lien présenter en premier : on pioche 2 liens au hasard parmi les trois, et on sélectionne celui des deux liens qui a la meilleur valeur. C’est celui-ci qu’on présente en premier. Pour les deux autres liens, on fait comme précédemment (on regarde la valeur des deux liens, et on présente en premier le meilleur avec une probabilité de 80%).
      3. S’il y a 4 liens et plus, trois liens sélectionnés par tournoi binaire sans remise :
   3. Pour le premier lien, on pioche deux liens aléatoirement parmi tous les liens possibles et on sélectionne le meilleur des deux (suivant la valeur dAPosPhdANegPh).
   4. Pour le deuxième lien, on fait pareil, mais en ayant pris soin de ne pas pouvoir sélectionner le lien déjà proposé.
   5. Pour le troisième lien, on fait pareil, mais en prenant soin de ne pas pouvoir sélectionner les deux liens déjà proposés.
2. Érosion des phéromones : pour éviter que des chemins précieux de phéromones ne disparaissent si une partie du graphe n’est pas utilisée pendant un certain temps, il ne faut pas que les phéromones s’évaporent (comme chez les fourmis), mais qu’elles s’érodent au passage des apprenants (c’est une des différences entre les hommilières et les fourmilières). Le mécanisme d’érosion des phéromones est le suivant : lorsqu’un participant termine un item pédagogique A et sélectionne un item pédagogique B, alors, il faut éroder tous les liens partant de A. Ainsi, les liens non suivis paieront de la valeur de l'érosion le fait de ne pas avoir été choisis, tandis que le lien suivi (vers B), érodé lui aussi, verra les valeurs des phéromones qu'il porte modifiées par le succès ou l'échec à l'item B. Le nouveau terme érosion a été choisi car la décrémentation du niveau de phéromone n'a lieu que lors du passage d'un élève sur un noeud. Cette érosion amène l'avantage de ne pas perdre l'information durant les périodes d'inactivité tout en conservant un équivalent d'évaporation pour les arcs non sélectionnés.

Ces mécanismes simples permettent d’implémenter une hommilière, que vous pourrez tester dans un premier temps sur des cas simples. Un jeu de test sera élaboré par le jury pour vérifier le bon fonctionnement de l’hommilière.