Pense-bête d'apprentissage supervisé
Star

Introduction à l'apprentissage supervisé

Étant donné un ensemble de points $\{x^{(1)}, ..., x^{(m)}\}$ associés à un ensemble d'issues $\{y^{(1)}, ..., y^{(m)}\}$, on veut construire un classifieur qui apprend à prédire $y$ depuis $x$.

Type de prédiction Les différents types de modèles prédictifs sont résumés dans le tableau ci-dessous :

	Régression	Classifieur
Issue	Continu	Classe
Exemples	Régression linéaire	Régression logistique, SVM, Naive Bayes

Type de modèle Les différents modèles sont présentés dans le tableau ci-dessous :

	Modèle discriminant	Modèle génératif
But	Estimer directement $P(y\|x)$	Estimer $P(x\|y)$ puis déduire $P(y\|x)$
Ce qui est appris	Frontière de décision	Distribution de probabilité des données
Illustration
Exemples	Régressions, SVMs	GDA, Naive Bayes

Notations et concepts généraux

Hypothèse Une hypothèse est notée $h_\theta$ et est le modèle que l'on choisit. Pour une entrée donnée $x^{(i)}$, la prédiction donnée par le modèle est $h_\theta(x^{(i)})$.

Fonction de loss Une fonction de loss est une fonction $L:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R}$ prenant comme entrée une valeur prédite $z$ correspondant à une valeur réelle $y$, et nous renseigne sur la ressemblance de ces deux valeurs. Les fonctions de loss courantes sont récapitulées dans le tableau ci-dessous :

Erreur des moindres carrés	Loss logistique	Hinge loss	Cross-entropie
$\displaystyle\frac{1}{2}(y-z)^2$	$\displaystyle\log(1+\exp(-yz))$	$\displaystyle\max(0,1-yz)$	$\displaystyle-\Big[y\log(z)+(1-y)\log(1-z)\Big]$

Régression linéaire	Régression logistique	SVM	Réseau de neurones

Fonction de coût La fonction de coût $J$ est communément utilisée pour évaluer la performance d'un modèle, et est définie avec la fonction de loss $L$ par :

\[\boxed{J(\theta)=\sum_{i=1}^mL(h_\theta(x^{(i)}), y^{(i)})}\]

Algorithme du gradient En notant $\alpha\in\mathbb{R}$ le taux d'apprentissage (en anglais learning rate), la règle de mise à jour de l'algorithme est exprimée en fonction du taux d'apprentissage et de la fonction de cost $J$ de la manière suivante :

\[\boxed{\theta\longleftarrow\theta-\alpha\nabla J(\theta)}\]

Remarque : L'algorithme du gradient stochastique (en anglais Stochastic Gradient Descent ou SGD) met à jour le paramètre à partir de chaque élément du jeu d'entrainement, tandis que l'algorithme du gradient de batch le fait sur chaque lot d'exemples.

Vraisemblance La vraisemblance d'un modèle $L(\theta)$ de paramètre $\theta$ est utilisée pour trouver le paramètre optimal $\theta$ par le biais du maximum de vraisemblance. En pratique, on utilise la log vraisemblance $\ell(\theta)=\log(L(\theta))$ qui est plus facile à optimiser. On a :

\[\boxed{\theta^{\textrm{opt}}=\underset{\theta}{\textrm{arg max }}L(\theta)}\]

Algorithme de Newton L'algorithme de Newton est une méthode numérique qui trouve $\theta$ tel que $\ell'(\theta)=0$. La règle de mise à jour est :

\[\boxed{\theta\leftarrow\theta-\frac{\ell'(\theta)}{\ell''(\theta)}}\]

Remarque : la généralisation multidimensionnelle, aussi connue sous le nom de la méthode de Newton-Raphson, a la règle de mise à jour suivante :

\[\theta\leftarrow\theta-\left(\nabla_\theta^2\ell(\theta)\right)^{-1}\nabla_\theta\ell(\theta)\]

Modèles linéaires

Régression linéaire

On suppose ici que $y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)$

Équations normales En notant $X$ la matrice de design, la valeur de $\theta$ qui minimise la fonction de coût a une solution de forme fermée tel que :

\[\boxed{\theta=(X^TX)^{-1}X^Ty}\]

Algorithme LMS En notant $\alpha$ le taux d'apprentissage, la règle de mise à jour d'algorithme des moindres carrés (LMS) pour un jeu de données d'entrainement de m points, aussi connu sous le nom de règle de Widrow-Hoff, est donné par :

\[\boxed{\forall j,\quad \theta_j \leftarrow \theta_j+\alpha\sum_{i=1}^m\left[y^{(i)}-h_\theta(x^{(i)})\right]x_j^{(i)}}\]

Remarque : la règle de mise à jour est un cas particulier de l'algorithme du gradient.

LWR Issue de l'anglais Locally Weighted Regression et souvent notée LWR, cette méthode est une variante de la régression linéaire appliquant un coefficient à chaque exemple dans sa fonction de coût via $w^{(i)}(x)$, qui est défini avec un paramètre $\tau\in\mathbb{R}$ de la manière suivante :

\[\boxed{w^{(i)}(x)=\exp\left(-\frac{(x^{(i)}-x)^2}{2\tau^2}\right)}\]

Classification et régression logistique

Sigmoïde La sigmoïde $g$, aussi connue sous le nom de fonction logistique, est définie par :

\[\forall z\in\mathbb{R},\quad\boxed{g(z)=\frac{1}{1+e^{-z}}\in]0,1[}\]

Régression logistique On suppose ici que $y|x;\theta\sim\textrm{Bernoulli}(\phi)$. On a la forme suivante :

\[\boxed{\phi=p(y=1|x;\theta)=\frac{1}{1+\exp(-\theta^Tx)}=g(\theta^Tx)}\]

Remarque : il n'y a pas de solution fermée dans le cas de la régression logistique.

Régression softmax Une régression softmax, aussi appelée un régression logistique multi-classe, est utilisée pour généraliser la régression logistique lorsqu'il y a plus de 2 classes à prédire. Par convention, on fixe $\theta_K=0$, ce qui oblige le paramètre de Bernoulli $\phi_i$ de chaque classe $i$ à être égal à :

\[\boxed{\displaystyle\phi_i=\frac{\exp(\theta_i^Tx)}{\displaystyle\sum_{j=1}^K\exp(\theta_j^Tx)}}\]

Modèles linéaires généralisés

Famille exponentielle Une classe de distributions est issue de la famille exponentielle lorsqu'elle peut être écrite en termes d'un paramètre naturel, aussi appelé paramètre canonique ou fonction de lien $\eta$, d'une statistique suffisante $T(y)$ et d'une fonction de log-partition $a(\eta)$ de la manière suivante :

\[\boxed{p(y;\eta)=b(y)\exp(\eta T(y)-a(\eta))}\]

Remarque : on aura souvent $T(y)=y$. Aussi, $\exp(-a(\eta))$ peut être vu comme un paramètre de normalisation s'assurant que les probabilités somment à un.

Les distributions exponentielles les plus communément rencontrées sont récapitulées dans le tableau ci-dessous :

Distribution	$\eta$	$T(y)$	$a(\eta)$	$b(y)$
Bernoulli	$\log\left(\frac{\phi}{1-\phi}\right)$	$y$	$\log(1+\exp(\eta))$	$1$
Gaussien	$\mu$	$y$	$\frac{\eta^2}{2}$	$\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)$
Poisson	$\log(\lambda)$	$y$	$e^{\eta}$	$\displaystyle\frac{1}{y!}$
Geometrique	$\log(1-\phi)$	$y$	$\log\left(\frac{e^\eta}{1-e^\eta}\right)$	$1$

Hypothèses pour les GLMs Les modèles linéaires généralisés (en anglais Generalized Linear Models ou GLM) ont pour but de prédire une variable aléatoire $y$ comme une fonction de $x\in\mathbb{R}^{n+1}$ et reposent sur les 3 hypothèses suivantes :

$(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}$

$(2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}$

$(3)\quad\boxed{\eta=\theta^Tx}$

Remarque : la méthode des moindres carrés ordinaires et la régression logistique sont des cas spéciaux des modèles linéaires généralisés.

Support Vector Machines

Le but des support vector machines est de trouver la ligne qui maximise la distance minimum des points à cette même ligne.

Classifieur à marges optimales Le classifieur à marges optimales $h$ est tel que :

\[\boxed{h(x)=\textrm{sign}(w^Tx-b)}\]

où $(w, b)\in\mathbb{R}^n\times\mathbb{R}$ est une solution du problème d'optimisation suivant :

\[\boxed{\min\frac{1}{2}||w||^2}\quad\quad\textrm{tel que }\quad \boxed{y^{(i)}(w^Tx^{(i)}-b)\geqslant1}\]

Remarque : la ligne est définie par $\boxed{w^Tx-b=0}$.

Hinge loss Le hinge loss est utilisé dans le cadre des SVMs et est défini de la manière suivante :

\[\boxed{L(z,y)=[1-yz]_+=\max(0,1-yz)}\]

Noyau Étant donné un feature mapping $\phi$, on définit le noyau (en anglais kernel) $K$ par :

\[\boxed{K(x,z)=\phi(x)^T\phi(z)}\]

En pratique, le noyau $K$ défini par $K(x,z)=\exp\left(-\frac{||x-z||^2}{2\sigma^2}\right)$ est nommé noyau gaussien et est communément utilisé.

Remarque : on dit que l'on utilise "l'astuce du noyau" (en anglais kernel trick) pour calculer la fonction de coût en utilisant le noyau parce qu'il se trouve que l'on n'a pas besoin de trouver le mapping explicite, qui est souvent compliqué. Il suffit de connaître les valeurs de $K(x,z)$.

Lagrangien On définit le lagrangien $\mathcal{L}(w,b)$ par :

\[\boxed{\mathcal{L}(w,b)=f(w)+\sum_{i=1}^l\beta_ih_i(w)}\]

Remarque : les coefficients $\beta_i$ sont appelés les multiplicateurs de Lagrange.

Apprentissage génératif

Un modèle génératif essaie d'abord d'apprendre comment les données sont générées en estimant $P(x|y)$, nous permettant ensuite d'estimer $P(y|x)$ par le biais du théorème de Bayes.

Gaussian Discriminant Analysis

Cadre Le Gaussian Discriminant Analysis suppose que $y$ et $x|y=0$ et $x|y=1$ sont tels que :

$(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}$

$(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}$

$(3)\quad\boxed{x|y=1\sim\mathcal{N}(\mu_1,\Sigma)}$

Estimation Le tableau suivant récapitule les estimations que l'on a trouvées lors de la maximisation de la vraisemblance :

$\widehat{\phi}$	$\widehat{\mu_j}\quad{\small(j=0,1)}$	$\widehat{\Sigma}$
$\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}}$	$\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}}$	$\displaystyle\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

Naive Bayes

Hypothèse Le modèle de Naive Bayes suppose que les caractéristiques de chaque point sont toutes indépendantes :

\[\boxed{P(x|y)=P(x_1,x_2,...|y)=P(x_1|y)P(x_2|y)...=\prod_{i=1}^nP(x_i|y)}\]

Solutions Maximiser la log vraisemblance donne les solutions suivantes, où $k\in\{0,1\},l\in[\![1,L]\!]$

\[\boxed{P(y=k)=\frac{1}{m}\times\#\{j|y^{(j)}=k\}}\quad\textrm{ et }\quad\boxed{P(x_i=l|y=k)=\frac{\#\{j|y^{(j)}=k\textrm{ et }x_i^{(j)}=l\}}{\#\{j|y^{(j)}=k\}}}\]

Remarque : Naive Bayes est couramment utilisé pour la classification de texte et pour la détection de spams.

Méthode à base d'arbres et d'ensembles

Ces méthodes peuvent être utilisées pour des problèmes de régression et de classification.

CART Les arbres de classification et de régression (en anglais CART - Classification And Regression Trees), aussi connus sous le nom d'arbres de décision, peuvent être représentés sous la forme d'arbres binaires. Ils ont l'avantage d'être très interprétables.

Random forest C'est une technique à base d'arbres qui utilise un très grand nombre d'arbres de décisions construits à partir d'ensembles de caractéristiques aléatoirement sélectionnés. Contrairement à un simple arbre de décision, il n'est pas interprétable du tout mais le fait qu'il ait une bonne performance en fait un algorithme populaire.

Remarque : les random forests sont un type de méthode ensembliste.

Boosting L'idée des méthodes de boosting est de combiner plusieurs modèles faibles pour former un modèle meilleur. Les principales méthodes de boosting sont récapitulées dans le tableau ci-dessous :

Boosting adaptif	Boosting par gradient
• Connu sous le nom d'Adaboost • De grands coefficients sont mis sur les erreurs pour s'améliorer à la prochaine étape de boosting	• Les modèles faibles sont entrainés sur les erreurs résiduelles

Autres approches non-paramétriques

$k$-nearest neighbors L'algorithme des $k$ plus proches voisins (en anglais $k$-nearest neighbors), aussi connu sous le nom de $k$-NN, est une approche non-paramétrique où la réponse d'un point est déterminée par la nature de ses $k$ voisins du jeu de données d'entrainement. Il peut être utilisé dans des cadres de classification et de régression.

Remarque : Plus le paramètre $k$ est élevé, plus le biais est élevé, et plus le paramètre $k$ est faible, plus la variance est élevée.

Théorie d'apprentissage

Inégalité de Boole Soit $A_1, ..., A_k$ $k$ évènements. On a :

\[\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}\]

Inégalité d'Hoeffding Soit $Z_1, .., Z_m$ $m$ variables iid tirées d'une distribution de Bernoulli de paramètre $\phi$. Soit $\widehat{\phi}$ leur moyenne empirique et $\gamma>0$ fixé. On a :

\[\boxed{P(|\phi-\widehat{\phi}|>\gamma)\leqslant2\exp(-2\gamma^2m)}\]

Remarque : cette inégalité est aussi connue sous le nom de borne de Chernoff.

Erreur de training Pour un classifieur donné $h$, on définit l'erreur d'entrainement $\widehat{\epsilon}(h)$, aussi connu sous le nom de risque empirique ou d'erreur empirique, par :

\[\boxed{\widehat{\epsilon}(h)=\frac{1}{m}\sum_{i=1}^m1_{\{h(x^{(i)})\neq y^{(i)}\}}}\]

Probablement Approximativement Correct (PAC) PAC est un cadre dans lequel de nombreux résultats d'apprentissages ont été prouvés, et contient l'ensemble d'hypothèses suivant :
- les jeux d'entrainement et de test suivent la même distribution
- les exemples du jeu d'entrainement sont tirés indépendamment

Éclatement Étant donné un ensemble $S=\{x^{(1)},...,x^{(d)}\}$, et un ensemble de classifieurs $\mathcal{H}$, on dit que $\mathcal{H}$ brise $S$ si pour tout ensemble de labels $\{y^{(1)}, ..., y^{(d)}\}$, on a :

\[\boxed{\exists h\in\mathcal{H}, \quad \forall i\in[\![1,d]\!],\quad h(x^{(i)})=y^{(i)}}\]

Théorème de la borne supérieure Soit $\mathcal{H}$ une hypothèse finie de classe telle que $|\mathcal{H}|=k$, soit $\delta$, et soit $m$ la taille fixée d'un échantillon. Alors, avec une probabilité d'au moins $1-\delta$, on a :

\[\boxed{\epsilon(\widehat{h})\leqslant\left(\min_{h\in\mathcal{H}}\epsilon(h)\right)+2\sqrt{\frac{1}{2m}\log\left(\frac{2k}{\delta}\right)}}\]

Dimension VC La dimension de Vapnik-Chervonenkis (VC) d'une classe d'hypothèses de classes infinies donnée $\mathcal{H}$, que l'on note $\textrm{VC}(\mathcal{H})$, est la taille de l'ensemble le plus grand qui est brisé par $\mathcal{H}$.

Remarque : la dimension VC de ${\small\mathcal{H}=\{\textrm{set of linear classifiers in 2 dimensions}\}}$ est égale à 3.

Théorème (Vapnik) Soit $\mathcal{H}$ donné, avec $\textrm{VC}(\mathcal{H})=d$ avec $m$ le nombre d'exemples d'entrainement. Avec une probabilité d'au moins $1-\delta$, on a :

\[\boxed{\epsilon(\widehat{h})\leqslant \left(\min_{h\in\mathcal{H}}\epsilon(h)\right) + O\left(\sqrt{\frac{d}{m}\log\left(\frac{m}{d}\right)+\frac{1}{m}\log\left(\frac{1}{\delta}\right)}\right)}\]

Pense-bête d'apprentissage supervisé Star