Page principale

«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 du 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: 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:

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 :
L'application ci-dessous vous permet de visualiser le déroulement de l'algorithme.
Caractéristiques des données


Caractéristiques 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.

Deux autres inconvénients de cet algorithme :
Reste que moyennant quelques astuces pour bien choisir les moyennes de départ, cet algorithme trouve rapidement des solutions raisonnables en pratique.

«Intelligence artifielle ?»

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.
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.
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 avant la recherche opérationnelle.

Courte bibliographie

Pour aller plus loin sur les algorithmes d'apprentissage :