Généralisation et borne de l'union

Chaque modèle que vous ajustez rapporte un score sur les données qui ont servi à l'ajuster. Ce nombre n'est pas ce que vous voulez savoir. Ce que vous voulez, c'est comment le modèle se comportera sur des données jamais vues, et l'écart entre les deux n'est pas un détail : c'est tout le sujet de ce parcours.

Deux erreurs, dont une seule est visible

Fixez une hypothèse $h$ : une règle qui prend une entrée et prédit une étiquette.

Son erreur vraie est sa fréquence d'erreur sur toute la population d’où proviennent les données. C'est la quantité qui vous importe, et vous ne pourrez jamais la calculer.

Son erreur d'apprentissage est sa fréquence d'erreur sur votre échantillon. Celle-la se calcule, et c'est la seule chose que vous observez jamais.

Pour une hypothèse unique et fixée, les deux sont proches, et la raison est ordinaire : chaque point de l'échantillon est un tirage indépendant, donc l'erreur d'apprentissage est une moyenne de tirages indépendants, et les moyennes se concentrent. L'inégalité de Hoeffding rend cela précis, en bornant la probabilité qu'une moyenne de $n$ termes indépendants bornes s'écarté de son espérance.

Jusqu'ici, aucun problème. Le problème arrive avec le mot fixée.

Choisir n'est pas gratuit

Un apprenant ne choisit pas son hypothèse à l'avance. Il regarde les données et retient celle qui obtient le meilleur score. Ce choix est lui-même une fonction de l'échantillon, et il détruit entièrement la garantie.

Voici l'ampleur de l'effet, mesurée sur des données conçues pour qu'il n'y ait rien à apprendre. Chaque hypothèse est du bruit pur avec une erreur vraie d'exactement $0,5$ ; aucune n'est meilleure qu'une autre. Tirez 200 points, notez-les toutes, rapportez la meilleure :

Avec un seul candidat il n'y a rien à choisir, et l'erreur d'apprentissage tombe à $0,0002$ de la vérité. Avec mille, l'erreur rapportée se situé $0,1149$ en dessous : un modèle qui paraît nettement meilleur que le hasard tout en étant exactement le hasard.

Rien dans ce tableau ne concerne la qualité des hypothèses. Elles sont identiques. Ce qui diffère, c'est la chance, et prendre le minimum revient à prendre la plus chanceuse. C'est le mécanisme derrière chaque classement qui ne se reproduit pas, chaque variable sélectionnée sur les données qui servent ensuite à l'évaluer, et chaque « nous avons essaye quelques architectures et celle-ci a marché ».

Payer la recherche

La réparation consiste à cesser d'interroger l'hypothèse choisie pour les interroger toutes à la fois.

Si la garantie vaut simultanément pour chaque hypothèse de la classe, alors elle vaut en particulier pour celle que l'apprenant a retenue, quelle que soit la manière dont ce choix s'est fait. L'outil est la borne de l'union, presque embarrassante de simplicité : la probabilité qu'au moins un de plusieurs événements survienne vaut au plus la somme de leurs probabilités individuelles.

Appliquez Hoeffding a chaque hypothèse, additionnez les probabilités d'échec, et résolvez pour la taille d'échantillon :

$$n \;\ge\; \frac{\ln|H| + \ln(2/\delta)}{2\varepsilon^2}$$

Lisez cela comme un tarif. Vous choisissez $\varepsilon$, la tolérance que vous acceptez, et $\delta$, la fréquence à laquelle vous admettez que la garantie échoue. La taille de la classe $|H|$ est ce que coûte votre recherche.

Le logarithme est toute l'histoire

Mettez-y des nombres. Pour $\varepsilon = 0,1$ et $\delta = 0,05$ :

Passer de deux hypothèses à plus d'un million - un demi-million de fois plus - coûte 658 échantillons de plus. Pas 658 fois plus ; 658 de plus.

Voilà ce qu'achète $\log|H|$, et c'est la raison pour laquelle l'apprentissage automatique est possible. Si l'exigence croissait avec $|H|$ plutôt qu'avec son logarithme, aucune classe de modèles intéressante ne serait jamais apprenable. Au lieu de cela, doubler la classe ajoute une constante : l'exigence croit avec le nombre de chiffres de la taille de la classe.

Les deux tableaux sont dans la figure ci-dessous, et aucun n'est simulé. Le meilleur de m hypothèses identiques est le minimum de m tirages binomiaux : la flatterie est donc une somme finie, et non une moyenne sur 200 essais. Cela corrige une entrée : avec un seul candidat, l'écart attendu vaut exactement 0, et le 0,0002 ci-dessus est le bruit de la simulation. Passez au second panneau et poussez la taille de classe jusqu'au milliard pour voir le budget refuser de suivre.

Pourquoi elle doit être uniforme

Un détail mérite d'être énoncé à part, car le sauter est le malentendu le plus fréquent.

La borne vaut pour chaque hypothèse de la classe à la fois. Pas pour la meilleure ; pas pour une hypothèse typique. Pour toutes, simultanément.

C'est exactement ce qu'il faut, et rien de plus faible ne conviendrait. La sortie de l'apprenant dépend de l'échantillon : elle n'est donc pas fixée à l'avance, et une garantie portant sur une hypothèse spécifiée d'avance n'en dit rien. Seul un énoncé couvrant toute la classe est assuré de couvrir ce que les données ont sélectionné.

Cela explique aussi pourquoi la borne est bilaterale et pourquoi elle est pessimiste. Elle doit survivre à un adversaire qui regarde votre échantillon et choisit le pire cas, et c'est une exigence forte. Les performances réelles sont d'ordinaire bien meilleures que ce que la borne promet, ce qui n'est pas grave : le rôle de la borne est d'indiquer quelle quantité contrôle la généralisation, non de prédire votre erreur de test.

Ce que cela laisse ouvert

L'argument compte les hypothèses, ce qui fonctionne quand elles sont en nombre fini. La plupart des classes réelles sont infinies - tous les seuils sur une droite, tous les hyperplans d'un espace - et $\log|H|$ vaut alors $\log\infty$, ce qui n'est pas une borne du tout.

Pourtant ces classes généralisent manifestement. Compter les membres est donc la mauvaise mesure de la capacité, et la leçon suivante la remplace par la bonne : non pas combien d'hypothèses une classe contient, mais combien de choses réellement différentes elle sait faire sur les données dont vous disposez.