Sur-apprentissage, régularisation et dropout

Sur-apprentissage

on se place dans le cadre des modèles paramétriques:

• approximation linéaire,
• approximation polynomiale,

• réseaux de neurones,...

  et d'un problème des moindre carrés. On veut donc, à partir d'échantillons $(x_i,y_i)$ avec $1\leq i\leq n$ trouver une approximation de $y=f(x)$ tel que on minimise $$ \operatorname{min} \sum_{i=1}^n \parallel y_i - f_{\theta}(x_i)\parallel_2^2 $$

  avec $f_{\theta}$ le modèle paramétrique. On part du principe qu'on a souvent des données bruitées, donc du type $$ y_i = f(x_i) + \epsilon_i $$ avec $\epsilon_i$ une perturbation Gaussienne.

Ce type problème est une régression. A la différence de l'interpolation on ne demande pas au modèle de passer obligatoirement par les exemples.

Surapprentissage: C'est lorsque le modèle approche trop bien l'échantillon et que cela à pour conséquence de dégrader son efficacité sur des données qui ne sont pas dans l'échantillon.

On risque d'apprendre le bruit ou les biais de l'échantillon.

Exemple: régression polynomiale avec (200 puis 30 points) sur la fonction $cos(\pi x)$.

plot_overfitting(200)

plot_overfitting(30)

But:

• Montrer sur la régression linéaire notamment, pourquoi cela arrive et comment éviter le problème.
• montrer l'importance de ce problème et les solutions sur des réseaux de neurones.

Régression linéaire

On a un problème qui peut s'écrire par:

$$ Y_i = (\mathbf{\beta},\mathbf{X}_i)+\alpha_0 + \epsilon $$

avec $\mathbf{X}\in \mathbb{R}^m$ et $Y\in \mathbb{R}$.

avec $\epsilon = \mathcal{N}(0,\sigma)$ un bruit Gaussien. On connait un échantillon $(\mathbf{X}_1,...,\mathbf{X}_n)$ et $(Y_1,...,Y_n)$ bruité du modèle.

Le problème de régression consiste à trouver $(\mathbf{\beta},\alpha)$ à partir de l'échantillon.

On écrit la matrice $\mathcal{X} \in \mathcal{M}_{n,m+1} (\mathbb{R})$ tel que

$$ \mathcal{X}_{i1}=1, \quad \mathcal{X}_{ij}= X_j^i $$

et le vecteur $\mathcal{Y} \in \mathcal{M}_{n}(\mathbb{R})$ tel que

$$ \mathcal{Y}_{i}= Y^i $$

On pose $\hat{\beta}=(\beta,\alpha)$. On cherche la solution du problème:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}} E(\hat{\beta})=\operatorname{argmin}_{\hat{\beta}}\parallel \mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2 $$

Cas de la petite dimension

Le minimum de la fonctionnelle $E(\hat{\beta})$ est atteint pour

$$ \nabla E(\hat{\beta}) =0 \Longleftrightarrow 2\mathcal{X}^t(\mathcal{X}\hat{\beta} - \mathcal{Y})=0 $$

donc

$$ \mathcal{X}^t\mathcal{X}\hat{\beta} = \mathcal{X}^t\mathcal{Y} $$

avec $\mathcal{X}^t\mathcal{X} \in \mathcal{M}_{m+1,m+1}(\mathbb{R})$.

On peut montrer que $Rg(\mathcal{X})=Rg(\mathcal{X}^t\mathcal{X})$. Dans ce cas la matrice est inversible si $Rg(\mathcal{X})=m+1$.

On se place dans le cas $n>>m$. On a donc beaucoup d'exemples par rapport à la dimension du problème.

Dans ce cas, on sera en général dans le cas inversible:

$$ \hat{\beta}^* = \underbrace{(\mathcal{X}^t\mathcal{X})^{-1}\mathcal{X}^t)}_{\mbox{pseudo inverse}}\mathbf{Y} $$

On regarde l'erreur:

$$ \mathbb{E}\left[\left(\mathcal{Y}-\mathcal{X}\hat{\beta}^*\right)^2\right] = \sigma^2+ Biais[\hat{\beta}^*]^2 + Var[\hat{\beta}^*] $$

avec

$$ Biais[\hat{\beta}^*]=\left(\mathbb{E}\left[\mathcal{X}\hat{\beta}^*\right] - \mathbb{E}\left[\mathcal{X}\hat{\beta}_{ref}\right]\right) $$

et

$$ Var[\hat{\beta}^*]= \mathbb{E}\left[\left(\mathcal{X}\hat{\beta}^*-\mathbb{E}\left[\mathcal{X}\hat{\beta}^*\right]\right)^2\right] $$

Ici $Biais[\hat{\beta}^*]=0$ et $Var[\hat{\beta}^*]=\sigma^2(\mathcal{X}^t\mathcal{X})^{-1}$.

L'estimateur obtenu est l'estimateur sans biais, linéaire en $\mathcal{Y}$ à la plus petite variance.

plot_biais()

sigma=0.2
lam=0.0
plot_result(lam,sigma,20)

sigma=0.2
lam=0.0
plot_result(lam,sigma,400)

Cas de la grande dimension

On voit que lorsque $m>n$ (nombre d'exemples inférieur à la dimension) on risque Le sur-apprentissage.

Le modèle colle parfaitement aux données bruitées mais moins bien avec les données non bruitées (le vrai modèle sous-jacent).

On le retrouve à travers la variance qui modélise la dispersion à la moyenne. Plus elle est grande plus le modèle est sensible au fluctuation d'échantillonnage.

Explication:

Si $m>n$ la matrice $(\mathcal{X}^t\mathcal{X})$ n'est pas inversible. Il existe plusieurs solutions (méthodes de gradients).

Plus $m>>n$ plus la variance de l'estimateur augmente plus on va avoir du sur-apprentissage.

Exemple: Classification/régression sur des images. $m=10^6$ et souvent $n \approx 10^4- 10^7$.

Régression avec régularisation $L^2$

Idée: Accepter une augmentation du biais (on espère petite) pour diminuer la variance. Pour cela on impose des contraintes supplémentaires.

Régularisation Ridge: on va ajouter une contrainte pour obtenir des poids pas trop larges.

On pose $\hat{\beta}=(\beta,\alpha)$. On cherche la solution du problème:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}} E(\hat{\beta})=\operatorname{argmin}_{\hat{\beta}}\frac12\parallel \mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2^2 $$

sous contrainte $\sum_{i=1}^{m+1}\beta_i^2 \leq \tau$.

En général on résout une version rélaxée (contrainte faible):

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}} E(\hat{\beta})=\operatorname{argmin}_{\hat{\beta}}\frac12\parallel \mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2^2 + \lambda \sum_{i=1}^{m+1}\hat{\beta}_i^2 $$

On voit que plus $\lambda$ est grand plus on va chercher à minimiser la norme des poids. $\lambda=0$ donne le cas sans régularisation.

Le minimum de la fonctionnelle $E(\hat{\beta})$ est atteint pour

$$ \nabla E(\hat{\beta}) =0 \Longleftrightarrow 2\mathcal{X}^t(\mathcal{X}\hat{\beta} - \mathcal{Y}) + 2\lambda\hat{\beta}=0 $$

donc

$$ \left(\mathcal{X}^t\mathcal{X}+\lambda I_d\right)\hat{\beta} = \mathcal{X}^t\mathcal{Y} $$

avec $\mathcal{X}^t\mathcal{X} \in \mathcal{M}_{m+1,m+1}(\mathbb{R})$. On voit que la régularisation ajoute une matrice homogène à l'idendité. La matrice $\mathcal{X}^t\mathcal{X}$ étant positive, on obtient un problème inversible.

$$ \hat{\beta}^* = \left(\mathcal{X}^t\mathcal{X}+\lambda I_d\right)^{-1}\mathcal{X}^t\mathcal{Y} $$

On voit que pour $\lambda >>1$ on voit que $\nabla E(\hat{\beta}) =0$ équivaut à $$ \hat{\beta} = O\left(\frac{1}{\lambda}\right) $$

Donc la régularisation pousse bien les poids à être le plus petit possible.

On regarde l'erreur:

$$ \mathbb{E}\left[\left(\mathcal{Y}-\mathcal{X}\hat{\beta}^*\right)^2\right] = \sigma^2+ Biais[\hat{\beta}^*]^2 + Var[\hat{\beta}^*] $$

avec

$$ Biais[\hat{\beta}^*]=\left[\left(\mathcal{X}^t\mathcal{X}+\lambda I_d\right)^{-1}- (\mathcal{X}^t\mathcal{X})^{-1}\right](\mathcal{X}^t\mathcal{X})\hat{\beta} $$

et

$$ Var[\hat{\beta}^*]= \sigma^2\left[\left(\mathcal{X}^t\mathcal{X}+\lambda I_d\right)^{-1}(\mathcal{X}^t\mathcal{X})\left(\mathcal{X}^t\mathcal{X}+\lambda I_d\right)^{-1}\right] $$

Il est possible de démontrer que le maximum de cette variance est atteint en $\lambda=0$.

Résultats: On fixe m =20 et n=100 et on fait varier le coefficient de la Régularisation "Ridge"

plot_reg_m(0.05,20)

Résultats: On fixe m =300 et n=100 et on fait varier le coefficient de la Régularisation "Ridge"

plot_reg_m(0.05,300)

Regréssion avec régularisation $L^1$

La régularisation $L^2$ permet d'avoir "peu" de cofficients de $\beta$ grands. Une autre solution est de forcer à avoir peu de coefficients non nuls (on parle de parcimonie).

Pour cela on fait une régularisation $L^1$ appelée régression Lasso.

En général on résout sous forme faible:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}}\frac12\parallel \mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2^2 + \lambda \sum_{i=1}^{m+1}\mid\hat{\beta}_i\mid $$

Il existe de pas de solution analytique contrairement à la régression Ridge.

Pour se convaincre de l'effet de la régularisation Lasso: cas simple $\mathcal{X}^t\mathcal{X}=I_d$.

On développe $ \frac12\parallel\mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2$ ce qui donne

$$ \frac12\parallel\mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2 = \frac{1}{2}(\mathcal{Y},\mathcal{Y})-(\mathcal{Y},\mathcal{X}\hat{\beta})+(\hat{\beta}, \mathcal{X}^t\mathcal{X}\hat{\beta}) = \frac{1}{2}(\mathcal{Y},\mathcal{Y})-(\mathcal{Y},\mathcal{X}\hat{\beta})+(\hat{\beta},\hat{\beta}) $$

puisque $\mathcal{Y}$ ne depend pas de $\hat{\beta}$, le problème de minimisation Lasso revient à minimiser

$$ \operatorname{argmin}_{\hat{\beta}} -(\mathcal{Y},\mathcal{X}\hat{\beta})+(\hat{\beta},\hat{\beta}) + \lambda \sum_{i=1}^{m+1}\mid\hat{\beta}_i\mid $$

On pose $\hat{\beta}_{mc}$ la solution du problème des moindres carrés sans régularisation:

$$ \hat{\beta}_{mc}= (\mathcal{X}^t\mathcal{X})^{-1}\mathcal{X}^t\mathcal{Y}=\mathcal{X}^t\mathcal{Y} $$

Le problème de minimisation se réécrit donc

$$ \operatorname{argmin}_{\hat{\beta}} -(\hat{\beta}_{mc},\hat{\beta})+(\hat{\beta},\hat{\beta}) + \lambda \sum_{i=1}^{m+1}\mid\hat{\beta}_i\mid $$

On remarque que si $\hat{\beta}_{j,mc}>0$ alors $\hat{\beta}_{j}\geq 0$ et si $\hat{\beta}_{j,mc}<0$ alors $\hat{\beta}_{j}\leq 0$

La fonction étant pas dérivable en zéro on sépare les cas:

• $\hat{\beta}_{j,mc}>0$ dans ce cas la fonction minimisée est

$$ f(\hat{\beta}_j)= -\hat{\beta}_{j,nc}\hat{\beta}_j+\frac12\hat{\beta}_j^2+\lambda \hat{\beta}_j $$

donc $f^{'}(\hat{\beta}_j)$ implique

$$ \hat{\beta}_j= \hat{\beta}_{j,mc}-\lambda $$

Comme $\hat{\beta}_j \geq 0$ on a $\hat{\beta}_j= max(0,\hat{\beta}_{j,mc}-\lambda)$. Par le même raisonnement on obtient que pour $\hat{\beta}_{j,mc}<0$ on a

$$ \hat{\beta}_j= max(0,-\hat{\beta}_{j,mc}-\lambda) $$

donc à la fin

$$ \hat{\beta}_j = sign(\hat{\beta}_{j,mc})max(0,\mid\hat{\beta}_{j,mc}\mid-\lambda) $$

On voit donc que plus $\lambda$ est large plus le nombre de coefficients nuls sera important.

La régression Lasso est très utile si un nombre faible de variables expliquent les données (hypothèse de parcimonie).

Si le vrai vecteur solution est creux. La régression Lasso peut capter cette solution.

Résultats: On fixe m =20 et n=100 et on fait varier le coefficient de la pénalisation "Lasso"

plot_reg_ml(0.05,20)

Résultats: On fixe m =300 et n=100 et on fait varier le coefficient de la pénalisation "Lasso"

plot_reg_ml(0.05,300)

Regréssion avec régularisation $L^1/L^2$

On peut évidemment mélanger les deux approches. On parle de régression ElasticNet. En général on résout sous forme faible:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}}\parallel \mathcal{Y}-(\hat{\beta},\mathcal{X})\parallel_2 + \lambda r \sum_{i=1}^{m+1}\mid\hat{\beta}_i\mid + \lambda (1-r) \sum_{i=1}^{m+1}\mid\hat{\beta}_i^2\mid $$

Il existe de pas de solution analytique.

Résultats: On fixe m =20, n=100 et $\lambda=0.2$ et on fait varier le ratio entre les deux pénalisations de "Elastic Net"

plot_reg_me(0.05,0.2,20)

Résultats: On fixe m =300, n=100 et $\lambda=0.2$ et on fait varier le ratio entre les deux pénalisations de "Elastic Net"

plot_reg_me(0.05,0.2,300)

Dropout

On se place dans un cadre non régularisé. On résout le problème de régression par des méthodes itératives comme des méthodes de gradients.

Idée de régularisation: la meilleure façon de "régulariser" un modèle de taille fixe est de faire une moyenne pondérée des prédictions de tous les jeux de paramètre $\theta$ possible. Possible pour des petits modèles. Impossible pour des gros modèles comme les réseaux de neurones.

But: approcher cette moyenne sur des gros modèles (croissances exponentielle des jeux de paramètres possibles).

Dropout (abandon): l'idée d'abandonner, désactiver certains paramètres temporairement pendant les itérations du gradient. En changeant régulièrement les paramètres gelés, on retrouve à la fin un effet de moyenne.

Dans le cas de la régression:

• si on gèle $\alpha$ paramètres à chaque itération, c'est comme si on était sur un problème de dimension $\alpha m$. On peut donc se retrouver dans des cas ou $\alpha m < n$ et donc pas de sur-apprentissage.

• chaque paramètre à une probabilité $p$ (loi de bernoulli) d'être temporairement abandonné.

• Pour la régression il suffit de mettre à zéro une sortie pour l'abandonner.

On définit $R$ une matrice tel que

$$ R_{ij} = \mathcal{B}(p) $$

avec $\mathcal{B}$ une loi de Bernouilli. La dropout s écrit donc

$$ R * \mathcal{X} $$ avec $*$ le produit terme à terme et le problème de minimisation s'écrit:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}}\mathbb{E}_{R \approx \mathcal{B}(p)}[\parallel \mathcal{Y}-R*\mathcal{X}\hat{\beta}\parallel_2^2] $$

On peut montrer que le précédent problème revient à:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}}[\parallel \mathcal{Y}-p\mathcal{X}\hat{\beta}\parallel_2^2] +p(1-p)\parallel \Gamma\hat{\beta}\parallel_2^2 $$

avec $\Gamma = \sqrt{diag(\mathcal{X}\mathcal{X}^t)}$

Conclusion: la dropout revient a une méthode de régularition Ridge ou les poids associés aux plus grosses entrées sont les plus régularisés.

Preuve:

On part de la fonction coût:

$$ \parallel \mathcal{Y}- R*\mathcal{X}\hat{\beta} \parallel_2^2= (\mathcal{Y},\mathcal{Y})- 2(R*\mathcal{X}\hat{\beta},\mathcal{Y}) +(R*\mathcal{X}\hat{\beta},R*\mathcal{X}\hat{\beta}) $$

On prend l'espérance pour obtenir:

$$ (\mathcal{Y},\mathcal{Y})- 2(\mathbb{E}[R*\mathcal{X}]\hat{\beta},\mathcal{Y}) +(\hat{\beta},\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}]\hat{\beta}) $$

on commence par la première espérance: $$ (\mathbb{E}[R*\mathcal{X}])_{ij}=\mathbb{E}_{R}[(R*\mathcal{X})_{ij}]= X_{ij}\mathbb{E}_{R}[R_{ij}]= p X_{ij} $$

On va maintenant calculer la seconde:

$$ ((R*\mathcal{X})^tR*\mathcal{X})_{ij}=\sum_{k=1}^n R_{ki}R_{jk}X_{ki}X_{kj} $$

On en déduit (car les lois sont indépendantes) que:

$$ (\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}])_{ij}= p^2 (\mathcal{X}^t\mathcal{X})_{ij}, \quad \forall i\neq j $$

et

$$ (\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}])_{ij}= p (\mathcal{X}^t\mathcal{X})_{ii}, \quad \forall i= j $$

Maintenant on revient au calcul global, on utilise la 1ère espérance pour avoir:

$$ \parallel \mathcal{Y}- R*\mathcal{X}\hat{\beta} \parallel_2^2 =\parallel \mathcal{Y}-p\mathcal{X}\hat{\beta}\parallel_2^2 -p^2(\mathcal{X}\hat{\beta} ,\mathcal{X}\hat{\beta} )+(\hat{\beta},\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}]\hat{\beta}) $$

On obtient donc

$$ \parallel \mathcal{Y}- R*\mathcal{X}\hat{\beta} \parallel_2^2 =\parallel \mathcal{Y}-p\mathcal{X}\hat{\beta}\parallel_2^2+(\hat{\beta},(\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}]-p^2(\mathcal{X}^t\mathcal{X}))\hat{\beta}) $$

En utilisant les calculs sur l'espérance $\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}]$ on voit que

$$ (\mathbb{E}[(R*\mathcal{X})^tR*\mathcal{X}]-p^2(\mathcal{X}^t\mathcal{X}))=p(1-p)diag(\mathcal{X}^t\mathcal{X}) $$

ce qui permet de conclure. Fin preuve

Régularisation de Tikhonov

Il s'agit d'un cas généralisé de Ridge qu'on écrit sous la forme:

$$ \hat{\beta}^*=\operatorname{argmin}_{\hat{\beta}}[\parallel \mathcal{Y}-\mathcal{X}\hat{\beta}\parallel_2^2] +\parallel \Gamma\hat{\beta}\parallel_2^2 $$

avec $\Gamma$ une matrice. Le dropout comme la régularisation Ridge rentre dans ce cas.

Exemple: Lorsque les données sont issues d'une fonction continue sur une grille régulière. On peut utiliser dans ce cas une pénalisation de ce type:

$$ \int \mid\nabla f\mid^2 dP_x(x) = -\int f \Delta f dP_x(x) $$

Plus la régularisaion est forte plus on irait vers des approximations régulières (simple) notamment vers les zones ou la densité de point est forte.

Ce genre de pénalisation peut être construite à partir des données (on ne détaillera pas).

Régularisation et dropout pour les réseaux de neurones

On applique les réseaux de neurones régulièrement dans ces cas ou $m>n$ ou $m \approx n$ avec $m$ le nombre de paramètres. On est surtout très souvent dans des cas ou le nombre de paramètres > $n$. C'est ca qui provoque du sur-apprentissage.

La régularisation est donc un outil très important.

Le principe (modification de la fonction coût) reste le même pour les réseaux.

model.summary() ### affiche du résumé du modèle
model.compile(optimizer=opt, loss="mse", metrics=["mse"]) ## construction du modèle

Model: "sequential_26"
_________________________________________________________________
Layer (type)                 Output Shape              Param #   
=================================================================
dense_101 (Dense)            (None, 100)               2100      
_________________________________________________________________
dense_102 (Dense)            (None, 200)               20200     
_________________________________________________________________
dense_103 (Dense)            (None, 50)                10050     
_________________________________________________________________
dense_104 (Dense)            (None, 1)                 51        
=================================================================
Total params: 32,401
Trainable params: 32,401
Non-trainable params: 0
_________________________________________________________________

Résultats dans le cas sans régularisation

history=apply_ANN(X_train,Y_train)

Résultats dans le cas Ridge

history2=apply_ANNL2(X_train,Y_train)

Résultats avec dropout

history3=apply_ANNDrop(X_train,Y_train)

Comparaison:

plt.plot(history.history['val_loss']) ## historique de la fonction cout du jeu de donnée "test"  ## historique de la fonction cout du jeu de donnée "train"
plt.plot(history2.history['val_loss']) ## historique de la fonction cout du jeu de donnée "test"## historique de la fonction cout du jeu de donnée "train"
plt.plot(history3.history['val_loss']) ## historique de la fonction cout du jeu de donnée "test"
plt.show()

Conclusion

Lorsque le nombre de paramètres $m$ est supérieur ou se rapproche du nombre de points $n$ on risque le sur-apprentissage.

Sur-apprentissage: on colle trop à l'échantillon (cela peut revenir à apprendre le bruit ou les biais des échantillons). On généralise moins bien à des nouvelles données.

Régularisation : on ajoute des contraintes sur les coefficients.