Andrew Ng est professeur à l’université de Stanford et cofondateur de la plateforme de cours en ligne Coursera. Son cours - en Anglais - sur le Machine Learning (ou “apprentissage automatique” en bon français) est l’un des plus anciens et populaires de Coursera, et reste une référence dans le domaine. Je vais tenter d’en résumer ici les points les plus importants.

Introduction

Qu’est-ce que le Machine Learning ? De façon générale c’est la capacité d’un programme informatique à apprendre à résoudre un certain type de problème, et à s’améliorer avec l’expérience. Les algorithmes de Machine Learning se divisent en deux catégories: l’apprentissage supervisé (supervised learning) et l’apprentissage non supervisé (unsupervised learning).

L’apprentissage supervisé est utilisé lorsqu’on possède un jeu de données qui à un certain nombre de variables d’entrée (features) associe une ou plusieurs variables de sortie. Le but de l’algorithme dans ce cas est d’apprendre à prédire les valeurs des variables de sorties si on lui donne de nouvelles variables d’entrée qui n’étaient pas dans le jeu de données initial. On peut par exemple chercher à prédire le prix d’une maison (variable de sortie) étant donné sa superficie (variable d’entrée). Si la variable de sortie est continue (comme un prix), on parle d’algorithme de régression. Dans d’autres problèmes, la variable de sortie est discrète, c’est-à-dire ne peut prendre qu’un certain nombre fini de valeurs, on parle alors d’algorithme de classification. Par exemple reconnaître si une image représente un homme ou une femme est un problème de classification. On parle d’apprentissage “supervisé” car l’algorithme doit être entraîné avec un jeu de données de référence, préparé à l’avance.

L’apprentissage non supervisé est utilisé lorsqu’on cherche à structurer automatiquement un jeu de données, par exemple en regroupant automatiquement les éléments similaires (algorithme de clustering), ou au contraire en séparant des éléments qui ont été mélangés (par exemple en isolant des voix au milieu d’un bruit ambiant). Dans un problème d’apprentissage non supervisé, on dispose uniquement des variables d’entrées, et on laisse l’algorithme calculer lui-même la variable de sortie, alors même qu’on ne peut pas l’entraîner avec un jeu de données de référence.

La régression linéaire simple

La régression linéaire est la base de tous les algorithmes d’apprentissage supervisé. Dans sa version la plus simple, il n’y a qu’une seule variable d’entrée, notée \(x\), et une variable de sortie, notée \(y\). Si par exemple \(x\) représente la superficie d’une maison et \(y\) son prix, il nous faut un échantillon de données comportant des valeurs connues de \(x\) et \(y\), appelées observations:

x y
55 195000
110 305000
60 205000
75 280000
150 370000

Les observations sont numérotés de 1 à \(m\). Les variables de la 2ème observation, par exemple, sont notées \(x^{(2)}\) = 110 et \(y^{(2)}\) = 305000.

Le but est alors de répondre à la question: quelle est l’estimation de prix la plus probable pour une maison de 100 \(m^2\) (ou n’importe quelle autre valeur de \(x\)) ?

Dans le modèle de régression linéaire, on cherche à prédire la valeur de \(y\) sous la forme:

\[\hat{y} = h_\theta(x) = \theta_0 + \theta_1 x\]

Ici le \(y\) “chapeau” désigne la valeur prédite par le modèle, à la différence du \(y\) normal qui désigne la vraie valeur de la variable. La fonction \(h_{\theta}\) s’appelle la fonction de prédiction (ou d’hypothèse), et les valeurs \(\theta_0\) et \(\theta_1\) s’appellent les paramètres du modèle. On peut également considérer que le modèle a un seul paramètre \(\theta\), qui est un vecteur de composantes \((\theta_0, \theta_1)\).

L’apprentissage consiste ici à déterminer quelles sont les valeurs de \(\theta_0\) et \(\theta_1\) qui donnent la meilleure estimation de \(y\). Concrètement, si on représente chaque observation par un point de coordonnées (\(x, y)\) dans un plan, il s’agit de tracer une droite qui s’approche la plus possible de toutes les observations.

La fonction d’erreur

Pour préciser ce que signifie une “bonne estimation” de \(y\), on définit ce qu’on appelle une fonction d’erreur (cost function), qui mesure l’erreur entre les valeurs prédites par le modèle et les valeurs obervées. Dans la régression linéaire, on utilise la fonction d’erreur dite des moindres carrés, qui a la forme suivante:

\[J(\theta_0, \theta_1) = \frac{1}{2m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2\]

Cette fonction représente la sommme sur toutes les observations de la distance (au carré) entre la valeur observée de y et sa valeur prédite par le modèle. Comme le but est que l’erreur soit globalement la plus petite possible, le problème revient à minimiser la fonction d’erreur \(J\), c’est-à-dire à trouver le paramètre \(\theta\) pour lequel la valeur \(J(\theta_0, \theta_1)\) est minimale.

L’algorithme de descente du gradient

La méthode la plus simple pour minimiser la fonction d’erreur est l’algorithme de descente du gradient. Comme \(J\) est une fonction à 2 variables (\(\theta_0\) et \(\theta_1\)), on peut la représenter en 3 dimensions par une surface d’équation \(z = J(x, y)\). L’idée de la méthode de descente du gradient est que pour trouver le minimum de la fonction \(J\), c’est-à-dire le point le plus bas de la surface, il suffit de partir d’un point quelconque de cette surface et de la parcourir en prenant toujours la direction qui “descend” le plus rapidement possible, c’est-à-dire en avançant “face à la pente” de la surface (en réalité la méthode ne fonctionne à coup sûr que si la fonction n’a qu’un seul minimum local, ce qui est le cas de la fonction \(J\)). Mathématiquement, cette direction est donnée par le gradient de la fonction \(J\), qui est le vecteur dont les composantes sont les dérivées partielles de la fonction par rapport à chacune de ses variables:

\[\nabla J(\theta_0, \theta_1) = \begin{pmatrix}\frac{\partial}{\partial \theta_0}J(\theta_0, \theta_1) \\ \frac{\partial}{\partial \theta_1}J(\theta_0, \theta_1)\end{pmatrix}\]

L’algorithme consiste donc à choisir des valeurs initiales quelconques pour \(\theta_0\) et \(\theta_1\), et à ajuster ces paramètres de manière itérative en suivant la direction du gradient de \(J\). Concrètement, on applique à chaque itération la formule suivante:

\[\begin{cases} \theta_0 := \theta_0 - \alpha \frac{\partial}{\partial \theta_0}J(\theta_0, \theta_1) \\ \theta_1 := \theta_1 - \alpha \frac{\partial}{\partial \theta_1}J(\theta_0, \theta_1)\end{cases}\]

où \(\alpha\) est appelé le taux d’apprentissage. Il faut exécuter cette boucle jusqu’à la convergence de l’algorithme, c’est-à-dire jusqu’à ce que les paramètres \(\theta_i\) ne varient (presque) plus.

Dans le cas de la régression linéaire simple, la formule devient:

\[\begin{cases} \theta_0 := \theta_0 - \alpha \frac{1}{m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right) \\ \theta_1 := \theta_1 - \alpha \frac{1}{m}\sum_{i=1}^m\left((h_\theta(x^{(i)})-y^{(i)})x^{(i)}\right) \end{cases}\]

En examinant cette formule, on voit bien que l’on fait déjà du Machine Learning, et plus précisément de l’apprentissage supervisé, car le modèle apprend bien à minimiser sa fonction d’erreur grâce aux données \(x^{(i)}\) et \(y^{(i)}\) de l’échantillon de référence.

La régression linéaire multiple

Dans le cas général, la variable de sortie \(y\) dépend non pas d’une mais de \(n\) variables d’entrées, notées \(x_1, x_2, …, x_n\). Dans ce cas le modèle de régression linéaire devient:

\[\hat{y} = h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n\]

Pour simplifier les calculs, on va rajouter une variable d’entrée fictive \(x_0\) qui vaut toujours 1, ce qui permet de réécrire la fonction de prédiction \(h_\theta\) sous la forme:

\[h_\theta(x) = \sum_{j=0}^n \theta_j x_j\]

En considérant \(\theta\) et \(x\) comme des vecteurs (colonnes) de dimension n+1, on peut aussi écrire l’équation précédente sous forme matricielle:

\[h_\theta(x) = \theta^T x\]

Pour reprendre l’exemple de la prédiction du prix d’une maison, supposons que l’on dispose maintenant de 3 variables d’entrée \(x_1\) (superficie), \(x_2\) (nombre d’étages) et \(x_3\) (nombre de pièces), et des 5 observations suivantes:

\(x_1\) \(x_2\) \(x_3\) \(y\)
55 1 3 195000
110 2 4 305000
60 2 3 205000
75 1 4 280000
150 2 5 370000

Les variables de la 2ème observation sont maintenant notées \(x_1^{(2)} = 110\), \(x_2^{(2)} = 2\), \(x_3^{(2)} = 4\) et \(y^{(2)} = 305000\).

On peut aussi représenter l’ensemble des observations par une matrice \(X\) et un vecteur \(\vec{y}\), toujours avec la convention \(x_0^{(i)} = 1\):

\[X = \begin{pmatrix}1 & 55 & 1 & 3 \\ 1 & 110 & 2 & 4 \\ 1 & 60 & 2 & 3 \\ 1 & 75 & 1 & 4 \\ 1 & 50 & 2 & 5\end{pmatrix}, \vec{y} = \begin{pmatrix}195000 \\ 305000 \\ 205000 \\ 280000 \\ 370000\end{pmatrix}\]

Avec cette écriture matricielle, la fonction de prédiction devient:

\[h_\theta(X) = X\theta\]

La fonction d’erreur peut également s’écrire sous forme matricielle:

\[\begin{align}J(\theta) &= \frac{1}{2m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2 \\ &= \frac{1}{2m}(X\theta - \vec{y})^T(X\theta - \vec{y})\end{align}\]

On peut maintenant généraliser l’algorithme de descente du gradient à \(n\) variables. A chaque itération, on applique la formule:

\[\theta := \theta - \alpha \nabla J(\theta)\]

ce qui donne pour chaque composante:

\[\begin{align}\theta_j &:= \theta_j - \alpha \frac{\partial}{\partial \theta_j}J(\theta)\\ &:= \theta_j - \frac{\alpha}{m}\sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right) x_j^{(i)} \\ &:= \theta_j - \frac{\alpha}{m}\vec{x_j}^T(X\theta - \vec{y})\end{align}\]

et donc sous forme matricielle:

\[\boxed{\theta := \theta - \frac{\alpha}{m} X^T(X\theta - \vec{y})}\]

Choix des features

Pour que la méthode de descente du gradient fonctionne correctement en pratique, il est recommandé de mettre à l’échelle les features (variables d’entrée), c’est-à-dire de faire en sorte qu’elles prennent des valeurs comprises entre -1 et 1.

Malgré sa simplicité, la régression linéaire multiple permet en fait de définir n’importe quel modèle, et pas seulement un modèle linéaire. Imaginons qu’on veuille estimer le prix d’une maison par un modèle polynomial comme celui-ci:

\[\hat{y} = h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_1 x_2 + \theta_4 x_1^2 + \theta_5 x_2^2\]

Dans ce cas il suffit de définir trois nouvelles features: \(x_3 = x_1 x_2\), \(x_4 = x_1^2\) et \(x_5 = x_2^2\), et le problème se ramène simplement à une régression linéaire à cinq variables \(x_1, x_2, … x_5\)!

Equation normale

En plus de la méthode de descente du gradient, il existe aussi une méthode directe (analytique) pour minimiser la fonction d’erreur \(J(\theta)\) définie ci-dessus.

On peut montrer que la valeur de \(\theta\) qui minimise la fonction d’erreur est donnée par la formule suivante appelée équation normale:

\[\boxed{\theta = (X^T X)^{-1} X^T \vec{y}}\]

En pratique, l’équation normale n’est utilisable que si le nombre de features (\(n\)) n’est pas trop grand. Quand il y a plus de 10000 features, le calcul de la matrice \((X^T X)^{-1} X^T\) devient trop coûteux et il est nécessaire d’utiliser la méthode de descente du gradient.

Pour utiliser l’équation normale, il faut aussi que la matrice \(X^T X\) soit inversible, ce qui impose que les features soient linéairement indépendantes, et que le nombre d’observations \(m\) soit plus grand que le nombre de features \(n\).

Classification et régression logistique

Quand la variable à prédire n’est plus continue mais discrète, on parle d’un problème de classification. L’exemple le plus simple est la classification binaire, qui correspond au cas où \(y\) peut prendre les valeurs 0 ou 1.

La fonction de prédiction \(h_\theta(x)\) adaptée à la classification binaire est basée sur la fonction \(g\) suivante, qui est appelée sigmoïde ou fonction logistique:

\[\begin{align}h_\theta(x) = g(\theta^T x) \\ g(z) = \frac{1}{1 + e^{-z}}\end{align}\]

Concrètement, \(h_\theta(x)\) (compris entre 0 et 1) correspond à la probabilité que \(y\) prenne la valeur 1 pour une variable d’entrée donnée \(x\) (\(x\) étant ici un vecteur de \(n\) features).

Pour calculer le paramètre \(\theta\), on utilise la fonction d’erreur suivante:

\[\begin{align}& J(\theta) = \frac{1}{m}\sum_{i=1}^mC\left(h_\theta(x^{(i)}), y^{(i)}\right) \\ &C(h_\theta(x), y) = -y\ ln(h_\theta(x)) - (1 - y)\ ln(1 - h_\theta(x))\end{align}\]

La régression logistique consiste à trouver la valeur de \(\theta\) qui minimise cette fonction d’erreur.

Tout comme dans le cas de la régression linéaire, on peut utiliser la méthode de descente du gradient pour calculer \(\theta\), en appliquant la formule suivante à chaque itération:

\[\boxed{\theta := \theta - \frac{\alpha}{m} X^T(g(X\theta) - \vec{y})}\]

La régression logistique peut facilement se généraliser à plus de 2 classes. Il suffit de calculer pour chaque classe i une fonction de prédiction \(h_\theta^{(i)}(x)\), et pour chaque valeur de x choisir la classe i qui donne la plus grande valeur de \(h_\theta^{(i)}(x)\).

Surapprentissage et régularisation

Les deux problèmes classiques en machine learning sont le surapprentissage (overfitting) et le sous-apprentissage (underfitting). Le sous-apprentissage signifie que le modèle donne une mauvaise estimation quelque soit l’observation (on parle de biais élevé). A l’inverse le surapprentissage signifie que le modèle donne une erreur très faible sur les données d’apprentissage, mais par contre une erreur élevée sur des nouvelles données (on parle de variance élevée). Un bon modèle doit être ni trop simple ni trop compliqué, pour éviter à la fois le sous-apprentissage et le surapprentissage.

Le surapprentissage peut se produire quand il y a trop de features par rapport au nombre d’observations. La solution est alors de simplifier le modèle en réduisant le nombre de features, ou bien d’appliquer la méthode de régularisation, qui consiste à diminuer les valeurs des paramètres \(\theta_j\).

Le principe de la régularisation est de pénaliser les valeurs trop élevées des paramètres, en rajoutant le terme \(\lambda\sum\theta_j^2\) à la fonction d’erreur. Augmenter la valeur de \(\lambda\) permet de diminuer le surapprentissage, mais si \(\lambda\) est trop élevé on risque cette fois le sous-apprentissage.

Pour la régression linéaire, la fonction d’erreur devient:

\[J(\theta) = \frac{1}{2m}\left[ \sum_{i=1}^m\left(h_\theta(x^{(i)})-y^{(i)}\right)^2 + \lambda\sum_{j=1}^n\theta_j^2 \right]\]

et l’équation normale:

\[\theta = \left(X^T X+\lambda\left[ \begin{array}{cccccc}0 \\ & 1 \\ & & 1 \\ & & & ... \\ & & & & 1 \end{array} \right]\right)^{-1} X^T \vec{y}\]

Pour la régression logistique, la fonction d’erreur devient:

\[\begin{align}& J(\theta) = \frac{1}{m}\sum_{i=1}^mC\left(h_\theta(x^{(i)}), y^{(i)}\right) + \frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2\\ &C(h_\theta(x), y) = -y\ ln(h_\theta(x)) - (1 - y)\ ln(1 - h_\theta(x))\end{align}\]

A suivre…