TP6b: Régression linéaire & logistique, Analyse discriminante linéaire & quadratique

TP à rendre :

Link

Questions théoriques :

On propose un autre modèle de classification dit génératif. On modélise les données de chaque classe comme un nuage Gaussien de distribution $𝒩(µ_1, Σ)$ pour la classe $1$ (i.e., $Y = 1$) et $𝒩(µ_0, Σ)$ pour la classe $0$ (i.e., $Y = 0$), où la matrice de covariance $Σ$ est supposée la même pour les deux classes.

On pose aussi $π_1 = ℙ(Y = 1)$, la probabilité pour un exemple d’avoir le label $1$. Ce modèle s’appelle le modèle de l’analyse discriminante linéaire (LDA en anglais).

NB: Comme $π$ apparaît dans l’expression des Gaussiennes, j’ai changé l’énoncé et ai posé \(π_1 ≝ ℙ(Y = 1)\)

\[\newcommand{\e}{\mathop{\rm e}\nolimits} \newcommand{\Tr}{\mathop{\rm Tr}\nolimits} \newcommand{\GL}{\mathop{\rm GL}\nolimits} \newcommand{\Ker}{\mathop{\rm Ker}\nolimits} \newcommand{\I}{\mathop{\rm I}\nolimits} \newcommand{\Nor}{\mathop{\rm Nor}\nolimits} \newcommand{\Cen}{\mathop{\rm C}\nolimits} \newcommand{\Gr}{\mathop{\rm Gr}\nolimits} \newcommand{\ll}{\left[\!\!\left[} \newcommand{\rr}{\right]\!\!\right]}\]

4.

a) Quel est le modèle conditionnel de $ℙ(Y |X = x)$ induit par ce modèle génératif ?

Pour tout $k∈ {0, 1}$, par la règle de Bayes :

\[\begin{align} P(Y=k \mid X=x) &= \frac{P(Y=k) \,P(X=x \mid Y=k)}{P(X=x)} \\ &= \frac{P(Y=k) \, P(X=x \mid Y=k)}{\displaystyle\sum_{i=0}^1 P(Y=i)\, P(X=x \mid Y=i)} \\ &= \frac{1}{1 + \displaystyle\frac{P(Y = 1-k)\, P(X=x \mid Y = 1-k)}{P(Y = k)\, P(X=x \mid Y = k)}} \\ &= \frac{1}{1 + \exp\left(-\ln\left(\displaystyle\frac{P(Y = k)\, P(X=x \mid Y = k)}{P(Y = 1-k)\, P(X=x \mid Y = 1-k)}\right)\right)} \end{align}\]

où

\[\begin{align} \ln\left(\displaystyle\frac{P(Y = k)\, P(X=x \mid Y = k)}{P(Y = 1-k)\, P(X=x \mid Y = 1-k)}\right) &= \ln\left(\displaystyle\frac{P(Y = k)}{P(Y = 1-k)}\right) + \ln\left(\frac{ \frac{1}{2π \sqrt{\det Σ}} \,\exp \left(- \frac 1 2 (x - μ_k)^T Σ^{-1} (x - μ_k) \right) }{ \frac{1}{2π \sqrt{\det Σ}} \,\exp \left(- \frac 1 2 (x - μ_{1-k})^T Σ^{-1} (x - μ_{1-k}) \right) }\right)\\ &= \ln\left(\displaystyle\frac{π_1^k (1-π_1)^{1-k}}{π_1^{1-k} (1-π_1)^k}\right) + \ln\left(\exp \left(-\frac 1 2 \Big((x - μ_k)^T Σ^{-1} (x - μ_k) - (x - μ_{1-k})^T Σ^{-1} (x - μ_{1-k})\Big) \right)\right) \\ &= \ln\left(\displaystyle\frac{π_1^k (1-π_1)^{1-k}}{π_1^{1-k} (1-π_1)^k}\right) -\frac 1 2 \Big( x^T Σ^{-1} x + μ_k^T Σ^{-1} μ_k \underbrace{- x^T Σ^{-1} μ_k - μ_k^T Σ^{-1} x}_{= \; - 2 x^T Σ^{-1} μ_k} - (x - μ_{1-k})^T Σ^{-1} (x - μ_{1-k})\Big) \\ &= \ln\left(\displaystyle\frac{π_1^k (1-π_1)^{1-k}}{π_1^{1-k} (1-π_1)^k}\right) -\frac 1 2 \Big(μ_k^T Σ^{-1} μ_k - μ_{1-k}^T Σ^{-1} μ_{1-k} - 2 x^T Σ^{-1} (μ_k - μ_{1-k}) \Big) \\ &= \underbrace{\ln\left(\displaystyle\frac{π_1^k (1-π_1)^{1-k}}{π_1^{1-k} (1-π_1)^k}\right) + \frac 1 2 \big(μ_{1-k}^T Σ^{-1} μ_{1-k} - μ_{k}^T Σ^{-1} μ_{k}\big)}_{≝ \; α_k} + x^T Σ^{-1} (μ_k - μ_{1-k}) \\ \end{align}\]

Donc

\[P(Y=k \mid X=x) = \frac{1}{1 + \e^{-\left(α_k + x^T Σ^{-1} (μ_k - μ_{1-k})\right)}}\]

avec \(α_k ≝ \ln\left(\displaystyle\frac{π_1^k (1-π_1)^{1-k}}{π_1^{1-k} (1-π_1)^k}\right) + \frac 1 2 \big(μ_{1-k}^T Σ^{-1} μ_{1-k} - μ_{k}^T Σ^{-1} μ_{k}\big)\)

b) Montrez qu’il correspond à un modèle probabiliste de classification linéaire de la même forme que la régression logistique.

En posant $\tilde{x} = \begin{pmatrix}x \ 1 \ \end{pmatrix}$, il vient, avec $k=1$, que

\[P(Y=1 \mid X=x) = \frac{1}{1 + \exp\Big(-\big(\underbrace{α_1 + x^T Σ^{-1} (μ_1 - μ_0)}_{≝ \; f(\tilde{x})}\big)\Big)} = σ(f(\tilde{x}))\]

où

• \[f(\tilde{x}) ≝ \tilde{x}^T \underbrace{\begin{pmatrix} Σ^{-1} (μ_1 - μ_0) \\ α_1 \\ \end{pmatrix}}_{≝ \; β}\]
• \[α_1 ≝ \ln\left(\displaystyle\frac{π_1}{1-π_1}\right) + \frac 1 2 \big(μ_0^T Σ^{-1} μ_0 - μ_1^T Σ^{-1} μ_1\big)\]

$P(Y=1 \mid X=x)$ s’écrit donc sous la forme $σ(f(\tilde{x}))$, où $f(\tilde{x}) ≝ \tilde{x}^T β$ : l’analyse discriminante linéaire et la régression logistique utilisent le même modèle de classification linéaire sous-jacent.

c) Appliquez le modèle aux données en utilisant le principe du maximum de vraisemblance pour apprendre les paramètres du modèle génératif.

On procède de manière analogue à ce qu’on a vu dans le cours:

Principe du maximum de vraisemblance

• $μ ≝ \begin{pmatrix} μ_0 \ μ_1 \end{pmatrix} ∈ ℝ^2$
• $Σ ∈ 𝒮_2(ℝ)$ est symmétrique définie positive

Dans la suite, on note

• $x_i ≝ \begin{pmatrix} x_i^{(1)} \ x_i^{(2)} \end{pmatrix}$ les points d’entrée
• $\vec{x} ≝ (x_1, \ldots, x_n)$
• $\vec{y} ≝ (y_1, \ldots, y_n)$

La log-vraissemblance s’écrit :

\[\begin{align*} - \ln L(\vec{x}, \vec{y}, μ, σ^2) &= -\sum\limits_{ i=1 }^n \ln \underbrace{P(X=x_i, Y=y_i)}_{=\; P(X=x_i \mid Y=y_i) P(Y=y_i)}\\ &= -\sum\limits_{ i=1 }^n \ln \Big(\big(π_1 P(X=x_i \mid Y=1)\big)^{y_i}\big((1-π_1) P(X=x_i \mid Y=0)\big)^{1-y_i}\Big)\\ & = \underbrace{- \sum\limits_{ i=1 }^n y_i \ln π_1 + (1-y_i) \ln(1-π_1) + y_i \ln\left(\frac{1}{2π \sqrt{\det Σ}} \exp \left(- \frac 1 2 (x_i - μ_1)^T Σ^{-1} (x_i - μ_1) \right)\right) + (1-y_i) \ln\left(\frac{1}{2π \sqrt{\det Σ}} \exp \left(- \frac 1 2 (x_i - μ_0)^T Σ^{-1} (x_i - μ_0) \right)\right)}_{≝ \; l(π_1, μ, Σ)} \\ \end{align*}\]

Estimation de $π_1$

Vue comme une fonction de la variable $π_1$ seulement, $l$ est convexe et s’écrit sous la forme :

\[-\sum\limits_{ i=1 }^n y_i \ln π_1 + (1-y_i) \ln(1-π_1) + cste\]

L’annulation de la dérivée par rapport à $π_1$ donne :

\[\begin{align*} & \sum\limits_{ i=1 }^n \frac{y_i}{π_1} - \frac{1-y_i}{1-π_1} = 0 \\ ⟺ \quad& π_1 = \frac{\sum\limits_{ i=1 }^n y_i}{\sum\limits_{ i=1 }^n y_i + (1-y_i)} \\ ⟺ \quad& π_1 = \frac 1 n \sum\limits_{ i=1 }^n y_i \end{align*}\]

$π_1$ est égal à la proportion de $x_i$ dont le label $y_i$ vaut $1$ (dans l’ensemble d’entraînement)

Estimation de $μ_1$

Vue comme une fonction de $μ_1$ seulement, $l$ est convexe et s’écrit sous la forme :

\[\sum\limits_{ i=1 }^n \frac{y_i}{2} (x_i - μ_1)^T Σ^{-1} (x_i - μ_1) + cste\]

L’annulation de la dérivée par rapport à $μ_1$ donne :

\[\begin{align*} & \sum\limits_{ i=1 }^n y_i Σ^{-1} (x_i - μ_1) = 0 \\ ⟺ \quad& μ_1 = \frac{\sum\limits_{ i=1 }^n y_i x_i}{\sum\limits_{ i=1 }^n y_i} \end{align*}\]

De même :

\[μ_0 = \frac{\sum\limits_{ i=1 }^n (1-y_i) x_i}{\sum\limits_{ i=1 }^n (1-y_i)}\]

$μ_1$ (resp. $μ_0$) est égal à la moyenne des $x_i$ dont le label $y_i$ vaut $1$ (resp. $0$) (dans l’ensemble d’entraînement).

Estimation de $Σ$

Vue comme une fonction de $Λ ≝ Σ^{-1}$ seulement, $l$ est convexe et s’écrit sous la forme :

\[\sum\limits_{ i=1 }^n -\frac{1}{2} \ln(\vert Λ \vert) + \frac{y_i}{2} \underbrace{\underbrace{(x_i - μ_1)^T}_{1 × 2} \underbrace{Λ}_{2 × 2} \underbrace{(x_i - μ_1)}_{2 × 1}}_{\Tr((x_i - μ_1)^T Λ (x_i - μ_1))} + \frac{1-y_i}{2} \underbrace{\underbrace{(x_i - μ_0)^T}_{1 × 2} \underbrace{Λ}_{2 × 2} \underbrace{(x_i - μ_0)}_{2 × 1}}_{=\, \Tr((x_i - μ_0)^T Λ (x_i - μ_0))} + cste\]

L’annulation de la dérivée par rapport à $Λ$ donne :

\[\begin{align*} & \sum\limits_{ i=1 }^n - Λ^{-1} + y_i(x_i - μ_1) (x_i - μ_1)^T + (1-y_i)(x_i - μ_0) (x_i - μ_0)^T = 0 \\ ⟺ \quad& Σ = Λ^{-1} = \frac 1 n \sum\limits_{ i=1 }^n y_i(x_i - μ_1) (x_i - μ_1)^T + (1-y_i)(x_i - μ_0) (x_i - μ_0)^T \end{align*}\]

---

Frontière de classification

On prédit $y=1$ si, et seulement si :

\[\begin{align*} & P(X=x, Y=1) ≥ P(X=x, Y=0) \\ ⟺ \quad& \frac{P(X=x, Y=1)}{P(X=x, Y=0)} ≥ 1 \\ ⟺ \quad& \ln \left(\frac{P(X=x, Y=1)}{P(X=x, Y=0)}\right) ≥ 0 \\ ⟺ \quad& \ln \left(\frac{P(X=x \mid Y=1) P(Y=1)}{P(X=x \mid Y=0) P(Y=0)}\right) ≥ 0 \\ ⟺ \quad& \underbrace{\ln\left(\displaystyle\frac{π_1}{1-π_1}\right) + \frac 1 2 \big(μ_0^T Σ^{-1} μ_0 - μ_1^T Σ^{-1} μ_1\big)}_{≝ \; α_1} + x^T Σ^{-1} (μ_1 - μ_0) ≥ 0 &&\text{(cf. question précédente)}\\ ⟺ \quad& \tilde{x}^T \underbrace{\begin{pmatrix} Σ^{-1} (μ_1 - μ_0) \\ α_1 \\ \end{pmatrix}}_{≝ \; β} ≥ 0 &&\text{(avec les notations de la question précédente)} \end{align*}\]

d) Analyse discriminante quadratique

Si on autorise les matrices de covariances à être différentes pour les deux classes (on les note $Σ_0$ et $Σ_1$), il vient, en reprenant les calculs, que :

• \[Σ_0 = \frac{\sum\limits_{ i=1 }^n (1-y_i)(x_i - μ_0) (x_i - μ_0)^T}{\sum\limits_{ i=1 }^n (1-y_i)}\]
• \[Σ_1 = \frac{\sum\limits_{ i=1 }^n y_i(x_i - μ_1) (x_i - μ_1)^T}{\sum\limits_{ i=1 }^n y_i}\]

Frontière de classification

On prédit $y=1$ si, et seulement si :

\[\begin{align*} & \underbrace{\ln\left(\displaystyle\frac{π_1}{1-π_1}\right) + \frac 1 2 \big(μ_0^T Σ_0^{-1} μ_0 - μ_1^T Σ_1^{-1} μ_1\big)}_{≝ \; α'_1} + x^T (Σ_1^{-1} μ_1 - Σ_0^{-1} μ_0) + x^T (Σ_0^{-1} - Σ_1^{-1}) x ≥ 0 \\ ⟺ \quad& \tilde{x}^T \underbrace{\begin{pmatrix} Σ_1^{-1} μ_1 - Σ_0^{-1} μ_0 \\ α'_1 \\ \end{pmatrix}}_{≝ \; β'} + x^T (Σ_0^{-1} - Σ_1^{-1}) x ≥ 0 &&\text{(avec les notations des questions précédentes)} \end{align*}\]

7.

Dans les différents ensembles d’apprentissage, je parlerai de “points bleus” (resp. “points rouges”) pour désigner les points dont le label est 0 (resp. 1).

• Dans l’ensemble A : les points bleus et rouges semblent générés par deux Gaussiennes (une pour chaque couleur) dont la matrice de covariance a un valeur propre bien plus grande que l’autre, donnant une forme d’“ellispe allongée” aux amas bleus et rouge. De plus, ils se chevauchent un peu, mais semblent néanmoins séparables par une droite, d’où :

  • la très bonne performance (un peu meilleure que les autres sur l’ensemble d’entraînement) de la régression linéaire sur cet ensemble
  • le fait que l’ensemble, les classifieurs se valent à peu près sur A

  On notera tout de même que QDA est meilleur que les autres sur l’ensemble de test : la conique de séparation épouse un peu la frontière de séparation des amas bleus et rouges.

• Dans l’ensemble B : les amas bleus et rouges semblent encore générés par deux Gaussiennes :

  • celle des points rouges étant semblable à celle de l’ensemble A
  • celle des points bleus ayant une matrice de covariance avec des valeurs propres de taille similaire, donnant une forme de disque à l’amas bleu

  Il est bien plus dur de séparer linéairement les deux amas, puisque l’amas rouge “plonge” (s’enfonce) dans l’amas bleu, d’où un taux d’erreur des classifieurs plus élevé que précédemment.

  • la régression logistique et QDA se démarque en étant meilleurs sur l’ensemble d’entraînement (la régression logisitique étant aussi meilleure que les autres sur l’ensemble test):

    • la régression logistique dresse une frontière de séparation linéaire un peu plus serrée contre l’amas bleu (du fait de la descente de gradient, qui “abaisse” la frontière de séparation de la régression linéaire et LDA (avec un nombre d’itérations inférieurs, régressions logistique, linéaire et LDA se superposent presque)
    • la conique de QDA “enveloppe” l’amas rouge plongeant dans l’amas bleu

• L’ensemble C est très similaire à B, à l’exception d’un deuxième amas circulaire de points rouges isolés de l’amas principal. Cet amas d’“outliers” fait baisser la performance de

  • QDA (qui devient le pire) en forçant la conique à prendre une forme d’hyperbole, englobant plus de points bleus dans la zone rouge
  • la régression linéaire et LDA, qui ont une frontière linéaire dont la pente a changé, pour éviter cet amas, englobant par là même plus de points bleus dans la zone estimée rouge

Par contre, la frontière de la régression logistique passe en-dessous de l’amas : elle ne change donc pas, et reste plus performante que les autres.

8.

La méthode des $k$ plus proches voisins, qui est un modèle discriminatif puisqu’aucune supposition n’est faite sur la distribution des $x_i$, est plus performante sur cette tâche de classification.

En effet, les modèles génératifs QDA et LDA essayent d’estimer $P(X, Y)$ en faisant des suppostions les distributions qui générent (d’où le nom) les $x_i$, pour chaque classe (en l’occurrence, la supposition faite est qu’il s’agit de Gaussiennes).

En ne faisant pas de supposition sur la distribution des $x_i$, la méthode des $k$ plus proches voisins ne s’attache qu’au fait que plus des images sont proches (au sens de la distance euclidienne) plus elles sont susceptibles de représenter le même chiffre (même classe).

On notera que les modèles génératifs ne sont pas à leur avantage dans cette tâche de classification de chiffres, puisqu’il n’y a aucune raison que les images d’une même classe soient générées par une Gaussienne : par le théorème central-limite, la génération par des Gaussiennes est une hypothèse raisonnable quand les données résultent d’une multitude de processus aléatoires suivant la même loi (comme dans la nature par exemple), ce qui n’est pas le cas ici.