Examen IA — GSI FI

i. Le sujet

Sujet officiel de la session principale du 10/04/2025 — ING2 GSI FI.

ii. Correction commentée

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

Exercice 1 — Questions de cours et de réflexion (CM4)

Différences clés :

• vs supervisé : pas d'étiquette directe « bonne action ». Le seul signal est la récompense $r$, souvent retardée.
• vs non supervisé : on a un signal de retour (la récompense), il y a un objectif explicite à maximiser.

Dans le Q-learning : on utilise la stratégie $\varepsilon$-greedy. À chaque étape :

• avec proba $\varepsilon$ → action aléatoire (exploration) ;
• avec proba $1 - \varepsilon$ → action $\arg\max_a Q(s,a)$ (exploitation).

Dans le recuit simulé : la dichotomie est portée par le critère de Metropolis couplé à la température $T$. À haute $T$, on accepte volontiers les voisins dégradants ($\Delta f > 0$) avec proba $\exp(-\Delta f / T)$ → exploration. À basse $T$, on n'accepte presque plus que les améliorations → exploitation.

Exercice 2 — Deep Learning : analyse de code Keras (CM1, CM2)

1. Caractéristiques des images. input_shape=(32,32,3) ⇒ images 32 × 32 pixels, à 3 canaux (RGB, niveau de couleur).

2. Nombre de classes. La dernière couche est Dense(5, softmax) → 5 classes. Le softmax produit un vecteur de probabilités de dimension 5.

3. Couche de convolution Conv2D(32, (3,3)).

• (a) Rôle : appliquer un ensemble de filtres (templates) qui glissent sur l'image pour détecter des motifs locaux (bords, coins, textures…). Chaque filtre produit une carte d'activation (feature map).
• (b) Taille / hyperparamètres : 32 filtres de taille $3 \times 3$. Sortie spatiale (sans padding ni stride) : $(32-3+1) \times (32-3+1) = 30 \times 30$, sur 32 canaux ⇒ tenseur $30 \times 30 \times 32$.
• (c) Nombre de paramètres : chaque filtre a $3 \times 3 \times 3 = 27$ poids (3 canaux d'entrée) + 1 biais = 28. Avec 32 filtres : $$\text{params} = 32 \times (3 \times 3 \times 3 + 1) = 32 \times 28 = \mathbf{896}.$$

4. Couche de pooling. MaxPooling2D(pool_size=(2,2)). Rôle : résumer / sous-échantillonner la feature map en regroupant les neurones par carré $2 \times 2$ et en prenant le maximum. Effet : réduire la dimension spatiale, gagner en robustesse aux translations. Taille de sortie : $15 \times 15 \times 32$. Aucun paramètre à apprendre (juste l'hyperparamètre $p = 2$).

5. Couches Dropout. Rôle : pendant l'entraînement, mettre à zéro chaque neurone de la couche précédente avec probabilité $p$. Effet : régulariser le réseau (anti sur-apprentissage), forcer une redondance entre neurones.

• Dropout(0.3) après le MaxPool : $p = 0{,}3$ ⇒ 30 % des neurones désactivés à chaque mini-batch. Taille inchangée ($15 \times 15 \times 32$). Aucun paramètre appris.
• Dropout(0.5) après le Dense(128) : $p = 0{,}5$. Taille inchangée (128). Aucun paramètre appris.

6. loss=keras.losses.categorical_crossentropy. C'est la fonction de perte entropie croisée catégorielle, utilisée pour la classification multi-classes avec sortie softmax et étiquettes one-hot. $$\mathcal{L}_{CCE} = -\sum_{k=1}^{C} y_k \log(\hat{y}_k)$$ où $y_k$ est l'étiquette one-hot (1 pour la vraie classe, 0 sinon) et $\hat{y}_k$ la probabilité prédite par le softmax pour la classe $k$. Minimisée quand $\hat y$ s'aligne avec $y$.

8. Évaluation du réseau.

• (a) La métrique est 'accuracy' = taux de bonnes prédictions : $$\text{accuracy} = \frac{\text{nombre de prédictions correctes}}{\text{nombre total d'exemples}}.$$ Elle mesure la performance globale du classifieur.
• (b) Pour évaluer chaque classe individuellement, on calcule la précision et le rappel par classe (à partir de la matrice de confusion). Pour la classe $c$ : $$\text{précision}_c = \frac{TP_c}{TP_c + FP_c}, \quad \text{rappel}_c = \frac{TP_c}{TP_c + FN_c}.$$ Le F1-score $= 2 \cdot \frac{P \cdot R}{P + R}$ combine les deux. Ces métriques par classe révèlent un éventuel déséquilibre (classe sous-représentée mal classée).

Exercice 3 — Recuit simulé pour la coloration de graphe (CM6)

On cherche à colorier les sommets d'un graphe non orienté $G = (V, E)$ de sorte que deux sommets adjacents aient des couleurs différentes, en minimisant le nombre total de couleurs.

1. Principe et utilité du recuit simulé. Méta-heuristique inspirée du recuit en métallurgie. On part d'une solution $X$ et d'une température $T$ élevée ; à chaque pas on tire un voisin $X'$ et on l'accepte selon le critère de Metropolis : $$P(\text{accept}) = \begin{cases} 1 & \text{si } \Delta f \le 0 \\ \exp(-\Delta f / T) & \text{si } \Delta f > 0 \end{cases}$$ puis on refroidit $T$ (typiquement géométriquement, $T_{k+1} = \alpha T_k$ avec $\alpha \approx 0{,}99$). Utilité : explorer un grand espace combinatoire en échappant aux minima locaux grâce à l'acceptation probabiliste de solutions dégradantes (surtout à haute $T$).

2. Représentation d'une solution. Si $|V| = n$, une solution est un vecteur $c = (c_1, c_2, \dots, c_n) \in \{1, 2, \dots, n\}^n$ où $c_i$ est la couleur attribuée au sommet $v_i$. (Borne sup. de couleurs = $n$, atteinte si tous les sommets sont différents.)

3. Fonction coût (énergie) à minimiser. Il faut pénaliser à la fois les conflits (arête monochrome) et le nombre de couleurs utilisées. Proposition : $$f(c) = |\{(u,v) \in E \mid c_u = c_v\}| \cdot W + |\{c_1, \dots, c_n\}|$$ avec $W$ un poids grand devant le nombre de couleurs (par ex. $W = |E| + 1$) afin que toute solution non valide coûte plus cher que n'importe quelle solution valide. L'optimum global $f^* $ est une coloration valide minimale.

4. Fonction de perturbation (voisinage). Plusieurs choix simples :

• Choisir un sommet $v_i$ au hasard et remplacer $c_i$ par une nouvelle couleur (au hasard parmi $\{1, \dots, K\}$ où $K$ = nb de couleurs courantes, ou $K+1$ pour autoriser l'ajout d'une couleur).
• Variante : choisir un sommet impliqué dans un conflit et lui attribuer une couleur qui ne crée pas de conflit avec ses voisins.

5. Probabilité d'acceptation d'une solution dégradante. C'est exactement le critère de Metropolis du cours : $$\boxed{P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)} \quad \text{lorsque } \Delta f = f(X') - f(X) > 0.$$ Quand $\Delta f \le 0$ on accepte d'office. Plus $T$ est grand, plus on accepte ; plus $\Delta f$ est grand, moins on accepte.

Exercice 4 — CFG et ambiguïté syntaxique (CM5)

Phrase analysée : « Le chat voit le poisson avec un jardin. »

1. Vérification CFG + symboles. Une grammaire est hors-contexte (CFG) ssi toute règle a un unique non-terminal en partie gauche. Toutes les règles fournies ($S \to NP\ VP$, $NP \to Det\ N$, …) sont de cette forme ⇒ la grammaire est bien une CFG.

2. Deux arbres syntaxiques différents. L'ambiguïté vient du groupe prépositionnel « avec une loupe » qui peut s'attacher soit au verbe voit (instrument), soit au nom poisson (modificateur du NP).

S
├── NP
│   ├── Det "le"
│   └── N   "chat"
└── VP                         (VP → VP PP)
    ├── VP                     (VP → V NP)
    │   ├── V  "voit"
    │   └── NP
    │       ├── Det "le"
    │       └── N   "poisson"
    └── PP                     (PP → P NP)
        ├── P  "avec"
        └── NP
            ├── Det "une"
            └── N   "loupe"

S
├── NP
│   ├── Det "le"
│   └── N   "chat"
└── VP                         (VP → V NP)
    ├── V  "voit"
    └── NP                     (NP → NP PP)
        ├── NP                 (NP → Det N)
        │   ├── Det "le"
        │   └── N   "poisson"
        └── PP                 (PP → P NP)
            ├── P  "avec"
            └── NP
                ├── Det "une"
                └── N   "loupe"

3. Origine de l'ambiguïté. Elle est syntaxique (et plus précisément structurelle, dite PP-attachment). La grammaire fournit deux dérivations valides du même mot grâce aux deux règles :

• $VP \to VP\ PP$ (le PP modifie le verbe)
• $NP \to NP\ PP$ (le PP modifie le nom)

Aucune contrainte syntaxique ne tranche, donc la phrase admet deux arbres. La désambiguïsation nécessite des indices sémantiques (un chat est plausiblement l'utilisateur d'une loupe ; un poisson l'est moins) ou pragmatiques, qui ne sont pas dans la CFG. On pourrait lever l'ambiguïté en enrichissant la grammaire (PCFG, contraintes sémantiques, lexicalisation).

iii. Notions ré-activées

Les concepts du cours mobilisés pour cet examen.