• 10 heures
  • Moyenne
Licence

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 02/08/2023

Trouvez une combinaison linéaire de variables qui approxime leurs étiquettes

Nous allons dans ce cours nous attaquer à des problèmes supervisés que nous allons résoudre à l'aide de modèles linéaires. Autrement dit, nous allons essayer d'approximer les étiquettes de nos données grâce à une combinaison linéaire des variables utilisées pour représenter lesdites données. Dans ce chapitre, nous allons travailler sur des problèmes de régression : nos étiquettes sont des nombres réels (et non pas des catégories).

Un exemple de problème que l'on pourrait chercher à résoudre ici est celui de prédire le nombre d'utilisateurs connectés sur OpenClassrooms (notre étiquette réelle) comme une combinaison linéaire de variables telle que l'heure et le jour de la semaine, à partir des données de l'année passée (nos observations étiquetées).

Prenons des données, $\(n\)$ points en $\(p\)$ dimensions, représentés par la matrice $\(X \in \mathbb{R}^{n \times p}\)$ , avec leurs étiquettes à valeurs réelles, représentées  par un vecteur $\(y \in \mathbb{R}^n\)$.

Le but de la régression linéaire est de trouver une fonction linéaire $\(f: \mathbb{R}^{p} \rightarrow \mathbb{R}\)$ qui permette de prédire l'étiquette $\(y^{(i)}\)$ du i-ème point à partir du vecteur  $\(x^{(i)}\)$. Autrement dit,  $\(f(x)\)$ peut s'écrire sous la forme  $\(\beta_0 + \beta_1 x_1 + \beta_2 x_2 + \dots + \beta_p x_p.\)$ 

Comment trouver les valeurs des coefficients  $\(\beta_0, \beta_1, \dots, \beta_p\)$ ?

Maximisation de la vraisemblance

Nous allons pour ce faire nous placer dans un contexte bayésien. Tout de suite les grands mots ! En fait, cela veut dire que nous allons réfléchir en termes de probabilités et chercher les valeurs de $\( \beta_0, \beta_1, \dots, \beta_p \)$ pour lesquelles il est le plus vraisemblable d'observer les données $\(\{X, y\}\)$ qui nous sont données.

Nous allons commencer par supposer que les vecteurs $\(x^{(i)}\)$ sont les réalisations d'une variable aléatoire $\(p\)$-dimensionnelle $\(x\)$ et que les nombres réels $\(y^{(i)}\)$ sont les réalisations d'une variable aléatoire $\(y\)$ .

Pour cela, nous allons avoir besoin de poser quelques hypothèses :

- la première, l'hypothèse de linéarité, est que nous pouvons approximer, pour chacun des points de notre jeu de données, son étiquette par une combinaison linéaire de la valeur des variables qui le décrivent : $\(y^{(i)} = \beta_0 + \sum_{j=1}^p \beta_j x_j^{(i)} + \epsilon_i.\)$ Le terme de bruit  $\(\epsilon_i\)$ représente la différence entre la combinaison linéaire des variables et la vraie étiquette.

- la deuxième, l'hypothèse de normalité, est que le bruit est gaussien, ou normalement distribué : les ϵi sont la réalisation d'une variable aléatoire gaussienne, centrée en 0 et d'écart-type σ:  $\(\epsilon \sim \mathcal{N}(0, \sigma^2).\)$ 

- la troisième, l'hypothèse d'indépendance, est que les n couples $\((x^{(i)}, y^{(i)})\)$ sont des réalisations indépendantes les unes des autres des variables x et y.

Appelons $\( \beta \)$ le vecteur de dimensions (p+1) $\(\beta = (\beta_0, \beta_1, \dots, \beta_p)\)$ . Ce vecteur paramétrise notre modèle : une fois que nous avons trouvé la valeur de $\(\beta\)$ , notre modèle est entièrement spécifié et nous pouvons l'utiliser pour faire des prédictions.

 Selon nos hypothèses, la probabilité de $\(y\)$ étant donné $\(x\)$ et $\(\beta\)$ : $\(p(y|x, \beta) \)$ suit une distribution normale, centrée en notre prédiction, $\(\beta_0 + \sum_{j=1}^p \beta_j x_j\)$ et d'écart-type $\(\sigma\)$.

L'erreur entre la prédiction et la vraie valeur de l'étiquette vient d'une distribution gaussienne.
L'erreur entre la prédiction et la vraie valeur de l'étiquette vient d'une distribution gaussienne (ici avec une seule variable).

Vraisemblance

La vraisemblance, que nous allons noter  $\(\ell\)$ (pour son nom anglais, « likelihood »), c'est la probabilité d'observer nos n observations étant donné  $\(\beta.\)$

Grâce à l'hypothèse d'indépendance, nous pouvons dire que cette probabilité est le produit des probabilités d'observer chacune des observations :

$\[\ell = \prod_{i=1}^n p(x^{(i)}, y^{(i)}|\beta)\]$

Par définition de la probabilité conditionnelle,

$\[p(x^{(i)}, y^{(i)}|\beta) = p(y^{(i)}|x^{(i)}, \beta)p(x^{(i)})\]$

 Nous cherchons donc à trouver  $\(\beta\)$ qui maximise cette quantité. Comme  $\(p(x^{(i)})\)$ ne dépend pas de $\(\beta\)$, on peut l'ignorer et nous cherchons donc à résoudre le problème suivant :

$\[\arg \max {\beta \in \mathbb{R}^{p+1}} \prod_{i=1}^n p(y^{(i)}|x^{(i)}, \beta)\]$

Pour simplifier les calculs, nous allons maximiser non la vraisemblance, mais son logarithme : comme le logarithme est une fonction monotone strictement croissante, les deux sont équivalents. Nous cherchons donc à maximiser le log de vraisemblance, à savoir

$\[\mathcal{L} = \sum_{i=1}^n \log p(y^{(i)}|x^{(i)}, \beta).\]$

En anglais, on appelle ça « log-likelihood maximisation ».

Grâce à nos hypothèses, nous connaissons la forme de $\(p(y^{(i)}|x^{(i)}, \beta)\)$ : une gaussienne, centrée en la prédiction et d'écart-type $\(\sigma\)$ . Nous pouvons donc écrire

 

Nous pouvons prendre le log de cette expression, et trouver le maximum du log de vraisemblance est donc équivalent à

 

En éliminant de cette équation les termes qui ne dépendent pas de $\(\beta\)$ , nous trouvons que maximiser le log de la vraisemblance est équivalent à résoudre

 

Méthode des moindres carrés

Regardons de plus près le résultat auquel nous sommes arrivés : nous cherchons à minimiser la somme des carrés des différences entre chaque étiquette et sa valeur prédite... autrement dit, maximiser la vraisemblance est équivalent à minimiser la somme des carrés des erreurs !

Cette façon de trouver les coefficients d'une régression linéaire s'appelle la méthode des moindres carrés et est connue depuis Gauss et Legendre, qui faisaient donc déjà du machine learning au début du XIXème siècle 😉

 Mais comment résout-on ce problème en pratique ? Pour cela, nous allons passer à une écriture sous forme matricielle. Nous allons commencer par ajouter une colonne de 1 à la matrice de données X : désormais, j'appelle X $\(\in \mathbb{R}^{n \times (p+1)}\)$ qui a la forme suivante :

 Cela me permet d'écrire  $\(\beta_0 + \sum_{j=1}^p \beta_j x_j\)$ comme $\(\sum_{j=0}^p \beta_j x_j\)$ , et donc sous forme matricielle pour toutes les observations comme le produit $\(X \beta\)$ . Ainsi, minimiser la somme des carrés des erreurs est équivalent à

$\[\arg \min_{\beta \in \mathbb{R}^{p+1}} (y - X \beta)^\top (y - X \beta)\]$

Il s'agit désormais de minimiser une forme quadratique convexe, ce qui peut se faire en annulant son gradient en  $\(\beta\)$ :

$\[\nabla_\beta (y - X \beta)^\top (y - X \beta) = 0\]$

Le gradient d'une forme quadratique se calcule de manière analogue à la dérivée d'un polynôme de degré 2 :

$\[\nabla_\beta (y - X \beta)^\top (y - X \beta) = -2 X^\top (y - X \beta)\]$

Nous cherchons donc à trouver  $\(\beta\)$ tel que

$\[X^\top y - X^\top X \beta = 0\]$

 Si la matrice  $\(X^\top X\)$ est inversible, alors la solution s'écrit

$\[\beta = (X^\top X)^{-1} X^\top y\]$

 Sinon, la solution n'est pas unique, et il faudra utiliser à la place de  $\((X^\top X)^{-1}\)$ un pseudo-inverse de $\(X^\top X\)$ , à savoir une matrice  $\(A\)$ telle que $\(A (X^\top X) A = (X^\top X)\)$

que l'on peut trouver grâce à un algorithme de calcul de pseudo-inverse comme celui de Moore-Penrose.

Interprétation

Un des grands avantages de la régression linéaire est qu'elle produit un modèle interprétable, au sens où il nous permet de comprendre sur quoi se base la prédiction.

Plus précisément, si je rajoute une unité à la valeur de la variable $\(x_1\)$ , alors son étiquette augmente de $\(\beta_1\)$ . Plus  $\(|\beta_1|\)$ est grande, plus la variable  $\(x_1\)$ a un effet important sur la prédiction.

Conclusion

  • On apprend les coefficients d'une régression linéaire en maximisant le log de la vraisemblance, où, de manière équivalente si l'on suppose l'erreur normalement distribuée et centrée en zéro, en minimisant la somme des carrés des erreurs.

  • Cette méthode s'appelle la méthode des moindres carrés.

  • Si la matrice  $\(X^\top X\)$ est inversible, la régression linéaire admet une solution unique et explicite.

  • Sinon, on peut calculer une solution grâce à un algorithme de calcul de pseudo-inverse, mais cette solution n'est pas unique.

Dans scikit-learn, la régression linéaire est implémentée comme LinearRegression dans le module linear_model.

Exemple de certificat de réussite
Exemple de certificat de réussite