Quelles sont les implications du théorème «Pas de déjeuner gratuit» pour l'apprentissage automatique?

10

Le théorème No Free Lunch (NFL) déclare (voir l'article Coevolutionary Free Lunches de David H. Wolpert et William G. Macready)

deux algorithmes sont équivalents lorsque leurs performances sont moyennées sur tous les problèmes possibles

Le théorème du «déjeuner gratuit» est-il vraiment vrai? Qu'est-ce que cela signifie réellement? Un bel exemple (dans le contexte ML) illustrant cette affirmation serait bien.

J'ai vu certains algorithmes qui se comportent très mal, et j'ai du mal à croire qu'ils suivent réellement le théorème énoncé ci-dessus, alors j'essaie de comprendre si mon interprétation de ce théorème est correcte ou non. Ou s'agit-il simplement d'un autre théorème ornemental comme le théorème d'approximation universelle de Cybenko?

DuttaA
la source

Réponses:

10

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.

John Doucette
la source
"Bien qu'un problème d'optimisation puisse être présent", présent? Je vous suggère de clarifier les points de la section "Certaines réponses courantes sont:".
nbro
Très bonne réponse. Mais par algorithme en incluent-ils toutes les variantes? Par exemple, le backprop peut être implémenté par des dérivés, ou en prenant de petites différences ou par des doubles dérivés (pour autant que je sache), sont-ils donc identiques ou différents? Et par performance est-ce aussi des résultats finaux ou des ressources?
DuttaA
1
@nbro: En fait , je pense que c'était tout simplement le choix malheureux <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.
Neil Slater
@NeilSlater Oui, merci de l'avoir fait!
John Doucette
1
@DuttaA Oui. L'idée clé est que, quelle que soit la stratégie que vous proposez pour résoudre votre problème d'optimisation (comme minimiser l'erreur en prenant en compte des dérivés plus élevés), je peux créer une version du problème qui ressemble exactement à la même chose, sauf que, aprèskitérations, vous vous retrouvez dans une mauvaise solution.
John Doucette