Le théorème qui ne dit rien de votre problème

Trois entrées binaires, donc huit points possibles, et une fonction attribue une étiquette à chacun. Il existe $2^8 = 256$ fonctions de ce type, et ce sont toutes.

Montrez à un apprenant quatre des huit points, avec leurs vraies étiquettes, et notez-le sur les quatre autres. Faites-le pour chacune des 256 fonctions et prenez la moyenne :

La dernière ligne est un apprenant construit pour se tromper : il trouve le point d’apprentissage le plus proche et prédit l’étiquette opposée. Moyenné sur toutes les fonctions, il est exactement aussi bon que le plus proche voisin, qui est exactement aussi bon qu’ignorer complètement les données.

C’est le théorème du « pas de repas gratuit », et le tableau n’est pas une approximation. Chaque entrée est une énumération exacte de 256 fonctions.

A. Pourquoi cela ne peut sortir autrement

Pour tout ensemble de quatre points mis de côté, les 256 fonctions s’apparient. À chaque fonction $f$ correspond une autre qui coïncide avec $f$ sur les quatre points d’apprentissage et diffère sur les quatre points de test. L’apprenant voit les mêmes données dans les deux cas, fait donc les mêmes prédictions, et ses erreurs sur la paire totalisent quatre sur quatre. En moyenne sur la paire : exactement un demi.

Rien de l’apprenant n’intervient dans cet argument. Il vaut pour un réseau profond, pour une table de correspondance et pour un générateur de nombres aléatoires.

B. Et pourquoi il ne s’applique pas

Le théorème moyenne sur une loi uniforme sur toutes les fonctions. C’est l’hypothèse qui fait le travail, et elle n’est pas anodine : sous elle, les étiquettes des points non vus sont indépendantes de celles des points vus. Un monde tiré ainsi ne contient, par construction, aucune structure apprenable, et le théorème le dit.

Restreignez la même moyenne aux six fonctions qui dépendent d’un seul bit - $f(x) = x_i$ ou $f(x) = \neg x_i$, la structure la plus simple qui soit - et les mêmes quatre apprenants donnent :

L’ordre apparaît immédiatement, et c’est celui que tout le monde aurait prédit : la prédiction par similarité aide quand des entrées semblables portent des étiquettes semblables, et l’anti-apprenant est désormais exactement aussi mauvais que l’apprenant est bon.

Ces deux nombres valent pour le découpage utilisé tout au long de l’article, où l’apprenant voit les quatre points dont le premier bit vaut 0 ; en moyenne sur les 70 façons de choisir les quatre points d’entraînement, les six fonctions donnent 0,342857 pour le plus proche voisin et 0,657143 pour l’anti-apprenant, dans le même ordre.

Six sur 256, c’est 2,3 % de l’espace des fonctions. Tout problème réel vit dans un sous-ensemble au moins aussi particulier, et d’ordinaire bien davantage.

C. À quoi sert réellement le théorème

Ce n’est pas un argument pour dire que toutes les méthodes se valent. C’est une preuve qu’aucune méthode n’est universellement meilleure, ce qui a une conséquence précise et utile : le succès d’un apprenant sur une classe de problèmes s’achète en épousant cette classe, et se paie en échouant sur son complémentaire.

C’est là le contenu réel, et il vaut d’être énoncé sous la forme qu’il prend en pratique :

• Tout apprenant a un biais inductif, y compris ceux qui n’en annoncent aucun. Les plus proches voisins supposent que des entrées voisines partagent leurs étiquettes ; les modèles linéaires supposent des effets additifs ; les réseaux convolutifs supposent que la translation compte et que la localité aide. Aucun n’est neutre et aucun ne peut l’être.
• Un résultat de benchmark est un énoncé sur une classe de problèmes. « La méthode X bat la méthode Y » est une affirmation sur la loi dont le benchmark a été tiré, non sur l’apprentissage en général.
• La question utile n’est jamais quel algorithme est le meilleur. C’est quelles hypothèses votre problème satisfait réellement, et quelle méthode est bâtie dessus.

D. À quoi il ne sert pas

Le théorème est régulièrement invoqué pour clore des débats qu’il ne peut trancher : que la sélection de modèle serait vaine, que la connaissance du domaine ne pourrait être encodée utilement, ou que comparer des méthodes n’aurait pas de sens. Les trois sont réfutées par le second tableau. Sous une structure aussi mince que « l’étiquette dépend de l’un des trois bits », un apprenant est deux fois meilleur qu’un autre, et il faut 256 évaluations exactes pour le montrer.