Pourquoi apprendre à partir de données fonctionne

Un modèle ajuste sur des données rapporte un score sur ces données. Tout le monde sait qu'il ne faut pas s'y fier. Moins de gens sauraient dire précisément ce qui cloche, de combien, et ce qu'il faudrait pour qu'on puisse s'y fier.

Ces questions ont des réponses exactes, plus intéressantes que l'avertissement. Cet article en travaille trois, en calculant chaque chiffre plutôt qu'en le citant.

Le nombre que vous voyez est un compte rendu de recherche

Fixez une règle avant de regarder les données. Son erreur sur votre échantillon sera proche de son erreur sur le monde, parce que les points sont des tirages indépendants et que les moyennes se concentrent. C'est de la statistique ordinaire, et rien ne cloche encore.

Les apprenants ne procèdent pas ainsi. Ils regardent les données et choisissent. Ce choix est une fonction de l'échantillon, et il détruit la garantie.

Voici l'ampleur des dégâts, mesurée sur des données construites pour qu'il n'y ait rien à apprendre. Chaque hypothèse candidate est du bruit pur, d'erreur vraie exactement $0,5$. Tirez 200 points, notez-les toutes, gardez la meilleure :

Avec un candidat, rien n'est choisi et le score est honnête à $0,0002$ pres. Avec mille, l'erreur rapportée se situé $0,1149$ sous la vérité - un modèle qui paraît nettement meilleur que le hasard tout en étant exactement le hasard.

Aucune de ces mille hypothèses n'est meilleure qu'une autre. Elles sont identiques en vérité. Ce qui diffère est la chance sur cet échantillon, et prendre la meilleure revient à prendre la plus chanceuse.

C'est le mécanisme derrière le résultat qui ne se reproduit pas, la variable sélectionnée sur les données qui servent ensuite à l'évaluer, et le « nous avons essaye plusieurs architectures et celle-ci a marché ». Le score d'apprentissage n'estimé pas les performances futures ; c'est un compte rendu de recherche.

Payer la recherche, en logarithmes

La réparation consiste à ne plus interroger le gagnant mais tous les candidats à la fois. Si une garantie vaut simultanément pour eux tous, elle couvre celui que les données ont retenu, quelle qu'ait été la sélection.

C'est la borne de l'union, et combinée à l'inégalité de Hoeffding elle donne une exigence en échantillons :

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

Lisez-la comme un tarif : $\varepsilon$ est la tolérance acceptée, $\delta$ la fréquence à laquelle vous laissez la garantie échouer, et $|H|$ ce que coûte votre recherche. A $\varepsilon = 0,1$ et $\delta = 0,05$ :

Un demi-million de fois plus d'hypothèses coûte 658 échantillons de plus. Pas 658 fois plus - 658 de plus.

Ce logarithme est la raison pour laquelle l'apprentissage automatique est possible. Si l'exigence croissait avec la taille de la classe plutôt qu'avec son nombre de chiffres, aucune classe de modèles utile ne serait abordable.

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.

La capacité, quand compter échoue

L'argument compte les hypothèses, et presque toute classe utile en contient une infinité : tous les seuils d'une droite, tous les hyperplans d'un espace. Ces classes généralisent pourtant très bien : compter les membres mesure donc la mauvaise chose.

Le remède est de regarder les données. Deux hypothèses qui attribuent les mêmes étiquettes à vos points sont indiscernables sur eux, quoi qu'elles fassent ailleurs. La quantité qui importe est donc le nombre d'étiquetages distincts que la classe peut produire - un nombre qui reste fini même quand la classe ne l'est pas.

Un ensemble de points est éclaté quand tous ses étiquetages sont atteignables. La dimension VC est la taille du plus grand ensemble éclaté.

Les intervalles sur une droite rendent cela concret. Deux points : un intervalle peut prendre les deux, l'un ou l'autre, ou aucun - les quatre étiquetages, éclaté. Trois points : la classe en atteint 7 sur 8, et celui qui manque est

$$(1, 0, 1)$$

car un intervalle contenant les deux points extérieurs doit contenir le médian. Sept sur huit est un échec - l'éclatement est du tout ou rien - donc la dimension VC vaut exactement 2, retenue par un motif inatteignable.

Les rectangles alignés éclatent quatre points en losange et échouent sur cinq, par un argument qu'il vaut la peine de garder : parmi cinq points, quatre au plus peuvent être extrêmes (gauche, droite, haut, bas), et le point restant est enfermé par eux. Tout rectangle contenant les quatre extrêmes le contient aussi.

Pourquoi cela aide

Le lemme de Sauer transforme une dimension finie en compte polynomial. Une classe de dimension VC $d$ réalisé au plus $\sum_{i \le d} \binom{n}{i}$ étiquetages sur $n$ points. A la dimension 2 :

La borne de l'union n'a jamais eu besoin des hypothèses, seulement de leurs comportements distincts. Mettez le polynôme là où était $|H|$, prenez le logarithme, et le prix devient environ $d \log n$ - assez lent pour que la garantie se resserre à mesure que les données s'accumulent. La capacité cesse d'être un compte d'hypothèses pour devenir un compte de comportements.

Le théorème qui égalise tout le monde

La capacité se mesure donc et se paie. Quel algorithme est le meilleur, alors ?

Prenez un domaine de cinq points : il y a $2^5 = 32$ fonctions cibles possibles. Un apprenant voit trois étiquettes et prédit les deux autres. Moyennez son score sur les 32 cibles. Quatre stratégies délibérément différentes - toujours prédire 1, suivre la majorité vue, ignorer les données et alterner, ou faire l’opposé de la majorité - obtiennent chacune

$$\frac{1}{2}$$

Exactement une moitié, calculée en fractions exactes sur les 32 cibles. Même la stratégie conçue pour être mauvaise.

Le mécanisme n'a rien à voir avec les apprenants. Fixez les étiquettes d'apprentissage et considérez un point non vu : les cibles compatibles vont par paires, identiques sauf en ce point, où l'une dit 0 et l'autre 1. Toute prédiction est juste pour l'une et fausse pour sa jumelle. L'apprenant n'entre jamais dans l'argument.

Et l'étape qui restaure l'apprentissage

N'autorisez maintenant que les 6 cibles qui passent de 0 à 1 au plus une fois, les seuils 00000, 00001, 00011, 00111, 01111 et 11111 - et utilisez un apprenant bâti pour cette forme. L'exactitude devient $3/4$.

Rien n'a été appris sur le monde entre ces deux calculs, et aucune donnée nouvelle n'est arrivée. Ce qui a changé, c'est quels mondes étaient considérés comme possibles.

C'est cela, un biais inductif, et c'est de la que vient la généralisation.

Ce qu'on fait dire au théorème

On le cité comme « aucun algorithme n'est meilleur qu'un autre », ce qui laisse tomber l'hypothèse qui fait tout le travail.

L'égalité vaut en moyennant uniformément sur toutes les cibles possibles. Demandez ce que contient cette distribution : de toutes les fonctions sur un domaine, l'écrasante majorité n'a aucune structure - du bruit incompressible, rien à extraire. Aucune méthode n'y bat le hasard, et elles dominent la moyenne.

Les vrais problèmes vivent dans un coin infime et hautement structure de cet espace. Une moyenne uniforme sur toutes les fonctions n'est le modèle d'aucun problème réel.

Le théorème n'est donc ni un conseil de désespoir ni un permis de déclarer toutes les méthodes équivalentes. Il dit quelque chose de plus net : on n'obtient pas de généralisation à partir de rien. La performance vient d'hypothèses, elles peuvent être fausses, et une méthode qui semble marcher partout n'a simplement pas rencontre le problème sur lequel elle se trompe.

Ce qui fait du choix d'une classe de modèles une affirmation de fond sur le monde

• à poser délibérément, et à énoncer à voix haute.

Le parcours Théorie statistique de l'apprentissage travaille les trois arguments en détail, avec chaque calcul exécutable et modifiable dans le navigateur.