Situez votre modèle face à la machine de Bayes

Votre droite prédit les salaires avec une erreur quadratique moyenne de, disons, 24 k$² sur la population. Est-ce bien ou mal ? Impossible de répondre sans un point de comparaison. Et le plus parlant de tous serait : quelle est la meilleure erreur possible, celle qu’aucune machine, aussi géniale soit-elle, ne pourrait battre ?

C’est l’étape 8 de la roue, l’analyse théorique. Dans ce chapitre, vous allez rencontrer la machine de Bayes, qui atteint cette erreur minimale, et apprendre à découper l’écart entre votre modèle et elle en deux morceaux qui ne se soignent pas de la même façon.

La meilleure machine possible

Reprenons le cadre du chapitre 2. La population est décrite par une loi $P_{XY}$ inconnue, la perte $\ell$ est fixée, et le risque d’une fonction $f$ est $R(f) = \mathbb{E}[\ell(Y, f(X))]$. Cette fois, oublions toute restriction : cherchons la meilleure fonction dans l’univers $\mathcal{Y}^{\mathcal{X}}$ de toutes les fonctions possibles.

$$f^* = \arg\min_{f \in \mathcal{Y}^{\mathcal{X}}} R(f), \qquad R^* = R(f^*)$$

• $f^*$ s’appelle la machine de Bayes (Bayes learner, ou règle de Bayes) ;
• $R^*$ est le risque de Bayes : la plus petite erreur atteignable pour ce problème et cette perte.

Pour les pertes usuelles (quadratique $L_2$, absolue $L_1$, 0-1), cette machine existe et l’on sait l’écrire. Pourquoi $R^*$ n’est-il pas nul ? Parce que $X$ ne détermine pas complètement $Y$. Deux diplômés qui ont exactement le même GPA ne gagnent pas le même salaire : l’un a fait un stage chez un grand groupe, l’autre a choisi une association, un troisième a mieux négocié. Tout ce que $X$ ne mesure pas se comporte, vu de $X$, comme du bruit. $R^*$ mesure ce bruit.

À retenir

La machine de Bayes $f^*$ est la meilleure fonction possible, sans aucune restriction. Son risque $R^*$ est un plancher : il dépend du problème (de ce que $X$ dit de $Y$), pas de l’algorithme. On ne peut le faire baisser qu’en ajoutant de l’information, c’est-à-dire de nouvelles variables.

Sa forme dépend de la perte

Voici le résultat central : la machine de Bayes change de visage avec la perte.

Perte	Machine de Bayes $f^*(x)$	En mots
Quadratique ($L_2$)	$\mathbb{E}[Y \mid X = x]$	le salaire moyen des diplômés de GPA $x$
Absolue ($L_1$)	la médiane de $Y$ sachant $X = x$	le salaire médian des diplômés de GPA $x$
0-1 (classification)	$\arg\max_y P(Y = y \mid X = x)$	la classe la plus probable sachant $x$

On retrouve, point par point, ce que vous avez vu au chapitre 2 pour une constante (moyenne pour $L_2$, médiane pour $L_1$). La différence : on calcule maintenant la moyenne ou la médiane à $x$ fixé, pour chaque valeur de $x$.

En régression, l’espérance conditionnelle

Pour la perte quadratique, la machine de Bayes est l’espérance conditionnelle :

$$f^*(x) = \mathbb{E}[Y \mid X = x] = \int y \, p(y \mid x) \, dy$$

où $p(y \mid x)$ est la densité des salaires parmi les diplômés de GPA $x$. Attention à la nuance : c’est l’espérance de $Y$ sachant $X = x$, pas l’espérance de $Y$ tout court (qui serait le salaire moyen de toute la population, sans tenir compte du GPA).

Pourquoi ce choix est-il optimal ? Pour n’importe quelle fonction $f$, on peut montrer (exercice 3) que

$$R(f) = R^* + \mathbb{E}\Big[\big(f(X) - f^*(X)\big)^2\Big]$$

Le second terme est positif et ne s’annule que si $f = f^*$ (presque partout). Autrement dit, le risque de n’importe quelle fonction est le risque de Bayes plus sa distance quadratique moyenne à $f^*$. Si le salaire s’écrit $Y = f^*(X) + \varepsilon$, avec un bruit $\varepsilon$ de moyenne nulle et de variance $\sigma^2$, alors $R^* = \sigma^2$.

La machine de Bayes passe par le centre de chaque densité conditionnelle p(y | x) : c'est le salaire moyen à GPA fixé. La dispersion autour d'elle (variance 16) est le risque de Bayes, qu'aucune machine ne peut réduire. La meilleure droite ajoute 7,85 d'erreur d'approximation.

En classification, la classe la plus probable

Pour la perte 0-1, se tromper coûte 1 quelle que soit l’erreur. La meilleure décision, pour un $x$ donné, est donc la classe qui a le plus de chances d’être la bonne. L’erreur de Bayes vaut alors, en moyenne sur les $x$, la probabilité de ne pas être dans cette classe :

$$R^* = \mathbb{E}\Big[1 - \max_y P(Y = y \mid X)\Big]$$

Exemple

Transformons notre problème en classification : on veut prédire si le premier salaire dépasse 60 k$ ($Y = 1$) ou non ($Y = 0$), à partir de la tranche de GPA. Supposons que l’on connaisse la population (ce qui n’arrive jamais, mais permet de calculer) :

Tranche de GPA	$P(X = x)$	$P(Y = 1 \mid X = x)$	$f^*(x)$	Erreur dans la tranche
bas (moins de 3)	0,3	0,20	0	0,20
moyen (3 à 3,5)	0,5	0,45	0	0,45
haut (3,5 et plus)	0,2	0,80	1	0,20

La machine de Bayes prédit « plus de 60 k$ » seulement pour la tranche haute. Son erreur est la moyenne des erreurs par tranche, pondérée par la taille des tranches :

$$R^* = 0{,}3 \times 0{,}20 + 0{,}5 \times 0{,}45 + 0{,}2 \times 0{,}20 = 0{,}06 + 0{,}225 + 0{,}04 = 0{,}325$$

Même en connaissant parfaitement la population, on se trompe une fois sur trois. C’est normal : la tranche de GPA ne dit pas grand-chose du salaire.

Chaque colonne est une tranche de GPA, de largeur P(X = x). La machine de Bayes prédit la classe majoritaire de la colonne ; les hachures sont ses erreurs, et leur aire totale vaut R* = 0,3 × 0,20 + 0,5 × 0,45 + 0,2 × 0,20 = 0,325.

Attention

On ne peut pas calculer la machine de Bayes en pratique : elle dépend de $P_{XY}$, que l’on ne connaît pas. Elle sert de référence théorique, et c’est déjà beaucoup. Le classifieur bayésien naïf, présenté dans le cours d’Apprentissage automatique, est une tentative d’en construire une approximation en estimant $P(Y \mid X)$ avec des hypothèses simplificatrices.

Trois fonctions, deux écarts

Nous avons maintenant trois fonctions en main, qu’il ne faut surtout pas confondre :

• $f^*$, la machine de Bayes : la meilleure dans tout l’univers $\mathcal{Y}^{\mathcal{X}}$ ;
• $f^\diamond_{\mathcal{H}}$ (lisez « f diamant »), la meilleure de l’espace $\mathcal{H}$ : la fonction de $\mathcal{H}$ qui minimise le vrai risque ;
• $\hat{f}_{\mathcal{H}, D_n}$, la machine apprise : celle de $\mathcal{H}$ qui minimise le risque empirique sur nos $n$ données.

L’écart entre le risque de la machine apprise et le plancher $R^*$, qu’on appelle l’excès de risque, se découpe exactement en deux :

$$R(\hat{f}_{\mathcal{H}, D_n}) - R^* = \underbrace{R(\hat{f}_{\mathcal{H}, D_n}) - R(f^\diamond_{\mathcal{H}})}_{\text{erreur d'estimation}} + \underbrace{R(f^\diamond_{\mathcal{H}}) - R^*}_{\text{erreur d'approximation}}$$

Chaque terme a une cause précise.

• L’erreur d’approximation vient de $\mathcal{H}$ : on ne cherche que dans une fraction de l’univers. Si la vraie relation est courbe et que $\mathcal{H}$ ne contient que des droites, même la meilleure droite reste loin de $f^*$. Elle ne dépend pas des données.
• L’erreur d’estimation vient de $D_n$ : on ne dispose que d’une fraction de la population. Avec d’autres diplômés, on aurait appris une autre droite. C’est le prix de l’inférence, du passage de l’échantillon à la population. Elle diminue quand $n$ augmente.

Exemple

Reprenons la classification par tranche de GPA, avec l’espace le plus pauvre : $\mathcal{H}$ = les constantes (on prédit la même classe pour tout le monde, sans regarder le GPA).

• Dans la population, $P(Y = 1) = 0{,}3 \times 0{,}20 + 0{,}5 \times 0{,}45 + 0{,}2 \times 0{,}80 = 0{,}445$. La meilleure constante prédit donc toujours 0, avec un risque $R(f^\diamond_{\mathcal{H}}) = 0{,}445$. L’erreur d’approximation vaut $0{,}445 - 0{,}325 = 0{,}12$.
• Sur un petit échantillon de 20 diplômés, il se peut que plus de la moitié gagnent plus de 60 k$, par hasard. La machine apprise prédit alors toujours 1, avec un vrai risque de $0{,}555$. L’erreur d’estimation vaut $0{,}555 - 0{,}445 = 0{,}11$.

Excès de risque total : $0{,}555 - 0{,}325 = 0{,}23 = 0{,}12 + 0{,}11$.

Les chiffres de l'exemple : partant du plancher R* = 0,325, se restreindre aux constantes coûte 0,12 (approximation), et n'avoir que 20 diplômés coûte encore 0,11 (estimation).

En entretien

« L’écart entre mon modèle et le meilleur possible a deux sources : l’erreur d’approximation, parce que ma famille de modèles est trop restreinte, et l’erreur d’estimation, parce que je n’ai qu’un échantillon fini. Enrichir le modèle réduit la première mais augmente la seconde ; c’est tout le compromis biais-variance. »

Réduire l’erreur d’approximation : le théorème de Weierstrass

Peut-on rendre l’erreur d’approximation aussi petite que l’on veut ? Pour les polynômes, un théorème classique d’analyse répond oui.

Théorème de Weierstrass. Toute fonction continue sur un segment $[a, b]$ peut être approchée uniformément d’aussi près que l’on veut par un polynôme : pour tout $\varepsilon > 0$, il existe un polynôme $P$ tel que $\lvert f(x) - P(x) \rvert \le \varepsilon$ pour tout $x \in [a, b]$.

Appliqué à notre problème : si le salaire moyen $f^*(x) = \mathbb{E}[Y \mid X = x]$ varie continûment avec le GPA, alors en prenant pour $\mathcal{H}$ les polynômes de degré $p$ assez grand, on peut rendre l’erreur d’approximation aussi faible que l’on veut. On a donc une échelle d’espaces emboîtés, les polynômes de degré 0, 1, 2…, dont l’erreur d’approximation tend vers 0.

Exemple

Supposons que, dans la population, le salaire moyen plafonne quand le GPA augmente : $f^*(x) = 70 - 25\,e^{-2(x - 2)}$ pour des GPA $x$ entre 2 et 4 (répartis uniformément), avec un bruit de variance $\sigma^2 = 16$ autour de cette courbe, donc $R^* = 16$. Pour chaque degré $p$, on calcule numériquement la meilleure approximation polynomiale de $f^*$ au sens quadratique, c’est-à-dire l’erreur d’approximation $\mathbb{E}\big[(f^\diamond_{\mathcal{H}}(X) - f^*(X))^2\big]$ :

Degré $p$	0	1	2	3	4
Erreur d’approximation (k$²)	40,45	7,85	0,76	0,044	0,0017

La meilleure droite a donc un vrai risque de $16 + 7{,}85 \approx 23{,}85$ k$² : c’est le « 24 » de l’introduction. Dès le degré 3, l’erreur d’approximation est négligeable devant le bruit.

Chaque degré en plus colle davantage à f* : l'erreur d'approximation est divisée par 5 à 20 à chaque pas, et passe sous le bruit R* = 16 dès le degré 1. Dès le degré 3, la courbe est indiscernable de f*.

Attention

On présente parfois ce résultat comme un « théorème d’approximation universelle ». Ce nom désigne plus couramment un résultat analogue pour les réseaux de neurones (un réseau à une couche cachée assez large approche toute fonction continue sur un compact). L’idée est la même : certaines familles de modèles sont assez riches pour tout approcher. Retenez aussi que Weierstrass garantit l’existence d’un bon polynôme, pas qu’on saura le trouver avec peu de données.

Peut-on connaître l’erreur d’approximation de son propre modèle ? En général, non : il faudrait connaître $f^*$. La théorie de l’approximation donne des vitesses (l’erreur décroît d’autant plus vite avec $p$ que $f^*$ est régulière), mais sous des hypothèses que l’on ne peut pas vérifier sur des données réelles. En pratique, on l’observe indirectement : un modèle qui se trompe beaucoup même sur ses données d’apprentissage souffre d’une forte erreur d’approximation.

Le prix d’un espace plus grand

Si Weierstrass nous autorise à rendre l’erreur d’approximation aussi petite que l’on veut, pourquoi ne pas prendre un polynôme de degré 50 ? Parce que l’erreur d’estimation, elle, augmente avec la taille de $\mathcal{H}$. Plus l’espace est riche, plus il contient de fonctions capables de coller au hasard de l’échantillon, et plus la machine apprise $\hat{f}$ risque de s’éloigner de $f^\diamond_{\mathcal{H}}$.

Quand on…	Erreur d’approximation	Erreur d’estimation	$R^*$
agrandit $\mathcal{H}$ (degré plus élevé)	baisse	monte	inchangé
augmente $n$ (plus de diplômés)	inchangée	baisse	inchangé
ajoute une variable (la filière)	peut changer	monte un peu	baisse (plus d’information)

C’est exactement le dilemme biais-variance, que le chapitre suivant rend quantitatif. Retenez d’ici là qu’il n’y a pas d’espace d’hypothèses « le meilleur dans l’absolu » : le bon choix dépend de la quantité de données.

En résumé

• La machine de Bayes $f^*$ minimise le risque sur l’univers de toutes les fonctions ; son risque $R^*$ est le plus petit possible et ne dépend que du problème.
• Pour la perte quadratique, $f^*(x) = \mathbb{E}[Y \mid X = x]$ ; pour la perte absolue, c’est la médiane conditionnelle ; pour la perte 0-1, c’est la classe la plus probable sachant $x$.
• $f^*$ est incalculable en pratique, car $P_{XY}$ est inconnue ; elle sert de référence.
• L’excès de risque $R(\hat{f}) - R^*$ se décompose en erreur d’estimation (échantillon fini) et erreur d’approximation (espace $\mathcal{H}$ restreint), avec $f^\diamond_{\mathcal{H}}$ la meilleure fonction de $\mathcal{H}$.
• Le théorème de Weierstrass garantit qu’avec des polynômes de degré assez élevé, l’erreur d’approximation d’une fonction continue devient aussi petite que l’on veut.
• Agrandir $\mathcal{H}$ réduit l’erreur d’approximation mais augmente l’erreur d’estimation ; seule une information nouvelle fait baisser $R^*$.

Exercices

Exercice · Calculer une erreur de Bayes

facile

Un recruteur classe les candidatures en « entretien » ($Y = 1$) ou « refus » ($Y = 0$) selon l’école d’origine, A ou B. Dans la population : 60 % des candidats viennent de A, et 90 % d’entre eux obtiennent un entretien ; 40 % viennent de B, et 30 % d’entre eux obtiennent un entretien. Donnez la machine de Bayes pour la perte 0-1 et son risque $R^*$.

Voir la solution

• Pour l’école A, $P(Y = 1 \mid A) = 0{,}9 > 0{,}5$ : $f^*(A) = 1$, avec une erreur de $0{,}1$ dans ce groupe.
• Pour l’école B, $P(Y = 1 \mid B) = 0{,}3 < 0{,}5$ : $f^*(B) = 0$, avec une erreur de $0{,}3$ dans ce groupe.

$R^* = 0{,}6 \times 0{,}1 + 0{,}4 \times 0{,}3 = 0{,}06 + 0{,}12 = 0{,}18$. Aucune règle fondée sur la seule école ne peut se tromper moins de 18 % du temps.

En code

Python

import numpy as np

p_ecole = np.array([0.6, 0.4])                    # P(A), P(B)
p_entretien = np.array([0.9, 0.3])                # P(Y = 1 | école)

f_bayes = (p_entretien > 0.5).astype(int)         # classe la plus probable par école
erreur = np.minimum(p_entretien, 1 - p_entretien) # erreur dans chaque groupe
print(f_bayes, erreur)                            # [1 0]  [0.1 0.3]
print(round(np.sum(p_ecole * erreur), 2))         # R* = 0.18

R

p_ecole <- c(A = 0.6, B = 0.4)
p_entretien <- c(A = 0.9, B = 0.3)                # P(Y = 1 | école)

f_bayes <- as.integer(p_entretien > 0.5)          # classe la plus probable par école
erreur <- pmin(p_entretien, 1 - p_entretien)      # erreur dans chaque groupe
f_bayes; erreur                                   # 1 0   0.1 0.3
sum(p_ecole * erreur)                             # R* = 0.18

Exercice · Quelle erreur a changé ?

moyen

Pour chaque décision, dites si elle agit sur l’erreur d’approximation, l’erreur d’estimation ou le risque de Bayes $R^*$, et dans quel sens.

1. Passer de 200 à 2 000 diplômés, en gardant des droites.
2. Passer des droites aux polynômes de degré 3, avec les mêmes 200 diplômés.
3. Ajouter la filière comme seconde variable explicative.
4. Dans l’exemple du salaire qui plafonne, vérifier que l’erreur d’approximation des constantes (40,45) est égale à la variance de $f^*(X)$. Pourquoi est-ce logique ?

Voir la solution

1. L’erreur d’estimation baisse (plus de données, droite apprise plus proche de la meilleure droite). L’erreur d’approximation est inchangée : c’est toujours l’espace des droites.
2. L’erreur d’approximation baisse (de 7,85 à 0,044 dans notre exemple), mais l’erreur d’estimation monte : quatre paramètres à estimer au lieu de deux, avec les mêmes données.
3. Le risque de Bayes baisse, ou au pire reste égal : on donne plus d’information sur $Y$, donc le plancher descend. Mais l’espace d’hypothèses change aussi, avec plus de paramètres, donc l’erreur d’estimation augmente un peu.
4. Pour la perte quadratique, la meilleure constante est $c = \mathbb{E}[f^*(X)]$ (la moyenne, comme au chapitre 2, appliquée à $f^*(X)$). L’erreur d’approximation vaut donc $\mathbb{E}[(f^*(X) - \mathbb{E}[f^*(X)])^2]$, qui est exactement la variance de $f^*(X)$ : ce que la constante ne peut pas capter, c’est précisément la variation du salaire moyen avec le GPA.

En code

Python

import numpy as np
from scipy.integrate import quad

f_star = lambda x: 70 - 25 * np.exp(-2 * (x - 2))  # salaire moyen, X uniforme sur [2, 4]
densite = 1 / 2

# Question 4 : meilleure constante = E[f*(X)], erreur d'approximation = Var(f*(X))
esperance = quad(lambda x: f_star(x) * densite, 2, 4)[0]
variance = quad(lambda x: (f_star(x) - esperance) ** 2 * densite, 2, 4)[0]
print(round(esperance, 2), round(variance, 2))   # 63.86  40.45

# Vérification par balayage des constantes c
c = np.linspace(50, 65, 1501)
erreur = [quad(lambda x: (f_star(x) - ci) ** 2 * densite, 2, 4)[0] for ci in c]
print(round(c[np.argmin(erreur)], 2), round(min(erreur), 2))   # 63.86  40.45

R

f_star <- function(x) 70 - 25 * exp(-2 * (x - 2))  # salaire moyen, X uniforme sur [2, 4]
densite <- 1 / 2

# Question 4 : meilleure constante = E[f*(X)], erreur d'approximation = Var(f*(X))
esperance <- integrate(function(x) f_star(x) * densite, 2, 4)$value
variance <- integrate(function(x) (f_star(x) - esperance)^2 * densite, 2, 4)$value
c(esperance, variance)                            # 63.86  40.45

# Vérification : la constante qui minimise l'erreur quadratique
erreur <- function(c) integrate(function(x) (f_star(x) - c)^2 * densite, 2, 4)$value
optimize(erreur, c(50, 65))                       # minimum 63.86, objectif 40.45

Exercice · Pourquoi l'espérance conditionnelle ?

difficile

On note $f^*(x) = \mathbb{E}[Y \mid X = x]$. Montrez que, pour toute fonction $f$,

$$\mathbb{E}\big[(Y - f(X))^2\big] = \mathbb{E}\big[(Y - f^*(X))^2\big] + \mathbb{E}\big[(f^*(X) - f(X))^2\big]$$

et concluez que $f^*$ est la machine de Bayes pour la perte quadratique. On pourra écrire $Y - f(X) = (Y - f^*(X)) + (f^*(X) - f(X))$.

Voir la solution

On développe le carré :

$$(Y - f(X))^2 = (Y - f^*(X))^2 + (f^*(X) - f(X))^2 + 2\,(Y - f^*(X))(f^*(X) - f(X))$$

Il suffit de montrer que le double produit est d’espérance nulle. Conditionnons par $X$ : sachant $X$, le facteur $g(X) = f^*(X) - f(X)$ est connu, donc

$$\mathbb{E}\big[(Y - f^*(X))\,g(X) \mid X\big] = g(X)\,\big(\mathbb{E}[Y \mid X] - f^*(X)\big) = g(X) \times 0 = 0$$

En prenant l’espérance (propriété de l’espérance totale), le double produit a une espérance nulle, d’où l’égalité annoncée.

Le premier terme de droite ne dépend pas de $f$, et le second est positif ou nul. Le risque est donc minimal quand le second terme est nul, c’est-à-dire quand $f(X) = f^*(X)$ presque sûrement. La machine de Bayes pour la perte quadratique est bien l’espérance conditionnelle, et $R^* = \mathbb{E}[(Y - f^*(X))^2]$.

En code

Python

import numpy as np

rng = np.random.default_rng(0)
n = 1_000_000
x = rng.uniform(2, 4, n)
f_star = lambda x: 70 - 25 * np.exp(-2 * (x - 2))  # E[Y | X = x]
y = f_star(x) + rng.normal(0, 4, n)               # bruit de variance 16

f = lambda x: 24 + 11 * x                         # une fonction quelconque
gauche = np.mean((y - f(x)) ** 2)
droite = np.mean((y - f_star(x)) ** 2) + np.mean((f_star(x) - f(x)) ** 2)
double_produit = np.mean(2 * (y - f_star(x)) * (f_star(x) - f(x)))
print(round(gauche, 2), round(droite, 2))         # 71.37  71.32 : égaux au bruit près
print(round(double_produit, 3))                   # 0.05 : proche de 0 (l'écart entre les deux)

R

set.seed(0)
n <- 1e6
x <- runif(n, 2, 4)
f_star <- function(x) 70 - 25 * exp(-2 * (x - 2))  # E[Y | X = x]
y <- f_star(x) + rnorm(n, 0, 4)                   # bruit de variance 16

f <- function(x) 24 + 11 * x                      # une fonction quelconque
gauche <- mean((y - f(x))^2)
droite <- mean((y - f_star(x))^2) + mean((f_star(x) - f(x))^2)
double_produit <- mean(2 * (y - f_star(x)) * (f_star(x) - f(x)))
c(gauche, droite)                                 # 71.45  71.40 : égaux au bruit près
double_produit                                    # 0.042 : proche de 0