Algorithme EM appliqué au mélange de 2 gaussiennes 1.

Modélisation : Choisir un modèle probabiliste approprié (ex: mélange de gaussiennes)

2. Inférence : Estimer les paramètres du modèle à partir des données
Algorithme
3. Affectation : Assigner chaque point de données au cluster le plus probable
Initialisation de l’algorithme
4. Itérations : Répéter le processus jusqu’à convergence
• Fixer les paramètres π1 et π2 tels que π1 + π2 = 1.
• Fixer les paramètres µ1 , Σ1 et µ2 , Σ2 .
• On peut utiliser l’algorithme K-means pour initialiser les clusters.
Répéter
Étape E (Expectation) : Calcul des probabilités a posteriori

π1 N (xi ; µ1 , Σ1 )
γi = ,
π1 N (xi ; µ1 , Σ1 ) + π2 N (xi ; µ2 , Σ2 )

Rmq : γi = Pr(zi = 1|xi ), Pr(zi = 0|xi ) = 1 − γi , i = 1, . . . , N,

où γi est la probabilité a posteriori que xi ∈ C1 .
Étape M (Maximisation) : Calcul des paramètres
PN (j) PN
γ i xi
(j)
γi Figure 1: Illustration de l’algorithme EM pour un mélange de gaussiennes
µj = Pi=1
N (j)
, πj = i=1
, j ∈ {1, 2},
N
i=1 γi

PN
i=1
(j)
γi (xi − µj )(xi − µj )⊤ Démonstration : diminution de l’erreur pour η petit
Σj = PN (j) , j ∈ {1, 2}.
i=1 γi
Considérons une fonction d’énergie E(θ) différentiable. À chaque étape, les paramètres sont mis
Jusqu’à convergence à jour selon :
θ(t+1) = θ(t) − η∇θ E(θ(t) ).
Algorithm 1 K-means séquentiel
Pour un η suffisamment petit, utilisons une approximation de Taylor au premier ordre autour
Require: Ensemble de données {x1 , x2 , . . . , xN }, nombre de clusters K de θ(t) :
Ensure: Centres des clusters {µ1 , µ2 , . . . , µK }, affectations {c1 , c2 , . . . , cN } E(θ(t+1) ) ≈ E(θ(t) ) + ∇θ E(θ(t) )⊤ (θ(t+1) − θ(t) ).
1: Initialisation : Choisir aléatoirement K centres initiaux {µ1 , µ2 , . . . , µK }
(0) (0) (0)

2: t ← 0
En substituant θ(t+1) − θ(t) = −η∇θ E(θ(t) ), on obtient :
3: repeat
E(θ(t+1) ) ≈ E(θ(t) ) − η∥∇θ E(θ(t) )∥2 .
4: Étape d’affectation :
5: for i = 1 to N do Puisque ∥∇θ E(θ(t) )∥2 ≥ 0, pour η > 0 suffisamment petit, E(θ(t+1) ) < E(θ(t) ), ce qui montre
(t)
6: ci ← arg mink∈{1,...,K} ∥xi − µk ∥2 que l’erreur diminue à chaque étape.
7: end for
8: Étape de mise à jour :
9: for k = 1 to K do
(t+1) P Questions sur la régression logistique
10: µk ← |C1k | i∈Ck xi
11: où Ck = {i : ci = k} 1. Expression de la fonction sigmoid :
12: end for
La fonction sigmoid est définie par :
13: t←t+1
14: until convergence (les centres ne changent plus ou changement ¡ seuil) 1
σ(z) =
15: return {µ1 , µ2 , . . . , µK }, {c1 , c2 , . . . , cN }
(t) (t) (t)
1 + e−z

2. Dérivée de la fonction sigmoid :

La dérivée de σ(z) est :
Principe de clustering par modélisation statistique σ ′ (z) = σ(z)(1 − σ(z))

Démonstration :
Le clustering par modélisation statistique vise à regrouper des données en clusters en supposant
que celles-ci sont générées par un modèle probabiliste, généralement un mélange de distribu- σ(z) = (1 + e−z )−1 (1)
tions (comme un mélange de gaussiennes). L’objectif est d’identifier les paramètres du modèle
qui décrivent au mieux la structure des données. e−z
σ ′ (z) = −(1 + e−z )−2 · (−e−z ) = (2)
Le principe repose sur les étapes suivantes : (1 + e−z )2

1 2

Puisque 1
1+e−z = σ(z) et e−z
1+e−z = 1 − σ(z), on a : Exercice 3: Mesure de qualité d’un classificateur (8 points)
e−z
σ ′ (z) = σ(z) · = σ(z)(1 − σ(z)) Supposons que nous classions les phrases en deux classes, sentiment et sans-sentiment, et obtenons
1 + e−z le tableau de contingence (la matrice de confusion) suivante :
3. Fonctionnement de la régression logistique :
Classe prédite
La régression logistique prédit la probabilité qu’une instance appartienne à une classe pos-
sentiment sans-sentiment
itive (1) par rapport à une classe négative (0). Pour une instance x ∈ Rd , le modèle calcule
sentiment 50 150
:
sans-sentiment 50 750
p(y = 1|x) = σ(wT x + b),
où w ∈ Rd est le vecteur de poids et b ∈ R est le biais. La classe prédite est : Table 1: Matrice de confusion
(
1 si σ(wT x + b) ≥ 0.5
ŷ =
0 sinon
Question 1 : Rappel, précision et mesure-F pour la classe sentiment
4. Entraı̂nement avec MLE : Pour la classe sentiment :
La Maximum Likelihood Estimation (MLE) maximise la vraisemblance des données ob-
servées. Pour un ensemble de données {(xi , yi )}ni=1 , où yi ∈ {0, 1}, la vraisemblance est • Vrais positifs (TP) : 50 (prédits comme sentiment et effectivement sentiment).
: • Faux négatifs (FN) : 150 (prédits comme sans-sentiment mais réellement sentiment).
n
Y n
Y
L(w, b) = p(yi |xi ) = [σ(wT xi + b)]yi [1 − σ(wT xi + b)]1−yi
i=1 i=1
• Faux positifs (FP) : 50 (prédits comme sentiment mais réellement sans-sentiment).

On maximise le log-vraisemblance : Les formules sont :

n
X TP
  • Rappel = TP+FN
ℓ(w, b) = yi log σ(wT xi + b) + (1 − yi ) log(1 − σ(wT xi + b))
TP
i=1
• Précision = TP+FP
Cela équivaut à minimiser l’erreur de cross-entropie binaire : Précision·Rappel
• Mesure-F = 2 · Précision+Rappel
E(w, b) = −ℓ(w, b)
Calculs :
On utilise la descente de gradient pour optimiser :
n • Rappel = 50
= 50
= 0.25
X 50+150 200
w ←w−η (σ(wT xi + b) − yi )xi (3)
i=1
• Précision = 50
50+50 = 50
100 = 0.5
n
X
b←b−η (σ(wT xi + b) − yi ) (4) • Mesure-F = 2 · 0.5·0.25
0.5+0.25 =2· 0.125
0.75 =2· 1
6 = 2
6 = 1
3 ≈ 0.333
i=1

5. Entraı̂nement avec MAP : Question 2 : Rappel, précision et mesure-F pour la classe sans-sentiment
La Maximum a Posteriori (MAP) estimation incorpore une distribution a priori sur les Pour la classe sans-sentiment :
paramètres, souvent une gaussienne N (0, σ 2 I) pour régularisation. La fonction à max-
imiser est : • Vrais positifs (TP) : 750 (prédits comme sans-sentiment et effectivement sans-sentiment).
log p(w, b|data) ∝ ℓ(w, b) + log p(w, b) • Faux négatifs (FN) : 50 (prédits comme sentiment mais réellement sans-sentiment).
Pour une priori gaussienne sur w (et b constant), on a :
• Faux positifs (FP) : 150 (prédits comme sans-sentiment mais réellement sentiment).
1
log p(w) = − 2 ∥w∥2 + constante Calculs :
2σ
La fonction objectif devient : • Rappel = 750
750+50 = 750
800 = 0.9375
1 • Précision = 750 750 5
≈ 0.8333
EM AP (w, b) = −ℓ(w, b) + ∥w∥2 750+150 = 900 = 6
2σ 2
Cela correspond à une régression logistique avec régularisation L2. La mise à jour par • Mesure-F = 2 · 0.8333·0.9375
0.8333+0.9375 =2· 0.7812375
1.7708 ≈ 2 · 0.4412 ≈ 0.8824
descente de gradient est :
" n #
X w
w ←w−η (σ(wT xi + b) − yi )xi + 2 (5)
i=1
σ
n
X
b←b−η (σ(wT xi + b) − yi ) (6)
i=1

3 4
 Problème 1 (MLP Linéaire) Question 5 : En utilisant la norme L2, quelle est la distance entre les deux points suivants en quatre di-
mensions : (4, 7, 1, 10)p
et (8, 3, 3, 5) ? p
Dans cet exercice, nous considérons un perceptron multicouche linéaire (MLP), comme ceux Calcul : Distance L2√ = (8 − 4)2 + (3 − 7)2 + (3 − 1)2 + (5 − 10)2 = 42 + (−4)2 + 22 + (−5)2 =
√
illustrés ci-dessous (MLP1 et MLP2). Un MLP dont chaque unité a une fonction d’activation 16 + 16 + 4 + 25 = 61 ≈ 7.81.
linéaire, telle que l’identité g : R → R, g(x) = x. Pour un vecteur x ∈ R2 , x = (x1 , x2 )T , et l’identité
comme fonction d’activation, la sortie du MLP1, o′ , est donnée par : Question 6 : En utilisant la norme L1, quelle est la distance entre les deux points suivants en quatre
dimensions : (4, 7, 1, 10) et (8, 3, 3, 5) ?
o ′ = w T x = w 1 x1 + w 2 x2 , Calcul : Distance L1 = |8 − 4| + |3 − 7| + |3 − 1| + |5 − 10| = 4 + 4 + 2 + 5 = 15.

où w = (w1 , w2 )T sont les poids. Les figures suivantes illustrent les architectures MLP1 et Question 7 : Réponse : Exemple : (0, 0) et (1, 0)
MLP2. Calcul :
• Distance L1 : |1 − 0| + |0 − 0| = 1
p √
Question 1 : Preuve que pour tout a, b, c, d, e, f ∈ R dans MLP2, il existe tou- • Distance L2 : (1 − 0)2 + (0 − 0)2 = 1 = 1
jours w1 , w2 ∈ R dans MLP1 tels que les deux sorties, o′ et o′′ , sont identiques.
Analysons la sortie de MLP2. La couche cachée produit h1 = ax1 + bx2 et h2 = cx1 + dx2 . La sortie
o′′ est alors donnée par : h1 = a × x1 + c × x2 h2 = b × x1 + d × x2 o00 = e × h1 + f × h2 Classification avec l’algorithme k-NN
o′′ = eh1 + f h2 = e(ax1 + bx2 ) + f (cx1 + dx2 ) = (ea + f c)x1 + (eb + f d)x2 . Nous devons classer la nouvelle instance q = (high, no, no, no) en utilisant l’algorithme des
k plus proches voisins avec k = 1, 2, 3. La base de cas contient sept cas avec leurs symptômes
Comparons cela avec la sortie de MLP1 : o′ = w1 x1 + w2 x2 . Pour que o′ = o′′ , il suffit de choisir
(Fièvre, Vomissements, Diarrhée, Frissons) et classifications. Les similarités entre q et les
:
cas d’entraı̂nement sont calculées à l’aide de la matrice de similarité fournie par un expert,
pondérée par les poids wF = 0.3, wV = 0.2, wD = 0.2, wSh = 0.3.
w1 = ea + f c,
w2 = eb + f d.
Calcul de la similarité pondérée
Puisque a, b, c, d, e, f ∈ R, les valeurs w1 et w2 sont toujours définies dans R. Ainsi, pour tout
a, b, c, d, e, f , il existe w1 , w2 tels que les sorties sont identiques. La similarité totale entre q et chaque cas ci est calculée comme : Sim(q, ci ) = wF ·sim(qF , ciF )+
wV · sim(qV , ciV ) + wD · sim(qD , ciD ) + wS · sim(qS , ciS ),
Question 2 : Considérons un vecteur x = (x1 , x2 ) où x1 , x2 ∈ {0, 1}. Prouver
Sim(q, ci ) = 0.3 · sim(qF , ciF ) + 0.2 · sim(qV , ciV ) + 0.2 · sim(qD , ciD ) + 0.3 · sim(qS , ciS ),
qu’un MLP linéaire ne peut pas apprendre la fonction XOR.
Définissons la fonction XOR : XOR[x1 , x2 ] = 1 si x1 ̸= x2 et 0 sinon. Les valeurs possibles sont : - où q = (high, no, no, no).
(x1 , x2 ) = (0, 0) → 0, - (x1 , x2 ) = (0, 1) → 1, - (x1 , x2 ) = (1, 0) → 1, - (x1 , x2 ) = (1, 1) → 0.
• c1 = (no, no, no, no):
La sortie d’un MLP linéaire est o′ = w1 x1 + w2 x2 . Puisque x1 , x2 ∈ {0, 1}, calculons les sorties :
Sim(q, c1 ) = 0.3 · 0.0 + 0.2 · 1.0 + 0.2 · 1.0 + 0.3 · 1.0 = 0.0 + 0.2 + 0.2 + 0.3 = 0.70
- (0, 0) → 0, - (0, 1) → w2 , - (1, 0) → w1 , - (1, 1) → w1 + w2 .
Pour apprendre XOR, les sorties doivent être : - (0, 0) → 0, - (0, 1) → 1, - (1, 0) → 1, - (1, 1) → 0. • c2 = (average, no, no, yes):
Cela implique w2 = 1 et w1 = 1, mais alors w1 + w2 = 2 ̸= 0, ce qui contredit (1, 1) → 0. De plus, Sim(q, c2 ) = 0.3 · 0.3 + 0.2 · 1.0 + 0.2 · 1.0 + 0.3 · 0.0 = 0.09 + 0.2 + 0.2 + 0.0 = 0.79
une fonction linéaire w1 x1 + w2 x2 ne peut pas représenter une fonction non linéaire comme XOR, • c3 = (high, no, no, yes):
qui nécessite une séparation non linéaire. Ainsi, un MLP linéaire ne peut pas apprendre XOR. Sim(q, c3 ) = 0.3 · 1.0 + 0.2 · 1.0 + 0.2 · 1.0 + 0.3 · 0.0 = 0.3 + 0.2 + 0.2 + 0.0 = 0.76
Question 1 : Quelle est la précision d’entraı̂nement (c’est-à-dire la précision sur les données d’entraı̂nement) • c4 = (high, yes, yes, no):
d’un classificateur des k plus proches voisins lorsque k = 1 ? Sim(q, c4 ) = 0.3 · 1.0 + 0.2 · 0.0 + 0.2 · 0.0 + 0.3 · 1.0 = 0.3 + 0.0 + 0.0 + 0.3 = 0.68
Réponse : Précision d’entraı̂nement : 100 % • c5 = (average, no, yes, no):
Sim(q, c5 ) = 0.3 · 0.3 + 0.2 · 1.0 + 0.2 · 0.0 + 0.3 · 1.0 = 0.09 + 0.2 + 0.0 + 0.3 = 0.63
Question 2 : Supposons qu’en utilisant un classificateur des k plus proches voisins sur n exemples d’entraı̂nement, • c6 = (no, yes, yes, no):
vous définissez k égal à n. Qu’est-ce qui sera vrai concernant les prédictions du classifica- Sim(q, c6 ) = 0.3 · 0.0 + 0.2 · 0.0 + 0.2 · 0.0 + 0.3 · 1.0 = 0.0 + 0.0 + 0.0 + 0.3 = 0.28
teur sur les données de test ? • c7 = (average, yes, yes, no):
Réponse : Prédictions constantes égales à la classe majoritaire de l’ensemble d’entraı̂nement Sim(q, c7 ) = 0.3 · 0.3 + 0.2 · 0.0 + 0.2 · 0.0 + 0.3 · 1.0 = 0.09 + 0.0 + 0.0 + 0.3 = 0.47

Question 3 : Réponse : Temps attendu : 2N secondes Classifications

Question 4 : Réponse : Temps attendu : N secondes - k = 1 : Le voisin le plus proche est c2 (sim = 0.79), classification : influenza (I). - k = 2 : Les
deux voisins les plus proches sont c2 (0.79, I) et c3 (0.76, I), votes : 2 pour influenza (I). - k = 3
: Les trois voisins les plus proches sont c2 (0.79, I), c3 (0.76, I), et c1 (0.70, H), votes : 2 pour
influenza (I), 1 pour healthy (H).

5 6

Réponses finales
• k = 1 : influenza (I)
• k = 2 : influenza (I)
• k = 3 : influenza (I)

Exercice 3 : Réponses

Contexte
Considérons un perceptron multicouche (MLP) de base avec deux entrées x1 , x2 , une sortie
unique y, et une couche cachée avec n unités hi . L’espace d’hypothèse H = {g : R2 → R |
Algorithme 2 : Algorithme des k plus proches voisins
Pn
g(x1 , x2 ; W ) = i=1 wi hi , où hi = σ(wi1 x1 + wi2 x2 )}. La sortie est y = g(x1 , x2 ; W ), où W
(2) (1) (1)

dénote l’ensemble des poids. Entrées :

- Ensemble d’entraı̂nement : xtrain = (xtrain,1 , . . . , xtrain,n ), i = 1 à m, où m est le nombre

(i) (i) (i)

a) Unité Linéaire (ReLU) où σ = max(0, x) d’exemples d’entraı̂nement. - Nouvel exemple de test : xtest = (xtest,1 , . . . , xtest,n ). - Paramètre
k (nombre de voisins).
Montrons qu’il existe avec n unités cachées au plus n + 2 points de transition internes, et
que l’on peut représenter exactement une fonction f (x) qui est linéaire par morceaux avec
k points de transition internes. Algorithme :
- Pour une unité ReLU hi = max(0, wi1 x1 + wi2 x2 ), la transition se produit lorsque wi1 x1 +
(1) (1) (1)
Pn Pour i = 1 à m faire
wi2 x2 = 0. Avec n unités, il y a au plus n hyperplans de transition. - La sortie y = i=1 wi hi
(1) (2)

peut changer à chaque intersection de ces hyperplans avec l’axe x, ajoutant potentiellement
• Calculer la distance euclidienne di entre xtest et xtrain :
(i)
2 points aux extrémités de l’intervalle [0, 1]. Ainsi, avec n unités, il y a au plus n + 2 points de
transition. - Pour f (x) = 2x sur [0, 1], avec k = 1 point de transition (par exemple à x = 1/2 v
uX
u n
si on ajuste les poids), on peut choisir w11 = 2, w12 = 0, h1 = max(0, 2x), et w1 = 1, donnant
(1) (1) (2) (i)
di = t (xtest,j − xtrain,j )2
y = 2x pour x ≥ 0. Avec n = 1, cela fonctionne avec 1 point de transition interne. j=1

b) Approximation par descente de gradient • Stocker di avec l’indice i. fin

Trier les distances di par ordre croissant pour obtenir d1 ≤ d2 ≤ · · · ≤ dm .
Considérons l’approximation d’une fonction générale Pmf (x) sur [0, 1] en utilisant une de- Sélectionner les k premières distances pour former l’ensemble des indices des k plus
scente de gradient pour minimiser la perte L(q) = i=1 (f (zi ) − g(zi ; w))2 , où zi ∈ [0, 1] et proches voisins Idxvoisins = {i1 , i2 , . . . , ik }, où di1 ≤ di2 ≤ · · · ≤ dik .
q = (zi , g(zi )) sont les points de données. État pour la MLP avec n = 1 et m = 1. Extraire les classes correspondantes : ytrain
j (i )
pour j = 1 à k.
- La perte est L(w) = (f (z1 ) − g(z1 ; w))2 . - Pour n = 1, g(z1 ; w) = w1 max(0, w11 z1 + w12 ). -
(2) (1) (1)
Calculer la classe majoritaire :
Le gradient ∂w dépend de ∂w . Pour w11 z1 + w12 > 0, ∂g(1) = w1 z1 , et la mise à jour est
∂L ∂g (1) (1) (2)
∂w11 k
X (i )
∂L
w ← w − α ∂w . - Graphe : ”Forward pass” calcule g(z1 ; w), ”backward pass” ajuste w via le ytest = arg max I(ytrain
j
= c)
c
gradient. j=1

où I est la fonction indicatrice.

c) Techniques pour éviter les minima locaux et le surapprentissage

- Pour éviter les minima locaux, utiliser une initialisation aléatoire des poids, un taux d’apprentissage Sortie :
adaptatif (ex. Adam), ou une recherche multi-départ. - Pour le surapprentissage, appliquer
la régularisation (L2), la validation croisée, ou réduire n pour limiter la complexité. Retourner la classe prédite ytest pour xtest .

Algorithme 2 : Algorithme des k plus proches voisins

Entrées
- Ensemble d’entraı̂nement : xtrain = (xtrain,1 , . . . , xtrain,n ), i = 1 à m, où m est le nombre
(i) (i) (i)

d’exemples d’entraı̂nement. - Nouvel exemple de test : xtest = (xtest,1 , . . . , xtest,n ). - Paramètre

k (nombre de voisins).

7 8