Skip to main content

Section 3.2 Rappel sur la régression et le maximum de vraisemblance

Ici on va rappeler la notion de régression linéaire qui permet de construire un modèle linéaire approchant au mieux des données. Il s'agit de premier modèle de régression. Pour construire ces modèles, on va se placer dans le cadre probabiliste qui est plus général.

Il s'agit d'une méthode développée par le statisticien Fisher en 1922. Elle permet la construction d'un estimateur statistique permettant de calculer une loi inférant les paramètres d'une loi inconnue dont on connaît un échantillon. Il s'agit d'une méthode générique basée sur la maximisation d'une fonction appelée fonction de vraisemblance. La fonction de vraisemblance quantifie la probabilité qu'un échantillon soit issu d'une loi donnée. Étant donné un échantillon observé \((x_1,\ldots,x_n)\) avec \(x \in \mathbb{R}^d\) et une loi de probabilité \(\mu_{\theta}\text{,}\) la fonction de vraisemblance quantifie la probabilité que les observations proviennent effectivement d'un échantillon (théorique) de la loi \(\mu_{\theta}\text{.}\)

Subsection 3.2.1 Estimateur de maximum de vraisemblance

Se donnant une loi paramétrique, on va chercher à maximiser la fonction de vraisemblance afin de trouver la loi qui maximise le fait que l'échantillon puisse être expliqué par elle. Pour mieux comprendre la définition qui suit, considérons un \(n\)-échantillon \((X_1,\dots ,X_n)\) de loi \(\mu_{\theta}\) discrète donnée par la probabilité \({P}_{\theta}\text{.}\) Soit \((x_1,\dots,x_n)\text{,}\) une observation de cet échantillon. On montre aisément que

\begin{equation*} \mathbb{P}\left(\bigcap_{i=1}^n\{X_i=x_i\}\right)=\prod_{i=1}^nP_\theta(x_i) \end{equation*}

en utilisant que les variables \((X_i)_{1\leq i\leq n}\) sont indépendantes. La méthode du maximum de vraisemblance revient à considérer qu'il est raisonnable d'estimer le paramètre \(\theta\) comme celui maximisant la probabilité de réalisation de \((x_1,\dots,x_n)\) définie ci-dessus.

Dans le cas où la loi \(\mu_{\theta}\) est donnée par une densité continue \(f_\theta\text{,}\) on se donne \(\varepsilon>0\) et on cherche à estimer \(\mathbb{P}\left(\bigcap_{i=1}^n\{|X_i-x_i|\leq \varepsilon\}\right)\text{.}\) On a

\begin{equation*} \mathbb{P}\left(\bigcap_{i=1}^n\{|X_i-x_i|\leq \varepsilon\}\right) =\prod_{i=1}^n\int_{x_i-\varepsilon}^{x_i+\varepsilon}f_\theta(x)\, dx \end{equation*}

Notons que \(\int_{x_i-\varepsilon}^{x_i+\varepsilon}f_\theta(x)\, dx\sim 2\varepsilon f_\theta(x_i)\) lorsque \(\varepsilon \to 0\) et par conséquent,

\begin{equation*} \mathbb{P}\left(\bigcap_{i=1}^n\{|X_i-x_i|\leq \varepsilon\}\right) \sim 2^n\varepsilon^n\prod_{i=1}^nf_\theta(x_i)\quad \text{lorsque }\varepsilon \to 0. \end{equation*}

Pour s'extraire de la dépendance en \(\varepsilon\text{,}\) on considère qu'il est raisonnable de chercher à maximiser \(\lim_{\varepsilon\to 0}\mathbb{P}\left(\bigcap_{i=1}^n\{|X_i-x_i|\leq \varepsilon\}\right)/(2\varepsilon)^n\text{.}\)

Définition 3.6. Fonction de vraisemblance.

Soit \(X\text{,}\) une v.a.r. discrète ou à densité sur l'espace probabilisé \((\Omega,\mathcal{A},\mathbb{P})\) de loi \(\mu_{\theta}\) définie par la probabilité \({P}_{\theta}\) dans le cas discret et par une densité \(f_{\theta}\) sinon, dont on veut estimer le paramètre \(\theta\) appartenant à un ensemble \(\Theta\text{.}\)

Soit

\begin{equation*} f: X(\Omega)\times \Theta\ni (x;\theta) \mapsto \begin{cases} f_{\theta}(x), \mbox{dans le cas continu}\\ P_{\theta}(X= x), \mbox{dans le cas discret}\\ \end{cases} \end{equation*}

Soit \((x_1,\dots ,x_n)\text{,}\) un \(n\)-échantillon de loi \(\mu_{\theta}\text{.}\) La fonction de vraisemblance \(\mathcal{L}\) associée à cet échantillon est définie par

\begin{equation} \displaystyle \mathcal{L}: X(\Omega)^n\times \Theta\ni (x_1,\dots, x_n;\theta)\mapsto \prod_{i=1}^n f(x_i;\theta)\tag{3.3} \end{equation}

Maintenant que la fonction est introduite on obtient l'estimateur par maximisation. En général on résout problème reformulé, qu'on appelle maximum du log vraisemblance. Il s'agit simplement de prendre le log de la fonction de vraisemblance ce qui permet d'obtenir une somme au lieu d'un produit ce qui est plus facile a dérivée.

Définition 3.7. Estimateur de maximum de vraisemblance/de log vraisemblance.

Lorsque la fonction de vraisemblance admet un unique maximum, l'estimateur du maximum de vraisemblance \(\hat{\theta}_n\) est défini par

\begin{equation} \hat{\theta}_n =\underset{\theta\in\Theta}{\operatorname{argmax}}~ \mathcal{L}(X_1,...X_n;\theta) \tag{3.4} \end{equation}

On définit également l'estimateur du maximum de log vraisemblance \(\hat{\theta}_n\) par

\begin{equation*} \hat{\theta}_n =\underset{\theta\in\Theta}{\operatorname{argmax}}~ \mathcal{L}_{\log}(X_1,...X_n;\theta) \quad \text{avec } \mathcal{L}_{\log}(X_1,...X_n;\theta)= \sum_{i=1}^n \log f(X_i;\theta) \end{equation*}

On va maintenant donner un rapide exemple.

On considère un échantillon \((x_1,\dots,x_n)\in \{0,1\}^n\) tiré selon une loi binomiale \(\mathcal{B}(1,p)\text{,}\) et on cherche à estimer \(\theta=p\in [0,1]\text{.}\) Remarquons que \(\sum_i x_i\) représente la quantité totale de "1" obtenue dans l'échantillon. Estimons \(p\text{.}\)

Solution.

La fonction de vraisemblance s'écrit alors :

\begin{equation*} \mathcal{L}(x_1,...x_n;\theta)= \prod_{i=1}^n\mathbb{P}_\theta(\{X_i=x_i\})=\theta^{\sum_i x_i}(1-\theta)^{n-\sum_ix_i}, \end{equation*}

en utilisant que \(\mathbb{P}_\theta(\{X_i=1\})=p=\theta\) et \(\mathbb{P}_\theta(\{X_i=0\})=1-p=1-\theta\text{.}\)

Remarquons que les extrémités de l'intervalle \([0,1]\) ne peuvent pas résoudre le problème de maximisation

\begin{equation*} max_{\theta\in [0,1]} \mathcal{L}(x_1,...x_n;\theta), \end{equation*}

sauf si \(\sum_ix_i\in \{0,n\}\text{.}\) Par ailleurs, il est aisé de se convaincre que ce problème possède une unique solution dans \([0,1]\text{.}\) On en déduit que la solution \(\theta^*\) est donnée par

\begin{equation*} \frac{\partial \displaystyle \mathcal{L}}{\partial \theta}(x_1,...,x_n;\theta) =0 \Leftrightarrow \theta^*=\frac{1}{n}\sum_ix_i. \end{equation*}

Ainsi, on retrouve l'estimateur de l'espérance obtenu en appliquant la loi des grands nombres, ce qui est cohérent puisque \(p=\mathbb{E}(X_i)\text{.}\)

On va rapidement introduire des résultats de convergence pour la méthode. l'objectif est notamment de quantifier la précision de l'estimateur de maximum de vraisemblance. Dans la suite on considérera que la fonction de fr log vraisemblance est de régularité suffisante.

On traite que le cas de loi de probabilité continue.
\begin{equation*} \mathbb{E}\left[\left( \frac{\partial}{\partial \theta} \mathcal{L}_{log}(X,\theta)\right) \mid \theta\right] = \int \frac{\partial}{\partial \theta} \mathcal{L}_{log}(x,\theta) f(x,\theta) dx \end{equation*}
en utilisant la derivée du log on obtient
\begin{equation*} \mathbb{E}\left[\left( \frac{\partial}{\partial \theta} \mathcal{L}_{log}(X,\theta)\right) \mid \theta\right] = \int \frac{\frac{\partial}{\partial \theta} f(x,\theta)}{f(x,\theta)} f(x,\theta) dx \end{equation*}
ce qui donne
\begin{equation*} \mathbb{E}\left[\left( \frac{\partial}{\partial \theta} \mathcal{L}_{log}(X,\theta)\right) \mid \theta\right] = \frac{\partial}{\partial \theta} \int f(x,\theta) dx= \frac{\partial}{\partial \theta} 1=0 \end{equation*}

Définition 3.10.

On nomme l'information de Fisher comme le moment d'ordre 2 de la fonction de log vraisemblance
\begin{equation*} I(\theta)=\mathbb{E}\left[\left( \frac{\partial}{\partial \theta} \mathcal{L}_{log}(X,\theta)\right)^2 \mid \theta\right] \end{equation*}
\begin{equation*} I(\theta)= - \mathbb{E}\left[\left( \frac{\partial}{\partial^2 \theta} \mathcal{L}_{log}(X,\theta)\right) \mid \theta\right] \end{equation*}
ce qui donne
\begin{equation*} I(\theta)= - \int \left(\frac{\partial_{\theta^2} f(x,\theta)}{f(x,\theta)} - \left(\frac{\partial_{\theta} f(x,\theta)}{f(x,\theta)}\right)^2\right)f(x,\theta) dx \end{equation*}
\begin{equation*} I(\theta)= - \int \left(\frac{\partial_{\theta^2} f(x,\theta)}{f(x,\theta)} - \left(\partial_{\theta} log f(x,\theta)\right)^2\right)f(x,\theta) dx \end{equation*}
ce qui donne
\begin{equation*} I(\theta)=- \partial_{\theta^2} \int f(x,\theta) dx + \mathbb{E}\left[\left(\partial_{\theta} log f(x,\theta)\right)^2\right] \end{equation*}
en utilisant \(\partial_{\theta^2} \int f(x,\theta) dx=0\) on conclut.

L'information de Fisher qui mesure la courbure va permettre d'obtenir des résultats sur les estimateurs et plus particulièrement celui du maximum de vraisemblance.

Subsubsection 3.2.1.1 Limite asymptotique de l'estimateur du maximum de vraisemblance

Pour finir cette section, on va montrer que dans la limite \(n\) grand, résoudre le problème du maximum de vraisemblance revient a minimiser une certaine "distance" entre la distribution générée par le paramètre \(\hat{\theta}_{\infty}\) et la distribution cible. Pour cela on va d'abord introduire une notion de distance.

Définition 3.14. Divergence de Kullback-Leibler.
Soit \(P\) et \(>Q\) deux distributions de probabilité. La divergence de Kullback Leibler est définie par

  1. Dans le cas discret par:

    \begin{equation*} D_{KL}(P\mid\mid Q)=\sum_{i=1}P(i)\operatorname{log}\left(\frac{P(i)}{Q(i)}\right) \end{equation*}

  2. Dans le cas continu par:

    \begin{equation*} D_{KL}(P\mid\mid Q)=\int_{-\infty}^{\infty}p(x)\operatorname{log}\left(\frac{p(x)}{q(x)}\right)dx \end{equation*}

On appelle la divergence KL aussi l'entropie relative entre les deux distributions.

La divergence KL n'est pas une distance au sens de la théorie des espaces métriques, car elle est non symétrique.

Il s'agira une preuve très formelle, notamment sur le passage à la limite.

On considère l'estimateur du maximum de vraisemblance. Soit:

\begin{align*} \hat{\theta}_n \amp =\operatorname{argmax}_{\theta} \mathcal{L}_{log}(x_1,...x_n,\theta)\\ \amp =\operatorname{argmax}_{\theta} \sum_{i=1}^n log f_{\theta}(x_i)\\ \amp =\operatorname{argmax}_{\theta} \sum_{i=1}^n (log f_{\theta}(x_i) - log f_{\theta_{ref}}(x_i)) \\ \amp =\operatorname{argmax}_{\theta} \sum_{i=1}^n log\left(\frac{f_{\theta}(x_i)}{ f_{\theta_{ref}}(x_i)}\right) \\ \amp =\operatorname{argmin}_{\theta} \sum_{i=1}^n log\left(\frac{f_{\theta_{ref}}(x_i)}{f_{\theta}(x_i)}\right) \\ \amp =\operatorname{argmin}_{\theta} \frac{1}{n}\sum_{i=1}^n log\left(\frac{f_{\theta_{ref}}(x_i)}{f_{\theta}(x_i)}\right)\\ \amp =\operatorname{argmin}_{\theta} \frac{1}{n}\sum_{i=1}^n g_{\theta}(x_i) \end{align*}

avec \(g_{\theta}(x)=log \left(\frac{f_{\theta_{ref}}(x)}{f_{\theta}(x)}\right)\text{.}\) On utilise ici le passage à la limite entre l'espérance empirique d'une fonction de variable aléatoire. On obtient donc en passant à la limite que

\begin{equation*} \operatorname{lim}_{n\rightarrow \infty} \hat{\theta}_n= \operatorname{argmin}_{\theta}\mathbb{E}[g_{\theta}(x)] \end{equation*}

Ensuite, puisque \(x\) est distribué selon \(f_{\theta_ref}\) on a

\begin{equation*} \operatorname{argmin}_{\theta}\mathbb{E}[g_{\theta}(x)] = \operatorname{argmin}_{\theta} \int_x f_{\theta_{ref}}(x)g_{\theta}(x)dx \end{equation*}

ce qui donne par définition

\begin{equation*} \operatorname{argmin}_{\theta}\mathbb{E}[g_{\theta}(x)] = \operatorname{argmin}_{\theta} \int_x f_{\theta_{ref}}(x) log \left(\frac{f_{\theta_{ref}}(x)}{f_{\theta}(x)}\right) dx \end{equation*}

ce la revient à

\begin{equation*} \operatorname{lim}_{n\rightarrow \infty} \hat{\theta}_n = \operatorname{argmin}_{\theta} D_{KL}\left(f_{\theta_{ref}} \mid \mid f_{\theta}\right) \end{equation*}

Subsection 3.2.2 Régression linéaire probabiliste

On va maintenant introduire le problème de de régression. L'enjeu est de construire un modèle qualitatif à partir de données.

Définition 3.17. Problème de régression probabiliste.

On se donne un jeu de données \(\mathcal{X}=(x_1,....,x_n) \in \mathbb{R}^d\) et \(\mathcal{Y}=(y_1,....,y_n) \in \mathbb{R}\) des échantillons i.d.d de deux variables aléatoires continues \(X\) et \(Y\text{.}\) On suppose qu'il existe une loi de probabilité \(\mathbb{P}(Y\mid X)\text{.}\) La régression consiste a construire une loi paramètrique \(\mathbb{P}_{\theta}(Y\mid X)\) approchant (en un certain sens) \(\mathbb{P}(Y\mid X)\text{.}\)

On va introduire un premier modèle de loi de probabilité paramétrée \(\mathbb{P}_{\theta}(Y\mid X)\) le plus simple qu'on puisse imaginer et montrer comment le construire.

Définition 3.18. Modèle linéaire.

Le modèle linéaire consiste à se donner une loi de probabilité paramétrée pour le problème de régression Définition 3.17 de la forme:

\begin{equation} p_{\theta}(y \mid x)=\mathcal{N}(y \mid (\omega,x) + b,\sigma^2)\tag{3.7} \end{equation}

avec les paramètres \(\omega\in \mathbb{R}^d\text{,}\) \(b\in \mathbb{R}\) et \(\mathcal{N}\) une loi Gaussienne. \(\sigma \in \mathbb{R}\) est fixé et modélise l'incertitude sur les données.

Maintenant la question est de savoir comment construire le modèle \(p_{\theta}(y \mid x)\) à partir d'échantillon. La fonction de vraisemblance mesure a quel un point un échantillon vérifie une loi de probabilité. On voit donc qu'on veut donc construire les paramètres du modèle \(\theta=(\omega,b)\in \mathbb{R}^{d+1}\) de façon a maximiser la vraisemblance sur l'échantillon. On va donc construire le modèle avec l'estimateur du maximum de vraisemblance.

Afin de déterminer les paramètres \(\theta=(\omega,b)\) On va donc calculer l'estimateur du maximum de vraisemblance (3.4) pour le modèle linéaire (3.7). On introduit la vraisemblance associée:

\begin{equation*} \mathcal{L}(y_1,....y_n,\theta)=\Pi_{i=1}^n \mathcal{N}(y_i \mid (\omega,x_i) + b,\sigma^2) \end{equation*}

Pour maximiser cette fonction on va devoir calculer les dérivées. Pour simplifier le calcul, on propose de transformer les produits en somme en appliquant une fonction "log". Cette fonction étant croissante maximiser le log de la vraisemblance maximise aussi la vraisemblance.

En appliquant la fonction log, on obtient

\begin{equation*} \mathcal{L}_{log}(y_1,....y_n,\theta)=\sum_{i=1}^n \operatorname{ln} \mathcal{N}(y_i \mid (\omega,x_i) + b,\sigma^2) \end{equation*}

En utilisant le caractère Gaussien de notre loi paramétrée on obtient

\begin{equation} \mathcal{L}_{log}(y_1,....y_n,\theta)=- \frac{1}{2\sigma^2}\sum_{i=1}^n ((\omega,x_i) + b -y_i)^2 + \frac{N}{2} \operatorname{ln} (\sigma^{-2}) - \frac{N}{2} \operatorname{ln} (2\pi)\tag{3.11} \end{equation}

Maximiser la fonction (3.11) revient à minimiser la fonction

\begin{equation} \frac{1}{2\sigma^2}\sum_{i=1}^n ((\omega,x_i) + b -y_i)^2\tag{3.12} \end{equation}

puisque les autres termes de (3.11) ne dépendent pas de \(\omega\) et \(b\text{.}\) On voit donc maximiser la log vraisemblance ici revient a minimiser l'erreur au sens des moindres carrés et donc résoudre un problème du type (3.1).

Dans ce cas particulier

\begin{equation*} A_x=\begin{pmatrix} 1 \amp x_1 \\ 1 \amp x_2 \\ \vdots \amp \vdots\\ 1 \amp x_{n-1} \\ 1 \amp x_n\\ \end{pmatrix} \end{equation*}

un rapide calcul matriciel montre que

\begin{equation*} A_x^{t} A_x = \begin{pmatrix} n \amp \sum_{i=1}^n x_i \\ \sum_{i}^n x_i \amp \sum_{i}^n x_i^2\\ \end{pmatrix} \end{equation*}

et

\begin{equation*} A_x^t b_y= \begin{pmatrix}\sum_{i=1}^n y_i \\ \sum_{i}^n x_iy_i\\ \end{pmatrix} = n \begin{pmatrix}\bar{y} \\ \frac{1}{n}\sum_{i}^n x_iy_i\\ \end{pmatrix} \end{equation*}

Maintenant on inverse la matrice en utilisant la formule d'inversion d'une matrice \(2x2\text{.}\) Cette matrice est inversible si sont déterminant est donc nul, donc ici si

\begin{equation*} Det(A_x^{t} A_x)= n \sum_{i}^n x_i^2- \left(\sum_{i}^n x_i\right)^2 = n^2 (\frac{1}{n}\sum_{i}^n x_i^2 - \bar{x}^2) \end{equation*}

et l'inverse est donnée par

\begin{equation*} (A_x^{t} A_x)^{-1}= \frac{1}{n (\frac{1}{n}\sum_{i}^n x_i^2 - \bar{x})} \begin{pmatrix} \frac{1}{n}\sum_{i}^n x_i^2 \amp -\bar{x} \\ -\bar{x} \amp 1\\ \end{pmatrix} \end{equation*}

On remarque que

\begin{equation*} \frac{1}{n}\sum_{i=1}^nx_iy_i-\bar{x}\bar{y}=\frac{1}{n}\sum_{i=1}^n(x_i-\bar{x})\sum_{i=1}^n(y_i-\bar{y})=Cov(\mathcal{X},\mathcal{Y}) \end{equation*}

On applique la même formule pour \(\frac{1}{n}\sum_{i=1}^nx_i^2-\bar{x}^2\) et cela nous donne en calculant le produit matrice vecteur que

\begin{equation*} \omega= \frac{Cov(\mathcal{X},\mathcal{Y})}{Var{\mathcal{X}}} \end{equation*}

Pour \(b\) on obtient

\begin{equation*} b = \frac{\frac{\bar{y}}{n}\sum_{i=1}^n x_i^2-\frac{\bar{x}}{n}\sum_{i=1}^n x_iy_i}{Var(\mathcal{X})}= \frac{Var(\mathcal{X})\bar{y} + \bar{y}\bar{x}^2 -\frac{\bar{x}}{n}\sum_{i=1}^n x_iy_i}{Var(\mathcal{X})} \end{equation*}

donc

\begin{equation*} b= \bar{y}-\frac{Cov(\mathcal{X},\mathcal{Y})}{Var{\mathcal{X}}}\bar{x}=\bar{y}-\theta \bar{x} \end{equation*}

Le maximum de vraisemblance nous permet donc de donner un cadre à la construction de modèle paramétré inférant des données. On a vu que cela se ramenait a un problème de moindre carré que l'ont peut résoudre par la méthode de l'équation normale. Le cadre déterministe est contenu dans le cadre probabiliste et se récupère avec \(\sigma \lt \lt 1\text{.}\)

Subsubsection 3.2.2.1 Formulation duale de la régression

On repart de notre problème de régression (3.8) - (3.9). Comme ont le sait la solution est donné par l'équation normale

\begin{equation*} A^t A\theta= A^t b \end{equation*}

Supposons maintenant que notre matrice \(A^t A\) soit inversible. On peut donc écrire

\begin{equation*} \theta = (A^t A)^{-1}A^t b= (A^t A)(A^t A)^{-2}A^t b = A^t\theta \end{equation*}

avec \(\theta=A(A^t A)^{-2}A^t b\text{.}\) On voit donc qu'on peut toujours écrire le résultat de la régression sous la forme d'une combinaison linéaire des points d'échantillonnages:

\begin{equation} \theta =\sum_{i=1}^n \langle \alpha_i, x_i \rangle\tag{3.13} \end{equation}

avec

\begin{equation*} \alpha =A(A^t A)^{-2}A^t b =A (A^{-1} A^{-t}) (A^{-1} A^{-t}) A^t b = A^{-t} A^{-1} b= (A A^t)^{-1}b \end{equation*}

On rappelle que par définition de la régression linéaire on cherche une fonction \(f(x)=\langle \theta,x\rangle\text{.}\) En utilisant (3.13) et cette définition on obtiendra la prédiction du modèle à partir de \(\alpha\text{.}\) Cette formulation inverse une matrice carrée de taille \(n\) la ou la formulation primale inversait une matrice de taille \(d+1\text{.}\) Elle peut donc être intéressante en grande dimension.

La matrice \(K\) est une matrice de Gram. Il s'agit des matrices générées par des produits scalaires de données. Ce type matrice matrice est symétrique positive par construction. Elle est inversible si les vecteurs \((\tilde{x}_1,...,\tilde{x}_n)\) forme une famille libre. On voit que cette formulation duale utilise au maximum le produit scalaire dans \(\mathbb{R}^n\text{.}\) Les produits Cette formulation nous sera utile par la suite.

Subsection 3.2.3 Régression polynomiale

Le 1er choix pour traiter les problèmes non linéaires est d'utiliser une approximation polynomiale. En effet le théorème de Stone-Weierstrass nous dit que toute fonction continue définie sur un segment de \(\mathbb{R}\) peut être uniformément approchée par des polynômes. De la même façon les polynômes orthogonaux forment une base de l'espace des fonctions \(L^2\) ce qui assure une approximation des fonctions \(L^2\) par une suite de polynômes. On va introduire la méthode pour \(d=1\text{.}\)

Définition 3.22. Modèle Polynomial.

Le modèle polynomial consiste à se donner une loi de probabilité paramétrée pour le problème de régression Définition 3.17 de la forme:

\begin{equation} p_{\theta}(y \mid x)=\mathcal{N}(y \mid \sum_{i=0}^{k}\theta_i p(x^i),\sigma^2)\tag{3.15} \end{equation}

avec \(p_i(x)\) des polynômes, les paramètres \(\theta\in \mathbb{R}^{k}\) et \(\mathcal{N}\) une loi Gaussienne. \(\sigma \in \mathbb{R}\) est fixé et modélise l'incertitude sur les données.

On décide donc d'approcher la moyenne dans notre modèle par une somme de polynômes. On peut prendre une base de polynômes de degré croissant ou des polynômes de Lagrange.

Comme dans le cas linéaire, on peut montrer qu'appliquer une méthode de maximum de vraisemblance permet de se ramener un problème aux moindres carrés avec une matrice:

\begin{equation*} A_x=\begin{pmatrix} p_0(x_1) \amp p_1(x_1) \amp \cdots \amp p_k(x_1) \\ p_0(x_2) \amp p_1(x_2) \amp \cdots \amp p_k(x_2) \\ \vdots \amp \amp \amp \vdots\\ p_0(x_{n-1}) \amp p_1(x_{n-1}) \amp \cdots \amp p_k(x_{n-1}) \\ \\ p_0(x_n) \amp p_1(x_n) \amp \cdots \amp p_k(x_n) \end{pmatrix} \end{equation*}

Puisqu'on se ramène un problème aux moindres carrés, on peut le résoudre avec l'équation normale ou une autre méthode. La méthode peut s'étendre en dimension \(d>1\text{,}\) mais le nombre de coefficients explose avec la dimension. Si on prend la base canonique des polynômes, on se donne un degré maximal \(q\) par direction. Dans ce cas on va avoir \(n_c=(q+1)^d\) coefficients. Pour \(q=5\) et \(d=10\) on a déjà autour de 60 millions de coefficients. Ce type de régression est rarement utilisée en grande dimension.

Subsection 3.2.4 Classification

La régression logistique est une méthode (il y a en a beaucoup d'autres) pour résoudre le problème de classification (catégorisation) de données .

On part d'un jeux de données de \(\mathcal{X}=\left\{x_1,..x_n\right\}\) avec \(x\in \mathbb{R}^d\text{.}\) On suppose que ses données appartiennent à des classes ou catégories. On parle de classification supervisée binaire s’ il y a deux catégories. Exemple:

  • \(y\) correspond a une image qui est soit un chat \((y=1)\) soit non \((y=0)\)

  • \(y\) correspond a une radio qui indique soit une tumeur \((y=1)\) soit non \((y=0)\)

Dans le cas avec \(n_c\) catégories on obtient donc que les données cibles \(y\) appartiennent à l'ensemble discret \(\left\{1,2,...,n_c\right\}\text{.}\)

Subsubsection 3.2.4.1 Régression logistique

On se place dans le cadre \(n_c=2\text{.}\) La variable \(y\) peut donc prendre deux valeurs \(y \in \left\{0,1\right\}\text{.}\) Au nuage de points \(\mathcal{X}\) on associe un ensemble de labels \(\mathcal{Y}=(y_1,..y_n)\text{.}\)

Définition 3.23. Classification supervisée.

La classification supervisée revient à construire la loi conditionnelle de \(y\) sachant \(x\) sous la d'une loi de Bernoulli:

\begin{equation*} \mathbb{P}(y=1 \mid x)=p, \quad \mathbb{P}(y=0 \mid x)=1-p \end{equation*}
L'enjeu est donc de construire la probabilité \(p\) à partir de \(x\text{.}\) Pour modéliser cette probabilité on utilise la fonction dit sigmoïde qui permet de transformer une fonction en probabilité:

\begin{equation*} \mathbb{P}(y=1 \mid x)=\frac{e^{f(x)}}{1+e^{f(x)}}, \quad \mathbb{P}(y=0 \mid x)=\frac{1}{1+e^{f(x)}}. \end{equation*}

On remarque que:

  • \(\operatorname{lim} f(x)\rightarrow -\infty\) implique que \(\mathbb{P}(y=1 \mid x)\rightarrow 0\) donc \(y = 0\text{,}\)

  • \(\operatorname{lim} f(x)\rightarrow \infty\) implique que \(\mathbb{P}(y=1 \mid x)\rightarrow 1\) donc \(y = 1\text{,}\)

  • \(\operatorname{lim} f(x)\rightarrow 0\) implique que \(\mathbb{P}(y=1 \mid x)\rightarrow 0.5\) et dans ce cas il y a indécision.

Cela nous permet de définir le modèle \(logistique\text{.}\)

Définition 3.24. Modèle logistique.

Pour un problème de classification binaire, le >modèle logistique consiste à approcher les probabilités conditionnelles par

\begin{equation} \mathbb{P}_{\theta}(y=1 \mid x)=\frac{e^{\langle \omega,x\rangle+b}}{1+e^{\langle\omega,x\rangle +b}}, \quad \mathbb{P}_{\theta}(y=0 \mid x)=\frac{1}{1+e^{\langle\omega,x\rangle+b}}\tag{3.16} \end{equation}
Le modèle logistique consiste donc a faire une approximation linéaire puis à la transformer en probabilité par une fonction sigmoïde. Cette approximation linéaire revient chercher un hyperplan séparant les données au sens ou les probabilités d'appartenir à telle ou telle classe seront de plus en plus grandes plus la donnée sera distante de l'hyperplan. Exemple de séparation sur la figure .........fig.......

Maintenant que le modèle est introduit, on doit mettre en place la stratégie d'apprentissage. Pour cela on doit d'abord construire une fonction coût. On doit faire coller le modèle aux données. Pour cela un outil naturel est l'estimateur du maximum de vraisemblance qui permet d'ajuster un modèle à partir des données. On rappelle la vraisemblance de notre problème:

\begin{equation*} \mathcal{L}(\mathcal{X},\theta)=\Pi_{i=1}^n \mathbb{P}_{\theta}(y= y_i \mid x_i) \end{equation*}

En utilisant les propriétés de la loi de Bernoulli, cette vraisemblance peut se réécrire:

\begin{equation*} \mathcal{L}(\mathcal{X},\theta)=\Pi_{i=1}^n \mathbb{P}_{\theta}(y=1\mid x_i)^{y_i}(1-\mathbb{P}_{\theta}(y=0\mid x_i))^{1-y_i} \end{equation*}

En général on ne souhaite pas maximiser la vraisemblance à cause du produit de probabilité, on préfère maximiser le log de cette vraisemblance. On prend donc le log:

\begin{equation*} \operatorname{log}\mathcal{L}(\mathcal{X},\theta)= \sum_{i=1}^n y_i \operatorname{log}(\mathbb{P}_{\theta}(y=1\mid x_i)) +(1-y_i) \operatorname{log}(\mathbb{P}_{\theta}(y=0\mid x_i)) \end{equation*}

En général on préfère un problème a minimiser.

Définition 3.25. Fonction coût entropie croisée binaire.

Pour un problème de classification binaire, on utilise une fonction coût appelée entropie croisée:

\begin{equation} \mathcal{L}(\theta)=-\sum_{i=1}^n y_i \operatorname{log}(\mathbb{P}_{\theta}(y=1\mid x_i)) +(1-y_i) \operatorname{log}(\mathbb{P}_{\theta}(y=0\mid x_i)) \tag{3.17} \end{equation}
Définition 3.26. Régression logistique.

On appelle la régression logistique la méthode qui utilise le modèle logistique (3.16) en minimiser la fonction de coût entropie croisée binaire (3.17).

Maintenant on va montrer qu'on peut calculer explicitement le gradient de la fonction coût ce qui permettra d'utilise une méthode d'optimisation.

On commence par réécrire la fonction coût:

\begin{align*} \mathcal{L}(\theta)\amp =-\sum_{i=1}^n y_i \operatorname{log}(\mathbb{P}_{\theta}(y=1\mid x_i)) +(1-y_i) \operatorname{log}(\mathbb{P}_{\theta}(y=0\mid x_i)) \\ \amp =-\sum_{i=1}^n y_i \operatorname{log}(\mathbb{P}_{\theta}(y=1\mid x_i)) - y_i \operatorname{log}(\mathbb{P}_{\theta}(y=0\mid x_i)) +\operatorname{log}(\mathbb{P}_{\theta}(y=0\mid x_i)) \\ \amp =-\sum_{i=1}^n y_i \operatorname{log}\left(\frac{\mathbb{P}_{\theta}(y=1\mid x_i)}{\mathbb{P}_{\theta}(y=0\mid x_i)}\right) +\operatorname{log}(\mathbb{P}_{\theta}(y=0\mid x_i)) \\ \amp =-\sum_{i=1}^n y_i \operatorname{log}\left(e^{\langle\omega,x_i\rangle+b}\right) +\operatorname{log}(\frac{1}{1+e^{\langle\omega,x_i\rangle+b}})\\ \amp =-\sum_{i=1}^n y_i \operatorname{log}\left(e^{\langle\omega,x_i\rangle+b}\right) +\operatorname{log}(1)- \operatorname{log}(1+e^{\langle\omega,x_i\rangle+b})\\ \amp =-\sum_{i=1}^n \left(y_i \left(\langle\omega,x_i\rangle+b\right) - \operatorname{log}(1+e^{\langle\omega,x_i\rangle+b})\right) \end{align*}

Maintenant on calcul le gradient avec des formules de dérivées composées et on obtient le résultat.

On voit que la non-linéarité induite par la fonction sigmoïde ne permet par de résoudre l'équation \(\nabla_{\theta}\mathcal{L}(\theta)=0\) de façon analytique. Pour cette raison on utilise en général des méthodes de gradients pour trouver la solution de la régression logistique. On peut construire des résultats théoriques sur la régression logistique. Il existe des résultats théoriques sur la régression logistique qu'on ne détaillera pas ici.

Subsubsection 3.2.4.2 Régression logistique polytomique

On cherche maintenant a étudier le cas \(n_c>2\text{.}\) La variable \(y\) peut donc prendre deux valeurs \(y \in \left\{0,n_c\right\}\text{.}\) Au nuage de points \(\mathcal{X}\) on associe un ensemble de label \(\mathcal{Y}=(y_1,..y_n)\text{.}\) De la même façon que précédemment on cherche a construire des probabilités conditionnelles qui prennent cette fois-ci la forme:

\begin{equation*} \mathbb{P}(y=k \mid x), \quad \forall k\leq n_c \end{equation*}

Ici on va construire un modèle de régression capable de traiter directement le cas multi classe. La méthode de la régression logistique partait d'un modèle dit logistique qui prenait une transformation affine des données avant de les transformer en probabilité à l'aide de la fonction sigmoïde. Ici on va faire la même chose, mais on doit générer une loi de probabilité prenant possiblement \(n_c\) valeur et non deux. On ne donc donc pas construire un seuil \(p\text{,}\) mais \(n_c-1\) seuils donc \(n_c\) probabilités qui seront approchées de façon affine.

Définition 3.28. Modèle Softmax.

Pour un problème de classification polytomique, le modèle consiste à approcher les probabilités conditionnelles par

\begin{equation} \mathbb{P}_{\theta}(y=k \mid x)=\frac{e^{\langle \omega_k,x\rangle +b_k}}{\sum_{l=1}^{n_c}e^{\langle \omega_l,x\rangle +b_l}}\tag{3.18} \end{equation}

On voit que toutes les probabilités sont positives et leurs sommes fait \(1\text{.}\) On a donc une loi de probabilité discrète.

De façon similaire au cas binaire, on va aussi pour construire le modèle maximiser la vraisemblance. Pour cela on introduit

\begin{equation*} \mathcal{L}(\mathcal{X},\theta)=\prod_{i=1}^n \mathbb{P}_{\theta}(y= y_i \mid x_i) \end{equation*}

On voit qu'on peut réécrire cette vraisemblance à l'aide de fonction indicatrice:

\begin{equation*} \mathcal{L}(\mathcal{X},\theta)=\prod_{i=1}^n \prod_{k=1}^{n_c}\mathbb{P}_{\theta}(y=k\mid x_i)^{\mathbb{1}_{\left\{y_i=k\right\}}} \end{equation*}

De façon similaire au cas binaire, on souhaite (pour le calcul du gradient de la vraisemblance) utiliser le logarithme afin de passer de produit à des sommes. On prend donc le log:

\begin{equation*} \operatorname{log}\mathcal{L}(\mathcal{X},\theta)= \sum_{i=1}^n \sum_{k=1}^{n_c}\mathbb{1}_{\left\{y_i=k\right\}}\mathbb{P}_{\theta}(y=k\mid x_i) \end{equation*}

En général on préfère un problème a minimiser.

Définition 3.29. Fonction coût entropie croisée.

Pour un problème de classification polytomique, on utilise une fonction coût appelée entropie croisée:

\begin{equation} \mathcal{L}(\theta)= -\sum_{i=1}^n \sum_{k=1}^{n_c}\mathbb{1}_{\left\{y_i=k\right\}}\mathbb{P}_{\theta}(y=k\mid x_i)\tag{3.19} \end{equation}
Définition 3.30. Régression logistique polytomique.

On appelle la régression logistique la méthode qui utilise le modèle logistique (3.18) en minimiser la fonction de coût entropie croisée binaire (3.19).

On le réécrit parfois de façon vectoriel. On pose comme label un vecteur \(\hat{y}_i\) qui est un vecteur de taille \(n_c\) qui vaut zéros partout sauf sur la ligne \(k\) si \(x_i\) est de catégorie \(k\text{.}\) Dans ce cas la fonction coût s'ecrit:

\begin{equation*} \mathcal{L}(\theta)=-\sum_{i=1}^n \langle\hat{y}_i,\operatorname{softmax}(x_i)\rangle \end{equation*}

avec \(\operatorname{softmax}\) uen fonction vectorielle de taille \(n_c\) dont la ligne \(k\) vaut \(\displaystyle \frac{e^{\langle\omega_k,x\rangle+b_k}}{\sum_{l=1}^{n_c}e^{\langle\omega_l,x\rangle+b_l}}\text{.}\)

Figure 3.31. On donne un exemple de classfication obtenu par une régression logistique (haut) et par une régression (polytomique).

Subsection 3.2.5 Méthodes de gradient

Pour résoudre notre problème de régression pon peut résoudre l'équation normale Lemme 3.3. En grande dimension la matrice a inverser peut devenir grande et donc le processus peut devenir coûteux. Une autre solution est de résoudre le problème du type (3.1) avec des méthodes de gradients. Ces méthodes seront centrales pour des modèles plus compliqués qu'on abordera par la suite.

Subsubsection 3.2.5.1 Méthode de gradient classique

On va commencer par réintroduire l'approche classique de descente de gradient. Dans le cadre des méthodes d'apprentissage introduites précédemment on cherche a minimiser

\begin{equation} \underset{\theta\in \mathbb{R}^{n_{\theta}}}{\operatorname{min}} \mathcal{J}(\theta)\tag{3.20} \end{equation}

avec

\begin{equation*} \mathcal{J}(\theta) =\sum_{i=1}^N l(f_{\theta}(x_i),y_i) + \parallel \theta\parallel_p \end{equation*}
On ne va pas détailler les critères d'existence et d'unicité de la solution du problème de minimisation. On supposera qu'il existe un unique minimum en général caractérisé par \(\nabla_{\theta} \mathcal{J}(\theta)=0\text{.}\)

Le premier algorithme est appelé l'algorithme de gradient à pas fixe. On souhait donc résoudre

\begin{equation*} \nabla_{\theta} \mathcal{J}(\theta)=0 \end{equation*}

Cela peut se réécrire:

\begin{equation*} \theta =\theta -\eta\nabla_{\theta} \mathcal{J}(\theta) \end{equation*}

avec \(\eta \gt 0\text{.}\) En posant \(g(.)=I_d-\eta\nabla_{\theta} \mathcal{J}(.)\) on voit qu'on se ramène a un problème de point fixe. Cela nous donne donc un algorithme immédiat.

On peut montrer assez facilement que sous des conditions assez restrictives cette méthode converge.

Définition 3.33. Convexité forte.

On dit qu'une fonction \(\mathcal{J}\text{,}\) définie sur un ensemble convexe \(K\text{,}\) est \(\alpha\)-convexe s'il existe \(a>0\) tel que, pour tout \(u, v \in K\) et tout \(t \in[0,1]\text{,}\)

\begin{equation*} \mathcal{J}(\theta \theta_1+(1-t) \theta_2) \leq t \mathcal{J}(\theta_1)+(1-t) \mathcal{J}(\theta_2)-\frac{\alpha t(1-t)}{2}\parallel \theta_1-\theta_2\parallel^2 . \end{equation*}

Cette condition revient a demander à une fonction d'être convexe aux moins aussi fortement qu'une fonction quadratique.

Maintenant, on donne le résultat de convergence de la méthode de gradient.

On commence par définir \(g(\theta)=\theta-\eta\nabla_{\theta} \mathcal{J}(\theta)\text{.}\) On va donc calculer

\begin{equation*} A=\parallel g(\theta_1)- g(\theta_2)\parallel_2^2. \end{equation*}
\begin{equation*} A =\parallel \theta_1 - \theta_2\parallel^2-2 \eta\left\langle \nabla_{\theta} \mathcal{J}(\theta_1)- \nabla_{\theta} \mathcal{J}(\theta_2),\theta_1-\theta_2\right\rangle +\eta^2\parallel \nabla_{\theta} \mathcal{J}(\theta_1)-\nabla_{\theta} \mathcal{J}(\theta_2)\parallel^2 \end{equation*}

Maintenant on va utiliser la \(\alpha\)-convexité et plus précisément la proposition Proposition 3.34 qui nous permet de majorer le terme. Le troisième terme est majoré en utilisant le côté Lipschitzien du gradient. Cela permet d'obtenir:

\begin{equation*} A \lt \left(1-2\alpha\eta +L^2\eta^2\right)\parallel \theta_1 - \theta_2\parallel^2 \end{equation*}

et on conclue en remarquant que si \(0\lt \eta \lt 2 \frac{\alpha}{L^2}\) alors \(\left(1-2\alpha\eta +L^2\eta^2\right)\lt 1\) l'application \(g\) est contractante et donc par le théorème de point on a convergence vers

\begin{equation*} \theta^*=g(\theta^*) \end{equation*}

ce qui est équivalent à \(\nabla_{\theta} \mathcal{J}(\theta^*)\text{.}\)

Il existe un certain nombre de variantes de la méthode. On peut citer le gradient à pas optimal qui calcul un pas \(\alpha\) de façon assurer la descente de gradient. On peut aussi citer le gradient conjugué qui prend comme direction de descente une moyenne du gradient et la direction de descente précédente.

Nous avons construit la méthode de descente de gradient par un argument de point fixe. On peut aussi utiliser une autre construction, basée sur les EDO, qui est parfois utilisée pour analyser les méthodes d'optimisation pour l'apprentissage. On pose l'équation:

\begin{equation} \frac{d \theta(t)}{dt} =-\nabla_{\theta} f(\theta(t))\tag{3.21} \end{equation}

Ce type d'EDO est appelé un un flot de gradient. On écrit donc la dynamique des poids de notre modèle d'apprentissage comme une dynamique en temps. L En multipliant cette équation par \(\nabla_{\theta} f(\theta(t))\) on obtient que

\begin{equation} \frac{d f(\theta(t))}{dt}=\nabla_{\theta} f(\theta(t)) \frac{d \theta(t)}{dt} =-\parallel\nabla_{\theta} f(\theta(t))\parallel^2\le 0\tag{3.22} \end{equation}

ce qui montre bien que \(f(\theta(t))\) (qui correspond à l'erreur de notre modèle) diminue en temps. Les états stationnaires du système sont caractérisés par \(\frac{d \theta(t)}{dt}\) et donc \(\nabla_{\theta} f(\theta(t))\text{.}\) On voit donc résoudre notre problème de minimisation revient a chercher un état stationnaire de notre EDO. Si on discrétise cette EDO avec un schéma d'Euler on obtient

\begin{equation*} \theta_{k+1}=\theta_k - \Delta t\nabla_{\theta} f(\theta_k) \end{equation*}

On voit donc que la méthode de descente de gradient s'écrit comme un schéma d'Euler pour un flot de gradients avec \(\alpha=\Delta t \text{.}\) Sous cette forme l'EDO (3.21) peut modéliser la trajectoire d'un point le long d'un potentiel (ou d'une bille le long d'un "paysage"). La fonction \(f(\theta(t))\) est une fonction de Lyapunov du système.

Subsubsection 3.2.5.2 Méthode de gradient stochastique

La méthode de gradient stochastique est une variante de la méthode de gradient qui est absolument central pour les problèmes d'apprentissage. Pour ce genre de problème on peut souvent écrire la fonction a minimiser sous la forme d'une somme de fonction de coût:

\begin{equation*} \mathcal{J}(\theta)=\frac{1}{N}\sum_{i=1}^N j_i(\theta) \end{equation*}

Par exemple dans le cas d'une régression on a \(j_i(\theta)=l(f_{\theta}(x_i),y_i)\text{.}\) Si on applique la méthode de gradient classique avec un pas variable donné, on obtient l'algorithme:

\begin{equation*} \theta_{k+1}=\theta_k-\nabla_{\theta} \mathcal{J}(\theta_k)=\theta_k - \eta_k\frac{1}{N}\sum_{i=1}^N \nabla_{\theta} j_i(\theta) \end{equation*}

On voit donc que le calcul du gradient faire intervenir l'ensemble des loss j_i. En apprentissage \(N\) représente le nombre de données qui peut être grand. Le calcul du chaque gradient associé à l'erreur commise par le modèle pour chaque donnée peut donc devenir très lourd. Afin de limiter cela il a été proposé une alternative appelée gradient stochastique. L'idée est d'utiliser l'itéré suivant:

\begin{equation} \theta_{k+1}=\theta_k - \eta_k\nabla_{\theta} j_{i^r}(\theta)\tag{3.23} \end{equation}

avec \(i^r\) tiré aléatoirement dans \(\left\{1,...,N\right\}\text{.}\) On utilise donc le gradient sur une seule donnée à chaque itération. Évidemment il n’est pas immédiat que cette approche converge. On va montrer par la suite que si.

La preuve est issue du cours [1.19]. On commence par réécrire (3.23)

\begin{equation*} \theta_{k+1}-\theta^*=\theta_k-\theta^*-\eta^k \nabla_{\theta} j_{i^r}(\theta_k) \end{equation*}

dont on calcule la norme au carré

\begin{equation} \parallel \theta_{k+1}-\theta^*\parallel^2=\parallel \theta_{k}-\theta^*\parallel^2-2 \eta^k\langle \theta_k-\theta_*, \nabla_{\theta} j_{i^r}(\theta_k)\rangle+\left(\eta_k\right)^2 \parallel \nabla_{\theta} j_{i^r}^2(\theta_k)\parallel^2 .\tag{3.25} \end{equation}

On définit une loi uniforme discrète \(p_u\) qui tire au sort aléatoirement l'indice \(i_k\) parmi \(\left\{1,...,N\right\}\text{.}\) On remarque que l'espérance selon \(p_u\) est donnée

\begin{equation*} \mathbb{E}_{p_u}\left[\nabla_{\theta} j_{i^r}(\theta) \right]=\sum_{i=1}^N \nabla_{\theta} j_{i^r=i}(\theta_k)\mathbb{P}(i_r=i)= \frac{1}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)=\nabla_{\theta} \mathcal{J}(\theta) \end{equation*}

On peut calculer l'espérence du carré de la même façon

\begin{equation*} \mathbb{E}_{p_u}\left[\nabla_{\theta} j_{i^r}(\theta)^2 \right]=\sum_{i=1}^n \nabla_{\theta} j_{i^r=i}(\theta_k)^2\mathbb{P}(i_r=i)= \frac{1}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)^2 \end{equation*}

On va maintenant prendre l'espérance de l'égalité (3.25) et en utilisant les deux identités introduites juste au dessus. On obtient:

\begin{equation*} \mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]=\parallel \theta_{k}-\theta^*\parallel^2-2 \eta^k\langle \theta_k-\theta_*, \nabla_{\theta} \mathcal{J}(\theta_k)\rangle+\left(\eta_k\right)^2 \mathbb{E}\left[\parallel \nabla_{\theta} j_{i^r}^2(\theta_k)\parallel^2\right] . \end{equation*}
\begin{equation*} \mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]=\parallel \theta_{k}-\theta^*\parallel^2-2 \eta^k\langle \theta_k-\theta_*, \mathbb{E}_{p_u}\left[\nabla_{\theta} j_{i^r}(\theta) \right]\rangle+\frac{\left(\eta_k\right)^2}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)^2 \end{equation*}

Maintenant on utilise la \(\alpha\) convexité de la fonction \(\mathcal{J}\text{,}\) on obtient:

\begin{equation} \mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]\le \left(1-2\eta_k\alpha \right)\parallel \theta_{k}-\theta^*\parallel^2 + \frac{\left(\eta_k\right)^2}{N} \sum_{i=1}^N \nabla_{\theta} j_{i}(\theta_k)^2\tag{3.26} \end{equation}

Pour finir on utilise l'hypothèse (3.24) on obtient:

\begin{equation} \mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]\le \left(1-2\eta_k\alpha+C\left(\eta_k\right)^2 \right)\parallel \theta_{k}-\theta^*\parallel^2 + C\left(\eta_k\right)^2\tag{3.27} \end{equation}

On pose le coefficient d'amplification

\begin{equation*} \beta_k = 1-2\eta_k\alpha+C\left(\eta_k\right)^2 \end{equation*}

qui est plus petit que strictement inférieur à un sous la condition sur \(\eta_k\) introduite dans la proposition. Par récurrence on a:

\begin{equation} \mathbb{E}\left[\parallel \theta_{k+1}-\theta^*\parallel^2\right]\le c_k\parallel \theta_{k}-\theta^*\parallel^2 + C c_k \sum_{i=1}^k \frac{(\eta_i)^2}{c_i} + C\left(\eta_k\right)^2\tag{3.28} \end{equation}

avec \(c_k=\Pi_{i=1}^N \beta_i\text{.}\) On va maintenant conclure à la convergence si \(0 \lt \alpha \lt \frac12\text{,}\) le choix \(\eta_k=\frac{1}{k+1}\) conduit à

\begin{equation*} \beta_k=1-\frac{2 \alpha}{k+1}+\mathcal{O}\left(k^{-2}\right), \quad c_k=O\left(k^{-2 \alpha}\right), \quad c_k \sum_{i=0}^k \frac{\left(\eta_i\right)^2}{c_i}=\mathcal{O}\left(k^{-2 \alpha}\right), \end{equation*}

Cela permet de conclure la preuve.

En pratique, on utilise une variante du gradient stochastique. En effet le gradient stochastique converge très lentement. Pour cela on utilie à la place le gradient stochastique par mini-batch. L'idée est d'utiliser pas l'ensemble des données pour calculer le gradient, mais un certains nombre tiré aléatoirement.

Figure 3.38. On affiche une descente de gradient pour le problème \(J(a,b)=\parallel y -(ax+b)\parallel_2^2\) sur 200 données. En haut on utilise un gradient complet (\(m=200\)). En bas un gradient stochastique avec \(m=1\text{.}\)