CS 229 - Machine Learning


Pense-bête d'apprentissage supervisé
Star

Par Afshine Amidi et Shervine Amidi

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 Discriminative model Generative model
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]$
Least squared error Logistic loss Hinge loss Cross entropy
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)}\]

Gradient descent

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}\]
SVM

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é.

SVM kernel

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.

k nearest neighbors

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)}\]
Union bound

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.

VC dimension

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)}\]