Как работает L-BFGS?

Целью статьи было оптимизировать некоторые параметры путем максимизации регуляризованного логарифмического правдоподобия. Затем они рассчитывают частичные производные. И затем авторы упоминают, что они оптимизируют уравнение, используя L-BFGS, стандартную квазиньютоновскую процедуру для оптимизации гладких функций многих переменных (не более подробностей).

Как это работает ?

По сути, L-BFGS - это способ найти (локальный) минимум целевой функции, используя значения целевой функции и градиент целевой функции. Этот уровень описания охватывает множество методов оптимизации в дополнение к L-BFGS. Вы можете прочитать больше об этом в разделе 7.2 Nocedal and Wright «Численная оптимизация, 2-е издание» http://www.springer.com/us/book/9780387303031 . Очень краткое обсуждение L-BFGS предоставляется по адресу https://en.wikipedia.org/wiki/Limited-memory_BFGS .

Метод первого порядка означает, что используются градиенты (первые производные) (и, возможно, значения целевой функции), но не гессиан (вторые производные). Подумайте, например, о градиентном спуске и самом крутом спуске, среди многих других.

Метод второго порядка означает, что используются градиенты и гессиан (и, возможно, значения целевой функции). Методы второго порядка могут быть основаны на

1. «Точная» матрица Гессе (или конечная разность градиентов), и в этом случае они известны как методы Ньютона или

2. Квазиньютоновские методы, которые аппроксимируют гессиан на основе различий градиентов в течение нескольких итераций путем наложения условия «секущий» (квазиньютоновский). Существует много разных квазиньютоновских методов, которые по-разному оценивают гессиан. Одним из самых популярных является BFGS. Гессенское приближение BFGS может быть либо основано на полной истории градиентов, в этом случае оно называется BFGS, либо оно может основываться только на самых последних m градиентах, и в этом случае оно известно как BFGS с ограниченной памятью, сокращенно как L-BFGS. Преимущество L-BFGS состоит в том, что требуется только сохранение самых последних m градиентов, где m обычно составляет от 10 до 20, что является гораздо меньшим требованием к памяти, чем n * (n + 1) / 2 элементов, необходимых для хранения полного (треугольник) гессианской оценки, как требуется для BFGS, где n - размерность проблемы. В отличие от (полной) BFGS, оценка гессиана никогда явно не формируется и не сохраняется в L-BFGS (хотя некоторые реализации BFGS только формируют и обновляют фактор Чоэлски в гессенском приближении, а не в самом гессенском приближении); скорее, вычисления, которые потребовались бы с оценкой гессиана, выполняются без явного ее формирования. L-BFGS используется вместо BFGS для очень больших проблем (когда n очень большое), но может работать не так хорошо, как BFGS. Следовательно, BFGS предпочтительнее, чем L-BFGS, когда требования к памяти BFGS могут быть выполнены. С другой стороны, L-BFGS не может быть намного хуже по производительности, чем BFGS. оценка гессиана никогда не формируется и не сохраняется в явном виде в L-BFGS (хотя некоторые реализации BFGS только формируют и обновляют фактор Чоэлски в приближении Гессиана, а не само приближение гессена); скорее, вычисления, которые потребовались бы с оценкой гессиана, выполняются без явного ее формирования. L-BFGS используется вместо BFGS для очень больших проблем (когда n очень большое), но может работать не так хорошо, как BFGS. Следовательно, BFGS предпочтительнее, чем L-BFGS, когда требования к памяти BFGS могут быть выполнены. С другой стороны, L-BFGS не может быть намного хуже по производительности, чем BFGS. оценка гессиана никогда не формируется и не сохраняется в явном виде в L-BFGS (хотя некоторые реализации BFGS только формируют и обновляют фактор Чоэлски в приближении Гессиана, а не само приближение гессена); скорее, вычисления, которые потребовались бы с оценкой гессиана, выполняются без явного ее формирования. L-BFGS используется вместо BFGS для очень больших проблем (когда n очень большое), но может работать не так хорошо, как BFGS. Следовательно, BFGS предпочтительнее, чем L-BFGS, когда требования к памяти BFGS могут быть выполнены. С другой стороны, L-BFGS не может быть намного хуже по производительности, чем BFGS. расчеты, которые потребовались бы с оценкой гессиана, выполняются без ее явного формирования. L-BFGS используется вместо BFGS для очень больших проблем (когда n очень большое), но может работать не так хорошо, как BFGS. Следовательно, BFGS предпочтительнее, чем L-BFGS, когда требования к памяти BFGS могут быть выполнены. С другой стороны, L-BFGS не может быть намного хуже по производительности, чем BFGS. расчеты, которые потребовались бы с оценкой гессиана, выполняются без ее явного формирования. L-BFGS используется вместо BFGS для очень больших проблем (когда n очень большое), но может работать не так хорошо, как BFGS. Следовательно, BFGS предпочтительнее, чем L-BFGS, когда требования к памяти BFGS могут быть выполнены. С другой стороны, L-BFGS не может быть намного хуже по производительности, чем BFGS.

Даже на этом уровне описания существует много вариантов. Например, методы могут быть абсолютно беззащитными, и в этом случае все идет, и они могут не сходиться ни к чему, даже при выпуклых задачах. Или они могут быть защищены. Защищенные методы обычно основаны на зонах доверия или поиске строк и предназначены для обеспечения сходимости к чему-либо. Очень важно то, что знание того, что метод является L-BFGS, само по себе не говорит вам, какой тип защиты, если таковой используется, используется. Это все равно, что сказать, что автомобиль - это 4-дверный седан, но, конечно, не все 4-дверные седаны одинаковы по производительности и надежности. Это всего лишь один атрибут алгоритма оптимизации.