Introduction à l’intelligence

artificielle
PSI 2022/2023

The development of full artificial intelligence could spell the end

of the human race. . . .It would take off on its own, and re-design
itself at an ever increasing rate. Humans, who are limited by slow
biological evolution, couldn’t compete, and would be superseded.

Stephen Hawking

La tristesse de l’intelligence artificielle est qu’elle est sans artifice,

donc sans intelligence.

Jean Baudrillard

1 Introduction
D’après le dictionnaire Larousse, l’intelligence artificielle est constituée de ”l’ensemble des théories
et des techniques mises en œuvre en vue de réaliser des machines capables de simuler l’intelligence hu-
maine”. Des exemples d’intelligence artificielles sont :

— les moteurs de recherche type Google,

— les systèmes de recommendation sur Youtube, Netflix...
— le systèmes de reconnaissance de langage comme Siri et Alexa,
— les voitures autonomes,
— les jeux vidéos où ”l’ordinateur” prend des décisions (jeu d’échec, jeux de combat...)
— les systèmes de reconnaissance faciale.

Le classement, la reconnaissance de similitudes, de proximités pertinentes est au cœur des pratiques

scientifiques, à la fois comme but et comme méthode. Quand le nombre de données est trop important,
des millions, des milliards, ce que l’on appelle le Big Data, il faut confier cette tâche à des algorithmes.

Depuis le début du 21ème siècle et l’accroissement de la mémoire des ordinateurs, l’intelligence ar-
tificielle s’est surtout développée autour de l’apprentissage automatique (machine learning). Il s’agit de
développer des méthodes qui ”apprennent”, c’est à dire des méthodes qui, en analysant une grande quan-
tité de données (deep learning), peuvent améliorer leurs performances sur un certains nombres de tâches.

1
PSI Intelligence artificielle page 2/??

Nous allons entrer dans ce domaine par deux algorithmes importants, représentatifs et accessibles.

• Le premier algorithme ci-dessous va créer, à partir d’une population d’individus, des catégories.

• Le deuxième essaiera, un classement étant connu, de classer au mieux un nouvel individu dans la
catégorie dont il est le plus proche.

Tout ceci se fera de manière automatique, par calcul, sans intervention, une fois l’algorithme écrit,
de l’intelligence humaine.

2 Algorithme des k-moyennes

Au cours de mes 11 années d’enseignement, j’ai pu observer un très grand nombre d’individus de
l’espèce praeparatorium genus studiosum. D’après mes études, il est possible de séparer cette espèce en
différentes sous-espèces en s’en tenant à la mesure de deux caractères spécifiques :

— la régularité du travail en Français notée x. C’est un réel compris entre 0 et 1. x vaut 0 pour
ceux qui ne font rien toute l’année sauf la veille des écrits, x vaut 1 pour ceux qui connaissent
par coeur les textes des programmes de spe et de sup.
— le nombre moyen de fautes d’homogénéité en DS de Physique noté y. C’est un réel compris
entre 0 et 10.

J’ai ensuite réuni les données sur le plan (x, y). Chaque point du plan correspond à un individu. Pour
plus de lisibilité, seul 40 individus sont représentés sur la figure ci-dessous 1 :

1. Question pour les 5/2 : saurez-vous retrouver quel point correspond à Theekshana ?
PSI Intelligence artificielle page 3/??

On voit bien que quatre groupes semblent se distinguer, qui sont coloriés de couleurs différentes dans
l’image ci-dessous.

On peut alors se poser deux questions :

— Peut-on donner une formulation précise (en l’occurrence mathématique) de ce que l’on entend
par ”groupe”?
— Étant donnés des points comme ci-dessus, peut-on calculer automatiquement une (la) décompo-
sition en groupes ? Calculer le nombre de groupes ?

Ce type de problème n’est pas limité à l’étude des élèves de prépa. On peut, par exemple, vouloir
indexer un ensemble de photos selon ce qui se trouve dessus (séparer les photos en photos de paysages,
photos de famille, photos de vacances). On peut également en avoir besoin pour regrouper des articles
similaires dans un grand corpus de textes...

Une formulation mathématique

Qu’entend-on par ”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. Pour cela, on définit un score de proximité.
Plus les points sont regroupés autour de leur moyenne, plus le score est faible.

Définition Soit S un ensemble (non vide) de points. On définit le score de S par :

X
sc(S) = ||Pi − m(S)||2
Pi ∈S

où m(S) est le barycentre (la ”moyenne”) des points du groupe .

Ce dernier a pour coordonnées (xS , yS ) :

(
1
P
xS = xP
n
1
PPi ∈S i
yS = n Pi ∈S yPi
 PSI Intelligence artificielle page 4/??

où n est le cardinal de S (le nombre d’éléments de S).

Notre problème consiste alors à diviser l’ensemble des points en sous-ensembles de points qui ont un
score très faible. Dans la suite, on va supposer le nombre de groupe connu à l’avance (on le notera k) et
on s’attachera à résoudre le problème suivant :
n
Étant donné un ensemble de points E non videPk de R et un entier k > 1, trouver une
partition de E en k parties {S1 ...Sk } telle que i=1 sc(Si ) soit minimale.

L’algorithme
L’algorithme des k-moyennes permet de résoudre le problème posé en un temps raisonnable.
1. On commence par choisir k points m1 , ...mk dans le plan - appelés ”moyennes”. Généralement, ces
points sont choisis au hasard parmi les points de E.
2. On répète les 2 étapes suivantes jusqu’à ce que les moyennes ne soient plus modifiées :
(a) assigner les points de E selon le mi dont ils sont le plus proche - on obtient ainsi k groupes
numérotés de 1 à k, chacun correspondant à une moyenne ;
(b) recalculer la moyenne de chaque groupe : mi reçoit comme nouvelle valeur le barycentre des
points du groupe i.
Une illustration est montrée ci-dessous. L’algorithme converge toujours.

Codage
On suppose que les caractéristiques de chaque individu est contenu dans un dictionnaire etudiants
dont les clés sont les noms et prénoms des élèves et les valeurs sont le tuple (x, y) associé :
1 etudiants = { ’ GaelMehdi Lelay ’: (0.9 ,1.3) , ’ Ovia Jogarajah ’: (0.7 ,6.3) , ’ Aleksije
Vojinovic ’ :(0.1 ,1.7) , ’ Mokrane Deghine ’ :........}

On dispose par ailleurs d’un dictionnaire groupes dont les clés sont les noms/prénoms et les valeurs
sont des entiers c indiquant le numéro du groupe dont fait parti chaque individu : c = 0, 1, ...k − 1. Au
départ, on suppose que tous les individus sont assignés au groupe 0.
1 groupes = { ’ GaelMehdi Lelay ’: 0 , ’ Ovia Jogarajah ’: 0 , ’ Aleksije Vojinovic ’:0 , ’ Mokrane
Deghine ’ :0 ,...}
 PSI Intelligence artificielle page 5/??

q 1 — Ecrire une fonction init_centre(etudiants,k) qui prend en argument le dictionnaire etu-

diants et un entier k > 1 et qui renvoie une liste de k coordonnées (xi , yi ) pris au hasard dans etudiants.
On pourra utiliser la fonction sample du module random dont voici l’aide :
1 help ( random . sample )
2 Help on method sample in module random :
3
4 sample ( population , k ,) method of random . Random instance
5 Chooses k unique random elements from a population sequence or set .

1 import random as rd
2

3 def init_centre ( etudiants , k ) :

4 ...............
5 ...............
6 ...............
7 ...............
8 return centres

q 2 — Ecrire une fonction dist(P1,P2) prenant en argument deux tuples P1 = (x1,y1) et P2 =

(x2,y2) représentant deux individus et qui renvoie le carré de la distance euclidienne dans le plan
(x, y).
1 def dist ( P1 , P2 ) :
2 ................

q 3 — Ecrire une fonction assignation(etudiants,groupes,centres) prenant en argument le dic-

tionnaire etudiants des individus, le dictionnaire groupes et la liste centres des positions des bary-
centres des k groupes et qui assigne à chaque individu le centre dont il est le plus proche.
1 def assignation ( etudiants , groupes , centres ) :
2 for . . . . . . . . . . . . . . . . . . . . . . :
3 d = float ( ’ inf ’) # distance infinie
4 for . . . . . . . . . . . . . . . . . . . . . . . :
5 a = ..................
6 if a < d :
7 ..................
8 ..................
9 ..........................

q 4 — Ecrire une fonction moyenne(etudiants,groupes) qui renvoie la liste des coordonnées des ba-
rycentres de chaque classe :
1 def moyenne ( etudiants , groupes ) :
2 sx , sy , cpt = [0.0]* k ,[0.0]* k ,[0]* k
3 for ..................
4 .... ....... ........
5 .... ....... ........
6 .... ....... ........
7 .... ....... ........
8 for j in range ( k ) :
9 assert cpt ( k ) .............
10 centres = []
11 for j in range ( k ) :
12 . . .. . . . . .. . . . . .. . . . . ..
13 return centres

q 5 — La fonction representation donne une représentation graphique colorée des classes ; les centres
sont en noir. Remplir cette fonction.
 PSI Intelligence artificielle page 6/??

1 coul = [ ’ bo ’ , ’ ro ’ , ’ go ’ , ’ yo ’ , ’ co ’ , ’ mo ’ , ’ ko ’] # couleurs pour representer les points .

On suppose k < 7.
2 def representation ( etudiants , centres ) :
3 plt . figure ()
4 for x in etudiants :
5 plt . plot ( etudiants [ x ][0] , etudiants [ x ][1] , coul [ . .. .. . .. .. . .. . .. .. ] )
6 for j in range ( len ( centres ) ) :
7 plt . plot (............ ,................ , coul [ -1])
8 plt . show ()

q 6 — Ecrire la fonction kmoyennes(etudiants, k, N) qui renvoie le résultat de l’algorithme des k-

moyennes après N itérations et qui effectue une représentation graphique à chaque étape.
1 def kmoyennes ( etudiants , groupes ,k , N ) :
2 .. .. ... ... .. ... .. ...
3 .... ....... ........
4 .. .. ... ... .. ... .. ...
5 .... ....... ........ # representation graphique a chaque etape
6 .... ....... ........
7 .. . . . . . . . . . . . . . . . . . . . . . . . # representation finale

Les k-moyennes sont un exemple 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.
La seule chose qui lui est fournie est le nombre k de groupes à constituer. Le terme ”apprentissage” doit
cependant être mis entre (beaucoup de) guillemets. 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.

3 k plus proches voisins (KNN)

A l’aide de l’algorithme précédent, nous avon vu que l’espèce praeparatorium genus studiosum pou-
vait être séparée en 4 sous-espèces :

— Groupe 0 : les littéraires homogènes (LIHO). Ils font leur travail en français et écrivent des for-
mules homogènes.

— Groupe 1 : les littéraires inhomogènes (LIINHO). Ils font leur travail en français et écrivent
V = 2πrh.

— Groupe 2 : les non littéraires homogènes (NIHO). Ils connaissent les équations de Maxwell mais
pensent que ”Par-dessus bord” est un jeu de société.

— Groupe 3 : les non littéraires inhomogènes (NIHILO). Ils sont complètement foutus.

Supposons qu’apparaisse un nouvel étudiant. Celui-ci, que nous nommerons H.P par souci d’ano-
nymat, a pour score littéraire x? et pour moyenne d’homogénéité y ? . Pour déterminer à quel groupe
appartient H.P, l’une des méthodes les plus simples est la méthode des k-plus proches voisins, couram-
ment abrégée en KNN. Étant donné le nouvel individu H.P, on cherche les k plus proches individus de
H.P dans le plan (x, y). S’il y a une majorité d’individus LIHO parmi eux, on décide que H.P est un
LIHO, s’il y a une majorité de NIHO, H.P est un NIHO etc... S’il y a égalité entre deux groupes, H.P
sera catégorisé comme inclassable.
 PSI Intelligence artificielle page 7/??

Codage
Les données ont été enregistrées dans un dictionnaire eleves :
1 >>> eleves . keys ()
2 dict_keys ([ ’ nom_groupe ’ , ’ data ’ , ’ num_groupe ’ ])
Regardons la valeur associée à la première clé, la clé nom_groupe :
1 >>> eleves [ ’ nom_groupe ’]
2 [ ’ LIHO ’ , ’ LIINHO ’ , ’ NIHO ’ , ’ NIHILO ’]
Il s’agit donc d’une liste contenant le nom de chacun des groupes. De même, les valeurs associées aux
deux autres clés sont des listes :
1 >>> eleves [ ’ data ’ ][:3] # valeurs de data ( trois premieres )
2 [[0.2 ,6.3] ,[0.9 ,6.7] ,[0.9 ,1.5]]
3 >>> eleves [ ’ num_groupe ’ ][:3] # valeurs de num_groupe ( trois premieres )
4 [3 ,1 ,0]

q 1 — Ecrire une fonction dist_a_x(P,data) qui renvoie la liste des distances entre le point P et
chaque élément d’une liste data. On pourra utiliser la fonction dist de la première partie :
1 def dist_a_x (P , data ) :
2 assert len ( P ) == len ( data [0]) # ??
3 L = [0]* len ( data )
4 ..................
5 ..................
6 ..................

q 2 — Appelons la fonction précédente :

1 P = (0.7 ,4.7)
2 distances = dist_a_x (P , eleves [ ’ data ’ ])

Parmi les distances calculées et mémorisées dans distances, il faut maintenant déterminer les indices
des k plus petites. Pour cela, on commence par créer une liste des indices :
 PSI Intelligence artificielle page 8/??

1 indices = [ i for i in range ( len ( liste_distances ) ) ]

On va ensuite effectuer un tri rapide pour trier simultanément les listes distances et indices. Le
principe du tri rapide est rappelé sur la figure ci-dessous :
1.On choisit un élément particulier appelé pivot. Ici, ce sera le dernier élément de la liste à trier.
2.On partitionne les éléments de la liste en deux parties : les éléments plus petits que le pivot à
gauche, le pivot, les éléments plus grands ou égaux au pivot à droite.
3.On trie les deux parties.

q 3 — Remplir la fonction partitionnement ci-dessous qui renvoie la position finale du pivot après
partitionnement.
1 def partitionnement (L , l ) : # L sera distances , l sera indices
2 assert len ( L ) == len ( l )
3 i , j = 0 ,0
4 while j < ..........:
5 if L [ j ] < L [ -1]:
6 L[j],L[i] = L[i],L[j]
7 l[j],l[i] = l[i],l[j]
8 ........
9 ..........
10 return i

q 4 — Remplir la fonction tri_rapide ci-dessous :

1 def tri_rapide (L , l ) :
2 if len ( L ) <= 1: # condition d ’ arret
3 return l # renvoie la liste contenant l ’ indice correspondant
4 i = partitionnement (L , l )
5 return tri_rapide ( L [...:...] , l [...:...]) +[ l [ -1]]+ tri_rapide ( L [...:...] , l [...:...])

q 5 — Le code :
1 indices_tries = tri_rapide ( distances , indices )

permet d’obtenir la liste des indices triés. Quelle ligne de commande faut-il écrire pour obtenir la liste
des indices des k plus proches voisins ?
1 ........

Ecrire quelques lignes de commande permettant d’obtenir la liste des numéro de groupes auquel appar-
tient les k voisins :
1 Gkppv = []
2 for x in indices_tries [0: k ]:
3 Gkppv . append ( . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . )
 PSI Intelligence artificielle page 9/??

q 6 — Ecrire une fonction groupe_predit(Gkppv,k) qui prend en argument la liste précédente et qui
renvoie le numéro du groupe majoritaire parmi les k voisins et le caractère ’i’ s’il y a égalité entre deux
groupes.
1 def groupe_predit ( Gkppv , k ) :
2 .. . . . . . . . . . . . . . . . . . . . . . . . .

q 7 — Ecrire une fonctionkppv(P,eleves) qui renvoie le numéro de groupe auquel appartient le point
P d’après l’algorithme des k-voisins.
1 .... . . . . .. . . . . .. . . . . ..
2 .... . . . . .. . . . . .. . . . . ..
3 .... . . . . .. . . . . .. . . . . ..
4 .... . . . . .. . . . . .. . . . . ..
5 .... . . . . .. . . . . .. . . . . ..
6 .... . . . . .. . . . . .. . . . . ..
7 .... . . . . .. . . . . .. . . . . ..
8 .... . . . . .. . . . . .. . . . . ..
9 .... . . . . .. . . . . .. . . . . ..
10 .... . . . . .. . . . . .. . . . . ..
11 .... . . . . .. . . . . .. . . . . ..

Matrice de confusion
Pour obtenir une bonne classification et ne pas assigner H.P à un mauvais groupe, il faut s’assurer d’un
bon choix de k. Si k est trop petit, une petite variation dans les résultats de H.P lui fera changer de
groupe. Si k est trop grand, on fera une prédiction du groupe de H.P en prenant en compte les résultats
d’étudiants qui n’ont pas du tout son profil, ce qui n’est ni logique ni efficace.

Afin de mesurer la qualité de l’algorithme, on peut déterminer la matrice de confusion du système

de classification. L’idée est de tester l’algorithme des k plus proches voisins sur des d’individus dont on
connaı̂t déjà le groupe d’appartenance. On compare ensuite le résultat prédit par l’intelligence artificielle
avec le résultat réel.
groupe de départ
LIHO LIINHO NIHO NIHILO
résultat prédit
LIHO 9 1 0 0
LIINHO 0 9 1 0
NIHO 1 0 9 0
NIHILO 0 0 0 10

Table 1 – Pour chaque groupe, 10 étudiants pris au hasard ont été soustraits de leur groupe et leur
appartenance a été prédite avec KNN (k = 5).

q 8 — Ecrire un algorithme qui permet d’obtenir la matrice de confusion de la population eleves. On

prendra 10 étudiants au hasard dans chaque groupe.
1 .... . . . . .. . . . . .. . . . . ..
2 .... . . . . .. . . . . .. . . . . ..
3 .... . . . . .. . . . . .. . . . . ..
4 .... . . . . .. . . . . .. . . . . ..
5 .... . . . . .. . . . . .. . . . . ..
6 .... . . . . .. . . . . .. . . . . ..
7 .... . . . . .. . . . . .. . . . . ..
 PSI Intelligence artificielle page 10/??

8 .... . . . . .. . . . . .. . . . . ..
9 .... . . . . .. . . . . .. . . . . ..
10 .... . . . . .. . . . . .. . . . . ..
11 .... . . . . .. . . . . .. . . . . ..
12 .... . . . . .. . . . . .. . . . . ..
13 .... . . . . .. . . . . .. . . . . ..
14 .... . . . . .. . . . . .. . . . . ..
15 .... . . . . .. . . . . .. . . . . ..
16 .... . . . . .. . . . . .. . . . . ..
17 .... . . . . .. . . . . .. . . . . ..
18 .... . . . . .. . . . . .. . . . . ..
19 .... . . . . .. . . . . .. . . . . ..
20 .... . . . . .. . . . . .. . . . . ..
21 .... . . . . .. . . . . .. . . . . ..
22 .... . . . . .. . . . . .. . . . . ..