=Paper=
{{Paper
|id=Vol-2133/cnia-paper3
|storemode=property
|title=Apprentissage par analogies grâce à des outils de la théorie des catégories(Learning through analogies using tools from category theory)
|pdfUrl=https://ceur-ws.org/Vol-2133/cnia-paper3.pdf
|volume=Vol-2133
|dblpUrl=https://dblp.org/rec/conf/rjcia/AmarBCELPP18
}}
==Apprentissage par analogies grâce à des outils de la théorie des catégories(Learning through analogies using tools from category theory)==
https://ceur-ws.org/Vol-2133/cnia-paper3.pdf
Apprentissage par Analogies grâce à des outils de la Théorie des Catégories
L. Cordesses1 O. Bentahar1 K. Poulet1 A. Laurent1 S. Amar1 T. Ehrmann1 J. Page2
1
Renault Innovation Silicon Valley, 1215 Bordeaux Drive, Sunnyvale, 94089 CA, USA
2
CNRS-Université Paris Diderot, Laboratoire SPHERE, 5 rue Thomas Mann, 75205 Paris cedex 13
{lionel.cordesses, kevin.poulet, thomas.ehrmann}@renault.com,
{aude.laurent, sarah.amar, omar.bentahar}@nissan-usa.com,
ju.page@hotmail.fr
Résumé moins en moins de données. Les solutions à base d’appren-
tissage par renforcement, avec des réseaux de neurones par
Les algorithmes d’apprentissage automatique utilisés pour
exemple, ont fait leurs preuves. Cependant, ces méthodes à
contrôler des systèmes physiques doivent pouvoir ap-
la pointe de la recherche ont besoin de beaucoup de don-
prendre rapidement, avec peu d’exemples, notamment
nées d’entraînement, données que l’on risque de ne pas
lorsque le coût ou la durée des expérimentations sont trop
pouvoir obtenir si l’on respecte des contraintes budgétaires
importants. Un tel objectif peut être atteint en utilisant des
et temporelles.
concepts provenant des sciences cognitives et des sciences
sociales, et formalisés grâce à des outils mathématiques de Nous proposons ici une approche complémentaire à l’ap-
la théorie des catégories et de la théorie du contrôle. prentissage par renforcement et aux réseaux de neurones
Ce formalisme aboutit à un système d’apprentissage auto- pour permettre aux machines d’apprendre rapidement avec
matique qui accumule les connaissances, puis les trans- des puissances de calcul réduites. L’objectif est d’être aussi
pose à de nouvelles configurations. Cette approche est performant que les solutions existantes avec environ un
illustrée sur un système cyber-physique (un circuit de voi- pour cent des données et du temps d’entraînement usuels.
tures), et sur les jeux Atari 2600. L’aspect novateur de notre travail repose sur l’utilisation
d’outils élémentaires de la théorie des catégories — une
Mots Clef branche des mathématiques datant des années 1940, assez
peu utilisée en apprentissage automatique (en anglais : Ma-
Apprentissage Automatique, Théorie des Catégories, Atari
chine Learning) — pour formaliser notamment la notion
2600, Circuit de voitures miniatures.
d’analogie. La théorie des catégories a été conçue en lien
Abstract avec la topologie algébrique, pour permettre de transférer
des théorèmes et des concepts d’une branche des mathé-
Machine learning algorithms for controlling devices need
matiques à une autre [28]. Nous utilisons ces outils pour
to learn quickly, with few trials, when limited by the dura-
avoir un cadre générique pour notre approche d’apprentis-
tion and cost of experiments. Such a goal can be attained
sage automatique, ce qui permet, par exemple, de formali-
with concepts borrowed from Cognitive Science and Social
ser rigoureusement le transfert de connaissances.
Science, and formalized mathematically using tools from
Par ailleurs, nous pensons qu’il est fondamental de recher-
Category Theory and Control Theory.
cher des structures dynamiques pour construire une intel-
This leads to a machine learning system that accumulates
ligence artificielle (IA) adaptative. Les sciences sociales et
knowledge, then transposes it to new configurations. Illus-
les sciences cognitives montrent que les structures dyna-
trations of this approach are presented on a cyber-physical
miques cadrent la cognition (cf. [22]), les langues (cf. [8])
system – the slot car game – and also on Atari 2600 games.
et les interactions sociales (cf. [26]). En effet, ces structures
Keywords permettent aux humains d’agir et de s’adapter en fonction
des expériences passées.
Machine Learning, Category Theory, Atari 2600, Slot Car.
Dans cet article, nous commençons par étudier les mé-
thodes d’apprentissage automatique pour les processus dé-
cisionnels markoviens (MDP) appliqués à des jeux. En-
1 Introduction suite, nous expliquons les motivations qui supportent notre
Les algorithmes qui contrôlent des systèmes cyber- approche inspirée des sciences sociales. Grâce au concept
physiques doivent apprendre comment opérer rapidement d’équivalence de catégories, nous décrivons des classes de
dans un environnement partiellement connu, le tout avec de problèmes non bijectifs, sur lesquels nous centrons notre
approche. Il en résulte un comportement innovant de l’al- renforcement inverse [13], et l’apprentissage par imitation
gorithme de contrôle. Enfin, nous illustrons cette approche [20] peuvent également être utilisés pour entraîner un agent
avec des résultats sur un circuit de voitures miniatures, et au comportement plus humain, qui a une efficacité et une
sur des jeux vidéo Atari 2600. Notre méthode utilise égale- réussite proches de celles des méthodes susmentionnées.
ment le savoir accumulé tout au long des expériences pas- Les « Schema Networks » [11] font un pas supplémen-
sées, et peut donc servir à valider des concepts modernes taire en direction du transfert de connaissances et de la ré-
tels que le « lifelong machine learning » [5]. duction des besoins en données et en puissance de calcul
pour l’entraînement, en utilisant un simulateur physique et
2 Travaux antérieurs en travaillant à un niveau plus élevé avec des entités plu-
tôt que des pixels. Cette méthode obtient le même score
Nous avons décidé de tester notre approche sur un cir- qu’un joueur humain sur Breakout (30 points) avec 100 000
cuit de voitures miniatures et sur des jeux vidéo Atari, car images d’entraînement.
ces deux expériences impliquent de prendre des décisions,
tâche plus complexe que la classification pure. Dans ce 3 Sciences Sociales, Sciences Cogni-
contexte, les approches d’apprentissage automatique appli-
quées à la prise de décision reposent souvent sur de nom- tives et Théorie du contrôle pour
breux essais, ce qui implique de grandes quantités de don- l’apprentissage automatique
nées d’entraînement et requiert une grande puissance de
calcul. Pour atteindre notre objectif de réduction des besoins en
D’autre part, les jeux sont devenus un banc d’essai clas- données d’entraînement et en puissance de calcul, nous
sique pour les algorithmes d’IA. Les circuits de voitures avons basé notre IA sur des concepts de haut niveau déjà
miniatures, par exemple, sont utilisés pour évaluer la per- étudiés par différentes sciences.
formance des systèmes de prise de décision. Le traitement Tout ce qui est produit par l’humain contient, en partie,
d’images basé sur de l’apprentissage par renforcement pré- une certaine structure humaine. Par exemple, lorsque des
senté dans [12] estime la position de la voiture sur le cir- humains conçoivent un jeu, ils utilisent des règles impli-
cuit grâce à un perceptron multicouche à convolution. L’en- cites qui leur permettent de jouer et de s’amuser. Cela si-
traînement prend 12 h et l’apprentissage de la stratégie de gnifie que ces jeux, comme les autres créations humaines,
contrôle requiert 30 min supplémentaires. La solution plus contiennent un minimum de structure pour que le joueur
rapide proposée par [24] pour le même système de circuit humain puisse les comprendre, et ils contiennent égale-
de voitures autonome dépend d’accéléromètres et d’un mi- ment de la dissonance cognitive pour les rendre attractifs
crocontrôleur rajoutés sur la voiture pour d’abord créer une [6][25][27]. La plupart des problèmes réels possèdent cette
cartographie du circuit, puis ensuite contrôler la vitesse de ambivalence.
la voiture. Parmi les structures clés, on retrouve les schémas cognitifs
Les jeux vidéo sont aussi devenus de plus en plus utiles universels auxquels les humains s’attendent quant aux ob-
pour fournir une représentation cyber-physique de notre jets et à l’environnement : état intérieur (intention et affect),
environnement. Même des systèmes anciens, tels que la propriétés matérielles (gravité, conservation de la forme,
console Atari 2600, fournissent une grande diversité de si- continuité de la trajectoire) ou propriétés naturelles non-
tuations, allant des labyrinthes (jeux de style Pac-Man) et humaines (mouvement et croissance). Ces schémas cogni-
jeux d’action (tel que Space Invaders) aux jeux de balle et tifs sont acquis durant l’enfance quand l’enfant découvre
raquette (Breakout, Pong). Malgré le fait que ces différents le monde au fil de ses mouvements et en utilisant ses sens
problèmes réclament des stratégies variées pour être réso- [22].
lus par un joueur humain standard, ils impliquent tous des Nous supposons qu’une IA ayant la connaissance de ces
prises de décision et ont donc été modélisés par des MDPs schémas cognitifs serait capable de prendre les bonnes dé-
[18]. Ce cadre permet l’implémentation de nombreuses cisions pour jouer, et de transférer les connaissances ac-
méthodes différentes. Certains travaux, tel que celui pré- quises à une grande variété de problèmes similaires.
senté dans [18], utilisent une image de l’aire de jeu remise
3.1 Entités dans le temps et dans l’espace
à l’échelle en entrée d’un « deep Q-network » (DQN), avec
pour but de sélectionner la meilleure action à jouer. Une Nous avons conçu notre IA pour qu’elle raisonne au niveau
autre possibilité est l’utilisation de méthodes classiques de syntaxique et non au niveau de l’échantillon ou du pixel.
recherche et de planification, telles que le « Iterated Width D’une certaine manière, cela correspond à raisonner au ni-
algorithm » [16] ou les algorithmes de parcours d’arbre veau du morphème en linguistique, défini dans [8] comme
tels que l’algorithme de recherche arborescente Monte- le plus petit élément significatif d’un langage. Nous appe-
Carlo [21] pour calculer la meilleure action possible. L’ap- lons entités les éléments de base de ce niveau syntaxique.
prentissage par renforcement peu profond [15] repose sur Ces entités sont détectées par des outils classiques de trai-
une représentation linéaire simplifiée, mais obtient cepen- tement du signal et d’apprentissage automatique. Elles sont
dant des résultats similaires aux méthodes non-linéaires. comme les objets de notre vie de tous les jours : des tron-
Enfin, l’apprentissage maître-élève [3], l’apprentissage par çons de circuit (lignes droites et virages), des voitures, des
balles, des raquettes, des murs. Elles sont organisées géo- 4 La Théorie des Catégories comme
métriquement dans un espace et peuvent être décrites, par
exemple, par les coordonnées cartésiennes de leur boîte en-
cadre pour des analogies non bijec-
globante. tives
Les données caractérisant ces entités sont collectées à L’un des outils les plus efficaces dont dispose l’humain
chaque échantillon de temps pour construire des modèles pour évoluer dans une situation inconnue est sa capacité
dynamiques décrits par les équations d’état (1) à temps dis- à faire des analogies entre cette nouvelle situation et ses
cret pour un système d’ordre Nd , où x est le vecteur d’état, expériences passées. Nous pressentons qu’une IA capable
y la mesure, u la commande, A la matrice d’état, B la ma- d’établir des analogies, et sachant, par exemple, comment
trice de commande, C la matrice d’observation, D la ma- jouer au jeu Breakout sera capable de transposer ses capa-
trice d’action directe, et k l’indice de l’échantillon. cités au jeu Pong, même si les aires de jeu et les règles ne
sont pas identiques, à l’instar d’un joueur de tennis qui sau-
x(k + 1) = Ax(k) + Bu(k) rait au moins partiellement comment manier une raquette
(1) de badminton même s’il n’a jamais pratiqué ce sport.
y(k) = Cx(k) + Du(k)
Les situations où deux problèmes ont exactement le même
nombre d’états et des structures isomorphes sont rares. La
3.2 Le Moi au sein du monde notion d’analogie semble alors adaptée au rapprochement
de structures conceptuellement proches mais mathémati-
Une étape clé pour se forger une identité propre lors du quement différentes. Or, la plupart des tentatives de for-
développement de l’enfant est appelée le stade du miroir. malisation de cette notion sont fondées sur une perspec-
Nous avons conçu notre IA pour qu’elle commence à ce tive structuraliste qui s’articule autour de la théorie des en-
stade en identifiant le « Moi » parmis toutes les entités. sembles via le concept d’isomorphisme qui préserve les
Cette identification du « Moi » est réalisée en utilisant des structures des ensembles. Il existe des outils mathéma-
résultats de la théorie du contrôle, à savoir le critère de tiques pour identifier des structures non isomorphes tels
contrôlabilité d’un système dynamique, comme présenté, que l’équivalence de catégories en théorie des catégories
par exemple, dans [10]. Le système est complètement [17]. En effet, celle-ci apparaît comme un cadre de travail
contrôlable si et seulement si (ssi) la matrice de contrôla- plus naturel pour aborder la notion structuraliste d’analo-
bilité CNd , [B|AB| . . . |ANd −1 B] est de rang Nd . Nous gie qui considère que les relations entre éléments sont plus
définissons le « Moi » comme étant l’entité qui vérifie le essentielles que les éléments eux-même pour définir des
critère de contrôlabilité. analogies [9]. 1 .
Comme le « Moi » et son environnement peuvent tous les Dans les problèmes qui reposent sur la théorie des en-
deux changer, les modèles établis peuvent ne plus être va- sembles, l’identification se réduit aux relations d’identité
lides. En s’inspirant d’une idée provenant de l’approche et aux cas bijectifs, tandis que la théorie des catégories ap-
scientifique décrite dans [23], selon laquelle il doit être porte des descriptions plus riches des objets, ce qui permet
possible d’invalider un système scientifique empirique par de nouvelles sortes d’identifications. Dans le cadre de cet
l’expérience, nous avons conçu notre algorithme de telle article, nous nous limitons à des concepts très élémentaires
sorte à ce qu’il puisse réfuter ses propres modèles pour les de la théorie des catégories, qui pourraient être décrits en
remplacer par de meilleurs. Le critère pour cette décision termes ensemblistes, tout comme les situations que l’on ex-
est basé sur l’erreur entre les prédictions (basées sur le mo- pose 2 . L’apport de ces travaux est le changement de pers-
dèle) et les mesures. Cette remise en cause ne s’effectue pective conceptuelle que nous croyons prometteur pour le
pas seulement pendant la phase d’apprentissage mais éga- domaine de l’apprentissage automatique 3 .
lement pendant la phase de test. Théorie des catégories. Une catégorie C est une collec-
Une fois que le « Moi » est identifié, notre IA classifie les tion d’objets et de morphismes (ou flèches) entre certains
entités restantes entre amis et ennemis, d’une manière si- de ces objets, munie d’une composition de morphismes, et
milaire à l’apprentissage par renforcement. Elle suit en- peut ainsi être assimilée à un graphe orienté. Si A et B sont
suite une simple stratégie de survie : essayer d’aller vers
ses amis, à part si un ennemi est proche du « Moi », auquel 1. Une autre approche pourrait être l’utilisation de la théorie des mo-
dèles, plus spécifiquement du concept d’équivalence élémentaire [4] dans
cas la première chose à faire est de s’enfuir. la perspective de doter l’IA de raisonnements logiques. Pour un pano-
En résumé, notre IA prend en compte les récompenses de rama philosophique des concepts d’analogie et de raisonnement analo-
gique, voir [1]
son environnement pour classifier les entités, comme en ap-
2. Ce qui n’est pas étonnant puisque la théorie des ensembles et la
prentissage par renforcement. Comme dans des approches théorie des catégories, en tant que propositions mathématiques fondation-
scientifiques empiriques, elle met à jour les classifications nelles de toutes les mathématiques, se fondent mutuellement l’une l’autre.
et les modèles quand les mesures ne sont pas compatibles Chaque concept catégorique doit pouvoir être décrit en termes ensem-
blistes et réciproquement.
avec les prédictions. Enfin, elle décrit au moins une entité 3. Dans une perspective bayésienne, [7] utilise des catégories de pro-
comme étant le « Moi », avec toutes les conséquences que babilités conditionnelles : les objets sont des espaces mesurables et les
cela implique pour sa survie. flèches des noyaux de Markov.
des objets de C, la flèche a : A → B est un isomorphisme f 0 : C 0 → {0, 1} valent 1 si les trajectoires des deux entités
si elle est inversible, i.e s’il existe une flèche b : B → A, d’une paire s’intersectent, et 0 sinon. Ce qui est observé du
telle que ba = IdA et ab = IdB . Dans ce cas, les objets A Moi d’une situation peut alors être supposé du moi d’une
et B sont isomorphes. Les isomorphismes définissent une autre situation par transfert de connaissances. Des observa-
relation d’équivalence sur la classe des objets de C, pour tions ultérieures permettront alors de confirmer ou infirmer
laquelle on note C/ ' son quotient. Aussi, si F : C → C 0 ces suppositions.
est ce qu’on appelle une équivalence de catégories, celle- Une explication plus détaillée et approfondie de la théorie
ci induit une bijection F 0 : (C/ ') → (C 0 / ') entre les des catégories peut être trouvée dans [17]. Son utilisation
classes d’objets isomorphes même si F n’est pas bijective. nous permet de formaliser une grande diversité de jeux et
Dès lors, on n’identifie plus les objets (ou états) un à un de situations.
entre deux situations, mais les types (ou classes d’isomor-
phismes) de ces états. Analogies entre circuits de voitures miniatures. Nous
introduisons les notations suivantes : soient N et N 0 les
Ce procédé peut être utilisé dans le cas de problèmes obser- nombres de segments par configuration du circuit, et C =
vables. En effet, considérons deux ensembles d’états non {s, s ∈ [1, N ]}, C 0 = {s0 , s0 ∈ [1, N 0 ]} les ensembles de
vides C et C 0 sans autre hypothèse sur leur cardinalité. Sup- positions possibles de la voiture sur le circuit, qui ne sont
posons aussi l’existence de deux fonctions d’observations utiles que pour le raisonnement théorique et ne sont pas
f : C → O et f 0 : C 0 → O0 . Quitte à restreindre O utilisés lors des expériences. Soient (u, i)s (resp. (u0 , i0 )s0 )
et O0 , supposons que ces deux fonctions sont surjectives. la tension et le courant mesurés lorsque la voiture passe sur
Pour tout o ∈ O, on dit que les états x ∈ C dont l’ob- la section s (resp. s0 ). Soit 1 ≤ s0 ≤ N (resp. 1 ≤ s00 ≤
servation associée est o (i.e f (x) = o) sont de type To . N 0 ) la position initiale de la voiture dans la configuration
Cela définit une relation d’équivalence Rf sur l’ensemble C (resp. C 0 ). Nous notons k une ligne droite de C et l un
C : ∀x, y ∈ C, x Rf y ssi f (x) = f (y). Transposé dans virage. De même, soient k 0 une ligne droite et l0 un virage
le champ lexical des catégories, cela revient à placer une de C 0 .
flèche inversible entre deux objets x et y de C ssi x Rf y. C
Le joueur peut agir sur (u0 , i0 )0s en utilisant la manette de
devient alors une catégorie, où toutes les flèches sont inver-
jeu, ce qui correspond à la stratégie π 0 définie par (2).
sibles et telle que C/ ' est exactement le quotient C/Rf ,
quotient qui définit aussi l’ensemble des types d’états de (
C. Puisque ces types ont été définis via les observations, la (u0 , i0 )k0 , si s0 est une ligne droite
π 0 (s0 ) = (2)
surjection f : C → O induit une bijection f˜ : (C/ ') → O (u0 , i0 )l0 , sinon
entre l’ensemble de types et l’ensemble d’observations. f˜
est donc l’inverse de la fonction T : O → (C/ '), o 7→ To Nous voulons identifier C et C 0 , pour pouvoir transposer la
qui définit les types To . Le même raisonnement peut être stratégie π 0 de C 0 à C. Les états de C sont les positions s de
reproduit à partir de C 0 et de f 0 . la voiture sur le circuit. De même, les états de C 0 sont les
Enfin, supposons qu’il existe une bijection G : O → O0 positions s0 . Si N = N 0 et s0 = s00 , nous pouvons définir
entre les ensembles d’observation et que O et O0 sont donc une bijection entre C et C 0 et transposer π 0 de manière tri-
de même cardinalité. Ainsi, on peut définir une autre bi- viale. En revanche, si N 6= N 0 ou s0 6= s00 , il est impossible
jection F 0 = f˜0−1 ◦ G ◦ f˜ : (C/ ') → (C 0 / ') de définir une telle bijection.
entre les ensemble de types d’objets, bijection en réalité Cependant, si nous transformons C et C 0 en catégories, en
induite par l’équivalence de catégories F : C → C 0 défi- définissant des morphismes, nous serons capables de dé-
nie comme suit : pour tout x ∈ C, soit o = f (x) et soit finir une équivalence de catégories F : C → C 0 . Dès
x0 ∈ f 0−1 (G(o)), définissons F telle que F (x) = x0 . Si C lors, nous définirons la stratégie π appliquée sur C par
et C 0 ont des cardinaux différents, F ne peut pas être bijec- π = π 0 ◦ F . Pour définir ces morphismes, nous utilisons
tive, mais F 0 l’est. Par construction, F envoie chaque état la fonction observable f définie sur les états s de C comme
x vers un état x0 du même type (modulo G). Cela permet de suit : f : C → {1, 2} avec f = h ◦ g où g et h sont telles
relier les catégories C et C 0 , de telle sorte que si l’on dispose que g(s) = (u, i)s et h ((u, i)s ) = 1 si s est un virage, et
d’une stratégie applicable dans C 0 , elle peut être transposée 2 sinon. f 0 est définie de la même manière sur les s0 de C 0 ,
dans C par la fonction F . c’est-à-dire f 0 : C 0 → {1, 2} avec f 0 = h0 ◦ g 0 et g 0 et h0
sont définies de la même manière que g et h, mais sur les
Si l’on remplace C et C 0 par des ensembles d’entités (option
états de C 0 .
1) ou de paires d’entités (option 2) dans deux (situations
de) jeux différent(e)s, nous pouvons les comparer grâce à Nous définissons un isomorphisme entre deux états de C
des fonctions d’observation du type f et f 0 comme décrit ssi ils ont la même image par f , et un isomorphisme entre
ci-dessus. Cela permet de transférer des connaissances re- deux états de C 0 ssi ils ont la même image par f 0 . Nous
latives à des entités ou des paires d’entités. Nous avons définissons ensuite F : C → C 0 par (3).
ainsi expérimenté les cas particuliers où dans l’option 1, (
f : C → {0, 1} et f 0 : C 0 → {0, 1} valent 1 si l’entité est l0 , si f (s) = 1
F (s) = (3)
un « Moi » et 0 sinon ; et dans l’option 2, f : C → {0, 1} et k 0 , si f (s) = 2
Il est facile de voir, si les définitions exactes sont connues, 5 Résultats Expérimentaux
que (3) est une équivalence de catégories qui permet de
transférer π de C 0 à C. F induit une bijection F 0 entre les 5.1 Circuit de voitures miniatures
ensembles de classes (ou types de position – ici C ,C 0
sont les types de virage et S ,S 0 sont les types de lignes
droites) : F 0 : (C/ ') → (C 0 / ') où (C/ ') est égal à
{C , S } et (C 0 / ') est égal à {C 0 , S 0 }. On obtient finale-
ment F 0 (C ) = C 0 et F 0 (S ) = S 0 .
Cet exemple de catégorisation systématique et de généra-
lisation prouve que nous ne travaillons pas à l’échelle des
états, mais que nous considérons les types d’états.
Analogies entre jeux vidéo. Considérons un jeu C (par
F IGURE 1 – Configuration des circuits : circuit 1 (à gauche), cir-
exemple le jeu Breakout pour Atari 2600) où une raquette
cuit 2 (à droite)
horizontale est située en x0 sur un segment [0, N ] d’états
initiaux possibles (0 ≤ x0 ≤ N ) et peut se déplacer vers la
gauche ou la droite afin d’atteindre une balle devant arriver Matériel et Implémentation. Le montage expérimental
à la position x1 ∈ [0, N ]. La stratégie π est la suivante : si est constitué d’un circuit MINI Challenge Set C1320 de la
x1 < x0 , se déplacer vers la gauche, si x1 = x0 , ne pas marque Scalextric dont le compteur de tours mécanique a
bouger, mais si x1 > x0 , alors se déplacer vers la droite. été remplacé par un capteur à effet Hall omnipolaire digital.
Désormais, considérons un autre jeu C 0 (tel que Pong sur Le courant est mesuré par une résistance shunt placée en
Atari 2600 par exemple) où cette fois-ci une raquette ver- série avec les rails d’alimentation. Le courant et la tension
ticale se trouve en position y0 sur le segment [0, N 0 ] des sont d’abord filtrés par un filtre RC passif du second ordre
positions atteignables (0 ≤ y0 ≤ N 0 ) et peut se déplacer puis échantillonnés à fs = 100 Hz. Ce montage ne contient
de haut en bas pour toucher une balle qui atteindra la posi- aucun capteur supplémentaire. Les algorithmes sont écrits
tion y1 ∈ [0, N 0 ]. en C et exécutés en temps réel sur un Arduino Mega 2560
Nous souhaitons identifier C et C 0 afin de transposer la stra- qui dispose de 8192 octets de mémoire vive (RAM). Nous
tégie π de C à C 0 . Les états (objets) de C sont les N + 1 définissons la période d’échantillonnage par ts = 1/fs , et
positions x1 de [0, N ]. De la même façon, les états (objets) l’instant associé à l’échantillon k est kts où k ∈ N.
de C 0 sont les N 0 + 1 positions y1 de [0, N 0 ]. Si N = N 0 Ce cas basé sur l’utilisation d’analogies, directement ins-
et x0 = y0 , alors il est facile de définir une bijection de C piré de notre utilisation de la théorie des catégories, repose
à C 0 puis de transposer π, mais si N 6= N 0 ou x0 6= y0 sur deux modules : un module de récompense, ainsi qu’un
alors il est impossible de définir une telle bijection. Pour module de prise de décision, tous deux décrits ci-dessous.
résoudre ce problème, nous transformons C et C 0 en caté- Puisque qu’il n’y a ici qu’un seul système dynamique, c’est
gories à travers la définition suivante de nos flèches, et ce nécessairement le « Moi » et aucune identification n’est
faisant, nous pourrons définir une équivalence de catégo- utile.
ries F : C → C 0 . Pour définir ces flèches, nous utilisons Comme en apprentissage par renforcement, notre approche
les fonctions d’observation suivantes définies sur les états s’appuie sur une récompense tirée de l’environnement.
de C et C 0 : f : C → {0, 1, 2} et f 0 : C 0 → {0, 1, 2} telles Celle-ci est le résultat de la combinaison de trois variables.
que f (x1 ) = 0 ssi x1 < x0 , f (x1 ) = 1 ssi x1 = x0 et La première variable est le temps du tour mesuré directe-
f (x1 ) = 2 ssi x1 > x0 . De la même façon, f 0 (y1 ) = 0 ment grâce au compteur de tours. La seconde variable bi-
ssi y1 < y0 , f 0 (y1 ) = 1 ssi y1 = y0 et f 0 (y1 ) = 2 naire indique la présence de la voiture sur la piste, et la
ssi y1 > y0 . Ensuite, nous définissons une flèche inver- dernière variable binaire indique si la voiture est en mou-
sible entre deux états de C ssi ils ont la même image par vement. Ce module de récompense surveille constamment
f , ainsi qu’une flèche inversible entre deux états de C 0 ssi la voiture pour vérifier qu’elle n’est pas sortie de la piste
ils ont la même image par f 0 . Soit F : C → C 0 , telle à cause d’une vitesse trop élevée, mais aussi qu’elle ne
que si x1 < x0 , alors F (x1 ) = 0 ; si x0 = x1 , alors s’est pas arrêtée à cause de frottements trop importants. Ces
F (x1 ) = y0 ; et si x1 > x0 , alors F (x1 ) = N 0 . Cette fonc- deux détecteurs reposent sur une classification par k plus
tion F définit une équivalence de catégories et induit une proches voisins (k-NN) en utilisant les courants et tensions
bijection F 0 entre les ensembles de classes : F 0 : (C/ ' comme entrées.
) → (C 0 / '). (C/ ') correspond (grâce à la stratégie Avec ce module de récompense, l’IA peut piloter la voiture
π) aux actions disponibles {Gauche, Attendre, Droite} sur des circuits qu’elle découvre sans rejouer ou manipu-
dans C alors que (C 0 / ') correspond aux actions dis- ler des échantillons enregistrés lors d’une partie du joueur
ponibles {Haut, Attendre, Bas} dans C 0 (en choisissant humain. La seule information conservée par l’algorithme
d’orienter l’axe des y du haut vers le bas). Dans ce cas- est une vitesse de sécurité dont l’IA sait qu’elle ne pro-
ci F 0 (Gauche) = Haut, F 0 (Attendre) = Attendre et voque ni sortie de piste, ni arrêt de la voiture. Comme la
F 0 (Droite) = Bas. configuration du circuit change, il n’y a pas bijection entre
TABLE 1 – Temps au tour en secondes (moyenne ± écart-type)(MLI = Modulation de Largeur d’Impulsion)
H UMAIN (10 tours) IA (jusqu’à 10 tours) R ÉGLAGES DE L’IA
C IRCUIT 1 (12 tronçons)
Premier tour 2.99 ± 0.46 3.12 ± 0.09 MLI=39% de la vitesse maximale
Dernier tour 2.29 ± 0.14 2.52 ± 0.08 Analogies (adaptation de la vitesse)
C IRCUIT 2 (18 tronçons)
Premier tour 4.30 ± 1.16 3.66 ± 0.03 MLI=39% de la vitesse maximale
Dernier tour 3.08 ± 0.54 3.13 ± 0.02 Analogies (adaptation de la vitesse)
les deux configurations et le cas bijectif ne peut pas s’ap- pilotées par l’algorithme, alors que certains tours humains
pliquer. Il faut donc s’appuyer sur des analogies et trans- ont occasionné des sorties de pistes et n’ont donc pas été
poser les connaissances acquises dans une première confi- comptabilisés.
guration en utilisant l’équation (2), conformément au for- Le cadre théorique détaillé en section 4 permet au système
malisme des cas non bijectifs décrit dans la partie 4. La d’être au niveau des meilleurs joueurs sur ce jeu en moins
fonction h((u, i)s ) est évaluée par un k-NN dont le co- d’une minute, sans ajout de capteurs embarqués. Ce cadre
efficient à été choisi comme le meilleur compromis entre permet d’atteindre de tels résultats sur des circuits incon-
la performance possible sur la cible embarquée et l’obten- nus où la simple reproduction d’un tour humain conduirait
tion de résultats satisfaisants. Les deux classificateurs sont immédiatement à une sortie de piste.
entraînés avec environ 1000 échantillons de (u, i) (ce qui
correspond à seulement 10 s de jeu) et sont implantés en 5.2 Jeux vidéo Atari 2600
version condensée afin d’être exécutables sur l’Arduino. Configuration et implémentation de la théorie. Tan-
En pratique, l’approche par analogies fonctionne comme dis que le circuit de voitures miniatures nous a permis de
suit : la voiture démarre sur le circuit inconnu avec cette valider l’approche sur des signaux analogiques réels, Ar-
vitesse de sécurité importée de la première configuration. cade Learning Environment (ALE, cf [2]) nous a permis
La fonction h((u, i)s ), évaluée par le k-NN à partir des de la valider sur des configurations plus complexes, avec
mesures de courant et de tension, détermine si la voiture des signaux déjà échantillonnés provenant de l’émulateur.
est dans une configuration que nous appelons courbe ou Les concepts d’entités avec le « Moi » introduits en 3.2
ligne droite. L’IA choisit ensuite la meilleure commande sont également utilisés pour jouer aux jeux Atari 2600.
utilisée au cours des expériences précédentes, en vérifiant On détecte les entités grâce à des algorithmes de traite-
l’objectif de minimiser le temps au tour en maintenant la ment d’images : le filtre de Sobel (image du centre en fi-
voiture sur la piste. L’algorithme permet donc de générali- gure 2) et la détection des boîtes englobantes (image de
ser les connaissances acquises au cours d’expériences pas- droite en figure 2). Elle repose sur la librairie OpenCV [19].
sées et de les appliquer dans une configuration radicale- Le « Moi » est trouvé en utilisant un algorithme d’iden-
ment différente. En effet, les deux circuits schématisés en tification de système. Des séquences d’actions pseudo-
figure 1 sont de forme et de taille différentes et une simple aléatoires [14] sont envoyées comme commande dans ALE
reproduction d’une commande préalablement enregistrée pour d’abord identifier quelles entités sont affectées par
échouerait à fournir des résultats probants. ces signaux, puis pour construire les modèles dynamiques
décrits par les équations (1) avec Nd = 2. Peu d’enti-
Résultats. Les expériences décrites dans cet article ont tés sont contrôlables : ce sont les « Moi ». Leurs formes
été menées sur deux configurations de complexité diffé- peuvent changer en cours de jeu, comme la raquette dans
rente présentées figure 1, et leur résultats sont présentés ta- Breakout, d’où la possibilité d’identifier plusieurs entités
bleau 1. L’IA démarre à vitesse constante (avec une Modu- comme étant le « Moi ». Ces mesures mettent également à
lation de Largeur d’Impulsion de 39% de la vitesse maxi- jour les fonctions p(E, F ) qui expriment la probabilité que
male). Cette IA, qui repose sur l’établissement d’analo- le contact entre les entités E et F change le score, d’une
gies entre configurations et ne rejoue pas d’enregistrement manière similaire à une fonction de récompense en appren-
d’une quelconque partie précédente, est capable d’amélio- tissage par renforcement. À partir de ces fonctions p, nous
rer les temps au tour en moins de 10 tours sur une piste déduisons les entités amies et ennemies, conduisant à la
inconnue. L’algorithme atteint des temps similaires aux stratégie de survie basique décrite en partie 3.2.
temps humains sur le circuit 2 : 3.08 s pour les derniers Nous choisissons d’utiliser le DQN comme référence, car
tours des joueurs humains contre 3.13 s pour l’algorithme. cette publication obtient de bons résultats par rapport à un
Les améliorations futures de l’algorithme sur un circuit in- joueur humain pour un grand nombre de jeux. Les tests
connu incluront l’optimisation des vitesses transposées par ont donc été effectués avec les paramètres décrits dans
l’algorithme. En effet, seule une vitesse de sécurité a été [18] : l’IA joue pendant une durée maximale de 5 minutes.
utilisée ici afin d’éviter les sorties de pistes des voitures Même si notre objectif est de contrôler des systèmes cyber-
TABLE 2 – Scores après 10 000 images d’entraînement (moyenne ± écart type pour 8 parties)
J EU A LÉATOIRE J OUEUR H UMAIN DQN MLCT
Breakout 1.7 31.8 1.25 ± 1.02 414.37 ± 88.47
Pong −20.7 9.3 −21.00 ± 0.00 0.25 ± 2.48
TABLE 3 – Effet du transfert de connaissances de Breakout vers Pong. Méthode (a) : Aucun transfert d’amis donc actions aléatoires.
Méthode (b) : Stratégie de survie basique. Méthode (c) : Transfert de connaissances de Breakout à Pong
M ÉTHODE S CORE N OMBRE D ’ IMAGES D ’ ENTRAÎNEMENT
(a) −20 500 (Pong)
(b) 0 10 000 (Breakout) + 10 000 (Pong)
(c) −2 10 000 (Breakout) + 500 (Pong)
physiques, nous souhaitions valider la versatilité de notre Breakout
Score Moyen par partie
approche en la testant d’abord sur cet environnement de DQN
référence. Nous avons entièrement reproduit la configura- 400 Notre IA
tion de cet article en utilisant le code mis à disposition par
300
les auteurs, et avons obtenu des résultats similaires à ceux
Score
annoncés. Cela nous a permis de calculer un score moyen 200
pour le DQN avec un faible nombre d’images d’entraîne-
ment, pour le comparer au score moyen obtenu avec notre 100
approche.
0
10 2 10 3 10 4 10 5 10 6 10 7 10 8
Nombre de frames d'entraînement
F IGURE 3 – Scores sur Breakout
capacité de l’IA à réfuter ses modèles.
F IGURE 2 – Traitement d’images sur Breakout. De
Les résultats dans Pong ont été obtenus en utilisant trois
gauche à droite : original, contours, boîtes englobantes, approches : la première (a) identifie le « Moi » (mais pas
prédictions des vitesses. la balle comme ami) en 500 images. La seconde (b) cor-
respond à la procédure suivie pour Breakout : elle iden-
tifie le « Moi » puis les amis sur chacun des deux jeux
Résultats. Les résultats pour Breakout 4 sont présentés en 10 000 images. La troisième (c) illustre le transfert de
dans la table 2 pour un temps d’entraînement de 10 000 connaissances formalisé en utlisant les similarités décrites
images (moins de 3 minutes). La figure 3 compare cette dans la partie 3.1 : l’IA commence par apprendre à jouer
approche avec le DQN et montre que des scores similaires à Breakout en 10 000 images, puis elle identifie le « Moi »
sont atteignables en utilisant 20 000 fois moins d’images. sur Pong en 500 images, et enfin elle transfère (sans images
Les étapes d’apprentissage sur Breakout sont les suivantes : d’entraînement supplémentaires) la connaissance de l’ami
durant les premières centaines d’images, l’IA utilise une vers Pong. L’expérience (c) permet d’obtenir un système
séquence pseudo-aléatoire pour identifier le « Moi ». Une capable de jouer à Breakout et Pong avec seulement 10 500
fois que cette identification a convergé vers le seul système images d’entraînement comme mis en évidence en table 3.
que l’IA contrôle – la raquette – l’algorithme recherche des
entités amies et ennemies. En quelques milliers d’images, il
détecte que la balle est un ami car le score augmente quand
6 Conclusion
elle casse une brique. À partir de concepts empruntés aux Sciences Sociales
Les scores autour de 400 points correspondent à des parties et Cognitives et d’enseignements tirés de caractéristiques
où quasiment toutes les briques du premier niveau ont été propres aux méthodes scientifiques, ces travaux utilisent
cassées. L’écart-type élevé est dû à certaines parties attei- des outils élémentaires de la théorie des catégories pour
gnant des scores de plus de 600 points, obtenus grâce à la faciliter l’établissement d’analogies et le transfert de
4. Les résultats pour le joueur humain et le mode aléatoire sont tirés
connaissances entre situations non bijectives. Ces outils
de [18]. Le temps d’entraînement pour le joueur humain est de 2 heures permettent aussi de formaliser une approche aboutissant à
soit 432 000 images. une IA capable de contrôler un agent dans un monde en
perpétuelle évolution. [13] G. Lee, M. Luo, F. Zambetta, and X. Li, “Learning
Les résultats des expériences conduites sur un système a Super Mario controller from examples of human
cyber-physique mais aussi sur des jeux vidéo Atari 2600 play,” in 2014 IEEE Congress on Evolutionary Com-
confirment nos attentes. En effet, ce système a été capable putation (CEC), July 2014, pp. 1–8.
d’identifier, puis de contrôler le « Moi » dans différentes [14] W. S. Levine, The Control Systems Handbook: Con-
situations, que ce soient des circuits de configurations dif- trol System Advanced Methods, 2011.
férentes, ou des jeux Atari 2600 différents, en s’appuyant
sur un transfert de connaissances et une faible quantité de [15] Y. Liang, M. C. Machado, E. Talvitie, and M. Bowl-
données. ing, “State of the art control of Atari games using
shallow reinforcement learning,” in Proceedings of
References the 2016 ICAAMAS, ser. AAMAS ’16, 2016, pp. 485–
493.
[1] P. Bartha, “Analogy and analogical reasoning,” in
The Stanford Encyclopedia of Philosophy, winter [16] N. Lipovetzky, M. Ramirez, and H. Geffner, “Clas-
2016 ed., E. N. Zalta, Ed. Metaphysics Research sical planning with simulators: Results on the Atari
Lab, Stanford University, 2016. video games,” in IJCAI’15, 2015, pp. 1610–1616.
[2] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowl- [17] S. Mac Lane, Categories for the working mathemati-
ing, “The arcade learning environment: An evaluation cian, 2nd ed. Springer-Verlag, 1998.
platform for general agents,” Journal of Artificial In- [18] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu,
telligence Research, vol. 47, pp. 253–279, 2013. J. Veness, M. G. Bellemare, A. Graves, M. Ried-
[3] M. Bogdanovic, D. Markovikj, M. Denil, and miller, A. K. Fidjeland, G. Ostrovski, S. Petersen,
N. de Freitas, “Deep apprenticeship learning for play- C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Ku-
ing video games,” in AAAI Workshop on Learning for maran, D. Wierstra, S. Legg, and D. Hassabis,
General Competency in Video Games, 2015. “Human-level control through deep reinforcement
learning,” Nature, vol. 518, no. 7540, pp. 529–533,
[4] C. Chang and H. J. Keisler, Model Theory, 3rd ed.
February 2015.
North Holland, 1990.
[19] OpenCV, “Open source computer vision library,”
[5] Z. Chen and B. Liu, Lifelong Machine Learning.
https://opencv.org/, 2017.
Morgan & Claypool Publishers, 2016.
[20] J. Ortega, N. Shaker, J. Togelius, and G. N. Yan-
[6] M. Csikszentmihalyi, Flow: The Psychology of Opti-
nakakis, “Imitating human playing styles in Super
mal Experience, ser. Harper Perennial Modern Clas-
Mario Bros,” Entertainment Computing, vol. 4, no. 2,
sics. Harper Collins, 2009.
pp. 93 – 104, 2013.
[7] J. Culbertson and K. Sturtz, “Bayesian machine
[21] T. Pepels, M. H. M. Winands, and M. Lanctot, “Real-
learning via category theory,” arXiv:1312.1445v1
Time Monte-Carlo Tree Search in Ms. Pac-Man,”
[math.CT] 5 Dec 2013, 2013.
IEEE Trans. on Computational Intelligence and AI in
[8] F. de Saussure, Cours de linguistique générale. Games, vol. 6, no. 3, pp. 245–257, Sept 2014.
Payot, 1916.
[22] J. Piaget, The construction of reality in the child. Ba-
[9] B. Falkenhainer, K. Forbus, and D. Gentner, “The sic Books, 1954.
structure-mapping engine: Algorithm and examples,”
Artificial Intelligence, vol. 41, pp. 2–63, 1989/90. [23] K. Popper, The Logic of Scientific Discovery.
Hutchinson & Co, London, 1959.
[10] R. E. Kalman, “On the general theory of control
systems,” in Proceedings of the First International [24] L. Pusman and K. Kosturik, “Control algorithm based
Congress on Automatic Control. Butterworth, Lon- on phase locked loop,” in Telecommunications Forum
don, 1960, pp. 481–492. (TELFOR), 2013 21st, Nov 2013, pp. 605–607.
[11] K. Kansky, T. Silver, D. A. Mély, M. Eldawy, [25] J. M. Schaeffer, L’expérience esthétique. Gallimard,
M. Lázaro-Gredilla, X. Lou, N. Dorfman, S. Sidor, 2015.
D. S. Phoenix, and D. George, “Schema networks: [26] A. Schutz, The phenomenology of the social world,
Zero-shot transfer with a generative causal model of ser. Northwestern University studies in phenomenol-
intuitive physics,” in ICML 2017, 8 2017, pp. 1809– ogy & existential philosophy. Northwestern Univer-
1818. sity Press, 1967.
[12] S. Lange, M. Riedmiller, and A. Voigtlander, “Au- [27] D. Sperber, La Contagion des idées. Éditions Odile
tonomous reinforcement learning on raw visual in- Jacob, 1996.
put data in a real world application,” in The 2012 [28] D. I. Spivak, Category Theory for the Sciences. The
International Joint Conference on Neural Networks MIT Press, 2014.
(IJCNN). IEEE, 2012, pp. 1–8.
F IGURE 4 – Algorithme utilisé.
Require: bdc = [entites, modeles, strategies]
Require: strategie_par_def aut
Require: seuil, Nmax
1: for Ninit = 0 to Nmax do
2: entites.append(donnees_prelevees)
3: action ← strategie_par_def aut
4: applique(action)
5: end for
6: jeu_similaire ← recherche jeu avec des entites similaires
7: modeles, strategies ← extrait(bdc, jeu_similaire)
8: bdc.append([entites, modeles, strategies])
9: f _ref ute_modeles ← false
10: if modeles est vide then
11: f _ref ute_modeles ← true
12: end if
13: while experimentation en cours do
14: entites.append(donnees_prelevees)
15: if f _ref ute_modeles then
16: action ← strategie_par_def aut
17: modeles, strategies, f _id ← identification(entites)
18: if f _id then
19: f _ref ute_modeles ← false
20: bdc.append([entites, modeles, strategies])
21: end if
22: else
23: action ← cherche_action(entites, strategies)
24: predictions ← cherche_predictions(entites, modeles)
25: erreur ← predictions − entites
26: if |erreur| > seuil then
27: f _ref ute_modeles ← true
28: end if
29: end if
30: applique(action)
31: end while
32: return bdc
Annexe : algorithme La base bdc est ensuite complétée.
Lors de la partie, le système continue à acquérir des échan-
L’algorithme utilisé est décrit en pseudo-code sur la figure
tillons et à les transformer en entités. Si le modèle est va-
4. Il repose sur une base de connaissance bdc, une stratégie
lide (lignes 23 à 27), le système calcule à partir des entités
par défaut strategie_par_def aut, un seuil seuil de rejet
présentes et stratégies disponibles la meilleure action à ef-
du modèle et un nombre d’itérations Nmax correspondant
fectuer. Avec les entités et les modèles, une prédiction de
à la durée de l’initialisation.
l’état de l’environnement est aussi calculée. Si ces predic-
La base bdc, initialement vide, se remplit progressivement tions sont trop éloignées de l’état mesuré, alors la variable
des stratégies obtenues au cours des parties jouées. La stra- f _ref ute_savoir devient vraie. Dans ce cas, dès l’itéra-
tégie par défaut strategie_par_def aut est, dams le cas tion suivante, la procédure d’identification (lignes 15 à 20)
du circuit de voitures, une MLI constante (39% dans nos se lance. De nouveaux modèles et stratégies sont calculés.
expériences). Dans le cas des jeux Atari 2600, c’est une Cette procédure est mise en oeuvre tant que de nouveaux
séquence pseudo-aléatoire d’actions envoyées en entrée du modèles et stratégies n’ont pas été trouvés puis validés.
système. Une fois validés, la base de connaissances bdc est enrichie
L’algorithme commence par acquérir les échantillons puis de ces résultats.
les assimile à des types d’entités en ligne 2. À partir de ces Notons que l’algorithme est identique en phase d’appren-
entités, l’algorithme détermine la situation qui présente les tissage et en phase d’exploitation (test). Il continue de réfu-
objets les plus similaires en ligne 6 avant d’extraire en ligne ter son savoir, si besoin est, même en phase d’exploitation.
7 les modèles et stratégies obtenus lors de cette situation.