§ 01

L'intuition

L’intuition

Tu prépares un examen sur les annales. Le jour du blanc, tu as 19/20. Que vaudra ta note demain, sur un sujet que tu n'as jamais vu ?

Deux histoires produisent le même 19/20. Dans la première, tu as compris le cours : demain tu auras 19 aussi. Dans la seconde, tu as appris les corrigés par cœur : demain tu auras 6. Rien dans ta note d'annales ne permet de distinguer les deux cas. Il faut une information de plus, et une seule : à quel point es-tu capable de produire n'importe quelle réponse. Un étudiant qui saurait réciter 10 000 corrigés aurait 19/20 même si les corrigés avaient été écrits au hasard. C'est cela, et rien d'autre, que mesure la théorie de l'apprentissage.

Le module 2.1 a posé le pari : on minimise le risque empirique , calculable sur les exemples dont on dispose, en espérant faire baisser le risque réel , qui ne sera jamais observé. Le module 2.2 a nommé les deux façons de perdre ce pari (biais, variance) et le module 2.4 a donné le protocole qui l'évalue honnêtement. Ce module-ci répond à la seule question qui reste, et c'est une question de mathématicien :

Sous quelles conditions le pari est-il gagné — pas « en pratique », mais avec une garantie démontrée ?
Combien d'exemples faut-il pour que l'écart entre et soit inférieur à , avec une probabilité au moins ?
Qu'est-ce qui, dans un modèle, décide de ce nombre d'exemples ? Le nombre de paramètres ? La réponse est non, et le contre-exemple du §2.6 ci-dessous est spectaculaire.

Prévenons tout de suite : c'est le module le plus abstrait du monde 2, et c'est aussi celui qui finit par une défaite honnête. La théorie qu'on va construire est magnifique, elle explique parfaitement la régression logistique et le SVM — et elle ne dit strictement rien d'un réseau de neurones moderne. Tu dois savoir les deux : ce qui est garanti, et où la garantie s'arrête. Un ingénieur qui confond « la borne est vide » avec « le modèle est mauvais » se trompe autant que celui qui croit que sa borne le protège.

Le contrat de lecture de ce module

Le corps du module est écrit pour être lu d'une traite, sans ouvrir une seule plongée : tu y trouveras les énoncés, les chiffres et ce qu'ils veulent dire. Les cinq plongées contiennent les démonstrations complètes. Si tu ne dois faire qu'une chose, fais le §4 à la main : trois calculs y tombent juste, et ils contiennent tout le module.

§ 02

La théorie

Où l'on se situe dans les « 4 étapes »

Le cadre de Machine Learnia1 découpe l'apprentissage supervisé en quatre cases : 1. Dataset — 2. Modèle — 3. Fonction Coût — 4. Algorithme de minimisation.

Ce module ne remplit aucune des quatre cases : il chiffre le prix de la case 2. Plus la boîte « Modèle » est riche — plus la classe d'hypothèses dans laquelle on choisit est grande — plus il est facile de rendre la case 3 petite, et moins ce petit nombre veut dire quelque chose. La théorie de l'apprentissage est la comptabilité exacte de ce marché : combien d'exemples la case 1 doit-elle contenir pour payer la richesse de la case 2.

Deux conséquences immédiates. La case 4 n'intervient pas : les bornes ci-dessous valent uniformément sur toute la classe, donc quel que soit le que ton optimiseur a fini par sortir. Et la case 3 est fixée à la perte 0-1 — on compte les erreurs, pas des logarithmes de vraisemblance. C'est la perte pour laquelle la théorie est complète.

2.1 Le cadre, en cinq lignes

Une distribution inconnue sur engendre les couples . Un échantillon est tiré i.i.d. selon (module 0.5). Une classe d'hypothèses est un ensemble de fonctions . Deux nombres, et tout le module tient dans leur écart :

R(h) = \Prob_{(x,y) \sim \Data}\big[h(x) \ne y\big] = \E_{\Data}\big[\ind\{h(x) \ne y\}\big], \qquad \hat{R}_S(h) = \frac{1}{m}\sum_{i=1}^{m} \ind\big\{h(x^{(i)}) \ne y^{(i)}\big\}

(1)

est le risque réel, inaccessible. est le risque empirique, calculable. L'algorithme ERM rend .

Attention au faux ami : est l'exactitude (accuracy) du classifieur, pas sa précision (precision), qui est une autre quantité, définie au module 2.5. Toute cette théorie porte sur l'exactitude.

2.2 Le point de départ : pour un fixé, tout va bien

Fixe une hypothèse avant de voir les données. Alors les indicatrices sont i.i.d., à valeurs dans , d'espérance , et leur moyenne est . L'inégalité de Hoeffding5 donne alors, pour tout :

\Prob_S\Big[\big|\hat{R}_S(h) - R(h)\big| \ge \varepsilon\Big] \ \le\ 2\,e^{-2m\varepsilon^2}

(2)

C'est une décroissance exponentielle en : avec 1 000 exemples et , la probabilité de se tromper de plus de 5 points est inférieure à . Si la question était « estimer le risque d'un modèle qu'on me donne », le module serait fini — et c'est exactement ce qu'on exploitera au §6 pour dimensionner un jeu de test.

Pourquoi l'équation (2) ne suffit pas — le vrai problème du module

L'ERM ne rend pas un fixé d'avance : il rend , choisi en fonction de . Les ne sont alors plus indépendants de l'hypothèse, et (2) ne s'applique tout simplement pas. C'est exactement l'erreur de l'étudiant qui récite : il choisit sa réponse après avoir vu le sujet.

Le seul remède connu est brutal : exiger que (2) tienne pour toutes les hypothèses à la fois. On appelle cela la convergence uniforme, et tout le reste du module consiste à en payer le prix.

2.3 Le cadre PAC : deux lettres, et

Valiant3 a posé en 1984 la bonne définition : on n'exigera ni la perfection, ni la certitude. Probablement Approximativement Correct.

Définition — apprenabilité PAC agnostique

Une classe est PAC-apprenable au sens agnostique s'il existe une fonction et un algorithme tels que, pour toute distribution et tout , l'échantillon de taille vérifie, avec probabilité au moins :

R\big(A(S)\big) \ \le\ \min_{h \in \Hyp} R(h) \ +\ \varepsilon

est la tolérance (approximativement), le risque d'échec (probablement), et la complexité d'échantillon. Le cas réalisable est le sous-cas où l'on sait que : la vérité est dans la classe.

Trois points de vigilance. Un : le « pour toute distribution » est ce qui rend la théorie utilisable sans hypothèse sur les données — et c'est aussi ce qui la rend pessimiste. Deux : la garantie est relative au meilleur élément de , jamais absolue ; si ta classe est mauvaise, PAC te garantit seulement d'être aussi mauvais qu'elle. Trois : est irréductible — quelle que soit la taille de , un tirage catastrophique reste possible.

2.4 Le cas fini : tout le mécanisme, en deux inégalités

Suppose finie, de cardinal . La recette tient en deux temps : appliquer (2) à chaque hypothèse, puis payer une borne de l'union (union bound) pour les couvrir toutes. C'est la dérivation canonique du cours de Stanford CS22910, et elle contient déjà tout le raisonnement du module.

\Prob_S\Big[\ \exists\, h \in \Hyp : \big|\hat{R}_S(h) - R(h)\big| \ge \varepsilon\ \Big] \ \le\ \sum_{h \in \Hyp} \Prob_S\Big[\big|\hat{R}_S(h) - R(h)\big| \ge \varepsilon\Big] \ \le\ 2\,|\Hyp|\,e^{-2m\varepsilon^2}

(3)

On égale le membre de droite à et on résout en . C'est la borne de base de toute la théorie :

\boxed{\ \text{avec probabilité} \ge 1-\delta, \quad \forall h \in \Hyp : \quad \big|\hat{R}_S(h) - R(h)\big| \ \le\ \sqrt{\frac{\ln|\Hyp| + \ln(2/\delta)}{2m}}\ }

(4)

Ce que l'équation (4) dit exactement

, pas . Doubler le nombre d'hypothèses ne coûte que au numérateur. C'est le logarithme qui rend l'apprentissage possible. Et il a une lecture exacte, celle du module 0.6 : est le nombre de nats nécessaires pour désigner une hypothèse dans la classe. La complexité d'une classe, c'est le coût de son adressage.
. Diviser l'incertitude par 2 coûte quatre fois plus de données. C'est la même racine que l'erreur type d'une moyenne, et dans le pire cas elle ne s'améliore pas : c'est le taux du cadre agnostique, où Hoeffding suppose la variance maximale . Sur un problème particulier — cas réalisable, bruit franchement écarté de — l'écart réel peut décroître en (§4.3), mais aucune borne uniforme sur toute distribution ne peut le savoir d'avance.
La garantie est uniforme. Elle vaut pour toutes les hypothèses simultanément, donc en particulier pour , qui dépend pourtant de . C'est tout le travail de l'union bound.
Et l'ERM est alors presque optimal : en appliquant (4) deux fois, à puis au meilleur , on obtient . Le facteur 2 est le prix de l'aller-retour ; la plongée le montre en trois lignes.

Dérivation complète du cas fini : Hoeffding, borne de l'union, et l'optimalité de l'ERMNiveau 2

A. L'inégalité de Hoeffding

Soient indépendantes, à valeurs dans , de moyenne empirique . Alors5 :

\Prob\big[\bar{Z} - \E[\bar{Z}] \ge \varepsilon\big] \ \le\ \exp\!\left(\frac{-2m^2\varepsilon^2}{\sum_i (b_i - a_i)^2}\right)

(5)

Ici , donc et le dénominateur vaut : l'exposant devient . En ajoutant la queue symétrique on obtient le facteur 2 de l'équation (2). ∎

D'où vient (5) ? De la méthode de Chernoff. Pour , l'inégalité de Markov appliquée à la variable positive donne

\Prob\Big[\textstyle\sum_i (Z_i - \E Z_i) \ge m\varepsilon\Big] \ \le\ e^{-\lambda m \varepsilon} \prod_{i=1}^{m} \E\big[e^{\lambda (Z_i - \E Z_i)}\big]

Le lemme de Hoeffding majore chaque facteur : pour . Avec , le produit vaut au plus , et il reste à minimiser en : une parabole, minimale en , de valeur . ∎ On retrouvera exactement ce schéma « transformée exponentielle, majoration, optimisation en » dans le lemme de Massart, plus bas.

B. La borne de l'union, ligne à ligne

Note l'événement — le mauvais événement pour l'hypothèse . La sous-additivité de la mesure de probabilité donne, sans aucune hypothèse d'indépendance entre les — et c'est essentiel, car ils sont très corrélés :

\Prob\Big[\bigcup_{h \in \Hyp} B_h\Big] \ \le\ \sum_{h \in \Hyp} \Prob[B_h] \ \le\ |\Hyp| \cdot 2 e^{-2m\varepsilon^2}

On pose et on inverse :

e^{-2m\varepsilon^2} = \frac{\delta}{2|\Hyp|} \ \Longrightarrow\ 2m\varepsilon^2 = \ln\frac{2|\Hyp|}{\delta} \ \Longrightarrow\ \varepsilon = \sqrt{\frac{\ln|\Hyp| + \ln(2/\delta)}{2m}}

ce qui est l'équation (4). ∎ Renversée en , elle donne la complexité d'échantillon du cas agnostique fini :

m \ \ge\ \frac{\ln|\Hyp| + \ln(2/\delta)}{2\varepsilon^2}

(6)

C. Pourquoi l'ERM est presque optimal — le facteur 2

Place-toi sur l'événement, de probabilité , où (4) tient pour toutes les hypothèses. Note un minimiseur du risque réel dans . Alors :

R(\hat{h}_S) \ \underset{(4)}{\le}\ \hat{R}_S(\hat{h}_S) + \varepsilon \ \underset{\text{ERM}}{\le}\ \hat{R}_S(h^\star) + \varepsilon \ \underset{(4)}{\le}\ R(h^\star) + 2\varepsilon

∎ Trois inégalités, trois raisons différentes : la convergence uniforme, la définition même de l'ERM — c'est la seule ligne où l'algorithme intervient — puis à nouveau la convergence uniforme. Le facteur 2 est le prix de l'aller-retour , et il explique pourquoi la complexité d'échantillon agnostique est en : pour garantir d'excès de risque, il faut une convergence uniforme à .

D. Le cas réalisable, nettement moins cher

Si , l'ERM atteint . On n'a alors plus besoin d'un contrôle bilatéral : il suffit de majorer la probabilité qu'une mauvaise hypothèse — de risque — survive à exemples sans commettre une seule erreur. Pour une telle , la probabilité de tomber juste sur un exemple est au plus , donc sur exemples indépendants :

\Prob\big[\hat{R}_S(h) = 0\big] \le (1-\varepsilon)^m \le e^{-\varepsilon m}

Borne de l'union sur les mauvaises hypothèses, dont il y a au plus : . On égale à :

\boxed{\ m \ \ge\ \frac{\ln|\Hyp| + \ln(1/\delta)}{\varepsilon}\ }

(7)

∎ au lieu de : savoir que la vérité est dans la classe vaut un facteur sur le nombre d'exemples. À , c'est cent fois moins de données. C'est l'équation (7) qu'on déroule à la main au §4, et elle y tombe sur 100 exemples ronds.

La raison profonde est la variance : une variable de Bernoulli de moyenne a pour variance , qui s'effondre quand . Près de zéro, la concentration est bien meilleure que ne le dit Hoeffding, qui suppose le pire cas . Les inégalités de Bernstein et de Bennett formalisent ce gain et donnent les bornes dites optimistes, de la forme , qui interpolent proprement entre les deux régimes.

2.5 Le passage à l'infini : ce qui compte n'est pas le cardinal

L'équation (4) s'écroule dès que est infinie : . Or la classe des seuils sur est infinie, et personne ne doute qu'on puisse l'apprendre. La borne de l'union est donc trop grossière, et pour une raison précise : elle compte les hypothèses, alors que l'échantillon ne peut pas les distinguer toutes.

Voilà l'idée centrale de Vapnik et Chervonenkis4. Sur points fixés, deux hypothèses qui produisent le même vecteur d'étiquettes sont indiscernables : elles ont le même risque empirique. Ce qui compte n'est donc pas , mais le nombre de comportements distincts réalisables sur points.

Définitions — restriction, dichotomie, fonction de croissance, éclatement

Pour , la restriction de à est l'ensemble des vecteurs d'étiquettes réalisables :

\Hyp_C = \big\{ \big(h(x_1), \dots, h(x_m)\big) \ :\ h \in \Hyp \big\} \subseteq \{0,1\}^m

Chaque élément de s'appelle une dichotomie. La fonction de croissance (growth function) est le pire cas sur les configurations de points :

\Pi_{\Hyp}(m) \ =\ \max_{C \subset \mathcal{X},\ |C| = m} \big|\Hyp_C\big| \ \le\ 2^m

(8)

On dit que éclate (shatters) l'ensemble lorsque : toutes les manières d'étiqueter sont réalisables. Sur un ensemble éclaté, la classe reproduit n'importe quel étiquetage, y compris tiré à pile ou face — c'est l'étudiant qui récite les corrigés.

La bonne nouvelle : dans la borne de l'union, on pourra remplacer par , qui est fini même pour une classe infinie. Le prix à payer est une symétrisation — on compare l'échantillon à un second échantillon fantôme au lieu de le comparer à la distribution — et c'est le cœur technique de la théorie. La plongée du §2.9 la fait entièrement.

2.6 La VC-dimension

Définition — VC-dimension

La VC-dimension de , notée , est le cardinal du plus grand ensemble éclaté par :

d_{\mathrm{VC}}(\Hyp) \ =\ \max\big\{\, m \ :\ \Pi_{\Hyp}(m) = 2^m \,\big\} \qquad (= \infty \text{ si ce maximum n'existe pas})

(9)

Lire la définition dans le bon sens est capital. Elle contient un ∃ puis un ∀ :

⟺ il existe une configuration de points que la classe éclate. Une seule suffit : on la choisit, et on la choisit bien.
⟺ aucune configuration de points n'est éclatée. Là il faut un argument général, valable pour toutes les configurations.

Une borne inférieure se prouve par un exemple ; une borne supérieure exige une démonstration. C'est pourquoi tout calcul de VC se fait en deux temps.

Sept classes calculées, à connaître :

Classe			Paramètres
seuils		1	1
seuils, les deux orientations		2	1 + 1 bit
intervalles		2	2
demi-espaces
rectangles alignés aux axes	—	4	4
disques	—	3	3
sinusoïdes		∞	1

La dernière ligne tue l'idée que « VC = nombre de paramètres »

La classe a un seul paramètre réel et une VC-dimension infinie : pour tout , elle éclate points bien choisis. La plongée en donne la construction explicite, en trois lignes, avec les points .

La coïncidence pour les demi-espaces est vraie, et elle est trompeuse : elle vient de la linéarité, pas d'un comptage de paramètres. L'implication inverse existe aussi — un SVM à noyau RBF travaille dans un espace de dimension infinie et généralise très bien, parce que ce qui le contraint est la marge, pas la dimension (modules 4.3 et 4.5). Retiens : le nombre de paramètres n'est ni une borne supérieure, ni une borne inférieure de la VC-dimension. C'est un nombre sans rapport.

Les calculs de VC : demi-espaces (= n+1, par Radon) et la sinusoïde (= ∞, par construction)Niveau 2

A. Demi-espaces de avec terme constant :

La classe est . Deux inégalités à démontrer.

A.1 — Minoration : points éclatés (un exemple suffit)

Prends les points et pour (la base canonique, module 0.1). Soit un étiquetage quelconque . Choisis

\w = (y_1, \dots, y_n)\T, \qquad b = \frac{y_0}{2}

Vérification, point par point :

en : , du signe de ✓
en : . Comme , le signe est celui de ✓

Les étiquetages sont donc réalisables. ∎

A.2 — Majoration : aucun ensemble de points n'est éclaté

C'est le théorème de Radon : tout ensemble de points de se partitionne en deux sous-ensembles et dont les enveloppes convexes s'intersectent.

Démonstration. Soient . Les vecteurs augmentés sont au nombre de : ils sont linéairement dépendants (module 0.1). Il existe donc tel que

\sum_{k} \lambda_k \x_k = \mathbf{0} \qquad\text{et}\qquad \sum_{k} \lambda_k = 0

Pose et . Comme et , les deux ensembles sont non vides. Note . Alors

\mathbf{p} \ =\ \sum_{k \in I} \frac{\lambda_k}{\Lambda}\,\x_k \ =\ \sum_{k \in J} \frac{-\lambda_k}{\Lambda}\,\x_k

et les coefficients sont positifs de somme 1 des deux côtés : appartient à . ∎

Conclusion. Prends l'étiquetage sur , sur . Un demi-espace qui le réaliserait vérifierait sur et sur . Mais est affine, donc ses valeurs sur une enveloppe convexe sont les combinaisons convexes de ses valeurs aux sommets : en elle devrait être à la fois (vu depuis ) et (vu depuis ). Contradiction. ∎

Donc exactement. Sans terme constant — hyperplans passant par l'origine — la même démonstration donne .

Le comptage exact de Cover, que la démonstration vérifie

Pour points en position générale de , le nombre de dichotomies linéaires (terme constant compris) est connu exactement7 :

\big|\Hyp_C\big| \ =\ 2\sum_{i=0}^{n} \binom{m-1}{i}

(10)

En dimension 2 : pour 3 points (éclatés), pour 4 points sur 16 possibles, pour 5, pour 8. La démonstration du §7 énumère réellement les dichotomies, et son autotest les compare à cette formule. Attention au « position générale » : trois points alignés ne donnent que 6 dichotomies au lieu de 8 — l'étiquetage y est impossible. Cela ne change pas la VC-dimension, puisque la définition ne demande qu'une configuration éclatée ; mais cela montre que est bien un maximum sur les configurations, et non une valeur commune à toutes.

B. La sinusoïde : un paramètre, VC infinie

Soit . Montrons que pour tout , éclate points. Prends

x_i = 2^{-i}, \quad i = 1, \dots, m

et un étiquetage cible . Choisis

\omega \ =\ \pi\Big(1 + \sum_{j=1}^{m} b_j\, 2^{j}\Big)

(11)

Alors . Découpe la somme en trois morceaux :

: est un entier pair, donc ces termes ajoutent un multiple de à l'argument du sinus. Ils ne changent rien.
: le terme vaut , c'est-à-dire ou — un changement de signe commandé exactement par le bit .
: ces termes, avec le initial, forment avec .

Encadrons . D'une part . D'autre part, en majorant tous les par 1 : . Donc , et par conséquent . Il vient

\sin(\omega x_i) \ =\ \sin\big(\pi b_i + \pi t_i\big) \ =\ (-1)^{b_i}\,\sin(\pi t_i)

donc . En prenant les bits complémentaires de l'étiquetage voulu, on réalise n'importe quel étiquetage : les points sont éclatés, et ce pour tout . ∎

Ce qui se passe vraiment. Le paramètre est un réel : il contient une infinité de bits. La construction (11) ne fait que ranger l'étiquetage voulu dans les bits de , et se servir des comme d'une horloge qui les relit un par un. Un seul réel suffit à encoder une bibliothèque de corrigés. Une classe paramétrée par un réel n'est pas « une classe à un degré de liberté » : la dimension paramétrique et la capacité sont deux notions sans rapport, et c'est la seconde que mesure la VC-dimension.

Corollaire à garder pour la fin du module : ce n'est pas parce qu'un réseau a paramètres que sa VC-dimension vaut — elle pourrait être infinie, ou beaucoup plus petite. Il faut la calculer, et c'est un travail difficile12.

2.7 Le lemme de Sauer-Shelah : la transition de phase

La VC-dimension est définie comme un seuil ; le miracle est qu'elle contrôle toute la fonction de croissance, pas seulement son point de rupture.

Lemme de Sauer-Shelah

Si , alors pour tout :

\Pi_{\Hyp}(m) \ \le\ \sum_{i=0}^{d} \binom{m}{i} \qquad\text{et, pour } m \ge d \ge 1, \qquad \Pi_{\Hyp}(m) \ \le\ \Big(\frac{e\,m}{d}\Big)^{d}

(12)

Démontré indépendamment par Sauer6, par Shelah, et sous une autre forme par Vapnik et Chervonenkis4.

La seconde forme se déduit de la première en trois lignes, et c'est un joli calcul. Comme , on a pour tout , donc :

\Big(\frac{d}{m}\Big)^{d}\sum_{i=0}^{d}\binom{m}{i} \ \le\ \sum_{i=0}^{d}\binom{m}{i}\Big(\frac{d}{m}\Big)^{i} \ \le\ \sum_{i=0}^{m}\binom{m}{i}\Big(\frac{d}{m}\Big)^{i} \ =\ \Big(1 + \frac{d}{m}\Big)^{m} \ \le\ e^{d}

(binôme de Newton, puis ). On divise par et c'est fini. ∎

La transition de phase, et pourquoi elle sauve tout

Regarde ce que dit (12), des deux côtés du seuil :

: . La classe fait absolument tout ce qu'elle veut. Aucune information ne peut être extraite de l'échantillon.
: . La croissance devient polynomiale de degré .

Il n'y a rien entre les deux. Une fonction de croissance est soit identiquement , soit majorée par un polynôme — jamais , jamais . C'est une transition de phase, et c'est elle qui rend l'apprentissage possible : dans les bornes, intervient par son logarithme divisé par ,

\frac{\ln \Pi_{\Hyp}(m)}{m} \ \le\ \frac{d\,\ln(em/d)}{m} \ \xrightarrow[m \to \infty]{} \ 0

alors que ne tend vers rien du tout. VC finie ⟺ la borne s'éteint. Tout le théorème fondamental est déjà là.

Démonstration du lemme de Sauer-Shelah, par récurrence sur le nombre de pointsNiveau 3

On démontre un énoncé plus fort, dû à Pajor, dont Sauer-Shelah est un corollaire immédiat.

Lemme (Pajor). Pour toute classe et tout ensemble fini :

\big|\Hyp_C\big| \ \le\ \Big|\big\{\, B \subseteq C \ :\ \Hyp \text{ éclate } B \,\big\}\Big|

(13)

Pourquoi c'est plus fort. Si , aucun éclaté n'a plus de éléments. Le membre de droite est donc majoré par le nombre de sous-ensembles de de taille , soit . C'est (12). ∎

Démonstration de (13), par récurrence sur .

Initialisation : contient exactement le vecteur vide, donc ; et est toujours éclaté (vacuously), donc le membre de droite vaut 1 aussi. ✓

Hérédité. Soit et . Découpe selon ce qui se passe sur le dernier point. Note

Y_1 = \big\{\, \mathbf{v} \in \Hyp_{C'} \ :\ (\mathbf{v}, 0) \in \Hyp_C \ \text{ et } \ (\mathbf{v}, 1) \in \Hyp_C \,\big\}

l'ensemble des préfixes qui se prolongent des deux façons. Chaque élément de se prolonge d'au moins une façon, et ceux de se prolongent une fois de plus. D'où le comptage exact :

\big|\Hyp_C\big| \ =\ \big|\Hyp_{C'}\big| \ +\ \big|Y_1\big|

(14)

On traite les deux termes séparément.

Premier terme. Par hypothèse de récurrence appliquée à sur : . Ce sont exactement les sous-ensembles éclatés de qui ne contiennent pas .

Second terme. Introduis la classe , restreinte à : par construction . Or si éclate un , alors éclate — puisque chaque étiquetage de réalisable dans l'est dans avec les deux valeurs possibles en . L'hypothèse de récurrence appliquée à sur donne donc :

\big|Y_1\big| = \big|\Hyp'_{C'}\big| \ \le\ \#\{B \subseteq C' : \Hyp' \text{ éclate } B\} \ \le\ \#\{B \subseteq C' : \Hyp \text{ éclate } B \cup \{x_m\}\}

et ce sont exactement les sous-ensembles éclatés de qui contiennent .

Somme. En reportant dans (14), les deux familles sont disjointes et leur réunion est l'ensemble de tous les sous-ensembles éclatés de :

\big|\Hyp_C\big| \ \le\ \#\{B \subseteq C,\ x_m \notin B,\ \text{éclaté}\} + \#\{B \subseteq C,\ x_m \in B,\ \text{éclaté}\} \ =\ \#\{B \subseteq C \text{ éclaté}\}

∎ La démonstration est purement combinatoire : ni probabilité, ni géométrie. C'est ce qui explique que le lemme s'applique tel quel aux rectangles, aux réseaux de neurones et aux formules booléennes.

Le lemme est atteint. Pour la classe des intervalles (), et : les deux expressions sont égales pour tout . On le vérifie à la main au §4, sur et . Sauer-Shelah n'est donc pas améliorable en général.

2.8 La borne VC de généralisation

Voici le théorème vers lequel tout converge. Il remplace par dans la borne de l'union, au prix d'une symétrisation (le vient de l'échantillon fantôme) et de constantes moins fines.

Théorème de Vapnik-Chervonenkis

Pour toute classe , toute distribution et tout 4 :

\Prob_S\Big[\ \sup_{h \in \Hyp}\big|R(h) - \hat{R}_S(h)\big| \gt \varepsilon\ \Big] \ \le\ 4\,\Pi_{\Hyp}(2m)\,e^{-m\varepsilon^2/8}

(15)

En égalant à , puis en appliquant Sauer-Shelah :

\boxed{\ \text{avec probabilité} \ge 1-\delta,\ \forall h \in \Hyp : \quad R(h) \ \le\ \hat{R}_S(h) + \sqrt{\frac{8}{m}\Big(d\,\ln\frac{2em}{d} + \ln\frac{4}{\delta}\Big)}\ }

(16)

Compare (16) à (4) : est devenu . Le cardinal a disparu, la VC-dimension l'a remplacé, et tout le reste est identique — la racine, le , le . Toute la théorie tient dans ce remplacement. En ordre de grandeur, ce qu'il faut retenir :

R(h) \ \lesssim\ \hat{R}_S(h) \ +\ O\!\left(\sqrt{\frac{d\,\ln(m/d)}{m}}\right)

(17)

Le rapport d/m est le seul nombre qui compte — et la borne est souvent vide

À un logarithme près, l'écart de généralisation est piloté par : le seul nombre qui compte est le rapport , et pour garantir un écart il faut de l'ordre de — quelques exemples par unité de VC-dimension pour un écart grossier, quelques centaines pour un écart fin. C'est la version rigoureuse de la règle empirique « dix exemples par paramètre » — sauf que le bon numérateur est , pas le nombre de paramètres.

Maintenant les chiffres, sans complaisance. Prends la classe la plus simple qui soit infinie — les intervalles, — et . L'équation (16) donne :

: borne . Elle affirme , c'est-à-dire rien, puisqu'un risque est déjà .
Il faut pour qu'elle passe sous 1, et pour qu'elle descende à .
Pendant ce temps, l'écart réellement mesuré à vaut environ : la borne est 54 fois trop grande.

Ces trois nombres sont recalculés à la main au §4 et tracés en direct par la démonstration du §7. Une borne VC n'est pas un outil de dimensionnement. C'est un théorème de structure : il dit de quoi dépend la généralisation et comment — pas combien.

2.9 La complexité de Rademacher : mesurer la capacité sur tes données

La VC-dimension a deux défauts. Elle est combinatoire — elle ignore complètement la distribution des données — et elle est binaire : elle ne s'applique qu'à des classifieurs à valeurs dans . La complexité de Rademacher8 répare les deux, et elle répond directement à la question de l'intuition : à quel point cette classe sait-elle coller à du bruit pur ?

Définition — complexité de Rademacher

Soit une classe de fonctions et un échantillon. Tire signes indépendants, valant ou avec probabilité — les variables de Rademacher, du pile ou face pur. La complexité de Rademacher empirique et sa moyenne valent :

\hat{\mathfrak{R}}_S(\mathcal{F}) = \E_{\sigma}\left[\ \sup_{f \in \mathcal{F}}\ \frac{1}{m}\sum_{i=1}^{m}\sigma_i\, f(z_i)\ \right], \qquad \mathfrak{R}_m(\mathcal{F}) = \E_{S \sim \Data^m}\big[\hat{\mathfrak{R}}_S(\mathcal{F})\big]

(18)

Lecture. On tire des étiquettes au hasard et on demande à la classe de s'y ajuster du mieux qu'elle peut. La corrélation atteinte mesure exactement sa capacité de mémorisation. Pour une classe à valeurs : , et si et seulement si éclate — car pour chaque tirage de il existe alors avec , et le supremum vaut . Réciproquement, la restriction étant finie, une moyenne égale à 1 force chaque terme à valoir 1, donc chaque à être réalisé. La VC-dimension est le cas limite tout-ou-rien de Rademacher.

Théorème — la borne de Rademacher

Pour à valeurs dans et la perte 0-1, avec probabilité au moins , pour toute 8 9 :

R(h) \ \le\ \hat{R}_S(h) \ +\ \mathfrak{R}_m(\Hyp) \ +\ \sqrt{\frac{\ln(1/\delta)}{2m}}

(19)

et la version empirique, calculable sur tes propres données au prix d'un terme de concentration supplémentaire :

R(h) \ \le\ \hat{R}_S(h) \ +\ \hat{\mathfrak{R}}_S(\Hyp) \ +\ 3\sqrt{\frac{\ln(2/\delta)}{2m}}

(20)

Et le pont vers la VC-dimension se fait en une chaîne d'inégalités, chacune démontrée dans la plongée ci-dessous :

\mathfrak{R}_m(\Hyp) \ \underset{\text{Massart}}{\le}\ \sqrt{\frac{2\ln \Pi_{\Hyp}(m)}{m}} \ \underset{\text{Sauer}}{\le}\ \sqrt{\frac{2\,d\,\ln(em/d)}{m}}

(21)

Pourquoi Rademacher domine VC — cinq raisons, une seule décisive

La chaîne (21) est à sens unique. On peut toujours majorer par puis par : toute borne VC est une borne Rademacher affaiblie. L'inverse est faux.
Elle est mesurable. se calcule sur ton échantillon — l'algorithme est au §3, la démonstration du §7 le fait tourner. Une VC-dimension, elle, se démontre.
Elle voit la distribution. VC est un pire cas sur toutes les distributions ; Rademacher dépend de . Sur des données concentrées, la classe a beaucoup moins de latitude, et le sait.
Elle s'applique aux fonctions réelles et à toute perte bornée lipschitzienne — hinge, logistique, quadratique tronquée. VC ne sait faire que du binaire.
Le cas décisif : les classes à norme bornée. Pour avec , on démontre en quatre lignes que

\hat{\mathfrak{R}}_S(\Hyp_B) \ \le\ \frac{B\,R}{\sqrt{m}} \qquad\text{— sans aucune dépendance en la dimension } n

(22)

Or la même classe, non contrainte, a une VC-dimension de (hyperplans passant par l'origine — si on lui ajoute un terme constant). En dimension avec et , la borne VC exige des millions d'exemples ; la borne de Rademacher donne , soit à . C'est exactement la raison d'être de la marge, du SVM et de la régularisation — et l'un des rares endroits où la théorie explique une pratique. On y reviendra aux modules 2.3, 4.3 et 4.5.

Une précaution, et elle est essentielle. est une classe de fonctions réelles. Contraindre ne restreint pas le classifieur , qui est invariant par changement d'échelle : la classe des demi-espaces de norme bornée est la classe de tous les demi-espaces, et sa VC-dimension vaut toujours . On ne peut donc pas reporter (22) tel quel dans (19), qui suppose à valeurs . Le gain n'apparaît qu'en remplaçant la perte 0-1 par une perte de marge, lipschitzienne, à laquelle (22) se transmet par le lemme de contraction de Talagrand8 : c'est la charpente des bornes en marge des modules 4.3 et 4.5. Retiens la forme du résultat plutôt que la formule : ce qui contrôle est rapporté à la marge, jamais .

Symétrisation, McDiarmid, Massart : la borne de Rademacher démontrée, et pourquoi elle domine VCNiveau 3

Cinq étapes : les quatre premières s'assemblent à la fin pour donner (19) et (21) ; la cinquième est indépendante et démontre (22). On travaille sur la classe de pertes , à valeurs dans , et sur la quantité

\Phi(S) \ =\ \sup_{g \in \mathcal{G}} \Big(\E_{\Data}[g] - \hat{\E}_S[g]\Big) \qquad\text{avec}\qquad \hat{\E}_S[g] = \frac{1}{m}\sum_i g(z_i)

Majorer avec grande probabilité, c'est exactement obtenir une borne uniforme.

Étape 1 — Concentration : McDiarmid

Change un seul point de en . Comme , chaque bouge d'au plus ; un supremum de fonctions qui bougent toutes d'au plus bouge d'au plus . Donc : la fonction vérifie la condition des différences bornées avec . L'inégalité de McDiarmid donne alors

\Prob\big[\Phi(S) \ge \E[\Phi] + t\big] \ \le\ \exp\!\left(\frac{-2t^2}{\sum_i c_i^2}\right) = e^{-2mt^2}

soit, en posant le membre de droite égal à : avec probabilité . C'est le troisième terme de (19). Il reste à majorer .

Étape 2 — Symétrisation : l'échantillon fantôme

C'est l'idée de Vapnik et Chervonenkis, et la seule ligne vraiment astucieuse de toute la théorie. On ne sait pas manipuler , qui est un objet inconnu ; on le remplace par la moyenne sur un second échantillon , indépendant et de même loi — jamais observé, purement mathématique. Alors , et :

\E_S[\Phi] = \E_S\Big[\sup_g \E_{S'}\big[\hat{\E}_{S'}g - \hat{\E}_S g\big]\Big] \ \le\ \E_{S,S'}\Big[\sup_g \big(\hat{\E}_{S'}g - \hat{\E}_S g\big)\Big]

(un supremum d'espérances est majoré par l'espérance du supremum : c'est l'inégalité de Jensen appliquée à la fonction convexe « sup », module 1.1). Développons :

\E_S[\Phi] \ \le\ \E_{S,S'}\left[\sup_g \frac{1}{m}\sum_{i=1}^{m}\big(g(z_i') - g(z_i)\big)\right]

Le tour de passe-passe. et sont i.i.d. de même loi : échanger les deux ne change pas la loi jointe. Donc pour n'importe quel choix de signes , remplacer par laisse l'espérance inchangée. En particulier si les sont des variables de Rademacher indépendantes :

\E_S[\Phi] \ \le\ \E_{\sigma, S, S'}\left[\sup_g \frac{1}{m}\sum_{i}\sigma_i\big(g(z_i') - g(z_i)\big)\right] \ \le\ 2\,\E_{\sigma, S}\left[\sup_g \frac{1}{m}\sum_{i}\sigma_i\,g(z_i)\right] \ =\ 2\,\mathfrak{R}_m(\mathcal{G})

en séparant le sup de la somme en somme des sups, et en utilisant que a la même loi que . ∎ La distribution inconnue a disparu. Il ne reste qu'une quantité qui ne dépend que de la classe et de l'échantillon.

Étape 3 — De la classe de pertes à la classe d'hypothèses

Écris à valeurs dans ; alors , et donc :

\hat{\mathfrak{R}}_S(\mathcal{G}) = \E_\sigma\left[\sup_h \frac{1}{m}\sum_i \sigma_i \frac{1 - y_i h(x_i)}{2}\right] = \frac{1}{2}\,\E_\sigma\left[\sup_h \frac{1}{m}\sum_i (-\sigma_i y_i)\, h(x_i)\right] = \frac{1}{2}\,\hat{\mathfrak{R}}_S(\Hyp)

Le terme ne dépend pas de et sort du sup, d'espérance nulle. Et a exactement la même loi que , puisque . ∎

Le facteur de la symétrisation et le facteur d'ici se compensent : c'est pourquoi (19) porte et non .

Étape 4 — Le lemme de Massart : d'une classe finie à une racine de log

Lemme. Soit fini, de rayon . Alors

\E_\sigma\left[\max_{\mathbf{a} \in A} \langle \sigma, \mathbf{a}\rangle\right] \ \le\ \rho\,\sqrt{2\ln|A|}

(23)

Démonstration. Même schéma qu'à la plongée du §2.4 : exponentielle, majoration, optimisation. Pour , par convexité de l'exponentielle (Jensen) :

\exp\!\Big(\lambda\,\E_\sigma\big[\max_{\mathbf{a}} \langle \sigma, \mathbf{a}\rangle\big]\Big) \ \le\ \E_\sigma\Big[\max_{\mathbf{a}} e^{\lambda\langle \sigma, \mathbf{a}\rangle}\Big] \ \le\ \sum_{\mathbf{a} \in A} \E_\sigma\big[e^{\lambda\langle \sigma, \mathbf{a}\rangle}\big] \ =\ \sum_{\mathbf{a} \in A} \prod_{i=1}^{m}\cosh(\lambda a_i)

car . L'inégalité (comparaison des séries entières : ) donne . En prenant le logarithme :

\E_\sigma\big[\max_{\mathbf{a}} \langle \sigma, \mathbf{a}\rangle\big] \ \le\ \frac{\ln|A|}{\lambda} + \frac{\lambda \rho^2}{2}

Le membre de droite est minimal en et y vaut . ∎

Application. Pour à valeurs , prends : chaque vecteur a pour norme , et . Donc

\hat{\mathfrak{R}}_S(\Hyp) = \frac{1}{m}\E_\sigma\Big[\max_{\mathbf{a} \in \Hyp_S}\langle \sigma, \mathbf{a}\rangle\Big] \ \le\ \frac{\sqrt{m}\sqrt{2\ln \Pi_{\Hyp}(m)}}{m} \ =\ \sqrt{\frac{2\ln \Pi_{\Hyp}(m)}{m}}

ce qui est l'équation (21). ∎ En y injectant Sauer-Shelah on retombe sur une borne en : la voie Rademacher redonne la borne VC, à des constantes près, mais l'inverse est impossible. C'est en ce sens précis qu'elle la domine.

Étape 5 — Le calcul qui change tout : la classe linéaire à norme bornée

Soit et un échantillon avec . Alors :

\hat{\mathfrak{R}}_S(\Hyp_B) = \frac{1}{m}\E_\sigma\left[\sup_{\|\w\| \le B} \Big\langle \w,\ \sum_i \sigma_i \x_i \Big\rangle\right] = \frac{B}{m}\,\E_\sigma\left[\Big\|\sum_i \sigma_i \x_i\Big\|\right]

(cas d'égalité de Cauchy-Schwarz, module 0.1 : le meilleur est colinéaire à la somme). Puis Jensen, dans l'autre sens cette fois, parce que la racine est concave :

\E_\sigma\left[\Big\|\sum_i \sigma_i \x_i\Big\|\right] \ \le\ \sqrt{\E_\sigma\Big\|\sum_i \sigma_i \x_i\Big\|^2} \ =\ \sqrt{\sum_{i,j}\E[\sigma_i\sigma_j]\,\x_i\T\x_j} \ =\ \sqrt{\sum_i \|\x_i\|^2} \ \le\ R\sqrt{m}

car : tous les termes croisés s'annulent. D'où . ∎

Il n'y a pas de dans cette formule. On peut travailler en dimension un million, ou infinie (un noyau, module 4.5), sans que la borne bouge : ce qui contraint la classe est le produit , c'est-à-dire l'inverse de la marge. La VC-dimension, elle, valait et ne voyait rien de tout cela. C'est le premier endroit du cours où la théorie de l'apprentissage produit un résultat qu'un praticien peut utiliser : contraindre la norme des poids généralise, indépendamment du nombre de paramètres. La suite du cours (régularisation, SVM, weight decay) n'est qu'une exploitation de l'équation (22).

2.10 Le théorème fondamental de l'apprentissage statistique

Tout se recolle en un énoncé unique, qui referme le sujet pour la classification binaire à perte 0-1.

Théorème fondamental (classification binaire, perte 0-1)

Pour une classe de fonctions , les assertions suivantes sont équivalentes2 :

a la propriété de convergence uniforme ;
tout algorithme ERM est un apprenant PAC agnostique pour ;
est PAC-apprenable au sens agnostique ;
est PAC-apprenable (cas réalisable) ;
tout algorithme ERM est un apprenant PAC pour ;
.

Et la complexité d'échantillon est encadrée, à constantes universelles près :

m_{\Hyp}^{\text{agn}}(\varepsilon, \delta) = \Theta\!\left(\frac{d + \ln(1/\delta)}{\varepsilon^2}\right), \qquad m_{\Hyp}^{\text{réa}}(\varepsilon, \delta) = \Theta\!\left(\frac{d + \ln(1/\delta)}{\varepsilon}\right) \ \text{(à un } \ln(1/\varepsilon) \text{ près)}

(24)

Trois choses à comprendre dans cet énoncé, et elles sont fortes.

: la VC-dimension suffit. C'est tout le travail de Sauer-Shelah et de la symétrisation.
: elle est aussi nécessaire. Si éclate un ensemble de points, on construit une distribution uniforme sur telle que tout algorithme se trompe : il n'a vu que la moitié de et n'a strictement aucune information sur l'autre moitié, où peut tout faire. C'est le théorème du No Free Lunch du module 2.6, appliqué à un ensemble éclaté. VC infinie ⟹ pas d'apprentissage possible, quel que soit l'algorithme.
: l'ERM est optimal. Aucun algorithme ne fait mieux, en ordre de grandeur, que minimiser le risque empirique. Cela justifie a posteriori les quatre étapes : le pari du module 2.1 est le bon pari.

Le contraste entre les deux formules de (24) est la version chiffrée du compromis biais-complexité du module 2.2 : agrandir fait baisser (moins de biais) et monter (plus de données nécessaires). La minimisation du risque structurel (SRM) de Vapnik consiste à choisir explicitement dans une suite emboîtée en minimisant : c'est l'ancêtre théorique de la régularisation du module 2.3.

2.11 Et maintenant, l'honnêteté : ces bornes sont vides en apprentissage profond

Le résultat qui a fait vaciller la théorie

Zhang, Bengio, Hardt, Recht et Vinyals11 ont mené en 2017 une expérience élémentaire : entraîner des réseaux de vision standards sur CIFAR-10 et ImageNet, en remplaçant les étiquettes par des tirages aléatoires. Résultat : erreur d'entraînement nulle. Le réseau mémorise parfaitement des étiquettes qui n'ont aucun rapport avec les images — et il le fait aussi quand on remplace les pixels eux-mêmes par du bruit.

Traduit dans le langage de ce module : la classe éclate l'échantillon d'entraînement — au sens de l'estimation de Monte-Carlo du §3, la seule dont on dispose : chaque étiquetage tiré est réalisé exactement, donc sur tous les tirages essayés. Les équations (19) et (20) donnent alors : rien. Et le point vraiment gênant : le même réseau, le même algorithme, le même nombre de paramètres généralisent excellemment sur les vraies étiquettes. Aucune borne qui ne regarde que la classe ne peut distinguer ces deux situations, puisque la classe est identique. Le bloc scikit-learn du §5 reproduit ce résultat en dix lignes et quelques secondes.

Les chiffres, pour un ResNet-18 sur ImageNet

Bartlett, Harvey, Liaw et Mehrabian12 encadrent la VC-dimension d'un réseau ReLU à poids et couches entre et — d'où le « nearly-tight » du titre : les deux bornes ne se rejoignent qu'à un facteur logarithmique près. Pour un ResNet-18 (, ) l'ordre de grandeur est , soit près de 2 700 fois la taille d'ImageNet ().

Attention : l'équation (16) ne s'applique pas ici. Elle suppose — sans quoi Sauer-Shelah ne dit rien, et devient négatif. Avec la seule majoration disponible est la majoration triviale , qu'on reporte dans (15) :

\varepsilon = \sqrt{\frac{8}{m}\Big(2m\ln 2 + \ln\frac{4}{\delta}\Big)} \ \xrightarrow[m \gg 1]{}\ \sqrt{16\ln 2} = 3{,}33

borne . Elle affirme que l'erreur est au plus 333 %. Et remarque le pire : dans ce régime saturé, elle ne dépend même plus de . Ajouter des images ne la fait pas bouger d'un pouce.
il faut d'abord que dépasse pour que (16) reprenne la main. Ensuite seulement elle descend : il faudrait images pour qu'elle devienne simplement non vide, et pour qu'elle atteigne 10 %.

Pendant ce temps, l'écart réel entre l'erreur d'entraînement et l'erreur de test d'un ResNet-18 sur ImageNet se compte en quelques points. Chiffre le décalage dans la seule unité qui ait un sens, le nombre d'exemples : la théorie en réclame de l'ordre de fois trop. Ce n'est pas une constante à améliorer : c'est que la quantité mesurée n'est pas la bonne.

L'état de la question : pourquoi les réseaux profonds généralisent, et ce que la recherche sait vraimentNiveau 3

Cette plongée n'est pas une démonstration : c'est une carte du champ, à jour, avec ce qui est établi et ce qui ne l'est pas. Tu en auras besoin dès le monde 7.

A. Le diagnostic : ce qui casse exactement

La chaîne du module est : parce que convergence uniforme sur . Deux maillons peuvent lâcher.

est trop grande. C'est le constat de Zhang et al.11 : la classe des réseaux d'une architecture donnée éclate n'importe quel échantillon de taille réaliste. Toute borne uniforme sur cette classe est donc vide, par construction.
Mais l'algorithme n'explore pas . Le SGD, partant d'une initialisation donnée, n'atteint qu'une partie minuscule de . La quantité pertinente n'est pas la capacité de la classe, c'est celle de l'ensemble effectivement atteint par l'algorithme sur les données réelles. Autrement dit, la case 4 des quatre étapes, qu'on avait soigneusement mise de côté au début de ce module, revient par la fenêtre.

Le résultat le plus dérangeant est celui de Nagarajan et Kolter17 : ils construisent des situations où même en restreignant à l'ensemble atteint par le SGD, toute borne obtenue par convergence uniforme reste vide. Ce n'est donc pas seulement que nos bornes sont mauvaises : c'est que la méthode pourrait être structurellement incapable d'expliquer le phénomène.

B. Les quatre pistes actuelles

1. Marges et normes. Reprends l'équation (22) : ce qui contrôle une classe linéaire n'est pas sa dimension mais . Bartlett, Foster et Telgarsky13 transposent l'idée aux réseaux : la borne fait intervenir le produit des normes spectrales des matrices de poids, divisé par la marge des prédictions. Ces bornes ont deux qualités — elles ne dépendent pas explicitement du nombre de paramètres, et elles montent quand on entraîne sur des étiquettes aléatoires, donc elles distinguent enfin les deux expériences de Zhang. Elles restent numériquement vides sur les réseaux réels, mais elles corrèlent avec ce qu'on observe.

2. PAC-Bayes. On abandonne l'idée de borner un unique : on borne le risque moyen d'une distribution sur les hypothèses, et le terme de complexité devient , où est un a priori choisi avant de voir les données (module 0.6 pour la divergence, 0.5 pour l'a priori). Dziugaite et Roy14 ont obtenu ainsi, en 2017, la première borne non vide sur un réseau profond stochastique appliqué à MNIST : ils optimisent directement pour rendre la borne petite. C'est la voie d'où viennent, à ce jour, les rares bornes inférieures à 1 obtenues sur un réseau réel.

3. Stabilité algorithmique. Bousquet et Elisseeff15 contournent complètement la convergence uniforme : si l'algorithme est -uniformément stable — changer un exemple de change sa prédiction d'au plus — alors l'écart de généralisation attendu est majoré par , quelle que soit la classe. Hardt, Recht et Singer16 montrent que le SGD est stable si l'on ne fait pas trop d'époques, ce qui donne un « train faster, generalize better » quantitatif et explique en partie l'arrêt précoce (module 2.3). La limite : les analyses actuelles supposent la convexité ou des pas très petits.

4. Régularisation implicite et double descente. Le SGD ne choisit pas n'importe quel minimiseur du risque empirique : parmi tous ceux qui annulent l'erreur, il tend vers ceux de petite norme. Belkin, Hsu, Ma et Mandal18 ont mis en évidence la double descente : quand on augmente la capacité, l'erreur de test monte jusqu'au point d'interpolation (là où le modèle commence tout juste à annuler l'erreur d'entraînement) puis redescend au-delà. La courbe en U du compromis biais-variance du module 2.2 est donc le début d'une courbe qui en a deux. Rien dans ce module ne prévoit cela : les bornes sont monotones en .

C. Ce qu'un ingénieur doit en retenir

Ce que la théorie garantit vraiment : que la généralisation dépend d'une notion de capacité et de ; que cette capacité n'est pas le nombre de paramètres ; que contraindre les normes ou la marge aide indépendamment de la dimension ; et que sur un modèle de VC finie et connue — linéaire, SVM, arbre de profondeur bornée — les bornes sont utilisables comme ordre de grandeur.
Ce qu'elle ne garantit plus : rien de numérique sur un réseau profond. Une borne à 3,33 n'est pas une mauvaise note pour ton modèle, c'est une absence d'information.
Ce qui reste, et qui marche : l'inégalité de Hoeffding sur un jeu de test tenu à l'écart. Elle ne suppose rien de la classe, rien de l'algorithme, rien de la dimension — juste que a été fixée avant de regarder ce jeu. C'est l'objet du §6, et c'est la seule garantie que tu écriras dans un rapport de qualification.

§ 03

L'algorithme

Un module de théorie a quand même des algorithmes, et ce sont exactement ceux que fait tourner la démonstration du §7. Trois briques : mesurer la fonction de croissance sur une configuration donnée, énumérer exactement les dichotomies d'une classe linéaire, et estimer une complexité de Rademacher.

Fonction de croissance empirique et test d'éclatemententrée : k points x₁…x_k, une classe ℋ munie d'un oracle d'énumération — sortie : Π̂, éclaté ?, VC observée

D ← ∅ // l'ensemble des dichotomies rencontrées, stockées en masques de k bits
pour chaque hypothèse candidate h de la liste complète fournie par ℋ :
1. y ← (h(x₁), …, h(x_k)) // une évaluation, k appels
2. D ← D ∪ {y}
Π̂ ← |D|
retourner Π̂, (Π̂ = 2^k), et le plus grand k éclaté rencontré

Tout le travail est dans « la liste complète fournie par ℋ ». Il n'est jamais question de balayer un continuum de paramètres : pour chaque classe, un nombre fini de candidats suffit à réaliser toutes les dichotomies possibles. C'est le point technique du module, et il se règle classe par classe :

seuils : trie les points, prends entre deux points consécutifs, plus les deux extrêmes. Exactement candidats.
intervalles : les fenêtres de l'ordre trié, plus l'intervalle vide. On retrouve .
rectangles alignés : un sous-ensemble est réalisable si et seulement si sa boîte englobante ne contient aucun point hors de . Test direct sur les sous-ensembles, en .
classes linéaires : c'est le cas intéressant, et il occupe l'algorithme suivant.

Deux classes de la démonstration sont linéaires après relèvement : donne les demi-plans (), et donne les frontières circulaires — intérieur ou extérieur d'un cercle (), puisque est affine dans ces variables. C'est déjà l'astuce du noyau du module 4.5, utilisée ici pour compter au lieu de classer.

Énumération exacte des dichotomies d'une classe linéaireentrée : Φ = (φ(x₁); … ; φ(x_k)) ∈ ℝ^{k×p}, lignes normalisées — sortie : TOUTES les dichotomies réalisables

// Chaque point définit un hyperplan {θ : θᵀφ(xᵢ) = 0} de ℝᵖ passant par 0.
// Les dichotomies sont EXACTEMENT les cellules de cet arrangement.
D ← ∅
pour chaque sous-ensemble J de {1…k} de taille p − 1 :
1. v ← vecteur unitaire du noyau de Φ_J // développement par cofacteurs : une arête de l'arrangement
2. si v n'existe pas, ou si Φ_l · v ≈ 0 pour un l ∉ J : continuer // configuration dégénérée
3. pour côté ∈ {+1, −1} // les deux sommets antipodaux sur la sphère
  1. pour chaque s ∈ {0,1}^{p−1} // les 2^{p−1} cellules autour du sommet
    1. y_j ← s_j pour j ∈ J // libre : on est exactement sur ces hyperplans
    2. y_l ← 𝟙[côté · (Φ_l · v) > 0] pour l ∉ J // imposé : le signe ne bascule pas
    3. D ← D ∪ {y}
retourner D

Pourquoi c'est exact. Les hyperplans découpent la sphère unité de en cellules, et deux d'une même cellule donnent la même dichotomie. Dès que les engendrent , chaque cellule est un cône pointé : elle possède des arêtes extrêmes, et une arête est l'intersection de hyperplans — c'est le vecteur . En balayant les combinaisons de signes autour de et de , on visite toutes les cellules qui touchent cette arête ; en balayant tous les , on les visite toutes. Aucune dichotomie n'est manquée, aucune n'est inventée. L'autotest de la démonstration vérifie le résultat contre la formule exacte de Cover7, équation (10).

La réserve, et elle est réelle. Ce raisonnement suppose la position générale : que les vecteurs de soient indépendants et qu'aucun autre ne soit orthogonal à . Sinon la ligne 4.2 saute ce , et si tous les sont dégénérés — c'est exactement le cas de trois points alignés — l'énumération ne rend plus rien. La démonstration du §7 complète donc par un balayage déterministe de 2 200 directions tirées à graine fixée : chaque direction produit une dichotomie authentiquement réalisable, donc ce filet n'invente jamais rien, mais il pourrait en principe manquer une cellule très mince. C'est le seul endroit du module où l'on n'a pas de garantie d'exactitude, et il ne concerne que les configurations dégénérées.

Complexité. candidats, chacun lu en , plus le calcul de en par cofacteurs — soit au total. Pour les demi-plans () c'est : instantané jusqu'à , taille au-delà de laquelle l'affichage des dichotomies n'a de toute façon plus de sens. À comparer au test naïf, qui résoudrait programmes linéaires de faisabilité.

Complexité de Rademacher empiriqueentrée : S = (x₁…x_m), classe ℋ, nombre de tirages T — sortie : estimation de R̂_S(ℋ)

s ← 0
répéter T fois :
1. σ ← m signes ±1 indépendants, équiprobables // du bruit pur, aucune structure
2. c ← max_{h ∈ ℋ} (1/m) Σᵢ σᵢ h(xᵢ) // UN PROBLÈME D'APPRENTISSAGE : l'ERM sur des étiquettes de pile ou face
3. s ← s + c
retourner s / T

La ligne 2.2 mérite qu'on s'y arrête : calculer une complexité de Rademacher, c'est entraîner un modèle sur du bruit. Pas une analogie, la même opération. Pour les intervalles, ce maximum se calcule exactement en : après tri des , maximiser est le problème du sous-tableau de somme maximale, que l'algorithme de Kadane résout en une passe. Le coût total est , et l'erreur de Monte-Carlo décroît en .

Pour un réseau de neurones, ce même maximum n'a pas de solution exacte — mais l'entraîner sur des étiquettes aléatoires en donne une borne inférieure, et c'est précisément l'expérience de Zhang et al.11 Quand l'erreur d'entraînement tombe à zéro sur du bruit, la borne inférieure vaut 1 : on n'a pas besoin d'aller plus loin pour savoir que l'équation (20) ne dira rien.

§ 04

L'exemple à la main

Trois calculs, dans l'ordre : la fonction de croissance des intervalles sur quatre points, la complexité d'échantillon du cas fini, et la borne VC. Chacun finit par une ligne de vérification. Aucune calculatrice n'est nécessaire pour le premier ; les deux autres ne demandent que quatre logarithmes.

4.1 La fonction de croissance des intervalles, par énumération

Quatre points sur : , , , . Classe : . Une dichotomie est réalisable si et seulement si l'ensemble des points positifs est un bloc contigu de l'ordre trié — un intervalle ne peut pas sauter un point.

Taille du bloc	Ensembles positifs réalisables	Témoin	Nombre
0	∅	[10, 11]	1
1	{1} · {2} · {4} · {7}	[0,5 ; 1,5] etc.	4
2	{1,2} · {2,4} · {4,7}	[0,5 ; 3] etc.	3
3	{1,2,4} · {2,4,7}	[0,5 ; 5] et [1,5 ; 8]	2
4	{1,2,4,7}	[0, 8]	1
Total réalisable			11
—	Impossibles : {1,4} · {1,7} · {2,7} · {1,2,7} · {1,4,7}	bloc non contigu	5
Contrôle : 11 + 5			16 = 2⁴ ✓

Donc : quatre points ne sont jamais éclatés. Le comptage ne dépend que de l'ordre des points, donc le résultat vaut pour toute configuration de quatre points, ce qui est exactement ce qu'exige la définition. Redescendons :

	blocs contigus		éclaté ?	Sauer
1	1 + 1 = 2	2	oui	1 + 1 = 2 ✓
2	3 + 1 = 4	4	oui	1 + 2 + 1 = 4 ✓
3	6 + 1 = 7	8	non	1 + 3 + 3 = 7 ✓
4	10 + 1 = 11	16	non	1 + 4 + 6 = 11 ✓
Vérification 1 — , et la borne de Sauer-Shelah est atteinte exactement pour tout : la colonne 2 et la colonne 5 sont égales, ligne par ligne.

Le lemme de Sauer-Shelah n'est donc pas améliorable : il existe des classes qui l'atteignent, et les intervalles en font partie. On retiendra aussi la lecture inverse : des étiquetages sont réalisables à , mais seulement à , à … La proportion s'effondre, et c'est tout ce dont on a besoin.

4.2 Combien d'exemples ? Le cas fini, cas réalisable

On discrétise : un capteur rend un entier sur 10 bits, et la classe est l'ensemble des seuils sur cette grille, soit hypothèses. On veut et , et l'on sait que la vérité est un seuil (cas réalisable). L'équation (7) donne :

Terme	Calcul	Valeur
	10 · ln 2 = 10 · 0,693147	6,9315
	ln 20 = ln 2 + ln 10	2,9957
somme	6,9315 + 2,9957	9,9272
÷	9,9272 / 0,10	99,27
complexité d'échantillon	arrondi supérieur	m = 100

Cent exemples suffisent pour garantir, à 95 %, une erreur inférieure à 10 %, sur une classe de mille hypothèses. Fais bouger les trois paramètres, un à un, et lis les asymétries — c'est là que tout se joue :

Modification	Nouveau calcul	Nouveau	Coût
référence	(6,9315 + 2,9957) / 0,10	100	—
doublé (2048)	(7,6246 + 2,9957) / 0,10 = 106,2	107	+7 exemples
× 1024 (2²⁰)	(13,8629 + 2,9957) / 0,10 = 168,6	169	+69 exemples
: 0,05 → 0,01	(6,9315 + 4,6052) / 0,10 = 115,4	116	+16 exemples
: 0,10 → 0,05	9,9272 / 0,05 = 198,5	199	×2

La leçon des deux lignes en évidence

Multiplier la classe par 1024 coûte 69 exemples ; diviser par deux coûte le double de tout. La complexité est logarithmique en la richesse du modèle et linéaire (agnostique : quadratique) en la précision demandée. C'est pourquoi on peut se permettre des modèles énormes, et pourquoi les derniers points de pourcentage coûtent si cher.

Vérification 2 — le prix de l'agnosticisme. Aux mêmes , , , mais sans supposer la vérité dans la classe, l'équation (4) donne :

\varepsilon = \sqrt{\frac{\ln(2 \cdot 1024 / 0{,}05)}{2 \cdot 100}} = \sqrt{\frac{\ln 40\,960}{200}} = \sqrt{\frac{10{,}6204}{200}} = \sqrt{0{,}053102} = 0{,}2304

La garantie passe de ±10 % à ±23 % pour le même jeu de données, uniquement parce qu'on ne sait plus si la vérité est dans la classe. C'est le facteur contre de la plongée du §2.4, vu de l'autre côté.

4.3 La borne VC sur ces mêmes intervalles — et sa vacuité

Repartons de la classe infinie des intervalles, dont on vient d'établir . Applique l'équation (16) avec et :

Terme	Calcul	Valeur
	2 · 2,71828 · 100 / 2 = 100 e	271,83
	ln 100 + 1 = 4,60517 + 1	5,6052
	2 · 5,6052	11,2103
	ln 80	4,3820
somme	11,2103 + 4,3820	15,5924
× 8/m	15,5924 · 0,08	1,2474
borne	√1,2474	1,117

Vérification 3 — la borne est vide, et de très loin

La borne affirme . Comme un risque est par définition inférieur à 1, elle n'apporte aucune information. Il faut pour qu'elle passe sous 1, et pour qu'elle descende à 0,1.

Or l'écart réellement mesuré sur cette classe, à et avec 10 % de bruit d'étiquettes, vaut — c'est la sortie du bloc NumPy du §5, moyennée sur 400 tirages ; la démonstration du §7, qui refait l'expérience avec ses propres tirages, affiche . Le rapport est de : la borne est 54 fois trop grande sur la classe la plus simple qui soit.

Retiens ce chiffre. Si la théorie se trompe d'un facteur 54 sur les intervalles, l'idée qu'elle puisse dimensionner un réseau de neurones est à abandonner tout de suite. Pire : le rapport ne se referme pas quand grandit, il s'ouvre. La borne décroît en , alors que l'écart mesuré décroît ici presque en — c'est le régime rapide, celui des problèmes dont le bruit reste franchement écarté de (ici , condition dite de Massart), et que Hoeffding ne sait pas voir parce qu'il suppose une variance de pire cas. Le tableau du §5 le montre ligne à ligne : l'écart passe de à à à , soit exactement dix fois moins pour dix fois plus de données ; le rapport à la borne, lui, monte de 54 à 183. Ce que la borne capture correctement, c'est la dépendance en et la forme ; ce qu'elle rate, c'est à la fois l'échelle et l'exposant.

§ 05

Le code

import numpy as np
from itertools import combinations, product
from math import comb

# --- 1. Dataset : k points du plan, en position generale --------------------
P = np.array([[-1.6, 0.9], [0.4, 1.4], [1.5, -0.2], [-0.7, -1.3], [0.9, -1.6]])

# --- 2. Modele : chaque classe rend l'ENSEMBLE des etiquetages realisables --
def dich_seuils(P):                       # h(x) = 1[x1 > a]
    o = np.argsort(P[:, 0]); k = len(P); out = set()
    for c in range(k + 1):                # c points a droite du seuil
        lab = [0] * k
        for t in range(k - c, k): lab[o[t]] = 1
        out.add(tuple(lab))
    return out

def dich_intervalles(P):                  # h(x) = 1[a <= x1 <= b]
    o = np.argsort(P[:, 0]); k = len(P); out = {tuple([0] * k)}
    for i in range(k):
        for j in range(i, k):
            lab = [0] * k
            for t in range(i, j + 1): lab[o[t]] = 1
            out.add(tuple(lab))
    return out

def dich_rectangles(P):                   # h(x) = 1[x dans une boite alignee]
    k = len(P); out = set()
    for S in product((0, 1), repeat=k):
        dedans = [i for i in range(k) if S[i]]
        if not dedans: out.add(S); continue
        lo, hi = P[dedans].min(0), P[dedans].max(0)
        if all(not np.all((P[j] >= lo) & (P[j] <= hi)) for j in range(k) if not S[j]):
            out.add(S)
    return out

def dich_lineaires(Phi):
    """Tous les etiquetages realisables par sign(theta . phi(x)), theta libre.
       Enumeration EXACTE des cellules de l'arrangement des k hyperplans de R^p :
       chaque cellule touche un sommet, intersection de p-1 hyperplans."""
    k, p = Phi.shape
    if k <= p and np.linalg.matrix_rank(Phi) == k:
        return set(product((0, 1), repeat=k))          # tout est realisable
    out = set()
    for J in combinations(range(k), p - 1):
        A = Phi[list(J)]
        v = np.array([(-1) ** i * np.linalg.det(np.delete(A, i, axis=1)) for i in range(p)])
        if np.linalg.norm(v) < 1e-12: continue
        r = Phi @ v
        autres = [l for l in range(k) if l not in J]
        if min(abs(r[l]) for l in autres) < 1e-9: continue   # configuration degeneree
        for cote in (1.0, -1.0):                       # les DEUX sommets antipodaux
            for s in product((0, 1), repeat=p - 1):
                lab = [0] * k
                for idx, j in enumerate(J): lab[j] = s[idx]
                for l in autres: lab[l] = 1 if cote * r[l] > 0 else 0
                out.add(tuple(lab))
    return out

def dich_demiplans(P): return dich_lineaires(np.hstack([P, np.ones((len(P), 1))]))
def dich_cercles(P):
    return dich_lineaires(np.hstack([P, (P ** 2).sum(1, keepdims=True), np.ones((len(P), 1))]))

CLASSES = {'seuils': dich_seuils, 'intervalles': dich_intervalles,
           'demi-plans': dich_demiplans, 'rectangles': dich_rectangles,
           'cercles': dich_cercles}

# --- 3. Fonction de croissance et eclatement --------------------------------
print("Pi_H(k) sur CETTE configuration de points")
print(f"{'k':>2} {'2^k':>5} " + " ".join(f"{n:>11}" for n in CLASSES))
for k in range(1, 6):
    ligne = [f"{k:>2} {2**k:>5}"]
    for nom, f in CLASSES.items():
        n = len(f(P[:k]))
        ligne.append(f"{n:>10}{'*' if n == 2**k else ' '}")
    print(" ".join(ligne))
print("(* = les k points sont eclates)")
#  k   2^k      seuils intervalles  demi-plans  rectangles     cercles
#  1     2          2*          2*          2*          2*          2*
#  2     4          3           4*          4*          4*          4*
#  3     8          4           7           8*          8*          8*
#  4    16          5          11          14          16*         16*
#  5    32          6          16          22          28          30

# --- 4. Verification : Cover pour les classes lineaires, Sauer partout ------
def cover(k, p): return 2 * sum(comb(k - 1, i) for i in range(p))
print("Cover  demi-plans (p=3) :", [cover(k, 3) for k in range(1, 6)])
print("Cover  cercles    (p=4) :", [cover(k, 4) for k in range(1, 6)])
print("Sauer  d=2, k=4         :", sum(comb(4, i) for i in range(3)),
      " | intervalles mesure :", len(dich_intervalles(P[:4])))
# Cover  demi-plans (p=3) : [2, 4, 8, 14, 22]
# Cover  cercles    (p=4) : [2, 4, 8, 16, 30]
# Sauer  d=2, k=4         : 11  | intervalles mesure : 11

import numpy as np
from math import log, sqrt, e

A, B, ETA, DELTA, D_VC = 0.3, 0.7, 0.10, 0.05, 2      # concept cible, bruit, risque, VC
NREP = 400                                            # tirages independants par valeur de m

# --- 1. Dataset : x uniforme, y = 1[x dans [A,B]] retourne avec proba ETA ---
def tirage(m, rng):
    x = rng.random(m)
    y = ((x >= A) & (x <= B)).astype(int)
    flip = rng.random(m) < ETA
    return x, np.where(flip, 1 - y, y), flip.mean()    # on retient le bruit REELLEMENT tire

# --- 2. Modele + 4. Minimisation : ERM exact sur les intervalles ------------
# Minimiser le nombre d'erreurs = maximiser (positifs dedans - negatifs dedans).
# Apres tri, c'est le sous-tableau de somme maximale (Kadane), en O(m log m).
def erm_intervalle(x, y):
    o = np.argsort(x); xs, ys = x[o], y[o]; m = len(x)
    v = np.where(ys == 1, 1, -1)
    best = cur = 0; deb = fin = -1; s = 0
    for j in range(m):
        cur, s = (v[j], j) if cur <= 0 else (cur + v[j], s)
        if cur > best: best, deb, fin = cur, s, j
    Rhat = (int(ys.sum()) - best) / m                  # 3. Fonction cout : erreur 0-1
    if deb < 0: return 0.0, 0.0, Rhat
    a = 0.0 if deb == 0 else 0.5 * (xs[deb - 1] + xs[deb])
    b = 1.0 if fin == m - 1 else 0.5 * (xs[fin] + xs[fin + 1])
    return a, b, Rhat

# Risque REEL, en forme close : aucun jeu de test n'est necessaire.
def risque(a, b):
    inter = max(0.0, min(b, B) - max(a, A))
    dsym = (b - a) + (B - A) - 2 * inter               # mesure de la difference symetrique
    return dsym * (1 - ETA) + (1 - dsym) * ETA

# --- Les bornes -------------------------------------------------------------
def borne_vc(m, d=D_VC):                               # Vapnik-Chervonenkis + Sauer
    lnPi = 2 * m * log(2)                              # majoration triviale : Pi(2m) <= 2^(2m)
    # (2em/d)^d ne majore Pi(2m) QUE si 2m >= d -- c'est l'hypothese de
    # l'equation (12). Au-dela, la classe eclate les 2m points, Pi(2m) vaut
    # exactement 2^(2m), et (2em/d)^d lui passe dessous : l'appliquer donnerait
    # une borne fausse, plus petite que la verite. C'est le regime sature du
    # deep learning, ou seule la majoration triviale subsiste.
    if 2 * m >= d: lnPi = min(lnPi, d * log(2 * e * m / d))
    return sqrt(8 / m * (lnPi + log(4 / DELTA)))

def borne_rademacher(m):                               # Massart + Pi exact des intervalles
    return sqrt(2 * log(m * (m + 1) / 2 + 1) / m) + sqrt(log(1 / DELTA) / (2 * m))

def rademacher_empirique(x, nrep, rng):                # le VRAI calcul : sup de la correlation
    o = np.argsort(x); m = len(x); tot = 0.0
    for _ in range(nrep):
        s = (rng.integers(0, 2, m) * 2 - 1)[o]
        best = cur = 0
        for j in range(m):
            cur = max(s[j], cur + s[j]); best = max(best, cur)
        tot += (2 * best - s.sum()) / m                # h vaut +-1 : somme = 2*dedans - total
    return tot / nrep

print(f"{'m':>6} {'R^(h^)':>8} {'R(h^)':>8} {'ecart':>8} {'Rad.emp':>8} {'b.Rad':>8} {'b.VC':>8}")
for m in (10, 30, 100, 300, 1000, 3000):
    rng = np.random.default_rng(7)
    Rh, R = [], []
    for _ in range(NREP):
        x, y, eta_tire = tirage(m, rng)
        a, b, rh = erm_intervalle(x, y)
        # Variable de controle. Le bruit de Monte-Carlo sur R^ est presque
        # entierement celui du taux d'etiquettes retournees, dont l'esperance
        # vaut exactement ETA : on recentre R^ dessus. Meme esperance, variance
        # divisee par 10 a m = 3000, et l'ecart devient positif tirage par
        # tirage. Sans cela, 400 tirages ne mesurent pas un ecart de 7e-4.
        Rh.append(rh + ETA - eta_tire); R.append(risque(a, b))
    xr = np.random.default_rng(11).random(m)
    print(f"{m:>6} {np.mean(Rh):>8.4f} {np.mean(R):>8.4f} {np.mean(R) - np.mean(Rh):>8.4f} "
          f"{rademacher_empirique(xr, 60, np.random.default_rng(11)):>8.4f} "
          f"{borne_rademacher(m):>8.4f} {borne_vc(m):>8.4f}")
#      m   R^(h^)    R(h^)    ecart  Rad.emp    b.Rad     b.VC
#     10   0.0515   0.2307   0.1792   0.6300   1.2843   2.9648
#     30   0.0833   0.1512   0.0678   0.3878   0.8635   1.8751
#    100   0.0954   0.1163   0.0208   0.2360   0.5354   1.1169
#    300   0.0984   0.1057   0.0073   0.1367   0.3380   0.6888
#   1000   0.0995   0.1016   0.0022   0.0726   0.2007   0.4020
#   3000   0.0998   0.1006   0.0008   0.0437   0.1234   0.2444

print("Risque de Bayes = ETA =", ETA, "-> l'ecart tend vers 0, pas le risque.")
print("A m = 100 : borne VC =", round(borne_vc(100), 3), "-> elle affirme R <= 1, donc RIEN.")
print("ResNet-18, d_VC ~ 3.2e9, m = 1.2e6 (ImageNet) : borne =",
      round(borne_vc(1_200_000, 3.21e9), 3))
# Risque de Bayes = ETA = 0.1 -> l'ecart tend vers 0, pas le risque.
# A m = 100 : borne VC = 1.117 -> elle affirme R <= 1, donc RIEN.
# ResNet-18, d_VC ~ 3.2e9, m = 1.2e6 (ImageNet) : borne = 3.33

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

# --- Dataset : 20 variables, 2 classes, 600 exemples ------------------------
X, y = make_classification(n_samples=600, n_features=20, n_informative=8,
                           n_redundant=0, class_sep=1.4, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=0)

# Le MEME jeu, avec des etiquettes tirees a pile ou face (Zhang et al. 2017)
rng = np.random.default_rng(0)
ytr_alea = rng.integers(0, 2, len(ytr))
yte_alea = rng.integers(0, 2, len(yte))

# --- Modele a grande capacite : noyau RBF, marge dure -----------------------
def essai(nom, ytr_, yte_):
    clf = SVC(kernel='rbf', C=1e6, gamma=0.05).fit(Xtr, ytr_)
    tr, te = clf.score(Xtr, ytr_), clf.score(Xte, yte_)
    print(f"{nom:22s} exactitude apprentissage = {tr:.3f}   test = {te:.3f}   "
          f"vecteurs de support = {clf.n_support_.sum():3d}")

essai("etiquettes vraies", ytr, yte)
essai("etiquettes aleatoires", ytr_alea, yte_alea)
# etiquettes vraies      exactitude apprentissage = 1.000   test = 0.977   vecteurs de support = 187
# etiquettes aleatoires  exactitude apprentissage = 1.000   test = 0.507   vecteurs de support = 295

# Le modele memorise 300 etiquettes de pile ou face. Et ce n'est pas une
# extrapolation a partir d'un seul tirage : la matrice de Gram du noyau RBF sur des
# points DISTINCTS est definie positive, donc TOUT etiquetage +-1 y est separable a
# marge dure. La classe eclate litteralement ces 300 points, elle realise les 2^300
# etiquetages, sa complexite de Rademacher empirique vaut exactement 1, et
# l'equation (20) devient R <= 0 + 1 + ... : vide.
# Meme architecture, meme algorithme, meme capacite -> generalisation excellente
# dans un cas, nulle dans l'autre. Aucune borne fondee sur la SEULE classe H ne
# peut distinguer ces deux lignes.

% --- 1. Dimensionner le plan de validation d'un detecteur de defaut --------
% Hoeffding sur une hypothese FIXEE, evaluee sur m exemples frais :
% |R - Rtest| <= eps avec proba 1 - delta des que m >= ln(2/delta)/(2 eps^2).
delta = 0.05;
eps_t = [0.05 0.02 0.01 0.005];
m_req = ceil(log(2/delta) ./ (2*eps_t.^2));
fprintf('eps = %.3f  ->  m_test = %6d\n', [eps_t; m_req]);
% eps = 0.050  ->  m_test =    738
% eps = 0.020  ->  m_test =   4612
% eps = 0.010  ->  m_test =  18445
% eps = 0.005  ->  m_test =  73778

% --- 2. Le prix de la reutilisation du jeu de test -------------------------
% Comparer k modeles sur le MEME jeu de test = une borne de l'union sur k.
kk    = [1 5 20 100];
m_k   = ceil(log(2*kk/delta) ./ (2*0.01^2));
fprintf('k = %3d modeles  ->  m_test = %6d\n', [kk; m_k]);
% k =   1 modeles  ->  m_test =  18445
% k =   5 modeles  ->  m_test =  26492
% k =  20 modeles  ->  m_test =  33424
% k = 100 modeles  ->  m_test =  41471

% --- 3. La borne VC sur l'APPRENTISSAGE, pour comparaison ------------------
% Classifieur lineaire sur 2 descripteurs spectraux + biais : d_VC = 3.
d = 3;
for m = [200 1000 5000]
    b = sqrt(8/m * (d*log(2*exp(1)*m/d) + log(4/delta)));
    fprintf('m = %5d  ->  borne VC = %.4f\n', m, b);
end
% m =   200  ->  borne VC = 0.9394
% m =  1000  ->  borne VC = 0.4638
% m =  5000  ->  borne VC = 0.2253

% --- 4. Verification : le comptage exact de Cover (equation 10) ------------
for kk = 1:8
    C = 2*sum(arrayfun(@(i) nchoosek(kk-1,i), 0:min(2,kk-1)));
    fprintf('k = %d : %3d dichotomies lineaires sur 2^%d = %3d\n', kk, C, kk, 2^kk);
end
% k = 1 :   2 dichotomies lineaires sur 2^1 =   2
% k = 2 :   4 dichotomies lineaires sur 2^2 =   4
% k = 3 :   8 dichotomies lineaires sur 2^3 =   8    <- eclatement, d_VC >= 3
% k = 4 :  14 dichotomies lineaires sur 2^4 =  16    <- plus jamais eclate
% k = 5 :  22 dichotomies lineaires sur 2^5 =  32
% k = 6 :  32 dichotomies lineaires sur 2^6 =  64
% k = 7 :  44 dichotomies lineaires sur 2^7 = 128
% k = 8 :  58 dichotomies lineaires sur 2^8 = 256

Les trois blocs Python tournent tels quels avec NumPy (et scikit-learn pour le troisième) et affichent exactement les valeurs commentées. Le premier reproduit les comptages de Cover et de Sauer ; le deuxième reproduit les trois vérifications du §4 ; le troisième est l'expérience de Zhang et al. en dix lignes.

§ 06

L'application réelle

6.1 Qualifier un détecteur de défaut de roulement

Ligne de production, contrôle de fin de chaîne. Un accéléromètre sur le palier, une acquisition de deux secondes, deux descripteurs extraits du spectre d'enveloppe — l'énergie dans la bande BPFO et le kurtosis (modules 11.1 et 11.7). Un classifieur linéaire sur ces deux descripteurs : . Tu as réussi à étiqueter pièces, ce qui a demandé de démonter 200 paliers. Le classifieur affiche .

Le service qualité veut une phrase dans le rapport de qualification. Applique l'équation (16) : la borne VC vaut 0,939. Elle autorise donc un risque réel allant jusqu'à . Inutilisable. Et ce n'est pas la faute du modèle : c'est le plus petit modèle non trivial qui existe.

6.2 Ce qui marche : Hoeffding sur un jeu de test

Change de question. Ne cherche pas à borner le risque de toute la classe : borne celui du classifieur que tu as, une fois pour toutes, figé. Il est alors fixé avant le tirage du jeu de test, et l'équation (2) s'applique exactement, sans convergence uniforme, sans VC-dimension, sans borne de l'union :

m_{\text{test}} \ \ge\ \frac{\ln(2/\delta)}{2\varepsilon^2} \qquad\Longrightarrow\qquad \big|R(h) - \hat{R}_{\text{test}}(h)\big| \le \varepsilon \ \text{ avec probabilité } 1-\delta

(25)

Garantie voulue à 95 % ()	Calcul	Pièces à tester
points	ln 40 / (2 · 0,05²) = 3,6889 / 0,005	738
points	3,6889 / 0,0008	4 612
point	3,6889 / 0,0002	18 445
point	3,6889 / 0,00005	73 778

Le seul chiffre du module qu'on écrit dans un rapport

Regarde ce qui n'apparaît pas dans l'équation (25) : ni la classe d'hypothèses, ni la VC-dimension, ni le nombre de paramètres, ni la dimension des descripteurs, ni l'algorithme d'apprentissage. Un classifieur linéaire et un ResNet-50 demandent exactement le même jeu de test pour la même garantie.

C'est le renversement complet du module : la théorie de la convergence uniforme, qui coûte si cher, ne sert qu'à borner le risque d'un modèle choisi sur les données d'entraînement. Dès qu'on accepte de payer des données supplémentaires — jamais vues, jamais utilisées pour choisir quoi que ce soit — le problème redevient une simple estimation de proportion. Le prix se lit en et c'est tout.

6.3 Le piège industriel : réutiliser le jeu de test

Le mot « figé » de l'équation (25) est une contrainte, pas une formalité. Chaque fois que tu compares un modèle de plus sur le même jeu de test, tu ajoutes une hypothèse dans la borne de l'union : comparaisons coûtent , et donc

m_{\text{test}} \ \ge\ \frac{\ln(2k/\delta)}{2\varepsilon^2}

(26)

Modèles comparés sur le même test		Pièces nécessaires ( point)	Surcoût
1 (le protocole propre)	3,6889	18 445	—
5	5,2983	26 492	+44 %
20	6,6846	33 424	+81 %
100	8,2940	41 471	+125 %

Deux lectures, opposées et toutes deux justes. Rassurante : le coût est logarithmique en , donc comparer cent modèles ne double même pas le jeu de test. Inquiétante : si tu ne corriges pas, la garantie que tu annonces est simplement fausse, et l'écart croît avec le nombre d'essais — c'est la même mécanique que les comparaisons multiples en statistique, et c'est exactement pourquoi le module 2.4 impose une validation croisée imbriquée (nested CV) et un jeu de test touché une seule fois.

Une nuance honnête : (26) suppose le pire cas, celui de modèles sans aucun rapport entre eux. En pratique les modèles comparés sont très corrélés — mêmes données, mêmes descripteurs, hyperparamètres voisins — et la dégradation réelle est plus faible que le logarithme ne le dit. Mais on ne sait pas la quantifier sans hypothèse supplémentaire. On paie donc le pire cas, ou on renouvelle le jeu de test.

6.4 Et si l'on passait à un petit réseau ?

Remplace le classifieur linéaire par un MLP : poids, couches. L'ordre de grandeur 12 donne , soit 125 fois tes 200 exemples. On est exactement dans le régime du §2.11 : Sauer-Shelah ne mord pas, il faut repartir de (15) avec , et (16) ne devient légitime que lorsque dépasse .

à : borne , et elle ne bougera pas tant que restera petit devant ;
il faudrait million de paliers démontés pour que la borne devienne simplement non vide.

Pour un réseau à deux couches cachées de 32 neurones. Voilà l'ordre de grandeur du décalage entre la théorie et la pratique — et voilà pourquoi la section 6.2 est la seule réponse opérationnelle.

6.5 Là où la forme de la borne sert quand même

La borne VC ne donne pas de chiffre, mais elle donne une structure : , avec une pénalité croissante en la capacité. C'est le principe de la minimisation du risque structurel de Vapnik, et c'est exactement ce qu'on fait, sous un autre nom, quand on choisit l'ordre d'un modèle ARX en identification de système (module 11.1) : les critères AIC, BIC et de Mallows sont les versions « vraisemblance » de la même idée, avec des pénalités calibrées, elles, sur des hypothèses gaussiennes. La théorie de ce module explique pourquoi une pénalité croissante en la complexité est la bonne forme ; les critères d'information disent combien. Ils sont complémentaires, et aucun des deux ne remplace le jeu de test du §6.2.

§ 07

La démonstration

Éclatement, dichotomies, et la borne face à la réalité

Mode ÉCLATEMENT : déplace les points à la souris, choisis une classe, et le compteur énumère RÉELLEMENT toutes les dichotomies réalisables — l'algorithme exact du §3, complété dans les seules configurations dégénérées par le balayage de directions décrit là-bas. Le curseur « dichotomie » fait défiler les 2^k étiquetages ; quand l'un est réalisable, la frontière du témoin est tracée. Commence par les demi-plans à k = 3 : 8 sur 8, éclaté. Passe à k = 4 : 14 sur 16, et le bouton « impossibles » isole les deux étiquetages interdits — ce sont exactement les deux moitiés de la partition de Radon : sur le quadrilatère du préréglage, les deux diagonales croisées ; traîne un point à l'intérieur du triangle des trois autres et l'interdit devient « ce point seul contre les trois ». Charge ensuite le préréglage « alignés » : à k = 3 tu tombes à 6 sur 8, alors que la VC vaut toujours 3, parce que la définition ne demande qu'UNE configuration éclatée. La classe « cercles » est celle des frontières circulaires, intérieur OU extérieur d'un cercle : c'est une classe linéaire dans les variables (x1, x2, ‖x‖², 1), donc d_VC = 4 et non 3. DÉFI : atteins l'éclatement à k = d_VC pour les cinq classes — 1 point pour les seuils, 2 pour les intervalles, 3 pour les demi-plans, 4 pour les rectangles et pour les cercles ; puis ajoute un point de plus et constate qu'aucune ne repasse jamais à 2^k. Les rectangles demandent un vrai effort : sur l'anneau du préréglage ils ne font que 14 sur 16 à k = 4, et il faut déplacer les points jusqu'à la configuration en losange — un extrême au nord, un au sud, un à l'est, un à l'ouest — pour atteindre 16. C'est le ∃ de la définition mis en pratique : une seule configuration suffit, encore faut-il la trouver. Mode BORNE : le vrai ERM sur les intervalles (Kadane) tourne sur des données tirées, le risque réel est calculé en forme close, et l'on trace l'écart mesuré, la complexité de Rademacher empirique (obtenue en entraînant sur des signes tirés à pile ou face), la borne de Massart et la borne VC. À m = 100 et 10 % de bruit, la borne VC vaut 1,12 : regarde de combien elle passe au-dessus de la ligne « 1 », et à quel point elle ne rejoint jamais la courbe mesurée.

§ 08

Les pièges

« VC-dimension = nombre de paramètres »

C'est l'erreur numéro un, et elle survit à la lecture du cours parce que la coïncidence pour les demi-espaces la conforte. Les deux contre-exemples sont dans le module : la sinusoïde a un paramètre et une VC infinie ; la classe linéaire réelle à norme bornée a paramètres et une complexité de Rademacher en , indépendante de . Le paramétrage est un choix de coordonnées ; la capacité est une propriété de l'ensemble de fonctions. Symptôme du malentendu : « mon modèle a 12 paramètres, il me faut 120 exemples ». Ce raisonnement n'est fondé que si tu as calculé .

Confondre une borne vide et un mauvais modèle

Une borne à 1,12 ne dit pas « ton modèle généralise mal » : elle dit « je n'ai rien à dire ». Ce sont deux affirmations complètement différentes, et la première est un contresens logique. Une borne supérieure ne devient une information que lorsqu'elle est inférieure à ce que tu savais déjà — ici 1. Corollaire pratique : ne jamais comparer deux modèles par leurs bornes. Une borne plus serrée peut venir d'une meilleure analyse plutôt que d'un meilleur modèle. On compare des modèles sur un jeu de test, point.

Appliquer l'équation (2) à l'hypothèse qu'on vient d'entraîner

C'est le péché originel, et il se commet tous les jours : calculer un intervalle de confiance de Hoeffding sur l'erreur d'entraînement. Le de l'équation (2) doit être fixé avant le tirage de l'échantillon. Sur le jeu d'entraînement, en dépend, et l'intervalle obtenu n'a aucune validité — il est systématiquement trop optimiste, exactement de l'écart de généralisation qu'il prétend estimer. Le test qui tranche : ton hypothèse aurait-elle été la même avec un autre échantillon ? Si oui, Hoeffding s'applique. Si non, il faut la convergence uniforme, ou un jeu de test frais.

Regarder le jeu de test « juste pour voir »

Chaque coup d'œil est une hypothèse de plus dans l'union bound de l'équation (26). Trois réglages essayés, c'est au lieu de ; et si tu arrêtes l'entraînement au moment où l'erreur de test est la plus basse, tu as fait une sélection sur le test, donc tu ne peux plus l'utiliser comme test. Le symptôme, en production : un modèle qui tenait ses 98 % en validation et qui en fait 91 % sur le terrain. Le remède est protocolaire, pas mathématique — module 2.4.

Croire que la VC-dimension explique le deep learning

Elle ne l'explique pas, et ce n'est pas un détail technique. Un ResNet-18 a une VC-dimension de l'ordre de 12, et il généralise sur 1,2 million d'images. Zhang et al.11 ont montré que le même réseau mémorise parfaitement des étiquettes aléatoires : la classe éclate l'échantillon, donc toute borne uniforme sur cette classe est vide par construction. Ce qu'il faut dire, et rien de plus : la généralisation des réseaux profonds n'est pas expliquée par la capacité de leur classe d'hypothèses. Les pistes actuelles — marges, normes, PAC-Bayes, stabilité — sont dans la plongée du §2.11.

Inverser ε et δ, ou oublier ce que « avec probabilité 1 − δ » signifie

porte sur l'erreur, sur le tirage de l'échantillon. « Avec probabilité » ne veut pas dire « pour des exemples » : cela veut dire que si tu rejouais tout le protocole — retirer un jeu de exemples, réentraîner, recalculer — la conclusion serait vraie dans des mondes possibles. Sur ton unique jeu de données, tu ne sauras jamais dans lequel tu es. Et remarque l'asymétrie des coûts : passer de à coûte au numérateur, presque rien ; diviser par deux coûte un facteur 4. La confiance est bon marché, la précision est chère.

Prendre Π_H(m) pour le nombre d'hypothèses sur une configuration donnée

est un maximum sur toutes les configurations de points, pas la valeur observée sur les tiens. Trois points alignés donnent 6 dichotomies linéaires au lieu de 8 : ta configuration particulière peut être plus pauvre que le pire cas, ce qui rend la borne encore plus pessimiste. C'est précisément l'un des arguments en faveur de la complexité de Rademacher empirique, qui elle se mesure sur ton échantillon réel — la démonstration du §7 te fait voir l'écart entre les deux.

Faux ami : accuracy

Tout ce module porte sur , dont le complément est l'exactitude (accuracy). Ce n'est pas la précision (precision), qui vaut VP / (VP + FP) et ne concerne qu'une classe (module 2.5). Une borne PAC ne dit rien de la précision, du rappel, ni du F1 : sur des classes déséquilibrées à 1 %, un modèle constant a un risque de 1 % et une borne PAC excellente, pour un rappel nul. La théorie garantit une métrique, et c'est rarement celle qui t'intéresse.