Les réseaux de neurones peuvent-ils être utilisés pour concevoir des algorithmes?

Après les succès de plus en plus récents des réseaux de neurones dans les jeux de société, on sent que le prochain objectif que nous nous sommes fixé pourrait être quelque chose de plus utile que de battre les humains dans Starcraft. Plus précisément, je me demandais si

Les réseaux de neurones peuvent-ils être formés pour résoudre des problèmes algorithmiques classiques?

Ici, je veux dire que, par exemple, le réseau obtiendrait un graphe d'entrée avec des bords pondérés et deux sommets et spécifiés, et nous lui avons demandé de trouver un chemin plus court aussi vite que possible. Ensuite, je suppose que le réseau neuronal se découvrirait et s'entraînerait à utiliser Dijkstra ou quelque chose de similaire.s t s $G$$s$$t$$st$

D'une part, nous savons que la puissance de calcul des réseaux de neurones est$TC^0$ . De l'autre, je ne sais pas si cela est nécessairement lié à ma question. Même ainsi, pour la plupart des problèmes, nous ne savons pas s'ils peuvent être résolus dans ou non. Voir si un réseau de neurones peut se former lui-même peut être un bon indicateur de l'existence ou non d'un algorithme rapide. Par exemple, si les réseaux de neurones ne peuvent pas s'entraîner à résoudre SAT rapidement, cela rend (encore plus) probable que . Je me demande ce qu'un réseau de neurones ferait avec GRAPHISOMORPHISME ou FACTORISATION.$TC^0$$NP\not\subset TC^0$

Bien sûr, extraire l'algorithme est une toute autre question. Je soupçonne que les experts savent comment procéder, mais en discuter n'est pas le sujet de cette question.

Ajouté deux jours plus tard: après avoir vu les réponses, permettez-moi de préciser que si vous répondez par la négative, je voudrais savoir

Pourquoi jouer aux échecs est-il plus facile que Dijkstra ou Graphisomorphism?

Selon ce blog de Reza Zadeh , la formation d'un réseau de neurones pour produire une sortie correcte même pour seulement deux tiers des exemples de formation est difficile à calculer:

En effet, en 1988, J. Stephen Judd montre que le problème suivant est NP-difficile:

Étant donné un réseau neuronal général et un ensemble d'exemples d'apprentissage, existe-t-il un ensemble de poids de bordure pour le réseau afin que le réseau produise la sortie correcte pour tous les exemples d'apprentissage?

Judd montre également que le problème reste NP-difficile même s'il ne nécessite qu'un réseau pour produire la sortie correcte pour seulement deux tiers des exemples de formation, ce qui implique que même la formation approximative d'un réseau de neurones est intrinsèquement difficile dans le pire des cas. En 1993, Blum et Rivest aggravent la situation: même un simple réseau avec seulement deux couches et trois nœuds est difficile à former!

Ce n'est pas une réponse complète et je ne suis pas très expérimenté dans les réseaux neuronaux, mais peut-être utile.

Les NN reçoivent essentiellement une entrée et produisent une réponse. Ils sont ensuite formés par la pratique pour produire des réponses similaires sur des entrées "similaires" dans le domaine, par exemple, la même étiquette pour les images du même animal, ou des notes élevées pour les "bonnes" positions d'échecs où bon signifie de grandes chances de gagner.

Donc, comme je l'ai commenté, les réseaux de neurones sont un modèle de calcul non uniforme qui fonctionne de manière totalement différente des algorithmes pas à pas exécutés sur les machines de Turing. Au lieu de cela, considérez-les comme des circuits "mous" qui utilisent des mathématiques continues plutôt que booléennes et peuvent être modifiés ou entraînés, et sont autorisés à se tromper.

Pourquoi jouer aux échecs est-il plus facile que Dijkstra ou Graphisomorphism?

En partie, c'est la différence entre demander à quelqu'un de répondre à une question au mieux de ses capacités et lui demander la seule réponse correcte accompagnée d'une preuve qu'elle est correcte. C'est en partie la différence entre la résolution d'un problème de taille fixe et la résolution simultanée du problème pour toutes les tailles d'entrée possibles.

Chaque fois que Dijkstra s'exécute sur une instance, qui peut être de n'importe quelle taille, cela prouve implicitement que sa sortie est la seule vraie réponse et aucune autre. En échecs et en reconnaissance d'image, on donne la meilleure réponse possible et les erreurs sont tolérées. De plus, on ne forme que des réseaux pour résoudre ces problèmes d'une taille à la fois. Je ne pense pas que nous sachions encore comment généraliser une telle solution de réseau neuronal pour, disons, des instances de problème de tailles et de formes entièrement différentes.

Je ne pense pas que nous devrions supposer que les réseaux neuronaux ne peuvent pas résoudre les chemins les plus courts ou des problèmes algorithmiques similaires, mais ils résolvent les problèmes d'une manière fondamentalement différente d'un algorithme étape par étape qui est toujours correct.

Pour en revenir à la similitude entre les réseaux de neurones et les circuits, notez que les circuits ont été étudiés pendant des décennies, mais à en juger par le manque de réponses à (5) de ma question précédente , nous ne savons presque rien sur la façon de construire des circuits entièrement corrects pour une donnée problème sauf via la transformation d'un algorithme uniforme (Turing Machine) en circuit.

Je ne suis en aucun cas un expert, mais je ne vois pas encore pourquoi.

Les réseaux de neurones effectuent fondamentalement l' optimisation selon une sorte de «modèle coût / bénéfice» qui est souvent déjà connu à l'avance. De plus, l'espace de recherche est bien défini, avec des mouvements valides et non valides connus, et des "variations" faciles à définir. Même pour AlphaZero et AlphaGo, les fonctions de coût sont probablement basées sur le taux de gain et la distribution des taux de gain qui en résulte pour tous les mouvements possibles après avoir effectué un mouvement, ou une sorte d'heuristique pour cela.

Pour concevoir des algorithmes, vous demandez essentiellement au programme d'apprendre à sortir une chaîne correcte (avec un encodage implicite et une fonction de coût déjà connue) qui correspond à un programme qui "exécute un algorithme". Cependant, il existe probablement une infinité d'algorithmes pour lesquels vous pouvez implémenter un programme. Alors peut-être voudrez-vous définir les mesures correctes de "fitness".

Cependant, même pour certains programmes, les paramètres de "fitness" peuvent être quelque peu difficiles à définir. Temps? Utilisation de l'espace? Quantification des "effets secondaires?" De manière optimale, vous générez "le programme le plus court" qui ne fait que ce que vous voulez qu'il fasse.

Je suppose que si vous trouvez les mesures de fitness et les algorithmes de réglage corrects, vous pourrez le faire.

les "réseaux de neurones" transforment un vecteur d'un espace dimensionnel en un autre espace dimensionnel. ils ne sont donc rien de plus que des approximateurs de fonctions hautement, très non linéaires. même les réseaux de neurones utilisent des algorithmes d'approximation pour leur minimisation des pertes. cependant, la formation de réseaux de neurones pour concevoir de nouveaux algorithmes est hors de question. tomas mikolov a fait quelques travaux dans ce domaine avec un réseau de neurones récurrents augmentés par pile, et j'ai également entendu parler de "machines neurales de turing" pour ce domaine. cependant, trouver des stratégies optimales a été la cause fondamentale de l'étude de l'apprentissage par renforcement qui est quelque peu lié à votre question. mais l'utilisation de réseaux de neurones pour concevoir de nouveaux algorithmes n'est pas possible, du moins dans un avenir proche.

Je suis ingénieur QA Automation donc ne revendiquez pas d'expertise dans les réseaux de neurones, mais, tautologiquement, oui NN peut lui-même créer des algorithmes. Les humains eux-mêmes sont NN à un certain niveau, et nous créons des algorithmes, il va donc de soi que les systèmes NN artificiels que nous créons peuvent eux-mêmes créer des algorithmes.