Est-il possible de former un réseau de neurones sans rétropropagation?

94

De nombreux ouvrages et tutoriels sur les réseaux de neurones consacrent beaucoup de temps à l'algorithme de rétropropagation, qui est essentiellement un outil permettant de calculer le gradient.

Supposons que nous construisons un modèle avec ~ 10K paramètres / poids. Est-il possible d'exécuter l'optimisation à l'aide d'algorithmes d'optimisation sans gradient?

Je pense que calculer le gradient numérique serait trop lent, mais qu’en est-il d’autres méthodes telles que Nelder-Mead, le recuit simulé ou un algorithme génétique?

Tous les algorithmes souffriraient de minima locaux, pourquoi être obsédé par le gradient?

Haitao Du
la source
6
@FranckDernoncourt, j’ai interprété l’autre question comme suit: "Pourquoi ne pas utiliser des techniques d’optimisation globale pour former des réseaux de neurones?", Alors que celle-ci est plutôt "Pourquoi ne pas utiliser des optimzeurs sans dérivés ...".
GeoMatt22
6
Avec 3 réponses votées, cela ne semble pas trop large pour que je puisse y répondre.
gung - Réintégrer Monica
5
Ouais, vous n'avez pas à vous inquiéter de ce que Nelder-Mead reste bloqué à un minimum local, car vous aurez de la chance si cela peut vous être utile.
Mark L. Stone
1
BTW, ultra L-BFGS, donnez-lui un tourbillon. c'est peut-être bien, mais c'est tellement obscur que probablement personne ne l'a même essayé sur des réseaux de neurones. Voir l'équation 2.9 à la p. 12 (vous devez toutefois lire les quelques pages précédentes pour comprendre la formule) de maths.dundee.ac.uk/nasc/na-reports/NA149_RF.pdf (non appelé ultra BFGS dans le document), qui devrait ensuite entrez dans une version "L" (mémoire limitée) pour être ultra L-BFGS, plutôt que ultra BFGS. La version non-L est présentée dans le document. Ultra BFGS est essentiellement un BFGS gonflé - peut être plus rapide, mais peut-être un peu plus sauvage.
Mark L. Stone

Réponses:

80

Les deux premiers algorithmes que vous mentionnez (Nelder-Mead et Simulated Annealing) sont généralement considérés comme relativement obsolètes dans les cercles d’optimisation, car il existe de bien meilleures alternatives qui sont à la fois plus fiables et moins coûteuses. Les algorithmes génétiques couvrent un large éventail, et certains d'entre eux peuvent être raisonnables.

Toutefois, dans la classe plus large des algorithmes d’optimisation sans dérivées (MPO), beaucoup sont nettement meilleurs que ces "classiques", dans la mesure où il s’agissait d’un domaine de recherche actif au cours des dernières décennies. Ainsi, certaines de ces nouvelles approches pourraient-elles être raisonnables pour un apprentissage en profondeur?

Un article relativement récent comparant l’état de la technique est le suivant:

Rios, LM, & Sahinidis, NV (2013) Optimisation sans dérivés: examen des algorithmes et comparaison des implémentations logicielles. Journal of Global Optimization.

Ceci est un bel article qui présente de nombreuses informations intéressantes sur les techniques récentes. Par exemple, les résultats montrent clairement que les meilleurs optimiseurs locaux sont tous "basés sur un modèle" et utilisent différentes formes de programmation quadratique séquentielle (SQP).

Cependant, comme indiqué dans leur résumé "Nous constatons que la capacité de tous ces solveurs à obtenir de bonnes solutions diminue avec l’augmentation de la taille du problème." Pour donner une idée des nombres, pour tous les problèmes, les solveurs se voyaient attribuer un budget de 2 500 évaluations de fonctions et la taille des problèmes représentait un maximum de ~ 300 paramètres à optimiser. Au-delà des paramètres O [10], très peu de ces optimiseurs se sont très bien comportés, et même les meilleurs ont montré une baisse notable des performances à mesure que la taille du problème augmentait.

Donc, pour les problèmes très dimensionnels, les algorithmes du MPO ne sont tout simplement pas compétitifs par rapport aux algorithmes dérivés. Pour donner une certaine perspective, l’ optimisation basée sur les PDE (équations aux dérivées partielles) est un autre domaine qui présente des problèmes dimensionnels très élevés (par exemple, plusieurs paramètres pour chaque cellule d’une grande grille d’éléments finis 3D). Dans ce domaine, la " méthode adjointe " est l'une des méthodes les plus utilisées. Il s’agit également d’un optimiseur de gradient-descente basé sur la différenciation automatique d’un code de modèle avancé.

Le filtre le plus proche d’un optimiseur DFO de haute dimension est peut-être le filtre d’ensemble Kalman , utilisé pour assimiler des données dans des simulations complexes d’EDP, par exemple des modèles météorologiques. Fait intéressant, il s’agit essentiellement d’une approche SQP, mais avec une interprétation bayésienne-gaussienne (le modèle quadratique est donc défini positif, c’est-à-dire qu’il n’ya pas de point d'équilibre). Mais je ne pense pas que le nombre de paramètres ou d'observations dans ces applications soit comparable à ce que l'on voit dans l'apprentissage en profondeur.

Note secondaire (minima locaux): D'après le peu que j'ai lu sur l'apprentissage en profondeur, je pense que le consensus est qu'il s'agit de points de selle plutôt que de minima locaux, qui sont les plus problématiques pour les espaces de paramètres NN de grande dimension.

Par exemple, la revue récente de Nature indique que "Les résultats théoriques et empiriques récents suggèrent fortement que les minima locaux ne sont pas un problème grave en général. Au lieu de cela, le paysage est rempli d'un nombre combinatoire important de points de selle où la pente est nulle et courbes de surface dans la plupart des dimensions et courbes dans le reste. "

Une préoccupation connexe concerne l'optimisation locale par rapport à l'optimisation globale (par exemple, cette question est soulignée dans les commentaires). Même si je n’apprends pas en profondeur, le fait de suréquiper est certainement une préoccupation valable. À mon avis, les méthodes d'optimisation globales sont les mieux adaptées aux problèmes de conception technique qui ne dépendent pas fortement de données "naturelles". En ce qui concerne les problèmes d'assimilation de données, les minima globaux actuels pourraient facilement changer si de nouvelles données étaient ajoutées (mise en garde: mon expérience est concentrée dans les problèmes géoscientifiques, où les données sont généralement "rares" par rapport à la capacité du modèle).

Une perspective intéressante est peut-être

O. Bousquet & L. Bottou (2008) Les compromis d'un apprentissage à grande échelle. NIPS.

qui fournit des arguments semi-théoriques sur pourquoi et quand l'optimisation approximative peut être préférable en pratique.

Note finale (méta-optimisation): Bien que les techniques basées sur les gradients semblent prédominer pour les réseaux de formation, le MPO pourrait jouer un rôle dans les tâches de méta-optimisation associées.

Un exemple serait le réglage hyper-paramètre. (Il est intéressant de noter que les optimiseurs DFO basés sur des modèles de Rios & Sahinidis, qui ont fait leurs preuves, pourraient essentiellement être considérés comme résolvant une séquence de problèmes de conception d'expériences / surface de réponse .)

O[N2]notL1 pourrait être méta-optimisé cependant.)

GeoMatt22
la source
1
La «critique» que vous citez provient des principaux partisans des réseaux de neurones; Je m'interrogerais sur l'affirmation concernant les minima locaux - une critique théorique bien connue des NN est précisément que tout modèle complexe ne peut pas être optimisé par descente de gradient car il restera bloqué dans les minima locaux. Il n’est pas clair si ce ne sont que les succès des réseaux sociaux qui peuvent être résolus en toile de fond et vous n’entendez pas parler des échecs.
seanv507
2
@ GeoMatt22 La divergence contrastive est une approximation spéciale du gradient d'une classe spéciale de modèles, dans laquelle les RBM sont classés. Il convient de noter que les RBM sont des modèles probabilistes qui impliquent un certain type de distribution, pour lesquels le gradient de l'estimation du maximum de vraisemblance est intraitable. Les réseaux de neurones sont des modèles informatiques qui peuvent être utilisés sans aucun point de départ probabiliste, par exemple via l'optimisation d'une perte de charnière. En résumé, le CD n'est pas un moyen général d'optimiser les réseaux de neurones.
bayerj
2
@ seanv507 Bien que la revendication ait été faite par les principaux promoteurs, des articles examinés par des pairs de grandes conférences de machine learning évaluent ces revendications de manière rigoureuse, par exemple arxiv.org/abs/1406.2572 . À l’heure actuelle, cette affirmation est largement acceptée dans la communauté du blanchiment de capitaux au sens large, principalement en raison de ses arguments théoriques supérieurs et de ses preuves empiriques. Je ne pense pas qu'un argument ad hominem soit adéquat ici.
Bayerj
1
Je conviens que la théorie de DL fait défaut. Vous devez néanmoins reconnaître que des articles comme celui-ci avancent dans ce sens. Si vous estimez que l'article énonce des résultats erronés et que les conclusions (telles que "les minima locaux posent moins de problèmes que les points de selle") sont invalides, vous devez faire mieux que d'affirmer une autre attaque ad hominem, cette fois-ci ML communauté dans son ensemble.
Bayerj
1
Des travaux récents montrent qu’avec une initialisation aléatoire, la descente de gradient converge vers un minimum local (plutôt qu’un point de selle). Papier ici: arxiv.org/abs/1602.04915 et billet de blog ici: offconvex.org/2016/03/24/saddles-again D'autre part, il y a une hypothèse (moins) récente que dans les grands réseaux de neurones, les minima locaux sont à propos de aussi bon que le global, discuté ici: stats.stackexchange.com/questions/203288/…
DavidR 21/09
12

Il y a toutes sortes d'algorithmes de recherche locaux que vous pouvez utiliser, la rétropropagation s'est révélée être le plus efficace pour les tâches plus complexes en général ; il y a des circonstances où d'autres recherches locales sont meilleures.

Vous pouvez utiliser l' escalade à démarrage aléatoire sur un réseau de neurones pour trouver rapidement une solution satisfaisante, mais il ne serait pas faisable de trouver une solution presque optimale.

Wikipedia (je sais, pas la plus grande source, mais quand même) dit

Pour les problèmes dans lesquels la recherche de l'optimum global précis est moins importante que la recherche d'un optimum local acceptable dans un laps de temps déterminé, un recuit simulé peut être préférable à des alternatives telles que la descente de gradient.

la source

En ce qui concerne les algorithmes génétiques, je verrais Backpropagation vs algorithme génétique pour la formation de réseau neuronal

Le principal argument que je voudrais faire valoir pour Backprop est qu’il est très largement utilisé et qu’il a apporté de nombreuses améliorations . Ces images montrent vraiment quelques-uns des progrès incroyables de la rétro-propagation de vanille.

Je ne penserais pas que backprop soit un algorithme, mais une classe d'algorithmes.

J'aimerais également ajouter que pour les réseaux de neurones, les paramètres 10k sont de petits haricots. Une autre recherche fonctionnerait très bien, mais sur un réseau profond avec des millions de paramètres, ce n’est guère pratique.

Liam McInroy
la source
12

Eh bien, les réseaux de neurones d'origine, avant la révolution de la rétropropagation des années 70, ont été "formés" à la main. :)

Cela étant dit:

Il existe une «école» d’apprentissage automatique appelée machine d’apprentissage extrême qui n’utilise pas la rétropropagation.

Ce qu'ils font est de créer un réseau de neurones avec un très grand nombre de nœuds (avec des poids aléatoires), puis de former la dernière couche en utilisant des carrés minimaux (comme une régression linéaire). Ils éliminent ensuite le réseau de neurones par la suite ou appliquent une régularisation à la dernière étape (comme un lasso) pour éviter les surajustements. J'ai vu cela s'appliquer aux réseaux de neurones avec une seule couche cachée. Il n'y a pas d'entraînement, donc c'est super rapide. J'ai fait des tests et étonnamment, ces réseaux de neurones "entraînés" de cette façon sont assez précis.

La plupart des gens, du moins ceux avec qui je travaille, traitent cette école "d'apprentissage" avec dérision et ils forment un groupe exclu avec leurs propres conférences, etc., mais je pense en fait que c'est un peu naïf.


Un autre point: dans la rétropropagation, il existe des alternatives rarement mentionnées, comme la rétroproposition résiliente , qui sont implémentées dans R dans le neuralnetpackage, qui utilisent uniquement l’ampleur de la dérivée. L'algorithme est constitué de conditions if-else au lieu d'algèbre linéaire. Ils présentent certains avantages par rapport à la rétropropagation traditionnelle, à savoir que vous n’avez pas besoin de normaliser vos données car ils ne souffrent pas du problème du gradient en voie de disparition .

Ricardo Cruz
la source
Vous faites la plupart (ou presque tous) les résultats de votre 4ème paragraphe, puis utilisez le résultat comme point de départ d’une optimisation basée sur les dérivées pour le "peaufiner".
Mark L. Stone
1
@ MarkL.Stone Je ne connais personne qui ait fait la rétropropagation en appliquant d'abord une régression linéaire à cette dernière couche. Cela semble intéressant cependant.
Ricardo Cruz
1
Autant que je sache, la controverse autour des ELM est principalement due aux aspects éthiques et non à la mise en œuvre. Schmidt et al. Avaient déjà abordé le sujet en 1992 avec leur réseau Feedforward à pondération aléatoire.
Firebug
3

Vous pouvez utiliser à peu près n'importe quel algorithme d'optimisation numérique pour optimiser les poids d'un réseau de neurones. Vous pouvez également utiliser des algorithmes d’optimisation mixtes continus et discrets pour optimiser non seulement les poids, mais également la présentation elle-même (nombre de couches, nombre de neurones dans chaque couche, même type de neurone). Cependant, il n'y a pas d'algorithme d'optimisation qui ne souffre pas de "malédiction de dimensionnalité" et d'optimas locaux d'une manière ou d'une autre

passant
la source
3

Vous pouvez également utiliser un autre réseau pour indiquer comment les paramètres doivent être mis à jour.

Il existe les interfaces de neurones découplées (DNI) de Google Deepmind. Au lieu d'utiliser la rétropropagation, il utilise un autre ensemble de réseaux de neurones pour prédire comment mettre à jour les paramètres, ce qui permet une mise à jour parallèle et asynchrone des paramètres.

Le document montre que le DNI augmente la vitesse de formation et la capacité modèle des RNN, et donne des résultats comparables pour les RNN et les FFNN pour diverses tâches.


Le document a également énuméré et comparé de nombreuses autres méthodes autres que la rétropropagation

Notre modèle de gradient synthétique est le plus analogue à une fonction de valeur utilisée pour l’ascension de gradient [2] ou à une fonction de valeur utilisée pour l’amorçage. La plupart des autres travaux visant à supprimer la rétropropagation le font dans le but d’affecter des cessions de crédits biologiquement plausibles, mais cela n’élimine pas le verrouillage des mises à jour entre les couches. Par exemple, la propagation de cible [3, 15] supprime la dépendance aux gradients de passage entre les couches, en générant à la place des activations de cible à adapter. Cependant, ces cibles doivent toujours être générées de manière séquentielle, se propageant en arrière sur le réseau et les couches sont donc toujours mises à jour et verrouillées en arrière. D'autres algorithmes suppriment le verrouillage arrière en permettant la perte ou les récompenses d'être diffusées directement sur chaque couche - par exemple, REINFORCE [21] (toutes les activations étant des actions),1et Gradient de politique Coagent Networks [20] - mais restent toujours verrouillés pour la mise à jour car ils nécessitent que les récompenses soient générées par une sortie (ou un critique global). Bien que l'apprentissage récurrent en temps réel [22] ou des approximations telles que [17] puissent sembler un moyen prometteur pour supprimer le verrouillage des mises à jour, ces méthodes nécessitent de conserver le gradient complet (ou approximatif) de l'état actuel par rapport aux paramètres. Cela n’est par nature pas évolutif et nécessite également que l’optimiseur ait une connaissance globale de l’état du réseau. En revanche, en définissant l'interaction entre les couches comme un problème de communication locale avec DNI, nous supprimons le besoin d'une connaissance globale du système d'apprentissage. D'autres travaux tels que [4, 19] permettent l'apprentissage de couches en parallèle sans rétropropagation,

dontloo
la source
2

Tant que cette question concerne la communauté, j'ai pensé ajouter une autre réponse. "Back Propagation" est simplement l'algorithme de descente de gradient. Cela implique d'utiliser uniquement la première dérivée de la fonction pour laquelle on cherche à trouver les minima ou les maxima locaux. Il existe une autre méthode appelée méthode de Newton ou Newton-Raphson qui consiste à calculer la hesse et à utiliser ainsi des dérivées secondes. Il peut réussir dans les cas où la descente de gradient échoue. D’autres me disent plus compétents que moi, et c’est un appel de seconde main à l’autorité, qu’il n’est pas utilisé dans les réseaux neuronaux, car le calcul de toutes les dérivées secondes est trop coûteux en termes de calcul.

Aginensky
la source