03 · Séance type — ajustement de données¶
Intuition
On dispose de points expérimentaux et l'on cherche la courbe qui « passe au mieux » à travers.
« Au mieux » demande une définition. Le choix universel est celui des moindres carrés : on minimise la somme des carrés des écarts verticaux. Ce choix n'est pas neutre — il privilégie certaines erreurs et en néglige d'autres —, et savoir pourquoi il est fait, c'est déjà la moitié du travail de modélisation.
1. Le problème des moindres carrés¶
Données : \((x_1,y_1),\dots,(x_n,y_n)\). Modèle : \(y \approx f(x;\theta)\) où \(\theta\) est un vecteur de paramètres.
Critère des moindres carrés
On cherche \(\theta\) minimisant
Pourquoi les carrés — trois raisons, toutes bonnes à citer :
- la fonction est dérivable, donc le minimum s'obtient en annulant le gradient (contrairement à la somme des valeurs absolues) ;
- le résultat a une formule close dans le cas linéaire ;
- sous hypothèse d'erreurs gaussiennes indépendantes, c'est l'estimateur du maximum de vraisemblance.
Et pourquoi c'est parfois un mauvais choix
Élever au carré donne un poids quadratique aux grands écarts : un seul point aberrant peut déplacer toute la droite.
Alternatives : minimiser \(\sum|y_i-f(x_i)|\) (régression médiane, robuste), ou écarter les valeurs extrêmes — mais il faut alors le dire et le justifier.
2. Régression linéaire simple¶
Modèle : \(y = ax+b\).
Solution explicite
Démonstration
\(S(a,b) = \sum(y_i-ax_i-b)^2\). On annule les dérivées partielles :
En substituant \(b\) et en réorganisant, on obtient l'expression de \(\hat a\).
\(S\) est un polynôme du second degré en \((a,b)\) à coefficient dominant positif : le point critique est bien un minimum. \(\blacksquare\)
Coefficient de détermination :
Il mesure la part de variance expliquée par le modèle.
\(R^2\) élevé ≠ bon modèle
Un \(R^2\) de 0,99 peut cacher :
- une relation non linéaire que la droite approche localement ;
- un point aberrant qui étire artificiellement l'échelle ;
- un sur-ajustement si le modèle a beaucoup de paramètres.
Il faut toujours regarder les résidus, pas seulement le \(R^2\).
Le quartet d'Anscombe
Quatre jeux de 11 points ayant exactement les mêmes moyennes, mêmes variances, même corrélation, même droite de régression et même \(R^2 = 0{,}67\) — et des formes radicalement différentes : une relation linéaire bruitée, une parabole, une droite parfaite avec un point aberrant, et un nuage vertical avec un point isolé.
C'est la démonstration la plus économique qu'aucun résumé numérique ne remplace l'examen des résidus.
3. Linéarisation¶
Beaucoup de modèles non linéaires deviennent linéaires par changement de variable.
| Modèle | Transformation | Régression linéaire sur |
|---|---|---|
| \(y = Ae^{bx}\) | \(\ln y = \ln A + bx\) | \((x,\ \ln y)\) |
| \(y = Ax^b\) | \(\ln y = \ln A + b\ln x\) | \((\ln x,\ \ln y)\) |
| \(y = \frac{1}{ax+b}\) | \(\frac1y = ax+b\) | \((x,\ 1/y)\) |
| \(y = a\ln x+b\) | — | \((\ln x,\ y)\) |
La linéarisation change ce qu'on minimise
Régresser sur \(\ln y\) minimise \(\sum(\ln y_i - \ln\hat y_i)^2\), c'est-à-dire les erreurs relatives, pas les erreurs absolues.
Conséquence : les petites valeurs de \(y\) pèsent autant que les grandes. Si les erreurs de mesure sont absolues et constantes, la linéarisation biaise le résultat.
C'est acceptable — souvent même souhaitable — mais il faut le dire.
4. Séance type complète¶
Problème. On mesure le temps d'exécution d'un algorithme sur des entrées de taille croissante. Quelle est sa complexité ?
Modélisation. On teste l'hypothèse \(T(n) = C\,n^{\alpha}\), soit après passage au logarithme
Le paramètre d'intérêt est \(\alpha\), l'exposant de complexité. Une régression linéaire sur \((\ln n, \ln T)\) le donne directement comme la pente.
import math
def regression(xs, ys):
"""Moindres carres : renvoie (pente, ordonnee, R2)."""
n = len(xs)
mx, my = sum(xs) / n, sum(ys) / n
sxy = sum((x - mx) * (y - my) for x, y in zip(xs, ys))
sxx = sum((x - mx) ** 2 for x in xs)
syy = sum((y - my) ** 2 for y in ys)
a = sxy / sxx
b = my - a * mx
r2 = sxy ** 2 / (sxx * syy)
return a, b, r2
# donnees simulees : un algorithme en n^2 avec 5 % de bruit multiplicatif
import random
rng = random.Random(4)
tailles = [100, 200, 400, 800, 1600, 3200, 6400]
temps = [1.7e-6 * n**2 * (1 + rng.uniform(-0.05, 0.05)) for n in tailles]
ln_n = [math.log(n) for n in tailles]
ln_t = [math.log(t) for t in temps]
alpha, lnC, r2 = regression(ln_n, ln_t)
print(f"exposant alpha = {alpha:.4f}")
print(f"constante C = {math.exp(lnC):.3e}")
print(f"R2 = {r2:.6f}")
# residus : ils doivent etre sans structure
print("\nresidus (ln) :")
for n, x, y in zip(tailles, ln_n, ln_t):
print(f" n={n:5d} residu = {y - (alpha * x + lnC):+.4f}")
Résultats.
exposant alpha = 2.0119
constante C = 1.542e-06
R2 = 0.999940
residus (ln) :
n= 100 residu = +0.0159
n= 200 residu = -0.0060
n= 400 residu = +0.0158
n= 800 residu = -0.0171
n= 1600 residu = -0.0345
n= 3200 residu = -0.0083
n= 6400 residu = +0.0343
Lecture complète
- \(\alpha = 2{,}012\) : la complexité est en \(n^2\), à 0,6 % près.
- \(R^2 = 0{,}99994\) : le modèle explique la quasi-totalité de la variance.
- Les résidus n'ont aucune structure : ils alternent de signe et restent dans \(\pm0{,}035\), cohérent avec le bruit de \(\pm5\%\) injecté (\(\ln(1{,}05)\approx0{,}049\)).
C'est cette dernière observation qui valide le modèle, pas le \(R^2\).
Ce qu'il faut critiquer dans ce compte rendu
- Les données sont simulées. Sur des mesures réelles, le bruit n'est ni multiplicatif ni uniforme : il y a des effets de cache, de JIT, de planification du système.
- La plage est étroite. Sept points sur deux ordres de grandeur. Un terme en \(n\log n\) serait pratiquement indiscernable de \(n^{1{,}1}\) sur cette plage.
- Le modèle en loi de puissance exclut les termes additifs. Un vrai \(T(n) = an^2+bn+c\) donnerait un \(\alpha\) légèrement inférieur à 2 pour de petites tailles.
Conclusion honnête : « les données sont compatibles avec une complexité quadratique sur la plage testée » — et non « l'algorithme est en \(O(n^2)\) ».
5. Sur-ajustement¶
Le piège du polynôme de haut degré
Avec \(n\) points, un polynôme de degré \(n-1\) passe exactement par tous — interpolation de Lagrange, chapitre Algèbre 06, exercice 8.
Le \(R^2\) vaut alors 1. Et le modèle est inutilisable : il oscille violemment entre les points et diverge dès qu'on sort de la plage.
Un \(R^2\) de 1 est un signal d'alarme, pas de réussite.
Les trois garde-fous
- Parcimonie : le nombre de paramètres doit rester très inférieur au nombre de points. Règle empirique : au moins 10 points par paramètre.
- Validation croisée : ajuster sur une partie des données, évaluer sur le reste.
- Sens physique : un modèle doit être justifiable a priori, pas seulement a posteriori.
Le troisième point est le plus important et le plus négligé : un exposant de complexité doit être 1, \(n\log n\), 2 ou 3 — pas 1,73.
Exercices¶
★★ Exercice 1. Ajuster une droite sur les points \((1,2{,}1)\), \((2,3{,}9)\), \((3,6{,}2)\), \((4,7{,}8)\), \((5,10{,}1)\). Calculer \(\hat a\), \(\hat b\), \(R^2\) et les résidus.
★★★ Exercice 2. On mesure la décroissance d'une quantité :
| \(t\) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| \(y\) | 100 | 74 | 55 | 41 | 30 |
a) Justifier un modèle \(y = Ae^{-\lambda t}\). b) Linéariser et estimer \(A\) et \(\lambda\). c) Calculer la demi-vie. d) Critiquer : que suppose la linéarisation sur les erreurs ?
★★★ Exercice 3. Reconstituer le quartet d'Anscombe et vérifier numériquement que les quatre jeux ont mêmes moyennes, mêmes variances, même corrélation et même droite de régression.
Les données :
x1..x3 = 10, 8, 13, 9, 11, 14, 6, 4, 12, 7, 5
y1 = 8.04, 6.95, 7.58, 8.81, 8.33, 9.96, 7.24, 4.26, 10.84, 4.82, 5.68
y2 = 9.14, 8.14, 8.74, 8.77, 9.26, 8.10, 6.13, 3.10, 9.13, 7.26, 4.74
y3 = 7.46, 6.77, 12.74, 7.11, 7.81, 8.84, 6.08, 5.39, 8.15, 6.42, 5.73
x4 = 8, 8, 8, 8, 8, 8, 8, 19, 8, 8, 8
y4 = 6.58, 5.76, 7.71, 8.84, 8.47, 7.04, 5.25, 12.50, 5.56, 7.91, 6.89
Commenter ce que cela implique pour la pratique.
★★★★ Exercice 4. Générer des données selon \(T(n) = 3n\log_2 n + 50n\) avec 5 % de bruit, puis ajuster un modèle en loi de puissance \(Cn^\alpha\).
a) Quel \(\alpha\) obtient-on ? b) Les résidus révèlent-ils que le modèle est faux ? c) Comment distinguer \(n\log n\) de \(n^{1{,}1}\) expérimentalement ?
★★★★ Exercice 5. Ajuster des polynômes de degrés 1, 3 et 9 sur 10 points bruités issus d'une droite.
a) Comparer les \(R^2\). b) Évaluer chaque modèle sur 10 nouveaux points issus de la même droite. c) Conclure sur le sur-ajustement.
Corrigés¶
Corrigé — Exercice 1
xs = [1, 2, 3, 4, 5]
ys = [2.1, 3.9, 6.2, 7.8, 10.1]
n = len(xs)
mx, my = sum(xs)/n, sum(ys)/n
sxy = sum((x-mx)*(y-my) for x, y in zip(xs, ys))
sxx = sum((x-mx)**2 for x in xs)
syy = sum((y-my)**2 for y in ys)
a = sxy/sxx
b = my - a*mx
r2 = sxy**2/(sxx*syy)
print(f"a={a:.4f} b={b:.4f} R2={r2:.6f}")
for x, y in zip(xs, ys):
print(f" x={x} residu={y-(a*x+b):+.4f}")
Résultats.
a=1.9900 b=0.0500 R2=0.997305
x=1 residu=+0.0600
x=2 residu=-0.1300
x=3 residu=+0.1800
x=4 residu=-0.2100
x=5 residu=+0.1000
Droite ajustée : \(y = 1{,}99x + 0{,}05\), avec \(R^2 = 0{,}9973\).
Lecture des résidus : ils sont petits (au plus 0,21) et alternent strictement de signe — le modèle linéaire est adapté, le bruit domine.
L'alternance parfaite des signes est un peu suspecte sur cinq points, mais largement dans les limites du hasard.
Corrigé — Exercice 2
a) Justification du modèle. Une décroissance exponentielle correspond à l'hypothèse que la vitesse de décroissance est proportionnelle à la quantité restante :
(chapitre Analyse 03, exercice 8.)
C'est le modèle de la désintégration radioactive, de la décharge d'un condensateur, de l'élimination d'un médicament.
Vérification rapide : les rapports successifs valent \(\frac{74}{100}=0{,}74\), \(\frac{55}{74}=0{,}743\), \(\frac{41}{55}=0{,}745\), \(\frac{30}{41}=0{,}732\) — quasiment constants, ce qui est la signature d'une exponentielle ✓
b) Linéarisation.
import math
ts = [0, 1, 2, 3, 4]
ys = [100, 74, 55, 41, 30]
ln_y = [math.log(y) for y in ys]
n = len(ts)
mt, ml = sum(ts)/n, sum(ln_y)/n
stl = sum((t-mt)*(l-ml) for t, l in zip(ts, ln_y))
stt = sum((t-mt)**2 for t in ts)
pente = stl/stt
ordo = ml - pente*mt
lam = -pente
A = math.exp(ordo)
print(f"lambda = {lam:.4f} A = {A:.2f}")
print(f"demi-vie = {math.log(2)/lam:.3f}")
Résultats.
lambda = 0.2998 A = 100.08
demi-vie = 2.312
c) Demi-vie : \(t_{1/2} = \frac{\ln2}{\lambda} \approx 2{,}31\) unités de temps. La valeur \(A \approx 100{,}1\) est cohérente avec la mesure initiale de 100 ✓
d) Critique de la linéarisation.
Régresser sur \(\ln y\) minimise \(\sum(\ln y_i - \ln\hat y_i)^2\), ce qui revient à minimiser les erreurs relatives.
- Si les erreurs de mesure sont proportionnelles à \(y\) (bruit multiplicatif de \(\pm5\%\)), c'est exactement le bon choix.
- Si elles sont absolues (\(\pm2\) unités quelle que soit la valeur), la linéarisation surpondère les petites valeurs — ici les mesures tardives — et biaise l'estimation de \(\lambda\).
Comment trancher : regarder si la dispersion des mesures répétées croît avec \(y\). Si oui, bruit multiplicatif, linéarisation légitime.
Sinon, il faut un ajustement non linéaire direct, minimisant \(\sum(y_i - Ae^{-\lambda t_i})^2\) par une méthode itérative (Gauss-Newton, Levenberg-Marquardt).
Corrigé — Exercice 3
x123 = [10, 8, 13, 9, 11, 14, 6, 4, 12, 7, 5]
y1 = [8.04, 6.95, 7.58, 8.81, 8.33, 9.96, 7.24, 4.26, 10.84, 4.82, 5.68]
y2 = [9.14, 8.14, 8.74, 8.77, 9.26, 8.10, 6.13, 3.10, 9.13, 7.26, 4.74]
y3 = [7.46, 6.77, 12.74, 7.11, 7.81, 8.84, 6.08, 5.39, 8.15, 6.42, 5.73]
x4 = [8, 8, 8, 8, 8, 8, 8, 19, 8, 8, 8]
y4 = [6.58, 5.76, 7.71, 8.84, 8.47, 7.04, 5.25, 12.50, 5.56, 7.91, 6.89]
def stats(xs, ys):
n = len(xs)
mx, my = sum(xs)/n, sum(ys)/n
vx = sum((x-mx)**2 for x in xs)/(n-1)
vy = sum((y-my)**2 for y in ys)/(n-1)
sxy = sum((x-mx)*(y-my) for x, y in zip(xs, ys))
sxx = sum((x-mx)**2 for x in xs)
syy = sum((y-my)**2 for y in ys)
a = sxy/sxx
return mx, my, vx, vy, a, my-a*mx, sxy**2/(sxx*syy)
for i, (xs, ys) in enumerate([(x123,y1),(x123,y2),(x123,y3),(x4,y4)], 1):
mx, my, vx, vy, a, b, r2 = stats(xs, ys)
print(f"jeu {i}: mx={mx:.2f} my={my:.2f} vx={vx:.2f} vy={vy:.3f} "
f"y={a:.3f}x+{b:.3f} R2={r2:.3f}")
Résultats.
jeu 1: mx=9.00 my=7.50 vx=11.00 vy=4.127 y=0.500x+3.000 R2=0.667
jeu 2: mx=9.00 my=7.50 vx=11.00 vy=4.128 y=0.500x+3.001 R2=0.666
jeu 3: mx=9.00 my=7.50 vx=11.00 vy=4.123 y=0.500x+3.002 R2=0.666
jeu 4: mx=9.00 my=7.50 vx=11.00 vy=4.123 y=0.500x+3.002 R2=0.667
Les quatre jeux sont numériquement indiscernables : mêmes moyennes, mêmes variances, même droite \(y=0{,}5x+3\), même \(R^2=0{,}67\).
Et pourtant :
- jeu 1 : relation linéaire bruitée — le modèle est correct ;
- jeu 2 : relation parabolique parfaite — un modèle linéaire est absurde ;
- jeu 3 : relation linéaire exacte sauf un point aberrant qui tire la droite ;
- jeu 4 : \(x\) constant sauf un point ; la droite est entièrement déterminée par une seule observation.
L'implication pratique
Les statistiques descriptives — moyenne, variance, corrélation, \(R^2\) — ne caractérisent pas les données. Deux jeux radicalement différents peuvent les partager toutes.
Il faut regarder les résidus, systématiquement. Un tableau de chiffres ne remplace jamais un graphique.
Corrigé — Exercice 4
import math
import random
def regression(xs, ys):
n = len(xs)
mx, my = sum(xs)/n, sum(ys)/n
sxy = sum((x-mx)*(y-my) for x, y in zip(xs, ys))
sxx = sum((x-mx)**2 for x in xs)
syy = sum((y-my)**2 for y in ys)
a = sxy/sxx
return a, my-a*mx, sxy**2/(sxx*syy)
rng = random.Random(8)
tailles = [2**k for k in range(7, 21)] # 128 .. 1 048 576
temps = [(3*n*math.log2(n) + 50*n) * (1 + rng.uniform(-0.05, 0.05))
for n in tailles]
ln_n = [math.log(n) for n in tailles]
ln_t = [math.log(t) for t in temps]
alpha, lnC, r2 = regression(ln_n, ln_t)
print(f"alpha = {alpha:.4f} R2 = {r2:.6f}")
print("residus :")
for n, x, y in zip(tailles, ln_n, ln_t):
print(f" n={n:>8} {y-(alpha*x+lnC):+.4f}")
Résultats.
alpha = 1.0494 R2 = 0.999893
residus :
n= 128 -0.0356
n= 256 +0.0444
n= 512 -0.0333
n= 1024 +0.0290
n= 2048 -0.0311
n= 4096 -0.0131
n= 8192 +0.0613
n= 16384 -0.0180
n= 32768 +0.0234
n= 65536 +0.0020
n= 131072 -0.0027
n= 262144 -0.0034
n= 524288 -0.0400
n= 1048576 +0.0172
a) \(\alpha \approx 1{,}05\) — le modèle en loi de puissance « voit » la complexité comme \(n^{1{,}05}\).
b) Les résidus ne révèlent rien. Ils oscillent dans \(\pm0{,}06\), sans tendance nette, ce qui est du même ordre que le bruit injecté. Le \(R^2 = 0{,}99989\) est excellent.
Le modèle est faux, et les diagnostics usuels ne le détectent pas.
c) Comment distinguer. Trois approches.
- Élargir la plage. L'exposant apparent de \(n\log n\) vaut \(1+\frac{1}{\ln n}\) : il décroît lentement avec \(n\). En ajustant séparément sur \([10^2;10^4]\) et \([10^5;10^7]\), on doit voir \(\alpha\) diminuer — ce qu'un vrai \(n^{1{,}09}\) ne ferait pas.
- Ajuster directement les deux modèles et comparer les sommes de carrés résiduelles, en pénalisant le nombre de paramètres (critère AIC/BIC).
- Tracer \(\frac{T(n)}{n}\) en fonction de \(\ln n\). Pour \(n\log n\), c'est une droite ; pour \(n^{1{,}05}\), c'est une exponentielle. C'est le diagnostic le plus lisible.
La leçon
Un bon \(R^2\) ne valide pas un modèle — il valide seulement qu'il n'est pas grossièrement faux sur la plage testée.
Le choix entre \(n\log n\) et \(n^{1{,}05}\) ne se tranche pas statistiquement : il se tranche par l'analyse de l'algorithme. C'est le troisième garde-fou du §5 — le sens a priori.
Corrigé — Exercice 5
import random
def ajuster_polynome(xs, ys, degre):
"""Moindres carres polynomial par equations normales + pivot de Gauss."""
d = degre
# matrice de Vandermonde^T * Vandermonde
A = [[sum(x**(i+j) for x in xs) for j in range(d+1)] for i in range(d+1)]
B = [sum(y * x**i for x, y in zip(xs, ys)) for i in range(d+1)]
# pivot de Gauss avec pivot partiel
n = d + 1
for k in range(n):
p = max(range(k, n), key=lambda i: abs(A[i][k]))
A[k], A[p] = A[p], A[k]
B[k], B[p] = B[p], B[k]
for i in range(k+1, n):
f = A[i][k] / A[k][k]
for j in range(k, n):
A[i][j] -= f * A[k][j]
B[i] -= f * B[k]
c = [0.0] * n
for i in reversed(range(n)):
c[i] = (B[i] - sum(A[i][j]*c[j] for j in range(i+1, n))) / A[i][i]
return c
def evaluer(c, x):
return sum(ci * x**i for i, ci in enumerate(c))
def sce(c, xs, ys):
return sum((y - evaluer(c, x))**2 for x, y in zip(xs, ys))
rng = random.Random(21)
vrai = lambda x: 2*x + 1
xs = [i/9 for i in range(10)] # 10 points sur [0,1]
ys = [vrai(x) + rng.gauss(0, 0.1) for x in xs]
# jeu de validation : memes abscisses, nouveau bruit
ys_val = [vrai(x) + rng.gauss(0, 0.1) for x in xs]
var_tot = sum((y - sum(ys)/len(ys))**2 for y in ys)
for d in (1, 3, 9):
c = ajuster_polynome(xs, ys, d)
s_app = sce(c, xs, ys)
s_val = sce(c, xs, ys_val)
print(f"degre {d}: R2={1-s_app/var_tot:.6f} "
f"SCE apprentissage={s_app:.5f} SCE validation={s_val:.5f}")
Résultats.
degre 1: R2=0.979677 SCE apprentissage=0.07633 SCE validation=0.05656
degre 3: R2=0.980405 SCE apprentissage=0.07360 SCE validation=0.04931
degre 9: R2=1.000000 SCE apprentissage=0.00000 SCE validation=0.16071
a) Les \(R^2\) augmentent avec le degré : \(0{,}9797 \to 0{,}9804 \to 1{,}0000\). Le degré 9 passe exactement par les 10 points.
b) Sur les nouvelles données, le classement s'inverse pour le degré 9 :
| Degré | Erreur d'apprentissage | Erreur de validation |
|---|---|---|
| 1 | 0,0763 | 0,0566 |
| 3 | 0,0736 | 0,0493 |
| 9 | 0,0000 | 0,1607 |
Le degré 9 est 2,8 fois pire que le degré 1 en validation, alors qu'il est parfait en apprentissage.
Les degrés 1 et 3 sont, eux, indiscernables : avec seulement 10 points, le degré 3 n'est pas encore assez souple pour sur-ajuster.
c) Conclusion. C'est la définition même du sur-ajustement : le modèle a appris le bruit au lieu du signal.
La seule mesure honnête de la qualité d'un modèle est son erreur sur des données qu'il n'a pas vues. Le \(R^2\) d'apprentissage ne mesure que la capacité du modèle à mémoriser.
Où cela mène
Ce constat est le fondement de tout l'apprentissage automatique : séparation apprentissage/validation/test, validation croisée, régularisation.
La régression ridge et le lasso, enseignés en deuxième année dans le module MERR23, sont précisément des techniques pour empêcher ce phénomène en pénalisant les coefficients trop grands.
Chapitre suivant : Séance type — graphes et matrices.