Évolution des réseaux de neurones artificiels pour résoudre les problèmes de NP

10

J'ai récemment lu une entrée de blog très intéressante de Google Research Blog sur le réseau neuronal. Fondamentalement, ils utilisent ces réseaux de neurones pour résoudre divers problèmes comme la reconnaissance d'image. Ils utilisent des algorithmes génétiques pour "faire évoluer" les poids des axones.

Donc, fondamentalement, mon idée est la suivante. Si j'étais censé écrire un programme qui reconnaît les nombres, je ne saurais pas comment commencer (je pourrais avoir une idée vague mais mon point est: ce n'est pas trivial, ni facile.) Mais en utilisant un réseau de neurones, je n'ai pas à le faire. En créant le bon contexte pour que le réseau neuronal évolue, mon réseau neuronal "trouvera l'algorithme approprié". Ci-dessous, j'ai cité une partie très intéressante de l'article où ils expliquent comment chaque couche a un rôle différent dans le processus de reconnaissance d'image.

L'un des défis des réseaux de neurones est de comprendre ce qui se passe exactement à chaque couche. Nous savons qu'après l'entraînement, chaque couche extrait progressivement des caractéristiques de plus en plus élevées de l'image, jusqu'à ce que la couche finale prenne essentiellement une décision sur ce que l'image montre. Par exemple, le premier calque recherche peut-être des bords ou des coins. Les couches intermédiaires interprètent les caractéristiques de base pour rechercher des formes ou des composants globaux, comme une porte ou un battant. Les dernières couches les assemblent en interprétations complètes - ces neurones s'activent en réponse à des choses très complexes telles que des bâtiments entiers ou des arbres.

Donc, fondamentalement, ma question est la suivante: ne pourrions-nous pas utiliser des algorithmes génétiques + des réseaux de neurones pour résoudre tous les problèmes de NP? Nous créons simplement le bon contexte évolutif et laissons la «nature» trouver une solution.

Inceptionnisme: approfondir les réseaux de neurones

EDIT: Je sais que nous pouvons utiliser Brute-Force ou trouver une solution non efficace dans de nombreux cas. C'est pourquoi j'essaie de mettre en évidence l' évolution des réseaux de neurones artificiels. Comme je l'ai dit dans un commentaire: avec suffisamment de temps et un taux de mutation approprié, nous pourrions trouver la solution optimale (ou du moins c'est ce que je pense).

Concept

NMO
la source
1
Nous n'avons pas à le faire. Nous pouvons simplement utiliser la force brute. Quel est votre objectif exactement?
Pål GD
2
Je ne suis pas un expert des réseaux de neurones, donc je ne sais pas s'ils peuvent être formés pour résoudre correctement les problèmes de NP. Mais je ne pense pas que vous posiez la bonne question. Trouver un algorithme qui résout un problème contenu dans NP n'est généralement pas difficile, il suffit de vérifier toutes les solutions possibles. Cependant, trouver un algorithme qui résout un problème NP-difficile en temps polynomial est une autre histoire et son existence est très peu probable. Étant donné que les réseaux de neurones peuvent être simulés par une machine de correction, ils ont toujours besoin d'un temps super polynomial à moins que P = NP et ne seront pas d'une grande aide.
Dennis Kraft
oui, des réseaux neuronaux ont été utilisés contre des problèmes complets de NP, par exemple le vendeur ambulant et bien d'autres et il existe des recherches / de la littérature sur le sujet. ils peuvent avoir des propriétés utiles mais ils n'échappent pas aux contraintes de temps de la théorie de la complexité comme le souligne DK.
vzn
Mon point est le suivant: en utilisant un taux de mutation approprié et un temps suffisant, nous pourrions (au moins théoriquement) trouver la solution optimale. (Ou au moins un maximum local) Image: Concept
NMO
2
Les algorithmes génétiques (et le reste du lot de techniques "AI") sont essentiellement randomisés "essayez un échantillon de l'espace de la solution" avec quelques astuces (heuristiques) pour ne pas le rendre totalement aléatoire. Non, ce n'est pas mieux que "essayer toutes les solutions possibles", la plupart du temps bien pire (car il n'y a aucune garantie de ne pas vérifier à nouveau le même cas mis au rebut). Bien sûr, ils trouvent des solutions "décentes". Mais nous voulons trouver le meilleur .
vonbrand

Réponses:

21

Non. Il est peu probable que cette orientation soit utile, pour deux raisons:

  1. Les réseaux de neurones ne sont pas «magiques». Ils sont un moyen d'essayer de trouver des modèles. Pour certains problèmes où il existe des modèles suffisamment solides pour être trouvés, et les modèles peuvent être tirés d'un nombre raisonnable d'exemples, ils peuvent être efficaces. Mais ce ne sont pas des poussières de fée magique. Ce n'est pas parce que vous pouvez configurer un réseau de neurones que la rétropropagation trouvera nécessairement un bon moyen de résoudre votre problème. Il se peut qu'il n'y ait aucun motif à trouver, que les motifs ne puissent être découverts qu'avec un nombre d'exemples irréalisables, ou que des motifs existent, mais la procédure de formation du réseau neuronal n'est pas en mesure de les trouver.

Les réseaux de neurones ne sont qu'une autre forme d'apprentissage automatique. Nous pourrions faire les mêmes remarques sur les SVM ou les forêts aléatoires ou la régression linéaire de toute autre forme d'apprentissage automatique. Les réseaux de neurones ne sont pas une sorte de solution miracle magique qui résout tous les problèmes d'apprentissage automatique. Ils sont à peu près aussi efficaces que d'autres méthodes d'apprentissage automatique, ou pour certains types de problèmes, peut-être un peu plus efficaces, mais ils ne sont pas magiques.

Parfois, je croise des gens qui n'ont entendu que peu de choses sur les réseaux de neurones, et ils s'éloignent en pensant que les réseaux de neurones sont la réponse à tout - peut-être parce qu'ils ont entendu que "votre cerveau utilise également les réseaux de neurones", ou ils en ont application cool (reconnaissance vocale ou quelque chose). Mais ne vous y trompez pas. Ne croyez pas le battage médiatique. Les réseaux de neurones sont une technique utile, mais ils ne permettront pas aux ordinateurs de résoudre des problèmes NP-complets, ou de battre le test de Turing, de supprimer tous nos emplois et de remplacer les humains par des ordinateurs. Pas de sitôt, de toute façon. C'est juste de la science-fiction.

DW
la source
1
Vraiment une bonne réponse. Algorithmes génétiques + réseaux de neurones semble très puissant, mais ce n'est peut-être pas suffisant pour résoudre tous les problèmes de np. J'imagine laisser ces réseaux de neurones + algorithmes génétiques à l'état sauvage à la recherche de ces solutions p. Comme des petits éclaireurs haha.
NMO
1
Il peut également être intéressant de noter que les réseaux de neurones fournissent généralement une certaine probabilité de trouver la bonne réponse, et non une garantie. Lorsque vous assouplissez les exigences de votre problème pour permettre des solutions sous-optimales, il existe très souvent des solutions pratiques aux problèmes NP-complets, malgré leur intractabilité dans le pire des cas.
Dan Bryant
9

Il semble que d'autres réponses, bien qu'informatives / utiles, ne comprennent pas vraiment votre question et y lisent un peu trop. Vous n'avez pas demandé si les réseaux de neurones surclasseraient d' autres méthodes, vous avez seulement demandé s'ils pouvaient être appliqués à des problèmes NP complets. La réponse est oui, avec un certain succès et cela est connu depuis des décennies et il existe une grande variété de recherches à ce sujet, et cela continue. Cela a à voir avec la flexibilité de l'apprentissage automatique. Notez que même s'ils ne trouvent pas de solutions exactes ou optimales, les solutions dont ils disposent peuvent avoir d'autres propriétés souhaitables. quelques papiers d'exemple:

vzn
la source
4

Les réseaux de neurones ne résolvent pas réellement les problèmes NP-complets. Ce qu'ils font , c'est résoudre des problèmes qui sont remarquablement proches des problèmes NP-complets.

Une grande caractéristique des réseaux de neurones est qu'ils ne sont pas obligés de trouver la "bonne" réponse à chaque fois. Ils ont le droit de se tromper. Par exemple, vous pourriez résoudre un problème de casier et arriver à une solution qui est à 1% de la solution idéale et être totalement satisfait de cette réponse.

Si vous supprimez l'exigence d'avoir 100% raison à chaque fois, d'autres approches de résolution de problèmes fonctionnent très bien. Par exemple, de nombreux algorithmes de planification d'itinéraire (à la Google Maps) doivent être complets NP, mais il est assez trivial de trouver un algorithme qui trouve un chemin à moins de 1% de l'optimum 99,9% du temps. Il essaie de déterminer les résultats dans le dernier 0,1% des cas, ce qui fait que les efforts de NP-Complete sont si coûteux.

En fait, lorsque nous essayons d'utiliser des équations NP-complètes dans la vie réelle, nous n'avons pas souvent besoin de la réponse réelle . Nous sommes souvent très à l'aise avec une réponse "close", même si nous n'avons souvent pas de libellé pour expliquer quelle métrique "close" nous utilisons. Ce sont les situations où un réseau de neurones peut répondre à la question que vous vouliez poser, plutôt que d'avoir à résoudre le problème NP-complet que vous avez demandé à la place.

Cort Ammon
la source
1

Les réseaux de neurones sont connus pour être capables d' approximation de la fonction universelle , mais cela nécessite de les former sur le problème (optimisation) qui est un problème NP-complet en soi , c'est pourquoi vous avez une formation évolutive et un SGD avec rétropropagation, etc.

Ainsi, même s'ils ne sont pas susceptibles de résoudre des problèmes NP-complets, ils peuvent être formés pour se rapprocher à un degré arbitraire de précision d'une fonction qui modélise le problème. De plus, même si vous résolvez un problème NP-complet de manière optimale en utilisant un réseau de neurones, vous n'avez toujours aucun moyen de prouver que la solution qu'il a trouvée est en fait l'optimum global sans forcer brutalement la solution (ce qui n'est bien sûr pas faisable pour presque toutes les pratiques). cas d'utilisation des réseaux de neurones).

Votre visualisation est précise dans le sens où les algorithmes évolutifs (voyez comment l' algorithme soigné empêche une seule espèce de prendre le dessus sur la population avec une structure initialement très performante en utilisant une forme physique partagée) sont moins aptes que SGD et d'autres techniques d'apprentissage automatique à être piégés dans optimaux locaux mais ils ne prouvent pas que la solution qu'ils trouvent est en fait la solution optimale globale.

nickw
la source
Pourriez-vous ajouter quelques références à votre réponse? Essayez également d'améliorer la mise en forme (par exemple, utilisez NP, SGD, rétropropagation, etc., et ajoutez peut-être des sauts de ligne).
Yuval Filmus
D'
accord,
Je pense que vous devriez justifier votre affirmation selon laquelle "les algorithmes évolutifs ... sont moins aptes que SGD et d'autres techniques d'apprentissage automatique à être piégés dans les optimums locaux". Je ne pense pas que ce soit vrai, en particulier pour la tâche particulière de la formation des réseaux de neurones.
DW
Cette réponse comporte une certaine confusion quant à la définition de l'exhaustivité de NP. Contrairement à ce que vous prétendez, si nous résolvons un problème NP-complet, nous pouvons vérifier si nous avons la bonne solution. Il existe une différence entre un problème de recherche NP-complet et un problème d'optimisation NP-hard; pour les premiers, nous pouvons en effet vérifier efficacement si la solution est correcte, mais pour les seconds nous ne pourrons peut-être pas.
DW
J'ai qualifié que nous ne pouvions pas vérifier que c'était la solution optimale sans forcer brutalement la solution vraiment optimale, n'est-ce pas? J'ai fourni une justification pour mon raisonnement selon lequel la neuroévolution est moins susceptible de rester coincée dans les optimums locaux avec le lien référencé vers l'algorithme soigné et la forme physique partagée, je pense que la sensibilité des descentes de gradient à être coincé dans les optimums locaux est plutôt évidente, et même si un réglage hyperparamétrique le cadre peut aider à atténuer cela, je ne créditerais pas cela car un sgd d'aversion possède à se coincer.
nickw