Fondements du Machine Learning

Clément W. Royer

Notes de cours - L3 IM2D - 2024/2025

• La dernière version de ce document est accessible à l’adresse :
[Link]

• Pour toute remarque, envoyer un mail à [Link]@[Link].

Merci à Thibault De Surrel De Saint Julien pour sa relecture attentive.

• Historique des versions du document

– 2024.10.14 : Corrections mineures.

– 2024.10.12 : Ajout du chapitre 3.
– 2024.09.10 : Modifications de l’exemple d’illustration.
– 2024.09.09 : Ajout du chapitre 1.
– 2024.09.03 : Première version avec contenu du premier cours.

• Objectifs d’apprentissage
À l’issue de ce cours, l’étudiant(e) sera capable de

– Donner la formule de la décomposition en valeurs singulières, et appliquer cette décomposition

à des problèmes matriciels;
– Reconnaı̂tre et formuler des problèmes aux moindres carrés linéaires;
– Donner des solutions de ces problèmes et expliciter leur lien avec la décomposition en
valeurs singulières;
– Donner la définition d’une composante principale, et appliquer l’analyse en composantes
principales à des données matricielles.
Sommaire

0 Introduction 4
0.1 Derrière le Machine Learning... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2 Contexte et objectifs du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.3 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

I Réduction de dimension 7

1 Décomposition en valeurs singulières 8

1.1 Rappels d’algèbre linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Valeurs propres et décomposition spectrale . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Décomposition en valeurs singulières . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Principe de la décomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Décomposition tronquée et approximation . . . . . . . . . . . . . . . . . . . 13

2 Analyse en composantes principales 16

2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Statistique empirique et pré-traitement des données . . . . . . . . . . . . . . . . . . 16
2.2.1 Individu moyen et données centrées . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Dispersion et dépendance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Principe de l’analyse en composantes principales . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Analyse en une composante principale . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Analyse en plusieurs composantes principales . . . . . . . . . . . . . . . . . 20
2.3.3 Application : Reconnaissance de visage . . . . . . . . . . . . . . . . . . . . 23

II Régression linéaire 24

3 Premiers pas avec le modèle linéaire 25

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Résolution de systèmes non linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Cas d’un système carré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.2 Cas d’un système rectangulaire . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.3 Pseudo-inverse et SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Moindres carrés linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Solution au sens des moindres carrés . . . . . . . . . . . . . . . . . . . . . . 29

2
SOMMAIRE 3

3.3.2 Résolution du problème aux moindres carrés . . . . . . . . . . . . . . . . . . 31

3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Régression linéaire 32
Chapitre 0

Introduction

0.1 Derrière le Machine Learning...

Le terme machine learning, dont les traductions varient entre apprentissage machine, apprentissage
automatique et apprentissage artificiel, fait partie d’un ensemble de mots-clés qui ont récemment
gagné en popularité. Parmi ceux-ci, on trouve également l’analyse de données (data analysis), la
fouille de données (data mining ), l’intelligence artificielle (artificial intelligence, ou simplement AI ),
les masses de données (Big Data), etc. L’utilisation de cette terminologie est parfois hasardeuse :
on leur préfèrera donc la notion de sciences des données, ou data science.
La notion de donnée est en effet au coeur des différents concepts sus-mentionnés, et représente
un enjeu majeur dans de nombreux secteurs d’activités. Pour les entreprises de service telles que
les GAFAM 1 , il s’agit de fournir une valeur ajoutée dans leur service autrement gratuit via la
façon dont les données des utilisateurs sont exploitées. En recherche et développement, la quantité
massive de données générées dans certains domaines (biologie, médecine) pose d’importants défis
mathématiques et informatiques. Plus globalement, les approches guidées par les données (data-
driven) deviennent de plus en plus populaires, car elles permettent de pallier le manque de modèles
formels ou implémentables. C’est le cas par exemple pour la modélisation météorologique à grande
échelle : nos capacités de calcul ne nous permettent pas de faire évoluer un modèle de prédiction à
l’échelle du globe, mais il est possible de collecter un grand volume de données et d’en extraire les
tendances majeures.
Dans ce cours, on considèrera deux approches d’analyse de données. La première approche, dite
prédictive, ne pré-supposera pas de distribution sur les données, et visera à extraire de l’information
des données même (on parle ainsi d’apprentissage non supervisé). L’analyse en composantes prin-
cipales (ou ACP, voir Chapitre 2) sera ici l’outil-clé pour obtenir cette information. La seconde,
dite fonctionnelle, supposera que les données d’apprentissage suivent une distribution de probabilité
connue : il est ainsi possible de construire un modèle de ces données adapté à la distribution sous-
jacente. Les approches de régression linéaire seront utilisés dans ce contexte d’apprentissage (dit
supervisé).

1
Google, Apple, Facebook, Amazon et Microsoft.

4
0.2. CONTEXTE ET OBJECTIFS DU COURS 5

0.2 Contexte et objectifs du cours

Dans ce cours, on s’intéressera à développer des techniques visant à extraire de l’information d’un jeu
de données. On considèrera que l’on dispose d’une quantité importante de données, non seulement
pour qu’il soit intéressant d’en extraire de l’information, mais aussi pour que ces données puissent
représenter des tendances. Les techniques que nous emploierons reposent sur des algorithmes, c’est-
à-dire des traitements systématiques à appliquer aux données. Comme on le verra, le développement
d’un algorithme efficace repose à la fois sur des arguments mathématiques et sur une implémentation
bien pensée.
Ce cours se concentre plus spécifiquement sur l’obtention de modèles linéaires des relations
entre les données; ces données seront de plus vues comme des réalisations de variables aléatoires
(généralement gaussiennes). Ce choix se justifie par la pertinence et l’efficacité de ces modèles
simples dans la pratique. Il permet également d’utiliser des résultats et algorithmes issus de l’algèbre
linéaire, de l’optimisation et des statistiques.

0.3 Notations
Conventions de notation
• Les scalaires seront représentés par des lettres minuscules : a, b, c, α, β, γ.

• Les vecteurs seront représentés par des lettres minuscules en gras : a, b, c, α, β, γ.

• Les lettres majuscules en gras seront utilisées pour les matrices : A, B, C.

• En l’absence d’ambiguı̈té, on pourra omettre les indices de début et de fin dans une somme
finie afin d’alléger les notations. On pourra de même utiliserP unPseul symbole
P P de P notation
pour plusieurs indices et ainsi écrire de manière équivalente m
i=1
n
j=1 , i j ou i,j si le
contexte le permet.

Notations vectorielles
• On notera Rn l’ensemble des vecteurs à n composantes réelles, et on considèrera toujours que
n est un entier supérieur ou égal à 1.

• Un vecteur x ∈ Rn sera pensé (par convention) comme un vecteur colonne. On notera
 xi ∈ R
x1
n  .. 
sa i-ème coordonnée dans la base canonique de R . On aura ainsi x =  . , que l’on
xn
notera plus succinctement x = [xi ]1≤ı≤n .

• Étant donné un vecteur (colonne) x ∈ Rn , le vecteur ligne correspondant sera noté xT . On

aura donc xT = [x1 · · · xn ] et [xT ]T = x.

• Pour tout n ≥ 1, les vecteurs 0n et 1n représentent les vecteurs colonnes de Rn dont tous les
éléments sont égaux à 0 ou 1, respectivement.
6 CHAPITRE 0. INTRODUCTION

Notations matricielles
• On notera Rm×n l’ensemble des matrices à m lignes et n colonnes à coefficients réels, où m
et n seront des entiers supérieurs ou égaux à 1. Les espaces Rm×1 et Rm étant isomorphes
(ce que l’on note Rm×1 ≃ Rm ), on pourra considèrer un vecteur de Rm comme une matrice
de Rm×1 , et vice versa. Une matrice A ∈ Rn×n est dite carrée (dans le cas général, on parlera
de matrice rectangulaire).

• Étant donnée une matrice A ∈ Rn , on notera Aij le coefficient en ligne i et colonne j de la

matrice. La notation [Aij ]1≤i≤m sera donc équivalente à A. Sans ambigüité sur la taille de la
1≤j≤n
matrice, on notera simplement [Aij ].

• Selon les besoins, on utilisera aT

i pour la
i-ème ligne de A ou aj pour la j-ème colonne de A.
aT1
Selon le cas, on aura donc A =  ...  ou A = [a1 · · · an ] .
 

aTm

• Pour une matrice A = [Aij ] ∈ Rm×n , la matrice transposée de A, notée AT , est la matrice
de Rn×m telle que
∀i = 1 . . . m, ∀j = 1 . . . n, AT
ji = Aij .

Nota Bene : Cette notation généralise donc la correspondance entre vecteurs lignes et vecteurs
colonnes.

• Pour tout n ≥ 1, la matrice In représentera la matrice identité de Rn×n (avec des 1 sur la
diagonale et des 0 partout ailleurs), tandis que les matrices 0n et 1n représenteront les matrices
dont tous les éléments sont égaux à 0 ou 1, respectivement. De manière plus générale, les
notations 0m,n et 1m,n seront utilisées pour les matrices de Rm×n ne contenant respectivement
que des 0 et des 1.
 Partie I

Réduction de dimension

7
Chapitre 1

Décomposition en valeurs singulières

1.1 Rappels d’algèbre linéaire

On considèrera toujours l’espace des vecteurs Rn muni de sa structure d’espace vectoriel normé de
dimension n :

• Pour tous x, y ∈ Rn , la somme des vecteurs x et y est notée x + y = [xi + yi ]1≤i≤n ;

• Pour tout λ ∈ R, on définit λx := λ · x = [λxi ]1≤i≤n .

• La norme euclidienne ∥ · ∥ sur Rn est définie pour tout vecteur x ∈ Rn par

v
u n
uX
∥x∥ := t x2i .
i=1

On dira que x ∈ Rn est unitaire si ∥x∥ = 1.

• Pour tous vecteurs x, y ∈ Rn , le produit scalaire dérivé de la norme euclidienne est noté xT y,
et défini par
Xn
xT y := x i yi .
i=1

Il s’agit d’une forme bilinéaire symétrique définie positive. On a en particulier y T x = xT y.

• Il existe une P
famille libre et génératrice de Rn de taille n. Par exemple, tout vecteur x de Rn
s’écrit x = ni=1 xi ei , où ei = [0 · · · 0 1 0 · · · 0]T est le i-ème vecteur de la base canonique
(le coefficient 1 se trouvant en i-ème position).

Définition 1.1 (Sous-espace engendré) Soient x1 , . . . , xp p vecteurs de Rn . Le sous-espace en-

gendré par les vecteurs x1 , . . . , xp est le sous-espace vectoriel
p
( )
X
vect(x1 , . . . , xp ) := x = αi xi αi ∈ Rn ∀i .
i=1

Ce sous-espace est de dimension au plus min(n, p).

8
1.1. RAPPELS D’ALGÈBRE LINÉAIRE 9

Lorsque l’on travaille avec des matrices, on s’intéresse généralement aux sous-espaces définis
ci-dessous.

Définition 1.2 (Sous-espaces matriciels) Soit une matrice A ∈ Rm×n , on définit les deux sous-
espaces suivants :

• Le noyau (kernel/null space en anglais) de A est le sous-espace vectoriel

ker(A) := {x ∈ Rn | Ax = 0m }

• L’image (range space) de A est le sous-espace vectoriel

Im(A) := {y ∈ Rm | ∃x ∈ Rn , y = Ax}

La dimension de ce sous-espace vectoriel s’appelle le rang de A. On la note rang(A) et on a

rang(A) ≤ min{m, n}.

Théorème 1.1 (Théorème du rang) Pour toute matrice A ∈ Rm×n , on a

dim(ker(A)) + rang(A) = n.

Définition 1.3 (Normes matricielles) On définit sur Rm×n la norme d’opérateur ∥ · ∥ et la norme
de Frobenius ∥ · ∥F par
∥Ax∥


 ∥A∥ := maxx∈Rn ∥x∥ = max x∈Rn ∥Ax∥

 x̸=0n ∥x∥=1
m×n
∀A ∈ R , rP
 2
 ∥A∥F := 1≤i≤m Aij .


1≤j≤n

Nous terminons cette section par quelques définitions de sous-ensembles de matrices carrées qui
nous seront utiles dans le cours.

Définition 1.4 (Matrice symétrique) Une matrice carrée A ∈ Rn×n est dite symétrique si elle
vérifie AT = A.

Définition 1.5 (Matrice inversible) Une matrice carrée A ∈ Rn×n est dite inversible s’il existe
B ∈ Rn×n telle que BA = AB = I n (où l’on rappelle que I n désigne la matrice identité de
Rn×n ).
Si elle existe, une telle matrice B est unique : elle est appelée l’inverse de A et on la note A−1 .

Définition 1.6 (Matrice (semi-)définie positive) Une matrice carrée A ∈ Rn×n est dite semi-
définie positive si elle est symétrique et que

∀x ∈ Rn , xT Ax ≥ 0.

Elle est dite définie positive si elle est semi-définie positive et que xT Ax > 0 pour tout vecteur x
non nul.
10 CHAPITRE 1. DÉCOMPOSITION EN VALEURS SINGULIÈRES

Définition 1.7 (Matrice orthogonale) Une matrice carrée P ∈ Rn×n est dite orthogonale si P T =
P −1 .
Par extension, on dira que Q ∈ Rm×n avec m ≤ n est orthogonale si QQT = I m (les colonnes
de Q sont donc orthonormées dans Rm ).
Si Q ∈ Rn×n est une matrice orthogonale, alors QT est également orthogonale.
On utilisera fréquemment la propriété des matrices orthogonales énoncée ci-dessous.
Lemme 1.1 Soit une matrice A ∈ Rm×n et U ∈ Rm×m , V ∈ Rn×n des matrices orthogonales
(respectivement de Rm×m et Rn×n . On a
∥A∥ = ∥U A∥ = ∥AV ∥et∥A∥F = ∥U A∥F = ∥AV ∥F ,
c’est-à-dire que la multiplication par une matrice orthogonale ne modifie pas la norme d’opérateur.
Démonstration. On montre tout d’abord que pour tout vecteur x ∈ Rm , on a ∥U x∥ = ∥x∥.
En utilisant la définition de la norme et celle d’une matrice orthogonale, on a :
∥U x∥2 = xT U T U x = xT x = ∥x∥2 ,
ce qui établit le résultat. Par conséquent, on a également
∥U Ax∥ = ∥Ax∥
pour tout vecteur x. En revenant à la définition de la norme d’opérateur, on obtient ainsi
∥U A∥ = max ∥U Ax∥ = max ∥Ax∥ = ∥A∥,
∥x∥=1 ∥x∥=1

ce qui est bien le résultat recherché. Pour le résultat sur ∥AV ∥, on note que V T est une matrice
orthogonale inversible avec V V T = I n , donc que pour tout x, il existe z tel que x = V T z et
∥x∥ = ∥z∥ d’après ce qui précède. On a ainsi :
∥AV ∥ = max ∥AV x∥ = max ∥AV V T z∥
∥x∥=1 ∥V T z∥=1
= max ∥Az∥ = ∥A∥,
∥z∥=1

ce qu’il fallait démontrer.

On démontre maintenant
Pm Pn le résultat pour la norme de Frobenius, dont on rappelle qu’elle est
2
définie par ∥A∥F = i=1 j=1 Ai j . On a ainsi
p p
∥A∥F = ∥a1• ∥2 + · · · + ∥am• ∥2 = ∥a•1 ∥2 + · · · + ∥a•n ∥2
où a1• , . . . , am• et a•1 , . . . , a•n représentent les lignes et les colonnes de A, respecitvement. Ainsi,
la norme de Frobenius d’une matrice au carré est égale à la somme des carrés des normes de ses
colonnes ou de ses lignes). Comme on a montré que la norme d’un vecteur ne change pas par
transformation orthogonale, pour toute matrice U ∈ Rm×m orthogonale, on a
p p
∥U a•1 ∥2 + · · · + ∥U a•n ∥2 = ∥a•1 ∥2 + · · · + ∥a•n ∥2 ,
d’où ∥U A∥F = ∥A∥F . En considérant les lignes de A, on montre de même que ∥A∥F = ∥AV ∥F .
□
Par corollaire immédiat du lemme précédent, on note qu’une matrice Q ∈ Rm×n orthogonale
√
avec m ≤ n vérifie nécessairement ∥Q∥ = 1 et ∥Q∥F = m.
1.2. VALEURS PROPRES ET DÉCOMPOSITION SPECTRALE 11

1.2 Valeurs propres et décomposition spectrale

Définition 1.8 (Valeur propre) Soit une matrice A ∈ Rn×n . On dit que λ ∈ R est une valeur
propre de A si
∃v ∈ Rn , v ̸= 0n , Av = λv.
Le vecteur v est appelé un vecteur propre associé à la valeur propre λ. L’ensemble des valeurs
propres de A s’appelle le spectre de A.

Le sous-espace engendré par les vecteurs propres associés à la même valeur propre d’une matrice
s’appelle un sous-espace propre. Sa dimension correspond à l’ordre de multiplicité de la valeur propre
relativement à la matrice.

Proposition 1.1 Pour toute matrice A ∈ Rn×n , on a les propriétés suivantes :

• La matrice A possède n valeurs propres complexes mais pas nécessairement réelles.

• Si la matrice A est semi-définie positive (respectivement définie positive), alors ses valeurs
propres sont réelles positives (respectivement strictement positives).

• Le noyau de A est engendré par les vecteurs propres associés à la valeur propre 0.

Théorème 1.2 (Théorème spectral) Toute matrice carrée A ∈ Rn×n symétrique admet une décom-
position dite spectrale de la forme :
A = P ΛP −1 ,
où P ∈ Rn×n est une matrice orthogonale , dont les colonnes p1 , . . . , pn forment une base or-
thonormée de vecteurs propres, et Λ ∈ Rn×n est une matrice diagonale qui contient les n valeurs
propres de A λ1 , . . . , λn sur la diagonale.

Il est à noter que la décomposition spectrale n’est pas unique. En revanche, l’ensemble des
valeurs propres est unique, que l’on prenne en compte les ordres de multiplicité ou non.
La décomposition spectrale définie dans le théorème 1.2 est particulièrement importante car elle
permet de synthétiser l’information de A par son effet sur les vecteurs pi . Ainsi, lorsque |λi | >> 1,
on aura ∥Api ∥ >> ∥pi ∥, et la matrice aura donc un effet expansif dans la direction de pi (ou sa
direction opposée lorsque λi < 0. De même, si |λi | << 1, la matrice aura un effet contractant dans
la direction de pi : le cas extrême est λi = 0, c’est-à-dire que pi ∈ ker(A) et la matrice ne conserve
donc pas d’information relative à pi .
Géométriquement parlant, on voit ainsi que, pour tout vecteur x ∈ Rn décomposé dans la base
des pi que l’on multiplie par A, les composantes de ce vecteur associées aux plus grandes valeurs
propres1 seront augmentées, tandis que celles associées aux valeurs propres de petite magnitude
seront réduites (voire annihilées dans le cas d’une valeur propre nulle).

1.3 Décomposition en valeurs singulières

La décomposition en valeurs singulières (ou SVD, pour Singular Value Decomposition) est une tech-
nique fondamentale en analyse et compression de données, particulièrement utile pour compresser
des signaux audios, des images, etc.
1
On parle ici de plus grandes valeurs propres en valeur absolue, ou magnitude.
12 CHAPITRE 1. DÉCOMPOSITION EN VALEURS SINGULIÈRES

1.3.1 Principe de la décomposition

Soit une matrice rectangulaire A ∈ Rm×n : dans le cas général, les dimensions de la matrice diffèrent,
et on ne peut donc pas parler de valeurs propres de la matrice A. On peut en revanche considérer
les deux matrices
AT A ∈ Rn×n et AAT ∈ Rm×m .
Ces matrices sont symétriques réelles, et par conséquent diagonalisables. Par ailleurs, elles sont
fortement liées à la matrice A. Le lemme ci-dessous illustre quelques-unes des propriétés de AT A;
des résultats similaires peuvent être démontrés pour AAT .

Lemme 1.2 Pour toute matrice A ∈ Rm×n , les propriétés suivantes sont vérifiées :
i) AT A est semi-définie positive;

ii) AT A est symétrique.

iii) ker(AT A) = ker(A);

iv) Im(AT A) = Im(AT );

v) rang(AT A) = rang(A).

Ces résultats sont à la base de la construction de la décomposition en valeurs singulières, dont

on donne l’énoncé ci-dessous.

Théorème 1.3 (Décomposition en valeurs singulières) Toute matrice A ∈ Rm×n admet une
décomposition en valeurs singulières ( SVD2 ) de la forme

A = U ΣV T ,

où U ∈ Rm×m est orthogonale (U T U = Im ), V ∈ Rn×n est orthogonale (V T V = In ) et

Σ ∈ Rm×n est telle que Σij = 0 si i ̸= j et Σii ≥ 0.
L’ensemble des valeurs {Σii } pour 1 ≤ i ≤ min{m, n}, noté {σ1 , . . . , σmin{m,n} est appelé
l’ensemble des valeurs singulières de la matrice A. Les colonnes de V (resp. de U ) sont appelées
les vecteurs singuliers à droite (resp. à gauche) de A.

Remarque 1.1 Comme dans le cas de la décomposition en valeurs propres, il n’y a pas unicité de
la décomposition en valeurs singulières, mais il y a unicité de l’ensemble des valeurs singulières.

Exemple 1.1 La décomposition en valeurs singulières d’une matrice de R3×2 est de la forme
Σ
z
 { }|
σ1 0  T 
v1
A = [u1 u2 u3 ]  0 σ2 
vT
0 0 {z2 }
| {z }
U |
VT

où σ1 ≥ 0, σ2 ≥ 0, les ui forment une base orthonormée de R3 et les v i forment une base orthonormée
de R2 .
2
Dans la suite, on utilisera fréquemment l’algorithme anglo-saxon SVD pour faire référence à la décomposition en
valeurs singulières.
1.3. DÉCOMPOSITION EN VALEURS SINGULIÈRES 13

Proposition 1.2 Soit A ∈ Rm×n et U ΣV T une décomposition en valeurs singulières de A. Alors :

i) Les carrés des valeurs singulières sont les valeurs propres de AT A.
ii) Si rang(A) = r, alors il y a exactement r valeurs singulières non nulles.
Remarque 1.2 Une preuve constructive de la décomposition en valeurs singulières sera réalisée en
TD (exercice 1.5). Si cette preuve permet de construire une décomposition en valeurs singulières, elle
n’est pas forcément aisée à utiliser en pratique de par son coût en termes d’opérations algébriques.
Les implémentations modernes de la décomposition en valeurs singulières reposent sur des tech-
niques d’algèbre linéaire (QR avec pivotage, factorisation symétrique). La version la plus utilisée,
basée sur l’algorithme de Golub et Kahan [3], possède de très bonnes garanties de stabilité numérique,
ce qui est fondamental pour une implémentation efficace. Cela explique en partie le succès de la
décomposition en valeurs singulières et son utilisation très répandue dans de nombreuses applications.

1.3.2 Décomposition tronquée et approximation

Le principal intérêt de la décomposition en valeurs singulières est de permettre de compresser la
représentation de données matricielles. Dans de nombreuses applications, il est fréquent que les
matrices de données présentent peu de valeurs singulières élevées, et beaucoup de petites valeurs
singulières. On peut alors se demander quelle est la perte d’information que l’on réalise en omettant
ces valeurs singulières.
La première réduction d’information que l’on peut opérer consiste à éliminer les valeurs singulières
nulles dans la représentation de la matrice. C’est le sens du résultat ci-dessous.
Théorème 1.4 (SVD réduite) Toute matrice A ∈ Rm×n de rang r admet une SVD réduite de la
forme
A = U ΣV T , (1.3.1)
où U ∈ Rm×r avec U T U = I, V ∈ Rn×r avec V T V = Ir et Σ ∈ Rr×r est diagonale à coefficients
diagonaux strictement positifs.
La décomposition (1.3.1) est plus compacte que la décomposition originelle. En particulier, il
suffit de stocker (n+m)r réels3 pour pouvoir reconstruire la matrice, ce qui peut être plus avantageux
que de stocker les mn coefficients de la matrice A.
Définition 1.9 (SVD tronquée) Soit A ∈ Rm×n une matrice de rang r et U ΣV T sa SVD réduite,
avec  
σ1 0 · · · 0
U = [u1 · · · ur ], V = [v 1 · · · v r ], Σ =  0 ..
0 .
 
.
0 · · · 0 σr .
On suppose que σ1 ≥ · · · ≥ σr . Alors, pour tout k ≤ r, la décomposition U k Σk,k V T
k , où
 
σ1 0 · · · 0
U k = [u1 · · · uk ], V k = [v 1 · · · v k ], Σk,k =  0
 .. 
. 0 
0 · · · 0 σk .
s’appelle la décomposition en valeurs singulières tronquée à k valeurs, ou k-SVD.
3
Le coût est de (n + m + 1) ∗ r si on stocke les valeurs singulières séparément, mais on peut également les incorporer
dans U ou V , auquel cas le coût de stockage sera de (n + m) ∗ r.
14 CHAPITRE 1. DÉCOMPOSITION EN VALEURS SINGULIÈRES

On remarque que cette factorisation est encore moins coûteuse en terme de coefficients que
la décomposition en valeurs singulière réduite. Contrairement à celle-ci, la k-SVD supprime de
l’information issue de la matrice A dès lors que k < r : tout l’enjeu du processus de troncature
consiste à préserver la majeure partie de l’information contenue dans la matrice, c’est-à-dire les
valeurs singulières les plus importantes.

Application en compression d’images On considère une image 307x241 pixels stockée sous la
forme d’une matrice A ∈ Rm×n . Si on calcule la décomposition en valeurs singulières de A, on peut
voir que le rang de la matrice est n = 241.

Figure 1.1: Image 307x241 pixels; la matrice correspondante est de rang 241.

On peut cependant se demander si toutes les valeurs singulières sont nécessaires pour encoder
l’image. On considère donc plusieurs troncatures de la SVD, correspondant à différentes valeurs de
k inférieures au rang véritable. Les résultats de la figure 1.2 montrent qu’il n’est pas nécessaire de
considérer la décomposition complète pour obtenir une image nette (voire indiscernable de l’image
d’origine à l’oeil nu). Par ailleurs, on notera qu’une SVD tronquée peut avoir un coût mémoire
supérieur à
1.3. DÉCOMPOSITION EN VALEURS SINGULIÈRES 15

Figure 1.2: Image 307x241 et SVD tronquées avec k ∈ {10, 20, 50, 100, 150}; le rang de chaque
matrice est indiqué, ainsi que le ratio (m+n)∗k
mn .
Chapitre 2

Analyse en composantes principales

2.1 Motivation
On se place maintenant dans un contexte du modèle fonctionnel ou factoriel1 . On supposera dans
la suite que l’on dispose d’un tableau de données X ∈ Rm×n , que l’on écrira des deux manières
suivantes :  T 
x1
 .. 
X =  .  = [v 1 · · · v n ] .
xTm

Dans cette écriture, les lignes de la matrice X représentent des individus xi ∈ Rn , chacun possédant
n caractéristiques (ou attributs). Les colonnes de la matrice X représentent quant à elles les vecteurs
des attributs : ainsi, le vecteur v j ∈ Rm contient l’ensemble des valeurs pour le j-ième attribut.
Le but de ce chapitre est de présenter une technique pour extraire l’information importante de X,
afin d’obtenir une représentation plus compacte des données. Nous avons déjà vu un exemple d’un
tel outil dans le chapitre 1, avec la décomposition en valeurs singulières tronquée. Cette dernière
permet en effet de compresser les données, mais l’interprétation des composantes obtenues n’est pas
toujours évidente. Par ailleurs, la SVD ne fournit aucune garantie statistique sur les données, car
elle ne fait pas intervenir la distribution des xi , qui est inconnue en général.
Dans le reste de ce chapitre, on va développer une approche géométrique d’analyse des données
X. L’idée est de considérer les vecteurs {xi }i ou {v j }j comme des nuages de points, respectivement
dans Rn et Rm . On peut alors exprimer une distribution empirique sur ces données, et chercher une
représentation de celles-ci qui soit de dimension réduite tout en étant la plus conforme possible aux
données d’origine. L’analyse en composantes principales repose précisément sur ce principe.

2.2 Statistique empirique et pré-traitement des données

Dans cette section, nous décrivons les statistiques qui peuvent être calculées à partir d’un échantillon
de données. Comme dit plus haut, la distribution sous-jacente des données n’est généralement pas
connue (on suppose cependant qu’il en existe une). On peut toutefois estimer des statistiques de
notre distribution, qui permettent une première transformation des données. Cette étape, appelée
pré-traitement, permet de se placer dans un contexte plus favorable à l’application de l’analyse en
1
Que l’on peut également considérer comme une problématique d’apprentissage non supervisé.

16
2.2. STATISTIQUE EMPIRIQUE ET PRÉ-TRAITEMENT DES DONNÉES 17

composantes principales. Mathématiquement parlant, cela correspond à appliquer une transformation

linéaire sur les données.

2.2.1 Individu moyen et données centrées

Une première étape dans l’analyse statistique de la matrice de données X consiste à centrer les
données : cette procédure est extrêmement classique en analyse de données, et possède également
une justification mathématique forte. On en donne ici

Définition 2.1 (Individu moyen) Soit une matrice X ∈ Rm×n . La moyenne arithmétique des
variables, que l’on appelle également l’individu moyen, est définie comme le vecteur :
 
m 1
1 X 1 T  .. 
x̄ := xi = X 1m , avec 1m =  .  ∈ Rm . (2.2.1)
m m
i=1 1
L’individu moyen représente ainsi la tendance centrale des données. Sur le plan géométrique, le
vecteur x̄ représente le centre de gravité du nuage de points formé par les individus xi dans Rn .
Une opération courante en analyse de données consiste à opérer un centrage des données. Cela
consiste à translater les individus par rapport à leur moyenne empirique, de sorte à obtenir un nuage
de points qui soit centré en l’origine dans Rn .

Définition 2.2 (Données centrées) Soit X ∈ Rm×n un tableau de données et xT T

1 , . . . , xm ses
lignes. On dit que l’on centre les données lorsque l’on remplace les xi et X par
xci := xi − x̄, X c := X − 1m x̄T . (2.2.2)

2.2.2 Dispersion et dépendance

La première statistique que nous avons établie concernait la moyenne des données; il est naturel de
chercher à estimer également la covariance des données (on parlera ici de covariance car on considère
des vecteurs aléatoires). Pour ce faire, on introduit la notion suivante.

Définition 2.3 (Matrice de covariance empirique) Soit X ∈ Rm×n un tableau de données et

xT T
1 , . . . , xm ses lignes. La matrice de covariance empirique associée à X est définie par
m
1 X 1
Σ := (xi − x̄)(xi − x̄)T = (X c )T X c ∈ Rn×n , (2.2.3)
m m
i=1

où x̄ désigne l’individu moyen et X c la matrice des données centrées.

Les coeffficients de la matrice Σ représentent les covariances empiriques des vecteurs d’attributs v i
et v k . Les composantes diagonales de la matrice de covariance sont particulièrement intéressantes
du point de vue géométrique : elles représentent les variances empiriques des n variables (et non des
m individus !). On note ainsi
m n m
!2
1 X 1 X 1 X
σj2 := [Σ]jj = ([xi ]j − [x̄]j )2 = [v j ]i − [v j ]k .
m m m
i=1 i=1 k=1

On regroupe généralement ces quantités dans la notion d’inertie.

18 CHAPITRE 2. ANALYSE EN COMPOSANTES PRINCIPALES

Définition 2.4 (Inertie) L’inertie du nuage de points X ∈ Rm×n est définie par

I(X) := trace(Σ), (2.2.4)

où Σ est la matrice de covariance empirique de X.

L’inertie d’un nuage de points X décrit ainsi la dispersion des individus xi autour de leur centre de
gravité. On notera que l’on a
n m
X 1 X
I(X) = σj2 = ∥xi − x̄∥2 .
m
j=1 i=1

De la même manière que nous avons centré les données à l’aide de l’individu moyen, nous pouvons
opérer une transformation des données en utilisant la diagonale de la matrice de covariance empirique.

Définition 2.5 (Données centrées réduites) Soit X ∈ Rm×n un tableau de données et xT T

1 , . . . , xm
ses lignes. La matrice diagonale de réduction pour X, notée D 1/σ , est définie par :
 1 
σ1 0 · · · 0
.. n×n
D 1/σ :=  0 0 ∈R (2.2.5)
 
.
1
0 ···0 σn .

où σ1 , . . . , σn sont les coefficients diagonaux de la matrice de covariance empirique de X.

De plus, la matrice
 
c [xi ]j − [x̄]j
X 0,1 := X D 1/σ = ∈ Rm×n (2.2.6)
σj i=1,...,m
j=1,...,n

s’appelle la matrice de données centrées réduites.

La réduction des données X correspond donc à une transformation diagonale, où l’on normalise
chaque attribut selon sa variance empirique. On peut alors étudier la corrélation de cette nouvelle
matrice.

Définition 2.6 (Matrice de corrélation empirique) Soit X ∈ Rm×n une matrice de données et
X 0,1 sa version centrée réduite. Alors, la matrice
1 T
R= X X 0,1 . (2.2.7)
m 0,1
s’appelle la matrice de corrélation empirique associée à X.

Lorsque [R]ij = 1, cela signifie qu’il existe une relation de dépendance affine entre v i et v j , qui
suggère que cette relation affine est valide pour les deux attributs sur l’ensemble de la distribution.
On peut dans ce cas réduire les deux attributs à un seul.
La matrice de corrélation empirique permet donc d’identifier des corrélations claires (affines).
Dans la pratique, les corrélations peuvent se présenter sous des formes plus complexes, et il n’est
pas trivial de réduire les n attributs à un nombre inférieur. L’analyse en composantes principales,
que nous détaillons dans la partie suivante, permet précisément de passer de n à k ≤ n attributs en
conservant le maximum d’information.
2.3. PRINCIPE DE L’ANALYSE EN COMPOSANTES PRINCIPALES 19

2.3 Principe de l’analyse en composantes principales

Dans cette partie, nous fournissons une analyse détaillée de l’analyse en composantes principales,
aussi appelée ACP2 . Nous séparons le cas d’une et de plusieurs composantes principale(s).

2.3.1 Analyse en une composante principale

Nous étudions tout d’abord le cas d’une seule composante principale. Du point de vue géométrique,
m n
on considère donc le problème suivant : étant donné un nuage  Tdepoints {xi }i=1 ⊂ R (que
x1
 .. 
l’on considèrera comme précédemment sous la forme X =  . ), on souhaite projeter ces
xTn
n
points sur une droite dans R de sorte à conserver le maximum d’information. Cela revient à
chercher à remplacer les n variables définissant un individu (ses attributs) par une unique variable
appelée composante principale, obtenue par combinaison linéaire des variables originelles, qui soit
de variance ou d’inertie maximale pour le nuage de points considéré.

Formulation mathématique Afin de préserver le maximum d’information, la droite sur laquelle

nous allons projeter devra nécessairement passer par l’individu moyen x̄. L’équation de cette droite
sera donc {x̄ + tu|t ∈ R}, où u est un vecteur de Rn que l’on considèrera unitaire (de norme 1)
sans perte de généralité.
On souhaite une droite qui représente au mieux chacun des points. Si on note y i la projection du
vecteur xi sur la droite, cela signifie que l’on souhaite que y i et xi soient les plus proches possibles.
Le problème d’optimisation sous-jacent est donc
m
1 X
min ∥y i − xi ∥2 . (2.3.1)
u∈Rn ,∥u∥=1 m
i=1

La proposition suivante montre que le problème peut s’exprimer relativement au nuage de points
formé par les projections y i .

Proposition 2.1 Minimiser l’erreur entre points originaux et points projetés revient à maximiser
l’inertie, au sens où le problème (2.3.1) possède le même ensemble de solutions que le problème
m
1 X
max I(Y ) = ∥y i − ȳ∥2 , (2.3.2)
u∈Rn ,∥u∥=1 m
i=1

yT
 
1
 .. 
où ȳ désigne le centre de gravité de Y =  . .
yTm

En résolvant le problème de projection (2.3.1), on cherche donc à maximiser la dispersion des

projections sur la droite. La projection orthogonale réalise précisément cet objectif.
2
Ou PCA, de l’anglais Principal Component Analysis.
20 CHAPITRE 2. ANALYSE EN COMPOSANTES PRINCIPALES

Définition 2.7 (Projection orthogonale sur une droite) La projection orthogonale d’un ensem-
ble de points {xi }i ⊂ Rn sur une droite de vecteur directeur u ∈ Rn (avec ∥u∥ = 1) et passant par
x̄ est donnée par :
y i = ci u + x̄, ci = uT (xi − x̄) . (2.3.3)

On dispose alors des propriétés suivantes.

Lemme 2.1 Soit {xi }m n m

i=1 un nuage de points de R et {y i }i=1 les projections orthogonales des xi
sur une droite de vecteur directeur u, où ∥u∥ = 1. Alors, les propriétés suivantes sont vérifiées :

i) On a ȳ = x̄;

ii) ci u = uT (xi − x̄)u = uuT (xi − x̄), où uuT est une matrice de projection orthogonale;

iii) Y = (X − 1m x̄T )uuT + 1m x̄T .

Définition 2.8 On appelle composante principale la coordonnée ci de y i dans le repère (x̄; u).
La droite de vecteur directeur u passant par x̄ s’appelle l’axe principal, et u est appelé le vecteur
principal.

On notera que les notions de composante, axe et vecteur principaux ne dépendent que des xi .

Calcul explicite de la composante principale

Théorème 2.1 Le problème maxu∈Rn ,∥u∥ I(Y ) possède le même ensemble de solutions que le
problème
max uT Σu. (2.3.4)
u∈Rn ,∥u∥=1

Le problème (2.3.4) est un problème très classique de mathématiques appliquées : il est lié au calcul
des vecteurs propres de la matrice Σ, qui est symétrique et semi-définie positive par construction.

Corollaire 2.1 L’ensemble des solutions du problème (2.3.2) est donné par l’ensemble des vecteurs
propres unitaires associés à la plus grande valeur propre de Σ.

Remarque 2.1 Dans la pratique, il sera fréquent que la plus grande valeur propre soit de multiplicité
1, donc qu’il n’existe que deux solutions au problème (2.3.4) qui seront égales au signe près. En
cas d’égalité, cependant, on aurait plusieurs directions possibles pour la composante principale, ce
qui indiquerait que plusieurs composantes possèderaient la même importance. Ces considérations
justifient en partie le recours à l’analyse en plusieurs composantes principales décrite dans la section
ci-dessous.

2.3.2 Analyse en plusieurs composantes principales

On étend maintenant l’analyse de la partie précédente en considèrant le calcul de plusieurs com-
posantes principales. Du point de vue mathématique, cela revient à projeter sur un sous-espace de
dimension k, où k ≥ 1. On considèrera comme précédemment un sous-espace affine de la forme

x̄ + Sk , Sk := vect{u1 , . . . , uk }, (2.3.5)
2.3. PRINCIPE DE L’ANALYSE EN COMPOSANTES PRINCIPALES 21

où S est un sous-espace vectoriel de dimension k, et U k = [u1 · · · uk ] ∈ Rn×k est une base
orthonormale du sous-espace S (c’est-à-dire U T k U k = I k , où I k est la matrice identité de R
k×k ).

Comme dans le cas d’une composante principale, on souhaite calculer la projection la plus proche
des données originelles. On considère donc le problème
m
1 X
min ∥y i − xi ∥2 . (2.3.6)
U k ∈Rn×k ,U T
k U k =I
m
i=1

où y i représente la projection de xi sur l’espace x̄ + Sk . Comme dans le cas d’une composante
principale, on va reformuler le problème en tant que maximisation de l’inertie.

Proposition 2.2 Minimiser l’erreur entre points originaux et points projetés revient à maximiser
l’inertie, au sens où le problème (2.3.1) possède le même ensemble de solutions que le problème
m
1 X
max I(Y ) = ∥y i − ȳ∥2 , (2.3.7)
U ∈ Rn×k ,U T U =I k m
i=1

yT
 
1
où ȳ désigne le centre de gravité de l’ensemble des points projetés Y =  ... .
 

yTm

Comme dans le cas unidimensionnel, on dispose d’une formule explicite sur les projections or-
thogonales.

Définition 2.9 (Projection orthogonale sur un sous-espace affine) On considère un sous-espace

affine de dimension k engendré par une base orthonormale U k et passant par le vecteur x̄. Alors,
pour tout i = 1, . . . , m, la projection de xi sur ce sous-espace est donné par :
y i = U k ci + x̄, où ci = U T
k (xi − x̄).

Cette propriété conduit à la définition des composantes principales.

Définition 2.10 (Composantes principales) Les vecteurs ci , qui représentent les coordonnées des
y i dans le repère (x̄; u1 , . . . , uk ), sont appelées les (k premières) composantes principales. Les
vecteurs u1 , . . . , uk sont appelés les axes principaux.

Calcul explicite de k composantes principales L’analyse en composantes principales repose

sur la création d’une base orthonormale, ce qui permet d’établir le lien suivant entre composantes
principales

Proposition 2.3 Soit U k la solution du problème (2.3.6) en k < n composantes principales. Alors,
le problème
max I(Y ) (2.3.8)
U ∈Rn×(k+1) ,U T U =I k+1

admet comme solution U k+1 = [U k uk+1 ], où uk+1 est la composante principale du nuage dans
l’espace orthogonal à vect{u1 , . . . , uk }, c’est-à-dire une solution du problème
max I(Z), (2.3.9)
u∈Rn ,∥u∥=1
uT u1 =0
···
uT uk =0
22 CHAPITRE 2. ANALYSE EN COMPOSANTES PRINCIPALES

zT
 
1
où Z =  ...  désigne l’ensemble des projections des points x1 , . . . , xn .
 

zTm

On voit ainsi que le calcul de k composantes principales se ramène à k problèmes en une

composante principale résolus de manière successive sur des espaces orthogonaux. Cette idée est
en lien direct avec la décomposition en valeurs propres (qui utilise des bases orthonormales donc
orthogonales), et conduit au résultat suivant.

Théorème 2.2 Les solutions du problème (2.3.6) sont donné par les ensembles de k vecteurs propres
unitaires de Σ associés aux k plus grandes valeurs propres de Σ, que l’on note λ1 ≥ · · · ≥ λk .

On notera qu’en cas de valeurs propres multiples, l’ensemble des solutions peut être ambigü (ce
qui peut indiquer qu’une analyse en k ′ > k composantes principales apportera une information
intéressante).
Le résultat ci-dessous permet d’établir des garanties sur les projections y i en tant qu’approximations
des xi .

Corollaire 2.2 Sous les hypothèses du théorème 2.2, on a les propriétés suivantes :

i) L’écart d’inertie entre les nuages de points projeté et originel est donné par
Pk Pk
I(Y ) j=1 λj j=1 λj
= = Pn .
I(X) I(X) j=1 λj

ii) Dans le cas général, le tableau Y est solution du problème d’optimisation en variables matricielles
suivant :
Y = argmin ∥M − X∥2F sous la contrainte rang(M ) = k.
M ∈Rm×n

iii) Si k = n, alors y i = xi pour tout i, mais la base utilisée pour décrire les vecteurs est différente.

En bref : Comment penser l’ACP ? L’analyse en composantes principales peut être vue comme
réalisant les opérations suivantes :

i) Un changement de repère trouvant les axes d’inertie maximale pour les données : on passe
ainsi du repère canonique {0; e1 , . . . , en }, où e1 , . . . , en sont les vecteurs de la base canonique
de Rn , au repère {x̄; u1 , . . . , uk , . . . , un } (et on ne considère généralement qu’une partie des
coordonnées dans ce nouveau repère).

ii) Une réduction de la dimension pour k < n : on

 passe en effet d’une matrice X ∈ Rm×n à une
T
matrice de composantes principales C = ci i=1,...,m ∈ R m×k , qui est donc moins coûteuse à
stocker en mémoire;

iii) Un centrage des données, car les composantes forment un jeu de données centrées :
m
1 X
c̄ = ci = 0;
m
i=1
2.3. PRINCIPE DE L’ANALYSE EN COMPOSANTES PRINCIPALES 23

iv) Une décorrélation des composantes, car la matrice de covariance des composantes centrées (qui
sont identiques aux composantes d’origine d’après le point précédent) est diagonale :

Σ′ = C T C = diag(λ1 , . . . , λk ),

où λ1 ≥ · · · ≥ λk sont les k plus grandes valeurs propres de Σ.

2.3.3 Application : Reconnaissance de visage

L’une des applications les plus connues de l’analyse en composantes principales est la reconnaissance
de visages. L’idée est de partir d’une base d’images de visages, vues commes des vecteurs de
dimension égale au nombre de pixels. Dans ce contexte, on peut calculer les axes principaux, qui
sont appelées les eigenfaces, ou “visages propres” (par analogie avec les vecteurs propres). On peut
ainsi se servir de ces eigenfaces pour approcher une image, mais aussi pour reconnaı̂tre un visage sur
une image absente du jeu de données originel.
 Partie II

Régression linéaire

24
Chapitre 3

Premiers pas avec le modèle linéaire

Dans le chapitre 1, nous avons introduit la décomposition en valeurs singulières, une technique
visant à extraire de l’information d’un jeu de données : ce paradigme est celui de l’apprentissage non
supervisé. Ce chapitre aborde un autre paradigme, celui de l’apprentissage supervisé, dans lequel
il s’agira de déterminer un modèle (une fonction linéaire pour les besoins de ce cours) décrivant
une relation entre différents éléments d’un jeu de données, pour potentiellement prédire (on parle
également d’inférer) le comportement de données futures.

3.1 Introduction
On considère un jeu de données ayant m éléments ou individus, et on associe à chaque individu n
caractéristiques1 sous la forme d’un vecteur de Rn . Soient x1 , . . . , xn ces vecteurs : on les regroupe
alors sous la forme d’une matrice de données
 T 
x1
 .. 
X =  .  ∈ Rm×n . (3.1.1)
T
xm

Exemple 3.1 • Chaque ligne de X représente un individu, et les n composantes de xi sont des
données médicales (âge, poids, taux de cholestérol, etc).

• Chaque ligne de X est une “vectorisation” d’une image 2D, et les valeurs de xi sont celles des
pixels, en niveau de gris. Ainsi, une image de taille 480*640 serait transformée (en mettant
les lignes bout à bout, par exemple) en un vecteur de taille n = 480 ∗ 640 = 307200.

Sans autre information que la matrice elle-même, on peut appliquer des techniques d’algèbre
linéaire pour en extraire de l’information : c’est ce que réalisait la SVD dans le chapitre précédent.
Dans un contexte d’apprentissage supervisé, on associe chaque vecteur de caractéristiques xi à un
label yi ∈ R, qui peut représenter une classe à laquelle l’individu appartient (malade/non malade,
image de chien ou de chat, etc). Ces labels sont concaténés pour former un vecteur de labels y ∈ Rm .
Par conséquent, notre but n’est plus seulement d’analyser l’information de la matrice X, mais bien
de trouver une relation entre les caractéristiques X et les labels y. Pour ce cours, on postulera que
1
Ou features en anglais.

25
26 CHAPITRE 3. PREMIERS PAS AVEC LE MODÈLE LINÉAIRE

cette relation est linéaire : on va donc chercher une fonction h : Rn → R de la forme h(x) = xT β.
On souhaite que h permette d’obtenir les yi à partir des xi , c’est-à-dire que l’on voudrait avoir

h(xi ) = xT
i β = yi ∀i = 1, . . . , m,

que l’on peut ré-écrire sous forme matricielle comme

X β = y.

On se trouve donc en présence d’un système linéaire que l’on va vouloir résoudre. Rien ne garantit
a priori que ce système possède une solution, ou que cette solution (si elle existe) est unique. Une
étude plus approfondie des systèmes d’équations linéaires semble donc nécessaire.

3.2 Résolution de systèmes non linéaires

Définition 3.1 Un système linéaire de m équations à n inconnues β1 , . . . , βn est donné par

x11 β1 + x12 β2 + ... + x1n βn = y1

x21 β1 + x22 β2 + ... + x2n βn = y2
.. .. .. .. ..
. . . . .
xm1 β1 + xm2 β2 + . . . + xmn βn = ym

ou, sous forme compacte,

Xβ = y,
avec X ∈ Rm×n , β ∈ Rn , y ∈ Rm .

Dans la suite, nous allons déterminer les conditions d’existence de solutions à ce système linéaire.

3.2.1 Cas d’un système carré

On s’intéresse tout d’abord au cas où n = m : on a donc un système dit “carré” de n équations à
n inconnues de la forme
Xβ = y, (3.2.1)
où X ∈ Rn×n , y ∈ Rn , et β ∈ Rn représente les paramètres inconnus de notre modèle.
L’existence et l’unicité de solutions au système (3.2.1) dépendent des propriétés de la matrice X
et du vecteur y, comme le montrent les exemples ci-dessous.

Exemple 3.2 a) Le système 

β1 + β2 = 0,
3β1 + 2β2 = 1.
possède une unique solution β1 = 1, β2 = −1.

b) Le système 
β1 = 0,
β1 = −1.
ne possède pas de solution.
3.2. RÉSOLUTION DE SYSTÈMES NON LINÉAIRES 27

c) Le système 
β1 + 2β2 = 2,
2β1 + 4β2 = 4.
possède une infinité de solutions.

On peut donc se trouver dans trois cas différents : pour les deux derniers, on ne sait pas ce
qui peut être fait. En revanche, le premier cas correspond à une matrice X inversible : dans cette
situation, il existe une caractérisation de la solution du système.

Théorème 3.1 (Résolution d’un système carré inversible) Soient X ∈ Rn×n une matrice in-
versible et y ∈ Rn . Le système carré inversible Xβ = y possède une unique solution β ∗ donnée
par
β ∗ = X −1 y.

Lorsque la matrice X n’est pas inversible en revanche, c’est-à-dire que rang(X) < n, il existera
une infinité de solutions si y ∈ Im(X), et aucune si y ∈
/ Im(X).

3.2.2 Cas d’un système rectangulaire

On considère maintenant le cas d’un système linéaire rectangulaire non carré, soit

Xβ = y, X ∈ Rm×n , m ̸= n. (3.2.2)

Comme le montrent les exemples ci-dessous, on retrouve les mêmes cas que pour un système
carré.

Exemple 3.3 a) Le système

β1 + β2 = 0,
3β1 + 2β2 = 1,
6β1 + 5β2 = 1.
possède une unique solution (β1 = 1, β2 = −1).

b) Le système
β1 + 2β2 = 2.
possède une infinité de solutions.

c) Le système
β1 = 2,
β2 = 3,
β1 + β2 = 0.
ne possède pas de solution.

Sans information sur le système linéaire, il ne semble donc pas possible de déterminer s’il possède
ou non des solutions. On peut cependant être plus spécifique pour certains types de systèmes
satisfaisant la propriété ci-dessous.

Définition 3.2 Une matrice X ∈ Rm×n est de rang plein si rang(X) = min{m, n}.
28 CHAPITRE 3. PREMIERS PAS AVEC LE MODÈLE LINÉAIRE

Toute matrice carrée inversible est de rang plein, mais cette notion est plus générique. On a ainsi
les cas particuliers suivants.

Théorème 3.2 Soient X ∈ Rm×n de rang plein et y ∈ Rm avec m ̸= n. On a :

a) Si rang(X) = n, alors X T X est inversible et le système (3.2.2) possède une unique solution
donnée par (X T X)−1 X T y lorsque y ∈ Im(X);

b) Si rang(X) = m, alors XX T est inversible et le vecteur X T (XX T )−1 y est solution de (3.2.2)

Il est donc toujours possible de déterminer une solution au problème (3.2.2) lorsque X est de
rang plein. Lorsque X n’est pas de rang plein, on retombe en revanche dans les mêmes difficultés
que pour un système carré.
Comme on le verra dans la section suivante, les différentes expressions établies dans les théorèmes 3.1
et 3.2 correspondent en fait à une même formule.

3.2.3 Pseudo-inverse et SVD

Le concept d’inverse d’une matrice carrée peut être généralisé au cas d’une matrice rectangulaire :
c’est le principe de la pseudo-inverse2 que l’on décrit ci-dessous.

Définition 3.3 (Pseudo-inverse d’une matrice) Soit une matrice X ∈ Rm×n . Il existe une unique
matrice M ∈ Rn×m vérifiant les équations de Penrose :

XM X = X
M XM = M
T
(XM ) = XM
T
(M X) = MX

Cette matrice s’appelle la pseudo-inverse de X et on la note X † .

Sous sa forme générale, le calcul de la pseudo-inverse ne semble pas évident. Il existe heureuse-
ment une formule explicite de la pseudo-inverse basée sur la décomposition en valeurs singulières.

Proposition 3.1 Soit une matrice diagonale par blocs Σ ∈ Rm×n de la forme
 
σ1 0 · · · 0 0
.. . 
0 .. 

 0 .
 
 0 · · · 0 σr 0 
0 ··· ··· 0

avec σ1 ≥ · · · ≥ σr > 0. La pseudo-inverse de la matrice Σ est la matrice Σ† ∈ Rn×m définie par

 1 
σ1 0 · · · 0 0
 .. .. 
†
Σ =
 0 . 0 . 
.
 0 ···0 1 0 
σr
0 ··· ··· 0
2
On parle aussi d’inverse généralisée ou d’inverse de Moore-Penrose.
3.3. MOINDRES CARRÉS LINÉAIRES 29

Le résultat de la proposition 3.1 illustre bien le concept de pseudo-inverse : on a ainsi “inversé”

uniquement le bloc diagonal contenant des valeurs non nulles, le reste étant simplement transposé
pour inverser les espaces de départ et d’arrivée.
On a alors le résultat générique suivant.

Théorème 3.3 (Formule de pseudo-inverse) Soit une matrice X ∈ Rm×n et U ΣV T une décomposition
en valeurs singulières de cette matrice. Alors, la pseudo-inverse de X est donnée par

X † = V Σ† U T . (3.2.3)

On peut vérifier que la formule (3.2.3) satisfait bien aux équations de Penrose. Ces dernières
suggèrent qu’il est possible d’utiliser la pseudo-inverse d’une manière similaire à celle de l’inverse pour
une matrice carrée inversible : le lien entre inverse et pseudo-inverse est encore plus ténu, comme le
montrer le corollaire suivant.

Corollaire 3.1 Soit X ∈ Rm×n une matrice de rang plein. Alors,

i) Si rang(X) = m, alors X † = X T (XX T )−1 ;

ii) Si rang(X) = n, alors X † = (X T X)−1 X T ;

iii) Si rang(X) = n et que n = m, alors X est carrée inversible, et les deux formules ci-dessus
correspondent à X † = X −1 .

La pseudo-inverse est ainsi apparue dans les sections 3.2.1 et 3.2.2 lorsque l’on supposait que la
matrice X était de rang plein. En ce sens, il semble que la technique de pseudo-inverse soit adaptée
aux problèmes bien posés. L’approche par moindres carrés, développée dans la section suivante,
va permettre de formaliser cette propriété, et de mettre en lumière le rôle plus large joué par la
pseudo-inverse.

3.3 Moindres carrés linéaires

Comme expliqué dans la section précédente, la notion de solution d’un système linéaire perd de son
sens lorsque le système ne possède pas de solution, ou une infinité. Pour cette raison, on définit un
autre concept de solution, dite au sens des moindres carrés.

3.3.1 Solution au sens des moindres carrés

Un problème aux moindres carrés linéaires est un problème d’optimisation, et plus précisément de
minimisation : étant donnés X ∈ Rm×n et y ∈ Rm , on ne cherche plus à résoudre Xβ = y
de manière exacte, mais plutôt à minimiser l’écart entre les vecteurs Xβ et y. Du point de vue
mathématique, on évaluera cet écart via la norme euclidienne, et on cherchera donc à résoudre le
problème (dit aux moindres carrés linéaires) suivant :

1
min ∥Xβ − y∥2 . (3.3.1)
β∈Rn 2
30 CHAPITRE 3. PREMIERS PAS AVEC LE MODÈLE LINÉAIRE

1 2
Il s’agit d’un problème de minimisation de la fonction β →
7 2 ∥Xβ − y∥ selon β, sous sa forme
standard en optimisation.3 Notons que si l’on décompose la norme, on obtient :
m
X
∥Xβ − y∥2 = (xT 2
i β − yi ) .
i=1

Cet objectif que l’on cherche à réduire représente donc bien l’attache aux données, c’est-à-dire la
correspondance entre notre modèle linéaire et les labels de chaque individu.

Définition 3.4 (Solution au sens des moindres carrés) Soient X ∈ Rm×n et y ∈ Rm . L’ensemble
des vecteurs β ∈ Rn tels que la valeur de 12 ∥Xβ − y∥2 soit minimale, que l’on note :

1
arg minn ∥Xβ − y∥2 , (3.3.2)
β∈R 2

s’appelle l’ensemble des solutions au sens des moindres carrés.

La notion de solution au sens des moindres carrés est à distinguer de celle d’une solution du
système linéaire, pour laquelle nous introduisons la terminologie ci-dessous.

Définition 3.5 (Solution au sens classique) Soient X ∈ Rm×n et y ∈ Rm . L’ensemble des

vecteurs β ∈ Rn tels que Xβ = y s’appelle l’ensemble des solutions au sens classique du système
linéaire.
Cet ensemble peut être vide, et il est nécessairement inclus dans l’ensemble des solutions au sens
des moindres carrés.

Le concept de solution au sens des moindres carrés nous permet d’introduire différents concepts,
liés notamment à la pseudo-inverse.

Théorème 3.4 Pour tous X ∈ Rm×n et y ∈ Rm , les propriétés suivantes sont vérifiées :

1. l’ensemble défini par (3.3.2) est toujours non vide;

2. le vecteur X † y est une solution au sens des moindres carrés;

3. parmi toutes les solutions au sens des moindres carrés, le vecteur X † y est la solution de norme
minimale :
1
∀ γ ∈ arg minn ∥Xβ − y∥2 , ∥γ∥ ≥ ∥X † y∥.
β∈R 2

Ce théorème ne sera pas démontré dans ce cours (voir à cet égard le cours de Méthodes
numériques : Optimisation au semestre 2, ou le cours Mathématiques pour les sciences des données).
En revanche, nous exploiterons fortement ce résultat pour calculer une solution au sens des moindres
carrés.
3
Pour des raisons de normalisation, on introduit notamment un facteur 1/2.
3.4. CONCLUSION 31

3.3.2 Résolution du problème aux moindres carrés

Le théorème ci-dessous récapitule l’ensemble des cas à considérer dans le calcul d’un modèle linéaire.

Théorème 3.5 Soient X ∈ Rm×n , y ∈ Rm et β ∗ = X † y.

1) Si m = n, on distingue trois cas :
a) Si rang(X) = m = n, on a β ∗ = X −1 y, et il s’agit de l’unique solution au sens classique et
au sens des moindres carrés;
b) Si rang(X) < m et y ∈ Im(X), alors β ∗ est une solution au sens classique et de norme
minimale au sens des moindres carrés. Les problèmes (3.2.1) et (3.3.1) admettent chacun
une infinité de solutions.
c) Si rang(X) < m et y ∈ / Im(X), alors il n’existe pas de solution au sens classique; en revanche,
β ∗ est la solution de norme minimale au sens des moindres carrés.
2) Si m < n (système sous-déterminé), on distingue trois cas :
b) Si rang(X) = m, alors β ∗ = X T (XX T )−1 y et il s’agit à la fois d’une solution classique et
de la solution de norme minimale au sens des moindres carrés. Les problèmes (3.2.2) et (3.3.1)
admettent chacun une infinité de solutions.
b) Si rang(X) < m et y ∈ Im(X), alors β ∗ est une solution au sens classique et de norme
minimale au sens des moindres carrés. Les problèmes (3.2.1) et (3.3.1) admettent chacun
une infinité de solutions.
b) Si rang(X) < m et y ∈ / Im(X), alors il n’existe pas de solution au sens classique; en revanche,
β ∗ est la solution de norme minimale au sens des moindres carrés.
3) Si m > n (système sur-déterminé), on distingue trois cas :
a) Si rang(X) = n, alors β ∗ = (X T X)−1 X T y et il s’agit de l’unique solution au sens des
moindres carrés. C’est une solution au sens classique lorsque y ∈ Im(X).
b) Si rang(X) < n et y ∈ Im(X), alors β ∗ est une solution au sens classique et de norme
minimale au sens des moindres carrés. Les problèmes (3.2.1) et (3.3.1) admettent chacun
une infinité de solutions.
c) Si rang(X) < n et y ∈/ Im(X), alors il n’existe pas de solution au sens classique; en revanche,
∗
β est la solution de norme minimale au sens des moindres carrés.

3.4 Conclusion
Dans le contexte de l’apprentissage supervisé, on peut être amené à vouloir expliquer nos données
par un modèle linéaire. Ce choix de modélisation fait naturellement apparaı̂tre des systèmes linéaires,
dont l’étude repose sur des propriétés issues de l’algèbre linéaire. Il apparaı̂t alors que le problème
peut être bien ou mal posé, selon que le système possède une, des ou même aucune solution(s).
On a ainsi introduit le concept de problème aux moindres carrés associé à un système linéaire,
qui a permis de formuler la procédure d’apprentissage du modèle linéaire en prenant en compte les
cas où le modèle ne peut pas expliquer les données de manière unique. Grâce à la pseudo-inverse,
nous avons pu caractériser une solution du problème qui fournit la meilleure erreur d’approximation
au sens des moindres carrés, tout en permettant d’avoir un modèle plus simple au sens de la norme.
Chapitre 4

Régression linéaire

32
Bibliographie

[1] S. Boyd and L. Vandenberghe. Introduction to Applied Linear Algebra - Vectors, Matrices and
Least Squares. Cambridge University Press, Cambridge, United Kingdom, 2018.

[2] S. L. Brunton and J. N. Kutz. Data-Driven Science and Engineering: Machine Learning, Dy-
namical Systems, and Control. Cambridge University Press, Cambridge, United Kingdom, 2019.

[3] G. H. Golub and C. F. Van Loan. Matrix computations. The Johns Hopkins University Press,
Baltimore, fourth edition, 2013.

33