Le carnet On est …
Annale 2024-2025 · MI FI

Examen IA — MI FI

Quatre exercices, 22 points : Expectiminimax (extension de minimax aux jeux non déterministes), recuit simulé appliqué au clustering, apprentissage par renforcement sur grille 4×4 et ConvNet Keras pour Fashion MNIST. Date : 09/04/2025.

2h · MI FI 4 exercices · sans documents Date : 09/04/2025

i. Le sujet

Le PDF ne s'affiche pas. Télécharger le sujet.

↗ Sujet en plein écran

ii. Notions mobilisées

ExoSujetNotion cléChapitre
1Jeux non déterministesExpectiminimax (extension de Minimax avec niveau Chance)Hors cours S2 — extension classique
2Clustering via recuit simuléReprésentation, espace de recherche, voisinage, énergieCM6
3RL sur grille 4×4MDP (états, actions, récompenses, transitions)CM4
Value IterationBoucle Bellman, convergence vers V*CM4
4ConvNet Fashion MNISTConvolutions, MaxPooling, Dropout, Flatten, Dense, SoftmaxCM2
Entraînement Kerasbatch_size, epochs, fit, validation_dataCM1 · CM2

1. Exercice 1 — Jeux non déterministes (5 pts)

L'algorithme Expectiminimax généralise Minimax en introduisant un nouveau type de nœud : les nœuds Chance. La valeur d'un nœud Chance est la moyenne pondérée de ses fils, chaque branche étant étiquetée par la probabilité de l'événement aléatoire correspondant.

Q1 — Compléter l'arbre

L'arbre du sujet : Max en racine, deux fils Chance, puis nœuds Min avec leurs feuilles. On remonte les valeurs depuis les feuilles.

Max 1.4 C₁ 1.4 C₂ 1.0 Min 1 Min 5 Min 1 Min 1 4 1 5 8 1 3 2 1 0.9 0.1 0.3 0.7
Calcul détaillé (bottom-up)
  1. Niveau Min — chaque nœud Min prend le minimum de ses fils :
    • Min(4, 1) = 1 · Min(5, 8) = 5 · Min(1, 3) = 1 · Min(2, 1) = 1
  2. Niveau Chance — moyenne pondérée par les probabilités :
    • C₁ = 0,9 × 1 + 0,1 × 5 = 0,9 + 0,5 = 1,4
    • C₂ = 0,3 × 1 + 0,7 × 1 = 0,3 + 0,7 = 1,0
  3. Racine Max — prend le maximum : Max(1,4 ; 1,0) = 1,4

Q2 — Meilleur coup de Max

La racine vaut 1,4 et correspond au coup gauche (vers C₁). Max doit donc choisir l'action de gauche pour maximiser son espérance de gain.

Q3 — Signification de la racine

Minimax « standard » La valeur de la racine est la valeur garantie que Max peut obtenir contre un adversaire jouant optimalement (le pire des cas). En jeu déterministe, c'est un score certain.
Expectiminimax La racine est l'espérance de gain de Max contre un adversaire optimal, en moyennant sur les événements aléatoires. C'est une grandeur statistique, pas un score garanti : sur une partie donnée le résultat peut être très différent.

Q4 — Représenter un nœud Chance

(a) Lancer d'une pièce — deux issues équiprobables : pile ou face.

C 0,5 0,5 Pile Face

(b) Lancer deux dés sans tenir compte de l'ordre — 21 résultats possibles (combinaisons avec répétition C(6+2-1, 2) = 21).

Pour {i, j} avec i ≠ j : 2 façons sur 36 → probabilité 2/36 = 1/18.

Pour {i, i} (double) : 1 façon sur 36 → probabilité 1/36.

Le nœud Chance a donc 21 fils, 15 étiquetés 1/18 (paires différentes) et 6 étiquetés 1/36 (doubles).

⚠ Sans tenir compte de l'ordre « {4, 5} » regroupe les deux séquences (4 puis 5) et (5 puis 4). On somme leurs probabilités : 1/36 + 1/36 = 2/36. C'est pourquoi les paires distinctes valent 1/18, et les doubles seulement 1/36.

2. Exercice 2 — Recuit simulé pour le clustering (5 pts)

Le problème : répartir n points de \(\mathbb{R}^p\) en k clusters tels que les points d'un même cluster soient proches, et ceux de clusters différents soient éloignés.

Q1 — Représentation d'une solution

Codage proposé Une solution est une fonction d'affectation qui à chaque point associe un numéro de cluster. Concrètement, un vecteur S = (s₁, s₂, ..., sₙ) où sᵢ ∈ {1, 2, ..., k} indique à quel cluster le point i est affecté.

Avantages de ce codage :

  • Représentation compacte (vecteur de n entiers).
  • Voisinage simple à définir (changer un seul élément).
  • Calcul d'énergie local possible (recalcul rapide après changement).

Q2 — Taille de l'espace de recherche

Chaque point a k choix de cluster, et il y a n points. Donc :

\(\text{Espace de recherche} = k^n\)
Pourquoi le RS est-il pertinent ici ? L'espace est combinatoire (exponentiel en n). Pour n = 100 et k = 5, on a 5¹⁰⁰ ≈ 8 × 10⁶⁹ solutions — impossible à explorer exhaustivement. Le RS échantillonne intelligemment cet espace en exploitant la structure locale via le voisinage, et évite les minima locaux grâce à la règle de Metropolis.

À noter : cette estimation surestime — beaucoup de configurations sont équivalentes par permutation des étiquettes de clusters. Mais l'ordre de grandeur reste exponentiel.

Q3 — Voisinage et énergie

Voisinage Une solution voisine de S est obtenue en changeant l'affectation d'un seul point : prendre un point i au hasard et lui affecter un autre cluster j ≠ sᵢ.
  • Voisinage de taille n × (k − 1).
  • Modification minimale → calcul d'énergie local.
Énergie (à minimiser) L'énergie traduit l'objectif : points proches dans un même cluster, éloignés entre clusters. Une formulation classique :
\(E(S) = \sum_{c=1}^{k} \sum_{i \in c} \|x_i - \mu_c\|^2\)
où μ_c est le centroïde du cluster c. C'est l'inertie intra-classe (objectif de k-means).
📌 Variante
On peut soustraire l'inertie inter-classe ou diviser par elle, pour favoriser explicitement l'éloignement entre clusters. Mais l'inertie intra-classe seule suffit en pratique.

3. Exercice 3 — Apprentissage par renforcement (6 pts)

Un agent se déplace sur une grille 4×4. Case verte = objectif. Trois cases rouges = obstacles.

+1 × × × (1,1) (1,2) (1,3) (1,4) (4,1)

Q1 — Modélisation du problème (MDP)

Cadre : Markov Decision Process Un MDP est défini par le quadruplet (S, A, T, R) :
  • S (états) — les 13 cases praticables (les 16 cases moins les 3 obstacles).
  • A (actions) — déplacements : haut, bas, gauche, droite. Une action sortant de la grille ou allant sur un obstacle laisse l'agent sur place (ou est interdite).
  • T(s, a, s') — fonction de transition. Déterministe ici : l'action choisie est exécutée exactement (probabilité 1 sur la case cible). On peut aussi modéliser une version stochastique (le glissement Frozen Lake).
  • R(s, a) — récompense. +1 à l'arrivée sur la case verte, optionnellement −1 sur les rouges pour éviter de tomber dedans, et 0 ou un léger −0,04 ailleurs pour favoriser les chemins courts.

Choix supplémentaires à argumenter :

  • Le facteur d'actualisation γ ∈ [0,1) (typiquement 0,9) pénalise les récompenses tardives.
  • L'état terminal : la case verte (épisodique) ou pas (continu avec récompense périodique).

Q2 — Définition d'une stratégie (policy)

Stratégie π Une stratégie (ou politique) est une fonction π : S → A qui à chaque état associe l'action à entreprendre. Elle peut être déterministe (une action par état) ou stochastique (distribution de probabilité sur les actions).

Exemple de stratégie déterministe pour cette grille : « aller toujours vers le haut, à défaut vers la gauche ». Cette stratégie n'est ni optimale ni complète, mais elle est valide pour illustrer.

Stratégie optimale π* — celle qui maximise l'espérance des récompenses futures cumulées (actualisées) depuis chaque état. C'est ce que Value Iteration construit indirectement.

Q3 — Utilité de Value Iteration

L'algorithme calcule itérativement la fonction de valeur optimale V*(s), qui représente l'espérance des récompenses cumulées en partant de s et en jouant optimalement. Une fois V* connue, la stratégie optimale s'en déduit :

\(\pi^*(s) = \arg\max_a \left[ R(s, a) + \gamma \sum_{s'} T(s, a, s') V^*(s') \right]\)

Value Iteration est fondé sur l'équation de Bellman et converge sous des hypothèses douces (γ < 1, espace fini).

Q4 — Deux premières itérations

Hypothèses simplificatrices Pour mener le calcul à la main :
  • Transitions déterministes (l'action choisie est toujours exécutée).
  • Récompense R(s, a) = +1 si l'action mène à la case verte, 0 sinon (récompense au state' atteint).
  • Facteur d'actualisation γ = 0,9.
  • Initialisation V₀(s) = 0 pour tous les états.
  • Actions interdites (sortie de grille, case rouge) → état inchangé.

Itération 1

Pour chaque état s, on calcule Q₁(s, a) = R(s, a) + γ · V₀(s'), puis V₁(s) = max_a Q₁(s, a).

Comme V₀ = 0 partout, on a Q₁(s, a) = R(s, a). Donc :

  • V₁(s) = 1 pour toute case adjacente à la case verte (puisqu'au moins une action mène à +1) — soit (1,1), (1,3) et la case verte elle-même.
  • V₁(s) = 0 pour toutes les autres cases.

Itération 2

On recalcule Q₂(s, a) = R(s, a) + γ · V₁(s'). La valeur se propage d'une case :

ÉtatMeilleure actionV₂(s)Détail
Case verte (1,2)—1,0Terminal (ou récompense reçue à l'arrivée)
(1,1)→ (1,2)1,0R + γ × V₁ = 1 + 0,9 × 0 = 1
(1,3)← (1,2)1,01 + 0,9 × 0 = 1
(1,4)← (1,3)0,90 + 0,9 × V₁(1,3) = 0,9 × 1 = 0,9
(2,1)↑ (1,1)0,90 + 0,9 × 1 = 0,9
(2,4)↑ (1,4) puis ←0,0V₁((1,4)) = 0, donc Q = 0,9 × 0 = 0
autres (cases plus éloignées)—0,0Aucun voisin avec V₁ > 0
📌 Propagation progressive
À chaque itération, la valeur +1 de l'objectif diffuse d'une case vers l'extérieur, amortie par γ. Au bout de quelques itérations, toutes les cases praticables ont une valeur non nulle reflétant leur distance à l'objectif. La stratégie optimale dérive alors naturellement de V*.

4. Exercice 4 — Deep Learning : Fashion MNIST (6 pts)

Classification de 60 000 images 28×28 en niveaux de gris, 10 classes (T-shirt, Trouser, Pullover, Dress, Coat, Sandal, Shirt, Sneaker, Bag, Ankle boot). Le modèle Keras du sujet :

model = Sequential()
model.add(Conv2D(32, kernel_size=(3, 3), activation='relu', input_shape=input_shape))
model.add(Conv2D(64, (3, 3), activation='relu'))
model.add(Conv2D(128, (3, 3), activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))
model.add(Dropout(0.25))
model.add(Flatten())
model.add(Dense(128, activation='relu'))
model.add(Dropout(0.5))
model.add(Dense(num_classes, activation=Activation(tf.nn.softmax)))

Q1 — Avantages d'un ConvNet sur un réseau entièrement connecté

Partage de poids Un filtre de convolution réutilise les mêmes paramètres sur toute l'image. Sur une 28×28, un Dense(128) sur l'entrée plate nécessite 784 × 128 ≈ 100 000 poids ; une Conv2D(32, 3×3) n'en a que 32 × 9 + 32 = 320.
Invariance par translation Un motif (col de t-shirt, lacet de chaussure) est détecté indépendamment de sa position dans l'image. Les filtres reconnaissent des motifs locaux, le pooling apporte une tolérance aux petits décalages.
  • Hiérarchie de représentations : les premières couches détectent des contours, les suivantes des motifs plus complexes (textures, parties d'objets), les dernières des concepts (chaussure vs sac).
  • Moins de paramètres : moins de risque de sur-apprentissage, entraînement plus rapide.
  • Exploite la structure 2D de l'image (voisinage spatial), contrairement à un Dense qui aplatit tout.

Q2 — Intérêt du Softmax en dernière couche

Softmax — distribution de probabilité sur les classes \[\text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^{K} e^{z_j}}\] Transforme un vecteur de scores réels en une distribution de probabilités : chaque sortie est dans [0, 1] et la somme vaut 1. Permet :
  • Interpréter chaque sortie comme P(classe | image).
  • Choisir la classe prédite par argmax.
  • Utiliser la cross-entropy comme fonction de perte (couplée naturellement au softmax).

Q3 — Description synthétique des couches

CoucheRôleEffet sur l'entrée 28×28×1
Conv2D(32, 3×3)32 filtres de convolution26×26×32 (sans padding)
Conv2D(64, 3×3)64 filtres24×24×64
Conv2D(128, 3×3)128 filtres22×22×128
MaxPooling2D(2×2)Sous-échantillonnage par max11×11×128
Dropout(0.25)Régularisation, désactivation aléatoire de 25% des neuronesmême shape
FlattenAplatit le tenseur en vecteur15 488
Dense(128)Couche entièrement connectée128
Dropout(0.5)Régularisation plus agressive128
Dense(num_classes)Couche de sortie + softmax10 probabilités

Q4 — Couches sans paramètres et hyperparamètres

Couches sans paramètres apprenables
  • MaxPooling2D — pas de poids, juste une opération de max sur des fenêtres. Hyperparamètres : pool_size, strides, padding.
  • Dropout — pas de poids, désactive aléatoirement des neurones à l'entraînement. Hyperparamètre : rate (proportion de neurones désactivés).
  • Flatten — pas de poids, simple réorganisation des données. Aucun hyperparamètre.

Les couches Conv2D et Dense ont des paramètres apprenables (filtres, poids, biais). Leurs hyperparamètres principaux : nombre de filtres / neurones, taille du noyau (kernel_size), pas (strides), padding, fonction d'activation.

Q5 — batch_size et epochs

batch_size Nombre d'exemples utilisés pour calculer un gradient et faire une mise à jour des poids. Sur 60 000 exemples avec batch_size = 128, chaque epoch comporte 60000 / 128 ≈ 469 mises à jour.
  • Petit batch → gradient bruité mais utile pour échapper aux minima locaux.
  • Gros batch → gradient stable mais convergence vers des minima « plus larges » potentiellement moins bons en généralisation.
epochs Nombre de passages complets sur l'ensemble d'entraînement. Si on a epochs = 10, le modèle voit chaque exemple 10 fois. Trop d'epochs → sur-apprentissage. Surveiller la perte sur le set de validation (validation_data).
🔑 Règle de pouce
On surveille la perte de validation en plus de la perte d'entraînement. Si la première remonte alors que la seconde continue de baisser, c'est le signe d'un sur-apprentissage : arrêter l'entraînement (early stopping) ou augmenter la régularisation.

★ Notions ré-activées

  • Expectiminimax = Minimax + nœuds Chance (espérance pondérée)
  • Racine Expectiminimax = espérance, pas un score garanti
  • Recuit simulé sur clustering : codage par affectation, espace k^n
  • Voisinage RS = changer l'affectation d'un point
  • Énergie clustering = inertie intra-classe
  • MDP : (S, A, T, R) + γ
  • Stratégie π : S → A (déterministe ou stochastique)
  • Value Iteration : Q(s,a) = R + γ Σ T·V(s'), V(s) = max_a Q(s,a)
  • π*(s) = argmax_a [R(s,a) + γ Σ T·V*(s')]
  • ConvNet vs Dense : partage de poids, invariance, hiérarchie
  • Softmax = distribution de probabilités sur les classes
  • Couches sans paramètres : MaxPool, Dropout, Flatten
  • batch_size = pas de mise à jour ; epochs = passages complets