Statistique et apprentissage · 2016-03-09 · Ce document contient les notes du cours Statistique et apprentissage donné dans le cadre de la spécialité Probabilités et modèles

Statistique et apprentissage

Gérard Biau

2014-2015

Ce document contient les notes du cours Statistique et apprentissage donnédans le cadre de la spécialité Probabilités et modèles aléatoires du masterMathématiques et applications de l’UPMC. Son contenu s’inspire pour toutou partie des ouvrages suivants :

. B. Cadre et C. Vial. (2012). Statistique mathématique - Master 1 et Agré-gation, Ellipse, Paris.

. V. Rivoirard et G. Stoltz (2012). Statistique en action (seconde édition),Vuibert, Paris.

. L. Devroye, L. Györfi et G. Lugosi (1996). A probabilistic theory of pat-tern recognition, Springer, New York.

Nous invitons le lecteur à se procurer ces trois manuels, dans lesquels iltrouvera approfondissements, compléments et exercices variés.

—G. Biau

Table des matières

1 Modélisation statistique 51.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Modèle statistique . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Estimation paramétrique 82.1 Estimateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Construction d’estimateurs . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Méthode des moments . . . . . . . . . . . . . . . . . . . 92.2.2 Méthode du maximum de vraisemblance . . . . . . . . 11

2.3 Critères de performance en moyenne . . . . . . . . . . . . . . 152.4 Critères de performance asymptotique . . . . . . . . . . . . . 172.5 Asymptotique de l’erreur d’estimation . . . . . . . . . . . . . . 19

3 Intervalles de confiance 233.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Utilisation des inégalités de probabilité . . . . . . . . . . . . . 253.3 Intervalles de confiance asymptotiques . . . . . . . . . . . . . 28

4 Tests statistiques 314.1 Formalisme et démarche expérimentale . . . . . . . . . . . . . 314.2 Risques d’un test . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3 Dissymétrie des rôles de H0 et H1 . . . . . . . . . . . . . . . . 334.4 Propriétés éventuelles d’un test . . . . . . . . . . . . . . . . . . 354.5 Tests de Neyman-Pearson . . . . . . . . . . . . . . . . . . . . . 364.6 Tests asymptotiques . . . . . . . . . . . . . . . . . . . . . . . . 37

5 Echantillons gaussiens et modèle linéaire 395.1 Rappels sur les vecteurs gaussiens . . . . . . . . . . . . . . . . 395.2 Théorème de Cochran . . . . . . . . . . . . . . . . . . . . . . . 415.3 Echantillons gaussiens . . . . . . . . . . . . . . . . . . . . . . . 425.4 Régression linéaire multiple . . . . . . . . . . . . . . . . . . . . 45

3

Table des matières

6 Information et exhaustivité 486.1 Information de Fisher . . . . . . . . . . . . . . . . . . . . . . . 486.2 Efficacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526.3 Exhaustivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.4 Comparaison des statistiques exhaustives . . . . . . . . . . . . 61

7 Tests d’adéquation et d’indépendance 637.1 Test du χ2 d’adéquation . . . . . . . . . . . . . . . . . . . . . . 637.2 Test du χ2 d’indépendance . . . . . . . . . . . . . . . . . . . . 677.3 Test de Kolmogorov-Smirnov . . . . . . . . . . . . . . . . . . . 70

8 Apprentissage et classification supervisée 748.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748.2 L’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . 778.3 Minimisation du risque empirique . . . . . . . . . . . . . . . . 788.4 Cas d’une classe de cardinal fini . . . . . . . . . . . . . . . . . 80

9 Théorie de Vapnik-Chervonenkis 839.1 Passage du supg∈G au supA∈A . . . . . . . . . . . . . . . . . . 839.2 Théorème de Vapnik-Chervonenkis . . . . . . . . . . . . . . . 849.3 Aspects combinatoires . . . . . . . . . . . . . . . . . . . . . . . 919.4 Application à la minimisation du risque empirique . . . . . . 93

10 Théorème de Stone et plus proches voisins 9610.1 Classification et régression . . . . . . . . . . . . . . . . . . . . . 9610.2 Le théorème de Stone . . . . . . . . . . . . . . . . . . . . . . . . 9810.3 k-plus proches voisins . . . . . . . . . . . . . . . . . . . . . . . 104

11 Quantification et clustering 10911.1 Principe de la quantification . . . . . . . . . . . . . . . . . . . . 10911.2 Quantification empirique et clustering . . . . . . . . . . . . . . 11311.3 Consistance et vitesse . . . . . . . . . . . . . . . . . . . . . . . . 116

4

Chapitre 1

Modélisation statistique

1.1 Problématique

Au cours d’un sondage d’opinion, on interroge n individus :

xi = 1 (oui)xi = 0 (non)

}i = 1, . . . , n.

Les réponses x1, . . . , xn sont considérées comme des réalisations d’une suitede variables aléatoires X1, . . . , Xn indépendantes et identiquement distri-buées (i.i.d.), de loi commune B(θ), avec θ ∈ ]0, 1[ inconnu.

Problème : estimer la valeur de θ et, éventuellement, tester si θ ≥ 1/2 oupas.

Cet exemple relève de la statistique inférentielle, dont les deux volets lesplus immédiats sont l’estimation et les tests. Bien comprendre ici la dif-férence avec le calcul des probabilités : en probabilités, on suppose la loiconnue précisément et on cherche à caractériser le comportement d’une va-riable aléatoire qui suit cette loi ; en statistique, la démarche est inverse : àpartir de la connaissance des réalisations de la variable, que peut-on direde sa loi ?

1.2 Modèle statistique

Dans la suite, l’espace des observations est H n = H × · · · ×H (n fois),avec H ⊂ Rd.

5

Chapitre 1 Modélisation statistique

Définition 1. Un modèle statistique est un couple (H n, {Pθ}θ∈Θ), où {Pθ}θ∈Θest une famille de probabilités sur (H n, B(H n)). Quand il existe k ∈N? tel queΘ ⊂ Rk, le modèle est dit paramétrique. Sinon, il est non paramétrique.

Définition 2. Pour θ ∈ Θ, une observation X = (X1, . . . , Xn) de loi Pθ est unevariable aléatoire à valeurs dans (H n, B(H n)) de loi Pθ. On note X ∼ Pθ.

Exemple. Dans le cas du sondage, H n = {0, 1}n, Pθ = B(θ)⊗n et Θ =]0, 1[.

Important : L’ensemble Θ est connu, mais le vrai paramètre θ0 (celui qui aservi à générer l’observation) ne l’est en revanche pas. La démarche statis-tique consiste précisément à donner de l’information sur ce paramètre (onparle alors d’inférence ou de statistique inférentielle) à partir de l’observa-tion X = (X1, . . . , Xn). L’hypothèse fondamentale est donc qu’il existe uncertain θ0 ∈ Θ tel que PX = Pθ0 .

Le cas le plus fréquent est celui où l’observation X = (X1, . . . , Xn) estissue de n répétitions indépendantes d’une même expérience. Les compo-santes X1, . . . , Xn sont alors des variables aléatoires i.i.d., de même loi Qθ

sur (H , B(H )). Le modèle statistique associé (H n, {Pθ}θ∈Θ) s’écrit ainsi(H n, {Q⊗n

θ }θ∈Θ), et l’on dit que X = (X1, . . . , Xn) est un n-échantillon(i.i.d.) de loi (commune) Qθ. Dans ce contexte d’échantillonnage, les va-riables aléatoires Xi sont souvent appelées, avec un abus de langage, obser-vations.

Exemples.

1. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), avec θ ∈ Θ =]0, 1[.Outre le sondage d’opinion, ce modèle peut aussi représenter n lan-cers indépendants du jeu de pile ou face.

2. X = (X1, . . . , Xn) i.i.d., de loi commune P(θ). Dans ce cas, θ ∈ Θ =R?

+.

3. X = (X1, . . . , Xn) i.i.d., de loi commune E (θ). Ici encore, θ ∈ Θ = R?+.

4. X = (X1, . . . , Xn) i.i.d., de loi commune N (m, σ2). Dans ce cas, θ =(m, σ) et Θ = R×R+. On peut aussi prendre θ = (m, σ2), en fonctiondu contexte.

Un modèle statistique doit être construit sans ambiguïté, en n’associant àchaque loi du modèle qu’un seul paramètre. C’est par exemple le cas dumodèle (Rn

+, {E (θ)⊗n}θ>0), car l’application θ 7→ E (θ)⊗n définie sur R?+

6

Chapitre 1 Modélisation statistique

est injective. Cette propriété, appelée identifiabilité, ôte toute ambiguïté àl’étape d’approximation, en faisant correspondre à l’observation un, et unseul, paramètre du modèle.

Définition 3. Le modèle statistique (H n, {Pθ}θ∈Θ) est dit identifiable si l’appli-cation θ 7→ Pθ définie sur Θ est injective.

Exemples. Le modèle statistique gaussien (Rn, {N (m, σ2)⊗n}m∈R,σ>0) estidentifiable, mais (Rn, {N (m, σ2)⊗n}m∈R,σ 6=0) ne l’est pas car N (m, σ2) =N (m, (−σ)2).

Dans toute la suite du cours, on supposera les modèles identifiables. Ter-minons ce chapitre introductif par une définition utile :

Définition 4. Le modèle statistique (H n, {Pθ}θ∈Θ) est dit dominé s’il existe unemesure σ-finie ν sur H n telle que Pθ � ν pour chaque θ. La mesure ν est appeléemesure dominante du modèle.

Exemples. Le modèle gaussien (Rn, {N (m, σ2)⊗n}m∈R,σ>0) et le modèle deBernoulli du jeu de pile ou face ({0, 1}n, {B(θ)⊗n}θ∈ ]0,1[) sont dominés :une mesure dominante du premier est la mesure de Lebesgue sur Rn, etune mesure dominante du second est (δ0 + δ1)

⊗n.

7

Chapitre 2

Estimation paramétrique

Dans tout le chapitre, (H n, {Pθ}θ∈Θ) désigne un modèle statistique para-métrique avec H ⊂ Rd et Θ ⊂ Rk. Le paramètre d’intérêt est g(θ) avecg : Θ → Rp une fonction connue. L’objectif consiste alors à estimer g(θ) àpartir de l’observation X = (X1, . . . , Xn) issue du modèle.

2.1 Estimateur

Définition 5. Une statistique est une fonction borélienne de l’observation X =(X1, . . . , Xn). Un estimateur est une statistique qui prend ses valeurs dans unsur-ensemble de g(Θ).

Un estimateur est censé approcher le paramètre d’intérêt, le rôle plus géné-ral d’une statistique étant de fournir des informations de diverses natures.De ce fait, ils doivent être construits indépendamment du paramètre dumodèle, comme l’indique la définition. Un estimateur de g(θ) est toujoursde la forme g = h(X1, . . . , Xn), où h est une fonction borélienne définie surH n.

Remarque. Dans la pratique, c’est la réalisation de l’estimateur qui four-nit une estimation du paramètre d’intérêt (on l’appelle parfois l’estimée).Ainsi, si (x1, . . . , xn) est une réalisation de (X1, . . . , Xn) de loi Pθ0 , on peutcalculer, en utilisant l’estimateur g, l’approximation g(x1, . . . , xn) de g(θ0).

La question est alors double : 1) Trouver des méthodes d’estimation et 2)Définir ce qu’est un bon estimateur (ça va de pair). Les deux grandes tech-

8

Chapitre 2 Estimation paramétrique

niques d’estimation paramétriques sont la méthode des moments d’unepart et la méthode du maximum de vraisemblance d’autre part.

Dorénavant, ‖ · ‖ désigne la norme euclidienne et 〈·, ·〉 représente le produitscalaire usuel. Les vecteurs de Rp sont assimilés à des matrices colonnes etle symbole > est utilisé pour la transposition des matrices.

Dans la suite, Eθ désigne l’espérance sous la loi Pθ, i.e. pour une variablealéatoire intégrable Z à valeurs dans Rp et de loi Pθ,

EθZ =∫

H nZ(x)Pθ(dx).

De plus, VθZ désigne la matrice de variance-covariance (ou la variance sip = 1) de Z ∈ L2 sous la loi Pθ, i.e.

VθZ = Eθ (Z−EθZ) (Z−EθZ)>

= EθZ Z> − (EθZ) (EθZ)> .

Une statistique S(X) est d’ordre q ∈ N si S(X) ∈ Lq pour chaque θ ∈ Θ,i.e.

Eθ ‖S(X)‖q =∫

H n‖S(x)‖qPθ(dx) < ∞ ∀θ ∈ Θ.

2.2 Construction d’estimateurs

2.2.1 Méthode des moments

Considérons le cas d’un n-échantillon i.i.d., pour lequel les composantesX1, . . . , Xn de l’observation X sont indépendantes et de même loi Qθ sur(H , B(H )). Dans le cas particulier où le paramètre d’intérêt g(θ) est unmoment de la loi Qθ ou, par extension, une fonction de plusieurs momentsde cette loi, la méthode des moments permet de retrouver des estimateursnaturels, en substituant à Qθ la mesure empirique construite avec l’échan-tillon.

Par exemple, si pour chaque θ ∈ Θ, g(θ) est le moment d’ordre 1 de laloi Qθ, autrement dit si g(θ) = Eθ(X1), l’estimateur g construit avec cetteméthode est la moyenne empirique Xn = 1

n ∑ni=1 Xi.

9


De même, si les Xi sont réels et pour chaque θ ∈ Θ, g(θ) = VθX1, i.e.

g(θ) = Eθ(X1 −EθX1)2 = EθX2

1 −E2θX1,

l’estimateur g obtenu par la méthode des moments est la variance empi-rique

S2n =

1n

n

∑i=1

(Xi − Xn)2 =

1n

n

∑i=1

X2i − (Xn)

2.

Plus généralement, si g(θ) = Ψ(g1(θ), . . . , gq(θ)), où gj(θ) = EθΦj(X1)et Eθ‖Φj(X1)‖ < ∞, la méthode des moments suggère de travailler avecl’estimateur

g = Ψ

(1n

n

∑i=1

Φ1(Xi), . . . ,1n

n

∑i=1

Φq(Xi)

).

Avantage : L’estimateur a souvent de bonnes propriétés, obtenues via la loides grands nombres ou le théorème central limite.

Inconvénient : Pour utiliser cette méthode, il faut pouvoir exprimer g(θ)comme une fonction des moments de la loi Qθ, ce qui n’est pas toujourspossible (ou facile).

Exemples.

1. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Puisque θ =EθX1, la méthode des moments suggère θ = Xn.

2. X = (X1, . . . , Xn) i.i.d., de loi commune P(θ), θ > 0. Ici encore,θ = EθX1, et l’on choisit donc θ = Xn. Mais comme θ = VθX1, onpeut aussi prendre θ = S2

n.

3. X = (X1, . . . , Xn) i.i.d., de loi commune N (m, σ2), (m, σ2) ∈ R×R+.Si σ2 est connu, m = Xn, et si m est connu, σ2 = 1

n ∑ni=1(Xi − m)2

(pourquoi ?). Dans le cas où m et σ2 sont tous les deux inconnus,θ = (m, σ2) et la méthode des moments conduit à l’estimateur θ =(Xn, S2

n).

4. X = (X1, . . . , Xn) i.i.d., de loi commune U ([0, θ]), θ > 0. Il est facilede voir que θ = 2Eθ(X1), d’où l’estimateur θ = 2Xn.

10


2.2.2 Méthode du maximum de vraisemblance

On suppose dans ce paragraphe que (H n, {Pθ}θ∈Θ) est un modèle statis-tique dominé par une mesure σ-finie ν, avec H ⊂ Rd et Θ ⊂ Rk. Le casclassique est celui où la mesure ν est la mesure de Lebesgue (cas continu)ou bien la mesure de comptage (cas discret).

Lorsque H n est discret, la probabilité que l’observation X = (X1, . . . , Xn)soit égale à (x1, . . . , xn) ∈ H n représente le degré de vraisemblance decette observation pour la loi Pθ. En étendant ce point de vue à tous lesmodèles, on obtient le concept de vraisemblance défini ci-dessous.

Définition 6. La vraisemblance du modèle (H n, {Pθ}θ∈Θ) est l’application Ln :H n × Θ → R+ telle que, pour chaque θ ∈ Θ, Ln(·; θ) : H n → R+ est unélément de la classe d’équivalence de la densité de Pθ par rapport à ν.

Dans un modèle à échantillonnage i.i.d., l’expression de la vraisemblancese simplifie, comme en témoigne le résultat qui suit.

Proposition 1. Soit L la vraisemblance du modèle (H , {Qθ}θ∈Θ) dominé par lamesure µ. Si, pour chaque θ ∈ Θ, Pθ = Q⊗n

θ , alors la fonction

Ln : H n ×Θ → R

(x1, . . . , xn, θ) 7→ ∏ni=1 L(xi; θ)

est la vraisemblance du modèle (H n, {Pθ}θ∈Θ) pour la mesure dominante ν =µ⊗n.

Démonstration. Il suffit de remarquer que, pour chaque θ ∈ Θ, l’application

(x1, . . . , xn) 7→n

∏i=1

L(xi; θ),

définie sur H n, est une version de la densité de Q⊗nθ par rapport à ν =

µ⊗n.

Les deux cas les plus classiques en échantillonnage i.i.d. sont ceux où µ estla mesure de comptage sur H (cas discret) ou la mesure de Lebesgue (cas

11


continu). On utilise alors souvent la notation Pθ(X1 = x) (cas discret) oufθ(x) (cas continu) en lieu et place de L(x; θ), de sorte que

Ln(x1, . . . , xn, θ) =n

∏i=1

Pθ(Xi = xi)

pour le cas discret, et

Ln(x1, . . . , xn, θ) =n

∏i=1

fθ(xi)

pour le cas continu.

Exemples.

1. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Le modèleest dominé par la mesure de comptage, et la vraisemblance Ln vaut

Ln(x1, . . . , xn; θ) = θnxn (1− θ)n(1−xn) ,

pour (x1, . . . , xn) ∈ {0, 1}n et θ ∈ ]0, 1[.

2. X = (X1, . . . , Xn) i.i.d., de loi commune N (m, σ2), (m, σ2) ∈ R ×R?

+. Le modèle est dominé par la mesure de Lebesgue sur Rn, et lavraisemblance Ln s’écrit

Ln(x1, . . . , xn; m, σ2) =1

(2πσ2)n/2 exp(−∑n

i=1(xi −m)2

2σ2

),

pour (x1, . . . , xn) ∈ Rn, m ∈ R et σ2 > 0.

L’intuition nous amène à choisir comme estimateur du paramètre du mo-dèle un paramètre qui maximise la vraisemblance. C’est le concept d’esti-mateur du maximum de vraisemblance.

Définition 7. Un estimateur du maximum de vraisemblance (EMV) est un esti-mateur θ qui vérifie

Ln(X1, . . . , Xn; θ(·)

)= sup

θ∈ΘLn(X1, . . . , Xn; θ).

Remarques.

12


1. En pratique, la vraisemblance se maximise en θ à X1, . . . , Xn “fixés”,et l’éventuel EMV s’écrit comme une fonction de X1, . . . , Xn.

2. Ni l’existence, ni l’unicité des EMV ne sont en général acquises. Deplus, sous réserve d’existence, l’EMV peut ne pas avoir de représen-tation explicite ; dans ce cas, le recours à une méthode d’optimisationnumérique est nécessaire afin de déterminer sa valeur en l’observa-tion.

3. L’EMV, noté θ, est donc un estimateur du paramètre θ du modèle. Sile paramètre d’intérêt est g(θ), avec g une fonction borélienne connuedéfinie sur Θ, on dit par abus que g(θ) est l’EMV de g(θ).

4. Lorsque X = (X1, . . . , Xn) est un n-échantillon i.i.d., on préfère par-fois calculer l’EMV en maximisant la log-vraisemblance, c’est-à-direle logarithme de la vraisemblance, plutôt que la vraisemblance. En ef-fet, d’après la Proposition 1, si L désigne la vraisemblance du modèle(H , {Qθ}θ∈Θ), la log-vraisemblance du modèle (H n, {Q⊗n

θ }θ∈Θ) s’é-crit

ln Ln(x1, . . . , xn; θ) =n

∑i=1

ln L(xi; θ),

pour (x1, . . . , xn) ∈ H n et θ ∈ Θ. L’intérêt pratique est clair, l’étapede maximisation étant en principe plus facile à mener.

5. Sous certaines conditions de régularité du modèle, l’EMV possède debonnes propriétés (existence, unicité, convergence, etc.).

Exemples.

1. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Dans ce cas,

ln Ln(x1, . . . , xn; θ) = nxn ln θ + n(1− xn) ln(1− θ),

pour (x1, . . . , xn) ∈ {0, 1}n et θ ∈ ]0, 1[. Une étude rapide montre quexn réalise le maximum de la fonction

θ 7→ ln Ln(x1, . . . , xn; θ),

définie sur ]0, 1[. Ainsi, θ = Xn.

2. X = (X1, . . . , Xn) i.i.d., de loi commune P(θ), θ > 0. Ici,

Ln(x1, . . . , xn; θ) =n

∏i=1

(e−θ θxi

xi!

)= e−nθθnxn

n

∏i=1

1xi!

,

13


et

ln Ln(x1, . . . , xn; θ) = −nθ + (nxn) ln θ −n

∑i=1

ln xi!,

pour (x1, . . . , xn) ∈ (R+)n et θ > 0. Le maximum de cette fonction estatteint en xn, de sorte que θ = Xn.

3. X = (X1, . . . , Xn) i.i.d., de loi commune N (m, σ2), (m, σ2) ∈ R×R?+.

On trouve

ln Ln(x1, . . . , xn; θ) = −n2

ln(2π)− n2

ln σ2 − 12σ2

n

∑i=1

(xi −m)2,

pour (x1, . . . , xn) ∈ Rn, m ∈ R et σ2 > 0. Si σ2 est connu, m =Xn, tandis que si m est connu, σ2 = 1

n ∑ni=1(Xi − m)2. Lorsque les

deux paramètres sont inconnus, on pose θ = (m, σ2) et on trouvefacilement 1 en maximisant la log-vraisemblance que θ = (Xn, S2

n).4. X = (X1, . . . , Xn) i.i.d., de loi commune U ([0, θ]), θ > 0. On écrit,

pour (x1, . . . , xn) ∈ [0, θ] et θ > 0,

L(x1, . . . , xn; θ) = θ−nn

∏i=1

1[0,θ](xi) = θ−nn

∏i=1

1[xi,+∞[(θ)

= θ−n1[x(n),+∞[(θ),

où x(n) = max(x1, . . . , xn). On trouve ainsi θ = X(n). Noter que, pource modèle, l’estimateur obtenu par la méthode des moments est dif-férent de l’EMV.

5. X = (X1, . . . , Xn) i.i.d., de densité commune sur R

fθ(x) =1

π (1 + (x− θ))2 , θ ∈ R

(modèle de translation de Cauchy). Alors, pour (x1, . . . , xn) ∈ Rn etθ ∈ R,

ln L(x1, . . . , xn; θ) = −n

∑i=1

ln(1 + (xi − θ)2)− n ln π.

Cette fonction, qui est dérivable en θ, converge vers −∞ lorsque θ →±∞. Elle admet donc certainement un maximum, difficile à localiser,qui est un point où sa dérivée s’annule.

1. Ne pas se lancer dans un calcul de matrice Hessienne mais observer que, à σ2 fixé,le maximum en m est toujours atteint au point xn, indépendamment de σ2.

14


2.3 Critères de performance en moyenne

La première propriété que l’on puisse exiger d’un estimateur est qu’il secomporte en moyenne comme le paramètre qu’il est censé approcher. C’estle concept de biais, qui fait l’objet de la prochaine définition.

Définition 8. Soit g un estimateur d’ordre 1. On appelle biais la fonction θ 7→Eθ g− g(θ). L’estimateur g est dit sans biais lorsque Eθ g = g(θ) ∀θ ∈ Θ. Il estasymptotiquement sans biais lorsque limn→∞ Eθ g = g(θ) ∀θ ∈ Θ.

Remarques.

1. Le caractère non biaisé d’un estimateur doit se vérifier pour chaque θ

dans Θ.

2. Il s’agit d’un critère parmi d’autres, sur lequel on peut discuter.

Exemples. Dans les exemples qui suivent, on se place dans le cadre d’unn-échantillon X = (X1, . . . , Xn) i.i.d., de loi Pθ = Q⊗n

θ .

1. Si Qθ admet un moment d’ordre 1, la moyenne empirique Xn esttoujours un estimateur sans biais de g(θ) = EθX1, puisque

EθXn =1n

n

∑i=1

EθXi = EθX1 = g(θ).

2. Supposons que H ⊂ R et que la probabilité Qθ admette un momentd’ordre 2. La variance empirique S2

n est alors un estimateur biaisé deg(θ) = VθX1. En effet, on a la décomposition :

nS2n =

n

∑i=1

X2i + n(Xn)

2 − 2n(Xn)2 =

n

∑i=1

X2i − n(Xn)

2.

Les variables aléatoires X1, . . . , Xn étant indépendantes et de mêmeloi, VθXn = VθX1/n = g(θ)/n car la variance de X1 vaut g(θ). Parsuite,

nEθS2n = nEθX2

1 − nEθ(Xn)2

= ng(θ) + nE2θX1 − nVθXn − nE2

θXn

= (n− 1)g(θ),

15


ce qui montre que

EθS2n =

n− 1n

g(θ).

Voilà pourquoi, lorsque n > 1, on considère plutôt l’estimateur

S?2n =

nn− 1

S2n =

1n− 1

n

∑i=1

(Xi − Xn)2

(appelé variance empirique corrigée) qui, lui, estime sans biais g(θ) =VθX1. Notons également que la variance empirique S2

n est asympto-tiquement sans biais.

3. Supposons que chaque Xi suive la loi U ([0, θ]), θ > 0. Dans ce mo-dèle, l’estimateur θ = 2Xn obtenu par la méthode des moments estsans biais. Il n’en est pas de même pour l’EMV θ = X(n), car Eθ θ < θ

(pourquoi ?). On montre d’ailleurs facilement que Eθ θ = nn+1 θ.

La proximité entre l’estimateur et le paramètre d’intérêt peut être évaluéepar leur distance dans L2.

Définition 9. Soit g un estimateur d’ordre 2.

1. Pour θ ∈ Θ, le risque quadratique de g sous Pθ est

R(g; θ) = Eθ ‖g− g(θ)‖2 .

2. g est dit préférable à l’estimateur g′ d’ordre 2 lorsque

R(g; θ) ≤ R(g′; θ) ∀θ ∈ Θ.

On a la relation fondamentale suivante (dite décomposition biais-variance) :

R(g; θ) = ‖Eθ g− g(θ)‖2 + Eθ‖g−Eθ g‖2 ∀θ ∈ Θ. (2.1)

Ainsi,R(g; θ) = biais2(θ) + Vθ g.

L’intérêt de cette décomposition est qu’elle montre que, pour un risquequadratique donné, abaisser le biais revient à augmenter le terme de va-riation Eθ‖g−Eθ g‖2, et réciproquement. Il est alors naturel de s’intéresseraux estimateurs qui minimisent uniformément la variance parmi les esti-mateurs sans biais de g(θ). On dit ainsi qu’un estimateur g d’ordre 2 est

16


de variance uniformément minimum parmi les estimateurs sans biais (VUMSB)s’il est sans biais et préférable à tout autre estimateur sans biais d’ordre2. L’existence d’un estimateur VUMSB n’est en général pas acquise. Nousreviendrons sur ce problème dans le Chapitre 6, en retenant pour l’instantl’idée qu’un estimateur est d’autant meilleur que son risque quadratiqueest faible.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. L’esti-mateur Xn de θ est sans biais, et sa variance vaut

VθXn =1n

VθX1 =θ(1− θ)

n,

car les variables aléatoires X1, . . . , Xn sont indépendantes et de même loiB(θ). Par suite, d’après la décomposition biais-variance (2.1) :

R(Xn; θ) =θ(1− θ)

n.

En augmentant n, l’estimateur Xn gagne donc en précision. Ce n’est pasle cas pour l’estimateur X1, de risque quadratique R(X1; θ) = θ(1 − θ).Comme on pouvait s’y attendre, Xn est donc préférable à X1. Nous mon-trerons dans le Chapitre 6 que Xn est VUMSB.

2.4 Critères de performance asymptotique

L’observation X = (X1, . . . , Xn) contient de plus en plus d’information surla vraie valeur du paramètre à mesure que sa taille n croît. De ce fait, on estamené à s’intéresser aux propriétés asymptotiques des estimateurs. Dans lasuite, sauf mention explicite du contraire, toute propriété de convergencesera entendue pour une taille d’échantillon n qui tend vers l’infini.

Définition 10. L’estimateur g est dit consistant lorsque

g P→ g(θ) ∀θ ∈ Θ.

Exemple. L’estimateur Xn de g(θ) = EθX1 construit avec un n-échantilloni.i.d. X = (X1, . . . , Xn) ∈ Rdn satisfaisant Eθ‖X1‖ < ∞ est consistant car,d’après la loi faible des grands nombres :

XnP→ EθX1 ∀θ ∈ Θ.

17


Pour d = 1, il en est de même de la variance empirique dès que EθX21 < ∞

puisque, toujours par la loi faible des grands nombres,

S2n

P→ VθX1 ∀θ ∈ Θ.

Remarque. Consistance et absence de biais asymptotique ne sont pas lesmêmes notions. Par exemple, pour se convaincre qu’un estimateur consis-tant n’est pas nécessairement asymptotiquement sans biais, considérons lemodèle statistique (Rn, {N (θ, 1)⊗n}θ∈ ]0,1[) et l’estimateur θ de θ issu deX = (X1, . . . , Xn) ∼ Pθ = N (θ, 1)⊗n défini par

θ = Xn +1

Φ(−√

n)1[Xn≤0],

où Φ désigne la fonction de répartition de la loi N (0, 1). L’estimateur Xnest consistant d’après la loi faible des grands nombres. En outre, commeθ > 0, pour chaque ε > 0 :

limn→+∞

P

(1

Φ(−√

n)1[Xn≤0] > ε

)= lim

n→+∞P(Xn ≤ 0) = 0.

On en déduit la consistance de θ. Or, comme Xn suit la loi N (θ, 1/n) etθ ≤ 1 :

P(Xn ≤ 0) =1√2π

∫ −θ√

n

−∞e−t2/2dt = Φ(−θ

√n) ≥ Φ(−

√n).

En conséquence,

Eθ θ = EθXn +1

Φ(−√

n)P(Xn ≤ 0) ≥ θ + 1,

donc θ est biaisé, et même asymptotiquement biaisé.

La consistance ne doit être vue que comme une propriété minimale quedoit satisfaire un estimateur. Elle ne permet cependant pas de préciser l’er-reur commise, d’où la définition qui suit.

Définition 11. Soit (vn)n≥1 une suite de réels positifs telle que vn → +∞. L’es-timateur g est dit de vitesse vn si, pour chaque θ ∈ Θ, il existe une loi `(θ) surRp différente de la loi de Dirac en 0, appelée loi limite de g, telle que

vn (g− g(θ)) L→ `(θ).

Si toutes les lois `(θ) sont normales, g est dit asymptotiquement normal.

18


La qualité d’un estimateur est ainsi évaluée sur sa vitesse car il est alorsd’autant plus proche de g(θ) qu’elle est rapide, mais aussi sur la variancede la loi limite, qui doit idéalement être faible afin que l’estimateur seconcentre sur le paramètre d’intérêt.

Exemples.1. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. L’estimateur

θ = Xn de θ est consistant. Il est aussi asymptotiquement normal devitesse

√n car, pour chaque θ ∈ ]0, 1[ :

√n (Xn − θ)

L→ N (0, θ(1− θ)) ,

d’après le théorème central limite. Noter que la variance de la loilimite prend ses valeurs les plus faibles lorsque θ est proche de 0 oude 1 et ses valeurs les plus grandes lorsque θ est proche de 1/2. De cefait, l’estimation de θ par Xn est d’autant meilleure que θ est prochede 0 ou de 1 car la loi limite de l’estimateur Xn est alors très peudispersée.

2. X = (X1, . . . , Xn) i.i.d., de loi commune P(θ), θ > 0. Ici encore,l’estimateur θ = Xn est consistant et asymptotiquement normal devitesse

√n, car

√n (Xn − θ)

L→ N (0, θ),

toujours d’après le théorème central limite.3. X = (X1, . . . , Xn) i.i.d., de loi commune U ([0, θ]), θ > 0. Il est facile

de voir (exercice) que l’EMV θ = X(n) est consistant et de vitesse n,car

n(X(n) − θ)L→ Z,

où −Z ∼ E (θ). De ce point de vue, il est plus performant (malgréson caractère biaisé) que l’estimateur 2Xn obtenu par la méthode desmoments, qui ne converge qu’à la vitesse

√n.

2.5 Asymptotique de l’erreur d’estimation

Pour fixer les idées, supposons dans cette section que l’estimateur θ de θ

est de vitesse vn, i.e.

vn(θ − θ)L→ `(θ) ∀θ ∈ Θ,

19


avec `(θ) une loi sur Rk différente de la mesure de Dirac en 0 et vn → +∞.

La loi de l’erreur renormalisée vn(θ − θ) est proche de la loi `(θ) pour lesgrandes valeurs de n. Or, `(θ) est inconnu car θ est inconnu, donc commentpeut-on préciser cette erreur d’approximation ? De plus, comment exploitercette propriété asymptotique lorsque le paramètre d’intérêt est g(θ) ? Sousréserve d’hypothèses supplémentaires, nous allons examiner de quelle ma-nière il est possible d’apporter des réponses à ces questions. Commençonsau préalable par énoncer le lemme très utile suivant dont la preuve, facile,est laissée au lecteur.

Lemme 1 (Lemme de Slutsky). Soient (Zn)n≥1 et (Yn)n≥1 des suites de va-riables aléatoires à valeurs dans Rk et Rq telles que (Zn)n≥1 converge en loi versune variable aléatoire Z et (Yn)n≥1 converge en probabilité vers y ∈ Rq. Alors,((Zn, Yn))n≥1 converge en loi vers (Z, y).

Le plus souvent, on applique à cette convergence jointe (Zn, Yn)L→ (Z, y)

une fonction continue h (somme, multiplication, etc.), et l’on en tire que

h(Zn, Yn)L→ h(Z, y).

Estimation de θ. Supposons qu’il existe une fonction connue σ : Θ→ R?

et une loi connue τ sur Rk telles que pour chaque θ ∈ Θ, `(θ) = σ(θ)τ.Pourvu que l’on dispose d’un estimateur consistant σ de σ(θ), on déduitdu lemme de Slutsky que(

vn(θ − θ), σ) L→ (σ(θ)W, σ(θ)) ∀θ ∈ Θ,

si W est une variable aléatoire de loi τ. Comme la convergence en loi estpréservée par la composition des fonctions continues,

vn

σ(θ − θ)

L→W ∀θ ∈ Θ.

Ainsi, la loi de l’erreur renormalisée (vn/σ)(θ− θ) est proche de celle de τ

pour les grandes valeurs de n.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Le théo-rème central limite donne

√n (Xn − θ)

L→ N (0, θ(1− θ)) ∀θ ∈ ]0, 1[.

20


De plus,√

Xn(1− Xn) est un estimateur consistant de√

θ(1− θ) d’aprèsla loi des grands nombres. La loi asymptotique de l’erreur renormalisée estdonc N (0, 1), car√

nXn(1− Xn)

(Xn − θ)L→ N (0, 1) ∀θ ∈ ]0, 1[.

Ce résultat peut alors être exploité pour encadrer le paramètre inconnu θ.

Estimation de g(θ). Revenons au problème plus général de l’estimationdu paramètre g(θ). Comme l’indique le résultat qui suit, le calcul de lavitesse de l’estimateur g(θ) est immédiat, sous réserve que g possède lespropriétés analytiques adéquates.

Théorème 1 (δ-méthode). Soient (vn)n≥1 une suite de réels qui tend vers +∞,z ∈ Rk et (Zn)n≥1 une suite de variables aléatoires à valeurs dans Rk telle quevn(Zn − z) converge en loi vers une loi `. Si g : Rk → Rp est de classe C 1, dematrice jacobienne Jg, vn(g(Zn)− g(z)) converge en loi vers Jg(z)`.

Ainsi, si la fonction g est de classe C 1, on a, pour tout θ ∈ Θ,

vn(

g(θ)− g(θ)) L→ Jg(θ)`(θ),

Jg(θ) désignant la matrice jacobienne de g évaluée en θ. De ce fait, g(θ) est,comme θ, un estimateur de vitesse vn dès que la loi Jg(θ)`(θ) est différentede la loi de Dirac en 0.

Comme dans la partie précédente, on peut préciser l’erreur commise enapprochant g(θ) par g(θ) au moins lorsqu’il existe une fonction σ : Θ→ R?

et une loi τ sur Rk telles que, pour chaque θ ∈ Θ, `(θ) = σ(θ)τ. En effet, siJg(θ) est une matrice carrée (donc k = p) inversible pour chaque θ ∈ Θ et σ

est un estimateur consistant de σ(θ), on déduit du lemme de Slutsky que

vn

σJg(θ)

−1 (g(θ)− g(θ)) L→ τ ∀θ ∈ Θ,

car, g étant de classe C 1, Jg(θ) est un estimateur consistant de Jg(θ). Laloi de l’erreur renormalisée (vn/σ)Jg(θ)−1(g(θ)− g(θ)) est donc proche decelle de τ pour les grandes valeurs de n.

21


Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Si g(θ) =θ(1− θ) est le paramètre d’intérêt, la méthode des moments nous conduità considérer l’estimateur g(Xn). Le théorème central limite et la δ-méthodedonnent alors

√n (g(Xn)− g(θ)) L→ N

(0, θ(1− θ)(1− 2θ)2

)∀θ ∈ ]0, 1[.

Puis, le lemme de Slutsky et la loi des grands nombres montrent que√n

Xn(1− Xn)(1− 2Xn)2 (g(Xn)− g(θ)) L→ N (0, 1) ∀θ ∈ ]0, 1[.

Remarque. L’utilisation de la δ-méthode ne se limite pas à l’obtention delois limites pour les estimateurs de g(θ). Pour s’en convaincre, considéronsun n-échantillon X = (X1, . . . , Xn) i.i.d., de loi commune P(θ), θ > 0. Dansce contexte, la variance empirique θ = S2

n = 1n ∑n

i=1 X2i − (Xn)2 est un esti-

mateur convergent de θ. Le théorème central limite multivarié (appliqué aucouple de variables aléatoires ( 1

n ∑ni=1 X2

i , Xn)) et la δ-méthode (appliquéeavec la fonction g(x, y) = x− y2) conduisent alors (exercice) à

√n(θ − θ)

L→ N (0, θ + 2θ2) ∀θ > 0.

Démonstration du Théorème 1. Notons Z une variable aléatoire de loi ` et ψ

la fonction définie pour tout y ∈ Rk par

ψ(y) =∫ 1

0Jg (z + u(y− z))du.

Comme (1/vn, vn(Zn − Z)) converge en loi vers le couple (0, Z) d’après lelemme de Slutsky, Zn − z = (1/vn) vn(Zn − z) tend vers 0 en probabilité.Or, ψ est continue car g est de classe C 1, d’où ψ(Zn) converge en probabilitévers ψ(z) = Jg(z). Par suite, d’après le lemme de Slutsky,

(ψ(Zn), vn(Zn − Z)) L→ (Jg(z), Z).

La formule de Taylor avec reste intégral nous donne, pour tout y ∈ Rk :

g(y)− g(z) = ψ(y)(y− z).

La convergence en loi étant préservée par la composition par des fonctionscontinues,

vn (g(Zn)− g(z)) = ψ(Zn)vn(Zn − z) L→ Jg(z)Z,

d’où le lemme.

22

Chapitre 3

Intervalles de confiance

3.1 Principe général

Ce chapitre est consacré à la construction d’intervalles contenant le para-mètre inconnu supposé réel, avec un niveau de confiance fixé. La théorie segénéralise sans problème au cas multivarié, en remplaçant les intervallespar des régions de confiance.

Dans la suite, (H n, {Pθ}θ∈Θ) est un modèle statistique paramétrique avecH ⊂ Rk et Θ ⊂ Rd. Le paramètre d’intérêt est g(θ), avec g : Θ → R unefonction connue.

Définition 12. Soit α ∈ ]0, 1[. Un intervalle de confiance pour g(θ) de niveau(1 − α) est une statistique I à valeurs dans les intervalles de R telle que pourchaque θ ∈ Θ,

P (g(θ) ∈ I) ≥ 1− α.

On distingue parfois les intervalles de confiance de niveau exactement (1−α) des intervalles de confiance de niveau supérieur ou égal à (1− α), quisont alors dits par excès. Noter que les deux critères de qualité d’un inter-valle de confiance, i.e. sa longueur et son niveau, s’opposent, et qu’il estdonc impératif de réaliser un compromis. En pratique, pour un niveau deconfiance raisonnable (souvent 90, 95 ou 99%), on cherche un intervalle deconfiance de plus petite longueur.

On veillera à ne pas confondre l’intervalle de confiance (qui est aléatoire)

23

Chapitre 3 Intervalles de confiance

et sa réalisation (qui ne l’est pas). Une erreur fréquente consiste à écrire

P (θ ∈ [−1.3, 2.5]) = 0.95,

ce qui n’a évidemment pas de sens, cette probabilité valant en fait 0 ou 1.

L’un des ingrédients de base pour construire un intervalle de confiance estle quantile d’une loi sur R.

Définition 13. Soit F la fonction de répartition d’une loi ν sur R. Le quantiled’ordre p ∈ ]0, 1[ de la loi ν est défini par

qp = inf {x ∈ R : F(x) ≥ p} .

Il n’est en général pas possible de calculer un quantile de façon exacte,mais la plupart des logiciels de mathématiques sont dotés de fonctionsconsacrées au calcul des valeurs approchées des quantiles des lois usuelles.Pour la loi N (0, 1), il faut se souvenir que q0.975 ≈ 1.960 et q0.95 ≈ 1.645.

La recherche d’une variable aléatoire pivotale, i.e. une variable aléatoiredont la loi est indépendante de celle de l’observation, joue un rôle essentieldans le mécanisme de construction des intervalles de confiance.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune N (θ, 1), θ ∈ R. Si α ∈]0, 1[, construisons un intervalle de confiance de niveau (1 − α) pour leparamètre θ. Soit Φ la fonction de répartition de la loi N (0, 1) et q1− α

2son

quantile d’ordre (1 − α2 ). Comme

√n(Xn − θ) est une variable aléatoire

pivotale de loi N (0, 1),

P(√

n |Xn − θ| ≤ q1− α2

)= Φ(q1− α

2)−Φ(−q1− α

2)

= 2Φ(q1− α2)− 1 = 1− α,

car la densité de la loi N (0, 1) est paire. Ainsi,

P

(θ ∈

[Xn −

q1− α2√

n, Xn +

q1− α2√

n

])= 1− α,

c’est-à-dire que [Xn −q1− α

2√n , Xn +

q1− α2√

n ] est un intervalle de confiance, ditbilatère, de niveau (1 − α) pour le paramètre θ. D’autres intervalles pos-sibles sont ]−∞, Xn +

q1−α√n ] (unilatère à gauche) et [Xn − q1−α√

n ,+∞[ (unilatèreà droite).

L’exemple ci-dessus illustre la méthode dite du pivot, qui se résume de lafaçon suivante :

24


1. On trouve un estimateur du paramètre dont on connaît la loi, fonctionde θ.

2. On transforme cet estimateur pour obtenir une statistique pivotale,dont la loi ne dépend plus de θ.

3. A partir des quantiles de cette loi, on essaie de trouver un intervallede confiance de niveau adéquat pour θ.

3.2 Utilisation des inégalités de probabilité

Pour toute la suite de cette section, on se place dans le cadre d’un n-échantillon X = (X1, . . . , Xn) i.i.d., de loi commune Qθ sur H ⊂ R, desupport [a, b] indépendant de θ. On suppose de plus que le paramètre d’in-térêt vérifie g(θ) = EθX1, et on utilise la moyenne empirique pour estimerg(θ) (méthode des moments).

A partir de l’inégalité de Bienaymé-Tchebytchev, on montre facilement que

I1 =

[Xn −

b− a2√

nα, Xn +

b− a2√

nα

]est un intervalle de confiance (par excès) pour g(θ) de niveau (1− α), avecα ∈ ]0, 1[.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Ici, a = 0,b = 1, et on trouve

I1 =

[Xn −

12√

nα, Xn +

12√

nα

].

Typiquement, 1− α = 0.95 et

12√

nα=

√5√n≤ 2.24√

n.

L’intervalle I1 peut être amélioré en basant sa construction sur une inéga-lité plus précise, par exemple l’inégalité de Hoeffding, qui fait l’objet duprochain théorème.

25


Théorème 2 (Inégalité de Hoeffding). Soit Z1, . . . , Zn des variables aléatoiresréelles indépendantes telles que ai ≤ Zi ≤ bi P-p.s. (ai < bi). Alors, pour toutε > 0,

P

(∣∣∣∣∣ n

∑i=1

(Zi −EZi)

∣∣∣∣∣ ≥ ε

)≤ 2 exp

(− 2ε2

∑ni=1(bi − ai)2

).

Construisons avec cette inégalité un intervalle de confiance par excès deniveau (1 − α) pour le paramètre g(θ). Puisque les variables aléatoiresX1, . . . , Xn sont indépendantes et de même loi avec Xi ∈ [a, b] P-p.s. etEθX1 = g(θ), l’inégalité de Hoeffding donne

P (|Xn − g(θ)| ≥ ε) = P

(1n

∣∣∣∣∣ n

∑i=1

(Xi −EθXi)

∣∣∣∣∣ ≥ ε

)

≤ 2 exp(− 2nε2

(b− a)2

),

pour chaque ε > 0. Avec le choix

ε = (b− a)

√1

2nln

2α

on trouve P(|Xn − g(θ)| ≥ ε) ≤ α. Par suite,

I2 =

[Xn − (b− a)

√1

2nln

2α

, Xn + (b− a)

√1

2nln

2α

]est un intervalle de confiance (par excès) pour g(θ) de niveau (1− α). Com-paré à l’intervalle I1 obtenu avec l’inégalité de Bienaymé-Tchebytchev, lescontributions de la taille de l’échantillon, en 1/

√n, et de la longueur du

support de Qθ sont les mêmes. En revanche, l’amélioration est nette en cequi concerne l’influence de α car√

12n

ln2α� 1√

2nα

pour les petites valeurs de α.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. On ob-tient

I2 =

[Xn −

√1

2nln

2α

, Xn +

√1

2nln

2α

].

26


Avec 1− α = 0.95, √1

2nln

2α≤ 1.36√

n.

Preuve du Théorème 2. Supposons pour simplifier que les Zi sont centrées,et notons Sn = ∑n

i=1 Zi. Pour tout r > 0,

P (|Sn| ≥ ε) = P(Sn ≥ ε) + P(−Sn ≥ ε)

= P(erSn ≥ erε

)+ P

(e−rSn ≥ erε

).

On en déduit, en utilisant l’inégalité de Markov que

P (|Sn| ≥ ε) ≤ e−rε{

EerSn + Ee−rSn}≤ e−rε

{n

∑i=1

EerZi +n

∑i=1

Ee−rZi

},

E désignant l’espérance sous la probabilité P. Majorons maintenant chaqueterme EesZi , pour s = r ou s = −r. Par convexité de la fonction exponen-tielle et comme Zi ∈ [ai, bi] P-p.s.,

esZi = exp(

Zi − ai

bi − aisbi +

bi − Zi

bi − aisai

)≤ Zi − ai

bi − aiesbi +

bi − Zi

bi − aiesai .

Puisque Zi est centrée, il vient

EesZi ≤ − ai

bi − aiesbi +

bi

bi − aiesai .

Or, en posant pi = −ai/(bi − ai), on trouve la représentation :

− ai

bi − aiesbi +

bi

bi − aiesai = exp

[−pis(bi − ai) + ln

(1− pi + pies(bi−ai)

)].

Par suite, si φ(x) = −pix + ln(1− pi + piex) pour tout x ∈ R,

EesZi ≤ eφ(s(bi−ai)).

La fonction φ est de classe C 2 et vérifie φ(0) = φ′(0) = 0 et φ′′(x) ≤ 1/4pour tout x. D’après la formule de Taylor-Lagrange, il existe donc κ ∈[0, s(b− a)] (si s = r) ou κ ∈ [s(b− a), 0] (si s = −r) tel que

φ (s(bi − ai)) =s2(bi − ai)

2

2φ′′(κ),

27


d’où φ (s(bi − ai)) ≤ s2(bi − ai)2/8 et EesZi ≤ er2(bi−ai)

2/8 car s2 = r2. Ils’ensuit que pour chaque r > 0,

P (|Sn| ≥ ε) ≤ 2 exp(−rε +

r2 ∑ni=1(bi − ai)

2

8

).

Finalement, le choix r = 4ε/ ∑ni=1(bi − ai)

2, qui minimise le terme de droitedans l’inégalité ci-dessus, nous donne l’inégalité annoncée.

3.3 Intervalles de confiance asymptotiques

A défaut d’informations suffisantes ou appropriées sur la loi de la variablealéatoire utilisée pour la construction de l’intervalle de confiance, une al-ternative consiste à se retrancher sur une propriété asymptotique.

Définition 14. Soit α ∈ ]0, 1[. Un intervalle de confiance asymptotique pour g(θ)de niveau (1− α) est une statistique In à valeurs dans les intervalles de R telleque pour chaque θ ∈ Θ,

limn→+∞

P (g(θ) ∈ In) ≥ 1− α.

En pratique, on écrit P(g(θ) ∈ In) ≈ 1− α et on raisonne comme si n étaitfixé. Il s’agit d’un abus.

Supposons maintenant que l’on veuille construire un intervalle de confian-ce asymptotique de niveau (1− α) dans le cas où l’estimateur g de g(θ)est asymptotiquement normal et de vitesse (vn)n≥1 : pour chaque θ ∈ Θ, ilexiste σ2(θ) > 0 tel que

vn (g− g(θ)) L→ N(0, σ2(θ)

).

Par suite,vn

σ(θ)(g− g(θ)) L→ N (0, 1).

La variable aléatoire vn(g− g(θ))/σ(θ) est dite asymptotiquement pivotale,car sa loi limite est indépendante de celle de l’observation. Cependant,un tel résultat ne permet pas en général de construire un intervalle de

28


confiance asymptotique pour g(θ). Si σ est un estimateur consistant deσ(θ), le lemme de Slutsky montre que pour chaque θ ∈ Θ,

vn

σ(g− g(θ)) L→ N (0, 1).

En désignant par q1− α2

le quantile d’ordre (1− α2 ) de la loi N (0, 1), on en

déduit que

limn→+∞

P(vn

σ|g− g(θ)| ≤ q1− α

2

)= Φ(q1− α

2)−Φ(−q1− α

2)

= 2Φ(q1− α2)− 1

= 1− α,

avec Φ la fonction de répartition de la loi N (0, 1). Nous avons ainsi montréque [g− q1− α

2σ/vn, g + q1− α

2σ/vn] est un intervalle de confiance asympto-

tique de niveau (1− α) pour g(θ).

Exemples.

1. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. On sait que√n

Xn(1− Xn)(Xn − θ)

L→ N (0, 1).

Par suite, en notant q1− α2

le quantile d’ordre (1− α2 ) de la loi N (0, 1),

I3 =

[Xn − q1− α

2

√Xn(1− Xn)

n, Xn + q1− α

2

√Xn(1− Xn)

n

]

est un intervalle de confiance asymptotique de niveau (1− α) pour θ.Avantage. Marge d’erreur plus faible :

1.96

√Xn(1− Xn)

n≤ 1√

n.

Inconvénient. Caractère asymptotique.Application. Marge d’erreur en 1/

√n : pour un échantillon de 1000

personnes (cas des sondages politiques), la précision est de l’ordre de±3% (seulement).

29


2. X = (X1, . . . , Xn) i.i.d., de loi commune E (θ), θ > 0. Comme θ =1/EθX1, on estime θ à l’aide de l’estimateur 1/Xn (méthode des mo-ments). Le théorème central limite et la δ-méthode conduisent alorsà √

nθ

(1

Xn− θ

)L→ N (0, 1).

On s’en sort sans estimer la variance en encadrant θ. On trouve ainsi,en notant q1− α

2le quantile d’ordre (1− α

2 ) de la loi N (0, 1), que 1Xn

1

1 +q1− α

2√n

,1

Xn

1

1−q1− α

2√n

est un intervalle de confiance asymptotique de niveau (1− α) pour θ.

En supposant toujours

vn (g− g(θ)) L→ N(0, σ2(θ)

),

on peut essayer d’identifier une fonction ϕ de classe C 1 sur Θ telle queϕ′(θ) = 1/σ(θ) pour tout θ. En effet, d’après la δ-méthode,

√n(

ϕ(g)− ϕ (g(θ))) L→ N (0, 1) ,

et cela conduit donc à l’intervalle de confiance asymptotique de niveau1− α pour g(θ)[

ϕ−1(

ϕ(g)−q1− α

2√n

), ϕ−1

(ϕ(g) +

q1− α2√

n

)].

Cette technique porte le nom de stabilisation de la variance.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Comme√

n(Xn − θ)L→ N (0, θ(1− θ)) ,

on cherche une fonction ϕ de classe C 1 sur ]0, 1[ telle que

ϕ′(θ) =1√

θ(1− θ)∀θ ∈ ]0, 1[.

On trouve ϕ(θ) = 2 arcsin√

θ, ce qui conduit à l’intervalle de confianceasymptotique[

sin2(

arcsin√

Xn −q1− α

2

2√

n

), sin2

(arcsin

√Xn +

q1− α2

2√

n

)].

30

Chapitre 4

Tests statistiques

4.1 Formalisme et démarche expérimentale

La notion de test, très importante, est sans doute aussi l’une des plus diffi-ciles à appréhender. Elle est liée au problème suivant : prendre une décisionqui ne permet que deux choix possibles, comme “oui” ou “non” et que l’onpeut toujours désigner, par commodité, par 0 et 1. Pour une élection avecseulement deux candidats, on souhaite déterminer lequel sera élu. Pour uncontrôle de qualité, il s’agit de décider si un processus de fabrication cor-respond ou non aux spécifications requises. Pour un essai médical, on veutsavoir si un médicament est suffisamment efficace, ou plus efficace qu’unautre, ou si ses effets secondaires sont admissibles, etc.

Dans le cadre du modèle statistique (H n, {Pθ}θ∈Θ), on se donne deuxsous-ensembles Θ0 et Θ1, disjoints et inclus dans Θ (on n’impose pas queleur union soit égale à Θ). Au vu d’une observation X = (X1, . . . , Xn) ∼ Pθ,on veut décider si θ0 (le vrai paramètre) appartient à Θ0 ou pas. Dans lanégative, on considère alors que θ0 ∈ Θ1.

On définit respectivement. H0 : θ ∈ Θ0 (l’hypothèse nulle) ;

. H1 : θ ∈ Θ1 (l’hypothèse alternative).

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. S’il s’agitd’un jeu de pile ou face, le problème de test associé à la question “La pièceest-elle équilibrée ou pas ?” s’écrit H0 : θ = 1/2 (i.e. Θ0 = {1/2}) contreH1 : θ 6= 1/2 (i.e. Θ1 = Θc

0).

31

Chapitre 4 Tests statistiques

Définition 15. Dans le cadre du problème de test de H0 contre H1, un test est unestatistique T à valeurs dans {0, 1} associée à la stratégie suivante : pour l’obser-vation X = (X1, . . . , Xn), H0 est conservée (respectivement rejetée) si T(X) = 0(respectivement T(X) = 1). La région de rejet du test est T−1({1}), i.e. l’ensembledes x ∈H n tels que T(x) = 1.

Un test peut donc toujours s’écrire T(X) = 1[X∈R], où R est la région derejet. Il est parfois plus naturel de l’écrire sous la forme T(X) = 1[h(X)∈R′],où h est une fonction mesurable appelée statistique de test. On dit aussisouvent, en commettant un abus de dénomination, que R′ est la région derejet associée à la statistique de test h(X).

En pratique, puisqu’on ne dispose que d’une réalisation x de X, le pro-tocole est alors le suivant : si x tombe dans la région de rejet R (ou sih(x) ∈ R′), on conserve H0, sinon on la rejette.

4.2 Risques d’un test

Un test est construit à partir d’une probabilité d’erreur, ou risque. Le pre-mier type de risque que l’on peut dégager est la probabilité de rejeter H0 àtort.

Définition 16. Le risque de première espèce du test T est l’application qui à chaqueélément θ ∈ Θ donne la probabilité de prendre la mauvaise décision :

α : Θ0 → [0, 1]θ 7→ EθT = P(T(X) = 1).

La taille du test est le réel α? défini par

α? = supθ∈Θ0

α(θ).

On dit que le test T est de niveau α ∈ ]0, 1[ si sa taille est inférieure ou égaleà α.

Pour un test de niveau suffisamment proche de 0, si la décision de reje-ter l’hypothèse nulle est convaincante, la décision de la conserver est, en

32


revanche, plus contestable. Par exemple, le test nul T ≡ 0, pour lequel l’hy-pothèse nulle est toujours choisie, possède un niveau nul. Pour autant, iln’apporte aucune information car la décision rendue est toujours la même.Ce phénomène nous conduit à distinguer un autre type de risque, en l’oc-currence la probabilité de conserver H0 à tort.

Définition 17. Le risque de seconde espèce du test T est l’application qui à chaqueélément θ ∈ Θ1 donne la probabilité de prendre la mauvaise décision :

β : Θ1 → [0, 1]θ 7→ 1−EθT = P(T(X) = 0).

A partir de là, on définit la puissance du test comme la fonction 1 − β,c’est-à-dire l’application qui à chaque élément de Θ1 associe la probabilitéde prendre la bonne décision.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune N (θ, 1), θ ∈ R. Onsouhaite tester

H0 : θ ≥ 1 contre H1 : θ < 1

ou, de façon équivalente, en définissant Θ0 = [1,+∞[ et Θ1 =]−∞, 1[,

H0 : θ ∈ Θ0 contre H1 : θ ∈ Θ1.

L’intuition conduit à prendre T(X) = 1[Xn<1] : ce test est fondé sur lastatistique de test Xn et la région de rejet ]−∞, 1[. En notant Φ la fonctionde répartition de la loi N (0, 1), on voit facilement que, ∀θ ≥ 1,

α(θ) = Φ(√

n(1− θ))

et, ∀θ < 1,β(θ) = 1−Φ

(√n(1− θ)

).

Par conséquent, la taille du test est Φ(0) = 1/2, ce qui n’est pas trèsconvaincant...

4.3 Dissymétrie des rôles de H0 et H1

L’exemple précédent montre qu’il est impossible de contrôler l’une et l’au-tre des hypothèses (c’est intuitivement clair, penser au cas dégénéré T ≡ 0).

33


On choisit donc de dissymétriser le problème, en faisant jouer un rôle par-ticulier à H0 et en maîtrisant exclusivement le risque de première espèce.Ainsi, on prendra pour H0 :

. Une hypothèse communément admise ;

. Une hypothèse de prudence, conservative ;

. Une hypothèse facile à formuler...

... en imposant que le risque de première espèce soit inférieur à α ∈ ]0, 1[,où α (le niveau) est fixé à l’avance par le statisticien. Reprenons l’exempledu test gaussien à la lumière de ce nouveau paradigme.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune N (θ, 1), θ ∈ R. Onsouhaite tester

H0 : θ ≥ 1 contre H1 : θ < 1.

La statistique de test naturelle est toujours Xn et l’on cherche, au vu de H1,une région de rejet de la forme ]−∞, kα[, soit T(X) = 1[Xn<kα]. Commentdéterminer kα ? En écrivant simplement la contrainte de niveau :

supθ≥1

P(Xn < kα) ≤ α.

Or, si N est une variable aléatoire de loi N (0, 1), on a, ∀θ ≥ 1,

P(Xn < kα) = P(√

n(Xn − θ) <√

n(kα − θ))

= P(

N <√

n(kα − θ))

.

Dès lors,supθ≥1

P(Xn < kα) = Φ(√

n(kα − 1))

.

Il suffit donc de choisir kα tel que Φ(√

n(kα − 1)) = α, soit

kα = 1 +qα√

n,

où qα désigne le quantile d’ordre α de la loi N (0, 1). En conclusion, onrejette l’hypothèse H0 si Xn < 1 + qα√

n .

Par ailleurs, pour θ < 1, on a 1− β(θ) = P(T(X) = 1). Ainsi,

1− β(θ) = P(

Xn < 1 +qα√

n

)= P

(√n(Xn − θ) <

√n(1− θ) + qα

)= P

(N <

√n(1− θ) + qα

),

34


la dernière égalité provenant du fait que, pour θ < 1, Xn ∼ N (θ, 1√n )

(et non pas N (1, 1√n ) : erreur classique !). La fonction puissance est donc

croissante, minorée par α et tend vers 1 lorsque θ tend vers l’infini.

4.4 Propriétés éventuelles d’un test

Lorsque la fonction puissance du test T passe strictement en dessous de sataille, la stratégie de décision qui en résulte devient incohérente. En effet, ilexiste alors θ1 ∈ Θ1 et θ0 ∈ Θ0 tels que Eθ1 T < Eθ0 T. On se retrouve alorsdans la situation paradoxale où la probabilité de rejeter H0 à raison est pluspetite que la probabilité de rejeter H0 à tort ! Dans un tel contexte, le testne sépare pas bien les hypothèses H0 et H1, d’où la nécessité de définir unconcept délimitant cette situation. C’est l’objet de la définition qui suit.

Définition 18. Un test T de niveau α ∈ ]0, 1[ est dit sans biais si sa puissance estsupérieure à α, i.e.

EθT ≥ α ∀θ ∈ Θ1.

Rien ne nous certifie, en général, qu’un test sans biais existe. Nous revien-drons sur ce problème ultérieurement.

Exemple. X = (X1, . . . , Xn) i.i.d., de densité commune sur R

fθ(x) = e−(x−θ)1[θ,+∞[(x),

où θ est un paramètre réel. Fixons α ∈ ]0, 1[. Dans le cadre du problèmede test de H0 : θ ≤ 0 contre H1 : θ > 0, nous allons montrer que le testT = 1[X∈R] associé à la région de rejet

R =

{(x1, . . . , xn) ∈ Rn : min

1≤i≤nxi ≥ −

ln α

n

}est de niveau α et sans biais. En effet, comme X1, . . . , Xn sont indépendanteset de même loi, on a lorsque θ ≤ 0 :

EθT = P(

min1≤i≤n

Xi ≥ −ln α

n

)= P

(X1 ≥ −

ln α

n

)n

=

{∫ +∞

− ln α/ne−(t−θ)dt

}n= αenθ.

35


Ainsi, EθT ≤ α (avec égalité si θ = 0), i.e. le test T est de niveau α. Cal-culons maintenant sa puissance : pour θ ≥ − ln α/n, EθT = 1 car toutesles variables aléatoires Xi sont P-p.s. plus grandes que θ ≥ − ln α/n ; pourθ ∈ ]0,− ln α/n[, EθT = αenθ ≥ α. Le test T est donc sans biais.

Définition 19. Un test T de niveau α ∈ ]0, 1[ est dit uniformément plus puissantparmi tous les tests de niveau α (UPPα) si, pour tout autre test T′ de niveau α, ona

EθT ≥ EθT′ ∀θ ∈ Θ1.

La notion d’optimalité envisagée est claire, un test UPP étant de puissancemaximale pour un niveau fixé. La question délicate de la caractérisationdes tests UPP fait l’objet de la section qui suit.

4.5 Tests de Neyman-Pearson

Dans cette section, H ⊂ Rd et (H n, {Pθ}θ∈Θ) est un modèle statistiquedominé par une mesure σ-finie ν et de vraisemblance Ln. Fixons deux pa-ramètres θ0 6= θ1 ∈ Θ et considérons le problème de test simple suivant :

H0 : θ = θ0 contre H1 : θ = θ1.

L’objectif de cette section est de donner, dans ce cas simple, des conditionssuffisantes pour qu’un test soit UPP. Le bon contexte est ici celui des testsde rapport de vraisemblance.

Définition 20. Un test T est dit de Neyman-Pearson (ou de rapport de vraisem-blance) s’il existe k ∈ R+ tel que

T = 1[Ln(X;θ1)>kLn(X;θ0)].

On note T = Tk et on désigne par T l’ensemble des tests de Neyman-Pearson.

Un test de Neyman-Pearson Tk s’interprète comme suit : si, par exemple,l’observation réalisée x ∈ H n est issue de la loi Pθ0 , la vraisemblance de xen θ0 est en principe plus grande que la vraisemblance de x en θ1, ce quiest exprimé par la propriété Ln(x; θ1) ≤ kLn(x; θ0) pour un certain k ∈ R+.Bien sûr, dans ce cas, T(x) = 0, i.e. H0 n’est pas rejetée.

Le résultat qui suit, appelé lemme de Neyman-Pearson, est relatif à l’exis-tence d’un test UPP dans la famille des tests de Neyman-Pearson.

36


Théorème 3. Soit α ∈ ]0, 1[. Si un test de T est de taille α, alors il est UPPα.

Démonstration. Soient T un test de niveau α et T?k ∈ T un test de taille α

avec k ∈ R+. Alors, pour tout x ∈H n,{T?(x)− T(x) > 0⇒ T?(x) = 1⇒ Ln(x; θ1) > kLn(x; θ0);T?(x)− T(x) < 0⇒ T?(x) = 0⇒ Ln(x; θ1) ≤ kLn(x; θ0).

Il s’ensuit,

(T?(x)− T(x)) Ln(x; θ1) ≥ k (T?(x)− T(x)) Ln(x; θ0),

et, par conséquent,

Eθ1 T? −Eθ1 T =∫

H n(T? − T)Ln(·; θ1)dν ≥ k

∫H n

(T? − T)Ln(·; θ0)dν.

On a donc Eθ1 T? −Eθ1 T ≥ k(Eθ0 T? −Eθ0 T). Or, Eθ0 T? ≥ Eθ0 T car T? estde taille α et T est de niveau α, ce qui montre que

Eθ1 T? ≥ Eθ1 T,

i.e. T? est UPPα.

Il existe de nombreuses extensions et raffinements divers du lemme deNeyman-Pearson, notamment en termes de forme des hypothèses. Nousrenvoyons le lecteur à l’ouvrage de Cadre et Vial (2012) pour un traitementplus en profondeur du problème.

4.6 Tests asymptotiques

A défaut d’informations suffisantes ou appropriées sur la loi de la statis-tique de test, on est amené, à l’instar des intervalles de confiance asympto-tiques, à définir la notion de test asymptotique.

Définition 21. Un test asymptotique Tn de niveau α ∈ ]0, 1[ est un test qui vérifie

supθ∈Θ0

limn→+∞

EθTn ≤ α.

37


La procédure de décision est calquée sur celle des tests à taille d’échantillonfinie. La seule différence est qu’un test asymptotique est construit pourcontrôler le risque de première espèce, mais seulement asymptotiquement.Dans ce contexte, il est raisonnable d’exiger une puissance asymptotiquemaximale. C’est le concept de convergence décrit ci-dessous.

Définition 22. Un test asymptotique Tn est dit convergent si

limn→+∞

EθTn = 1 ∀θ ∈ Θ1.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. On sou-haite confronter les hypothèses

H0 : θ = 1/2 contre H1 : θ 6= 1/2.

Pour ce faire, nous allons construire un test asymptotique de niveau 5%. Siθ = 1/2, d’après le théorème central limite :

2√

n (Xn − 0.5) L→ N (0, 1).

En notant q0.975 le quantile d’ordre 0.975 de la loi N (0, 1), on en déduit que

limn→+∞

P(2√

n |Xn − 0.5| > q0.975)= 1−Φ(q) + Φ(−q)

= 2 (1−Φ(q)) = 0.05,

si Φ désigne la fonction de répartition de la loi N (0, 1). Par suite, le testTn = 1[Xn∈R] défini par

R = {x ∈ R : 2√

n|x− 0.5| > q0.975}

est un test asymptotique de niveau 5%.

Ce test est de plus convergent car, si θ 6= 1/2,

limn→+∞

EθTn = limn→+∞

P(Xn ∈ R)

= limn→+∞

P(2∣∣√n(Xn − θ) +

√n(θ − 0.5)

∣∣ > q0.975)

= 1,

puisque√

n(θ − 0.5) tend vers l’infini.

Application numérique : Supposons que n = 1000. Comme q0.975 = 1.960,on rejette H0 dès lors que |Xn − 0.5| > 0.03. Si, par exemple, xn = 0.52, onconserve H0 au niveau (asymptotique) 5%.

38

Chapitre 5

Echantillons gaussiens etmodèle linéaire

5.1 Rappels sur les vecteurs gaussiens

Cas réel. Une variable aléatoire réelle X est dite gaussienne (ou de loi nor-male) de paramètres m ∈ R et σ2 ∈ R+ (σ ≥ 0) si sa fonction caractéristiques’écrit

E exp(iuX) = exp(

ium− σ2u2

2

)∀u ∈ R.

La loi de X est notée N (m, σ2), et l’on a EX = m et VX = σ2. Lorsqueσ = 0, on dit que X est dégénérée ; dans le cas contraire, elle admet ladensité par rapport à la mesure de Lebesgue

1√2πσ

exp(− (x−m)2

σ

)∀x ∈ R.

Cas vectoriel. Plus généralement, une variable aléatoire X à valeurs dansRd est un vecteur gaussien de Rd s’il existe M ∈ Rd et Σ une matrice d ×d réelle, symétrique et positive, tels que la fonction caractéristique de Xs’écrive

E exp (i〈u, X〉) = exp(

i〈u, M〉 − 12

u>Σu)∀u ∈ Rd.

(Les vecteurs sont considérés comme des matrices colonnes.) La loi de Xest notée Nd(M, Σ). Alors M est la moyenne de X, i.e. EX = M, et Σ est la

39

Chapitre 5 Echantillons gaussiens et modèle linéaire

matrice de variance-covariance de X, i.e.

Σ = E(X−EX)(X−EX)>.

Lorsque la matrice Σ est inversible (i.e., définie positive), X admet la densitépar rapport à la mesure de Lebesgue

1(2π)d/2

√det Σ

exp(− 1

2(x−M)>Σ−1(x−M)

)∀x ∈ Rd.

Lorsque Σ n’est pas inversible, on montre facilement que la loi de X estP-p.s. concentrée sur le sous-espace affine de Rd d’origine M et engendrépar les vecteurs propres correspondant aux valeurs propres non nulles deΣ.

Un moyen simple de montrer qu’un vecteur aléatoire est gaussien est d’uti-liser la définition équivalente (exercice) suivante :

Définition 23. Un vecteur aléatoire est gaussien si et seulement si toute combi-naison linéaire de ses composantes est une variable aléatoire réelle gaussienne.

Mentionnons pour finir deux résultats d’utilité constante dans la manipu-lation des vecteurs gaussiens, dont la preuve est laissée en exercice.

Proposition 2.(i) Transformation affine. Si A est une matrice réelle de format k× d, b ∈ Rk

et X est un vecteur de loi Nd(M, Σ), alors AX + b suit la loi Nk(AM +b, AΣA>).

(ii) Caractérisation de l’indépendance. Soit X un vecteur gaussien. Lescomposantes de X sont des variables aléatoires réelles indépendantes si etseulement si la matrice de variance-covariance de X est diagonale.

Ainsi, lorsque X = (X1, . . . , Xd) est un vecteur gaussien, on a l’équivalence :

∀i 6= j, Xi et Xj indépendantes⇔ Cov(Xi, Xj) = 0.

Rappelons que seule l’implication⇒ est vraie dans le cas général.

Exemple. Soient Z ∼ N (0, 1) et ε ∼ B(1/2) deux variables aléatoires in-dépendantes. Alors X1 = Z et X2 = (2ε− 1)Z sont des variables aléatoiresréelles gaussiennes (pourquoi ?), mais X = (X1, X2) n’est pas un vecteurgaussien, puisque X1 + X2 = 2εZ prend avec probabilité 1/2 la valeur 0.On notera que Cov(X1, X2) = 0 mais que X1 et X2 ne sont pas indépen-dantes (sans quoi X serait un vecteur gaussien...)

40


5.2 Théorème de Cochran

Dans le monde des vecteurs gaussiens, orthogonalité et indépendance seconfondent. Ce lien entre la géométrie et les probabilités a pour consé-quence le théorème ci-dessous, qui constitue la pierre angulaire de toute lastatistique des échantillons gaussiens.

Théorème 4 (Cochran). Soient σ > 0, X ∼ Nn(0, σ2Id) et V1, . . . , Vp dessous-espaces vectoriels orthogonaux de dimensions respectives r1, . . . , rp tels que

V1 ⊕ · · · ⊕Vp = Rn.

Alors les projections orthogonales π1, . . . , πp de X sur V1, . . . , Vp sont des vec-teurs gaussiens indépendants et, pour chaque i = 1, . . . , p,

1σ2‖πi‖2 ∼ χ2(ri).

Démonstration. Soit (eij)i,j une base orthonormée de Rn telle que pour cha-

que i = 1, . . . , p, (eij)1≤j≤ri est une base orthonormée de Vi. Si i = 1, . . . , p,

πi = MiX, où Mi est la matrice symétrique de format n× n définie par

Mi = (ei1 · · · ei

ri) (ei

1 · · · eiri)>.

Noter que puisque les vecteurs (eij)i,j sont normés et orthogonaux, Mi est

idempotente et de plus Mi Mj = 0 pour tout i 6= j.

Montrons la première assertion du théorème. Tout d’abord, X étant gaus-sien, toute combinaison linéaire de ses composantes est gaussienne, donc(π1, . . . , πp) est gaussien. De plus, la covariance entre les vecteurs aléa-toires πi et πj est nulle pour tout i 6= j. En effet, ces vecteurs aléatoiresétant centrés,

C(πi, πj) = E (πi −Eπi)(πj −Eπj

)>= Eπiπ

>j ,

C et E désignant respectivement la matrice de covariance et l’espérancesous la probabilité P. Il vient,

C(πi, πj) = EMiX(MjX)>

= MiEXX>Mj

= σ2Mi Mj,

41


d’où C(πi, πj) = 0. Par suite, π1, . . . , πp sont des vecteurs gaussiens indé-pendants.

Pour montrer la seconde assertion, fixons i = 1, . . . , p et remarquons quecomme Mi est symétrique et idempotente :

πi ∼ Nn(0, σ2Mi Id Mi

)= Nn(0, σ2Mi).

En notant Ei la matrice de format n× ri définie par Ei = (ei1 · · · ei

ri), on a

doncπi ∼ σEiNri(0, Id).

Or, si Z est un vecteur aléatoire de loi Nri(0, Id), ‖EiZ‖2 = ‖Z‖2 ∼ χ2ri

carE>i Ei = Id, d’où le théorème.

5.3 Echantillons gaussiens

Rappelons que pour une suite X1, . . . , Xn de variables aléatoires réelles, onnote

Xn =1n

n

∑i=1

Xi, S2n =

1n

n

∑i=1

(Xi − Xn)2 et S?2

n =1

n− 1

n

∑i=1

(Xi − Xn)2.

Le théorème ci-dessous met en évidence le rôle tenu par la loi de Studentet la loi du χ2 lorsque X1, . . . , Xn sont indépendantes et de même loi gaus-sienne.

Théorème 5. Soient m ∈ R, σ > 0 et X1, . . . , Xn des variables aléatoires indé-pendantes et de même loi N (m, σ2). Alors :

(i) Xn et S2n sont indépendantes.

(ii) (n− 1)S?2n /σ2 ∼ χ2(n− 1).

(iii)√

n(Xn −m)/S?n ∼ T (n− 1).

Remarque. Dans ce théorème, (iii) est à comparer à la propriété classique√n(Xn − m)/σ ∼ N (0, 1) satisfaite par la suite de variables aléatoires in-

dépendantes X1, . . . , Xn de même loi N (m, σ2).

42


Démonstration. Pour simplifier les écritures, considérons le cas m = 0 etσ = 1. Soit V le sous-espace vectoriel de Rn engendré par e = (1 · · · 1)>et X = (X1 . . . Xn)>. Le projecteur orthogonal P sur V est la matrice n× ndont tous les coefficients valent 1/n. De ce fait,

PX = Xne et (Id− P)X =

X1 − Xn...

Xn − Xn

.

Comme (Id− P)X est la projection orthogonale de X sur l’orthogonal deV et X suit la loi Nn(0, Id), on déduit du théorème de Cochran que PX estindépendant de (Id− P)X, et donc en particulier que Xn est indépendantde S?2

n , d’où (i). De plus, comme V est de dimension 1,

(n− 1)S?2n = ‖(Id− P)X‖2 ∼ χ2(n− 1)

d’après le théorème de Cochran, d’où (ii). Enfin, (iii) se déduit des ré-sultats précédents, car

√nXn et (n− 1)S?2

n sont indépendantes, et de loisrespectives N (0, 1) et χ2(n− 1).

Le Théorème 5 a des conséquences simples mais fondamentales pour letraitement des échantillons gaussiens i.i.d. Nous détaillons dans les pa-ragraphes qui suivent deux exemples (le test de Student et le test de Fi-sher), mais bien d’autres extensions sont possibles. A partir de mainte-nant, on considère un n-échantillon X = (X1, . . . , Xn) i.i.d., de loi communeN (m, σ2), avec m ∈ R et σ > 0.

Test de Student. Construisons un test de niveau α ∈ ]0, 1[ dans le pro-blème de test de

H0 : m ≥ m1 contre H1 : m < m1,

avec m1 un réel fixé. Un protocole naturel de rejet pour ce problème est dela forme Xn < kα, avec kα un seuil à préciser, car H0 est rejetée lorsque lamoyenne des observations prend une valeur anormalement faible. Cepen-dant, ce test n’est pas utilisable car la loi de la statistique Xn, en l’occurrenceN (m, σ2/n), fait intervenir les paramètres inconnus m et σ2.

43


Adaptons la construction du test à cette contrainte : si t(n−1)α est le quantile

d’ordre α de la loi T (n− 1) alors, sous H0 (i.e. m ≥ m1),

P(

Xn < m1 + t(n−1)α

S?n√n

)≤ P

(Xn < m + t(n−1)

αS?

n√n

),

et donc d’après le Théorème 5,

P(

Xn < m1 + t(n−1)α

S?n√n

)≤ P

(√n

Xn −mS?

n< t(n−1)

α

)= α,

avec égalité lorsque m = m1. Ainsi, le test de région de rejet

RStudent =

{(x1, . . . , xn) ∈ Rn : xn < m1 + t(n−1)

αs?n√

n

},

appelé test de Student, est de niveau (de taille) α. La procédure de décisionconsiste donc à rejeter H0 au niveau α lorsque (X1, . . . , Xn) ∈ RStudent.

Test de Fisher. Construisons un test de niveau α ∈ ]0, 1[ dans le problèmede test de

H0 : σ ≥ σ1 contre H1 : σ < σ1,

avec σ1 > 0 fixé. Une région de rejet naturelle pour ce problème de test estde la forme s?n < kα avec kα un seuil à préciser, car H0 est rejetée lorsque lavariance empirique prend une valeur anormalement faible. Soit χ2

α(n− 1)le quantile d’ordre α de la loi χ2(n− 1). Sous H0 (i.e. σ ≥ σ1),

P(

S?2n <

χ2α(n− 1)n− 1

σ21

)≤ P

(S?2

n <χ2

α(n− 1)n− 1

σ2)

.

D’après le Théorème 5,

P(

S?2n <

χ2α(n− 1)n− 1

σ21

)≤ P

( (n− 1)S?2n

σ2 < χ2α(n− 1)

)= α,

avec égalité lorsque σ = σ1. Le test de Fisher est le test de région de rejet

RFisher =

{(x1, . . . , xn) ∈ Rn : s?2

n <χ2

α(n− 1)n− 1

σ21

}.

Ce test est de niveau (de taille) α, et la procédure de décision consiste àrejeter H0 au niveau α lorsque (X1, . . . , Xn) ∈ RFisher.

44


5.4 Régression linéaire multiple

Modèle statistique. De manière générale, il s’agit de modéliser une ex-périence dont chaque observation est influencée par des régresseurs (dé-terministes), représentés par k vecteurs de Rn connus notés R1, . . . , Rk. Onimpose l’hypothèse d’homoscédasticité du modèle selon laquelle la matricede variance-covariance de la loi dont l’observation est issue est proportion-nelle à la matrice identité. En désignant par R = (R1 . . . Rk) la matrice desrégresseurs de format n × k, le modèle statistique admet la formulationsuivante :

X = Rθ + ε,

avec ε ∼ Nn(0, σ2Id), pour des paramètres inconnus θ ∈ Rk et σ > 0. Parailleurs, il admet la formulation équivalente suivante :(

Rn, {Nn(Rθ, σ2Id)}θ∈Rk,σ>0

).

En réduisant au besoin leur nombre, on peut toujours considérer que lesrégresseurs sont linéairement indépendants et que, par conséquent, la ma-trice des régresseurs R est de rang k.

Estimation des paramètres. Dans ce qui suit, E désigne l’espace vecto-riel engendré par les vecteurs R1, . . . , Rk. Prenons la projection orthogonaleXE

1 de X sur E ; elle s’écrit XE = Rθ avec θ un estimateur de θ. On peutdécrire explicitement θ en remarquant que, comme X − Rθ est dans l’or-thogonal de E, pour tout u ∈ Rk :

〈Ru, X− Rθ〉 = 0.

Par suite, 〈u, R>X − R>Rθ〉 = 0 pour tout u ∈ Rk et donc R>X = R>Rθ.Puisque R est de rang plein, la matrice R>R est inversible (pourquoi ?),d’où

θ = (R>R)−1R>X.

L’estimateur θ est sans biais car, si Eθ,σ désigne l’espérance sous la loi deX :

Eθ,σ θ = (R>R)−1R>Eθ,σX = (R>R)−1R>Rθ = θ.

1. uF désigne la projection orthogonale de u ∈ Rn sur le sous-espace vectoriel F de Rn.

45


Construisons maintenant un estimateur de σ2. Comme XE = Rθ + εE,X − XE = ε − εE, d’où ‖X − XE‖2 ∼ σ2χ2(n − k) d’après le théorème deCochran. La moyenne de la loi χ2(n− k) valant n− k, l’estimateur

σ2 =‖X− XE‖2

n− k

de σ2 est donc sans biais.

Test de l’utilité des régresseurs. Dans le cadre d’une modélisation tropcomplète, tous les régresseurs n’ont pas la même influence, et certains n’ontqu’une contribution mineure. Nous allons construire un test dans le but desupprimer ces régresseurs à l’influence réduite.

Fixons q = 0, . . . , k− 1. S’interroger sur l’utilité des (k− q) derniers régres-seurs mène au problème de test suivant :

H0 : ∀i = q + 1, . . . , k, θi = 0 contre H1 : ∃i = q + 1, . . . , k, θi 6= 0.

Sous H0, la matrice des régresseurs utiles R = (R1 . . . Rq) est la restric-tion de R à ses q premiers régresseurs. L’effet moyen Rθ se trouve alorsdans l’espace vectoriel V engendré par R1, . . . , Rq, dont la dimension estq car R1, . . . , Rq sont linéairement indépendants par hypothèse. Avec cesnotations, le problème de test se réécrit de la manière suivante :

H0 : Rθ ∈ V contre H1 : Rθ ∈ E \V.

Le principe de construction d’un tel test est de rejeter H0 lorsque les pro-jections orthogonales de l’observation sur E et sur V sont significative-ment différentes. Selon ce principe, une région de rejet naturelle est dela forme {x ∈ Rn : ‖xE − xV‖ ≥ s} avec s un seuil à préciser. Maisla loi de ‖XE − XV‖ dépend du paramètre inconnu σ. En effet, sous H0,XV = Rθ + εV car Rθ ∈ V et donc, d’après le théorème de Cochran appli-qué au vecteur gaussien ε,

‖XE − XV‖2 = ‖εE − εV‖2 ∼ σ2χ2(k− q).

Or, le théorème de Cochran montre aussi que sous H0, le vecteur aléatoireεE − εV = XE − XV est indépendant de ε − εE = X − XE. Enfin, ‖X −

46


XE‖2 ∼ σ2χ2(n − k). En réunissant ces observations, et en notant pouru ∈ Rn :

F(x) =‖xE − xV‖2/(k− q)‖x− xE‖2/(n− k)

,

on trouve F(X) ∼ F (k− q, n− k) sous H0. Si f (k−q,n−k)1−α désigne le quantile

d’ordre (1− α) de la loi de Fisher F (k− q, n− k) alors, sous H0,

P(

F(X) ≥ f (k−q,n−k)1−α

)= α.

La région de rejet

Rregress ={

x ∈ Rn : F(x) ≥ f (k−q,n−k)1−α

}nous donne donc un test de niveau (de taille) α pour le problème de testde H0 contre H1. La procédure de décision consiste à rejeter H0 au niveauα si l’observation X = (X1, . . . , Xn) tombe dans Rregress.

47

Chapitre 6

Information et exhaustivité

6.1 Information de Fisher

Dans la suite, ∇F(θ) désigne le gradient de F : Θ → R évalué en θ ∈ Θ.Par convention, le gradient d’une fonction n’est calculé en θ que si la fonc-tion est de classe C 1 sur un voisinage de θ. Par ailleurs, Covθ (respecti-vement Vθ) désigne la covariance (respectivement la matrice de variance-covariance) sous la loi Pθ.

On suppose dans tout le chapitre que (H n, {Pθ}θ∈Θ) est un modèle statis-tique dominé par une mesure σ-finie ν, avec H ⊂ Rd et Θ un ouvert de Rk.On note Ln la vraisemblance du modèle et on désigne comme d’habitudepar X = (X1, . . . , Xn) une observation générique issue de Pθ.

Définition 24. Supposons que ∇ ln Ln(X; θ) ∈ L2 pour chaque θ ∈ Θ. L’infor-mation de Fisher est la fonction In définie sur Θ telle que, pour chaque θ ∈ Θ,

In(θ) = Vθ (∇ ln Ln(X; θ)) .

Dorénavant, l’information de Fisher n’est évoquée que lorsque les condi-tions ci-dessus sont implicitement satisfaites.

Dans cette définition, si ∂/∂θi désigne la dérivée partielle relativement à lai-ème composante de θ :

In(θ) =

(Covθ

(∂

∂θiln Ln(X; θ),

∂

∂θjln Ln(X; θ)

))i,j=1,...,k

.

48

Chapitre 6 Information et exhaustivité

L’information de Fisher est donc une fonction à valeurs dans l’ensembledes matrices symétriques et positives. On notera en particulier que dans lecas réel (k = 1)

In(θ) = Vθ (∇ ln Ln(X; θ)) = Vθ

(∂

∂θln Ln(X; θ)

).

L’information précise donc le pouvoir de discrimination du modèle entredeux valeurs proches du paramètre du modèle : dans le cas k = 1, unegrande valeur pour In(θ) traduit une variation importante de la nature desprobabilités du modèle au voisinage de Pθ, d’où une discrimination de lavraie valeur du paramètre inconnu facilitée. A l’inverse, si In(θ) est petit, laloi est piquée et on est amené à rechercher le maximum de la vraisemblancedans une région plus vaste.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. La vrai-semblance Ln vaut, si θ ∈ ]0, 1[ et (x1, . . . , xn) ∈ {0, 1}n :

Ln(x1, . . . , xn; θ) = θnxn (1− θ)n(1−xn) .

Il vient facilement

In(θ) = Vθ (∇ ln Ln(X; θ)) =n2

θ2(1− θ)2 Vθ (Xn) =n

θ(1− θ).

Dans ce modèle, l’incertitude est faible pour θ proche de 0 et 1 alors qu’elleest d’autant plus grande que θ est proche de 1/2, ce qui se traduit par uneinformation In(θ) maximale pour θ proche de 0 et 1, et minimale pourθ = 1/2.

Dans une situation d’échantillonnage i.i.d., l’information de Fisher est pro-portionnelle à la taille de l’échantillon :

Proposition 3. Soit I l’information de Fisher du modèle (H , {Qθ}θ∈Θ) dominépar la mesure µ. Si, pour chaque θ ∈ Θ, Pθ = Q⊗n

θ , l’information de Fisher In dumodèle (H n, {Pθ}θ∈Θ) pour la mesure dominante ν = µ⊗n vaut

In(θ) = nI(θ) ∀θ ∈ Θ.

Démonstration. Si L désigne la vraisemblance du modèle (H , {Qθ}θ∈Θ), lavraisemblance Ln du modèle (H n, {Pθ}θ∈Θ) vérifie, d’après la Proposition1 :

∇ ln Ln(X1, . . . , Xn; θ) =n

∑i=1∇ ln L(Xi; θ).

49


On en déduit la relation

In(θ) = Vθ (∇ ln Ln(X; θ)) =n

∑i=1

Vθ (∇ ln L(Xi; θ)) = nVθ (∇ ln L(X1; θ)) ,

car les variables aléatoires X1, . . . , Xn sont indépendantes et de même loi.Comme I(θ) = Vθ (∇ ln L(X1; θ)), la proposition est démontrée.

Du point de vue des calculs, on se réfèrera souvent à la proposition quisuit, dont l’objectif principal est de donner une forme simplifiée pour l’in-formation de Fisher. Dans la suite, ∇2F(θ) désigne la matrice Hessienne deF : Θ → R évaluée en θ ∈ Θ. Par convention, l’utilisation de la notation∇2F(θ) signifie implicitement que F est de classe C 2 sur un voisinage de θ.

Proposition 4. Soit In l’information de Fisher du modèle (H n, {Pθ}θ∈Θ). Sup-posons que pour chaque θ ∈ Θ, il existe un voisinage V ⊂ Θ de θ tel quesupα∈V ‖∇Ln(·; α)‖ ∈ L(ν). Alors :(i) Eθ(∇ ln Ln(X; θ)) = 0.

(ii) Si, en outre, supα∈V ‖∇2Ln(·; α)‖ ∈ L1(ν), on a

In(θ) = −Eθ

(∇2 ln Ln(X; θ)

).

Les conditions de cette proposition ne sont pas aussi restrictives qu’ellespeuvent le sembler, car elles sont satisfaites par bon nombre de modèlesstatistiques. Pour la suite, on notera que, pour tout θ ∈ Θ, Ln(·; θ) > 0Pθ-p.s. En effet, puisque dPθ = Ln(·; θ)dν,

Pθ (Ln(·; θ) = 0) =∫{Ln(·;θ)=0}

Ln(·; θ)dν = 0.

Les dénominateurs en Ln(·; θ) éventuellement nuls ne posent donc aucunproblème lorsque l’on intègre contre dPθ = Ln(·; θ)dν.

Démonstration. Sous la condition supα∈V ‖∇Ln(·; α)‖ ∈ L1(ν), on a, d’aprèsle théorème de dérivation sous l’intégrale,∫

H n∇Ln(·; θ)dν = ∇

∫H n

Ln(·; θ)dν,

d’où, puisque dPθ = Ln(·; θ)dν et Pθ(Hn) = 1 :∫

H n∇Ln(·; θ)dν = ∇Pθ

(H n) = 0.

50


Or, comme dPθ = Ln(·; θ)dν et ∇ ln Ln(·; θ) = ∇Ln(·; θ)/Ln(·; θ),

Eθ (∇ ln Ln(X; θ)) =∫

H n∇ ln Ln(·; θ) Ln(·; θ)dν =

∫H n∇Ln(·; θ)dν,

d’où (i). Montrons maintenant (ii). Si F : Θ → R est de classe C 2, notonspour tout i, j = 1, . . . , k et θ ∈ Θ :

∇iF(θ) =∂F∂θi

(θ) et ∇2ijF(θ) =

∂2F∂θi∂θj

(θ).

Le théorème de dérivation sous l’intégrale montre que∫H n∇2

ijLn(·; θ)dν = ∇2ij

∫H n

Ln(·; θ)dν

sous l’hypothèse supα∈V ‖∇2Ln(·; α)‖ ∈ L1(ν), et donc∫H n∇2

ijLn(·; θ)dν = ∇ijPθ(Hn) = 0.

Par ailleurs, on vérifie que

∇2ij ln Ln(·; θ) =

∇2ijLn(·; θ)

Ln(·; θ)−∇iLn(·; θ)∇jLn(·; θ)

L2n(·; θ)

.

De ce fait,

Eθ

(∇2

ij ln Ln(X; θ))=∫

H n∇2

ij ln Ln(·; θ) Ln(·; θ)dν

= −∫

H n

∇iLn(·; θ)∇jLn(·; θ)

Ln(·; θ)dν

= −Eθ

(∇i ln Ln(X; θ)∇j ln Ln(X; θ)

),

car ∇ ln Ln(·; θ) = ∇Ln(·; θ)/Ln(·; θ). Or, par définition de l’information deFisher,

In(θ)ij = Covθ

(∇i ln Ln(X; θ),∇j ln Ln(X; θ)

)= Eθ

(∇i ln Ln(X; θ)∇j ln Ln(X; θ)

),

puisque Eθ(∇ ln Ln(X; θ)) = 0, d’où (ii).

51


Cette proposition légitime la définition qui suit, en donnant des conditionssuffisantes au concept de régularité d’un modèle statistique.

Définition 25. Le modèle statistique (H n, {Pθ}θ∈Θ) est dit régulier si les pro-priétés suivantes sont vérifiées en chaque θ ∈ Θ :

1. Son information de Fisher In en θ existe et est inversible.

2. Eθ(∇ ln Ln(X; θ)) = 0 et In(θ) = −Eθ(∇2 ln Ln(X; θ)).

Exemple. Le modèle statistique ({0, 1}n, {B(θ)⊗n}θ∈ ]0,1[) du jeu de pile ouface constitue un exemple de modèle régulier : d’une part, on constate queson information de Fisher est inversible pour chaque θ ∈ ]0, 1[ ; d’autre part,sa vraisemblance, qui vérifie les hypothèses de la Proposition 4, réponddonc au second jeu de conditions imposé dans la définition ci-dessus.

6.2 Efficacité

Dans cette section, on suppose en que le modèle (H n, {Pθ}θ∈Θ) est régu-lier, dominé par ν, de vraisemblance Ln et d’information de Fisher In. Parailleurs, le paramètre d’intérêt est g(θ), où g : Θ → R est une fonctionconnue, supposée réelle.

Définition 26. L’estimateur g est dit régulier s’il est d’ordre 2 et∫H n

g∇Ln(·; θ)dν = ∇{ ∫

H ng Ln(·; θ)dν

}.

Remarque. En pratique, l’intérêt de cette définition réside dans la remarquesuivante : si l’estimateur régulier g est sans biais, Eθ g = g(θ) pour chaqueθ ∈ Θ et donc, comme dPθ = Ln(·; θ)dν :∫

H ng∇Ln(·; θ)dν = ∇

{ ∫H n

g dPθ

}= ∇Eθ g = ∇g(θ).

Comme le montre le résultat qui suit, le risque quadratique est uniformé-ment minoré dans la famille des estimateurs réguliers et sans biais, nousdonnant ainsi une vitesse plancher.

52


Théorème 6 (Cramér-Rao). Si g est un estimateur régulier et sans biais, alors,pour tout θ ∈ Θ,

R(g; θ) ≥ ∇g(θ)> In(θ)−1∇g(θ).

Le minorant ∇g(θ)> In(θ)−1∇g(θ) s’appelle borne de Cramér-Rao.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. Le pa-ramètre d’intérêt est le paramètre du modèle, et l’estimateur sans biais Xnconstruit à partir du n-échantillon vérifie :

R(Xn; θ) =θ(1− θ)

n.

Nous savons également que l’information de Fisher In de ce modèle vaut

In(θ) =n

θ(1− θ).

Ainsi, le risque quadratique de l’estimateur Xn atteint la borne de Cramér-Rao du modèle. Par ailleurs, l’espace des observations étant fini, tout esti-mateur (d’ordre 2) du paramètre de ce modèle est régulier. En conséquence,tout estimateur d’ordre 2 sans biais θ du paramètre du modèle vérifie

R(θ; θ) ≥ R(Xn; θ) ∀θ ∈ Θ,

i.e. Xn est VUMSB.

Démonstration du Théorème 6. Soit θ ∈ Θ. L’estimateur g étant régulier etsans biais,

∇g(θ) = ∇Eθ g =∫

H ng∇Ln(·; θ)dν.

Comme ∇ ln Ln(·; θ) = ∇Ln(·; θ)/Ln(·; θ) et Eθ(∇ ln Ln(X; θ)) = 0 par ré-gularité du modèle, il vient

∇g(θ) = Eθ (g∇ ln Ln(X; θ)) = Eθ [(g− g(θ)) ∇ ln Ln(X; θ)] .

Pour u ∈ Rd, on déduit de l’inégalité de Cauchy-Schwarz que

〈u,∇g(θ)〉2 ={

Eθ

[(g− g(θ)

)〈u,∇ ln Ln(X; θ)〉

]}2

≤ R(g; θ)Eθ〈u,∇ ln Ln(X; θ)〉2.

53


Or, par définition de l’information de Fisher,

Eθ〈u,∇ ln Ln(X; θ)〉2 = u>{

Eθ

(∇ ln Ln(X; θ)∇ ln Ln(X; θ)>

)}u

= u>Vθ (∇ ln Ln(X; θ)) u

= u> In(θ)u,

et donc, si u = In(θ)−1∇g(θ) :

Eθ〈u,∇ ln Ln(X; θ)〉2 = ∇g(θ)> In(θ)−1∇g(θ).

De plus, ce même choix pour u donne 〈u,∇g(θ)〉 = ∇g(θ)> In(θ)−1∇g(θ).En conclusion,

R(g; θ) ≥ ∇g(θ)> In(θ)−1∇g(θ),

d’où le théorème.

Définition 27. L’estimateur g sans biais d’ordre 2 est dit efficace si son risquequadratique atteint la borne de Cramér-Rao du modèle, i.e. pour tout θ ∈ Θ :

R(g; θ) = ∇g(θ)> In(θ)−1∇g(θ).

Lorsqu’un estimateur efficace existe, la borne de Cramér-Rao fournit unmajorant pour la plus petite erreur quadratique dans la famille des estima-teurs sans biais d’ordre 2 (pas nécessairement réguliers). En particulier, sig est un estimateur VUMSB,

R(g; θ) ≤ ∇g(θ)> In(θ)−1∇g(θ) ∀θ ∈ Θ.

Les estimateurs efficaces sont souvent simples à caractériser. On peut parexemple montrer qu’un estimateur g régulier et sans biais est efficace si etseulement si il existe une fonction ψ : Θ→ Rk telle que pour tout θ ∈ Θ :

g = g(θ) + 〈ψ(θ),∇ ln Ln(X; θ)〉 P-p.s.

6.3 Exhaustivité

Dans le modèle statistique ({0, 1}n, {B(θ)⊗n}θ∈ ]0,1[) du jeu de pile ou face,l’observation (X1, . . . , Xn) issue de la loi B(θ)⊗n peut être résumée par sa

54


moyenne Xn, sans perte d’information sur θ. Pour s’en convaincre, il suffitde voir que pour chaque (x1, . . . , xn) ∈ {0, 1}n, on a :

P(X1 = x1, . . . , Xn = xn

∣∣ Xn = xn)=

P (X1 = x1, . . . , Xn = xn)

P(Xn = xn)

=θnxn(1− θ)n−nxn

Cnxnn θnxn(1− θ)n−nxn

=1

Cnxnn

,

car nXn suit la loi B(n, θ). La loi conditionnelle de (X1, . . . , Xn) sachant Xnest donc indépendante du paramètre θ. En d’autres termes, toute l’infor-mation sur θ contenue dans l’échantillon (X1, . . . , Xn) est en fait contenuedans Xn. On dit alors que Xn est une statistique exhaustive.

Définition 28. La statistique S(X) à valeurs dans Rq est dite exhaustive lorsque,pour chaque θ ∈ Θ, la loi conditionnelle de X = (X1, . . . , Xn) sachant S(X) nedépend pas de θ.

En clair, une statistique exhaustive élimine toute l’information superfluecontenue dans l’observation, en ne retenant que la partie informative surle paramètre du modèle.

Remarques.

1. Du point de vue technique, la statistique S(X) à valeurs dans Rq estexhaustive s’il existe un noyau de transition K sur Rq ×B(H n) telque pour tout θ ∈ Θ, A ∈ B(Rq) et B ∈ B(H n),

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫

AK(·, B)dPθ ◦ S−1.

Pour une telle statistique exhaustive, si g est un estimateur d’ordre 1,la quantité

Eθ (g|S(X)) =∫

H ng(x)K(S(X), dx)

est indépendante de θ, donc Eθ(g|S(X)) est une statistique.

2. Une statistique exhaustive peut prendre ses valeurs dans Rq avec q >1. Il peut donc, en particulier, s’agir d’un vecteur.

55


3. L’observation X = (X1, . . . , Xn) est toujours une statistique exhaus-tive car la loi conditionnelle de (X1, . . . , Xn) sachant (X1, . . . , Xn) estla mesure de Dirac en (X1, . . . , Xn). Cependant, cette statistique, quine résume pas l’information sur le paramètre contenue dans l’obser-vation, doit être délaissée au profit de n’importe quelle autre statis-tique exhaustive.

4. Il n’y a pas unicité des statistiques exhaustives. En effet, si S(X) =ϕ(T(X)) est exhaustive, avec ϕ une fonction borélienne quelconque,il en va de même de T(X) (pourquoi ?).

Malgré son apparence, la propriété d’exhaustivité est souvent simple à éta-blir, comme le montre le résultat suivant.

Théorème 7 (Neyman-Fisher). Supposons le modèle statistique (H n, {Pθ}θ∈Θ)dominé par ν, de vraisemblance Ln. Une statistique S(X) à valeurs dans Rq estexhaustive si et seulement si il existe deux fonctions boréliennes ψ : Rq × Θ →R+ et γ : H n → R+ telles que, pour tout θ ∈ Θ,

Ln(·; θ) = γ(·)ψ(S(·), θ

)ν-p.p.

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune N (θ, 1), θ ∈ R. Lamoyenne empirique Xn est une statistique exhaustive car la vraisemblanceLn pour la mesure de Lebesgue vaut

Ln(x1, . . . , xn; θ) =1

(2π)n/2 exp(− 1

2

n

∑i=1

(xi − θ)2)

=1

(2π)n/2 exp(− n

2(xn − θ)2

)exp

(− 1

2

n

∑i=1

(xi − xn)2)

,

pour tout (x1, . . . , xn) ∈ Rn et θ ∈ R.

Démonstration du Théorème 7. Supposons, pour simplifier la preuve, que lamesure dominante ν appartient au convexifié 1 de {Pθ}θ∈Θ, i.e.

ν = ∑i≥1

aiPθi ,

1. On peut effectivement montrer qu’il existe une probabilité du convexifié qui dominele modèle.

56


avec θi ∈ Θ, ai ≥ 0 pour chaque i ≥ 1 et ∑i≥1 ai = 1.

Dans ce cadre, nous allons montrer que S(X) est exhaustive si et seulementsi il existe une fonction borélienne ψ : Rq × Θ → R+ telle que, pour toutθ ∈ Θ,

Ln(·; θ) = ψ(S, θ) ν-p.p.

Fixons θ ∈ Θ et supposons que Ln(·; θ) = ψ(S, θ) ν-p.p. Comme dPθ =ψ(S, θ)dν, par définition de l’espérance conditionnelle pour la probabilitéν, notée Eν, on a

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫

H n1A(S)1B ψ(S, θ)dν

=∫

H nEν (1A(S)1B ψ(S, θ) | S)dν,

pour tout A ∈ B(Rq) et B ∈ B(H n). Puis, 1A(S)ψ(S, θ) étant une fonctionborélienne de S, on a en notant ν(B|S) = Eν(1B|S) :

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫

H nν(B |S)1A(S)ψ(S, θ)dν

=∫

Rqν(B | S = y)1A(y)ψ(y, θ) ν ◦ S−1(dy),

la dernière égalité provenant du théorème de transfert. Or, Pθ ◦ S−1 estabsolument continue par rapport à ν ◦ S−1, et sa densité est Eν(Ln(·; θ)|S =·) 2. De ce fait, dPθ ◦ S−1 = ψ(·, θ)dν ◦ S−1 car Ln(·, θ) = ψ(S, θ) est σ(S)-mesurable, d’où

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫

Aν(B |S = y) Pθ ◦ S−1(dy).

L’application (y, B) 7→ ν(B|S = y) définie sur Rq ×B(H n) est donc lenoyau de transition de la loi conditionnelle sachant S. Comme il est indé-pendant de θ, S est une statistique exhaustive.

2. En effet, pour tout A ∈ B(Rq), par définition de l’espérance conditionnelle :

Pθ ◦ S−1(A) =∫{S∈A}

Ln(·; θ)dν =∫{S∈A}

Eν(Ln(·; θ) | S)dν.

D’après le théorème de transfert, Pθ ◦ S−1(A) =∫

A Eν(Ln(·; θ) | S = y) ν ◦ S−1(dy), d’oùle résultat annoncé.

57


Réciproquement, supposons que S(X) est exhaustive. Pour tout θ ∈ Θ, laloi conditionnelle Pθ(· | S = ·) de l’observation sachant S est indépendantede θ ; notons-là P(· | S = ·). Si A ∈ B(Rq) et B ∈ B(H n), on a d’une part

ν ({S ∈ A} ∩ B) = ∑i≥1

aiPθi ({S ∈ A} ∩ B)

= ∑i≥1

ai

∫A

Pθi(B|S = y) ν(dy)

=∫

AP(B|S = y) ν(dy),

car ∑i≥1 ai = 1. D’autre part, en désignant par ν(·|S = ·) la loi condition-nelle sachant S, on sait que

ν ({S ∈ A} ∩ B) =∫

Aν(B|S = y) ν(dy).

Puisque ces relations sont vraies pour tout A ∈ B(Rq) et B ∈ B(H n), onen déduit par unicité que les lois conditionnelles P(· | S = ·) et ν(· | S = ·)sont les mêmes, d’où

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫

Aν(B | S = y) Pθ ◦ S−1(dy).

On a déjà remarqué que ψ(·, θ) = Eν(Ln(·; θ) | S = ·) est la densité dePθ ◦ S−1 par rapport à ν ◦ S−1. De ce fait,

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫

Aν(B | S = y)ψ(y, θ) ν ◦ S−1(dy).

Par ailleurs, la définition de l’espérance conditionnelle et le théorème detransfert donnent

P ({S(X) ∈ A} ∩ {X ∈ B}) =∫{S∈A}

1B Ln(·; θ)dν

=∫

AEν(1B Ln(·; θ) | S = y) ν ◦ S−1(dy).

Ces égalités étant vraies pour tout A ∈ B(Rq), il vient

ν(B | S = ·)ψ(·, θ) = Eν(1B Ln(·; θ) | S = ·) ν ◦ S−1-p.s.,

et doncEν

(1B (ψ(S, θ)− Ln(·; θ))

∣∣ S)= 0 ν-p.s.

58


En particulier,

Eν [1B (ψ(S, θ)− Ln(·; θ))] = EνEν

(1B (ψ(S, θ)− Ln(·; θ))

∣∣ S)

= 0.

Ceci étant vrai pour tout B ∈ B(H n), Ln(·; θ) = ψ(S, θ) ν-p.s., d’où lethéorème.

Le concept d’exhaustivité permet d’améliorer le risque d’un estimateur :

Théorème 8. [Rao-Blackwell] Soit S(X) une statistique exhaustive et g unestimateur d’ordre 2. Alors Eθ(g|S(X)) est un estimateur de même biais que gqui lui est préférable, i.e. pour tout θ ∈ Θ :

R (Eθ(g|S (X)) ; θ) ≤ R(g; θ).

Exemple. X = (X1, . . . , Xn) i.i.d., de loi commune B(θ), θ ∈ ]0, 1[. AlorsX1 est un estimateur sans biais de θ et Xn est une statistique exhaus-tive. A l’aide du théorème de Rao-Blackwell, nous allons améliorer l’er-reur quadratique de l’estimateur X1 en calculant Eθ(X1|Xn). Comme lesvariables aléatoires X1, . . . , Xn sont indépendantes et de même loi, pourtout i ∈ {1, . . . , n} et A ⊂ {k/n, k = 0, . . . , n} :

Eθ

(X11[Xn∈A]

)= Eθ

(Xi1[Xn∈A]

).

Ceci étant vrai pour chaque A ⊂ {k/n, k = 0, . . . , n}, on en déduit vial’unicité de l’espérance conditionnelle que Eθ(X1|Xn) = Eθ(Xi|Xn) P-p.s.Par suite,

Eθ(X1|Xn) =1n

n

∑i=1

Eθ(Xi|Xn) = Eθ(Xn|Xn) = Xn P-p.s.

Ainsi, l’estimateur préférable construit avec le théorème de Rao-Blackwelln’est autre que la moyenne empirique.

Démonstration du Théorème 8. Soit θ ∈ Θ. Par exhaustivité de S(X), η =Eθ[g|S(X)], qui ne dépend pas de θ, est donc un estimateur. De plus,puisque

Eθ η = EθEθ (g|S(X)) = Eθ g,

59


les estimateurs η = Eθ(g|S(X)) et g ont même biais. Notons maintenant,pour un estimateur ψ d’ordre 2,

Vθ(ψ) = Eθ‖ψ−Eθψ‖2.

Alors,

Vθ g = Eθ ‖(g− η) + (η −Eθ g)‖2

= Eθ‖g− η‖2 + Vθ η + 2Eθ〈g− η, η −Eθ η〉,

car g et η ont même biais. Or, comme η est une fonction borélienne deS(X),

Eθ

(〈g− η, η −Eθ η〉

∣∣S(X))= 〈Eθ (g− η|S(X)) , η −Eθ η〉= 〈η − η, η −Eθ η〉= 0.

De ce fait,

Eθ〈g− η, η −Eθ η〉 = EθEθ

(〈g− η, η −Eθ η〉

∣∣S(X))= 0,

et donc Vθ g ≥ Vθ η. D’après la décomposition (2.1),

R(η; θ) = ‖Eθ η − g(θ)‖2 + Vθ η ≤ ‖Eθ g− g(θ)‖2 + Vθ g = R(g; θ),


Conclusion. Chaque fois que l’on dispose d’un estimateur g et d’une sta-tistique exhaustive S(X), on a intérêt à remplacer g par Eθ(g|S(X)) qui,par définition, ne dépend pas de θ. On a alors deux cas de figure :

1. Ou bien Eθ(g|S(X)) = g P-p.s. : on n’a rien changé, mais g est déjàune fonction de S(X).

2. Ou bien Eθ(g|S(X)) 6= g P-p.s. : on gagne.

Il est donc clair qu’il est inutile de considérer des estimateurs qui ne sontpas fonctions de S(X). La difficulté en fait vient de ce qu’il n’y a pas unicitédes statistiques exhaustives.

60


6.4 Comparaison des statistiques exhaustives

Un problème se pose lorsque l’on dispose de deux statistiques exhaus-tives, S(X) et T(X). Laquelle doit-on utiliser de préférence ? Considéronsd’abord le cas le plus simple, lorsqu’il existe une fonction ϕ telle queS(X) = ϕ(T(X)). Alors toute fonction de S(X) est aussi une fonction deT(X) (mais la réciproque n’est pas nécessairement vraie). Si ϕ est inver-sible, l’ensemble des fonctions de S(X) est aussi celui des fonctions deT(X), et conditionner par rapport à l’une ou l’autre statistique conduit aumême résultat. Il est donc indifférent d’utiliser l’une ou l’autre.

La situation est différente si ϕ n’est pas inversible car il existe alors desfonctions de T(X) qui ne sont pas des fonctions de S(X). En particulier, siun estimateur g(T(X)) n’est pas une fonction de S(X), on a

h (S(X)) = Eθ

[g (T(X))

∣∣S(X)]6= g (T(X))

et le Théorème 8 nous dit que, pour le risque quadratique, h(S(X)) serameilleur que g(T(X)), ce qui montre qu’il convient de préférer S(X) àT(X).

On a donc des statistiques exhaustives plus ou moins “grosses”. Par ex-emple, dans un n-échantillon N (θ, 1), Xn est exhaustive, mais aussi lecouple (X1, Xn), 1/Xn (qui existe P-p.s.), ou (X1, . . . , Xn). Il est clair queXn est meilleure que (X1, Xn) ou (X1, . . . , Xn) d’après ce qui précède, etéquivalente à 1/Xn. On a ainsi intérêt à chercher des statistiques “minima-les” au sens précédent. Chaque fois que l’on remplace S(X) par ϕ(S(X))où ϕ n’est pas bijective, on gagne et clairement ϕ(T(X)) est plus simple.C’est très clair lorsque l’on remplace un vecteur par un nombre réel.

Exemples.

1. X = (X1, . . . , Xn) i.i.d., de densité commune (par rapport à une me-sure de référence sur Rd) de la forme

fθ(x) = C(θ) exp [Q(θ)T(x)] h(x),

avec θ ∈ Θ ⊂ R, Q(θ), T(x) ∈ R, et C(θ), h(x) ∈ R+. Ce modèleporte le nom de modèle exponentiel général (de dimension 1) et on vé-rifiera que la plupart des lois classiques (lois normale, exponentielle,

61


gamma, Bernoulli, binomiale, de Poisson, etc.) tombent dans son es-carcelle. La vraisemblance s’écrit, pour (x1, . . . , xn) ∈ Rdn et θ ∈ Θ,

Ln(x1, . . . , xn; θ) = Cn(θ) exp

[Q(θ)

n

∑i=1

T(xi)

]n

∏i=1

h(xi),

et le Théorème 7 indique que ∑ni=1 T(Xi) et Tn = 1

n ∑ni=1 T(Xi) sont

deux statistiques exhaustives équivalentes. Dans le modèle gaussienN (m, σ2), m ∈ R et σ2 > 0, Xn est exhaustive si σ est connu et∑n

i=1(Xi − m)2 l’est lorsque c’est m qui est inconnu. Pour un n-éch-antillon de loi de Poisson P(θ), c’est Xn qui est exhaustive.

2. X = (X1, . . . , Xn) i.i.d., de densité commune U ([0, θ]), θ > 0. Dans cecas, comme déjà vu, pour (x1, . . . , xn) ∈ [0, θ]n,

Ln(x1, . . . , xn; θ) = θ−n1[0,θ](x(n)),

où x(n) = max(x1, . . . , xn), ce qui montre que X(n) est une statistiqueexhaustive. La situation est différente si l’on considère les lois uni-formes U ([θ, θ + 1]) avec θ ∈ R, ou U ([−θ, θ]) avec θ > 0. Dans cedernier cas, en notant x(1) = min(x1, . . . , xn),

Ln(x1, . . . , xn; θ) = (2θ)−nθ−n1[−θ,+∞[(x(1))1]−∞,θ](x(n)),

et le couple (X(1), X(n)) forme une statistique exhaustive. L’autre ex-emple se traite de la même façon.

3. X = (X1, . . . , Xn) i.i.d., de densité commune fθ(x), θ ∈ Θ, par rapportà une mesure de référence sur Rd. Le vecteur des statistiques d’ordre(X(1), . . . , X(n)) est toujours exhaustif car

Ln(x1, . . . , xn; θ) =n

∏i=1

fθ(x(i)), avec x(1) ≤ x(2) ≤ · · · ≤ x(n).

Dans un modèle d’échantillonnage, seul compte l’ensemble des va-leurs (avec éventuelles répétitions) prises par les observations, pasl’ordre dans lequel on les a observées.

62

Chapitre 7

Tests d’adéquation etd’indépendance

Les tests d’adéquation tels que le test du χ2 d’adéquation et le test deKolmogorov-Smirnov ont pour objectif de préciser la loi dont l’observa-tion est issue. Les tests d’indépendance, comme le test du χ2 d’indépen-dance, étudient l’absence de lien entre deux observations. La constructionet l’étude de ces trois tests fait l’objet de ce chapitre.

7.1 Test du χ2 d’adéquation

Dans cette section, H est un ensemble fini identifié à H = {1, . . . , d}.Considérons le modèle statistique (H n, {P⊗n}P∈P), P désignant l’ensem-ble des probabilités sur H de support H , c’est-à-dire que pour chaqueP ∈ P , P(j) > 0 ∀j ∈ H . Ce modèle est paramétrique car chaque loi deP est à support dans l’ensemble fini H .

Fixons P0 ∈P . Nous allons construire un test asymptotique dans le cadredu problème de test de

H0 : P = P0 contre H1 : P 6= P0.

Selon le principe habituel, l’enjeu est de trouver une statistique mesurantla proximité entre P0 et une version empirique de la loi de l’échantillon.Cette statistique doit être de surcroît asymptotiquement libre sous H0, ce

63

Chapitre 7 Tests d’adéquation et d’indépendance

qui signifie que sa loi asymptotique sous H0 ne doit pas dépendre de la loide l’échantillon. Dans le cadre du test du χ2 d’adéquation, elle est donnéepar la statistique de Pearson, définie pour l’observation X = (X1, . . . , Xn) par

Dn(X, P0) = nd

∑j=1

(Pn(j)− P0(j)

)2

P0(j),

où Pn désigne la mesure définie par

Pn(j) =1n

n

∑i=1

1{j}(Xi) ∀j ∈H .

Cette statistique, également appelée pseudo-distance du χ2, est un bon can-didat pour construire un test asymptotique dans le cadre du problème detest de H0 contre H1.

Théorème 9. Soient P ∈P et X = (X1, . . . , Xn) ∼ P⊗n.(i) Sous H0, i.e. P = P0,

Dn(X, P0)L→ χ2(d− 1).

(ii) Sous H1, i.e. P 6= P0,Dn(X, P0)

P→ +∞.

Dans le problème de test de H0 contre H1, la région de rejet d’un test basésur la statistique de Pearson est de la forme {x ∈ H n : Dn(x, P0) ≥ s}, carH0 est rejetée lorsque la statistique de test prend des valeurs anormalementgrandes. Le test du χ2 d’adéquation est le test de région de rejet

R(α) ={

x ∈H n : Dn(x, P0) ≥ χ21−α(d− 1)

},

avec α ∈ ]0, 1[ et χ21−α(d− 1) le quantile d’ordre (1− α) de la loi χ2(d− 1).

Ce test asymptotique est de niveau α puisque, d’après la propriété (i) duThéorème 9, sous H0,

limn→+∞

P (X ∈ R(α)) = limn→+∞

P(

Dn(X, P0) ≥ χ21−α(d− 1)

)= α.

Il est de plus convergent d’après l’assertion (ii). La procédure de testest donc définie ainsi : H0 est rejetée au niveau asymptotique α lorsque(X1, . . . , Xn) ∈ R(α).

Remarques.

64


1. Il s’agit d’un test asymptotique. En pratique, on demande souventque n ≥ 30 et nP0(j) ≥ 5 pour chaque j ∈ H . Si cette dernièrecondition n’est pas vérifiée, on effectue des regroupements de classesvoisines.

2. Ce test est en pratique souvent utilisé dans le cadre plus général oùl’espace des observations n’est pas fini : le principe est de se rame-ner au cas fini en considérant une partition finie de l’espace des ob-servations ; toute la difficulté est alors de choisir convenablement lapartition.

Exemple. Une usine fabrique des bonbons de 8 couleurs différentes : bleu,vert, marron, rose, rouge, orange, jaune, violet. L’objectif est de savoir si leprocédé de mise en sachets des bonbons produit une répartition uniformedes 8 couleurs. Le tableau ci-dessous donne la répartition dans un sachetcontenant n = 83 bonbons :

Bleu Vert Marron Rose Rouge Orange Jaune Violet15 11 11 10 10 10 8 8

En attribuant un chiffre à chaque couleur et en considérant que les cou-leurs des bonbons sont indépendantes, le modèle statistique associé à cetteexpérience est (H n, {P⊗n}P∈P), où H = {1, . . . , 8} et P est l’ensembledes probabilités de support H . Le problème de test s’écrit H0 : P = P0contre H1 : P 6= P0, avec P0 la loi uniforme sur H . Le quantile d’ordre 95%de la loi χ2(7) vaut environ 14.07 donc, pour un niveau α = 5%, la régionde rejet est

R(0.05) ={

x ∈H n : Dn(x, P0) ≥ 14.07}

.

Avec l’observation x = (x1, . . . , xn) ∈ H n résumée dans le tableau ci-dessus, la statistique de Pearson vaut Dn(x, P0) = 3.27. Par suite, x /∈R(0.05), i.e. H0 est conservée au niveau 5%.

Preuve du Théorème 9. Montrons tout d’abord (ii). Si P 6= P0, il existe j ∈Htel que P(j) 6= P0(j). La propriété annoncée se déduit de l’inégalité

Dn(X, P0) ≥ n(

Pn(j)− P0(j))2

P0(j),

car Pn(j) P→ P(j) d’après la loi des grands nombres.

65


Montrons maintenant (i). Soient p0,√

p0 et Y1, . . . , Yn les vecteurs de Rd

définis par

p0 =

P0(1)...

P0(d)

,√

p0 =

√

P0(1)...√

P0(d)

et Yi =

1{1}(Xi)...

1{d}(Xi)

,

pour i = 1, . . . , n. En désignant par Yn la moyenne empirique de Y1, . . . , Yn,on trouve la représentation :

Dn(X, P0) = ‖Zn‖2, avec Zn =√

n diag(√

p0)−1(Yn − p0),

avec diag(α) la matrice diagonale dont les éléments diagonaux sont ceuxdu vecteur α = (α1 . . . αd)

>. Comme Y1 a (sous H0) pour moyenne p0 etpour matrice de variance-covariance V = diag(p0)− p0p>0 , on obtient, avecle théorème central limite,

√n(Yn − p0)

L→ Nd(0, V).

Par suite,Zn

L→ diag(√

p0)−1Nd(0, V).

Or, un calcul montre que diag(√

p0)−1Vdiag(

√p0)−1 = Id − √p0

√p0>

d’où, si Γ = Id−√p0√

p0> :

ZnL→ Nd(0, Γ).

Il reste à identifier la loi du carré de la norme euclidienne d’un vecteuraléatoire de loi Nd(0, Γ). La matrice Γ est le projecteur orthogonal dansl’orthogonal du sous-espace vectoriel E engendré par le vecteur

√p0. Elle

est en particulier symétrique et idempotente. Si N est un vecteur aléatoirede loi Nd(0, Id), sa projection orthogonale ΓN sur l’orthogonal de E a doncpour loi Nd(0, Γ). L’orthogonal de E formant un espace vectoriel de dimen-sion d− 1, le théorème de Cochran montre que ‖ΓN‖2 suit la loi χ2(d− 1).Par suite,

Dn(X, P0) = ‖Zn‖2 L→ χ2(d− 1),


66


Remarque. Le test du χ2 d’ajustement peut être étendu au cas où l’on saituniquement que la loi sous H0 appartient à une famille de lois de référenceparamétrées par θ ∈ Θ ⊂ Rk. On se ramène alors au cas classique enestimant le paramètre inconnu sous H0 par maximum de vraisemblance.On peut établir dans ce contexte un analogue du Théorème 9, avec une loilimite égale à χ2(d− 1− k).

7.2 Test du χ2 d’indépendance

Dans cette section, H est le produit de deux ensembles finis, identifié àH = H1 ×H2 avec H1 = {1, . . . , d} et H2 = {1, . . . , `}. Considérons lemodèle statistique (H n, {P⊗n}P∈P), où P désigne l’ensemble des proba-bilités sur H de support H , i.e. P(j, k) > 0 ∀(j, k) ∈ H . Ce modèle estparamétrique car chaque loi de P est à support dans l’ensemble fini H .

Basé sur une observation ((X1, Y1), . . . , (Xn, Yn)) ∈H n, un test d’indépen-dance précise si les extractions X = (X1, . . . , Xn) et Y = (Y1, . . . , Yn) sontindépendantes. En notant Pindep l’ensemble des probabilités produits deP du type P1 ⊗ P2, où P1 et P2 sont des lois marginales à support dans H1et H2, le problème de test se formule de la manière suivante :

H0 : P ∈Pindep contre H1 : P /∈Pindep.

Le test est fondé sur une comparaison asymptotique entre la loi empiriquede l’échantillon ((X1, Y1), . . . , (Xn, Yn)) et le produit des lois empiriques dessous-échantillons (X1, . . . , Xn) et (Y1, . . . , Yn). Soient donc Pn la probabilitéjointe

Pn(j, k) =1n

n

∑i=1

1{j,k}(Xi, Yi) ∀(j, k) ∈H ,

et Pn,1, Pn,2 les probabilités marginales

Pn,1(j) =1n

n

∑i=1

1{j}(Xi) et Pn,2(k) =1n

n

∑i=1

1{k}(Yi) ∀(j, k) ∈H .

La statistique de test compare les lois empiriques Pn et Pn,1 ⊗ Pn,2 de lamanière suivante :

Dn(X, Y) = nd

∑j=1

`

∑k=1

(Pn(j, k)− Pn,1(j)Pn,2(k)

)2

Pn(j, k),

67


avec la convention 0/0 = 0.

Comme le montre le théorème ci-dessous, cette statistique est asymptoti-quement libre sous H0. Combinée avec le fait que la statistique Dn(X, Y)compare les lois empiriques Pn et Pn,1⊗ Pn,2, cette propriété en fait un can-didat pour la construction du test de H0 contre H1.

Théorème 10. Soient P ∈P et ((X1, Y1), . . . , (Xn, Yn)) ∼ P⊗n.

(i) Sous H0, i.e. P ∈Pindep,

Dn(X, Y)L→ χ2(d− 1)(`− 1).

(ii) Sous H1, i.e. P /∈Pindep,

Dn(X, Y)P→ +∞.

Dans le problème de test de H0 contre H1, un test basé sur la statistiqueDn est associé à une région de rejet de la forme {(x, y) ∈ H n

1 ×H n2 :

Dn(x, y) ≥ s}, car H0 est rejetée lorsque Dn prend des valeurs anormale-ment grandes. Le test du χ2 d’indépendance est le test asymptotique derégion de rejet

R(α) ={(x, y) ∈H n

1 ×H n2 : Dn(x, y) ≥ χ2

1−α(d− 1)(`− 1)}

,

avec α ∈ ]0, 1[ et χ21−α(d− 1)(`− 1) le quantile d’ordre (1 − α) de la loi

χ2(d− 1)(`− 1). Ce test est de niveau α puisque, d’après la propriété (i)du Théorème 10, pour chaque P ∈Pindep :

limn→+∞

P ((X, Y) ∈ R(α)) = limn→+∞

P(

Dn(X, Y) ≥ χ21−α(d− 1)(`− 1)

)= α.

Il est de plus convergent d’après l’assertion (ii) du même théorème. Laprocédure de test est donc définie ainsi : H0 est rejetée au niveau asympto-tique α lorsque ((X1, . . . , Xn), (Y1, . . . , Yn)) ∈ R(α).

Exemple. Pour savoir si, dans la population féminine, les couleurs des yeuxet des cheveux sont indépendantes, on exploite une étude publiée en 1951portant sur 2000 femmes parisiennes. Les données sont résumées dans letableau suivant :

68


Cheveux \ Yeux Clairs Mixtes Bruns TotalRoux 14 9 8 31Clairs 745 253 305 1303Foncés 146 187 333 666Total 905 449 646 2000

En attribuant un chiffre à chaque couleur et en considérant que les indi-vidus de l’étude sont indépendants, le modèle statistique associé à cetteexpérience est (H n, {P⊗n}P∈P), avec H = {1, 2, 3} × {1, 2, 3}, et le pro-blème de test s’écrit H0 : P ∈ Pindep contre H1 : P /∈ Pindep. Pour donnerune réponse à la question initiale, utilisons le test du χ2 d’indépendancedécrit plus haut, avec un niveau α = 5%. Le quantile d’ordre 95% de la loiχ2(4) vaut environ 9.49, donc la région de rejet est

R(0.05) ={(x, y) ∈ {1, 2, 3}n × {1, 2, 3}n : Dn(x, y) ≥ 9.49

}.

Pour l’observation ((x1, y1), . . . , (xn, yn)) ∈ H n résumée dans le tableauci-dessus, la statistique de test vaut Dn(x, y) = 233.28 si x = (x1, . . . , xn) ety = (y1, . . . , yn). Par suite, (x, y) ∈ R(0.05) donc H0 est rejetée au niveau5% : les couleurs des yeux et des cheveux sont liées.

La preuve de l’assertion (ii) du Théorème 10 est calquée sur celle de l’as-sertion (ii) du Théorème 9, en exhibant un couple (j, k) ∈ H tel queP(j, k) 6= P1(j)P2(k), où P1 et P2 désignent les lois marginales selon lapremière et la seconde composante de P /∈ Pindep. En revanche, la dé-monstration complète de l’assertion (i) est longue et technique, et elle estadmise dans le cadre de ce cours.

Le cas du test du χ2 d’homogénéité. Il s’agit d’une situation particulièreoù l’une des deux variables (par exemple X) ne peut plus raisonnablementêtre considérée comme aléatoire. Illustrons ceci par une étude sur des étu-diants de l’UPMC, pour lesquels on cherche à savoir si le niveau d’étude(L3, M1 ou M2) est indépendant de l’opinion politique (gauche, centre,droite ou autre). Dans ce cas, si l’opinion politique peut être correctementmodélisée par une variable aléatoire Y à quatre modalités, il n’en est pasde même du niveau d’étude à trois modalités X, qui n’est pas aléatoire etnous est imposé par l’expérience (on connaît à l’avance les effectifs de L3,

69


M1 et M2). Dans ce contexte, le problème n’est donc pas de tester l’indé-pendance entre X et Y, mais plutôt de savoir si le comportement politiquedes étudiants est homogène d’une année sur l’autre. Tout se passe en faitcomme si l’on disposait de trois échantillons i.i.d., indépendants entre eux,issus des variables aléatoires Y1 (pour le L3), Y2 (pour le M1) et Y3 (pourle M2), la question posée étant désormais :“Ces trois échantillons ont-ils lamême loi (H0) ou pas (H1) ?”. On parle alors de test d’homogénéité, et il estfacile de voir que le test du χ2 d’indépendance s’adapte sans problème àce contexte, avec exactement les mêmes formules. Choisir entre un test duχ2 d’indépendance et d’homogénéité relève plus d’un problème d’interpré-tation de l’expérience (ou de protocole expérimental) que d’une questionmathématique.

7.3 Test de Kolmogorov-Smirnov

L’objectif du test de Kolmogorov-Smirnov est de préciser, comme dans letest du χ2 d’adéquation, si l’observation est issue d’une loi fixée par l’utili-sateur. Cependant, leurs périmètres d’utilisation sont complémentaires car,dans le cas du test de Kolmogorov-Smirnov, l’espace des observations estnécessairement non fini.

Le modèle statistique de cette section est (Rn, {P⊗n}P∈P), P désignantl’ensemble des probabilités sur R sans atomes, i.e. P(x) = 0 pour toutx ∈ R et P ∈P . Soit P0 ∈P fixé. Le problème de test s’énonce :

H0 : P = P0 contre H1 : P 6= P0.

L’enjeu est de trouver une statistique mesurant la proximité entre P0 et unemesure empirique, et qui soit de surcroît libre, ou asymptotiquement libre,sous H0. Dans cet esprit, une idée naturelle consiste à comparer la fonctionde répartition de P0 à la fonction de répartition d’un n-échantillon. Soitdonc, pour chaque X = (X1, . . . , Xn) ∈ Rn, FX,n la fonction

FX,n(t) =1n

n

∑i=1

1]−∞,t](Xi) ∀t ∈ R.

Il est instructif de noter que FX,n, appelée fonction de répartition empirique,n’est autre que la fonction de répartition associée à la loi uniforme sur

70


l’ensemble {X1, . . . , Xn}. La statistique de Kolmogorov-Smirnov compareP0 à la probabilité associée à l’observation X = (X1, . . . , Xn) par le biais deleurs fonctions de répartition. Elle est définie par

Kn(X, P0) = ‖FX,n − F0‖∞,

avec F0 la fonction de répartition de la loi P0, et ‖ · ‖∞ la norme uniforme,i.e.

‖ f ‖∞ = supt∈R

| f (t)| ,

pour chaque fonction bornée f : R→ R.

Remarque. En pratique, la statistique de Kolmogorov-Smirnov est simpleà calculer. Si P ∈ P et X = (X1, . . . , Xn) ∼ P⊗n, notons (X(1), . . . , X(n)) levecteur des statistiques d’ordre associé à l’échantillon, c’est-à-dire le réar-rangement des variables aléatoires X1, . . . , Xn tel que

X(1) < · · · < X(n) P-p.s.

Observer que ces inégalités sont strictes car P est sans atomes. Comme F0est continue et croissante, et comme la fonction

R 3 t 7→ FX,n(t) =1n

n

∑i=1

1]−∞,t](Xi) =1n

n

∑i=1

1]−∞,t](X(i))

prend ses valeurs dans {k/n, k = 0, . . . , n}, en notant X(0) = 0 et X(n+1) =+∞ :

Kn(X, P0) = max0≤k≤n

maxt∈[X(k),X(k+1)]

∣∣∣∣ kn− F0(t)

∣∣∣∣= max

1≤k≤nmax

{∣∣∣∣ kn− F0(X(k))

∣∣∣∣ ,∣∣∣∣k− 1

n− F0(X(k))

∣∣∣∣} .

Le calcul explicite de la statistique de Kolmogorov-Smirnov requiert doncau préalable un réarrangement des observations.

La première propriété importante de la statistique de Kolmogorov-Smirnovest énoncée dans le résultat ci-dessous.

Théorème 11. Si X = (X1, . . . , Xn) ∼ P⊗n0 , Kn(X, P0) est une statistique libre,

i.e. sa loi ne dépend pas de P0.

71


Démonstration. Soit F(−1)0 le pseudo-inverse de F0 défini pour chaque s ∈

[0, 1] parF(−1)

0 (s) = inf{t ∈ R : F0(t) ≥ s}

(par convention, inf R = −∞ et inf ∅ = +∞). On constate que F(−1)0 (s) ≤

t ⇔ s ≤ F0(t) et, puisque F0 est continue car P0 est sans atomes, F0 ◦F(−1)

0 (s) = s pour tout s ∈ ]0, 1[. Par suite (exercice), pour chaque i =1, . . . , n et s ∈ ]0, 1[,

P(F0(Xi) ≤ s) = P(Xi ≤ F(−1)

0 (s))= F0 ◦ F(−1)

0 (s) = s,

les cas s = 0 et s = 1 donnant les valeurs 0 et 1. Ainsi, chaque variablealéatoire Ui = F0(Xi) suit la loi U ([0, 1]). Comme F0 est croissante, on ob-tient en prenant la notation (U(1), . . . , U(n)) de la remarque précédente pourdésigner les statistiques d’ordre de (U1, . . . , Un) :

(U(1), . . . , U(n)) =(

F0(X(1)), . . . , F0(X(n))).

Finalement, la représentation

Kn(X, P0) = max1≤k≤n

max{∣∣∣∣ k

n− F0(X(k))

∣∣∣∣ ,∣∣∣∣k− 1

n− F0(X(k))

∣∣∣∣}de la remarque montre que la statistique de Kolmogorov-Smirnov est libre.

Nous pouvons utiliser cette propriété de liberté et calculer les quantilesde la loi commune, par exemple en simulant des réalisations de Kn(X, P0)lorsque P0 est la loi uniforme sur [0, 1]. Une fois connus ces quantiles uni-versels ζn,α pour α ∈ ]0, 1[, le test de Kolmogorov-Smirnov de niveau α

rejette H0 si Kn(X, P0) prend des valeurs anormalement grandes, soit

T(X) = 1[Kn(X,P0)≥ζn,1−α].

Si le Théorème 11 fournit une statistique de test pour le problème de testde H0 contre H1, il ne donne cependant aucune information concernant sapuissance. En revanche, une information de cette nature peut être fourniedans le cadre d’un test asymptotique car, si X = (X1, . . . , Xn) ∼ P⊗n avecP ∈P et P 6= P0, √

n Kn(X, P0)P→ +∞.

72


Cette propriété s’obtient en invoquant la loi des grands nombres et la mi-noration √

n Kn(X, P0) ≥√

n |FX,n(x)− F0(x)|

avec x ∈ R tel que F(x) 6= F0(x), F désignant la fonction de répartitionassociée à la loi P. Par ailleurs, le théorème de Kolmogorov-Smirnov, quenous admettrons, stipule que lorsque X = (X1, . . . , Xn) ∼ P⊗n

0 ,

√n Kn(X, P0)

L→ µKS,

où µKS est la loi de Kolmogorov-Smirnov, de fonction de répartition conti-nue définie par

R+ 3 t 7→ 1− 2 ∑`≥1

(−1)`+1e−2`2t2.

Dans le cadre du problème de test de H0 contre H1, le test de Kolmogorov-Smirnov est le test asymptotique de région de rejet

R(α) ={

x ∈ Rn :√

n Kn(x, P0) ≥ k1−α

},

avec k1−α le quantile d’ordre (1− α) de la loi µKS, i.e.

2 ∑`≥1

(−1)`+1e−2`2k2= α.

La forme de cette région de rejet est due au fait que H0 est rejetée lorsque lastatistique de test Kn(X, P0) prend des valeurs anormalement grandes. Cetest asymptotique est convergent et de niveau α, d’après les deux résultatsde convergence mentionnés ci-dessus.

73

Chapitre 8

Apprentissage et classificationsupervisée

8.1 Objectifs

On considère un couple (X, Y) de variables aléatoires à valeurs dans Rd

(pour X) et {0, 1} (pour Y). La variable Y est appelée label, classe ou étiquette.Le problème de la classification supervisée (binaire) consiste à prédire aumieux Y à partir de X, c’est-à-dire à construire une fonction borélienneg : Rd → {0, 1} (appelée règle de décision ou de classification) qui, à un xdonné (réalisation de X) associe son label supposé 0 ou 1. Pour prendre unexemple, on peut penser à X comme une variable aléatoire représentant lafréquence d’un certain nombres de mots-clés dans un email, et à Y commela variable associée exprimant le fait que l’email est sain (label 0) ou bienspam (label 1).

Remarques.

1. Dans ce cours, le label est supposé binaire pour simplifier. La théo-rie s’étend sans trop de difficultés au cas multi-labels, pour lequel Yprend ses valeurs dans un ensemble fini {1, . . . , M}.

2. Le terme “apprentissage statistique”, dont les contours sont larges, seconfond parfois avec la classification supervisée. Il peut aussi englo-ber la régression bornée, où Y prend ses valeurs dans un ensemblecompact, et la classification non supervisée, que nous aborderonsdans le Chapitre 11.

74

Chapitre 8 Apprentissage et classification supervisée

La loi du couple (X, Y) est entièrement caractérisée par le couple (µ, r), oùµ est la loi de X et r la fonction de régression de Y sur X. Plus précisément,pour tout A ∈ B(Rd), µ(A) = P(X ∈ A), et

r(x) = E(Y|X = x) = P(Y = 1|X = x),

la dernière égalité provenant du fait que Y prend ses valeurs dans {0, 1}.

Attention ! Dans ce modèle, Y n’est pas nécessairement lié à X de manièrefonctionnelle, i.e. rien ne dit qu’il existe une fonction ϕ telle que Y = ϕ(X).Pour s’en convaincre, il suffit de penser à l’exemple des emails, au seinduquel le mot “Viagra” peut être associé à un label spam ou non

Bien entendu, n’importe quelle fonction borélienne g : Rd → R fournit unerègle de décision, et il est donc nécessaire d’adjoindre un critère de qualitéà chaque décision. On remarque pour cela qu’une erreur de classificationse produit lorsque g(X) 6= Y et l’on définit naturellement la probabilitéd’erreur d’une règle g par

L(g) = P(g(X) 6= Y).

La quantité L(g), qui mesure la pertinence de la règle g, permet donc dehiérarchiser les fonctions de décision agissant sur le couple (X, Y). Il estalors légitime de se poser la question de l’existence éventuelle d’une règlemeilleure que les autres. Ce champion existe et s’appelle la règle de Bayes :

g?(x) ={

1 si P(Y = 1|X = x) > P(Y = 0|X = x)0 sinon.

(Les égalités sont rompues en faveur de 0 par convention.) De façon équi-valente,

g?(x) ={

1 si r(x) > 1/20 sinon.

Le lemme qui suit nous assure que g? mérite bien son statut de champion :

Lemme 2. Quelle que soit la règle de décision g : Rd → {0, 1}, on a

L(g?) ≤ L(g).

Démonstration. Soit g : Rd → {0, 1} une fonction borélienne arbitraire.Comme

P(g(X) 6= Y) = 1−P (g(X) = Y) ,

75


on a

P(g(X) 6= Y)−P(g?(X) 6= Y) = P (g?(X) = Y)−P (g(X) = Y)= E (P(g?(X) = Y|X)−P(g(X) = Y|X))

≥ 0,

puisque

P(g?(X) = Y|X) = P(g?(X) = 1, Y = 1|X) + P(g?(X) = 0, Y = 0|X)

= 1[g?(X)=1]P(Y = 1|X) + 1[g?(X)=0]P(Y = 0|X)

= max (P(Y = 0|X), P(Y = 1|X)) ,

par définition de g?. Le résultat est donc démontré.

L? est appelée probabilité d’erreur de Bayes (erreur de Bayes ou risque de Bayes).On note en particulier que

L? = infg:Rd→{0,1}

P(g(X) 6= Y),

où l’infimum est évalué sur toutes les fonctions de décision. Il est égalementinstructif de remarquer que L? = 0 si et seulement si Y = g?(X) P-p.s., i.e.si et seulement si Y est une fonction borélienne de X. Dans le jargon de laclassification supervisée, les probabilités P(Y = 0|X = x) et P(Y = 1|X =x) sont dites probabilités a posteriori.

Observons enfin que

L(g) = 1−P(g(X) = Y)= 1−E (P(g(X) = Y|X))

= 1−E[1[g(X)=1]r(X) + 1[g(X)=0] (1− r(X))

].

En conséquence,

L? = 1−E[1[r(X)>1/2]r(X) + 1[r(X)≤1/2] (1− r(X))

].

Ceci montre que

L? = E [min (r(X), 1− r(X))] =12− 1

2E|2r(X)− 1|,

76


et nous fournit donc des écritures alternatives pour L?.

Le problème : La règle de classification optimale g? dépend de la loi ducouple (X, Y). Si cette loi est connue (ce qui est rarement le cas), le cours estterminé. Si elle ne l’est pas, g? et L? sont inaccessibles et il faut alors faireappel à un échantillon i.i.d. (X1, Y1), . . . , (Xn, Yn), de même loi que (X, Y),pour espérer récupérer de l’information sur ces deux quantités. C’est là queles choses deviennent intéressantes.

8.2 L’apprentissage

On suppose donc à partir de maintenant que l’on a accès à un n-échantilloni.i.d. (également appelé dans ce contexte base de données ou base d’apprentis-sage) formé de n couples (X1, Y1), . . . , (Xn, Yn) de variables aléatoires in-dépendantes entre elles, de même loi que (X, Y) et indépendantes de cedernier couple. Pour abréger, on note Dn = (X1, Y1), . . . , (Xn, Yn). C’est àpartir de cet échantillon que l’on va s’attacher à construire une règle dedécision gn(x) := gn(x, Dn) à valeurs dans {0, 1} dont les performances serapprochent de celles de la règle de Bayes g?. C’est le mécanisme d’appren-tissage.

La qualité d’une règle gn est mesurée par la probabilité d’erreur (condi-tionnelle)

L(gn) = P(gn(X) 6= Y|Dn).

Il convient de remarquer que, tout comme gn, L(gn) est aléatoire par l’in-termédiaire de Dn. Le conditionnement par Dn dans la probabilité d’erreurpermet de distinguer l’aléatoire provenant de l’échantillon de celui issu ducouple générique (X, Y). On notera au passage que EL(gn) = P(gn(X) 6=Y). (Pourquoi ?)

A partir de là, il est raisonnable de s’interroger sur le comportement de laprobabilité d’erreur lorsque la taille de l’échantillon tend vers l’infini. Onest en particulier en droit d’attendre d’une “bonne règle” que sa probabilitéd’erreur se rapproche de L? lorsque n croît. Comme L(gn) est aléatoire(contrairement à L?), il convient de bien préciser le sens des convergences.C’est l’objet de la définition qui suit.

Définition 29. Une règle de classification gn est convergente si EL(gn) → L?.Elle est fortement convergente si Ln → L? P-p.s.

77


Comme L(gn) ≥ L?, on notera que la propriété EL(gn) → L? est équiva-lente à L(gn) → L? dans L1. On pourra aussi montrer, à titre d’exercise,que la convergence équivaut à la convergence en probabilité de L(gn) versL?. On en déduit en particulier que si gn est fortement convergente, elle estaussi convergente.

8.3 Minimisation du risque empirique

La minimisation du risque empirique fait partie des grands paradigmesde l’apprentissage statistique. Le principe général est le suivant. Donnons-nous un n-échantillon i.i.d. Dn = (X1, Y1), . . . , (Xn, Yn) de même loi que(et indépendant de) (X, Y), et une famille G de règles de décision candi-dates. On se pose alors le problème de choisir dans G , en utilisant Dn, unerègle particulière g?n telle que L(g?n) = P(g?n(X) 6= Y|Dn) soit proche deinfg∈G P(g(X) 6= Y). En d’autres termes, on cherche à utiliser au mieuxla base de données afin de sélectionner la meilleure technique de prévi-sion possible au sein d’une collection G de règles fixée a priori. Il peutpar exemple s’agir des règles linéaires (qui décident 0 ou 1 selon que l’ontombe d’un côté ou de l’autre d’un hyperplan), de règles polynomiales (quidécident 0 ou 1 en fonction du signe d’un polynôme), mais bien d’autresexemples sont possibles.

Afin d’atteindre cet objectif, une façon naturelle de procéder consiste àsélectionner dans G une règle g?n qui minimise l’erreur empirique

Ln(g) =1n

n

∑i=1

1[g(Xi) 6=Yi]

parmi tous les éléments de G , soit donc

g?n ∈ arg ming∈G

Ln(g).

En rappelant que L(g?n) = P(g?n(X) 6= Y|Dn), on espère donc naturellementque L(g?n) ≈ infg∈G L(g). Remarquons d’emblée que

L(g?n)− L? =

[L(g?n)− inf

g∈GL(g)

]+

[infg∈G

L(g)− L?

].

78


Cette égalité, simple mais fondamentale, montre que l’erreur commise parL(g?n) en tant qu’estimateur de L? se décompose en deux termes, respec-tivement appelés erreur d’estimation et erreur d’approximation. L’erreur d’es-timation est aléatoire et reflète l’écart, en termes de probabilités, entre larègle sélectionnée et le champion local dans G . L’erreur d’approximationest déterministe et mesure la proximité, toujours en termes de probabilités,entre la famille G et la règle optimale de Bayes.

Il est facile de voir que les deux termes d’erreur varient en sens inverseavec la taille de la classe G , qui doit donc être suffisamment grande pourque l’erreur d’approximation soit petite, mais aussi suffisamment petitepour que l’erreur d’estimation soit contrôlée ! Pour s’en convaincre, il suffitd’envisager la situation extrême où G est constituée de toutes les fonctionsmesurables de Rd dans {0, 1}. Dans ce cas, l’erreur d’approximation estnulle, mais l’erreur d’estimation peut être importante, comme le montre lechoix de la règle

g?n(x) ={

Yi si x = Xi, 1 ≤ i ≤ n0 sinon,

dont le risque empirique est nul ! Ce phénomène indésirable, qui traduitune accroche trop importante aux données, est appelé sur-apprentissage(“overfitting” en anglais) et nous donnerons dans la suite des conditionsprécises sur G permettant de l’éviter. A partir de maintenant, nous suppo-sons donc la classe G fixée une fois pour toutes et cherchons à contrôler leterme d’estimation.

Lemme 3. On a, d’une part,

(i) L(g?n)− infg∈G L(g) ≤ 2 supg∈G |Ln(g)− L(g)|et, d’autre part,

(ii) |Ln(g?n)− L(g?n)| ≤ supg∈G |Ln(g)− L(g)|.

Démonstration. On écrit

L(g?n)− infg∈G

L(g) ≤∣∣L(g?n)− Ln(g?n)

∣∣+ ∣∣Ln(g?n)− infg∈G

L(g)∣∣.

Clairement, ∣∣L(g?n)− Ln(g?n)∣∣ ≤ sup

g∈G

∣∣Ln(g)− L(g)∣∣,

79


et ∣∣Ln(g?n)− infg∈G

L(g)∣∣ = ∣∣ inf

g∈GLn(g)− inf

g∈GL(g)

∣∣ ≤ supg∈G

∣∣Ln(g)− L(g)∣∣.

Cela prouve la première assertion. La preuve de la seconde est immédiate.

Le Lemme 3 montre qu’en contrôlant la quantité supg∈G |Ln(g)− L(g)|, onfait coup double, puisque l’on maîtrise non seulement la sous-optimalitéde g?n dans G mais aussi l’erreur |Ln(g?n)− L(g?n)| commise lorsque Ln(g?n)est utilisée pour estimer L(g?n), la véritable probabilité d’erreur de la règlesélectionnée. Il est donc désormais légitime de faire porter nos efforts surl’analyse du terme supg∈G |Ln(g)− L(g)|. Nous commençons simplement,en examinant le cas où la classe de fonctions G a un cardinal fini.

8.4 Cas d’une classe de cardinal fini

L’inégalité de Hoeffding (Théorème 2) montre que si Z désigne une va-riable aléatoire de loi binomiale B(n, p), alors, pour tout ε > 0,

P

(∣∣∣∣Zn − p∣∣∣∣ ≥ ε

)≤ 2e−2nε2

.

En remarquant que pour une règle de décision fixée g, la quantité

nLn(g) =n

∑i=1

1[g(Xi) 6=Yi]

suit une loi B(n, L(g)), on en conclut que

P(∣∣Ln(g)− L(g)

∣∣) ≤ 2e−2nε2,

ce qui conduit au premier résultat fondamental suivant :

Théorème 12. Supposons que la classe G soit de cardinal fini majoré par N.Alors, pour tout ε > 0,

P(

supg∈G

∣∣Ln(g)− L(g)∣∣ ≥ ε

)≤ 2Ne−2nε2

. (8.1)

80


Il faut noter que cette inégalité est déjà remarquable car la majoration de laprobabilité est universelle, au sens où elle ne dépend pas de la loi du couple(X, Y). On en déduit en particulier, en utilisant le lemme de Borel-Cantelli,que

supg∈G

∣∣Ln(g)− L(g)∣∣→ 0 P-p.s.

et donc, d’après le Lemme 3, que

L(g?n)− infg∈G

L(g)→ 0 P-p.s.

Ce résultat signifie que pourvu que la classe G soit de cardinal fini, l’er-reur d’estimation tend p.s. vers 0 lorsque n tend vers l’infini ; en d’autrestermes, l’apprentissage est asymptotiquement optimal. Tout ceci s’étendsans difficulté au contrôle de l’espérance E(supg∈G |Ln(g)− L(g)|), via lepetit lemme technique suivant.

Lemme 4. Soit Z une variable aléatoire à valeurs dans R+. Supposons qu’il existeune constante C > 0 telle que, pour tout ε > 0,

P(Z ≥ ε) ≤ Ce−2nε2.

Alors

EZ ≤√

ln(Ce)2n

.

Démonstration. En partant de l’identité

EZ2 =∫ +∞

0P(Z2 > ε)dε,

on a, pour tout u ≥ 0,

EZ2 =∫ u

0P(Z2 > ε)dε +

∫ +∞

uP(Z2 > ε)dε

≤ u + C∫ +∞

ue−2nεdε

= u +C2n

e−2nu.

Avec le choix u? = ln C2n (qui minimise la borne de droite), on en déduit que

EZ2 ≤ ln(Ce)2n , d’où le résultat par l’inégalité de Cauchy-Schwarz.

81


Le lemme précédent, couplé à l’inégalité (8.1), montre que

E(

supg∈G

∣∣Ln(g)− L(g)∣∣ ) ≤ √ ln(2eN)

2n.

Le Lemme 3 nous permet alors de conclure que

EL(g?n)− infg∈G

L(g) ≤ 2

√ln(2eN)

2n,

ce qui montre que, pour une classe G de cardinal fini, l’espérance de l’er-reur d’estimation reste sous contrôle (avec une borne plus ou moins grandeselon sa taille N) et tend vers 0 à la vitesse 1/

√n lorsque n tend vers l’infini.

Néanmoins, lorsque G n’est pas de cardinal fini (comme c’est le cas dansla plupart des problèmes intéressants), l’approche que nous venons de pré-senter ne fonctionne plus, et il faut trouver de nouveaux outils pour ap-préhender la “taille” de G . C’est l’objet du chapitre suivant, qui présente lathéorie de Vapnik-Chervonenkis.

82

Chapitre 9

Théorie de Vapnik-Chervonenkis

9.1 Passage du supg∈G au supA∈A

Etant donné un n-échantillon i.i.d. Dn = (X1, Y1), . . . , (Xn, Yn) de mêmeloi que (et indépendant de) (X, Y), et une famille G de règles de décisioncandidates, le chapitre précédent a montré le rôle essentiel joué par le termesupg∈G |Ln(g) − L(g)|, qu’il faut donc apprendre à contrôler avec la plusgrande généralité possible.

Désignons par ν la loi du couple (X, Y) et par νn la mesure empiriqueassociée à Dn, i.e., pour tout A ∈ B(Rd × {0, 1}),

νn(A) =1n

n

∑i=1

1[(Xi,Yi)∈A].

A une règle de décision quelconque g ∈ G , nous pouvons associer le boré-lien

Ag ={(x, y) ∈ Rd × {0, 1} : g(x) 6= y

}.

En utilisant cette notation, il est alors facile de voir que, d’une part,

L(g) = P(g(X) 6= Y) = ν(Ag)

et, d’autre part,

Ln(g) =1n

n

∑i=1

1[g(Xi) 6=Yi]= νn(Ag).

83

Chapitre 9 Théorie de Vapnik-Chervonenkis

On constate ainsi que{supg∈G

∣∣Ln(g)− L(g)∣∣ } =

{supA∈A

|νn(A)− ν(A)|}

,

où, par définition, A = {Ag : g ∈ G }. Ce jeu d’écriture nous montre doncque pour analyser le comportement probabiliste du terme supg∈G |Ln(g)−L(g)|, il faut avant tout comprendre comment se comporte la déviationmaximale de la mesure empirique par rapport à la vraie mesure sur uneclasse d’ensembles mesurables A donnée. On peut d’ores et déjà observerque, pour un ensemble A fixé,

|νn(A)− ν(A)| → 0 P-p.s.

d’après la loi des grands nombres. D’autre part, si le cardinal de A est finiet majoré par N, un raisonnement similaire à celui du Théorème 12 nousapprend que, pour tout ε > 0,

P(

supA∈A

|νn(A)− ν(A)| ≥ ε)≤ 2Ne−2nε2

, (9.1)

d’où l’on déduit (lemme de Borel-Cantelli) que, pour toute loi ν,

supA∈A

|νn(A)− ν(A)| → 0 P-p.s.

En revanche, si la classe A est trop massive, des catastrophes peuvent seproduire. On s’en convaincra facilement en remarquant que si A désignel’ensemble de tous les boréliens de Rd × {0, 1}, alors on peut trouver deslois ν (un exemple ?) telles que

supA∈A

|νn(A)− ν(A)| = 1 P-p.s.

La conclusion de tout ceci c’est qu’il faut arriver, d’une manière ou d’uneautre, à contrôler la “taille” de la classe d’ensembles A . Pour atteindre cetobjectif, il convient au préalable d’introduire quelques outils combinatoiresnouveaux.

9.2 Théorème de Vapnik-Chervonenkis

Soit A une famille de sous-ensembles de Rp, de cardinal (pas nécessaire-ment fini) strictement supérieur à 1 (cette hypothèse sera implicite dans

84


la suite). Etant donné n points z1, . . . , zn de Rp, on définit la quantitéNA (z1, . . . , zn) par

NA (z1, . . . , zn) =∣∣ {{z1, . . . , zn} ∩ A : A ∈ A }

∣∣.En d’autres termes, NA (z1, . . . , zn) représente le nombre de sous-ensem-bles de {z1, . . . , zn} que l’on peut obtenir en intersectant ces n points parles ensembles de A . Bien entendu, on a toujours NA (z1, . . . , zn) ≤ 2n, etlorsque NA (z1, . . . , zn) = 2n, on dit que la classe A pulvérise l’ensemble{z1, . . . , zn}. Afin de ne pas être gêné par le choix arbitraire de z1, . . . , zn,on pose

SA (n) = max(z1,...,zn)∈Rpn

NA (z1, . . . , zn)

et on appelle cet indice le coefficient de pulvérisation de n points par la classeA .

Clairement, SA (n) ≤ 2n. D’autre part, SA (1) = 2 (pourquoi ?), et si l’on aSA (k) < 2k pour un certain entier k > 1 alors SA (n) < 2n pour tout n ≥ k(pourquoi ?). Il est donc naturel de s’interroger sur l’existence d’un plusgrand entier n tel que SA (n) = 2n. C’est l’objet de la définition suivante.

Définition 30. Soit A une famille de sous-ensembles de Rp. On appelle dimen-sion de Vapnik-Chervonenkis de A , notée VA , le plus grand entier n0 ≥ 1 tel queSA (n0) = 2n0 . Si SA (n) = 2n pour tout n ≥ 1, on pose VA = +∞.

La dimension de Vapnik-Chervonenkis mesure, en un certain sens, la “tai-lle” (la “dimension”) de la famille A et généralise ainsi la notion de car-dinal. Il s’agit d’un concept combinatoire important qui, comme nous leverrons dans la suite, joue un rôle clé dans la théorie de l’apprentissagestatistique. Examinons auparavant quelques exemples (les preuves sont dedifficultés variées et laissées au lecteur).

Exemples.1. Supposons |A | < ∞. Bien entendu, SA (n) ≤ |A |. D’autre part, par

définition de VA , SA (VA ) = 2VA , d’où l’on déduit que

VA ≤ ln2 |A |.

2. En dimension p = 1. Si A = {] −∞, a] : a ∈ R}, alors VA = 1. SiA = {[a, b] : (a, b) ∈ R2}, alors VA = 2. On remarquera que dansle premier cas SA (n) = n + 1, tandis que dans le second SA (n) =n(n+1)

2 + 1.

85


3. En dimension p quelconque. Si

A ={]−∞, a1]× · · · ×]−∞, ap] : (a1, . . . , ap) ∈ Rd

},

alors VA = d. Si A = {rectangles de Rp}, alors VA = 2d. En re-vanche, pour A = {convexes de Rp}, on a VA = +∞.

4. (Important.) Soit G un espace vectoriel de fonctions de Rp → R, dedimension finie dim G . Alors, si

A ={{x ∈ Rp : g(x) ≥ 0} : g ∈ G

},

on a VA ≤ dim G . En particulier, si A désigne la famille des 1/2-espaces linéaires, i.e. les sous-ensembles de Rp de la forme {x ∈ Rp :a>x + b ≥ 0 : a ∈ Rp, b ∈ R}, il vient VA ≤ p + 1.

Nous sommes désormais équipés pour énoncer le théorème fondamentalsuivant, appelé théorème de Vapnik-Chervonenkis.

Théorème 13 (Vapnik-Chervonenkis). Soient Z1, . . . , Zn des variables aléa-toires indépendantes, de même loi ν sur Rp, et soit νn la mesure empirique corres-pondante. Alors, pour toute famille borélienne A ⊂ Rp et pour tout ε > 0, ona

P

(supA∈A

|νn(A)− ν(A)| > ε

)≤ 8SA (n)e−nε2/32.

Avant de prouver ce théorème, il convient de souligner quelques pointsessentiels.

1. La borne est universelle, dans le sens où elle ne dépend pas de la loiparticulière ν.

2. Ce résultat généralise l’inégalité (9.1) qui n’était valable que pour uneclasse A de cardinal fini. Grosso modo, le cardinal de A est remplacépar le coefficient de pulvérisation.

3. D’après le lemme de Borel-Cantelli, il s’ensuit que

supA∈A

|νn(A)− ν(A)| → 0 P-p.s.

dès que la série de terme général SA (n)e−nε2/32 est sommable. C’estpar exemple le cas si |A | < ∞ ou si SA (n) est un polynôme en n. Enrevanche, il est impossible de conclure si SA (n) = 2n pour tout n (ou,c’est équivalent, si VA = +∞).

86


4. La preuve du Théorème 13 n’est pas compliquée et repose sur quel-ques arguments clés que l’on rencontre fréquemment en théorie del’apprentissage. En un mot, le principe consiste à faire sortir le supre-mum de la parenthèse pour le placer devant la probabilité. Ce grandsaut est effectué en jouant sur les propriétés combinatoires de la classeA telles que décrites par SA (n).

Démonstration du Théorème 13. Dans toute la preuve, on suppose ε > 0 fixéet on choisit n assez grand de sorte que nε2 ≥ 2. Dans le cas contraire, il estfacile de voir que le résultat annoncé est correct car la borne du théorèmeest alors plus grande que 1. La preuve s’organise en 4 étapes.

Etape 1 : Symmétrisation. En sus du n-échantillon i.i.d. original Z1, . . . , Zn,on considère un second échantillon i.i.d. Z′1, . . . , Z′n de la loi ν, indépendantdu premier. On note νn la mesure empirique relative à Z1, . . . , Zn et ν′n cellerelative à Z′1, . . . , Z′n. La première étape consiste à montrer que

P(

supA∈A

|νn(A)− ν(A)| > ε)≤ 2 P

(supA∈A

∣∣νn(A)− ν′n(A)∣∣ > ε/2

).

Choisissons pour cela un ensemble aléatoire A? ∈ A (dépendant de l’é-chantillon initial Z1, . . . , Zn) tel que |νn(A?)− ν(A?)| > ε (si un tel ensem-ble n’existe pas, on prend A? = Rp). On a alors

P(

supA∈A

∣∣νn(A)− ν′n(A)∣∣ > ε/2

)= E

(P(

supA∈A

∣∣νn(A)− ν′n(A)∣∣ > ε/2

∣∣∣ Z1, . . . , Zn

))≥ E

(P( ∣∣νn(A?)− ν′n(A?)

∣∣ > ε/2∣∣∣ Z1, . . . , Zn

))= P

( ∣∣νn(A?)− ν′n(A?)∣∣ > ε/2

).

On en déduit, en utilisant l’inégalité triangulaire, que

P(

supA∈A

∣∣νn(A)− ν′n(A)∣∣ > ε/2

)≥ P

(|νn(A?)− ν(A?)| > ε,

∣∣ν′n(A?)− ν(A?)∣∣ < ε/2

)= E

(1[|νn(A?)−ν(A?)|>ε]P

( ∣∣ν′n(A?)− ν(A?)∣∣ < ε/2

∣∣∣ Z1, . . . , Zn

)).

87


L’inégalité de Bienaymé-Tchebytchev montre que

P( ∣∣ν′n(A?)− ν(A?)

∣∣ < ε/2∣∣∣ Z1, . . . , Zn

)≥ 1−

E((ν′n(A?)− ν(A?))2

∣∣∣ Z1, . . . , Zn

)ε2/4

.

En observant que, conditionnellement à Z1, . . . , Zn, nν′n(A?) suit une loiB(n, ν(A?)), on en déduit en particulier que

P( ∣∣ν′n(A?)− ν(A?)

∣∣ < ε/2∣∣∣ Z1, . . . , Zn

)≥ 1−

V(ν′n(A?)

∣∣Z1, . . . , Zn)

ε2/4

= 1− ν(A?)(1− ν(A?))

nε2/4

≥ 1− 1nε2

(car supu∈[0,1] u(1− u) = 1/4).

Ainsi,

P(

supA∈A

∣∣νn(A)− ν′n(A)∣∣ > ε/2

)≥ E

(1[|νn(A?)−ν(A?)|>ε]

(1− 1

nε2

))≥ 1

2P(|νn(A?)− ν(A?)| > ε

)(car nε2 ≥ 2)

=12

P(

supA∈A

|νn(A)− ν(A)| > ε)

.

On en conclut bien que

P(

supA∈A

|νn(A)− ν(A)| > ε)≤ 2 P

(supA∈A

∣∣νn(A)− ν′n(A)∣∣ > ε/2

).

Etape 2 : Signes aléatoires. On se donne maintenant n variables aléa-toires σ1, . . . , σn, indépendantes et chacune de loi de Rademacher, vérifiantP(σi = −1) = P(σi = +1) = 1/2. On suppose en outre que les variablesσ1, . . . , σn sont indépendantes de Z1, . . . , Zn, Z′1, . . . , Z′n. Il est alors facile devoir (exercice) que

n supA∈A

∣∣νn(A)− ν′n(A)∣∣ = sup

A∈A

∣∣∣∣ n

∑i=1

(1A(Zi)− 1A(Z′i)

) ∣∣∣∣88


a même loi que

supA∈A

∣∣∣ n

∑i=1

σi(1A(Zi)− 1A(Z′i)

) ∣∣∣.Dès lors, en utilisant le résultat de la première étape, nous pouvons écrireque

P(

supA∈A

|νn(A)− ν(A)| > ε)

≤ 2 P(

supA∈A

1n

∣∣∣ n

∑i=1

σi(1A(Zi)− 1A(Z′i)

) ∣∣∣ > ε/2)

,

et donc

P(

supA∈A

|νn(A)− ν(A)| > ε)≤ 4 P

(supA∈A

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

).

Etape 3 : Le saut du sup. En poursuivant le calcul précédent, on a

P(

supA∈A

|νn(A)− ν(A)| > ε)

≤ 4E

(P(

supA∈A

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)).

Or,

P(

supA∈A

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)≤ P

(∃A ∈ A :

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣Z1, . . . , Zn

).

Une fois fixés les points z1, . . . , zn, le vecteur (1A(z1), . . . ,1A(zn)) prendNA (z1, . . . , zn) valeurs distinctes lorsque A varie dans A , soit donc unmaximum de SA (n) valeurs. Du coup,

P(

supA∈A

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)≤ P

(∃A ∈ A0 :

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

),

89


où A0 est un ensemble fini (fonction de Z1, . . . , Zn) de cardinal au plusSA (n). Il s’ensuit que

P(

supA∈A

1n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)≤ ∑

A∈A0

P( 1

n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)≤ SA (n) sup

A∈A

P( 1

n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

).

On notera ici le saut du sup de l’intérieur vers l’extérieur de la probabilité,accompli grâce à l’introduction des signes aléatoires et du coefficient depulvérisation. Ainsi,

P(

supA∈A

|νn(A)− ν(A)| > ε)

≤ 4SA (n)E(

supA∈A

P( 1

n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)). (9.2)

Etape 4 : Inégalité de Hoeffding et conclusion. Conditionnellement àZ1, . . . , Zn, la variable aléatoire ∑n

i=1 σi1A(Zi) est la somme de n variablesaléatoires indépendantes, centrées et comprises entre−1 et 1. Ainsi, d’aprèsl’inégalité de Hoeffding,

P( 1

n

∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > ε/4

∣∣∣ Z1, . . . , Zn

)= P

(∣∣∣ n

∑i=1

σi1A(Zi)∣∣∣ > nε/4

∣∣∣ Z1, . . . , Zn

)≤ 2e−nε2/32.

On conclut alors en utilisant (9.2) que

P(

supA∈A

|νn(A)− ν(A)| > ε)≤ 8SA (n)e−nε2/32,

ce qui est bien le résultat annoncé.

90


Application importante. Plaçons-nous sur la droite réelle et considéronsun n-échantillon Z1, . . . , Zn de variables aléatoires i.i.d., de loi commune ν.En prenant A = {] −∞, z] : z ∈ R}, il est facile de voir que, pour toutA =]−∞, z] ∈ A , on a ν(A) = F(z) et νn(A) = Fn(z), où F (respective-ment, Fn) est la fonction de répartition associée à la loi ν (respectivement, lafonction de répartition empirique associée à Z1, . . . , Zn). D’autre part, uneanalyse rapide indique que SA (n) = n + 1. Ainsi, en utilisant le théorèmede Vapnik-Chervonenkis, on montre que

P(

supA∈A

|νn(A)− ν(A)| > ε)= P

(supz∈R

|Fn(z)− F(z)| > ε)

≤ 8(n + 1)e−nε2/32.

Le lemme de Borel-Cantelli implique alors que

supz∈R

|Fn(z)− F(z)| → 0 P-p.s.,

c’est-à-dire que la fonction de répartition empirique converge presque sû-rement vers la fonction de répartition, au sens de la convergence uniformedes fonctions. Ce résultat remarquable porte le nom de théorème de Glivenko-Cantelli.

Avant de tirer les conséquences du Théorème 13 pour la théorie de l’ap-prentissage, il convient de préciser quelques propriétés élémentaires de ladimension de Vapnik-Chervonenkis.

9.3 Aspects combinatoires

Nous admettrons le résultat combinatoire suivant, connu sous le nom delemme de Sauer :

Théorème 14 (Lemme de Sauer). Soit A une famille d’ensembles admettantune dimension de Vapnik-Chervonenkis finie VA . Alors, pour tout n ≥ 1,

SA (n) ≤VA

∑i=1

(ni

).

Dans la suite, c’est surtout le corollaire suivant qui nous sera utile :

91


Corollaire 1. Soit A une famille d’ensembles admettant une dimension de Vap-nik-Chervonenkis finie VA . Alors, pour tout n ≥ 1,

SA (n) ≤ (n + 1)VA .

Démonstration. On a

(n + 1)VA =VA

∑i=0

(VA

i

)ni =

VA

∑i=0

niVA !i!(VA − i)!

≥VA

∑i=0

ni

i!

≥VA

∑i=0

(ni

)≥ SA (n).

On déduit en particulier du corollaire précédent qu’un coefficient de pul-vérisation tombe forcément dans l’une des deux catégories suivantes :

. Ou bien SA (n) = 2n pour tout n ≥ 1 (dans ce cas, VA = +∞).

. Ou bien SA (n) ≤ (n + 1)VA (dans ce cas, VA < ∞).

On ne peut donc jamais avoir des situations intermédiaires, comme parexemple SA (n) ∼ 2

√n.

Enfin, en combinant le théorème de Vapnik-Chervonenkis, le Lemme tech-nique 4 et le Corollaire 1, on conclut que pour toute famille d’ensemblesmesurables A ⊂ Rp admettant une dimension de Vapnik-Chervonenkisfinie VA ,

E(

supA∈A

|νn(A)− ν(A)|)≤ 8

√ln (8eSA (n))

2n

≤ 8

√VA ln(n + 1) + 4

2n

= O

(√VA log n

n

).

Il est à noter qu’il est possible de se débarasser du terme logarithmique enutilisant des techniques dites de chaînage, dont la présentation dépasseraitle cadre de ce cours.

92


9.4 Application à la minimisation du risqueempirique

Nous pouvons à présent peaufiner les bornes sur l’erreur d’estimation dansle problème de classification supervisée. Rappelons, pour mémoire, quel’on considère un n-échantillon i.i.d. Dn = (X1, Y1), . . . , (Xn, Yn) de mêmeloi que (et indépendant de) (X, Y), et une famille G de règles de décisioncandidates. En désignant par g?n un minimiseur du risque empirique dansG , nous savons que, d’une part,

L(g?n)− infg∈G

L(g) ≤ 2 supg∈G

∣∣Ln(g)− L(g)∣∣

et, d’autre part,{supg∈G

∣∣Ln(g)− L(g)∣∣ } =

{supA∈A

|νn(A)− ν(A)|}

,

où, par définition, A = {Ag : g ∈ G }, avec

Ag ={(x, y) ∈ Rd × {0, 1} : g(x) 6= y

}.

Il est alors clair, de par le théorème de Vapnik-Chervonenkis, que le coeffi-cient de pulvérisation SA (n) va jouer un rôle fondamental dans le contrôledu terme supg∈G |Ln(g) − L(g)|. Néanmoins, la classe A , composée desous-ensembles de Rd×{0, 1}, revêt une structure un peu complexe qui nese prête pas bien à l’analyse combinatoire. Fort heureusement, les chosesse simplifient grâce à la proposition suivante, dont la preuve est laissée àtitre d’exercice.

Proposition 5. Soit A = {Ag : g ∈ G } et ¯A = {{x ∈ Rd : g(x) = 1} : g ∈G }. Alors, pour tout n ≥1, S ¯A (n) = SA (n). En particulier, V ¯A = VA .

Nous sommes désormais en mesure d’énoncer le principal résultat de cechapitre, dont la preuve découle du Lemme 3, du théorème de Vapnik-Chervonenkis (et du Lemme technique 4 pour la seconde assertion).

Théorème 15. On a, pour tout n ≥ 1,

P(∣∣L(g?n)− inf

g∈GL(g)

∣∣ > ε)≤ 8S ¯A (n)e−nε2/128.

93


En outre,

EL(g?n)− infg∈G

L(g) ≤ 16

√ln (8eS ¯A (n))

2n.

D’après le lemme de Borel-Cantelli, il suit de ce résultat que

L(g?n)− infg∈G

L(g)→ 0 P-p.s.

dès que la série de terme général S ¯A (n)e−nε2/128 est sommable. Or, d’aprèsle Corollaire 1, c’est précisément le cas dès que V ¯A (ou VA ) est finie puis-qu’alors S ¯A (n) a une croissance au plus polynomiale en n. On retiendradonc de tout ceci que la condition V ¯A < ∞ est suffisante pour assurer laconvergence presque sûre du terme d’estimation vers 0 et que, dans ce cas,

EL(g?n)− infg∈G

L(g) = O

(√V ¯A ln n

n

).

Exemples.

1. Classification linéaire. En notant x = (x(1), . . . , x(d)), on considèredes règles très simples, de la forme

g(x) =

{1 si ∑d

j=1 ajx(j) + a0 > 00 sinon,

où (a0, a1, . . . , ad) ∈ Rd+1 est un paramètre vectoriel. Dans ce cas,

¯A ⊂{{x ∈ Rd : a>x + a0 ≥ 0} : a ∈ Rd, a0 ∈ R

}et, d’après les propriétés de la dimension de Vapnik-Chervonenkisvues plus haut, on a V ¯A ≤ d + 1. Ainsi,

P(∣∣L(g?n)− inf

g∈GL(g)

∣∣ > ε)≤ 8(n + 1)d+1e−nε2/128

etL(g?n)− inf

g∈GL(g)→ 0 P-p.s.

94


2. Classification par des boules fermées. La classe G est composée detoutes les indicatrices des boules fermées de Rd. Ainsi,

¯A =

{{x ∈ Rd :

d

∑j=1|x(j) − aj|2 ≤ a0

}: (a0, a1, . . . , ad) ∈ Rd+1

}.

En remarquant que

a0 −d

∑j=1|x(j) − aj|2 = a0 −

d

∑j=1

(x(j))2

+ 2d

∑j=1

x(j)aj −d

∑j=1

a2j ,

on voit que ¯A est inclus dans une famille d’ensembles de la forme= {{x ∈ Rd : f (x) ≥ 0} : f ∈ F}, où F est un espace vectoriel dedimension d + 2. On conclut comme précédemment que

L(g?n)− infg∈G

L(g)→ 0 P-p.s.

3. Classification par des convexes. On prend pour ¯A l’ensemble detous les convexes de Rd, famille pour laquelle nous avons déjà vu queV ¯A = +∞. Cette classe d’ensembles est trop massive pour que l’er-reur d’estimation puisse être raisonnablement contrôlée par la théoriede Vapnik-Chervonenkis.

4. Classification linéaire généralisée. On se place dans Rd et on sedonne Ψ1, . . . , Ψd? un nombre fixe de fonctions mesurables de Rd →R. Les règles de classification considérées sont alors de la forme

g(x) =

{1 si ∑d?

j=1 ajΨj(x) + a0 > 00 sinon,

où (a0, a1, . . . , ad?) ∈ Rd? est un paramètre vectoriel. Lorsque Ψj(x) =x(j), on retrouve la famille des règles linéaires. Néanmoins, bien d’au-tres choix sont possibles. En prenant par exemple pour les Ψj lesapplications coordonnées et produits de ces coordonnées, on voit que

¯A est incluse dans une famille d’ensembles du type{a0 +

d

∑j=1

ajx(j) +d

∑j=1

bj(x(j))2

+ ∑1≤j1<j2≤d

cj1cj2 x(j1)x(j2) ≥ 0}

.

Ainsi, en posant d? = 1 + 2d + d(d+1)2 , V ¯A ≤ d?, et donc

L(g?n)− infg∈G

L(g)→ 0 P-p.s.

95

Chapitre 10

Théorème de Stone et plusproches voisins

10.1 Classification et régression

Les chapitres précédents ont mis en lumière le rôle essentiel joué par leprincipe de minimisation du risque empirique et le théorème de Vapnik-Chervonenkis dans le contrôle de l’erreur d’estimation. Il s’avère cependantque les familles de règles de décision admettant une dimension de Vapnik-Chervonenkis finie sont presque toujours trop petites et ne permettent pasd’approcher correctement le risque de Bayes. On peut par exemple montrerque pour n’importe quelle famille de règles G dont la classe de boréliensassociée ¯A admet une dimension de Vapnik-Chervonenkis finie, et pourtout ε ∈ ]0, 1/2[, il existe un couple de variables aléatoires (X, Y) tel que

infg∈G

L(g)− L? > 1/2− ε.

Il existe cependant d’autres façons de procéder. Ainsi, en partant de l’iden-tité

g?(x) ={

1 si r(x) > 1/20 sinon,

(10.1)

une stratégie concurrente de la minimisation du risque empirique consisteà utiliser l’échantillon Dn = (X1, Y1), . . . , (Xn, Yn) pour estimer la fonctionde régression r(x) = E(Y|X = x), et remplacer r par son estimateur rn

96

Chapitre 10 Théorème de Stone et plus proches voisins

dans (10.1). La règle de classification résultante, dite règle plug-in, s’écritdonc naturellement

gn(x) ={

1 si rn(x) > 1/20 sinon.

Le théorème qui suit précise le lien entre gn et rn, en termes d’erreur. Onrappelle que µ désigne la loi de la variable aléatoire X.

Théorème 16. Soit rn un estimateur de la fonction de régression et gn la règle dedécision plug-in associée. Alors

0 ≤ L(gn)− L? ≤ 2∫

Rd|rn(x)− r(x)| µ(dx).

En particulier, pour tout p ≥ 1,

0 ≤ L(gn)− L? ≤ 2(∫

Rd|rn(x)− r(x)|p µ(dx)

)1/p,

et0 ≤ EL(gn)− L? ≤ 2 E1/p |rn(X)− r(X)|p .

Démonstration. En procédant comme dans la preuve du Lemme 2, nouspouvons écrire

P(gn(X) 6= Y|X,Dn)

= 1−P(gn(X) = Y|X,Dn)

= 1−(P(gn(X) = 1, Y = 1|X,Dn) + P(gn(X) = 0, Y = 0|X,Dn)

)= 1−

(1[gn(X)=1]P(Y = 1|X,Dn) + 1[gn(X)=0]P(Y = 0|X,Dn)

)= 1−

(1[gn(X)=1]r(X) + 1[gn(X)=0] (1− r(X))

),

où, dans la dernière inégalité, nous avons utilisé l’indépendance entre lecouple (X, Y) et Dn. De façon similaire,

P(g?(X) 6= Y|X) = 1−(1[g?(X)=1]r(X) + 1[g?(X)=0] (1− r(X))

).

Ainsi,

P(gn(X) 6= Y|X,Dn)−P(g?(X) 6= Y|X)

= r(X)(1[g?(X)=1] − 1[gn(X)=1]

)+ (1− r(X))

(1[g?(X)=0] − 1[gn(X)=0]

)= (2r(X)− 1)

(1[g?(X)=1] − 1[gn(X)=1]

)= |2r(X)− 1|1[gn(X) 6=g?(X)].

97


Finalement,

P(gn(X) 6= Y|Dn)− L? = 2∫

Rd|r(x)− 1/2|1[gn(x) 6=g?(x)]µ(dx)

≤ 2∫

Rd|rn(x)− r(x)| µ(dx),

puisque gn(x) 6= g?(x) implique |rn(x)− r(x)| ≥ |r(x)− 1/2|. Les autresassertions découlent de l’inégalité de Hölder et de celle de Jensen.

On retiendra du Théorème 16 que si l’on dispose d’un estimateur rn de lafonction de régression qui soit tel que∫

Rd|rn(x)− r(x)|2 µ(dx)→ 0 (10.2)

dans L1 (ou presque sûrement), alors la règle de classification associée gnest automatiquement convergente (ou fortement convergente). Il nous restedonc à savoir comment construire des estimateurs de la fonction de ré-gression qui possèdent la propriété de convergence (10.2). Le théorème deStone, que nous présentons dans la prochaine section, répond précisémentà cette question.

10.2 Le théorème de Stone

Une façon canonique de construire des estimateurs de la fonction de ré-gression r(x) = E(Y|X = x) à partir du n-échantillon Dn consiste à écrire

rn(x) =n

∑i=1

Wni(x)Yi, x ∈ Rd, (10.3)

où chaque Wni(x) est une fonction borélienne réelle de x et X1, . . . , Xn (pasY1, . . . , Yn). Il est intuitivement clair que les couples (Xi, Yi) pour lesquelsXi est “proche” de x (en un sens qui reste à préciser) devraient apporterdavantage d’information sur r(x) que leurs homologues plus éloignés. Enconséquence, les poids devront en règle générale être plus grands autourde x, de telle sorte que rn(x) ainsi défini se présente comme une moyennepondérée des Yi correspondants aux Xi situés dans un voisinage de x. Voilàpourquoi un estimateur rn de la forme (10.3) est appelé estimateur de type

98


moyenne locale. Bien souvent (mais pas toujours), les Wni(x) sont positifs etnormalisés à 1, de telle sorte que (Wn1(x), . . . , Wnn(x)) est en fait un vecteurde probabilités.

Un exemple typique d’estimateur de type moyenne locale est l’estimateur ànoyau, qui est obtenu en prenant

Wni(x) =K(

x−Xih

)∑n

j=1 K(

x−Xjh

) ,

où K une fonction positive mesurable sur Rd (appelée noyau), et h est unparamètre strictement positif (appelé fenêtre), éventuellement fonction den. En d’autres termes, pour x ∈ Rd,

rn(x) =∑n

i=1 K(

x−Xih

)Yi

∑nj=1 K

(x−Xj

h

) .

(Si le dénominateur est nul, on pose rn(x) = 1n ∑n

i=1 Yi.) En particulier, pourle choix de noyau dit naïf K(z) = 1[‖z‖≤1], on obtient

rn(x) =∑n

i=1 1[‖x−Xi‖≤h]Yi

∑nj=1 1[‖x−Xj‖≤h]

,

ce qui montre que r(x) est estimé par la moyenne des Yi tels que la dis-tance euclidienne entre x et Xi ne dépasse pas h. Pour un noyau plus gé-néral K, le poids de Yi dépend de la distance entre x et Xi par l’intermé-diaire de la forme du noyau. Les noyaux les plus classiques sont le noyaud’Epanechnikov K(z) = (1−‖z‖2)1[‖z‖≤1] et le noyau gaussien K(z) = e−‖z‖

2.

Un second exemple important d’estimateur de type moyenne locale nousest fourni par l’estimateur des plus proches voisins :

rn(x) =n

∑i=1

vniY(i)(x), x ∈ Rd,

pour lequel (vn1, . . . , vnn) est un vecteur de poids (déterministes) positifsnormalisés à 1, et la suite (X(1)(x), Y(1)(x)), . . . , (X(n)(x), Y(n)(x)) est la per-mutation de (X1, Y1), . . . , (Xn, Yn) correspondante aux distances croissantes

99


des ‖Xi − x‖ (en cas d’égalité ‖Xi − x‖ = ‖Xj − x‖ avec i < j, Xi sera arbi-trairement déclaré plus proche de x que Xj). En d’autres termes,

‖X(1)(x)− x‖ ≤ ‖X(2)(x)− x‖ ≤ · · · ≤ ‖X(n)(x)− x‖.

Pour s’assurer que cet estimateur est bien de la forme (10.3), il suffit deposer

Wni(x) = vnΣi ,

où (Σ1, . . . , Σn) est la permutation de (1, . . . , n) telle que Xi est le Σi-èmeplus proche voisin de x. Parmi tous les choix possibles (vn1, . . . , vnn), uncas particulier important est obtenu en posant vni = 1/k pour 1 ≤ i ≤ k etvni = 0 autrement, avec {k} = {kn} une suite d’entiers strictement positifsne dépassant pas n. L’estimateur résultant s’appelle estimateur des k-plusproches voisins et s’écrit donc

rn(x) =1k

k

∑i=1

Y(i)(x), x ∈ Rd.

Le principe est naturel : pour estimer la fonction de régression autour de x,on regarde les k observations Xi les plus proches de x et on fait la moyennedes Yi correspondants.

Conformément à ce que nous avons dit dans la section précédente, on as-socie naturellement à un estimateur de type moyenne locale la règle declassification plug-in

gn(x) ={

1 si ∑ni=1 Wni(x)Yi > 1/2

0 sinon

ou, de façon équivalente, si ∑ni=1 Wni(x) = 1,

gn(x) ={

1 si ∑ni=1 Wni(x)1[Yi=1] > ∑n

i=1 Wni(x)1[Yi=0]0 sinon.

Le théorème ci-après, connu sous le nom de théorème de Stone, donne desconditions suffisantes sur les poids Wni(x) garantissant que la règle declassification plug-in gn soit convergente. Pour simplifier, nous suppose-rons désormais que les poids Wni(x) sont positifs et normalisés à 1 (i.e.,∑n

i=1 Wni(x) = 1), ce qui fait de (Wn1(x), . . . , Wnn(x)) un vecteur de proba-bilités.

100


Théorème 17 (Stone). Supposons que, quelle que soit la loi de X, les poids satis-fassent les conditions suivantes :

1. Il existe une constante c telle que, pour toute fonction borélienne f : Rd →R telle que E| f (X)| < ∞,

E

( n

∑i=1

Wni(X) | f (Xi)|)≤ c E | f (X)| pour tout n ≥ 1.

2. Pour tout a > 0,

E

( n

∑i=1

Wni(X)1[‖Xi−X‖>a]

)→ 0.

3. On a

E

(max

1≤i≤nWni(X)

)→ 0.

Alors la règle de classification associée gn est universellement convergente, i.e.

EL(gn)→ L?

quelle que soit la loi du couple (X, Y).

La condition 2 exprime le fait que la contribution des poids à l’extérieurde n’importe quelle boule fermée centrée en X doit être asymptotiquementnégligeable. En d’autres termes, seuls les points situés dans un voisinagelocal de la cible sont importants pour l’évaluation de la moyenne. La condi-tion 3 interdit à un seul point d’avoir une influence disproportionnée surle calcul de l’estimateur. Enfin, l’hypothèse 1, parfois appelée condition deStone, est essentiellement de nature technique. Insistons bien sur le fait quele résultat du théorème est universel, au sens où la convergence est valablequelle que soit la loi du couple (X, Y) !

Démonstration du Théorème 17. En vertu du Théorème 16, nous savons qu’ilsuffit de montrer que, quelle que soit la loi de (X, Y), on a

E (rn(X)− r(X))2 =∫

Rd(rn(x)− r(x))2 µ(dx)→ 0.

Posons

rn(x) =n

∑i=1

Wni(x)r(Xi).

101


En utilisant l’inégalité (a + b)2 ≤ 2(a2 + b2), on a

E (rn(X)− r(X))2 = E (rn(X)− rn(X) + rn(X)− r(X))2

≤ 2(

E (rn(X)− rn(X))2 + E (rn(X)− r(X))2)

. (10.4)

Il suffit donc de montrer que chacun des deux termes ci-dessus tend vers0 lorsque n tend vers l’infini. Comme les poids Wni(x) sont positifs et nor-malisés, l’inégalité de Jensen permet d’écrire que

E (rn(X)− r(X))2 = E

( n

∑i=1

Wni(X) (r(Xi)− r(X))

)2

≤ E

( n

∑i=1

Wni(X) (r(Xi)− r(X))2)

.

Si la fonction r, qui satisfait 0 ≤ r ≤ 1, est continue à support borné, alorselle est aussi uniformément continue. Ainsi, pour tout ε > 0, il existe a > 0tel que ‖x − x′‖ ≤ a implique |r(x) − r(x′)|2 ≤ ε. Dans ce cas, comme|r(x)− r(x′)| ≤ 1, on obtient

E

( n

∑i=1


≤ E

( n

∑i=1

Wni(X)1[‖Xi−X‖>a]

)+ E

( n

∑i=1

Wni(X)ε

)→ ε,

d’après la condition 2. Dans le cas général, par densité, on peut toujourstrouver une fonction r? continue à support borné telle que

E (r(X)− r?(X))2 < ε.

Avec ce choix, et en utilisant le fait que (a + b + c)2 ≤ 3(a2 + b2 + c2), ontrouve

E (rn(X)− r(X))2

≤ E

( n

∑i=1


≤ 3( n

∑i=1

Wni(X)((r(Xi)− r?(Xi))

2 + (r?(Xi)− r?(X))2

+ (r?(X)− r(X))2))

.

102


Ainsi, en utilisant la condition 1,

E (rn(X)− r(X))2

≤ 3c E (r(X)− r?(X))2 + 3E

( n

∑i=1

Wni(X) (r?(Xi)− r?(X))2)

+ 3E (r?(X)− r(X))2 .

Au final,lim sup

n→+∞E (rn(X)− r(X))2 ≤ 3ε(2 + c).

Il nous reste à contrôler le premier terme du membre de droite de l’inégalité(10.4). Observons pour cela que, pour i 6= j,

E(Wni(X)

(Yi − r(Xi)

)Wnj(X)

(Yj − r(Xj)

)= E

[E(Wni(X)

(Yi − r(Xi)

)Wnj(X)

(Yj − r(Xj)

)|X, X1, . . . , Xn, Yi

) ]= E

[Wni(X)

(Yi − r(Xi)

)Wnj(X)E(Yj − r(Xj) |X, X1, . . . , Xn, Yi)

]= E

[Wni(X)

(Yi − r(Xi)

)Wnj(X)E(Yj − r(Xj) |Xj)

](par indépendence entre (Xj, Yj) et X, X1, Xj−1, Xj+1, . . . , Xn, Yi)

= E[Wni(X)

(Yi − r(Xi)

)Wnj(X)

(r(Xj)− r(Xj)

)]= 0.

Du coup,

E (rn(X)− rn(X))2 = E

( n

∑i=1

Wni(X) (Yi − r(Xi))

)2

=n

∑i=1

n

∑j=1

E(Wni(X) (Yi − r(Xi))Wnj(X)

(Yj − r(Xj)

))=

n

∑i=1

E(

W2ni(X) (Yi − r(Xi))

2)

.

On en déduit que

E (rn(X)− rn(X))2 ≤ E

( n

∑i=1

W2ni(X)

)≤ E

(max

1≤i≤nWni(X)

n

∑j=1

Wnj(X)

)= E

(max

1≤i≤nWni(X)

)→ 0,

103


d’après 3, ce qui conclut la preuve du théorème.

10.3 k-plus proches voisins

Dans la suite, k est un entier strictement positif compris entre 1 et n (fonc-tion de n). On rappelle que (X(1)(x), Y(1)(x)), . . . , (X(n)(x), Y(n)(x)) désignele réordonnement de l’échantillon original (X1, Y1), . . . , (Xn, Yn) suivant lesdistances euclidiennes croissantes des Xi à x.

Nous avons vu dans la section précédente que la règle de classification desk-plus proches voisins a pour expression

gn(x) =

{1 si 1

k ∑ki=1 1[Y(i)(x)=1] >

1k ∑k

i=1 1[Y(i)(x)=0]

0 sinon

ou, de façon équivalente,

gn(x) =

{1 si ∑k

i=1 1[Y(i)(x)=1] > ∑ki=1 1[Y(i)(x)=0]

0 sinon.

Le prochain théorème, dont la preuve utilise le théorème de Stone, établitla convergence universelle de la règle gn, pourvu que la dépendence de ken n ne soit pas trop anarchique.

Théorème 18. Supposons que k → +∞ et k/n → 0. Alors la règle de classifica-tion des k-plus proches voisins est universellement convergente, i.e.

EL(gn)→ L?

quelle que soit la loi du couple (X, Y).

Pour prouver le résultat, il suffit simplement de s’assurer que les condi-tions 1− 3 du théorème de Stone sont effectivement vérifiées par la règledes k-plus proches voisins. Pour ce faire, nous aurons au préalable besoinde quelques lemmes techniques. Pour simplifier un peu, nous supposeronsdans la suite que les égalités entre distances ‖Xi − x‖ = ‖Xj − x‖ se pro-duisent avec probabilité zéro (c’est par exemple le cas lorsque ‖X− x‖ ad-met une densité par rapport à la mesure de Lebesgue). La preuve du Théo-rème 18 s’étend au cas général, au prix de quelques petits aménagements

104


techniques pour gérer les distances ex-aequo. On rappelle que le supportde la loi µ est défini comme l’ensemble des x ∈ Rd tels que µ(B(x, ε)) > 0,avec B(x, ε) la boule fermée de centre x et de rayon ε. Alternativement, ils’agit du plus petit ensemble fermé de µ-mesure 1.

Lemme 5. Soit x dans le support de µ. Alors, si k/n→ 0, on a

‖X(k)(x)− x‖ → 0 P-p.s.

Démonstration. Fixons ε > 0 et observons, puisque x appartient au sup-port de µ, que µ(B(x, ε)) > 0. Notons également l’égalité suivante entreévénements :{

‖X(k)(x)− x‖ > ε

}=

{1n

n

∑i=1

1[Xi∈B(x,ε)] <kn

}.

Or, d’après la loi forte des grands nombres,

1n

n

∑i=1

1[Xi∈B(x,ε)] → µ (B(x, ε)) P-p.s.

Comme k/n → 0, on en conclut immédiatement que ‖X(k)(x) − x‖ → 0P-p.s.

Lemme 6. Soit ν une mesure de probabilité sur Rd. Fixons x′ ∈ Rd et définissons,pour a ≥ 0,

Ba(x′) ={

x ∈ Rd : ν(

B(x, ‖x′ − x‖))≤ a

}.

Alorsν(

Ba(x′))≤ γd a,

où γd est une constante strictement positive ne dépendant que de d.

Démonstration. Fixons x′ ∈ Rd et considérons une famille C1, . . . , Cγd decones d’angle π/6 centrés en x′, suffisamment nombreux pour que leurunion recouvre Rd. En d’autres termes,

γd⋃j=1

Cj = Rd.

105


Il est facile de voir (exercice) que si u ∈ Cj − {x′}, u′ ∈ Cj et ‖u− x′‖ ≤‖u′ − x′‖, alors ‖u− u′‖ < ‖u′ − x′‖. Par ailleurs,

ν(

Ba(x′))≤

γd

∑j=1

ν(Cj ∩ Ba(x′)

).

Soit alors x? ∈ Cj ∩ Ba(x′). En utilisant la propriété géométrique des conesmentionnée ci-dessus, nous pouvons écrire

ν(Cj ∩ B(x′, ‖x? − x′‖) ∩ Ba(x′)

)≤ ν

(B(x?, ‖x′ − x?‖)

)≤ a,

la seconde inégalité provenant du fait que x? ∈ Ba(x′). Puisque x? estarbitraire, on en conclut que

ν(Cj ∩ Ba(x′)

)≤ a.

Une conséquence fondamentale du lemme précédent indique que le nom-bre de points dans {X1, . . . , Xn} pour lesquels X figure parmi les k plusproches voisins ne dépasse pas une constante fois k. Dans la suite, l’abré-viation k-ppv signifie “k-plus proches voisins”.

Corollaire 2. Si les égalités entre distances se produisent avec probabilité zéro, ona

n

∑i=1

1[X est parmi les k-ppv de Xi dans {X1, . . . , Xi−1, X, Xi+1, . . . , Xn}] ≤ kγd,

P-p.s.

Démonstration. On applique le Lemme 6 avec a = k/n et ν la mesure empi-rique µn associée à X1, . . . , Xn. Avec ce choix, on a

Bk/n(X) ={

x ∈ Rd : µn (B(x, ‖X− x‖)) ≤ k/n}

et, P-p.s.,

Xi ∈ Bk/n(X)

⇔ µn (B(Xi, ‖X− Xi‖)) ≤ k/n⇔ X est parmi les k-ppv de Xi dans {X1, . . . , Xi−1, X, Xi+1, . . . , Xn}.

106


(Noter que la seconde équivalence utilise le fait que les égalités entre dis-tances se produisent avec probabilité zéro.) Ainsi, en appliquant le Lemme6, il vient, P-p.s.,

n

∑i=1

1[X est parmi les k-ppv de Xi dans {X1, . . . , Xi−1, X, Xi+1, . . . , Xn}]

=n

∑i=1

1[Xi∈Bk/n(X)]

= n× µn (Bk/n(X))

≤ kγd.

Lemme 7. Supposons que les égalités entre distances se produisent avec probabilitézéro. Alors, pour toute fonction borélienne f : Rd → R telle que E| f (X)| < ∞,on a

n

∑i=1

E∣∣ f (X(i)(X)

∣∣ ≤ kγdE | f (X)| ,

où γd est une constante strictement positive ne dépendant que de d.

Démonstration. Prenons f une fonction comme dans l’énoncé. Alorsn

∑i=1

E∣∣ f (X(i)(X)

∣∣= E

( n

∑i=1| f (Xi)|1[X est parmi les k-ppv de X dans {X1, . . . , Xn}]

)= E

(| f (X)|

×n

∑i=1

1[X est parmi les k-ppv de Xi dans {X1, . . . , Xi−1, X, Xi+1, . . . , Xn}]

)(en échangeant X et Xi)

≤ E (| f (X)| kγd) ,

d’après le Corollaire 2. Ceci conclut la preuve du lemme.

Nous sommes désormais en mesure de démontrer le Théorème 18. Il suffitpour cela de vérifier les conditions du théorème de Stone, avec Wni(x) =1/k si Xi est parmi les k plus proches voisins de X, et Wni(x) = 0 sinon.

107


La condition 3 est évidente dans la mesure où k → +∞. Pour la condition2, on note que

E

( n

∑i=1

Wni(X)1[‖Xi−X‖]>ε

)= E

(1k

k

∑i=1

1[‖X(i)(x)−X‖]>ε

),

de sorte que

E

( n

∑i=1

Wni(X)1[‖Xi−X‖]>ε

)→ 0

dès lors que, pour tout ε > 0,

P(‖X(k)(X)− X‖ > ε

)→ 0.

Or,P(‖X(k)(X)− X‖ > ε

)=∫

RdP(‖X(k)(x)− x‖ > ε

)µ(dx).

Pour x fixé dans le support de µ, le Lemme 5 indique que la convergence

P(‖X(k)(x)− x‖ > ε

)→ 0

a lieu lorsque k/n → 0. Le résultat s’en déduit par convergence dominée,en notant que le support de µ est de µ-mesure 1.

Examinons pour terminer la condition 1. Il s’agit de voir que, pour toutefonction f telle que E| f (X)| < ∞, on a

E

(1k

n

∑i=1| f (Xi)|1[Xi est parmi les k-ppv de X]

)≤ c E | f (X)| ,

pour une certaine constante c. C’est précisément l’énoncé du Lemme 7.

108

Chapitre 11

Quantification et clustering

11.1 Principe de la quantification

La quantification est un principe probabiliste dont l’objectif est de com-presser l’information contenue dans une variable aléatoire X à valeurs dans(Rd, ‖ · ‖), où ‖ · ‖ désigne la norme euclidienne. On se donne dorénavantune telle variable X, en notant µ sa loi et en supposant que E‖X‖2 < ∞ ou,ce qui est équivalent, que ∫

Rd‖x‖2µ(dx) < ∞.

Définition 31. Soit k un entier ≥ 1. Un quantifieur q d’ordre k est une fonctionmesurable q : Rd → C ⊂H avec |C | ≤ k.

Un quantifieur q d’ordre k est donc caractérisé par :

. Un alphabet C = {c1, . . . , ck}.

. Une partition P = {A1, . . . , Ak} de Rd, avec la numérotation imposéepar

q(x) = cj ⇔ x ∈ Aj.

On écrira dans la suite q = (C , P). Un quantifieur apparaît ainsi commeun outil de compression de l’information. L’étape suivante consiste alorsà se doter d’un critère mesurant la pertinence de la compression de lavariable aléatoire X (ou de sa loi) au travers de q.

109

Chapitre 11 Quantification et clustering

Définition 32. La distorsion (pour X ou µ) d’un quantifieur q = (C , P) d’ordrek est définie par

D(µ, q) = E‖X− q(X)‖2 =∫

Rd‖x− q(x)‖2µ(dx).

La distorsion minimale à l’ordre k est

D?k (µ) = inf

qD(µ, q),

où l’infimum est évalué sur tous les quantifieurs d’ordre k.

Bien entendu, plus la distorsion est faible, meilleure est la compression. Parailleurs, comme on s’en doute, la qualité d’une quantification s’améliorelorsque k grandit. Ce phénomène est précisé dans le lemme ci-dessous.

Lemme 8. On a D?k (µ)↘ 0 si k→ +∞.

Démonstration. Tout d’abord, il est clair que la distorsion minimale décroîtà mesure que son ordre augmente. Puis, comme Rd est un espace polonais,la mesure bornée ν définie pour tout borélien A de Rd par

ν(A) =∫

A‖x‖2µ(dx)

est tendue, i.e. pour tout ε ∈ ]0, 1], il existe un compact K tel que ν(K) ≥1− ε. On note {c1, c2, . . .} un sous-ensemble dénombrable dense dans Rd.Comme K est compact, on a pour tout k assez grand

K ⊂ B :=k⋃

j=1

B(cj,√

ε).

On a donc ν(B) ≥ 1 − ε. Notons maintenant qk+1 le quantifieur d’ordrek + 1 d’alphabet {c1, . . . , ck, 0} (en supposant, sans perte de généralité, que0 /∈ {c1, c2, . . .}) et de partition {A1, . . . , Ak, Bc}, avec A1 = B(c1,

√ε) et,

pour j = 2, . . . , k, Aj = B(cj,√

ε) \ Aj−1. Comme ‖x− cj‖ ≤√

ε si x ∈ Aj,on a

D?k+1(µ) ≤ Dk+1(µ, qk+1) =

∫Rd‖x− qk+1(x)‖2µ(dx)

=k

∑j=1

∫Aj

‖x− cj‖2µ(dx) +∫

Bc‖x‖2µ(dx)

≤ εµ

( k⋃j=1

Aj

)+ ν(Bc) ≤ 2ε,

110


ce qui achève la preuve.

Parmi toutes les façons possibles de compresser l’information, la classedes quantifieurs de type plus proches voisins (que nous abrégerons désor-mais en quantifieurs PPV) joue un rôle bien particulier. Dans la suite, onsuppose que les quantifieurs sont d’ordre k et on note, pour un alphabetC = {c1, . . . , ck} ⊂ Rd de taille k, PV(C ) la partition de Voronoi associée àC , définie par

A1 ={

x ∈ Rd : ‖x− c1‖ ≤ ‖x− c`‖, ∀` = 1, . . . , k}

, et

Aj ={

x ∈ Rd : ‖x− cj‖ ≤ ‖x− c`‖, ∀` = 1, . . . , k}\

j−1⋃t=1

At,

pour j = 2, . . . , k.

Définition 33. Un quantifieur d’ordre k est un quantifieur PPV si sa partition estune partition de Voronoi associée à son alphabet. En d’autres termes, un quantifieurPPV s’écrit q = (C , PV(C )), avec C ⊂ Rd de cardinal inférieur ou égal à k.

Un quantifieur PPV q est donc entièrement caractérisé par son alphabet(dont les élèments sont appelés centres ou centroïdes), via la règle

‖x− q(x)‖ = mincj∈C‖x− cj‖,

les égalités entre distances sur le bord des cellules étant brisées en faveurdes plus petits indices. On notera les propriétés élémentaires suivantes.

Proposition 6. Soit qppv un quantifieur PPV d’alphabet C = {c1, . . . , ck}. Alors

D(µ, qppv) = E min1≤j≤k

‖X− cj‖2 =∫

Rdmin

1≤j≤k‖x− cj‖2µ(dx).

En outre, pour tout quantifieur q = (C , P), on a D(µ, qppv) ≤ D(µ, q).

Démonstration. Pour la première propriété, en désignant par PV(C ) ={AV,1, . . . , AV,k} la partition de Voronoi associée à C :

D(µ, qppv) =∫

Rd‖x− qppv(x)‖2µ(dx) =

k

∑j=1

∫AV,j

‖x− cj‖2µ(dx)

=∫

Rdmin

1≤j≤k‖x− cj‖2µ(dx).

111


Puis, pour la seconde propriété, si P = {A1, . . . , Ak},

D(µ, qppv) =k

∑j=1

∫Aj

min1≤j≤k


≤k

∑j=1

∫Aj


≤∫

Rd‖x− q(x)‖2µ(dx) = D(µ, q),

par définition de la distorsion.

La conséquence fondamentale de cette dernière proposition est que lesquantifieurs de distorsion minimale, s’ils existent, sont à rechercher parmiles quantifieurs du type qppv = (c, PV(c)) avec c = (c1, . . . , ck) ∈ Rdk

(noter l’abus de notation), de distorsion

W(µ, c) :=∫

Rdmin

1≤j≤k‖x− cj‖2µ(dx) = D(µ, qppv).

Théorème 19. Il existe un quantifieur de distorsion minimale.

Esquisse de démonstration. D’après la Proposition 6, on peut restreindre l’é-tude aux quantifieurs PPV. Il s’agit donc de montrer qu’il existe c? ∈ Rdk

tel queW(µ, c?) = inf

c∈RdkW(µ, c).

On prouve d’abord (admis) qu’il existe R > 0 tel que

infc∈Rdk

W(µ, c) = inf‖c‖≤R

W(µ, c).

On établit ensuite que la fonction Rdk 3 c 7→ W(µ, c) est continue. Ob-servons pour cela que la fonction x 7→ min1≤j≤k ‖x− cj‖ est continue. Dèslors, pour c0 = (c1,0, . . . , ck,0) ∈ Rdk, on a

limc→c0

W(µ, c) =∫

Rdlimc→c0

min1≤j≤k


(d’après le théorème de Lebesgue)

=∫

Rdmin

1≤j≤k‖x− cj,0‖2µ(dx)

(par continuité)= W(µ, c0),

112


ce qui montre bien que W(µ, ·) est continue.

On déduit de cette dernière propriété et de la compacité de la boule B(0, R)de Rdk qu’il existe c? ∈ Rdk minimum de W(µ, ·). Le quantifieur q? =(c?, Pppv(c?)) est alors de distorsion minimale car

W(µ, c?) = infc∈Rdk

W(µ, c) = infq

D(µ, q) = D?(µ).

11.2 Quantification empirique et clustering

Dans la pratique, la loi µ de la variable aléatoire X est inconnue et il estdonc, par voie de conséquence, impossible de procéder à sa quantifica-tion. On dispose cependant bien souvent d’un n-échantillon i.i.d. X1, . . . , Xnformé de variables aléatoires indépendantes entre elles, de même loi que Xet indépendante de cette dernière. C’est à partir de cet échantillon que l’onva s’attacher à construire un quantifieur empirique qn(·) = qn(·, X1, . . . , Xn)dont les performances se rapprochent si possible de celles du quantifieuroptimal.

On suppose toujours que E‖X‖2 < ∞ et on désigne par µn la mesureempirique associée à X1, . . . , Xn, i.e.

µn =1n

n

∑i=1

δXi .

Dans ce contexte, la distorsion pour µ du quantifieur empirique qn (d’ordrek) est naturellement définie par

D(µ, qn) = E(‖X− qn(X)‖2 |X1, . . . , Xn

)=∫

Rd‖x− qn(x)‖2µ(dx)

(noter qu’il s’agit d’une variable aléatoire). La distorsion empirique d’unquantifieur q prend la forme

D(µn, q) =∫

Rd‖x− q(x)‖2µn(dx) =

1n

n

∑i=1‖Xi − q(Xi)‖2.

113


Dans le cas particulier de qppv = (c, PV(c)), avec c = (c1, . . . , ck) ∈ Rdk, ona

D(µn, qppv) = W(µn, c) =1n

n

∑i=1

min1≤j≤k

‖Xi − cj‖2.

Pour se doter d’outils qui assurent que la méthode de quantification empi-rique est performante, on introduit la définition qui suit.

Définition 34. Soit qn un quantifieur empirique. On dit qu’il est consistant siED(µ, qn) → D?(µ). On dit qu’il est de vitesse (vn)n si ED(µ, qn)− D?(µ) =O(1/vn), avec vn → +∞.

On aura noté au passage que, puisque D(µ, qn) ≥ D?(µ), la propriétéED(µ, qn)→ D?(µ) est équivalente à D(µ, qn)→ D?(µ) dans L1.

Le quantifieur empirique q?n le plus naturel est obtenu en minimisant la dis-torsion empirique sur les quantifieurs PPV. En d’autres termes, on chercheles centres optimaux c?n = (c?n,1, . . . , c?n,k) tels que

W(µn, c?n) = infc∈Rdk

W(µn, c). (11.1)

(Observons que q?n existe en vertu du Théorème 19.) On a donc

q?n = (c?n, PV(c?n)) .

Un quantifieur empirique qn (d’ordre k) est naturellement associé à une mé-thode de regroupement (ou clustering) des données X1, . . . , Xn en k classes,en décidant que l’observation Xi est rangée dans la classe j (1 ≤ j ≤ k) siqn(Xi) = j.

Pour le quantifieur empirique PPV optimal q?n, le j-ème cluster est constituédes observations Xi telles que ‖Xi − c?n,j‖ ≤ ‖Xi − c?n,`‖, ∀` = 1, . . . , k.

On parle parfois, en lieu et place de clustering, de classification (ou appren-tissage) non supervisé, l’adjectif “non supervisé” renvoyant au fait qu’il n’ya pas d’information annexe apportée par des variables réponses Yi. Le pro-blème consiste ici à regrouper les données X1, . . . , Xn “à l’aveugle”, de lafaçon la plus pertinente possible et sans information annexe.

114


Algorithme des k-means. En pratique, l’approche (11.1) par minimisa-tion de la distorsion empirique est difficile à mettre en œuvre, surtouten grande dimension (problème NP-complet). On a alors recours à unetechnique approchée, appelée algorithme des k-means. Cette procédure estfondée sur la remarque suivante. Pour une partition P = {A1, . . . , Ak}et C = {c1, . . . , ck} ⊂ Rd, on définit q = (C , P) et qn = (Cn, P), avecCn = {cn,1, . . . , cn,k} tel que, pour tout j = 1, . . . , k,

cn,j = arg miny∈Rd

n

∑i=1‖Xi − y‖21[Xi∈Aj]

=

1n ∑n

i=1 Xi1[Xi∈Aj]

1n ∑n

i=1 1[Xi∈Aj]

. (11.2)

Noter que cn,j est, à un facteur près, une espérance conditionnelle pour lamesure empirique. On a alors

D(µn, q) =1n

k

∑j=1

n

∑i=1‖Xi − cj‖21[Xi∈Aj]

≥ 1n

k

∑j=1

n

∑i=1‖Xi − cn,j‖21[Xi∈Aj]

= D(µn, qn).

En d’autres termes, l’opération (11.2) permet de faire décroître la distorsiondu quantifieur q, en conservant sa partition mais en modifiant les centres.

Ce qui précède conduit naturellement à une technique de minimisationeffective permettant d’approcher les centres optimaux c?n définis par (11.1).Pour ce faire, on commence par choisir un jeu de k centres (plus ou moinsau hasard) C (1) = {c(1)1 , . . . , c(1)k }, en notant P

(1)V = {A(1)

1 , . . . , A(1)k } la

partition de Voronoi associée. On répète ensuite le processus en passant deC (`) = {c(`)1 , . . . , c(`)k } à C (`+1) = {c(`+1)

1 , . . . , c(`+1)k } via l’itération (dite de

Lloyd) :

c(`+1)j =

1n ∑n

i=1 Xi1[Xi∈A(`)j ]

1n ∑n

i=1 1[Xi∈A(`)j ]

, 1 ≤ j ≤ k,

avec {A(`)1 , . . . , A(`)

k } la partition de Voronoi à l’étape `, associée à C (`). Onnotera que l’affectation de Xi à sa cellule de Voronoi s’effectue très facile-ment via la recherche de son plus proche voisin dans c(`)1 , . . . , c(`)k . Même s’il

115


est assuré que la distorsion décroît entre deux itérations et que l’algorithmes’arrête au bout d’un nombre d’itérations fini, rien ne garantit cependantque les centres ainsi définis soient proches des centres optimaux c?n. Il s’agitd’une méthode approchée que l’on manipulera donc avec prudence...

11.3 Consistance et vitesse

L’outil indispensable pour établir la consistance du quantifieur empiriquePPV optimal défini via (11.1) est la distance de Wasserstein.

Définition 35. Soient ν1 et ν2 des probabilités d’ordre 2 sur Rd. La distance deWasserstein ρW entre ν1 et ν2 est définie par

ρW(ν1, ν2) = infX∼ν1,Y∼ν2

√E‖X−Y‖2.

Il s’agit d’une distance usuelle sur les mesures de probabilité. Mentionnonssans preuve deux de ses propriétés fondamentales :

Propriétés.

1. Pour ν1, ν2 des probabilités d’ordre 2 sur Rd, il existe un couple devariables aléatoires (X0, Y0) telles que X0 ∼ ν1, Y0 ∼ ν2, et

ρW(ν1, ν2) =√

E‖X0 −Y0‖2.

2. Soient (νn)n et ν des probabilités d’ordre 2 sur Rd. On a ρW(νn, ν)→ 0si

νn ⇒ ν et∫

Rd‖x‖2νn(dx)→

∫Rd‖x‖2ν(dx).

Le lien entre l’étude qui nous intéresse et la distance de Wasserstein estétabli dans la proposition qui suit.

Proposition 7. Soient ν1 et ν2 des probabilités d’ordre 2 sur Rd. Si q est unquantifieur PPV, alors∣∣∣D(ν1, q)1/2 − D(ν2, q)1/2

∣∣∣ ≤ ρW(ν1, ν2).

116


Démonstration. Soit (X0, Y0) tel que X0 ∼ ν1, Y0 ∼ ν2, et

ρW(ν1, ν2) =√

E‖X0 −Y0‖2.

Si q = (c, PV(c)), alors :

D(ν1, q)1/2 = W(ν1, c)1/2 =√

E min1≤j≤k

‖X0 − cj‖2

=√

E(

min1≤j≤k

‖X0 − cj‖)2

≤√

E(

min1≤j≤k

(‖X0 −Y0‖+ ‖Y0 − cj‖

) )2

≤√

E(‖X0 −Y0‖+ min

1≤j≤k‖Y0 − cj‖

)2

≤√

E‖X0 −Y0‖2 +√

E min1≤j≤k

‖Y0 − cj‖2

(en utilisant l’inégalité de Cauchy-Schwarz)

= ρW(ν1, ν2) + D(ν2, q)1/2,

d’où la proposition.

On considère à partir de maintenant le quantifieur empirique optimal PPVq?n, défini via (11.1) par ses centres c?n = (c?n,1, . . . , c?n,k) :

q?n = (c?n, PV(c?n)) .

Théorème 20. Le quantifieur q?n est consistant, i.e. ED(µ, q?n)→ D?(µ).

Démonstration. Si q? est un quantifieur optimal PPV pour µ, on a, d’aprèsla Proposition 7,

D(µ, q?n)1/2 − D?(µ)1/2

=[

D(µ, q?n)1/2 − D(µn, q?n)

1/2]+[

D(µn, q?n)1/2 − D(µ, q?)1/2

]≤[

D(µ, q?n)1/2 − D(µn, q?n)

1/2]+[

D(µn, q?)1/2 − D(µ, q?)1/2]

≤ 2 ρW(µ, µn).

117


Or, ρW(µn, µ) → 0 P-p.s. car P(µn ⇒ µ) = 1 (théorème de Varadarajan) etP-p.s. ∫

Rd‖x‖2µn(dx)→

∫Rd‖x‖2µ(dx)

(loi forte des grands nombres). On en conclut que D(µ, q?n)→ D?(µ) P-p.s,i.e. q?n est consistant.

Analysons maintenant la vitesse de convergence de q?n. Pour ce faire, noussupposerons qu’il existe une constante R ≥ 0 telle que ‖X‖ ≤ R P-p.s.Cette hypothèse est parfois appelée contrainte de pic dans le vocabulaire dela quantification.

Théorème 21. Si ‖X‖ ≤ R P-p.s., alors

ED(µ, q?n)− D?(µ) ≤ 12kR2√

n.

Enonçons tout d’abord, sans preuve, un outil fondamental dans l’étude dela mesure empirique :

Lemme 9 (Principe de contraction). Soit σ1, . . . , σn des variables aléatoires i.i.d.de loi de Rademacher, indépendantes de X1, . . . , Xn, et soit F un ensemble defonctions réelles définies sur Rd. Si |F | = {| f | : f ∈ F}, on a

E supf∈F

1n

∣∣∣∣ n

∑i=1

σi | f (Xi)|∣∣∣∣ ≤ E sup

f∈F

1n

∣∣∣∣ n

∑i=1

σi f (Xi)

∣∣∣∣.Remarques préliminaires.

1. Si ‖X‖ ≤ R P-p.s, alors les centres optimaux sont dans BR = B(0, R).En effet, si ‖c‖ > R et p est la projection orthogonale sur BR, alors,par définition de la projection orthogonale, on a, ∀x ∈ BR,

‖x− c‖2 = ‖x− p(c)‖2 + ‖p(c)− c‖2 − 2〈x− p(c), c− p(c)〉≥ ‖x− p(c)‖2.

On a donc une distorsion plus petite pour des centres dans BR.2. Si X ∼ µ, on a

W(µ, c) = E min1≤j≤k

‖X− cj‖2

= E‖X‖2 + E min1≤j≤k

(−2〈X, cj〉+ ‖cj‖2

).

118


Ces deux observations nous conduisent à la conclusion suivante : plutôtque de minimiser W(µ, ·) sur Rdk, il suffit donc de minimiser, sur Bk

R,

W(µ, c) = E min1≤j≤k

fcj(X), si fc(x) = −2〈x, c〉+ ‖c‖2.

La même observation est valable en remplaçant µn au lieu de µ.

Démonstration du Théorème 21. On a

D(µ, q?n)− D?(µ)

= W(µ, c?n)− infc∈Bk

R

W(µ, c)

= W(µ, c?n)− infc∈Bk

R

W(µ, c)

=[W(µ, c?n)− W(µn, c?n)

]+[

infc∈Bk

R

W(µn, c)− infc∈Bk

R

W(µ, c)]

≤ 2 supc∈Bk

R

∣∣W(µn, c)− W(µ, c)∣∣

= 2 supc∈Bk

R

1n

∣∣∣∣ n

∑i=1

(min

1≤j≤kfcj(Xi)−E min

1≤j≤kfcj(X)

)∣∣∣∣.En utilisant un n-échantillon indépendant annexe X′1, . . . , X′n et un argu-ment de symétrisation similaire à celui employé dans la preuve du théo-rème de Vapnik-Chervonenkis (Théorème 13), il vient

ED(µ, q?n)− D?(µ)

≤ 2E supc∈Bk

R

1n

∣∣∣∣ n

∑i=1

(min

1≤j≤kfcj(Xi)−E min

1≤j≤kfcj(X)

)∣∣∣∣= 2E sup

c∈BkR

1n

∣∣∣∣E[ n

∑i=1

(min

1≤j≤kfcj(Xi)− min

1≤j≤kfcj(X′i)

) ∣∣X1, . . . , Xn

]∣∣∣∣≤ 2E sup

c∈BkR

1n

E

[∣∣∣∣ n

∑i=1

(min


1≤j≤kfcj(X′i)

)∣∣∣∣ ∣∣X1, . . . , Xn

](par l’inégalité de Jensen).

119


Ainsi, en observant que sup E(·) ≤ E sup(·),

ED(µ, q?n)− D?(µ) ≤ 2E supc∈Bk

R

1n

∣∣∣∣ n

∑i=1

(min


1≤j≤kfcj(X′i)

)∣∣∣∣≤ 4E sup

c∈BkR

1n

∣∣∣∣ n

∑i=1

σi min1≤j≤k

fcj(Xi)

∣∣∣∣.Pour le traitement de ce dernier terme, nous allons procéder par itérationsur k, en nous appuyant sur le principe de contraction. On note

Sk = E sup(c1,...,ck)∈Bk

R

1n

∣∣∣∣ n

∑i=1

σi min1≤j≤k

fcj(Xi)

∣∣∣∣.Cas k = 1. Comme ‖X‖ ≤ R :

S1 = E supc∈BR

1n

∣∣∣∣ n

∑i=1

σi(− 2〈Xi, c〉+ ‖c‖2)∣∣∣∣

≤ 2E supc∈BR

1n

∣∣∣∣ n

∑i=1

σi〈Xi, c〉∣∣∣∣+ E sup

c∈BR

‖c‖2

n

∣∣∣∣ n

∑i=1

σi

∣∣∣∣≤ 2E sup

c∈BR

1n

∣∣∣∣ n

∑i=1

σi〈Xi, c〉∣∣∣∣+ R2

nE

∣∣∣∣ n

∑i=1

σi

∣∣∣∣≤ 2E sup

c∈BR

1n

∣∣∣∣ n

∑i=1

σi〈Xi, c〉∣∣∣∣+ R2√

n

(par l’inégalité de Cauchy-Schwarz).

Ainsi,

S1 ≤ 2E supc∈BR

1n

∣∣∣∣⟨ n

∑i=1

σiXi, c⟩∣∣∣∣+ R2

√n

≤ 2Rn

E

∥∥∥∥∥ n

∑i=1

σiXi

∥∥∥∥∥+ R2√

n

≤ 2R

√E‖X‖2

n+

R2√

n(par l’inégalité de Cauchy-Schwarz)

≤ 3R2√

n.

120


Cas k = 2. Comme min(a, b) = a+b2 −

|a−b|2 , on a

S2 = E sup(c1,c2)∈B2

R

12n

∣∣∣∣ n

∑i=1

σi(

fc1(Xi) + fc2(Xi)− | fc1(Xi)− fc2(Xi)|)∣∣∣∣

≤ S1 + E sup(c1,c2)∈B2

R

12n

∣∣∣∣ n

∑i=1

σi∣∣ fc1(Xi)− fc2(Xi)

∣∣∣∣∣∣.En appliquant le principe de contraction, on obtient

S2 ≤ S1 + E sup(c1,c2)∈B2

R

12n

∣∣∣∣ n

∑i=1

σi(

fc1(Xi)− fc2(Xi))∣∣∣∣

≤ 2S1.

Cas k = 3. Comme S2 ≤ 2S1,

S3 ≤S1 + S2

2+

S1 + S2

2≤ 3S1.

En itérant le procédé, on trouve

Sk ≤ kS1 ≤3kR2√

n.

Finalement,

ED(µ, q?n)− D?(µ) ≤ 4Sk ≤12kR2√

n,


121

Documents

Statistique et apprentissage · 2016-03-09 · Ce document contient les notes du cours Statistique et apprentissage donné dans le cadre de la spécialité Probabilités et modèles