Les techniques d'apprentissage automatique sont-elles des «algorithmes d'approximation»?

23

Récemment, il y a eu une question de type ML sur cstheory stackexchange, et j'ai posté une réponse recommandant la méthode de Powell, la descente de gradient, les algorithmes génétiques ou autres "algorithmes d'approximation". Dans un commentaire, quelqu'un m'a dit que ces méthodes étaient des "heuristiques" et non des "algorithmes d'approximation" et ne se rapprochaient pas souvent de l'optimum théorique (parce qu'elles "se coincent fréquemment dans les minima locaux").

D'autres sont-ils d'accord avec cela? De plus, il me semble que l'on peut garantir que les algorithmes heuristiques peuvent se rapprocher des optimaux théoriques s'ils sont configurés pour explorer une grande partie de l'espace de recherche (par exemple, définir des paramètres / tailles de pas petits), bien que je n'aie pas pas vu ça dans un journal. Est-ce que quelqu'un sait si cela a été démontré ou prouvé dans un article? (sinon pour une grande classe d'algorithmes, peut-être pour une petite classe, disons NN, etc.)

vzn
la source
après réflexion sur cette question, il semble que le domaine de recherche connexe / pertinent soit appelé méthodes / variantes d' optimisation globale en plus d'algorithmes de type local, par exemple la descente de gradient ...
vzn

Réponses:

29

Je pense que vous mélangez plusieurs concepts importants. Permettez-moi de clarifier deux ou trois choses:

  • Il existe des méthodes métaheuristiques, qui sont des méthodes qui tentent de manière itérative d'améliorer une solution candidate. Des exemples de cela sont la recherche taboue, le recuit simulé, les algorithmes génétiques, etc. Et plus important encore lorsqu'ils ne parviennent pas à la solution, nous pouvons en être arbitrairement éloignés. Les problèmes résolus par les méthodes métaheuristiques ont tendance à être de nature discrète, car il existe de bien meilleurs outils pour gérer les problèmes continus. Mais de temps en temps, vous voyez aussi des métaheuristiques pour des problèmes continus.

  • Il existe des méthodes d'optimisation numérique, les membres de cette communauté examinent attentivement la nature de la fonction à optimiser et les restrictions de la solution (en groupes comme l'optimisation convexe, la programmation quadratique, la programmation linéaire, etc.) et appliquent des algorithmes qui ont été montrés de travailler pour ce type de fonction, et ce type de restrictions. Quand les gens dans ce domaine disent "montré qu'ils fonctionnent", cela signifie une preuve. La situation est que ces types de méthodes fonctionnent dans des problèmes continus. Mais lorsque votre problème tombe dans cette catégorie, c'est certainement l'outil à utiliser.

  • Il existe des méthodes d'optimisation discrètes, qui ont tendance à être liées à des algorithmes à des problèmes discrets bien étudiés: tels que les chemins les plus courts, le flux maximal, etc. Il y a un sous-ensemble de personnes dans ce groupe qui étudient des problèmes vraiment difficiles pour lesquels aucun algorithme rapide ne devrait exister. Ils étudient ensuite les algorithmes d'approximation, qui sont des algorithmes rapides pour lesquels ils sont capables de montrer que leur solution se situe dans un facteur constant du véritable optimum. C'est ce qu'on appelle des «algorithmes d'approximation». Ces personnes montrent également leurs résultats comme preuves.

Alors ... pour répondre à votre question, je ne pense pas que les métaheuristiques soient des algorithmes d'approximation. Cela ne me semble pas lié à l'opinion, c'est juste un fait.

carlosdc
la source
En ce qui concerne les "méthodes d'optimisation numérique", les "méthodes d'optimisation discrètes", il semble que de nombreuses techniques ML pourraient se révéler être dans un facteur constant du véritable optimum si leur "espace de recherche initial" est forcé d'être grand, mais je n'ai pas vu de référence sur ce.
2
Je ne suis pas d'accord. * pour l'optimisation numérique, vous pouvez entrer dans le minimum local (bien sûr, vous pouvez également appliquer des procédures qui rendent cela improbable). * Il en va de même pour les réseaux de neurones (au moins, cela peut se produire pendant l'entraînement du perceptron). * Les algorithmes génétiques peuvent également entrer dans le minimum local, de plus si vous choisissez de gros taux de mutation, vous n'obtiendrez aucune évolution sensible! II soupçonne également fortement qu'il existe des ensembles de données qui feront toujours que certains modèles auront des erreurs arbitraires importantes.
jb.
2
@vzn beaucoup de gens choisissent des modèles pour lesquels la solution optimale peut être trouvée. En effet, les fonctions de perte convexe sont utilisées, comme le font les SVM. Trouver le véritable optimum ici signifie «trouver la solution optimale dans votre espace de recherche», ce qui n'a rien à voir avec l'apparence de l'espace de recherche. Comme l'a dit jb, pour les fonctions de perte générales, trouver le véritable optimum est généralement impossible / irréalisable.
Andreas Mueller
acceptant cette réponse comme une description de l'état actuel des choses et des catégories générales d'applications, mais pense toujours qu'il existe des thms de pont qui existent et restent à prouver qui relient les différents domaines. la preuve que les NN peuvent modéliser ou "approximer" tout fn mathématique continu avec un degré de précision arbitraire est étroitement liée ... ie kolmogorovs thm
vzn
3

L'apprentissage automatique traite souvent de l'optimisation d'une fonction qui comporte de nombreux minimas locaux. Les réseaux de neurones à action directe avec des unités cachées en sont un bon exemple. Que ces fonctions soient discrètes ou continues, il n'existe aucune méthode permettant d'atteindre un minimum global et de s'arrêter. Il est facile de prouver qu'il n'y a pas d'algorithme général pour trouver un minimum global d'une fonction continue même si elle est unidimensionnelle et lisse (a une infinité de dérivées). Dans la pratique, tous les algorithmes d'apprentissage des réseaux de neurones sont coincés dans un minimum local. Il est facile de vérifier cela: créez un réseau neuronal aléatoire, créez un grand ensemble de ses réponses à des entrées aléatoires, puis essayez d'apprendre un autre réseau neuronal avec la même architecture pour copier les réponses. Bien que la solution parfaite existe, ni la rétropropagation ni aucun autre algorithme d'apprentissage ne pourront la découvrir,

Certaines méthodes d'apprentissage, comme le recuit simulé ou les algorithmes génétiques, explorent de nombreux minimas locaux. Pour les fonctions continues, il existe des méthodes comme la descente de gradient, qui trouvent le minimum local le plus proche. Ils sont beaucoup plus rapides, c'est pourquoi ils sont largement utilisés dans la pratique. Mais avec suffisamment de temps, l'ancien groupe de méthodes surpasse le dernier en termes d'erreur d'ensemble de formation. Mais avec des contraintes de temps raisonnables, pour les problèmes du monde réel, ce dernier groupe est généralement meilleur.

Pour certains modèles, comme la régression logistique, il existe un minimum local, la fonction est convexe, la minimisation converge vers le minimum, mais les modèles eux-mêmes sont simplistes.

C'est la vérité amère.

Notez également que la preuve de convergence et la preuve de convergence vers la meilleure solution sont deux choses différentes. L'algorithme K-means en est un exemple.

Enfin, pour certains modèles, nous ne savons pas du tout comment apprendre. Par exemple, si la sortie est une fonction arbitraire calculable des entrées, nous ne connaissons pas de bons algorithmes qui, dans un délai raisonnable, trouvent une machine de Turing ou équivalente implémentant cette fonction. Par exemple, si f (1) = 2, f (2) = 3, f (3) = 5, f (4) = 7, ..., f (10) = 29 (dix premiers nombres premiers), nous don Je ne connais aucun algorithme d'apprentissage qui serait capable de prédire, dans un délai raisonnable, que f (11) = 31, à moins qu'il ne connaisse déjà le concept de nombres premiers.

user31264
la source