Algorithmes pour les systèmes de fermeture et leurs représentations

Ce travail prend racine dans la théorie des espaces de connaissances (Doignon et Falmagne, 1985 ; Doignon et Falmagne, 2012 ; Falmagne et Doignon, 2010), à l’intersection de la psychologie mathématique, dont le but est de proposer des modélisations mathématiques des processus cognitifs (entre autres), et de l’informatique. L’objectif principal de la théorie des espaces de connaissances est d’utiliser l’outil informatique pour aider les enseignant(e)s dans le processus d’évaluation des élèves. Plus précisément : pour évaluer les connaissances d’un(e) élève, un(e) enseignant(e) va poser des questions relatives à des problèmes particuliers de la matière en question. Les questions auxquelles l’élève est capable de répondre délimitent l’état actuel de ses connaissances. Maintenant, pourrait-on utiliser l’outil informatique pour assister l’enseignant(e) dans ce processus ? L’élève serait devant un ordinateur qui lui proposerait des questions sélectionnées dans une base de données appropriée. En fonction des réponses de l’élève, l’ordinateur identifierait ensuite l’état de connaissance approprié parmi une liste d’états stockée dans sa mémoire. Le système ALEKS aux États-Unis repose sur ce principe.

La théorie des espaces de connaissances vise à formaliser et mettre en place ce processus. Pour ce faire, il faut d’abord représenter les objectifs pédagogiques d’une matière scolaire par une liste de problèmes (ou items) que les élèves devront in fine maîtriser. Tous les items auxquels un(e) élève est capable de répondre correctement constituent son état de connaissance. Non seulement cet état de connaissance permet de situer les forces et faiblesses de l’élève, mais il devrait également permettre de cibler les prochains items à apprendre. Bien sûr, certains items dépendent d’autres, et donc l’apprentissage ne peut se faire dans n’importe quel ordre. Ce faisant, certains groupes d’items ne peuvent représenter un état de connaissance pertinent. La collection de tous les états de connaissance possibles devient un espace de connaissance quand elle respecte la propriété suivante : l’union de deux états de connaissance est aussi un état (fermeture par union). Cette hypothèse semble arbitraire, mais elle n’est pas insensée : il semble naturel d’estimer que si un élève est dans un état de connaissance A, et une élève dans l’état B, alors les deux peuvent progresser jusqu’à maîtriser tous les items de A et B. Mais surtout, la fermeture par union permet de bénéficier de deux outils mathématiques pour aborder les espaces de connaissances plus efficacement. En effet, l’utilisation de ceux-ci pose, entre autres, deux questions majeures :

1. comment déterminer avec justesse les états d’un espace de connaissance ?
2. comment peuvent-ils être stockés dans la mémoire d’un ordinateur ?

Nous arrivons finalement aux questions de cette étude. Nous disposons de deux représentations différentes pour un même espace de connaissance : des implications (ou requêtes) et sa base. Les interactions entre ces deux représentations constituent le cœur de ce travail de recherche. Nous nous sommes principalement intéressés aux deux questions suivantes :

1. comment passer d’une représentation à l’autre ?
2. comment trouver les états de connaissances satisfaisant des contraintes (ensemblistes) sur les items ?

Dans la section suivante, nous donnons une vision plus fine de ces deux problématiques.

Question 1 : comment passer d’une représentation à l’autre ? Ou plus précisément, comment traduire entre les différentes représentations d’un espace de connaissance (système de fermeture/treillis). Dans le contexte des espaces de connaissances, ce problème est surtout utile quand il s’agit de trouver les atomes d’un espace de connaissance depuis un ensemble d’implications qui seraient données par exemple par des enseignant(e)s. Les atomes constituent en général une description plus fidèle, car unique, de l’espace de connaissance correspondant.

Il s’avère que le problème de traduction a suscité beaucoup d’intérêt ces trente dernières années (Adaricheva et Nation, 2017 ; Babin et Kuznetsov, 2013 ; Beaudou et al., 2017 ; Khardon, 1995 ; Mannila et Räihä, 1992 ; Wild, 1995).

Premièrement, il est crucial quand il s’agit d’utiliser la représentation la plus compacte possible. En général, un ensemble d’implications ou l’ensemble des atomes, la base, sont plus concis que l’espace de connaissance lui-même. En revanche, en comparant la taille des représentations l’une à l’autre, il peut arriver que le nombre d’atomes soit exponentiel par rapport au nombre (minimum) d’implications, et vice-versa (Kuznetsov, 2004 ; Mannila et Räihä, 1994). Au delà des frontières des espaces de connaissance, le choix de la représentation impacte la complexité de nombreux problèmes, donnant au problème de traduction un caractère essentiel. Par exemple en base de données, décider si un élément appartient à une clé est difficile si l’on utilise des implications (Lucchesi et Osborn, 1978), mais aisé depuis la base (Bertet et al., 2018). La complexité de reconnaître une classe d’espace de connaissance dépend également du choix de la représentation. En effet, de nombreuses propriétés peuvent être identifiées en un temps raisonnable (polynomial) depuis la base de l’espace : la distributivité (Birkhoff, 1937), la semi-modularité (Stern, 1999), la semi-distributivité ainsi que la sup/inf-distributivité (les géométries convexes) (Beaudou et al., 2017 ; Edelman et Jamison, 1985 ; Habib et Nourine, 2018 ; Nation, 2000), l’extrémalité (Markowsky, 1992), les espaces obtenus par duplication (Bertet et Caspard, 2002). Savoir s’il est possible de reconnaître toutes ces propriétés depuis les implications est un problème ouvert, en particulier pour les géométries convexes et les treillis sup-semi-distributifs. Un autre exemple où le choix de la représentation est prépondérant est celui de l’abduction en logique propositionnelle. Si la tâche peut être menée à bien en temps polynomial depuis les atomes, elle devient beaucoup plus complexe depuis un ensemble d’implications (Kautz et al., 1993).

Question 2 : comment trouver les états de connaissances satisfaisant des contraintes (ensemblistes) sur les items ? Dans le cadre de notre étude, une contrainte est un ensemble d’items, qui n’est pas nécessairement un état de l’espace. Ainsi, une contrainte peut être assimilée à une compétence plus complexe que des items seuls. Un état de connaissance satisfait cette contrainte quand il contient au moins un des items qui la compose. Autrement dit, pour qu’un état soit satisfaisant, il doit contenir au moins un des items présents dans la compétence (contrainte) en question. Si l’état de connaissance d’un(e) élève satisfait toutes les contraintes, alors l’élève a au moins entamé l’apprentissage de toutes les compétences.

Étant donné un espace de connaissance représenté par des implications ou sa base, et une collection de contraintes, nous nous intéressons aux deux problèmes suivants :
P1 trouver les états de connaissances admissibles, c’est-à-dire ceux qui satisfont toutes les contraintes.
P2 parmi les états admissibles, trouver les plus petits possibles, que l’on appelle préférés (les termes admissibles et préférés sont issus du langage de l’argumentation ; voir Dung, (1995) et Dunne et al., (2015)).

Les états préférés sont une représentation compacte de tous les états admissibles, ce qui les rend plus intéressants. D’ailleurs, il est possible que le nombre d’états admissibles soit exponentiel par rapport au nombre d’états préférés. Ce faisant, résoudre le problème P1 ne permet pas de résoudre le problème P2 en un temps raisonnable en général, car il faudrait « jeter » tous les admissibles qui ne sont pas préférés. Par contre, résoudre le problème P2 permet ensuite de résoudre le problème P1 facilement.

Comme pour la traduction, utiliser des contraintes comme nous les avons définies est très commun en informatique (Chepoi, 2012 ; Davey et al., 1975 ; Dunne et al., 2015 ; Mignosi et al., 2002 ; Schäffter, 1997 ; Stork et Uetz, 2005). En général, lister les états admissibles est un problème plus général que celui de lister tous les états de connaissance de l’espace. Ce problème-ci a été très largement étudié dans la littérature (Bordat, 1986 ; Demko et al., 2020 ; Ganter et Wille, 2012 ; Kuznetsov, 1996 ; Kuznetsov et Obiedkov, 2002 ; Nourine et Raynaud, 1999). Lister les états préférés est un problème qui englobe quant à lui la dualisation des hypergraphes (Eiter et Gottlob, 1995 ; Eiter et al., 2008 ; Fredman et Khachiyan, 1996) et plus largement la dualisation des systèmes de fermeture (Babin et Kuznetsov, 2017 ; Defrain et Nourine, 2020). Il apparaît aussi dans des formes restreintes dans de divers domaines de l’informatique. Par exemple, des implications et des contraintes de taille 2 servent à encoder les semi-treillis médians et modulaires (Barthélemy et Constantin, 1993). Ceci sont ensuite utilisés pour les structures événementielles (Chepoi, 2012 ; Nielsen et al., 1981), les complexes cubiques (Ardila et al., 2012), ou pour les fonctions k-sous-modulaires (Hirai et Nakashima, 2020 ; Hirai et Oki, 2018). Dans ce dernier cas, résoudre le problème P2 revient à trouver les minimiseurs maximaux de ces fonctions.

Question 1 : Commençons par le problème de traduction. À ce jour, il est grand ouvert, même dans des espaces de connaissance très restreints. Il est intéressant de noter qu’il est plus difficile que le problème de la dualisation des hypergraphes (Khardon, 1995), pour lequel le meilleur algorithme connu a un temps d’exécution total quasi-polynomial (Fredman et Khachiyan, 1996). On trouvera un acompte détaillé de tous les résultats disponibles dans les revues de littérature (Bertet et al., 2018 ; Wild, 2017). Nous nous sommes particulièrement intéressé au cas où les implications sont dites « acycliques » : s’il y a un « chemin » de l’item 1 vers l’item 2 dans les implications, alors il n’y a pas de chemin de l’item 2 vers l’item 1. Cette hypothèse semble naturelle dans la mesure où elle permet d’éviter à des items d’être mutuellement dépendants les uns des autres. Notre approche ici est de décomposer hiérarchiquement, si possible, un ensemble d’implications par le prisme de partitions appelées splits. Nous déduisons ainsi une caractérisation récursive des atomes du système de fermeture associé. En conséquence, nous obtenons de nouveaux types de systèmes de fermeture (et de géométries convexes) pour lesquels la traduction peut être effectuée en temps total quasi-polynomial au moyen d’un algorithme reposant sur la dualisation des hypergraphes (Fredman et Khachiyan, 1996). Ces résultats ont fait l’objet de communications et d’un article en cours de relecture (Nourine et Vilmin, 2020a ; Nourine et Vilmin, 2020b ; Nourine et Vilmin, 2022). Une autre contribution en amont de ces résultats a mené à une publication dans un journal (Defrain et al., 2021).

En bref : Pour le problème de traduction, nous nous sommes concentrés sur les espaces de connaissances dans lesquels les items ne sont pas mutuellement dépendants. Ces espaces sont intéressants car il semble naturel de faire en sorte qu’au cours de l’apprentissage, il n’y ait pas de « boucle » dans les prérequis des items à maîtriser. Dans ce contexte-là, nous avons proposé un nouvel outil théorique qui nous permet de mieux comprendre la structure de tels espaces, et ce faisant d’améliorer la découverte des atomes si l’on nous donne accès à des implications représentants les dépendances entre items.

Question 2 : Passons à l’énumération des états admissibles et préférés. L’énumération des états admissibles revient en fait à énumérer tous les états de connaissance d’un autre espace. Les représentations de cet espace alternatif peuvent être dérivées très facilement à partir de celles de l’espace initial. Il apparaît donc que le problème P1 est simple à résoudre, et est un corollaire direct de résultats préexistants (Bordat, 1986 ; Demko et al., 2020 ; Ganter et Wille, 2012 ; Kuznetsov, 1996 ; Kuznetsov et Obiedkov, 2002 ; Nourine et Raynaud, 1999). Le problème P2 quant à lui se révèle très vite être équi- valent à la dualisation des systèmes de fermeture. Malheureusement, quelle que soit la représentation choisie (implications/atomes), le problème de dualisation ne peut être résolu en général en temps total polynomial à moins que P = NP (Babin et Kuznetsov, 2017 ; Defrain et Nourine, 2020 ; Kavvadias et al., 2000). Pour cette raison, nous avons restreint notre étude au cas où toutes les contraintes ne contiennent que deux items (des paires d’items). En apparence, cette restriction semble simplifier le problème. Cependant, nous montrons qu’il n’en est rien puisque si des implications sont données, le problème reste impossible à résoudre, même dans les treillis obtenus par duplications de pseudo-intervalles. Aussi, nous prouvons que dans de nombreuses classes d’espace de connaissance généralisant la propriété de distributivité, le problème Q2 restreint reste équivalent à la dualisation dans les classes en question. En particulier, il reste plus difficile à résoudre que le problème de la dualisation des hypergraphes. Ces résultats contrastent avec certains résultats positifs antérieurs (Hirai et Nakashima, 2020 ; Hirai et Oki, 2018 ; Kavvadias et al., 2000) sur les semi-treillis médians et modulaires. D’un autre côté, nous utilisons un algorithme basé sur un paramètre particulier, le nombre de Carathéodory d’un système de fermeture, pour identifier des classes d’espace de connaissance où le problème d’énumération des états préférés par rapport à des contraintes de taille 2 peut être résolu en temps total polynomial. Avec le même algorithme, nous démontrons que cette tâche peut être réalisée en temps total quasi-polynomial dans les treillis modulaires atomiques. Une partie de ces résultats a été présentée dans une conférence internationale à comité de lecture (Nourine et Vilmin, 2021).

En bref : Nous avons cherchés à énumérer les (plus petits) états de connaissances satisfaisant certaines contraintes du type « l’état doit contenir au moins un des items parmi ceux composant telle compétence » (une compétence est juste un ensemble d’items). Nous avons montré que même si les compétences sont seulement des groupes de deux items, énumérer ces états est extrêmement difficile. Cependant, si l’on est capable de borner une propriété des espaces de connaissance, nous parvenons à résoudre ce problème d’énumération en un temps raisonnable dans un certains nombres d’espaces de connaissances particuliers.

Les dernières décennies ont vu l’informatique s’investir dans de nombreux aspects de la vie quotidienne. L’éducation et les processus pédagogiques ne sont pas étrangers à ces changements. À ce titre, la théorie des espaces de connaissances est un domaine au carrefour de la psychologie mathématique et de l’informatique qui a pour l’objectif d’évaluer et représenter les connaissances des élèves. Au cœur de cette théorie se trouvent les espaces de connaissances. Ces structures sont équivalentes à des objets combinatoires bien connus : les systèmes de fermeture (ou treillis). Implémenter les espaces de connaissance, comme c’est le cas avec le système ALEKS aux États-Unis, donne naissance à des défis théoriques fascinants, et ce malgré la puissance des ordinateurs actuels.

En effet, les espaces de connaissance souffrent notamment de leur taille, et il faut donc trouver des moyens compacts de les représenter. Dans cette thèse, nous avons étudié deux représentations : des implications ou la base. Plus précisément, nous avons travaillé sur le problème de traduction entre les représentations et sur un problème d’énumération sous contraintes. D’une part, la présence de ces questions dans de nombreux domaines de l’informatique et des mathématiques renforce leur caractère fondamental.

D’autre part, la littérature existante et les recherches que nous avons conduites témoignent de leur complexité. En somme, travailler sur ces questions d’ordre théorique ne permet pas seulement de mieux com- prendre la nature des liens unissant divers langages et objets mathématiques, mais aussi de contribuer à rendre les outils informatiques appliqués à l’éducation plus rapides, plus efficaces, et moins coûteux.