Le Pas de théorème du déjeuner gratuit est souvent jeté dans le domaine de l’optimisation et de l’apprentissage automatique, souvent avec peu de compréhension de ce que cela signifie ou implique.

Le théorème déclare que tous les algorithmes d’optimisation fonctionnent également bien lorsque leurs performances sont moyennées sur tous les problèmes possibles.

Cela implique qu’il n’y a pas de meilleur algorithme d’optimisation. En raison de la relation étroite entre l’optimisation, la recherche et l’apprentissage automatique, cela implique également qu’il n’existe pas de meilleur algorithme d’apprentissage automatique unique pour les problèmes de modélisation prédictive tels que la classification et la régression.

Dans ce didacticiel, vous découvrirez le théorème sans déjeuner gratuit pour l’optimisation et la recherche.

Après avoir terminé ce tutoriel, vous saurez:

• Le théorème sans déjeuner gratuit suggère que les performances de tous les algorithmes d’optimisation sont identiques, sous certaines contraintes spécifiques.
• Il n’existe pas de meilleur algorithme d’optimisation ou d’algorithme d’apprentissage automatique.
• Les implications pratiques du théorème peuvent être limitées étant donné que nous nous intéressons à un petit sous-ensemble de toutes les fonctions objectives possibles.

Commençons.

Présentation du didacticiel

Ce tutoriel est divisé en trois parties; elles sont:

1. Qu’est-ce que le théorème du non-déjeuner gratuit?
2. Implications pour l’optimisation
3. Implications pour l’apprentissage automatique

Qu’est-ce que le théorème du non-déjeuner gratuit?

Le théorème du No Free Lunch, souvent abrégé en NFL ou NFLT, est une découverte théorique qui suggère que tous les algorithmes d’optimisation fonctionnent également bien lorsque leurs performances sont moyennées sur toutes les fonctions objectives possibles.

La NFL a déclaré que dans certaines contraintes, sur l’espace de tous les problèmes possibles, chaque technique d’optimisation fonctionnera aussi bien que toutes les autres en moyenne (y compris la recherche aléatoire)

– Page 203, Essentials of Metaheuristics, 2011.

Le théorème s’applique à l’optimisation en général et aux problèmes de recherche, car l’optimisation peut être décrite ou encadrée comme un problème de recherche.

L’implication est que les performances de votre algorithme préféré sont identiques à celles d’un algorithme complètement naïf, comme la recherche aléatoire.

En gros, nous montrons que pour les problèmes d’optimisation statiques et dépendants du temps, les performances moyennes de toute paire d’algorithmes sur tous les problèmes possibles sont exactement identiques.

– Aucun théorème de déjeuner gratuit pour l’optimisation, 1997.

Un moyen simple de réfléchir à cette découverte est de considérer une grande table comme vous pourriez avoir dans Excel.

Dans la partie supérieure du tableau, chaque colonne représente un algorithme d’optimisation différent. Sur le côté du tableau, chaque ligne représente une fonction objectif différente. Chaque cellule du tableau représente les performances de l’algorithme sur la fonction objectif, en utilisant la mesure de performance que vous souhaitez, à condition qu’elle soit cohérente sur l’ensemble du tableau.

Vous pouvez imaginer que ce tableau sera infiniment grand. Néanmoins, dans ce tableau, nous pouvons calculer la performance moyenne de n’importe quel algorithme à partir de toutes les valeurs de sa colonne et elle sera identique à la performance moyenne de n’importe quelle autre colonne d’algorithme.

Si un algorithme fonctionne mieux qu’un autre algorithme sur une classe de problèmes, alors il fonctionnera moins bien sur une autre classe de problèmes

– Page 6, Algorithmes d’optimisation, 2019.

Maintenant que nous sommes familiers avec le théorème de l’absence de repas gratuit en général, examinons les implications spécifiques pour l’optimisation.

Implications pour l’optimisation

Les algorithmes d’optimisation dits de boîte noire sont des algorithmes d’optimisation généraux qui peuvent être appliqués à de nombreux problèmes d’optimisation différents et supposent très peu de choses sur la fonction objectif.

Des exemples d’algorithmes de boîte noire incluent l’algorithme génétique, le recuit simulé et l’optimisation de l’essaim de particules.

Le théorème de l’absence de repas gratuit a été proposé dans un environnement de la fin des années 1990 où les affirmations selon lesquelles un algorithme d’optimisation de la boîte noire était meilleur qu’un autre algorithme d’optimisation étaient régulièrement formulées. Le théorème repousse cela, indiquant qu’il n’y a pas de meilleur algorithme d’optimisation, qu’il est prouvé impossible.

Le théorème indique qu’aucun algorithme d’optimisation n’est en moyenne meilleur que tout autre algorithme d’optimisation.

… Connu sous le nom de théorème «pas de repas gratuit», fixe une limite à la qualité d’un apprenant. La limite est assez basse: aucun apprenant ne peut être meilleur que de deviner au hasard!

– Page 63, L’algorithme maître, 2018.

Le hic, c’est que l’application d’algorithmes ne suppose rien sur le problème. En fait, les algorithmes sont appliqués à des fonctions objectives sans aucune connaissance préalable, même si la fonction objectif minimise ou maximise. Et c’est une contrainte dure du théorème.

Nous avons souvent “quelques”Connaissance de la fonction objectif optimisée. En fait, si en pratique on ne savait vraiment rien de la fonction objectif, on ne pourrait pas choisir un algorithme d’optimisation.

Tel qu’élaboré par les théorèmes no free lunch de Wolpert et Macready, il n’y a aucune raison de préférer un algorithme à un autre à moins de faire des hypothèses sur la distribution de probabilité sur l’espace des fonctions objectives possibles.

– Page 6, Algorithmes d’optimisation, 2019.

Le praticien débutant dans le domaine de l’optimisation est invité à apprendre et à utiliser le plus possible le problème dans l’algorithme d’optimisation.

Plus nous en savons et exploitons les algorithmes sur le problème, plus la technique est adaptée au problème et plus l’algorithme est censé fonctionner correctement sur le problème. Le théorème de l’absence de repas gratuit soutient ce conseil.

Nous ne nous soucions pas de tous les mondes possibles, seulement de celui dans lequel nous vivons. Si nous savons quelque chose sur le monde et l’incorporons dans notre apprenant, il a maintenant un avantage sur les devinettes aléatoires.

– Page 63, L’algorithme maître, 2018.

De plus, les performances sont moyennées sur toutes les fonctions objectives possibles et tous les algorithmes d’optimisation possibles. Alors qu’en pratique, nous nous intéressons à un petit sous-ensemble de fonctions objectives qui peuvent avoir une structure ou une forme spécifique et des algorithmes adaptés à ces fonctions.

… Nous ne saurions trop insister sur le fait qu’aucune affirmation n’est faite dans cet article concernant le bon fonctionnement de divers algorithmes de recherche dans la pratique. Cet article se concentre sur ce qui peut être dit a priori sans aucune hypothèse et à partir des seuls principes mathématiques concernant l’utilité d’un algorithme de recherche.

– Aucun théorème de déjeuner gratuit pour l’optimisation, 1997.

Ces implications amènent certains praticiens à noter la valeur pratique limitée du théorème.

Ceci est d’un intérêt théorique considérable mais, je pense, d’une valeur pratique limitée, car l’espace de tous les problèmes possibles comprend probablement de nombreux problèmes extrêmement inhabituels et pathologiques qui sont rarement, voire jamais vus dans la pratique.

– Page 203, Essentials of Metaheuristics, 2011.

Maintenant que nous avons examiné les implications du théorème de l’absence de repas gratuit pour l’optimisation, passons en revue les implications pour l’apprentissage automatique.

Implications pour l’apprentissage automatique

L’apprentissage peut être décrit ou encadré comme un problème d’optimisation, et la plupart des algorithmes d’apprentissage automatique résolvent un problème d’optimisation à la base.

Le théorème de l’absence de repas gratuit pour l’optimisation et la recherche est appliqué à l’apprentissage automatique, en particulier à l’apprentissage supervisé, qui sous-tend les tâches de modélisation prédictive de classification et de régression.

Cela signifie que tous les algorithmes d’apprentissage automatique sont également efficaces pour tous les problèmes de prédiction possibles, par exemple, la forêt aléatoire est aussi bonne que les prédictions aléatoires.

Donc, tous les algorithmes d’apprentissage sont les mêmes en ce que: (1) selon plusieurs définitions de «moyenne», tous les algorithmes ont le même risque moyen de mauvaise classification hors formation, (2) donc aucun algorithme d’apprentissage ne peut avoir un risque plus faible qu’un autre pour tout f…

– Les théorèmes d’apprentissage supervisé sans déjeuner gratuit, 2002.

Cela a également des implications sur la manière dont les algorithmes sont évalués ou choisis, comme le choix d’un algorithme d’apprentissage via un harnais de test de validation croisée k fois ou non.

… Un algorithme qui utilise la validation croisée pour choisir parmi un ensemble préfixé d’algorithmes d’apprentissage ne fait pas mieux en moyenne qu’un qui ne le fait pas.

– Les théorèmes d’apprentissage supervisé sans déjeuner gratuit, 2002.

Cela a également des implications pour l’heuristique commune de ce qui constitue un “bon»Modèle d’apprentissage automatique, comme éviter le surajustement ou choisir le modèle le plus simple possible qui fonctionne bien.

Un autre ensemble d’exemples est fourni par toutes les heuristiques que les gens ont mises au point pour l’apprentissage supervisé, évitez le surajustement, préférez les modèles plus simples aux modèles plus complexes, etc. [no free lunch] dit que toutes ces heuristiques échouent aussi souvent qu’elles réussissent.

– Les théorèmes d’apprentissage supervisé sans déjeuner gratuit, 2002.

Étant donné qu’il n’existe pas de meilleur algorithme d’apprentissage automatique unique pour tous les problèmes de prédiction possibles, cela motive la nécessité de continuer à développer de nouveaux algorithmes d’apprentissage et de mieux comprendre les algorithmes qui ont déjà été développés.

En conséquence du théorème de l’absence de repas gratuit, nous devons développer de nombreux types de modèles différents, pour couvrir la grande variété de données qui se produisent dans le monde réel. Et pour chaque modèle, il peut y avoir de nombreux algorithmes différents que nous pouvons utiliser pour entraîner le modèle, qui font différents compromis vitesse-précision-complexité.

– Pages 24-25, Apprentissage automatique: une perspective probabiliste, 2012.

Il soutient également l’argument consistant à tester une suite d’algorithmes d’apprentissage automatique différents pour un problème de modélisation prédictive donné.

Le “Pas de repas gratuit”Theorem soutient que, sans avoir d’informations substantielles sur le problème de modélisation, il n’y a pas de modèle unique qui fera toujours mieux que tout autre modèle. Pour cette raison, il est possible d’essayer une grande variété de techniques, puis de déterminer sur quel modèle se concentrer.

– Pages 25-26, Modélisation prédictive appliquée, 2013.

Néanmoins, comme pour l’optimisation, les implications du théorème reposent sur le choix d’algorithmes d’apprentissage n’ayant aucune connaissance du problème à résoudre.

En pratique, ce n’est pas le cas, et un praticien débutant en apprentissage automatique est encouragé à examiner les données disponibles afin d’en apprendre davantage sur le problème qui peut être intégré dans l’algorithme d’apprentissage.

Nous pouvons même vouloir aller plus loin et dire que l’apprentissage n’est pas possible sans certaines connaissances préalables et que les données à elles seules ne sont pas suffisantes.

En attendant, la conséquence pratique du théorème «pas de déjeuner gratuit» est qu’il n’y a rien de tel qu’apprendre sans connaissance. Les données seules ne suffisent pas.

– Page 64, L’algorithme maître, 2018.

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous souhaitez approfondir.

Papiers

Livres

Des articles

Résumé

Dans ce didacticiel, vous avez découvert le théorème de l’absence de déjeuner gratuit pour l’optimisation et la recherche.

Plus précisément, vous avez appris:

• Le théorème sans déjeuner gratuit suggère que les performances de tous les algorithmes d’optimisation sont identiques, sous certaines contraintes spécifiques.
• Il n’existe pas de meilleur algorithme d’optimisation ou d’algorithme d’apprentissage automatique.
• Les implications pratiques du théorème peuvent être limitées étant donné que nous nous intéressons à un petit sous-ensemble de toutes les fonctions objectives possibles.

Avez-vous des questions?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.