Introduction

Dans cet article, nous allons premièrement considerer le cas d’un modèle linéaire avec une seule variable. Cependant, la formule sera ensuite généralisée. Le mot hyperplan sera utilisé pour désigner des plans ou des droites.

Afin d’illustrer le prolème, nous allons commencer par prendre un exemple:

La méthode des moindres carré est utilisée afin de déterminer le meilleur hyperplan (ligne ici) pour un ensemble de points. Afin de trouver cette ligne, nous cherchons à minimiser l’erreur (la distance entre la ligne et les points). Moins l’erreur est grande, plus le modèle est précis.

Si nous affichons l’erreur en fonction de la pente et de l’ordonnée à l’origine, nous obtenons une parabole. L’argmin de cette parabole est le meilleur paramètre pour notre modèle.

Optimisation unidimensionnelle (une seule variable)

Dans le cas d’une seule variable, la formule de l’erreur est :

$$ E(m, b) = \sum_{i=1}^{n} (y_i - (mx_i + b))^2 $$ Où $y_i$ est le $i$-ème point de l’ensemble de données, $m$ est la pente et $b$ est l’ordonnée à l’origine. Si nous affichons l’erreur en fonction de $m$ et $b$ avec les données précédentes :

Visuellement, on peut voir que le minimum semble être :

• $b = 3$
• $m = 2$

Trouver la meilleur ligne revient à résoudre un problème d’optimisation. Trouver cette ligne revient à trouver le minimum de cette surface.

Nous voulons trouver le minimum de la fonction $E(b,m)$.

La solution analytique de ce problème (avec une seule variable) est : $$ argmin_{b, m} E(b, m) = argmin_{b, m} \sum_{i=1}^n (y_i - (b + m x_i))^2 $$

La solution analytique est donc :

• $m = \frac{\sum_{i=1}^n (x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=1}^n (x_i - \bar{x})^2}$
• $b = \bar{y} - m \bar{x}$

où $\bar{x}$ et $\bar{y}$ sont les moyennes des valeurs de $x$ et $y$ respectivement. La preuve n’est pas laissé comme exercice. Vous pouvez la trouver ici.

Cependant, que se passe-t-il si nous avons plusieurs variables ?

Optimisation avec plusieurs variables

Nous n’avons maintenant plus une ligne $y = ax + b$ mais un hyperplan $y = a_1 x_1 + a_2 x_2 + … + a_n x_n + b$ à trouver.

Nous pouvons commencer par réécrire l’équation $y$ sous la forme d’une multiplication matricielle : $y = Ax$ où $A$ est une matrice et $x$ un vecteur. $A$ est une matrice contenant tout les $a_i$ et une colonne supplémentaire contenant des $1$ (afin de pouvoir calculer $b$).

Cela implique maintenant que nous devons trouver la solution la plus proche du système :

$$\begin{cases} y_1 = a_{1,1}x_1 + a_{1,2}x_2 + \ldots + a_{1,n}x_n + x_0 \\ y_2 = a_{2,1}x_1 + a_{2,2}x_2 + \ldots + a_{2,n}x_n + x_0 \\ \ldots \\ y_n = a_{n,1}x_1 + a_{n,2}x_2 + \ldots + a_{n,n}x_n + x_0 \\ \end{cases} $$

Juste pour avoir un exemple rapide, si vous avez les points $(1, 1)$ et $(2, 2)$, la matrice $A$ sera : $A = \begin{pmatrix} 1 & 1 & 1 \\ 2 & 2 & 1 \end{pmatrix}$ and your vector $X$ will be : $X = \begin{pmatrix} a_1 \\ a_2 \\ a_0 \end{pmatrix}$. Nous devons trouver le vecteur $X$ qui minimise la fonction $E(X)$.

Si les points sont alignés, il est tout à fait possible d’utiliser une méthode telle que le pivot de Gauss pour trouver le vecteur $X$ (résultant d’une erreur de $0$). Cependant, dans tous les autres cas, nous devons le meilleur $X$ minimisant $E(X)$.

Minimiser cette erreur est équivalent à trouver le minimum de la surface. Comme pour le cas d’une equation simple, pour trouver le minimum d’une courbe, nous devons calculer la dérivée de la fonction et trouver les points où la dérivée est nulle. Nous pouvons faire la même chose ici.

$$ x_{opt} = argmin_{x} E(x) = argmin_x\nabla_x E(x)$$

Nous pouvons la réécrire :

$$ x_{opt} = argmin_x \sum_{i=1}^n (A_i x - y_i)^2 $$

$$ x_{opt} = argmin_x ||Ax - y||^2_2 $$

La notation $||x||_2$ est la norme euclidienne de $x$ (la longueur du vecteur de $x$). La notation $||x||_2^2$ est la norme au carré de $x$. Juste pour un exemple, si $x = \begin{pmatrix} 1 \ 2 \end{pmatrix}$, alors $||x||_2 = \sqrt{1^2 + 2^2} = \sqrt{5}$ and $||x||_2^2 = 1^2 + 2^2 = 5$.

Nous pouvons calculer la dérivée et essayer de résoudre l’équation :

$$ \nabla_x \frac{1}{2}||Ax - y||^2_2 = 0 $$

Ici 1/2 est juste une constante qui sera annulée par la résolution de l’équation. Nous pouvons donc l’ignorer car argmin est identique pour $f(x)$ et $\frac{1}{2}f(x)$.

$$ \frac{1}{2} \nabla_x ||Ax - y||^2_2 = 0 $$

Avec la règle de la chaîne (chain rule) :

$$ A^T \nabla_{Ax} ||Ax - y||^2_2 = 0 $$

Avec la formule de la norme : $\nabla_x ||x||^2_2 = 2x$

$$ A^T(Ax - y) = 0 $$

$$ A^TAx = A^Ty $$

$$ x = (A^TA)^{-1}A^Ty $$

$$ x_{opt} = (A^TA)^{-1}A^Ty $$

Nous avons maintenant la solution optimale pour chaque $x_i$.

Dans la section suivante, nous allons essayer d’appliquer cette formule sur un vrai jeu de données.

Exemple avec Python

Pour illustrer la méthode, commençons par générer un jeu de donnéees.

import numpy as np

Génération de données

Il y a évidemment plusieurs façons de générer des données. Pour cet exemple :

x = np.linspace(0, 10, 100)
y = 2*x + 3 + np.random.normal(0, 1, 100)

Comme prévu, nous pouvons appercevoir une relation linéaire entre $x$ et $y$.

Solution

La première étape est de créer une matrice A. La première colonne de A sera le vecteur x, la seconde colonne sera le 1 vecteur.

Nous ajontons une colonne de 1 pour être capable de calculer l’ordonnée à l’origine (la valeur de b quand x = 0). La première colonne de $A$ sera utilisé pour calculer la pente de la droite (la valeur de $b$ quand $x = 1$). Si vous ne comprenez pas pourquoi, je vous propose de relire la première partie de l’article.

A = np.vstack([x, np.ones(len(x))]).T

Ensuite, nous utilisons la formule : $X = (A^T \cdot A)^{-1} \cdot A^T \cdot y$

X = np.dot((np.dot(np.linalg.inv(np.dot(A.T,A)),A.T)),y)
line = [X[0]*i + X[1] for i in x] # y = ax + b

Nous obtenons ici $b_0 = a = 2.0$ et $b_1 = b = 2.8$ !

Si nous affichons cette ligne avec les points, nous obtenons le même graphique que celui de la première partie de l’article.

On peut faire la même chose avec des dimensions plus élevées en prenant l’intersection de plusieurs hyperplans.