Il s'agit d'une réaction très courante après la première rencontre avec les théorèmes No Free Lunch (NFL). Celui de l'apprentissage automatique est particulièrement peu intuitif, car il va à l'encontre de tout ce qui est discuté dans la communauté ML. Cela dit, le théorème est vrai, mais ce qu'il signifie est sujet à débat.
Pour reformuler le théorème pour les personnes qui ne le connaissent pas, le théorème NFL pour l'apprentissage automatique est vraiment un cas particulier du théorème NFL pour la recherche et l'optimisation locales . La version de recherche locale est plus facile à comprendre. Le théorème fait la déclaration suivante, quelque peu radicale:
Moyennée sur tous les problèmes d'optimisation possibles, la qualité moyenne de la solution trouvée par n'importe quel algorithme de recherche local que vous choisissez d'utiliser est exactement la même que la qualité moyenne de la solution d'un algorithme de «recherche» local qui génère simplement des solutions possibles en échantillonnant uniformément au hasard à partir de l'espace de toutes les solutions.
Une autre formulation, lorsque les gens veulent une réaction encore plus forte, est de dire que si vous voulez trouver la meilleure solution à un problème, il est tout aussi bon d'essayer des choses qui semblent aggraver votre solution de manière itérative que d'essayer des choses qui semblent améliorer votre solution de manière itérative. En moyenne, ces deux approches sont tout aussi bonnes.
D'accord, alors pourquoi est-ce vrai? Eh bien, la clé réside dans les détails. Wolpert a parfois décrit le théorème comme une spécialisation du travail de Hume sur le problème de l'induction . L'énoncé de base du problème de l'induction est: nous n'avons aucune base logique pour supposer que l'avenir sera comme le passé. Logiquement, il n'y a aucune raison pour que les lois de la physique ne puissent pas toutes changer radicalement demain. D'un point de vue purement logique , il est tout à fait raisonnable que l'avenir puisse être différent du passé de plusieurs façons. Le problème de Hume est que, en général , l'avenir est comme le passé dans beaucoup de façons. Il a essayé de formuler un argument philosophique (logique) selon lequel cela devait être le cas, mais a essentiellement échoué.
Les théorèmes No Free Lunch disent la même chose. Si vous ne savez pas à quoi ressemble votre espace de recherche, alors si vous affinez de manière itérative à quoi ressemble une bonne solution, en réponse aux observations que vous avez faites dans le passé sur ce à quoi ressemblent les bonnes solutions (c'est-à-dire apprendre de données), alors il est tout aussi probable que l’opération que vous effectuez aide qu’elle fait mal. C'est pourquoi la partie "moyennée sur tous les problèmes d'optimisation possibles" est essentielle. Pour tout problème d'optimisation où l'escalade est une bonne stratégie aprèskse déplace, nous pouvons faire un qui est identique, sauf que le kème mouvement d'escalade de colline conduit à une terrible solution. La preuve réelle est plus subtile que cela, mais c'est l'idée de base.
Un très bref résumé profane pourrait être:
Un algorithme d'apprentissage automatique ne peut être amélioré que pour fonctionner mieux sur certains types de problèmes en étant rendu plus mauvais sur un autre type de problème.
Alors qu'est-ce que cela signifie dans un sens pratique? Cela signifie que vous devez avoir une raison a priori de penser que votre algorithme sera efficace sur un problème particulier . Exactement ce à quoi ressemble une bonne raison fait l'objet d'un débat vigoureux au sein de la communauté ML. Ceci est très étroitement lié au compromis biais / variance .
Voici quelques réponses courantes:
- Lorsque vous regardez un nouveau problème d'optimisation, bien qu'il puisse avoir n'importe quel type de structure aléatoire, les problèmes que nous rencontrons dans le monde réel sont beaucoup plus réguliers et certains thèmes communs sont présents, comme le fait que le déplacement " en montée "(minimisation des erreurs) a tendance à conduire de manière itérative à de bonnes solutions. Fondamentalement, cette école de pensée dit que la NFL est un théorème ornemental: la plupart des algorithmes ML fonctionnent mieux sur "le type de problèmes que nous voyons dans la vie réelle", en travaillant pire sur "le genre de problèmes que nous ne voyons pas dans la vraie vie".
- Lorsque vous examinez un nouveau problème d'optimisation dans [insérer votre domaine d'application préféré], bien qu'il puisse avoir tout type de structure aléatoire, les problèmes ont tendance à ressembler à [quoi que vous en pensiez], ce qui rend [votre algorithme préféré] beaucoup plus efficace que la devinette aléatoire.
- Wolpert & McCready eux - mêmes publié un résultat intéressant montrant qu'il ya effectivement sont des processus d'optimisation spécialisée, basée sur la co-évolution, qui sont toujours mieux que deviner au hasard.
Quoi qu'il en soit, il est incontestable que certains algorithmes sont meilleurs que d'autres, dans certains sous-domaines (nous pouvons le voir empiriquement). La NFL nous dit que pour être meilleurs là-bas, ils doivent être pires ailleurs. La question à débattre est de savoir si «ailleurs» est un problème réel ou purement artificiel.
<et>de montrer des espaces réservés. Je les ai éteints pour que vous puissiez voir de plus près ce que John voulait.