TD 12: Révisions
Exercice 1: Naive Bayes
- $Y \sim Ber(π)$
- \[X = (\underbrace{X_1, ⋯, X_d}_{\text{indépendants sachant } Y}) \quad \text{ tq }\quad X_i \mid Y \sim Ber(μ_{i,y})\]
- $X_i \mid Y=0 \sim Ber(μ_{i0})$
- $X_i \mid Y=1 \sim Ber(μ_{i1})$
a).
\[\begin{align*} \underbrace{p(x,y)}_{≝ \, p(X=x, Y=y)} & = p(\underbrace{x}_{= (x_1, ⋯, x_d) ∈ ℝ^d} \mid y) p(y) \\ & = \underbrace{p(y)}_{= π^y (1-π)^{1-y}} \prod\limits_{ i=1 }^d p(x_i \mid y) \\ & = π^y (1-π)^{1-y} \prod\limits_{ i=1 }^d (\underbrace{μ_{i1}}_{=p(x_i=1 \mid y=1)})^{x_iy} (\underbrace{1-μ_{i1}}_{=p(x_i=0 \mid y=1)})^{(1-x_i)y}(μ_{i0})^{x_i (1-y)} (1-μ_{i0})^{(1-x_i)(1-y)} \end{align*}\]Donc
\[\begin{align*} \log(p(x,y)) & = y \log π + (1-y) \log(1-π) + \sum\limits_{ i=1 }^d x_i y \log(μ_{i1}) + (1-x_i) y \log(1-μ_{i1}) + x_i (1-y) \log(μ_{i0}) + (1-x_i)(1- y) \log(μ_{i0}) \\ & = y \log π + (1-y) \log(1-π) + y \left(\sum\limits_{ i=1 }^d x_i \log(μ_{i1}) + (1-x_i) \log(1-μ_{i1}) \right) + (1-y)\left(\sum\limits_{ i=1 }^d x_i \log(μ_{i0}) + (1-x_i) \log(μ_{i0}) \right) \\ \end{align*}\]b).
\[\begin{align*} \log p(Y=1 \mid x) - \log p(Y=0 \mid x) & = \log\left(\frac{p(Y=1 \mid x)}{p(Y=0 \mid x)}\right) \\ & = \log\left( \frac{p(x, y=1)}{p(x)} \frac{p(x)}{p(x, y=0)} \right) &&\text{(Bayes)}\\ &= \log\left( \frac{p(x, y=1)}{p(x, y=0)} \right) \\ &= \log\left( \frac{π \prod\limits_{ i=1 }^d μ_{i1}^{x_i}(1-μ_{i1})^{1-x_i} }{ (1- π) \prod\limits_{ i=1 }^d μ_{i0}^{x_i}(1-μ_{i0})^{1-x_i}} \right) \\ &= \log\left(\frac{π}{1-π}\right) + \sum\limits_{ i=1 }^d x_i \log\left(\frac{μ_{i1}}{μ_{i0}}\right) + \sum\limits_{i=1}^d (1-x_i) \log\left(\frac{1-μ_{i1}}{1-μ_{i0}}\right) \end{align*}\]c).
\[\begin{align*} \log \underbrace{p(y=1 \mid x)}_{p_{1x}} - \log \underbrace{p(y=0 \mid x)}_{p_{0x}} & = \log p_{1x} - \log (1- p_{1x}) \\ & = \log\left(\frac{p_{1x}}{1-p_{1x}}\right) \\ & = \underbrace{\log\left(\frac{π}{1-π}\right) + \sum\limits_{i=1}^d \log\left(\frac{1-μ_{i1}}{1-μ_{i0}}\right)}_{=b} + \sum\limits_{ i=1 }^d x_i \underbrace{\left( \log\left(\frac{μ_{i1}}{μ_{i0}}\right) - \log\left(\frac{1-μ_{i1}}{1-μ_{i0}}\right)\right)}_{= a_i} \\ & = b + \underbrace{\sum\limits_{ i } x_i a_i}_{= a^T x} \end{align*}\]Donc
\[\frac{p_{1x}}{1-p_{1x}} = \exp(a^Tx+b)\]et
\[p_{1x} = \frac 1 {1+ \exp(-a^Tx-b)}\]d).
- $(x^1, y^1, ⋯, x^n, y^n)$
- $x^1 = (x^1_1, ⋯, x^1_d)$
Estimation du Maximum de Vraisemblance:
\[\begin{align*} \frac{\partial l}{\partial π} & = 0 \\ ⟺ & \quad \frac 1 π \sum\limits_{ j=1 }^n y^j - \frac 1 {1-π} \sum\limits_{ j=1 }^n (1-y^j) = 0 \\ ⟺ & \quad π \sum\limits_{ j=1 }^n (1-y^j) = (1-π) \sum\limits_{ j=1 }^n y^j \\ ⟺ & \quad π n = \sum\limits_{ j=1 }^n y^j \\ ⟺ & \quad π = \frac{\sum\limits_{ j=1 }^n y^j}{n} \end{align*}\] \[\frac{\partial l}{\partial μ_{i0}} = 0 ⟺ μ_{i0} = \frac{ \sum\limits_{ j=1 }^n y^j x_i^j}{\sum\limits_{ j=1 }^n y_j }\] \[\frac{\partial l}{\partial μ_{i1}} = 0 ⟺ μ_{i1} = \frac{ \sum\limits_{ j=1 }^n (1-y^j) x_i^j}{\sum\limits_{ j=1 }^n (1-y_j) }\]e).
Régression logistique ⟶ descente de gradient
f).
C’est un modèle génératif.
Proba jointe ⟹ modèle génératif
Proba conditionnelle ⟹ modèle discriminatif
h).
Sans indépendance: On a besoin de $2^d$ paramètres: toutes les lois conjointes des $x_i$
Exercice 2
\[\min_{x∈ℝ^d} \frac 1 2 \Vert x-z \Vert^2_2 + λ \Vert x \Vert_1\]a).
Forte convexité (si on enlève un terme quadratique, elle reste convexe) ⟹ existence et unicité du minimum
b).
\[\min_{(x_1, ⋯, x_n)∈ ℝ^d} \frac 1 2 \sum\limits_{ i=1 }^d \underbrace{(x_i - z_i)^2 + λ \vert x_i \vert}_{f_i(x_i)}\]Le problème est séparable : on peut résoudre coordonnée par coordonnée
\[\partial f_i(x_i) = x_i - z_i + λ \begin{cases} 1 &&\text{ si } x_i > 0 \\ -1 &&\text{ si } x_i < 0 \\ [-1, 1] &&\text{ si } x_i = 0 \end{cases}\]Remarque: à l’optimum, $x_i$ et $z_i$ sont de même signe (cf. TP Lasso, on le montre par l’absurde).
Cas 1: $z_i ≥ 0$ et donc $x_i ≥ 0$
\[0 ∈ \partial f_i (x_i) ⟺ x_i = z_i - λ\]Or, $x_i ≥ 0$, donc
\[z_i ≥ λ\]Cas 2: $z_i ≤ 0$ et donc $x_i ≤ 0$
\[0 ∈ \partial f_i (x_i) ⟺ x_i = z_i + λ\]Or, $x_i ≤ 0$, donc
\[z_i ≤ - λ\]NB: si $z_i = 0$, $x_i = 0$ (minimisation d’une somme de carrés)
\[x_i = \begin{cases} 0 &&\text{ si } \vert z_i \vert ≤ λ \\ z_i - λ &&\text{ si } z_i ∈ [λ, +∞] \\ z_i + λ &&\text{ si } z_i ∈ [-∞, -λ] \end{cases}\]c).
\[\inf_{x} a^T x + λ \Vert x \Vert_1 \\ = \inf_x \sum\limits_{ i=1 }^d a_i x_i + λ \vert x_i \vert\]-
Si $\vert a_{i_0} \vert = \max_i \vert a_i \vert > λ$ on prend $x_{i_0} ⟶ -sign(a_{i_0}) ∞$ et la fonction tend vers $-∞$
-
Si $\vert a_{i_0} \vert = \underbrace{\max_i \vert a_i \vert}{ = \Vert a \Vert∞} ≤ λ$ on prend $x_{i_0} = 0$ (comme $λ \vert x_i \vert$ est plus grand que $a_i x_i$, le terme $a_i x_i + λ \vert x_i \vert$ est positif)
Donc \(\inf_x a^T x + λ \Vert x \Vert_1 = \begin{cases} -∞ &&\text{ si } \Vert a \Vert_∞ > λ \\ 0 &&\text{ si } \Vert a \Vert_∞ ≤ λ \end{cases}\)
\[minimize_{x ∈ ℝ^d} \frac 1 2 \Vert x-z \Vert^2_2 + λ \Vert x \Vert_1\\ ⟺ minimize_{x, u ∈ ℝ^d} \frac 1 2 \Vert u \Vert^2_2 + λ \Vert x \Vert_1 \text{ tq } \begin{cases} x-z=u \\ ⟺ x-z-u = 0 \end{cases}\]
Lagrangien:
\[ℒ(μ, u, x) = \frac 1 2 \Vert u \Vert^2_2 + λ \Vert x \Vert_1 + μ^T(x-z-u)\]Dual:
\[\sup_{μ∈ℝ^d} \inf_{u,x∈ℝ^d} ℒ(μ, u, x) \\ = \sup_{μ∈ℝ^d} (- μ^T z) + \inf_{u∈ℝ^d} \left(\frac 1 2 \Vert u \Vert^2_2 - μ^T u\right) + \underbrace{\inf_{x∈ℝ^d} \left(μ^T x + λ \Vert x \Vert_1 \right)}_{= -∞ \text{ ou } 0 \text{ par la question précédente ⟶ on exclut le cas } -∞} \\ = \sup_{\Vert μ \Vert_∞ ≤ λ} (-μ^T z) + \inf_{u∈ℝ^d} \left(\frac 1 2 \Vert u \Vert^2_2 - μ^T u\right)\]Et
\[\inf_{u∈ℝ^d} \left(\frac 1 2 \Vert u \Vert^2_2 - μ^T u\right) = - \frac 1 2 \Vert μ \Vert^2_2\]Donc
\[\sup_{μ∈ℝ^d} \inf_{u,x∈ℝ^d} ℒ(μ, u, x) = \sup_{\Vert μ \Vert_∞ ≤ λ} - μ^T z - \frac 1 2 \Vert μ \Vert^2_2 \\ = \sup_{\Vert -μ \Vert_∞ ≤ λ} μ^T z - \frac 1 2 \Vert -μ \Vert^2_2 \\ = \sup_{\Vert μ \Vert_∞ ≤ λ} μ^T z - \frac 1 2 \Vert μ \Vert^2_2 \\ = \sup_{\Vert μ \Vert_∞ ≤ λ} - \frac 1 2 \Vert μ - z \Vert^2_2\]
Leave a comment