«Intelligence artificielle», apprentissage : l'exemple de l'algorithme des $k$-means
L'objet de cette page est de présenter de façon concrète
un algorithme simple d'«apprentissage non-supervisé», et
ce faisant de parler un peu de ce que l'on appelle
l'«intelligence artificielle» (et de la démystifier).
Pour les lecteurs sans connaissance en informatique
(au sens de «science informatique»), il est utile de
commencer par définir ce qu'est un algorithme - terme
régulièrement dévoyé dans les mediaOù il est régulièrement employé comme synonyme d'«algorithme d'intelligence artificielle», cette dernière notion poussant elle-même au malentendu… :
Un algorithme est une séquence finie d'instructions, permettant, à partir de données de départ, de produire un résultat.
Par exemple, lorsque vous posez et effectuez l'addition $134+228$, vous
exécutez un algorithme.
Un problème de partitionnement de données
Après quelques mois de prospection dans les forêts
profondes et inexplorées de l'Hérault, je suis parvenu à
capturer 40 specimens du rarissime «Kangourou à six pattes
du Haut-Languedoc».
Afin d'évaluer la pertinence d'une séparation en plusieurs
sous-espècesAvec le secret espoir que l'une pourrait porter mon nom., j'ai mesuré deux caractères morphologiques (la
longueur $x$ du bec, ainsi que celle $y$ du tarse de la patte
gauche de la 2ème paire de pattes). À chaque specimen correspond
donc un point du plan. Les données obtenues (sans dimension) sont
synthétisées ci-dessous.
«On voit bien que» quatre groupes semblent se distinguer, qui sont coloriés de couleurs différentes dans l'image ci-dessous.
Ce «on voit bien que» n'est pas encore de la science, mais
est à l'origine de deux interrogations :
Peut-on donner une formuation précise (en
l'occurrence mathématique) de ce que l'on entend par
«groupes»
Étant donnés des points comme ci-dessus, peut-on
calculer automatiquement une (la) décomposition en
groupes ? Calculer le nombre de groupes ?
Il s'agit du problème de partionnement de données.
Problème qui apparait dans de nombreux autres domaines que la cryptozoologie. En voici trois exemples :
Imaginons par exemple que l'on veuille indexer automatiquement
un ensemble de photos, selon les personnes qui se
trouvent dessus (pour classer vos photos de famille, pour développer un
moteur de recherche sur une base
d'images, ou pour une utilisation beaucoup plus problématique de reconnaissance faciale dans l'espace public). Après une phase (non-triviale) de
détection des visages dans les images, on peut
extraire un ensemble de caractéristiques
numériques $(x_1, \dots x_n)$ de celui-ci (par
exemple la distance entre les yeux, la distance
d'un oeil au bout du nez…). À chaque visage va
donc être associé un point $(x_1,
\dots x_n)\in\mathbb{R}^n$. On souhaiterait
regrouper les points correspondant au visage de la
même personne dans des photos différentes. On peut
penser que ces points vont être «proches» dans
$\mathbb{R}^n$, et donc
qu'effectuer un partitionnement de ces points
comme dans l'exemple ci-dessusLa
seule différence étant que l'on est dans
$\mathbb{R}^n$ et non plus dans $\mathbb{R}^2$ peut permettre de
répondre au problème. Si l'on au moins une photo
de visage «annotée» pour chaque personne
(c'est-à-dire que l'on connait le nom de la
personne sur la photo), on espère que tous les
visages qui seront dans le même groupe pourront
être automatiquement annotés.
En biologie, ce type de problèmes peut intervernir pour regrouper des gènes ressemblants en familles de gènes homologues.
On peut également en avoir besoin pour regrouper
des articles similaires dans un grand corpus de
textes, pour suggérer au lecteur d'un article d'autres
pages ressemblantes.
Cette page démontre une
application des $k$-moyennes au regroupement de
couleurs dans une image.
Une formulation mathématique
Qu'attend-on d'un «groupe» dans un problème de partionnement
de données ? Intuitivement, il s'agit d'un ensemble de points
qui sont «proches» les uns des autres.
Soit $S$ un ensemble (non vide) de points. On définit le score de $S$ par $$sc(S)=\sum_{p\in S}||p-m(S)||^2,$$ où $m(S)$ est la moyenne des
points du groupe.
Le carré s'explique par le fait que le score ainsi défini a de bonnes propriétés mathématiques : il s'agit d'une variance. Il serait plus naturel de ne pas le mettre, mais des problèmes se posent alors pour l'algorithme dont il va être question ci-dessous.
Une première formulation tentante de notre problème est alors :
Étant donné un ensemble $E$ non vide de points de $\mathbb{R}^n$, trouver une partition $\{S_1\dots S_k\}$ de $E$un ensemble de parties non vides de $E$ qui recouvrent $E$, et ne s'intersectent pas 2 à 2. telle que $\sum_{i=1}^ksc(S_i)$ soit minimale.
Mais cela ne fonctionne pas : pour minimiser cette quantité,
il suffit de prendre des groupes réduits à 1 point ! Le score
de chaque groupe est alors nul - puisque sa moyenne est confondue avec son unique point.
L'une des façon de résoudre ce problème est de fixer le nombre
de groupes à trouver. On le notera $k$ dans la suite.
Voici la formulation obtenue.
Étant donné un ensemble de points $E$ non vide de $\mathbb{R}^n$ et un entier $k>1$, trouver une partition de $E$ en $k$ parties $\{S_1\dots S_k\}$ telle que $\sum_{i=1}^ksc(S_i)$ soit minimale.
Il s'agit d'un problème très étudié, mais algorithmiquement
difficile à résoudreIl semble NP-difficile à résoudre de façon exacte - notion qui sera expliquée ultérieurement dans un poly - mais différentes sources sont en désaccord sur le sujet. en général.
Il existe cependant une heuristiqueIl s'agit d'un algorithme donnant la plupart du temps rapidement une solution raisonnable à un problème, mais sans garantie théorique. classique permettant de
trouver de bonnes partitions dans la plupart des cas :
l'algorithme des $k$-means.
L'algorithme des $k$-means ($k$-moyennes)
Algorithme des $k$-means
On commence par choisir $k$ points
$m_1,\dots m_k$ dans le plan - appelés «moyennes». Généralement, ces points sont choisis au hasard parmi les points de $E$.
On répète les 2 étapes suivantes jusqu'à ce que les
moyennes ne soient plus modifiées :
classer les points de $E$ selon le $m_i$ dont ils sont
le plus proche - on obtient ainsi $k$ groupes numérotés de $1$ à $k$, chacun correspondant à une moyenne;
recalculer la moyenne de chaque groupe : $m_i$ reçoit comme nouvelle valeur le barycentre des points du groupe $i$.
L'application ci-dessous vous permet de visualiser le
déroulement de l'algorithme.
Vous pouvez commencez par générer des données,
selon un mélange de gaussiennes.
Puis vous pouvez générer les moyennes de départ.
Et enfin lancer l'exécution de l'algorithme. Dans
certaines situations où l'on accès au score optimal,
celui-ci est également affiché.
Générer des données
Générer des moyennes de départ
On peut montrer la propriété suivante :
À chaque itération le score total diminue.
Comme il n'y a qu'un nombre fini de façons de former les
différents groupes, on en déduit que l'algorithme termine,
et que la configuration atteinte est un minimum localC'est-à-dire qu'on ne peut pas l'améliorer par une nouvelle étape de l'algorithme..
Cependant, comme le nombre de façons de former les différents groupes est grandPar exemple, pour $k=2$, si l'on note $n$ le nombre de points, ce nombre est $2^{n-1}-1$. Pour un $k$ quelconque, il s'agit du nombre de Stirling de seconde espèce .,
le nombre d'étapes nécessaires pour
que l'algorithme se termineC'est ce que l'on appelle sa complexité. l'est également.
On n'est pas certain non plus que les groupes trouvés sont les
meilleurs possibles : le minimum local atteint n'est pas
nécessairement global. Cet algorithme ne présente pas de
bonnes garanties théoriques sur la qualité de la solution obtenue, ni sur le temps mis pour y parvenir.
D'autres inconvénients de cet algorithme :
La solution trouvée dépend du choix des moyennes de départ, comme vous pouvez l'oberver sur l'application ci-dessus. Si on exécute deux fois l'algorithme sur les mêmes données, on n'obtiendra pas nécessairement le même résultat à la fin.
Cet algorithme suppose une certaine organisation «en
paquets ronds» des données. Essayez de l'appliquer à des
points uniforméments répartis, ou à des groupes de points
formant des lignes.
La contrainte d'avoir fixé le nombre de groupes est
problématique dans les cas où l'on n'a pas de connaissance a
priori sur les données.
Reste que moyennant quelques astuces pour bien choisir les
moyennes de départ, cet algorithme trouve «rapidement» des
solutions «raisonnables» en pratique, quitte à relancer plusieurs fois la résolution en partant de différentes moyennes de départ et en gardant la solution solution obtenue (celle ayant le score le plus bas). L'application permet de tester différentes stratégies d'initialisation :
Forgy consiste à choisir $k$ points de données distincts aléatoirement comme moyennes de départ
Uniforme consiste à choisir $k$ points uniformément dans le carré contenant les données
Dans partition aléatoire on donne une étiquette aléatoire parmi $\{1,\dots k\}$ à chaque point de données. La moyenne des points étiquetés par $1$ donne notre première moyenne initiale, la moyenne des points étiquetés par $2$ donne notre deuxième moyenne initiale, etc. En pratique, cela donne des moyennes très proches et «centrales» par rapport aux données.
Enfin $k$-moyennes++ est une méthode très efficace en pratique permettant de disperser les moyennes de départ. On choisit la première moyenne aléatoirement, puis successivement les moyennes suivantes parmi les points de données avec une probabilité proportionnelle à la distance entre le point et la plus proche moyenne déjà calculée. Les nouvelles moyennes ont donc tendance à être choisies «loin» des précédentes.
«Intelligence artificelle ?»
Les $k$-means sont un algorithme d'apprentissage non-supervisé :
l'ordinateur «apprend» les groupes, uniquement à partir des
données, sans intervention d'un humain pendant l'exécution de
l'algorithme. Le terme «apprentissage» doit être mis entre
(beaucoup de) guillemets - il ne s'agit évidemment pas d'un
type d'apprentissage dont les cerveaux biologiques sont
capables. Comme expliqué ci-dessus, il s'agit simplement d'un
programme qui tente de minimiser une certaine quantité en
suivant des instructions simples et précises : il
n'«apprendra» jamais à préparer un café, ou à faire quoi que
ce soit d'autre.
Il existe de nombreux autres algorithmes d'apprentissage,
supervisés ou non, en général plus mathématisés et nettement
plus complexes que les $k$-means, permettant de résoudre des
problèmes similaires à celui du partitionnement de données. Cette page traite par exemple des intéressants séparateurs à vaste marge.
La branche de l'informatique et des mathématiques qui étudie ce
type de problèmes et d'algorithmes est appelée intelligence artificielle -
ce qui sonne bien mais me parait bien mal choisi.
On devrait a minima parler d'intelligence artificielle faible, par opposition à l'intelligence artificielle forte,
dont le but serait de créer une intelligence comparable à
l'intelligence humain. À l'heure actuelle, en 2018, cela
relève purement et simplement de la science-fiction.
Le terme intelligence me pose problème. Quelle
que soit la façon de le définir, il recouvre une notion
d'adaptabilité dont sont incapables les algorithmes comme
les $k$-means décrits dans cette page. Ces algorithmes font ce pour quoi ils ont été programmés, et ne peuvent pas apprendre de façon autonome à résoudre un autre problème.
Il ne faut donc pas fantasmer sur des machines qui seraient
capables de prendre des décisions de manière autonome, et ne
jamais oublier que tout résultat produit par un ordinateur est
une conséquence des choix des personnes qui ont conçu le
programme, ou qui ont modélisé le problème à résoudre. En un
sens, ce que l'on appelle «intelligence artificielle» est un
ensemble de méthodes d'ingénierie (généralement sophistiquées)
permettant de résoudre des problèmes d'optimisation, dans la
lignée de ce que l'on appelait auparavant la recherche
opérationnelle.