L’intelligence arificielle (IA) est une discipline scientifique qui a vu officiellement le jour en 1956.
Elle repose sur la conjecture selon laquelle toutes les fonctions cognitives, en particulier l’apprentissage, le raisonnement, le calcul,
la perception, la mémorisation, voire la découverte scientifique ou la créativité artistique, peuvent
être reproduites sur des ordinateurs.
L’apprentissage automatique (Machine Learning) est à l’intersection de l’IA et d’un autre champ scientifique : la science des données (data science).
En pratique, il s’agit de produire des réponses adaptées aux données fournies en entrée (identifier des motifs, des tendances, construire des modèles, faire des prédictions).
L’apprentissage automatique n’est donc ni plus ni moins que du traitement de données visant à prédire des résultats en fonction
des données entrantes.
KNN est un algorithme d’apprentissage supervisé cela signifie que l’algorithme nécessite
des données classifiées en amont qui vont lui servir à trouver la bonne étiquette pour
d’autres données non encore classifiées.
Suivant la nature de l’étiquette, KNN peut servir à :
KNN enregistre, dans un premier temps, tous les points de données étiquetées qui vont lui servir à l’apprentissage (c’est le training set).
Puis, quand arrive un point de donnée non étiqueté, l’algorithme calcule sa distance aux autres points et sélectionne les k plus proches.
On a alors deux cas possibles :
si les étiquettes sont des catégories, l’algorithme calcule le mode des catégories des voisins sélectionnés (catégorie la plus représentée).
si les étiquettes sont des nombres, l’algorithme calcule la moyenne des étiquettes des voisins sélectionnés.
Dans l’animation suivante, on utilise KNN pour répondre à la question suivante :
Quelle est la couleur du nouveau point ?
L’algorithme des k plus proches voisins
est non paramétrique.
Aucun modèle mathématique de classification ou régression n’est construit à partir des données
(pas de paramètre à ajuster).
Les données d’apprentissage
sont enregistrées telles quelles.
Cela signifie qu’on ne présuppose rien de particulier sur les données (à part que des points proches appartiennent à la même catégorie).
L’algorithme est donc particulièrement
robuste (les données parlent d’elles-même)
et simple à mettre à jour (suffit d’ajouter
les nouvelles données d’apprentissage).
Le choix de k modifie le résultat obtenu.
Le choix de k est donc affaire de compromis. Pour le rendre plus scientifique, on peut chercher à mesurer la performance de l’algorithme pour différentes valeurs de k.
Mais comment mesure-t-on la performance d’un algorithme d’apprentissage automatique ?
La matrice de confusion permet d’évaluer
la qualité des prédictions d’un algorithme.
Utilisons KNN sur une banque d’images de chiffres écrits à la main et concentrons-nous sur
sa capacité à reconnaître des “3”.
Un algorithme peut très bien être très précis
(les prédictions positives sont bien des 3),
mais peu sensible, avec un faible taux de rappel (parmi tous les 3, peu ont été identifiés).
À l’inverse, on peut avoir une bonne sensibilité
(la plupart des vrais 3 ont été identifiés comme tel), mais peu précis (beaucoup de chiffres identifiés comme des 3 sont en fait d’autres chiffres).
L’algorithme des k-moyennes regroupe
en catégories des données
dont on ne connaît rien a priori.
C’est un algorithme
de partitionnement
des données (clustering).
L’algorithme depend d’un seul paramètre
(en plus des données) :
le nombre de partitions k.
On commence par choisir k points au hasard dans l’espace des données (il peut s’agir de k points de données ou de k autres points). Ce sont les k centres (ou centroïdes).
On attribue ensuite à chaque centre tous les points de données qui lui sont le plus proches, formant ainsi k groupes.
Enfin, on déplace chaque centre au barycentre de son groupe.
On répète les deux dernières opérations (attribution des points les plus près
et déplacement des centres)
tant que les centres bougent
d’une itération à l’autre.
L’algorithme vise à résoudre au final un problème d’optimisation ; son but est en effet de trouver le minimum de la distance entre les points à l’intérieur de chaque partition.
Mathématiquement, étant donné un ensemble
de points $(x_1,x_2,\ldots,x_n)$, on cherche à partitionner les $n$ points en $k$ ensembles $S=\{S_1,S_2,\ldots,S_k\}$ en minimisant la grandeur
$$I = \sum_{i=1}^{k}\sum_{x_j \in S_i}||x_i-\mu_i||^2$$
où $\mu_i$ est le barycentre des points dans $S_i$.
$I$ est la variance intra-classe ou inertie intra-classe (terme surtout utilisé en anglais).
On quitte l’apprentissage automatique
mais on reste dans le champ de l’IA.
Vocabulaire
On entendra ici par jeu :
L’arène dans laquelle le jeu prend place
est un graphe orienté biparti.
Deux joueurs, $J_1$ et $J_2$, s’affrontent sur un graphe orienté biparti $G=(S,A)$ où $S$ est constitué des sommets contrôlés par le joueur 1, $S_1$, et de ceux contrôlés par le joueur 2, $S_2$. Chaque sommet est une position valide du jeu et chaque arête est un mouvement autorisé entre ces positions.
Dans le cas d’un jeu d’accessibilité, on attribue à chaque joueur un sous-ensemble de sommets correspondant à des états gagnants qu’il doit atteindre pour… gagner.
Il peut aussi exister un sous-ensemble de sommets correspondant à des états de partie nulle.
Un jeu d’accessibilité est alors défini
par un quadruplet $(G,S_1,S_2,F)$
où $(G,S_1,S_2)$ est une arène et $F$ est l’ensemble des sommets gagnants pour $J_1$.
Autre variante du jeu de Nim :
Eve joue en premier et peut retirer autant d’allumettes qu’elle le souhaite dans un tas
du moment qu’elle en prend au moins une
et qu’elle en laisse au moins une.
C’est ensuite au tour d’Adam de retirer des allumettes avec pour tous les tours qui suivent
une contrainte supplémentaire :
on ne peut pas retirer plus de deux fois le nombre d’allumettes prises par son adversaire
au tour précédent.
Le joueur qui retire la dernière allumette gagne.
Il n’y a pas de match nul.
En commençant avec un tas de 5 allumettes,
on obtient l’arène suivante
où chaque sommet est étiqueté par le couple
(nombre d’allumettes présentes,
nombre d’allumettes prenables).
L’arène s’écrit donc :
$$ \begin{aligned} &(G,\color{blue}\{(5,4,0),(3,2,0),(2,2,0),(1,1,0),(0,0,0)\}\color{black},\\ &\color{magenta}\{(4,2,1),(3,3,1),(2,2,1),(1,1,1),(0,0,1)\}\color{black},\color{orange}(0,0,1)\color{black}) \end{aligned} $$
Remarque
Tout jeu impartial à deux joueurs est une variante du jeu de Nim (théorème de Sprague-Grundy).
Un jeu impartial est un jeu tour par tour dans lequel les coups autorisés, ainsi que les gains obtenus, dépendent uniquement de la position,
et pas du joueur dont c’est le tour.
Un jeu qui n’est pas impartial est appelé jeu partisan (le morpion ou les échecs par exemple).
Le morpion :
On part ici d’une partie avancée.
Eve a les ronds et c’est son tour.
Il faut pouvoir s’assurer qu’Eve arrive sur $F$.
Comment faire ?
Positions gagnantes et attracteurs
Pour déterminer l’ensemble des positions gagnantes pour Eve sur l’arène, on travaille récursivement depuis les sommets de $F$
en suivant les deux préceptes suivants :
Formalisons en définissant la suite $Attr_i(F)$
qui contient l’ensemble des sommets
gagnants après $i$ étapes :
$$ \begin{array}{lll} Attr_0(F) &= &F \\ Attr_{i+1}(F) &= &Attr_{i}(F) \\ &&\cup \{s \in S_1|Succ(s)\cap Attr_i(F) ≠ \varnothing \} \\ &&\cup \{s\in S_2| Succ(s)\subseteq Attr_i(F)\} \end{array} $$
Étant donné que $Attr_i(F) \subseteq Attr_{i+1}(F) \subseteq S$, pour tout $i≥0$, si on suppose le graphe fini,
la suite est croissante et bornée
et donc stationnaire
(à partir d’un certain $i=i_0$,
$Attr_i(F)$ est constante).
Et si $|G|=n$, $i_0$ vaut au plus $n-1$.
On appelle attracteur de $F$ pour le joueur $J_1$
la limite de $Attr_i(F)$.
On le note $Attr(F)$.
Tout sommet dans l’attracteur
est une position gagnante pour $J_1$.
Le complémentaire d’un attracteur
est appelé piège.
Si le joueur 1 est sur une position n’appartenant pas à son attracteur (et appartenant
donc à son piège), cela signifie que :
Cette position est donc perdante…
Dans le cas de la variante de Nim, l’attracteur se réduit à $Attr(G) = \{(0,0,1) , (1,1,0) , (2,2,0) \}$
Le sommet de départ $(5,4,0)$ n’est pas dedans
$\Rightarrow$ c’est perdu pour Eve 😭.
Sur l’exemple du morpion, l’attracteur contient
13 sommets dont celui de départ 🥳.
Programme permettant de calculer l’attracteur
On peut écrire un programme récursif calculant l’attracteur en temps linéaire en $|S | + |A|$
(le parcours complet d’un graphe est au mieux en $O(|S | + |A|)$ car cela correspond à parcourir
les $|S|$ sommets et les $|A|$ arêtes).
Pour éviter de calculer plusieurs fois le même élément, l’algorithme tient à jour, pour chaque sommet $s$, un compteur n des successeurs non encore inspectés (sous la forme d’un dictionnaire) .
def attracteur(G: dict, F: list) -> list:
"""
préconditions : G est est un graphe sous forme de liste d'adjacence implémentée par un dictionnaire
F est la liste des sommets gagnants pour le joueur 1
postcondition : la fonction retourne l'attracteur de F pour le joueur 1 sous forme d'un dictionnaire
dont les clés sont les sommets de G et les valeurs True ou False suivant que le sommet appartienne ou non à l'attracteur
"""
Pred = inverseGraphe(G)
n = {s:len(G[s]) for s in G}
Attr = {s:False for s in G}
for sommet in F :
Joueur1 = True
propage(sommet,Joueur1,Attr,Pred,n)
return Attr
def propage(sommet,Joueur1,Attr,Pred,n) :
if Attr[sommet] :
return
Attr[sommet] = True
for s in Pred[sommet] :
n[s] -= 1
if Joueur1 or (n[s] == 0) :
propage(s,not Joueur1,Attr,Pred,n)
Une stratégie sans mémoire est une fonction $\sigma$ qui assigne un mouvement autorisé à un joueur pour chaque position non terminale : $\forall s\in S, (s,\sigma(s))\in A.$
Un joueur sur une position $s$ suit une stratégie s’il emprunte le chemin $<s,\sigma(s),\sigma^2(s),\ldots>$.
Elle est dite sans mémoire car pour une position donnée, la stratégie est indépendante du chemin qui y a mené ($\sigma$ ne dépend que du sommet).
Une stratégie sans mémoire gagnante depuis une position donnée garantit la victoire au joueur en un nombre de coups limité.
Pour le joueur 1, une stratégie gagnante garantit d’arriver sur un sommet de $F$.
Mais suivant la position de départ, une telle stratégie n’existe pas forcément…
En construisant l’attracteur,
on répond à notre première question :
La position d’Eve est-elle gagnante ?
$\rightarrow$ Il suffit de vérifier qu’elle
appartient à l’attracteur.
Si c’est le cas, une stratégie gagnante est facile à mettre en place ; il faut faire en sorte que chaque déplacement sur le graphe (chaque coup joué) se fasse vers un sommet de l’attracteur. Chaque coup d’Eve vers un sommet de l’attracteur piège aussi le coup suivant d’Adam dans l’attracteur.
Comme son nom l’indique, l’attracteur attire irrémédiablement vers $F$,
assurant la victoire
au joueur 1.
Le joueur 2 aussi, bien sûr, a son attracteur,
et il appartient au complémentaire de l’attracteur du joueur 1, piège du joueur 1.
Donc un seul écart du joueur 1 en dehors de son attracteur, et s’en est fini pour lui, le joueur 2 peut le condanner à rester dans le piège.
Pour la variante de Nim, c’est foutu ! Quelle que soit notre stratégie, elle sera perdante…
Enfin, pour le morpion, la victoire tend les bras au joueur 1. Et, sans surprise, son premier mouvement doit être de prendre
le milieu.
Algorithme star pour les jeux. C’est ce type d’algorithme que Deep Blue a utilisé
pour battre Kasaparov en 1997.
Le principe de l’algo est proche de celui de l’attracteur, mais il est plus souple et permet surtout de n’explorer qu’une petite partie de l’arène (au détriment de sa performance).
Le plus grand changement par rapport au raisonnement sur l’attracteur : on transforme
le graphe de l’arêne en arbre.
Avantage ?
Inconvénient ?
Le but va être de trouver un chemin entre la racine de l’arbre et une feuille gagnante (victoire finale).
L’idée est, comme pour l’attracteur,
de partir de la situation finale et de remonter récursivement tour par tour.
On score chaque feuille terminale
avec une valeur de $+\infty$ si le joueur 1 gagne
et de $-\infty$ si c’est le joueur 2.
On remonte ensuite niveau par niveau :
Chaque joueur simulé joue bien ainsi
de manière optimale.
L’intérêt majeur de minimax est la possibilité
de partir de n’importe quel niveau
et pas seulement des positions finales !
On peut donce se contenter de regarder
seulement quelques coups à l’avance.
Quel est l’intérêt ?
Mais pour se limiter à une certaine profondeur dans l’arbre, il faut pouvoir scorer
les sommets du niveau de départ !
On utilise alors une heuristique.
Exemples :
Au morpion, si c’est au tour du joueur 1, on peut compter le nombre de diagonales encore possibles pour le joueur 1 et soustraire le nombre de celles encore possibles pour le joueur 2.
L’arbre total du morpion n’est pas si gros :
le facteur de ramification $b$ est de 5 en moyenne et il y a au plus 9 niveaux (9 coups),
ce qui donne $\approx 5^9 = 1\,953\,125$
Aux échecs, $b\approx35$ et un partie dure en moyenne 100 coups, ce qui donne $b^m\approx10^{54}$
sommets à inspecter…
Minimax inspecte en réalité environ 4 fois moins de sommets que les deux millions prédits (beaucoup de parties se terminent
avant le neuvième coup).
Il en inspecte néanmoins beaucoup trop puisqu’il n’y a que $9!=362\,880$ coups possibles
si l’ordi commence.
Cela illustre le fait qu’un arbre contient beaucoup de sommets redondants par rapport au graphe
du jeu dont il est tiré (c’est le prix à payer
pour casser les cycles).
Le problème du sac-à-dos est
un probème clé d’optimisation.
Il s’agit de choisir des objets ayant une certaine valeur et un certain poids pour les mettre dans
un sac ayant une capacité maximum
(un poids à ne pas dépasser).
On souhaite obtenir le sac de plus grande valeur.
On ne s’occupe ici que de la version la plus simple du problème dite knapsack 0-1 où un objet est soit présent une seule fois dans le sac, soit absent.
Le problème du sac-à-dos est un problème d’optimisation sous contrainte et une foule de défis scientifiques et industriels peuvent se mettre sous cette forme. Son importance est colossale.
Supposons que l’on ait $n$ objets.
Un algorithme force brute consiste
à étudier les … possibilités.
Et dès qu’il s’agit d’explorer un ensemble de combinaisons, la récursivité est l’outil de choix.
Supposons que l’on cherche à placer les objets suivants dans un sac de capacité 900.
| objets | 🥏 | 🎺 | 🥊 | 🧸 | 🪠 | ⏰ |
|---|---|---|---|---|---|---|
| valeurs $v$ | 5 | 50 | 65 | 20 | 10 | 12 |
| poids $p$ | 320 | 700 | 845 | 180 | 70 | 420 |
def KS(v,p,c,i,valeur,poids):
n = len(v)
if i == n: # cas de base (i = n-ième objet)
if poids > c:
return 0
else:
return valeur
else:
valeurAvec = valeur + v[i]
poidsAvec = poids + p[i]
return max(KS(v,p,c,i+1,valeur,poids),KS(v,p,c,i+1,valeurAvec,poidsAvec))
C’est bien sûr trop long si le nombre
d’objets devient conséquent.
Pour accélérer les choses, on peut se tourner vers une stratégie gloutonne (stratégie étape par étape où un critère de classement permet de sélectionner le prochain objet à ajouter).
La complexité devient alors …
Le ratio valeur/poids de chaque objet
semble un bon critère.
| objets | 🥏 | 🎺 | 🥊 | 🧸 | 🪠 | ⏰ |
|---|---|---|---|---|---|---|
| ratio $v/p$ | 1/64 | 1/14 | 1/13 | 1/9 | 1/7 | 1/35 |
Problème : ça ne marche pas forcément…
Ici, on se retrouve avec 🪠 et 🧸 dans le sac
pour une valeur de 30€ ce qui n’est
évidemment pas optimal.
Une autre démarche consiste à construire l’abre binaire comme pour l’approche force brute mais en l’élaguant au fur et à mesure quand des branches ne peuvent plus donner la solution.
C’est la méthode “séparation et évaluation”
(branch and bond ou BB en anglais).
Ici, deux élagages possibles :
On se sert donc ici de l’approche gloutonne
comme d’une …