Un paramètre, une capacité infinie

Voici un classifieur. Il prend un réel $x$, possède un paramètre réel $\theta$, et prédit

$$h_\theta(x) = \operatorname{sign}\left(\sin(\theta x)\right).$$

Un paramètre. Moins qu’une droite passant par l’origine en dimension deux, ce qui est d’ordinaire l’extrémité bon marché de l’échelle.

Placez vingt points en $x_i = 2^{-i}$ pour $i = 1, \dots, 20$ et donnez-lui l’étiquetage de votre choix. Il y en a $2^{20} = 1{,}048{,}576$. Une seule valeur de $\theta$ réalise chacun d’eux, vérification exhaustive à l’appui.

A. Comment il s’y prend

L’astuce est que $\theta$ n’est pas utilisé comme un bouton de réglage. Il est utilisé comme une bande magnétique.

Prenez les étiquettes $y_1, \dots, y_m$, chacune valant $\pm 1$, et posez

$$\theta = \pi\left(1 + \sum_{i=1}^{m} \frac{1 - y_i}{2}\, 2^{i}\right).$$

Alors $\theta x_i = \theta 2^{-i}$ extrait le développement binaire de $\theta/\pi$ à partir du chiffre $i$, et le signe du sinus lit le bit qui y a été écrit. Chaque étiquette occupe sa propre position binaire et rien n’interfère, parce que les points ont été choisis à une octave les uns des autres.

Un réel contient une infinité de bits. Il n’existe aucun $m$ où cela cesse de fonctionner : la classe $\{h_\theta\}$ pulvérise donc des ensembles de toute taille finie, et sa dimension de Vapnik-Chervonenkis est infinie.

B. Il n’apprend rien

Ajustez les vingt points avec des étiquettes aléatoires, puis interrogez-le sur un vingt et unième point en $x_{21} = 2^{-21}$, lui aussi étiqueté au hasard. Sur 20 000 essais : exactitude d’apprentissage de 100 % à chaque fois, exactitude hors échantillon de 0,5038.

C’est très exactement ce que « dimension VC infinie » veut dire en pratique. Les vingt étiquettes fixent les vingt premiers bits de $\theta/\pi$ et ne disent absolument rien du vingt et unième, si bien que la prédiction sur un point nouveau est un tirage à pile ou face. Le modèle a une mémoire parfaite et aucune généralisation, et les bornes indépendantes de la distribution refusent à juste titre d’en dire quoi que ce soit.

Jusqu’ici, c’est une curiosité. Ce qu’il faut en retenir, c’est l’effet sur le comptage des paramètres.

C. Le nombre de paramètres n’est pas une borne supérieure

La lecture naturelle de « un paramètre » est « cette classe ne peut pas exprimer grand-chose ». Le classifieur sinusoïdal montre que cette lecture est fausse. La capacité porte sur le nombre d’étiquetages distincts qu’une classe peut produire sur un échantillon fini, et le nombre de paramètres ne la contraint que si les paramètres sont utilisés comme on l’attend : continûment, localement, une direction de variation chacun.

Les séparateurs linéaires dans $\mathbb{R}^d$ ont une dimension VC de $d + 1$ : l’intuition survit là et se généralise mal au-delà. Un seul réel peut porter un jeu d’entraînement entier.

Par contraste, la figure montre une classe à deux paramètres dont la capacité est réellement finie : avec un intervalle sur trois points, elle atteint 7 des 8 étiquetages et ne peut pas produire (1, 0, 1).

D. Et ce n’est pas non plus une borne inférieure

Le sens inverse échoue également, et c’est celui qui compte en pratique.

Ajoutez une exigence de marge aux séparateurs linéaires : classer correctement avec tous les points à distance au moins $\gamma$ de la frontière, les données tenant dans une boule de rayon $R$. La capacité de cette classe restreinte est bornée par $R^2 / \gamma^2$ quelle que soit la dimension. Poussez $d$ vers l’infini, ce que fait un noyau, et cette borne ne bouge pas d’un pouce : la contrainte a retiré presque toutes les fonctions que les paramètres pouvaient exprimer, et ce qui reste est gouverné par une échelle et non par un décompte.

Les réseaux modernes sont le même phénomène à plus grande échelle. Ils ont plus de paramètres que d’exemples d’entraînement, si bien que le comptage place leur capacité au-dessus de $n$ et que toute borne classique bâtie dessus est vide. Ils généralisent tout de même. Les paramètres ne sont pas libres de prendre des valeurs arbitraires : ils sont atteints par un optimiseur donné, depuis une initialisation donnée, sous décroissance des poids, arrêt précoce et augmentation des données, et l’ensemble des fonctions réellement atteignables ainsi est bien plus petit que celui que l’architecture pourrait exprimer.

E. Que mesurer à la place

Si le décompte ne borne la capacité dans aucun des deux sens, les options honnêtes sont empiriques.

• Essayez d’ajuster des étiquettes aléatoires. Si un modèle atteint une erreur d’entraînement nulle sur les mêmes entrées avec les étiquettes mélangées, sa capacité effective sur cet échantillon vaut au moins $n$, et toute explication de ses performances réelles doit venir d’ailleurs que de la taille de la classe d’hypothèses.
• Mesurez la marge, et la norme. Pour les classes où une borne existe, la quantité qui y figure est une échelle et non un décompte : $R^2/\gamma^2$ pour les séparateurs, des normes de poids pour les réseaux. Ce sont des choses que l’on peut calculer après l’entraînement.
• Gardez de côté un jeu de test, et gardez-le vraiment. Une estimation de validation mesure directement ce que les bornes cherchent à borner, et elle reste la seule mesure de capacité toujours disponible.
• Méfiez-vous de toute affirmation de capacité formulée avant l’entraînement. Le classifieur sinusoïdal est à une ligne de code d’avoir l’air du modèle le plus simple du monde.

La capacité est une propriété de ce qu’une procédure peut réellement atteindre, non du nombre de nombres qu’elle se trouve stocker.