Examen IA — GM FA

i. Le sujet

Sujet officiel de la session principale 2024-2025 — ING2 GM FA. Aucun document autorisé.

ii. Correction commentée

Pour chaque exercice : énoncé reformulé + correction étape par étape + renvoi au CM concerné.

Exercice 1 — Jeux : Minimax + élagage α-β (5 pts, hors CM mais classique)

Feuilles de gauche à droite : 2, 3, 5, 9, 0, 1, 7, 5. Arbre binaire de profondeur 3, racine = Max.

1. Construction de l'arbre.

                       Max  (racine)
                      /         \
                   Min           Min
                  /    \        /    \
                Max   Max     Max    Max
                / \   / \     / \    / \
               2   3 5   9   0   1  7   5

Niveaux (en partant de la racine) : Max → Min → Max → feuilles.

2. Signification des feuilles. Les feuilles sont les valeurs d'évaluation des positions terminales (ou de positions à profondeur limitée). Elles peuvent être obtenues par :

• la règle du jeu si la position est terminale (gain, perte, nulle) ;
• une fonction d'évaluation heuristique $h(\text{position})$ si on coupe la recherche à une profondeur donnée (Max cherche à maximiser $h$, Min à la minimiser).

3. Technique de parcours. Minimax explore l'arbre en profondeur d'abord (DFS) et remonte récursivement les valeurs (post-ordre).

4. Application Minimax. On remonte les valeurs depuis les feuilles :

Valeur de la racine = 3. Signification : si les deux joueurs jouent optimalement, Max est assuré d'obtenir au moins 3 et Min de limiter Max à au plus 3.

5. Principe et intérêt de l'élagage α-β. Optimisation de Minimax qui élague les branches dont on est sûr qu'elles n'influenceront pas la décision finale. Le résultat est identique à Minimax, mais on évite d'explorer une partie de l'arbre.

• α = meilleure valeur que Max peut garantir jusqu'ici. Valeur initiale : $\alpha = -\infty$.
• β = meilleure valeur que Min peut garantir jusqu'ici. Valeur initiale : $\beta = +\infty$.
• Coupure dès que $\alpha \ge \beta$ (le nœud courant ne sera pas choisi).

6. Application de Minimax + élagage α-β (parcours gauche → droite).

Racine Max (α=-∞, β=+∞)
├─ Min gauche (α=-∞, β=+∞)
│  ├─ Max (α=-∞, β=+∞)
│  │  ├─ feuille 2 → α=2
│  │  └─ feuille 3 → α=3
│  │  retourne 3   (Max gauche = 3)
│  │  → Min : β = min(+∞, 3) = 3
│  ├─ Max (α=-∞, β=3)
│  │  ├─ feuille 5 → α=5
│  │  ❗ 5 ≥ β=3  ⇒ COUPURE β  (feuille 9 NON visitée)
│  │  retourne ≥5
│  │  → Min : min(3, ≥5) = 3
│  retourne 3   (Min gauche = 3)
│  → Racine : α = max(-∞, 3) = 3
├─ Min droite (α=3, β=+∞)
│  ├─ Max (α=3, β=+∞)
│  │  ├─ feuille 0 → α reste 3 (0 < 3)
│  │  └─ feuille 1 → α reste 3 (1 < 3)
│  │  retourne 1   (Max = 1)
│  │  → Min : β = min(+∞, 1) = 1
│  ❗ α=3 ≥ β=1  ⇒ COUPURE α  (sous-arbre Max droit NON visité)
│  retourne ≤1
│  → Racine : max(3, ≤1) = 3
Racine = 3  ✓

Feuilles visitées : 2, 3, 5, 0, 1 (5 feuilles sur 8). Feuilles élaguées : 9, 7, 5.

7. Mesure de l'amélioration de l'élagage. On compare le nombre de nœuds (typiquement les feuilles évaluées) avec et sans élagage.

Sur cet exemple l'élagage évite 3 évaluations de feuilles sur 8 (≈ 37,5 % de gain). En général, dans le meilleur cas (ordre optimal des fils), $\alpha$-$\beta$ visite $O(b^{d/2})$ nœuds au lieu de $O(b^d)$ — soit on peut explorer deux fois plus profondément à coût égal.

Exercice 2 — Apprentissage par renforcement : gridworld 8×5 (4 pts, CM5)

Grille 8 colonnes (A–H) × 5 lignes (1–5). Récompense : +10 pour toute action menant à F3 (état absorbant), −1 sinon. Facteur d'actualisation $\gamma$.

Stratégie $\pi_1$ : presque toutes les cases pointent ↓, sauf la ligne 5 qui pointe → vers F5 puis ↑ pour atteindre F3 (F4 pointe ↑, F3 = but).

1. Gain à long terme depuis A1, A5, H1, H5 sous $\pi_1$. Le gain est la somme actualisée des récompenses $G = \sum_{t \ge 0} \gamma^t r_{t+1}$ le long de la trajectoire générée par $\pi_1$ jusqu'à atteindre F3.

On analyse les trajectoires :

• A1 : la stratégie est ↓ partout en colonne A → A1 → A2 → A3 → A4 → A5 (4 pas en ↓, récompense −1 chacun, on n'est pas encore en F3). Puis ligne 5 pointe → : A5 → B5 → C5 → D5 → E5 → F5 (5 pas, récompense −1, puis arrivée à F5 récompense −1). Puis F5 → F4 (↑, récompense −1). Puis F4 → F3 (↑, récompense +10, fin).
  Total : 4 + 5 + 1 + 1 = 11 actions ; les 10 premières donnent −1 et la 11ᵉ donne +10. $$G(A1) = -\sum_{t=0}^{9} \gamma^t + 10\,\gamma^{10} = -\frac{1 - \gamma^{10}}{1 - \gamma} + 10\,\gamma^{10}.$$
• A5 : on est déjà ligne 5. A5 → B5 → C5 → D5 → E5 → F5 (5 actions à −1) → F4 (−1) → F3 (+10). Total 7 actions. $$G(A5) = -\frac{1 - \gamma^{6}}{1 - \gamma} + 10\,\gamma^{6}.$$
• H1 : colonne H pointe ↓ : H1 → H2 → H3 → H4 → H5 (4 actions à −1). Ligne 5 : H5 → G5 (← , −1) → F5 (← , −1). Puis F5 → F4 (−1) → F3 (+10). Total : 4 + 2 + 1 + 1 = 8 actions. $$G(H1) = -\frac{1 - \gamma^{7}}{1 - \gamma} + 10\,\gamma^{7}.$$
• H5 : déjà ligne 5. H5 → G5 → F5 (2 × −1) → F4 (−1) → F3 (+10). Total 4 actions. $$G(H5) = -\frac{1 - \gamma^{3}}{1 - \gamma} + 10\,\gamma^{3}.$$

2. Argument intuitif que $\pi_1$ n'est pas optimale. Depuis A1, le chemin direct (↓↓↓↓↓ jusqu'à A5 puis → → → → → → ↑ ↑ vers F3) compte 11 actions, alors que descendre moins et bifurquer plus tôt serait plus court (ex. A1 → A2 → A3 → B3 → C3 → D3 → E3 → F3 ne fait que 7 actions, dont la dernière à +10). De manière générale, $\pi_1$ fait passer toutes les cases du haut par la ligne 5 au lieu de viser directement F3 → trajectoires inutilement longues → cumul de récompenses négatives → gain plus faible (car $\gamma < 1$ pénalise les récompenses lointaines).

3. Modification → stratégie optimale $\pi_2$. Pour chaque case, on prend la direction qui mène vers F3 par le plus court chemin (distance de Manhattan minimale). Schématiquement :

• Cases à gauche de F : aller → puis ↓ ou ↑ vers la ligne 3.
• Cases à droite de F : aller ← puis ↓ ou ↑ vers la ligne 3.
• Cases en haut de la ligne 3 : aller ↓ jusqu'à la ligne 3 puis → ou ← vers F.
• Cases en bas de la ligne 3 : aller ↑ jusqu'à la ligne 3 puis → ou ← vers F.

$\pi_2$ est l'ensemble de ces flèches « radiales » vers F3.

4. Algorithme qui aurait trouvé $\pi_2$. L'algorithme de Value Iteration (du cours CM5) ; ou plus généralement tout algorithme de programmation dynamique sur un MDP (Policy Iteration), ou un Q-learning à convergence.

5. Principe de Value Iteration.

• Objectif : calculer la fonction de valeur optimale $V^*(s)$ puis en déduire la stratégie optimale $\pi^*(s) = \arg\max_a Q^*(s, a)$.
• Ce qu'il calcule : $V(s)$ pour tout état $s \in S$, par application répétée de l'équation de Bellman optimale.
• Comment :
  1. Initialiser $V(s)$ à des valeurs quelconques (souvent 0).
  2. Répéter : pour chaque état $s$, pour chaque action $a$, $Q(s, a) = R(s, a) + \gamma \sum_{s'} T(s, a, s') V(s')$, puis $V(s) \leftarrow \max_a Q(s, a)$.
  3. Arrêt quand $\max_s |V_{k+1}(s) - V_k(s)| < \varepsilon$.

Exercice 3 — Deep learning : Convnet niveau de gris (8 pts, CM1 + CM2)

On veut classer des images en niveau de gris en nbClasses catégories avec un Convnet.

1. Types de couches d'un Convnet.

• Couche d'entrée (tenseur image).
• Couches de convolution (Conv2D) + activation (ReLU).
• Couches de pooling (typiquement MaxPooling).
• Couches de Dropout (régularisation).
• Flatten pour aplatir le tenseur en vecteur.
• Couches entièrement connectées (Dense) avec activation ReLU.
• Couche de sortie Dense avec softmax.

2. Couche de sortie justifiée. Type : Dense(nbClasses, activation='softmax').

• nbClasses neurones car on a $nbClasses$ classes (un score par classe).
• Softmax car on veut une distribution de probabilités : $\sum_k \hat y_k = 1$, $\hat y_k \in [0,1]$. Compatible avec une perte d'entropie croisée catégorielle.

3. Hyperparamètres et nombre de paramètres par couche.

4. Comment les paramètres sont calculés (5 phrases max).

1. On choisit une fonction de perte $\mathcal{L}$ qui mesure l'écart entre $\hat y$ et $y$.
2. Pour chaque mini-batch, passe avant : calcul des activations couche par couche.
3. On calcule $\mathcal{L}$ puis le gradient $\nabla_\theta \mathcal{L}$ par rétropropagation (règle de la chaîne).
4. L'optimiseur met à jour les poids par descente de gradient : $\theta \leftarrow \theta - \eta \nabla_\theta \mathcal{L}$.
5. On répète sur tous les mini-batches pendant epochs passages de l'ensemble d'apprentissage.

5. Rôle de la fonction de perte + choix. Rôle : quantifier l'écart entre la prédiction $\hat y$ du réseau et la vraie étiquette $y$ ; c'est l'objectif à minimiser par la descente de gradient. Choix ici : categorical_crossentropy (entropie croisée catégorielle) car on est en classification multi-classes avec softmax et étiquettes one-hot : $$\mathcal{L}_{CCE} = -\sum_{k=1}^{nbClasses} y_k \log \hat y_k.$$ Si les étiquettes sont des entiers (non one-hot), on prend sparse_categorical_crossentropy.

6. Rôle du taux d'apprentissage (learning rate $\eta$). C'est le pas de la descente de gradient : $\theta \leftarrow \theta - \eta \nabla_\theta \mathcal{L}$.

• Trop petit → convergence lente, risque de bloquer en minimum local.
• Trop grand → oscillation, divergence (la perte explose).

7. Rôle de epochs et batch_size.

• epochs = nombre de passages complets sur l'ensemble d'apprentissage.
• batch_size = taille d'un mini-batch : nombre d'exemples utilisés pour calculer une mise à jour des poids (mini-batch SGD).

8. Métrique de test. L'accuracy (taux de bonnes classifications) sur l'ensemble de test : $$\text{accuracy} = \frac{\#\{i \mid \hat y_i = y_i\}}{N_{test}}.$$ Calcul : prédire $\hat y_i = \arg\max_k \text{softmax}_k$ pour chaque image test, compter les égalités avec $y_i$, diviser par $N_{test}$.

9. Deux façons d'évaluer la performance par classe.

• Matrice de confusion : tableau $nbClasses \times nbClasses$ où $M_{ij}$ = nombre d'exemples de vraie classe $i$ prédits comme $j$. On lit immédiatement la diagonale et les confusions.
• Précision / rappel / F1 par classe : $$P_c = \frac{TP_c}{TP_c + FP_c}, \quad R_c = \frac{TP_c}{TP_c + FN_c}, \quad F1_c = \frac{2 P_c R_c}{P_c + R_c}.$$ $TP_c$ = exemples de classe $c$ correctement classés ; $FP_c$ = autres exemples classés en $c$ à tort ; $FN_c$ = exemples de classe $c$ classés ailleurs.

10. Problème mis en évidence par la figure 1. L'erreur d'apprentissage continue à baisser, mais l'erreur de test baisse puis remonte à partir de ~250 epochs. C'est du sur-apprentissage (overfitting) : le réseau mémorise le train et perd en généralisation.

Exercice 4 — Recuit simulé : questions de cours (4 pts, CM6)

1. Méta-heuristique (avec exemple du recuit simulé). Une méta-heuristique est une stratégie générale de recherche stochastique pour résoudre des problèmes d'optimisation difficiles (combinatoires, non convexes), qui ne dépend pas du problème particulier et ne garantit pas l'optimum global mais fournit de bonnes solutions en temps raisonnable. Le recuit simulé en est un exemple historique (Kirkpatrick, Gelatt & Vecchi 1983 ; Černý 1985), première méta-heuristique inspirée d'un phénomène physique (le recuit en métallurgie : on chauffe puis on refroidit lentement un matériau pour atteindre un état de basse énergie / cristal régulier).

2. Vocabulaire du recuit simulé.

3. Utilité de l'exploitation ET de l'exploration.

• Exploration = accepter des solutions dégradantes (surtout à haute $T$) → permet d'échapper aux minima locaux.
• Exploitation = accepter quasi exclusivement les améliorations (à basse $T$) → permet de converger finement vers un minimum.

Le recuit combine les deux dans le temps via le refroidissement : on explore beaucoup au début, on exploite ensuite.

4. Rôle du critère de Metropolis. Décider d'accepter ou non un voisin $X'$ généré par la perturbation. Concrètement, avec $\Delta f = f(X') - f(X)$ :

Le critère permet d'accepter probabilistiquement des solutions dégradantes (donc d'explorer) tout en favorisant les améliorations. Plus $T$ baisse, plus le critère devient sélectif.

5. Conséquences du choix de $T_{init}$ et $T_{min}$.

Heuristique : choisir $T_{init}$ tel qu'un voisinage typiquement dégradant soit accepté avec proba élevée (≈ 0,8), et $T_{min}$ tel que l'on n'accepte presque plus que les améliorations.

iii. Notions ré-activées

Les concepts du cours mobilisés pour cet examen.