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)}\{x^{(1)}, ..., x^{(m)}\} associés à un ensemble d'issues {y(1),...,y(m)}\{y^{(1)}, ..., y^{(m)}\}, on veut construire un classifieur qui apprend à prédire yy depuis xx.

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(yx)P(y|x) Estimer P(xy)P(x|y) puis déduire P(yx)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θh_\theta et est le modèle que l'on choisit. Pour une entrée donnée x(i)x^{(i)}, la prédiction donnée par le modèle est hθ(x(i))h_\theta(x^{(i)}).


Fonction de loss Une fonction de loss est une fonction L:(z,y)R×YL(z,y)RL:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R} prenant comme entrée une valeur prédite zz correspondant à une valeur réelle yy, 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
12(yz)2\displaystyle\frac{1}{2}(y-z)^2 log(1+exp(yz))\displaystyle\log(1+\exp(-yz)) max(0,1yz)\displaystyle\max(0,1-yz)
[ylog(z)+(1y)log(1z)]\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 JJ est communément utilisée pour évaluer la performance d'un modèle, et est définie avec la fonction de loss LL par :

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

Algorithme du gradient En notant αR\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 JJ de la manière suivante :

θθαJ(θ)\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(θ)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 (θ)=log(L(θ))\ell(\theta)=\log(L(\theta)) qui est plus facile à optimiser. On a :

θopt=arg max θL(θ)\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 (θ)=0\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 :

θθ(θ2(θ))1θ(θ)\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 yx;θN(μ,σ2)y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)

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

θ=(XTX)1XTy\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 :

j,θjθj+αi=1m[y(i)hθ(x(i))]xj(i)\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)w^{(i)}(x), qui est défini avec un paramètre τR\tau\in\mathbb{R} de la manière suivante :

w(i)(x)=exp((x(i)x)22τ2)\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 gg, aussi connue sous le nom de fonction logistique, est définie par :

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

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

ϕ=p(y=1x;θ)=11+exp(θTx)=g(θTx)\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 θK=0\theta_K=0, ce qui oblige le paramètre de Bernoulli ϕi\phi_i de chaque classe ii à être égal à :

ϕi=exp(θiTx)j=1Kexp(θjTx)\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)T(y) et d'une fonction de log-partition a(η)a(\eta) de la manière suivante :

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

Remarque : on aura souvent T(y)=yT(y)=y. Aussi, exp(a(η))\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)T(y) a(η)a(\eta) b(y)b(y)
Bernoulli log(ϕ1ϕ)\log\left(\frac{\phi}{1-\phi}\right) yy log(1+exp(η))\log(1+\exp(\eta)) 11
Gaussien μ\mu yy η22\frac{\eta^2}{2} 12πexp(y22)\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)
Poisson log(λ)\log(\lambda) yy eηe^{\eta} 1y!\displaystyle\frac{1}{y!}
Geometrique log(1ϕ)\log(1-\phi) yy log(eη1eη)\log\left(\frac{e^\eta}{1-e^\eta}\right) 11

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 yy comme une fonction de xRn+1x\in\mathbb{R}^{n+1} et reposent sur les 3 hypothèses suivantes :

(1)yx;θExpFamily(η)(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}
(2)hθ(x)=E[yx;θ](2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}
(3)η=θTx(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 hh est tel que :

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

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

min12w2tel que y(i)(wTx(i)b)1\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 wTxb=0\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 :

L(z,y)=[1yz]+=max(0,1yz)\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) KK par :

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

En pratique, le noyau KK défini par K(x,z)=exp(xz22σ2)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)K(x,z).


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

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

Remarque : les coefficients βi\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(xy)P(x|y), nous permettant ensuite d'estimer P(yx)P(y|x) par le biais du théorème de Bayes.

Gaussian Discriminant Analysis

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

(1)yBernoulli(ϕ)(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}
(2)xy=0N(μ0,Σ)(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}
(3)xy=1N(μ1,Σ)(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} μj^(j=0,1)\widehat{\mu_j}\quad{\small(j=0,1)} Σ^\widehat{\Sigma}
1mi=1m1{y(i)=1}\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}} i=1m1{y(i)=j}x(i)i=1m1{y(i)=j}\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}} 1mi=1m(x(i)μy(i))(x(i)μy(i))T\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 :

P(xy)=P(x1,x2,...y)=P(x1y)P(x2y)...=i=1nP(xiy)\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{0,1},l[ ⁣[1,L] ⁣]k\in\{0,1\},l\in[\![1,L]\!]

P(y=k)=1m×#{jy(j)=k} et P(xi=ly=k)=#{jy(j)=k et xi(j)=l}#{jy(j)=k}\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

kk-nearest neighbors L'algorithme des kk plus proches voisins (en anglais kk-nearest neighbors), aussi connu sous le nom de kk-NN, est une approche non-paramétrique où la réponse d'un point est déterminée par la nature de ses kk 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 kk est élevé, plus le biais est élevé, et plus le paramètre kk est faible, plus la variance est élevée.

k nearest neighbors

Théorie d'apprentissage

Inégalité de Boole Soit A1,...,AkA_1, ..., A_k kk évènements. On a :

P(A1...Ak)P(A1)+...+P(Ak)\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}
Union bound

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

P(ϕϕ^>γ)2exp(2γ2m)\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é hh, on définit l'erreur d'entrainement ϵ^(h)\widehat{\epsilon}(h), aussi connu sous le nom de risque empirique ou d'erreur empirique, par :

ϵ^(h)=1mi=1m1{h(x(i))y(i)}\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)}S=\{x^{(1)},...,x^{(d)}\}, et un ensemble de classifieurs H\mathcal{H}, on dit que H\mathcal{H} brise SS si pour tout ensemble de labels {y(1),...,y(d)}\{y^{(1)}, ..., y^{(d)}\}, on a :

hH,i[ ⁣[1,d] ⁣],h(x(i))=y(i)\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 H\mathcal{H} une hypothèse finie de classe telle que H=k|\mathcal{H}|=k, soit δ\delta, et soit mm la taille fixée d'un échantillon. Alors, avec une probabilité d'au moins 1δ1-\delta, on a :

ϵ(h^)(minhHϵ(h))+212mlog(2kδ)\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 H\mathcal{H}, que l'on note VC(H)\textrm{VC}(\mathcal{H}), est la taille de l'ensemble le plus grand qui est brisé par H\mathcal{H}.

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

VC dimension

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

ϵ(h^)(minhHϵ(h))+O(dmlog(md)+1mlog(1δ))\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)}