Comment fonctionne le L-BFGS?

14

Le but de l'article était d'optimiser certains paramètres en maximisant la log-vraisemblance régularisée. Ensuite, ils calculent des dérivées partielles. Et puis les auteurs mentionnent qu'ils optimisent l'équation en utilisant L-BFGS, une procédure standard de Newton pour optimiser les fonctions lisses de nombreuses variables (pas plus de détails).

Comment ça marche ?

Abir
la source
3
Quel papier? Mettre en lien avec le papier A besoin d'un contexte. Mettez des liens vers des acronymes, par exemple L-BFGS ET épelez-les: L-BFGS = algorithme Broyden – Fletcher – Goldfarb – Shanno (BFGS) à mémoire limitée
Carl
1
en.wikipedia.org/wiki/Limited-memory_BFGS Il existe de nombreuses variantes, qui peuvent différer considérablement en termes de capacités et de performances.
Mark L. Stone
salut, merci monsieur Mark :) je vais jeter un oeil. L'article est cs.stanford.edu/people/jure/pubs/circles-tkdd14.pdf (optimisation de l'équation 6)
Abir
Pensez essentiellement au L-BFGS comme un moyen de trouver un minimum (local) d'une fonction objectif, en utilisant les valeurs de la fonction objectif et le gradient de la fonction objectif. Ce niveau de description couvre cependant de nombreuses méthodes d'optimisation en plus du L-BFGS. Vous pouvez en savoir plus à ce sujet dans la section 7.2 de springer.com/us/book/9780387303031 .
Mark L. Stone
1
BFGS est un moyen d'essayer d'obtenir une méthode de premier ordre pour imiter une méthode de second ordre (newton) via la méthode sécante
user795305

Réponses:

28

Pensez essentiellement au L-BFGS comme un moyen de trouver un minimum (local) d'une fonction objectif, en utilisant les valeurs de la fonction objectif et le gradient de la fonction objectif. Ce niveau de description couvre cependant de nombreuses méthodes d'optimisation en plus du L-BFGS. Vous pouvez en savoir plus à ce sujet dans la section 7.2 de Nocedal et Wright "Numerical Optimization, 2nd edition" http://www.springer.com/us/book/9780387303031 . Une discussion très rapide du L-BFGS est fournie à https://en.wikipedia.org/wiki/Limited-memory_BFGS .

La méthode du premier ordre signifie que des gradients (dérivées premières) (et peut-être des valeurs de fonction objectives) sont utilisés, mais pas de Hesse (dérivées secondes). Pensez, par exemple, à la descente en pente et à la descente la plus raide, entre autres.

La méthode du second ordre signifie que les gradients et la toile de jute sont utilisés (et peut-être des valeurs de fonction objectives). Les méthodes de second ordre peuvent être basées sur

  1. Matrice de Hesse "exacte" (ou différences finies de gradients), auquel cas elles sont appelées méthodes de Newton ou

  2. Méthodes Quasi-Newton, qui rapproche la Hesse en fonction des différences de gradients sur plusieurs itérations, en imposant une condition "sécante" (Quasi-Newton). Il existe de nombreuses méthodes Quasi-Newton différentes, qui évaluent la Hesse de différentes manières. L'un des plus populaires est le BFGS. L'approximation BFGS de Hesse peut être basée sur l'historique complet des gradients, auquel cas elle est appelée BFGS, ou elle peut être basée uniquement sur les gradients m les plus récents, auquel cas elle est connue sous le nom de mémoire limitée BFGS, abrégée comme L-BFGS. L'avantage du L-BFGS est qu'il nécessite de ne conserver que les gradients m les plus récents, où m est généralement d'environ 10 à 20, ce qui est une exigence de stockage beaucoup plus petite que n * (n + 1) / 2 éléments nécessaires pour stocker l'intégralité (triangle) d'une estimation de Hesse, comme cela est requis avec BFGS, où n est la dimension du problème. Contrairement au BFGS (complet), l'estimation de la Hesse n'est jamais explicitement formée ou stockée dans L-BFGS (bien que certaines implémentations de BFGS forment et mettent à jour uniquement le facteur Choelsky de l'approximation de Hesse, plutôt que l'approximation de Hesse elle-même); au contraire, les calculs qui seraient nécessaires avec l'estimation de la Hesse sont accomplis sans le former explicitement. L-BFGS est utilisé à la place de BFGS pour les très gros problèmes (lorsque n est très grand), mais peut ne pas fonctionner aussi bien que BFGS. Par conséquent, BFGS est préféré à L-BFGS lorsque les besoins en mémoire de BFGS peuvent être satisfaits. D'un autre côté, le L-BFGS peut ne pas être bien moins performant que le BFGS. l'estimation de la Hesse n'est jamais explicitement formée ou stockée dans L-BFGS (bien que certaines implémentations de BFGS forment et mettent à jour uniquement le facteur Choelsky de l'approximation de Hesse, plutôt que l'approximation de Hesse elle-même); au contraire, les calculs qui seraient nécessaires avec l'estimation de la Hesse sont accomplis sans le former explicitement. L-BFGS est utilisé à la place de BFGS pour les très gros problèmes (lorsque n est très grand), mais peut ne pas fonctionner aussi bien que BFGS. Par conséquent, BFGS est préféré à L-BFGS lorsque les besoins en mémoire de BFGS peuvent être satisfaits. D'un autre côté, le L-BFGS peut ne pas être bien moins performant que le BFGS. l'estimation de la Hesse n'est jamais explicitement formée ou stockée dans L-BFGS (bien que certaines implémentations de BFGS forment et mettent à jour uniquement le facteur Choelsky de l'approximation de Hesse, plutôt que l'approximation de Hesse elle-même); au contraire, les calculs qui seraient nécessaires avec l'estimation de la Hesse sont accomplis sans le former explicitement. L-BFGS est utilisé à la place de BFGS pour les très gros problèmes (lorsque n est très grand), mais peut ne pas fonctionner aussi bien que BFGS. Par conséquent, BFGS est préféré à L-BFGS lorsque les besoins en mémoire de BFGS peuvent être satisfaits. D'un autre côté, le L-BFGS peut ne pas être bien moins performant que le BFGS. les calculs qui seraient nécessaires avec l'estimation de la Hesse sont accomplis sans le former explicitement. L-BFGS est utilisé à la place de BFGS pour les très gros problèmes (lorsque n est très grand), mais peut ne pas fonctionner aussi bien que BFGS. Par conséquent, BFGS est préféré à L-BFGS lorsque les besoins en mémoire de BFGS peuvent être satisfaits. D'un autre côté, le L-BFGS peut ne pas être bien moins performant que le BFGS. les calculs qui seraient nécessaires avec l'estimation de la Hesse sont accomplis sans le former explicitement. L-BFGS est utilisé à la place de BFGS pour les très gros problèmes (lorsque n est très grand), mais peut ne pas fonctionner aussi bien que BFGS. Par conséquent, BFGS est préféré à L-BFGS lorsque les besoins en mémoire de BFGS peuvent être satisfaits. D'un autre côté, le L-BFGS peut ne pas être bien moins performant que le BFGS.

Même à ce niveau de description, il existe de nombreuses variantes. Par exemple, les méthodes peuvent être totalement non protégées, auquel cas tout va, et elles peuvent ne converger vers rien, même sur des problèmes convexes. Ou ils peuvent être protégés. Les méthodes sauvegardées sont généralement basées sur des régions de confiance ou une recherche de ligne et visent à assurer la convergence vers quelque chose. Très important, le simple fait de savoir qu'une méthode est L-BFGS ne vous dit pas en soi quel type de protection, le cas échéant, est utilisé. C'est un peu comme dire qu'une voiture est une berline 4 portes - mais bien sûr, toutes les berlines 4 portes ne sont pas les mêmes en termes de performances ou de fiabilité. Ce n'est qu'un attribut d'un algorithme d'optimisation.

Mark L. Stone
la source
1
Salut Mark, j'ai encore besoin de votre aide, pourriez-vous me dire brièvement la différence entre les méthodes newton et quazi newton ?? merci
Abir
3
Les méthodes de Newton calculent la matrice de Hesse, "par zéro", à chaque itération de l'algorithme, soit exactement, soit par des différences finies du gradient à cette itération. Les méthodes de Quasi-Newton construisent une approximation de la matrice de Hesse en utilisant le différences de gradient entre les itérations. Il existe de nombreuses façons différentes de le faire, donnant lieu à une variété de méthodes Quasi-Newton différentes, telles que BFGS, DFP, SR1 et autres. Habituellement, les méthodes de Newton nécessitent une grande quantité de calcul à chaque itération pour calculer la Hesse, beaucoup plus de calcul par itération que les méthodes de Quasi-Newton.
Mark L. Stone