REGRESSION LINEAIRE

I Intérêt de déterminer un modèle de données

I.1 Présentation
Lors d’une étude expérimentale, des points de mesures sont réalisés (en figure 1(a)). Afin de traiter
ces données, celles-ci sont alors souvent représentées graphiquement afin de mieux les visualiser.
Mesure en fonction du paramètre

Mesure en fonction du paramètre

• • • • • •
• • • •
• •
• •
• •

• •

Paramètre Paramètre
(a) Relevé de mesures (b) Modèle proposé à partir du relevé de mesures

Figure 1 – Exemple (fictif) de relevé de mesures

L’ingénieur (ou plus largement le scientifique) peut alors à partir de ces données tenter de définir
un modèle de comportement de ce qui a été observé (figure 1(b)). C’est-à-dire en déduire une équation
liant les paramètres expérimentaux et les mesures obtenues.
Cette démarche est une démarche tout à fait classique et que vous avez déjà probablement effectuée.
Le modèle que l’on vous demandait de trouver était généralement un modèle linéaire (la droite passant
au mieux par le relevé de points effectués). Cette approche déductive d’un modèle à partir d’expériences
est largement répandue dans le monde scientifique.
Un exemple très simple et qui est abordé au collège est d’effectuer un relevé de tension aux bornes
d’une résistance ainsi que l’intensité circulant dans le circuit électrique. Ce relevé de mesures de tension
et intensité permet de mettre en exergue la relation U = R.I.

I.2 Différents modèles possibles

La méthode permettant de déterminer une équation à partir d’un relevé de points n’est cependant
pas ”magique” et nécessite en fait de faire un choix sur le type de modèle que l’on va utiliser pour
déterminer la ”meilleure” équation représentative des données disponibles.
Exemple 1 : En reprenant les données de l’exemple de la figure 1(b), on propose deux modèles
d’interpolation/régression de données. On ne notera ces deux modèles f˜1 (x) et f˜2 (x)
— un modèle régressif de type exponentielle : f˜1 (x) = γ1 × (1 − eγ2 .x )
8
X
— un modèle interpolant de type polynomiale : f˜2 (x) = βi × xi
i=0
Après optimisation des paramètres γi et βi , le résultat obtenu est :
 f (x)

• • •
• •
•
• f˜2 (x)
• f˜1 (x)

Figure 2 – Deux modèles interpolant ou régressif de données

À partir de cet exemple, on en déduit rapidement que la qualité finale du modèle obtenue dépend
donc du choix initial de fonction f˜ fait. Clairement, sur cette figure, le modèle polynomial ne semble
pas adapté pour au moins une raison : lim f˜2 (x) = +∞ alors que les mesures semblent plutôt
x→+∞
converger vers une valeur limite.

Conclusion

La qualité du modèle représentatif de données obtenues par simulation numérique ou expérience

dépend donc d’un choix de l’utilisateur sur le type de fonction utilisée pour la régression. Cette
pratique nécessite donc un certain recul et expérience dans ce domaine pour faire des choix pertinents.

I.3 Critère d’optimisation des paramètres du modèle choisi

I.3.1 Définition de l’erreur quadratique moyenne

On dispose d’un ensemble de données X = {x1 , x2 , · · · , xp } avec xi ∈ Rn . xi peut donc être

considéré comme un vecteur de dimension n. On vérifie alors :

xi = [xi1 , xi2 , · · · xin ]

Pour les données de l’ensemble X , on dispose de leurs évaluations qui sont stockées dans l’ensemble
Y = {y1 , y2 , · · · , yp }. On vérifie yi ∈ R. (On peut généraliser à yi ∈ Rk ).
Dans ce cours, quel que soit le modèle utilisé pour établir une régression des données, on s’appuie
sur la minimisation de l’erreur quadratique moyenne. On dispose d’un modèle f˜ dont on cherche
à optimiser les paramètres param. (param est un vecteur des paramètres que l’on chercher à optimiser).
On pose alors :
ỹi = f˜(xi , param)
 L’erreur quadratique moyenne (mean square error en anglais) est donnée par :
p
1X
M SE(param) = k yi − ỹi k2
p
i=1
p
1 X
= k yi − f˜(xi , param) k2
p
i=1

I.3.2 Résolution du problème

Afin de trouver le vecteur param le plus adapté aux données X et leurs évaluation Y, il faut résoudre
le problème suivant :
p
!
1X
arg min k yi − f˜(xi , param) k2
param p
i=1

Résoudre ce problème revient à chercher la solution d’un problème de minimisation. On peut définir
différents types de minimum pour une fonction f quelconque (voir figure 3)

Figure 3 – Illustration de différents types de minima

Pour résoudre, ce problème de minimisation, on peut utiliser différents algorithmes. L’un des plus
simples à utiliser est l’algorithme de descente de gradient à pas constant.
 Algorithme 1 : Algorithme de descente de gradient à pas fixe
Initialisation;
Données : Une fonction f onc dont on cherche un minimum. Un point xinit ∈ Rn avec lequel
on initialise l’algorithme. α est un paramètre appelé le pas. α > 0. Un paramètre ε > 0 servant
de critère d’arrêt;
xsol ← xinit ;
tant que k ∇f onc(xsol ) k> ε faire
xsol ← xsol − α∇f onc(xsol ) ;
fin
return xsol
Il est tout à fait possible de résoudre directement ce problème en fonction du modèle f˜ notamment
lorsque le problème est linéaire en fonction des paramètres du vecteur param.

II La régression linéaire simple

II.1 Cas de la régression monovariable : f˜(x) = a.x
Soient X = {0, 1, 2} et Y = {1, 2.3, 3.9} avec X les paramètres évaluées et Y leurs évaluations. On
souhaite établir un modèle de régression du type f˜(x) = a.x à partir de ces données.

II.1.1 Résolution directe du problème

On écrit l’erreur quadratique moyenne de ce problème :

3
1X
M SE(a) = (yi − [Link] )2
3
i=1
(y1 − a.x1 )2 + (y2 − a.x2 )2 + (y3 − a.x3 )2
=
3
(1 − a × 0)2 + (2.3 − a × 1)2 + (3.9 − a × 2)2
=
3
5 × a2 − 20.2 × a + 21.5
M SE(a) =
3
De par sa définition, la quantité M SE est positive et il s’agit d’une fonction quadratique concave
(car le coefficient devant a2 est positif). De ce fait, résoudre le problème :

dM SE(a)
arg minM SE(a) ⇐⇒ =0
a da
Ainsi, sur notre exemple :

dM SE(a)
=0
da
10 × a − 20.2
⇐⇒ =0
3
⇐⇒ a = 2.02

Et en effet, lorsque l’on trace la fonction M SE(a) on constate que le minimum est effectivement
atteint autour de la valeur de paramètre a = 2
 M SE(a)

1
a
0 1 2 3 4

Figure 4 – MSE correspondant au problème traité

II.1.2 Résolution par algorithme de descente à pas fixe

On présente sur cet exemple assez simple, le principe de l’algorithme de descente à pas fixe pour
résoudre le problème. On illustre l’évolution de l’algorithme au cours des itérations. α = 0.1 dans ces
illustrations.

Figure 5 – Présentation de l’algorithme à descente de gradient

 dM SE
Sur les figures 5, on a initialisé l’algorithme avec une valeur a = 0. La valeur de (0),
da
c’est-à-dire la dérivée de M SE(a) au point a = 0, est de :

dM SE
(0) = −6.73
da
Ainsi, la valeur du paramètre a à la prochaine itération selon l’algorithme de descente du gradient à
pas constant sera :
a = 0 − 0.1 × (−6.73) = 0.673
On répète ensuite l’opération jusqu’à ce que l’on juge que la valeur de la dérivée soit suffisamment
petite pour supposer avoir atteint le minimum de la fonction.

II.2 Cas de la régression multivariable : f˜(x) = a.x + b

Clairement, par rapport à l’exemple qui vient d’être traité, on peut améliorer le modèle de régression
proposé en introduisant une ordonnée à l’origine : paramètre b. On considère ainsi le modèle de
régression suivant : f˜(x) = a.x + b

II.2.1 Résolution directe du problème

On écrit l’erreur quadratique moyenne de ce problème :

3
1X
M SE(a, b) = (yi − ([Link] + b))2
3
i=1
(y1 − a.x1 − b)2 + (y2 − a.x2 − b)2 + (y3 − a.x3 − b)2
=
3
(1 − a × 0 − b)2 + (2.3 − a × 1 − b)2 + (3.9 − a × 2 − b)2
=
3
5a2 + 3b2 + 6ab − 20.2 × a − 14.4 × b + 21.5
M SE(a, b) =
3
La fonction M SE(a, b) est représentée sur la figure 6 ci-dessous :

100
f (a, b)

4
0 2
−4 0
−2 0
2 −2
4 −4 b
a

Figure 6 – Fonction M SE(a, b)

 Remarque

Cette fonction admet un unique minimum sur R2 . Une façon simple de l’expliquer est de constater
que pour a fixé, la fonction M SE(b) est une fonction quadratique concave. Il en va de même pour b
fixé et la fonction M SE(a).
Les valeurs de a et b permettant de trouver le minimum de la fonction f sont les solutions du
système d’équation :  ∂M SE
 =0
∂a


 ∂M SE = 0

∂b
(
10a + 6b − 20.2 = 0
On aboutit alors au système : La solution de ce système d’équation est alors :
6b + 6a − 14.4 = 0
(
a = 1.45
b = 0.95

II.2.2 Approche matricielle de la résolution du problème

Ce que l’on constate sur ces deux exemples est qu’il est tout à fait possible de déterminer les
coefficients a et b. Cependant, s’il y a beaucoup de points, réaliser ce genre de calculs ”à la main”
devient vite assez long.

II.2.3 Approche numérique et mathématique pour déterminer les coefficients de régres-

sion

Pour illustrer l’approche qui va être mise en place, on poursuit avec le même exemple que précé-
demment. Pour rappel, X = {0, 1, 2} et Y = {1, 2.3, 3.9} avec X les paramètres évaluées et Y leurs
évaluations. On cherche à réaliser la régression de ces données grâce au modèle suivant :

f˜(x) = a × x + b

. On a donc a : 

 f˜(0) = b
f˜(1) = a + b
 f˜(2) = 2a + b


On peut écrire ce système sous une forme matricielle :

 
1 0 !
b
 1 1 ·
 
a
1 2

On peut donc écrire les quantités f˜(xi ) − yi sous la forme

   
1 0 ! y1
b
 1 1 · −  y2 
   
a
1 2 y3
    
1 0 ! y1
b
On pose A =  1 1 , B = et Y =  y2 . Le critère que l’on cherche à minimiser est
   
a
1 2 y3
3
1X
M SE(a, b) = ([Link] + b − yi )2 , c’est-à-dire que l’on cherche à minimiser la somme des compo-
3
i=1
santes au carré du vecteur A · B − Y.
Or « la somme des composantes au carré d’un vecteur » correspond à la norme au carré de ce même vecteur.
Le problème devient donc :

arg min kA · B − Yk2 ⇐⇒ arg min (A · B − Y)T (A · B − Y)

B B

Pour le résoudre, il faut dériver ce système matriciel par rapport à B.

Attention

La dérivation d’un vecteur dans un système matriciel se fait exactement comme pour la dérivée d’une
dA · X
grandeur scalaire. Par exemple =A
dX
On peut alors prouver (ce n’est pas au programme) :

d (A · B − Y)T (A · B − Y)
= 0 ⇐⇒ AT AB = AT Y
dB
On en déduit alors que

−1
B = AT A AT Y
.

Remarque

La résolution informatique d’un système matriciel est au programme en SI en 2ème année et s’appuie
sur la méthode du pivot de Gauss.

II.2.4 Résolution par algorithme de descente de gradient à pas fixe

Dans ce paragraphe, on va illustrer le fonctionnement de l’algorithme de descente de gradient à pas

fixe. On va expliquer comment on peut passer de l’étape d’initialisation (itération 0) avec des valeurs
initiales : a = 0 et b = 0 à l’itération 1. Le processus se poursuivant ensuite jusqu’à ce que la norme
du gradient soit jugée suffisamment petite pour supposer avoir trouvé le minimum. On utilise α = 0.3
À l’initialisation, on pose a = 0 et b = 0. Le gradient de M SE(0, 0) est alors donné par :
 ∂M SE 
(0, 0)
" #
∂a −6.7333
∇M SE(0, 0) =  =
 
∂M SE −4.7999
(0, 0)
∂b
Ainsi, pour l’itération 1, on utilise :

a = 0 − 0.3 × (−6.7333) = 2.0199

b = 0 − 0.3 × (−4.7999) = 1.4399

On réitère ensuite le processus, en recalculant le gradient ∇M SE(2.0199, 1.4399) etc.

Figure 7 – Présentation de l’algorithme à descente de gradient
III Régression linéaire multiple
III.1 Méthode de résolution directe
Nous venons de traiter des problèmes de régression pour modéliser un comportement/un problè-
me/une fonction ne dépendant que d’une variable (la variable x). Les paramètres a et b déterminés
précédemment ne sont que les paramètres du modèle de régression déterminé.
Nous allons dans cette section, nous intéresser au problème dépendant de plusieurs variables.
Le problème est le suivant : On dispose d’un ensemble de données X = {x1 , x2 , · · · , xp } avec
xi ∈ Rn . xi peut donc être considéré comme un vecteur de dimension n. On vérifie alors :

xi = [xi1 , xi2 , · · · xin ]

Pour cet ensemble de données X , on dispose de leurs évaluations qui sont stockées dans l’ensemble
Y = {y1 , y2 , · · · , yp }. On vérifie yi ∈ R.

Dans le cas de régression linéaire multiple, on cherche donc à établir un modèle

f˜(x, B) = β0 + β1 .x1 + β2 .x2 + · · · βn .xn avec x ∈ Rn et B = [β0 , β1 , · · · βn ]T ∈ Rn+1

L’erreur quadratique moyenne est donc définie par :

p
1X
M SE(B) = k yi − f˜(xi , B) k2
p
i=1

De nouveau, on
 peut représenter ce problème
 de
 manière
 matricielle.
 
1 x11 x12 · · · x1n β0 y1
 1 x21 x22 · · · x2n   β1   y2 
     
On pose A = 
 .. . . . . . . . . . , B =  ..  et Y =  .. 
..     
 . .   .   . 
1 xp 1 xp 2 · · · xp n βn yp
De ce fait :

p
1X
M SE(B) = k yi − f˜(xi , B) k2
p
i=1
1
= k A.B − Y k2
p
On se retrouve exactement dans la même situation que dans la section II.2.2. On cherche à résoudre
le problème :
arg min kA · B − Yk2 ⇐⇒ arg min (A · B − Y)T (A · B − Y)
B B

La solution de ce problème est (voir section II.2.2) :

−1
B = AT A AT Y
.
III.2 Complexité temporelle de la résolution directe

−1 T
On calcule B = AT A A Y. Ce calcul a une certaine complexité qui n’est pas négligeable. La
taille de la matrice A est p × (n + 1).
Xp
— On pose C = AT A avec ∀(i, j) ∈ J1 ; n + 1K2 Cij = ATik Akj . La complexité de ce calcul est
k=1
alors Θ (n + 1)2 × p

— On pose D = AT Y. De la même façon, on montre que la complexité de ce calcul est en Θ (p × n)

−1
— On montre que la résolution de ce système par la méthode de Gauss (calcul de AT A ) a une
complexité en Θ(n)3

Conclusion

Lorsque le problème de régression que l’on cherche à résoudre est constitué de p données en nombre
important et que la dimension du problème n est aussi importante, les différentes opérations matri-
cielles prennent un temps non négligeable. C’est pour cela qu’une approche itérative (comme celle
de l’algorithme à descente de gradient à pas fixe) est une solution. Il y a plusieurs variantes sur ce
genre d’algorithme (pas variable, pas adapté, etc...). Une autre méthode efficace sont les méthodes à
région de confiance.