Pourquoi la méthode de Newton n'est-elle pas largement utilisée dans l'apprentissage automatique?

C'est quelque chose qui me dérange depuis un moment et je ne trouvais pas de réponses satisfaisantes en ligne, alors voici:

Après avoir passé en revue un ensemble de conférences sur l'optimisation convexe, la méthode de Newton semble être un algorithme bien supérieur à la descente de gradient pour trouver des solutions globalement optimales, car la méthode de Newton peut fournir une garantie pour sa solution, elle est invariante affine et converge surtout vers beaucoup moins d'étapes. Pourquoi les algorithmes d'optimisation de second ordre, tels que la méthode de Newton, ne sont-ils pas aussi largement utilisés que la descente de gradient stochastique dans les problèmes d'apprentissage machine?

$N$$N^2$

Davantage de personnes devraient utiliser la méthode de Newton en apprentissage automatique *. Je dis cela en tant que personne ayant une formation en optimisation numérique, qui a touché à l'apprentissage automatique au cours des deux dernières années.

Les inconvénients des réponses ici (et même dans la littérature) ne sont pas un problème si vous utilisez correctement la méthode de Newton. De plus, les inconvénients qui en découlent ralentissent également la descente de gradient d’un montant égal ou supérieur, mais par le biais de mécanismes moins évidents.

• L'utilisation de la recherche de lignes dans les conditions de Wolfe ou l'utilisation de ou de régions de confiance empêche la convergence vers les points d'équilibre. Une mise en œuvre appropriée de la descente de gradient devrait également le faire. Le document référencé dans la réponse de Cam.Davidson.Pilon signale des problèmes avec la "méthode de Newton" en présence de points de selle, mais le correctif qu’ils préconisent est également une méthode de Newton.

• Utiliser la méthode de Newton ne nécessite pas de construire le hessien entier (dense); vous pouvez appliquer l'inverse de la hesse à un vecteur à l'aide de méthodes itératives n'utilisant que des produits matriciels (par exemple, les méthodes de Krylov telles que le gradient conjugué). Voir, par exemple, la méthode de région de confiance CG-Steihaug.

• Vous pouvez calculer efficacement les produits matriciels hessiens en résolvant deux équations adjointe d'ordre supérieur de la même forme que l'équation adjointe déjà utilisée pour calculer le gradient (par exemple, le travail de deux étapes de rétropropagation dans la formation d'un réseau neuronal).

• Un mauvais conditionnement ralentit la convergence des solveurs linéaires itératifs, mais il ralentit également ou moins bien la descente de gradient. Utiliser la méthode de Newton au lieu de la descente de gradient déplace la difficulté du stade d'optimisation non linéaire (où l'on ne peut pas faire grand chose pour améliorer la situation) au stade de l'algèbre linéaire (où on peut l'attaquer avec tout l'arsenal de techniques de préconditionnement d'algèbre linéaire numérique).

• En outre, le calcul passe de "nombreuses étapes peu coûteuses" à "quelques étapes coûteuses", ouvrant davantage de possibilités de parallélisme au niveau des sous-étapes (algèbre linéaire).

Pour des informations générales sur ces concepts, je recommande le livre "Optimisation numérique" de Nocedal et Wright.

* Bien sûr, la méthode de Newton ne vous aidera pas avec L1 ou d’autres fonctions de pénalité similaires de compression / promotion de la compression, car elles n’ont pas la douceur requise.

J'ai récemment appris cela moi-même - le problème est la prolifération de points de selle dans un espace de grande dimension, vers lequel les méthodes de Newton veulent converger. Voir cet article: Identifier et attaquer le problème du point de selle dans l'optimisation non convexe de grande dimension .

En effet, le rapport entre le nombre de points de selle et les minima locaux augmente de façon exponentielle avec la dimensionnalité N.

Alors que la dynamique de descente de gradient est repoussée par un point de selle vers une erreur plus basse en suivant les directions de courbure négative, ... la méthode de Newton ne traite pas les points de selle de manière appropriée; comme expliqué ci-dessous, les points de selle deviennent attrayants sous la dynamique de Newton.

Une combinaison de deux raisons:

• La méthode de Newton attire les points de selle;
• Les points de selle sont courants dans l'apprentissage automatique, ou en fait, dans toute optimisation multivariable.

$$f=x^2-y^2$$

$$\mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{H}f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n)$$

$$\mathbf{H}= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

$$\mathbf{H}= \begin{bmatrix} 2 & 0 \\[2.2ex] 0 & -2 \end{bmatrix}$$

$$[\mathbf{H} f]^{-1}= \begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix}$$

$$\nabla f=\begin{bmatrix} 2x \\[2.2ex] -2y \end{bmatrix}$$

$$\mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_{n+1} = \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n -\begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix} \begin{bmatrix} 2x_n \\[2.2ex] -2y_n \end{bmatrix}= \mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_n - \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n = \begin{bmatrix} 0 \\[2.2ex] 0 \end{bmatrix}$$

$x=0,y=0$

En revanche, la méthode de descente de gradient ne mènera pas au point de selle. La pente est nulle au niveau de la selle, mais un petit pas en arrière détournerait l'optimisation, comme vous pouvez le voir sur la pente ci-dessus - sa pente sur la variable y est négative.

Vous avez posé deux questions: pourquoi davantage de personnes n'utilisent-elles pas la méthode de Newton et pourquoi tant de personnes utilisent-elles la descente de gradient stochastique? Ces questions ont des réponses différentes, car de nombreux algorithmes réduisent le fardeau informatique de la méthode de Newton, mais fonctionnent souvent mieux que SGD.

$H$$O(N^2)$$N$$g$$O(N)$$H^{-1} g$$O(N^3)$pour calculer. Ainsi, bien que le calcul de la Hesse coûte cher, l'inverser ou résoudre les moindres carrés est souvent pire. (Si vous avez des caractéristiques rares, les asymptotiques regarder mieux, mais d' autres méthodes aussi effectuer mieux, donc sparsity ne fait pas Newton relativement plus attrayante.)

Deuxièmement, de nombreuses méthodes, pas seulement la descente de gradient, sont utilisées plus souvent que Newton; ils sont souvent des imitations de la méthode de Newton, en ce sens qu'ils se rapprochent d'une étape de Newton à un coût de calcul par étape inférieur, mais prennent plus d'itérations pour converger. Quelques exemples:

• $H^{-1}$

• $O(N^2)$

• Lorsque vous ne voulez pas du tout vous approcher des dérivées secondes, la descente de gradient est attrayante car elle utilise uniquement des informations de premier ordre. La descente de gradient est implicitement approximative du hessien inverse lorsque le taux d’apprentissage est multiplié par la matrice d’identité. Personnellement, j’utilise rarement la descente de gradient: L-BFGS est tout aussi facile à mettre en oeuvre, puisqu’il ne nécessite que de spécifier la fonction objectif et le gradient; l'approximation hessienne inverse est meilleure que la descente de gradient; et parce que la descente de gradient nécessite d’ajuster le taux d’apprentissage.

• Parfois, vous avez un très grand nombre d'observations (points de données), mais vous pourriez presque aussi bien apprendre d'un nombre d'observations plus petit. Dans ce cas, vous pouvez utiliser des "méthodes de traitement par lots", comme la descente de gradient stochastique, qui défilent en utilisant des sous-ensembles d'observations.

Il est moins coûteux de calculer la direction de descente de gradient et effectuer une recherche de ligne dans cette direction est une source de progrès plus fiable et régulière vers un optimum. En bref, la descente de gradient est relativement fiable.

La méthode de Newton est relativement coûteuse dans la mesure où vous devez calculer le hessien à la première itération. Ensuite, à chaque itération suivante, vous pouvez recalculer complètement le Hessian (comme dans la méthode de Newton) ou simplement "mettre à jour" le Hessian de l'itération précédente (dans les méthodes quasi-Newton), qui est meilleur marché mais moins robuste.

Dans le cas extrême d'une fonction très sage, en particulier d'une fonction parfaitement quadratique, la méthode de Newton l'emporte clairement. Si c'est parfaitement quadratique, la méthode de Newton convergera en une seule itération.

Dans le cas contraire d'une fonction très mal conduite, la descente de gradient aura tendance à l'emporter. Il choisira une direction de recherche, effectuera une recherche dans cette direction et, finalement, franchira une étape petite mais productive. En revanche, la méthode de Newton aura tendance à échouer dans ces cas, surtout si vous essayez d'utiliser les approximations quasi-newtoniennes.

Entre la descente de gradient et la méthode de Newton, il existe des méthodes telles que l'algorithme de Levenberg – Marquardt (LMA), bien que j'ai vu les noms un peu confus. L’essentiel est d’utiliser une recherche plus informée sur la descente lorsque les choses sont chaotiques et confuses, puis de passer à une recherche plus informée par la méthode de Newton lorsque les choses deviennent plus linéaires et fiables.

$Hd = g$

La méthode de Newton fonctionne bien à l'approche d'une solution ou si le Hessian varie lentement, mais nécessite quelques astuces pour faire face au manque de convergence et au manque de précision.

Souvent, une amélioration est recherchée plutôt qu'une solution exacte, auquel cas le coût supplémentaire de méthodes de type Newton ou de type Newton n'est pas justifié.

Il existe différentes manières d’améliorer ce qui précède, telles que les méthodes de métrique variable ou de région de confiance.

Il convient de noter que dans de nombreux problèmes, l’échelle est un problème essentiel et le Hessian fournit d’excellentes informations sur l’échelle, bien qu’à un coût. Si l'on peut se rapprocher de la Hesse, cela peut souvent améliorer considérablement les performances. Dans une certaine mesure, la méthode de Newton fournit la "meilleure" mise à l'échelle en ce qu'elle est invariante affine.

L'utilisation de la méthode de Newton pour SGD soulève de nombreuses difficultés, notamment:

• il a besoin d’une matrice de Hesse - comment l’estimer par exemple à partir de gradients bruyants avec une précision suffisante à un coût raisonnable?

• full Hessian est trop coûteux - nous avons plutôt besoin de certaines restrictions, par exemple à un sous-espace (quel sous-espace?),

• $H^{-1}$$\lambda=0$

• La méthode de Newton attire directement le point de fermeture avec un gradient nul ... qui est généralement une selle ici. Comment les repousser à la place? Par exemple, Newton sans sellerie inverse les directions de courbure négatives, mais il faut contrôler les signes de valeurs propres,

• ce serait bien de le faire en ligne - au lieu de faire beaucoup de calculs en un seul point, essayez de le scinder en plusieurs petites étapes exploitant davantage d'informations locales.

Nous pouvons passer du 1er ordre au 2ème ordre par petites étapes. Par exemple, en ajoutant la mise à jour de seulement 3 moyennes à la méthode momentum, nous pouvons simultanément ajuster MSE à la parabole dans son sens pour un choix plus judicieux de la taille de pas ... peut toujours utiliser les coordonnées restantes pour une descente simultanée du gradient.