Introduction à l'intelligence artificielle

1. Qu'est-ce que l'intelligence artificielle ?

L'intelligence artificielle (IA) est la branche de l'informatique qui cherche à doter les machines de capacités habituellement associées à l'intelligence humaine : percevoir, raisonner, décider, apprendre, comprendre le langage. Plutôt que de programmer explicitement la solution d'un problème, on cherche souvent à faire en sorte que la machine apprenne à le résoudre à partir d'exemples.

Pourquoi l'IA ? Certains problèmes sont trop complexes ou trop variables pour être codés à la main : reconnaître un chiffre manuscrit, filtrer un courriel indésirable, recommander un film. Pour ces tâches, il est plus efficace d'apprendre un comportement à partir de grandes quantités de données que d'énumérer toutes les règles.

2. Les sous-domaines de l'IA

L'IA est un vaste domaine qui regroupe plusieurs sous-disciplines :

3. L'apprentissage automatique (Machine Learning)

L'apprentissage automatique consiste à construire un modèle capable de faire des prédictions à partir de données. Chaque donnée est généralement décrite par un vecteur de caractéristiques (features). On distingue trois grandes familles :

4. Apprentissage supervisé : classification et régression

En apprentissage supervisé, on dispose d'un jeu de données étiqueté : chaque exemple est un couple (x, y) où x est le vecteur de caractéristiques et y l'étiquette connue. Le modèle apprend la correspondance x → y pour ensuite prédire l'étiquette de données inédites. Selon la nature de y :

• Classification  : y est une classe (valeur discrète). Ex. : courriel « spam » ou « non spam », fleur de type A, B ou C.
• Régression  : y est une valeur numérique continue. Ex. : prédire le prix d'un appartement.

5. L'algorithme des k plus proches voisins (KNN)

Le KNN (k-Nearest Neighbors) est l'un des algorithmes de classification les plus simples. Son principe repose sur une intuition : un point ressemble à ses voisins. Pour classer un nouveau point :

1. Calculer la distance entre ce point et tous les points étiquetés du jeu d'apprentissage.
2. Sélectionner les k plus proches voisins.
3. Attribuer au point la classe majoritaire parmi ces k voisins (vote).

On utilise le plus souvent la distance euclidienne. Pour deux points a = (a₁, …, a_n) et b = (b₁, …, b_n) à n caractéristiques :

KNN est un apprentissage « paresseux » (lazy learning) : il n'y a pas de phase d'entraînement, on garde simplement les données et tout le calcul se fait au moment de la prédiction. La complexité d'une prédiction est en \(O(N·n)\) pour N points en dimension n, à laquelle s'ajoute le tri ou la sélection des k voisins.

6. Implémentation de KNN en Python

from collections import Counter

def distance(a, b):
    """Distance euclidienne entre deux points (listes de coordonnées)."""
    s = 0
    for i in range(len(a)):
        s += (a[i] - b[i]) ** 2
    return s ** 0.5

def knn(donnees, etiquettes, x, k):
    """donnees : liste de points ; etiquettes : classe de chaque point.
       x : point a classer ; k : nombre de voisins.
       Renvoie la classe majoritaire parmi les k plus proches voisins."""
    # 1. distances de x a tous les points etiquetes
    dists = [(distance(x, donnees[i]), etiquettes[i])
             for i in range(len(donnees))]
    # 2. on garde les k plus proches
    dists.sort(key=lambda couple: couple[0])
    k_voisins = [classe for (_, classe) in dists[:k]]
    # 3. vote majoritaire
    return Counter(k_voisins).most_common(1)[0][0]

# --- exemple ---
donnees    = [[1, 1], [2, 1], [4, 5], [5, 4]]
etiquettes = ['A',    'A',    'B',    'B']
print(knn(donnees, etiquettes, [1, 2], k=3))   # -> 'A'
print(knn(donnees, etiquettes, [5, 5], k=3))   # -> 'B'

7. Évaluer un classifieur : la matrice de confusion

Pour mesurer la qualité d'un classifieur, on compare ses prédictions aux vraies étiquettes d'un jeu de test. La matrice de confusion croise classes réelles et classes prédites. Dans le cas à deux classes (positif / négatif) :

On en déduit plusieurs indicateurs :

• Exactitude (accuracy) : proportion de bonnes prédictions = (VP + VN) / (VP + VN + FP + FN).
• Précision : parmi les prédits positifs, combien le sont vraiment = VP / (VP + FP).
• Rappel (recall, sensibilité) : parmi les réels positifs, combien sont retrouvés = VP / (VP + FN).

8. Bien choisir le paramètre k

Le choix de k influence fortement le KNN :

• k trop petit (ex. k = 1) : le modèle est très sensible au bruit et aux points aberrants (surapprentissage).
• k trop grand : les frontières entre classes deviennent floues, on prend en compte des voisins lointains (sous-apprentissage).

En pratique, on essaie plusieurs valeurs de k, on construit la matrice de confusion sur un jeu de test pour chacune, et on retient celle qui donne les meilleurs indicateurs. On choisit souvent un k impair dans le cas à deux classes pour éviter les égalités au vote.

9. Apprentissage non supervisé : la segmentation

En apprentissage non supervisé, les données ne sont pas étiquetées : on ne connaît pas la classe des points. L'objectif est de découvrir une structure cachée. La segmentation (ou clustering) consiste à regrouper un ensemble d'éléments hétérogènes en sous-groupes (clusters) liés par des caractéristiques communes : les points d'un même groupe se ressemblent, et ceux de groupes différents diffèrent.

10. L'algorithme des k-moyennes (K-means)

K-means partitionne les données en k clusters. Chaque cluster est représenté par son centre (ou centroïde), la moyenne des points qu'il contient. L'algorithme alterne deux étapes jusqu'à stabilisation :

1. Initialisation : choisir k centres (souvent k points tirés au hasard).
2. Affectation : associer chaque point au centre le plus proche (distance euclidienne).
3. Mise à jour : recalculer chaque centre comme la moyenne des points qui lui sont affectés.
4. Répéter les étapes 2 et 3 jusqu'à ce que les centres ne bougent plus (ou plus d'affectation ne change).

L'algorithme cherche à minimiser l'inertie, somme des distances au carré de chaque point à son centre :

11. Implémentation de K-means et convergence

def distance(a, b):
    return sum((a[i] - b[i]) ** 2 for i in range(len(a))) ** 0.5

def plus_proche(x, centres):
    """Indice du centre le plus proche de x."""
    best, dmin = 0, distance(x, centres[0])
    for j in range(1, len(centres)):
        d = distance(x, centres[j])
        if d < dmin:
            best, dmin = j, d
    return best

def moyenne(points):
    """Centre (moyenne) d'une liste de points de meme dimension."""
    n = len(points)
    dim = len(points[0])
    return [sum(p[i] for p in points) / n for i in range(dim)]

def kmeans(donnees, centres, iter_max=100):
    """centres : k centres initiaux. Renvoie (centres, affectation)."""
    for _ in range(iter_max):
        # 1. affectation
        groupes = [[] for _ in centres]
        affectation = []
        for x in donnees:
            j = plus_proche(x, centres)
            groupes[j].append(x)
            affectation.append(j)
        # 2. mise a jour des centres
        nouveaux = [moyenne(g) if g else centres[j]
                    for j, g in enumerate(groupes)]
        if nouveaux == centres:        # stabilisation
            break
        centres = nouveaux
    return centres, affectation

# --- exemple ---
donnees = [[1, 1], [1, 2], [2, 1], [8, 8], [9, 8], [8, 9]]
centres0 = [[1, 1], [8, 8]]
centres, aff = kmeans(donnees, centres0)
print(centres)   # -> deux centres bien separes
print(aff)       # -> [0, 0, 0, 1, 1, 1]

12. Récapitulatif

CPGE MP / PSI — Informatique · Chapitre 2-2 · Introduction à l'intelligence artificielle