Como o L-BFGS funciona?

O objetivo do artigo era otimizar alguns parâmetros, maximizando a probabilidade logarítmica regularizada. Então eles calculam derivadas parciais. E os autores mencionam que otimizam a equação usando L-BFGS, um procedimento quase-Newton padrão para otimizar funções suaves de muitas variáveis ​​(sem mais detalhes).

Como funciona ?

Pense basicamente no L-BFGS como uma maneira de encontrar um mínimo (local) de uma função objetivo, usando valores de função objetivo e o gradiente da função objetivo. Esse nível de descrição abrange muitos métodos de otimização, além do L-BFGS. Você pode ler mais sobre isso na seção 7.2 da Nocedal and Wright "Numerical Optimization, 2nd edition" http://www.springer.com/us/book/9780387303031 . Uma discussão muito superficial do L-BFGS é fornecida em https://en.wikipedia.org/wiki/Limited-memory_BFGS .

O método de primeira ordem significa que gradientes (primeiras derivadas) (e talvez valores de função objetivos) sejam usados, mas não Hessianos (segundas derivadas). Pense em, por exemplo, descida de gradiente e descida mais acentuada, entre muitos outros.

O método de segunda ordem significa que são utilizados gradientes e Hessian (e talvez valores de função objetivos). Os métodos de segunda ordem podem ser baseados em

1. Matriz hessiana "exata" (ou diferenças finitas de gradientes), caso em que são conhecidas como métodos de Newton ou

2. Métodos quase-Newton, que aproximam o Hessiano com base em diferenças de gradientes ao longo de várias iterações, impondo uma condição "secante" (Quasi-Newton). Existem muitos métodos Quasi-Newton diferentes, que estimam o Hessiano de maneiras diferentes. Um dos mais populares é o BFGS. A aproximação do BFGS Hessian pode ser baseada no histórico completo de gradientes, caso em que é referida como BFGS, ou pode ser baseada apenas nos m gradientes mais recentes, caso em que é conhecida como memória limitada BFGS, abreviada como L-BFGS. A vantagem do L-BFGS é que isso requer apenas a manutenção dos gradientes m mais recentes, em que m geralmente fica entre 10 e 20, o que é um requisito de armazenamento muito menor do que n * (n + 1) / 2 elementos necessários para armazenar a totalidade (triângulo) de uma estimativa de Hessian, como é exigido no BFGS, onde n é a dimensão do problema. Diferentemente do BFGS (completo), a estimativa do Hessian nunca é explicitamente formada ou armazenada no L-BFGS (embora algumas implementações do BFGS apenas formem e atualizem o fator Choelsky da aproximação do Hessian, em vez da própria aproximação do Hessian); ao contrário, os cálculos que seriam necessários com a estimativa do Hessian são realizados sem explicitamente formulá-lo. O L-BFGS é usado em vez do BFGS para problemas muito grandes (quando n é muito grande), mas pode não ter um desempenho tão bom quanto o BFGS. Portanto, o BFGS é preferível ao L-BFGS quando os requisitos de memória do BFGS podem ser atendidos. Por outro lado, L-BFGS pode não ter desempenho muito pior que o BFGS. a estimativa do Hessian nunca é explicitamente formada ou armazenada no L-BFGS (embora algumas implementações do BFGS apenas formem e atualizem o fator Choelsky da aproximação do Hessian, em vez da própria aproximação do Hessian); ao contrário, os cálculos que seriam necessários com a estimativa do Hessian são realizados sem explicitamente formulá-lo. O L-BFGS é usado em vez do BFGS para problemas muito grandes (quando n é muito grande), mas pode não ter um desempenho tão bom quanto o BFGS. Portanto, o BFGS é preferível ao L-BFGS quando os requisitos de memória do BFGS podem ser atendidos. Por outro lado, L-BFGS pode não ter desempenho muito pior que o BFGS. a estimativa do Hessian nunca é explicitamente formada ou armazenada no L-BFGS (embora algumas implementações do BFGS apenas formem e atualizem o fator Choelsky da aproximação do Hessian, em vez da própria aproximação do Hessian); ao contrário, os cálculos que seriam necessários com a estimativa do Hessian são realizados sem explicitamente formulá-lo. O L-BFGS é usado em vez do BFGS para problemas muito grandes (quando n é muito grande), mas pode não ter um desempenho tão bom quanto o BFGS. Portanto, o BFGS é preferível ao L-BFGS quando os requisitos de memória do BFGS podem ser atendidos. Por outro lado, L-BFGS pode não ter desempenho muito pior que o BFGS. os cálculos que seriam necessários com a estimativa do Hessian são realizados sem o formar explicitamente. O L-BFGS é usado em vez do BFGS para problemas muito grandes (quando n é muito grande), mas pode não ter um desempenho tão bom quanto o BFGS. Portanto, o BFGS é preferível ao L-BFGS quando os requisitos de memória do BFGS podem ser atendidos. Por outro lado, L-BFGS pode não ter desempenho muito pior que o BFGS. os cálculos que seriam necessários com a estimativa do Hessian são realizados sem o formar explicitamente. O L-BFGS é usado em vez do BFGS para problemas muito grandes (quando n é muito grande), mas pode não ter um desempenho tão bom quanto o BFGS. Portanto, o BFGS é preferível ao L-BFGS quando os requisitos de memória do BFGS podem ser atendidos. Por outro lado, L-BFGS pode não ter desempenho muito pior que o BFGS.

Mesmo neste nível de descrição, existem muitas variantes. Por exemplo, os métodos podem ser totalmente desprotegidos; nesse caso, tudo acontece e eles podem não convergir para nada, mesmo em problemas convexos. Ou eles podem ser salvaguardados. Os métodos salvaguardados geralmente são baseados em regiões de confiança ou pesquisa de linha e visam garantir a convergência para algo. Muito importante, apenas o conhecimento de que um método é L-BFGS não indica por si só que tipo de proteção, se houver, é usada. É como dizer que um carro é um sedã de 4 portas - mas é claro que nem todos os sedãs de 4 portas são iguais em desempenho ou confiabilidade. É apenas um atributo de um algoritmo de otimização.