Le nez dans le code

Le code de Parcoursup a été publié. J'invite chacun à y jeter un œil, pour trois raisons. Tout d'abord parce que c''est libre, gratuit, ça ne coûte rien. Ensuite, il n'est pas indispensable de parler JAVA ou PLSQL pour comprendre à quel jeu sont soumis nos enfants, enfin, parce que l'on découvre ce qui ce joue.


Comme d'habitude, la religion est utilisée pour faire diversion, comme l'illustre très bien cette Une de Charlie Hebdo. Il ne faut pas tomber dans ce piège-là. La question, c'est Parcoursup et ce que ça entraîne (sélection à l'université, etc...), et rien d'autre... 

Servez-vous !


Le code est disponible à cette adresse :
https://framagit.org/parcoursup/algorithmes-de-parcoursup

Si l'on souhaite avoir le code sur son ordinateur, on peut installer un programme, nommé git ou taper :
git clone https://framagit.org/parcoursup/algorithmes-de-parcoursup.git

Après avoir récupéré les fichiers une première fois, on peut le faire régulièrement. Cela m'a permis de m'apercevoir que le code bougeait beaucoup, c'est-à-dire que l'artisan derrière ces lignes travaille pour améliorer son œuvre.


Par exemple, hier soir, 22 fichiers ont été modifiés. Il y a eu, 270 insertions (+) et 82 suppressions (-). C'est juste énorme, même si dans les 270 ajouts, il y a 188 lignes d'un fichier effacé par erreur la veille.

Pour un développeur, publier son code, c'est montrer ses faiblesses et espérer que quelqu'un comprendra les coups de génie. C'est aussi le plaisir d'être lu dans l'espoir que quelqu'un suggère une modification, ou une erreur avant qu'un utilisateur ne crie au scandale parce que ça ne marche pas. C'est ce qui s'est passé ici. Les remarques des utilisateurs sur twitter sont immédiatement prises en compte par Hugo Gimbert. 


Le code a été publié lundi. Dans les heures qui ont suivi, les modifications étaient plutôt cosmétiques [1]. Dans l'exemple ci-dessus, on a supprimé un long message d'alerte que personne ne lira  : 
Surcapacité formation non expliquée par le rang limite, veuillez vérifier qu'une diminution du surbooking a eu lieu pour le groupe de classement.  

par : "Surcapacité formation"

Comment lire ce code ?


Quand on ouvre un fichier, on voit des lignes commentées (qui commencent par //) dans un français qui n'est pas celui de Voltaire. Le but est d'expliquer ce que fait chaque variable, chaque instruction. Il faut donc que ce soit rapide. Ceci n'est pas indispensable au fonctionnement du programme, et seuls les meilleurs développeurs détaillent vraiment ce qu'ils font.


Les deux langages utilisés sont PLSQL et JAVA. On peut très bien tirer des informations sans les connaître du tout, un peu comme on place assez facilement les coins, puis les bords d'un puzzle. On n'aura pas l'image complète, mais certaines informations apparaîtront.


Prenons par exemple le fichier ConnecteurDonneesAppelOracle.java [2] qui se trouve dans /java/parcoursup/ordreappel/donnees/ . Le bout de code ci-dessous, va sélectionner (SELECT) des informations dans des tables (FROM) avec des conditions (WHERE). 


Dans les informations qui sont sélectionnées, on note deux variables intéressantes : 
  • Le candidat est-il boursier ?
  • Est-ce un résident (c'est-à-dire quelqu'un habitant dans l'académie) ?

On note aussi des commentaires qui font penser à un jeu vidéo : 
 //dossier non-annulé (décès...)
+ " AND   c.g_ic_cod >= 0"


Il est aussi intéressant de voir que le décret du 18 mai autorisant à ne pas classer les candidats est codé. Il n'était pas indispensable de créer de l'angoisse chez les candidats en brandissant hache de guerre ou araignée dans les formations où l'on sait qu'il y a assez de place. 


Ce commentaire lié au décès m'a immédiatement fait penser aux tueries aux USA. Non, ce n'est pas bien de tuer ses camarades qui sont devant soit sur liste d'attente ! Charlie Hebdo a eu une bonne intuition...

Une recherche scientifique.

La bonne et la mauvaise nouvelle, c'est que ce bout de code est fait par un chercheur, Hugo Gimbert, dont l'adresse email est en début de pas mal de fichiers. Il a dû résoudre des problèmes complexes, comme la question des internats. Il a optimisé pas mal de choses, pour que ça aille plus vite. Procédure linéaire ou quadratique ? Quand 800 000 utilisateurs font 10 vœux, la base de données prend des proportions qui nécessitent de se poser ces questions métaphysiques. L'ordre d'appel des candidats est calculé par deux méthodes, ce qui permet de vérifier que le résultat est le bon. 

Si l'on peut se réjouir d'avoir une personne très compétente aux manettes, qui dit recherche, dit expérience. Pour résumer, on ne sait pas si l'algorithme de Parcoursup est meilleur que l'algorithme des mariages stables utilisé pour APB, et beaucoup de spécialistes en doutent [4]. On vérifie cette hypothèse grâce aux 800 000 candidats qui servent de cobayes. Nul doute que l'on va modéliser leur comportement. Quand un candidat reçoit une seule proposition, est-ce qu'il conserve les vœux pour lesquels il est en attente ? S'il ne le fait pas, il ne libérera aucune place tant qu'il n'aura pas reçu une proposition pour un autre de ses vœux.

Un jeu de stratégie

On peut imaginer qu'un ado soit incapable de dire s'il préfère PACES (médecine) ou STAPS (sport). Il va accepter la première proposition qui lui sera faite, tout en restant sur liste d'attente "au cas où", un peu comme dans ce jeu, il va cliquer sur le premier objet qu'il voit, mais sans forcément avoir de préférence pour l'un ou l'autre.

Pour avoir le choix le plus longtemps possible, il a intérêt à prendre son temps, à rester sur les listes d'attente tant qu'aucune nouvelle proposition ne lui est faite, histoire de se laisser la possibilité de comparer deux formations. S'il accepte STAPS et renonce à PACES où il est en liste d'attente, en regardant ses élèves jouer au foot, il pourra se dire "Peut-être que j'aurais pu être médecin".

Mais ceci n'est pas dans l'intérêt de la société... Parcoursup pourrait se transformer en Titanic, ou du moins évoluer très lentement. Les lycéens ont intérêt à prendre un tableur et à noter chaque jour leur position, histoire de vérifier à quelle vitesse la file d'attente diminue.


Le classement pédagogique chamboulé.

On a des témoignages du style "Mon fils à 19/20 en maths, mais il est 300e sur liste d'attente". Ce qui s'affiche dans Parcoursup, c'est l'ordre d'appel, qui se base sur le classement pédagogique, mais essaye à chaque itération de respecter le taux de boursier (par exemple 20%) et le taux de résidents s'il existe. 

Imaginons un classement pédagogique comme ci-dessous :
Il y a 12 candidats, et 3 boursiers. S'il y a 1 place par exemple, on ne respectera pas le taux de 20%. Il faut donc placer Bernard avant Elsa.


Si on appelle 5 candidats, c'est OK, mais si on doit en appeler 6, on ne respectera pas le taux de 20% de boursiers. Franck passe donc de la 11ième à la 6ième position.


Cet ordre d'appel est calculé une fois pour toutes en début de procédure, dès que le classement pédagogique est connu. Même si les boursiers refusent les propositions, il y aura toujours eu 20% de boursiers appelés.

Quel partie du code avons-nous ? 

Comme le signale Guillaume Ouattara, nous n'avons qu'une partie du code [5].   Dans l'exemple ci-dessus, si on avait appelé les 12 candidats sans les classer, on aurait eu les 20% de boursiers, et surtout, beaucoup de temps aurait été gagné.

Dans la plupart des universités, le classement pédagogique a été établi avec des algorithmes dont on ne sait rien. Pourquoi Elsa est-elle classée devant Charb qui est devant Cabu ? Le code qui n'a pas été publié et ne le sera jamais, c'est celui qui a permis d'établir le classement pédagogique. Il doit y avoir quelques horreurs dedans.

Par exemple il semblerait que les économistes aient deviné les notes des candidats au bac en tenant compte du lycée d'origine. Or il n'existe pas de corrélation entre les notes de l'années (en gros la capacité à recracher la leçon vue hier), et celles du bac. Dans ce graphique fourni par F. Tétard [3], nous avons en abscisse les notes du bac en math, en ordonnée la moyenne sur l'année des notes en math, pour des terminales S, appartenant à des lycées ayant de 95% à 100% de réussite au bac.


Si on prend les candidats qui ont eu 16/20 au bac, leur moyenne s'échelonne de 3 à 18.  Pour les STAPS, le même programme aurait été utilisé sur toute la France.

Cela dit, cet algorithme nous apprend que les universités pouvaient prendre tout le monde, surtout s'il n'y a pas eu de tirage au sort l'année dernière.


Une initiative à encourager

La publication du code sur framagit est une très bonne chose. La réactivité du seul développeur, à savoir Hugo Gimbert est à saluer. Il a résolu des problèmes complexes en voulant remplacer l'algorithme des mariages stables utilisé par APB. Il répond aux questions, corrige son code, qui par conséquent s'améliore grâce aux citoyens. 

La lecture du code nous apprend que l'ordre d'appel des candidats n'est pas du tout le classement pédagogique, que des universités ont pu classer tout le monde égaux, que le décès d'un candidat est envisagé, ou que le surbooking est possible..

Mais c'est vraiment une toute petite partie du code. On attend le reste ! Si cette partie algorithmique semble d'une bonne qualité, l'interface web, c'est une autre affaire. J'espère que les parents qui lisent pas ou peu le français trouveront de l'aide.

Mettre des lycéens au cœur d'un test à l'échelle nationale est soit très amusant si on voit le côté jeu vidéo, soit sadique. Si le résultat de l'expérience Parcoursup est catastrophique, des milliers de jeunes se retrouveront sans solution. Ils auront juste passé le bac la mauvaise année. 

  1. Maj Doc Algo
  2. ConnecteurDonneesAppelOracle.java
  3. Tweet de F. Tétard
  4. Ertzscheid, Olivier (24 mai 2018). "Le jeune président de la Start-up Nation était en fait un vieux con comme les autres". Affordance.info [carnet de recherche]. ISSN 2260-1856. Consulté le 25 mai 2018. http://affordance.typepad.com/mon_weblog/2018/05/jeune-president-vieux-con.html
  5. Ouattara, Guillaume  (22 mai 2018) "Que révèle une première analyse du code source de Parcoursup ?"

Commentaires

Guillaume Haeringer a dit…
On peut difficilement comparer l’algorithme d’APB avec celui de parcoursu. Les algorithmes de parcoursup ne servent qu’à déterminer les choix des formations. On a à faire ici à un problème de many-to-one matching, il faut donc rajouter une fonction de choix du côté des formations. APB faisait la même chose, mais en plus APB calculait une affection, ce que les algorithmes de parcoursup ne font pas. Avec parcoursup on a un mécanisme de matching décentralisé, on ne peut donc pas garantir la stabilité du matching final.
Autre erreur souvent vue dans les commentaires sur APB: celui-ci n’optimisait pas, stricto sensu, les préférences des candidats car il utilisait la version formations proposant de l’algorithme d’acceptation différée (mais pour des problèmes de cette taille il n’y a en général qu’un seul matching stable, donc il est probable que APB donne aussi le matching student-optimal).
Elisabeth a dit…
Merci pour ce commentaire. Je viens de comprendre le problème d'un algorithme décentralisé. En gros Parcoursup fait la moitié du boulot par rapport à APB, parce qu'il n'a pas les données nécessaires pour libérer une place ou non après qu'un candidat ait accepté une formation.
Le candidat est obligé d'agir à partir du moment où il a au moins 2 propositions. Il doit en choisir une seule. Ce n'est qu'à ce moment là que les places se libèrent.
Guillaume Haeringer a dit…
Presque. Si un étudiant n’a qu’une offre et il l’acce alors il/elle est éliminé(e) des autres formations, et donc fait remonter d’un cran tous ceux wui sont en liste d’atte En dessous de cet étudiant. Mais ce n’est vrai que si l’etudiant accepte définitivement la proposition.
Unknown a dit…
@Guillaume: sur les données APB2017, d'après mes calculs, les matchings formation-optimal et students-optimal ne sont pas exactement les mêmes mais sont extrêmement proches.

Le matching calculé au jour le jour par parcoursup converge très exactement vers le matching qui aurait été calculé par APB (en tenant compte des démissions). En supposant les préférences des étudiants indépendantes du temps, hypothèse non-satisfaite ni dans APB et ses trois phases, ni dans Parcoursup et ses n phases.

En simulation le matching Parcoursup converge rapidement vers le matching APB. Les observations actuelles sur les temps de réponse nous placent au dessus d'un scénario optimiste.
Unknown a dit…
Avant d atteindre un matching optimal et stable, il faut passer par une succession de matchings sous-optimaux. Dans APB ces matchings sous optimaux étaient juste des étapes de calcul stockées dans la mémoire de l'ordinateur. Avec Parcoursup, toutes ces étapes sont visibles au jour le jour. Les propositions sont traitées par les candidats et non pas par l'ordinateur.
Elisabeth a dit…
Je viens de rédiger un nouvel article suite à cet échange. N'hésitez pas à signaler des erreurs.