Как работает метод Левенберга-Марквардта

в 19:28, , рубрики: trust-region, Алгоритмы, задача наименьших квадратов, математика, машинное обучение, метод доверительного региона, метод Левенберга-Марквардта, методы оптимизации

Алгоритм Левенберга-Марквардта прост. Алгоритм Левенберга-Марквардта эффективен.

А еще о нем говорят, что он где-то посередине между градиентным спуском и методом Ньютона, что бы это не значило. Ну, с методом Ньютоном и его связью с градиентным спуском вроде как разобрались. Но что имеют ввиду когда произносят эту глубокомысленную фразу? Попробуем слегка подразобраться.

В своих статьях товарищ Левенберг [Levenberg, K. A Method for the Solution of Certain Problems in Last Squares. Quart. Appl. Math. 1944. Vol. 2. P. 164—168.], а после него гражданин Марквардт [Marquardt, Donald (1963). «An Algorithm for Least-Squares Estimation of Nonlinear Parameters». SIAM Journal on Applied Mathematics. 11 (2): 431–441.] рассмотрели задачу наименьших квадратов, которая выглядит так:

Как работает метод Левенберга-Марквардта - 1,

которую можно записать проще в векторной форме

Как работает метод Левенберга-Марквардта - 2.

А можно еще проще, полностью забив на наименьшие квадраты. Это никак не повлияет на повествование.

Итак, рассматривается задача

Как работает метод Левенберга-Марквардта - 3.

Такая задача возникает настолько часто, что важность нахождения эффективного метода ее решения сложно переоценить. Но мы начнем с другого. В предыдущей статье было показано, что широко известный метод градиентного спуска, и не только он, может быть получен из следующих соображений. Допустим, что мы пришли в некоторую точку Как работает метод Левенберга-Марквардта - 4, в которой минимизируемая функция имеет значение Как работает метод Левенберга-Марквардта - 5. Определим в этой точке вспомогательную функцию Как работает метод Левенберга-Марквардта - 6, а также некоторую ее модель Как работает метод Левенберга-Марквардта - 7. Для данной модели мы ставим вспомогательную задачу

Как работает метод Левенберга-Марквардта - 8

где Как работает метод Левенберга-Марквардта - 9 – некоторое наперед заданное множество допустимых значений, выбираемое так, чтобы задача имела простое решение и при этом функция Как работает метод Левенберга-Марквардта - 10 достаточно точно аппроксимировала Как работает метод Левенберга-Марквардта - 11 на Как работает метод Левенберга-Марквардта - 12. Такую схему называют методом доверительного региона, а множество Как работает метод Левенберга-Марквардта - 13, на котором минимизируется значение модельной функции — доверительным регионом этой функции. Для градиентного спуска мы брали Как работает метод Левенберга-Марквардта - 14, для метода Ньютона Как работает метод Левенберга-Марквардта - 15, а в качестве модели для Как работает метод Левенберга-Марквардта - 16 выступала линейная часть разложения в ряд Тейлора Как работает метод Левенберга-Марквардта - 17.

Посмотрим, что будет, если усложнить модель, взяв

Как работает метод Левенберга-Марквардта - 18.

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

Как работает метод Левенберга-Марквардта - 20,

решение которой удовлетворяет равенству

Как работает метод Левенберга-Марквардта - 21

или

Как работает метод Левенберга-Марквардта - 22

Здесь, в отличие от того, что мы видели раньше при использовании линейной модели, направление p оказывается зависимым не только от метрики Как работает метод Левенберга-Марквардта - 23, но и от выбора размера доверительного региона Как работает метод Левенберга-Марквардта - 24, а значит методика линейного поиска неприменима (по крайней мере обоснованно). Также оказывается проблемным определить в явном виде величину Как работает метод Левенберга-Марквардта - 25, соответствующую величине Как работает метод Левенберга-Марквардта - 26. Однако вполне очевидно, что при увеличении Как работает метод Левенберга-Марквардта - 27 длина Как работает метод Левенберга-Марквардта - 28 будет уменьшаться. Если при этом мы еще наложим условие Как работает метод Левенберга-Марквардта - 29, то длина шага будет не больше, чем та, которую дал бы метод Ньютона (всамделешный, без модификаций и условий).

Таким образом, мы можем вместо того, чтобы для заданного Как работает метод Левенберга-Марквардта - 30 искать подходящее значение Как работает метод Левенберга-Марквардта - 31, поступить с точностью до наоборот: найти такое Как работает метод Левенберга-Марквардта - 32, при котором выполняется условие Как работает метод Левенберга-Марквардта - 33. Это своего рода замена почившему в данном случае линейному поиску. Марквардт предложил следующую простую процедуру:

  1. если для некотрого значения Как работает метод Левенберга-Марквардта - 34 условие Как работает метод Левенберга-Марквардта - 35 выполнено, то повторять Как работает метод Левенберга-Марквардта - 36 до тех пор, пока Как работает метод Левенберга-Марквардта - 37
  2. если же Как работает метод Левенберга-Марквардта - 38, то принять Как работает метод Левенберга-Марквардта - 39 и повторить.

Здесь Как работает метод Левенберга-Марквардта - 40 и Как работает метод Левенберга-Марквардта - 41 – константы, являющиеся параметрами метода. Умножение на Как работает метод Левенберга-Марквардта - 42 соответствует расширению доверительного региона, а умножение на Как работает метод Левенберга-Марквардта - 43 – его сужению.

Указанная методика может быть применена к любой целевой функции. Заметьте, здесь уже не требуется положительная определенность гессиана в отличие от рассмотренного ранее случая, когда метод Ньютона представлялся частным случаем метода последовательного спуска. Не требуется даже его невырожденность, что в ряде случаев очень важно. Однако в этом случае увеличивается цена поиска направления, поскольку каждое изменение Как работает метод Левенберга-Марквардта - 44 приводит к необходимости решать линейную систему для определения Как работает метод Левенберга-Марквардта - 45.

Посмотрим что будет, если применить данный подход к задаче о наименьших квадратах.

Градиент функции Как работает метод Левенберга-Марквардта - 46, ее гессиан Как работает метод Левенберга-Марквардта - 47, где Как работает метод Левенберга-Марквардта - 48. Подставляем и получаем следующую систему, определяющую направление поиска

Как работает метод Левенберга-Марквардта - 49.

Вполне приемлемо, но вычислять вторые производные вектор-функции может быть довольно накладно. Марквардт для обхода этой проблемы предложил использовать не саму функцию Как работает метод Левенберга-Марквардта - 50, а ее линейную аппросимацию Как работает метод Левенберга-Марквардта - 51, при которой матрица Как работает метод Левенберга-Марквардта - 52 обращается в ноль. Если теперь в качестве Как работает метод Левенберга-Марквардта - 53 взять единичную матрицу Как работает метод Левенберга-Марквардта - 54, то получим стандартную форму метода Левенберга-Марквардта для решения задачи наименьших квадратов:

Как работает метод Левенберга-Марквардта - 55.

Для данного способа определения направления спуска Марквардтом же была доказана теорема о том, что при устремлении Как работает метод Левенберга-Марквардта - 56 к бесконечности направление Как работает метод Левенберга-Марквардта - 57 стремится к антиградиенту. Строгое доказательство заинтересованный читатель сможет найти в базовой статье, но надеюсь, что само это утверждение стало достаточно очевидным из логики построения метода. Оно в определенной мере оправдывает вездесущую отсылку к тому, что при увеличении лямбды (которую по непонятной мне причине часто называют параметром регуляризации) мы получаем градиентный спуск. На самом деле ничего подобного — мы получили бы его только в пределе, в том самом, где длина шага стремится к нулю. Намного важнее то, что при достаточно большом значении лямбды направление, которое мы получаем, будет являться направлением спуска, а значит мы получаем глобальную сходимость метода. А вот вторая часть утверждения, что при устремлении лямбды к нулю мы получаем метод Ньютона, со всей очевидностью верна, но только если принять вместо Как работает метод Левенберга-Марквардта - 58 ее линейную аппроксимацию Как работает метод Левенберга-Марквардта - 59.

Казалось бы, всё. Минимизируем норму вектор-функции в эллиптической метрике – используем Левенберга-Марквардта. Имеем дело с функцией общего вида и имеем возможность вычислить матрицу вторых производных – велкам использовать метод доверительного региона общего вида. Но есть же извращенцы…

Иногда методом Левенберга-Марквардта для минимизации функции Как работает метод Левенберга-Марквардта - 60 называют выражение вот такого вида:

Как работает метод Левенберга-Марквардта - 61.

Вроде все то же самое, но здесь Как работает метод Левенберга-Марквардта - 62 – матрица вторых! производных функции Как работает метод Левенберга-Марквардта - 63. Формально это имеет право на существование, но является извращением. И вот почему. Тот же Марквардт в своей статье предложил метод решения системы уравнений Как работает метод Левенберга-Марквардта - 64 путем минимизации функции Как работает метод Левенберга-Марквардта - 65 описанным методом. Если в качестве Как работает метод Левенберга-Марквардта - 66 взять градиент целевой функции, то действительно получим приведенное выражение. А извращение это потому, что

решается задача минимизации, порождаемая системой нелинейных уравнений, порождаемых задачей минимизации.

Даблстрайк. Такое выражение, как минимум, не лучше первого уравнения сферического доверительного региона, а вообще намного хуже как с точки зрения производительности (лишние операции по умножению, а в нормальных реализациях — факторизации), так и с точки зрения устойчивости метода (умножение матрицы на себя ухудшает ее обусловленность). Здесь иногда возражают, что Как работает метод Левенберга-Марквардта - 67 гарантированно положительно определена, но в данном случае это не имеет никакого значения. Давайте посмотрим на метод Левенберга-Марквардта с позиций метода последовательного спуска. В этом случае мы, получается, хотим в качестве метрики использовать матрицу Как работает метод Левенберга-Марквардта - 68, и чтобы она могла выступать в этом качестве, значение Как работает метод Левенберга-Марквардта - 69 должно обеспечивать ее положительную определенность. Учитывая, что Как работает метод Левенберга-Марквардта - 70 положительно определена, нужное значение Как работает метод Левенберга-Марквардта - 71 всегда может быть найдено — а значит никакой необходимости требовать от Как работает метод Левенберга-Марквардта - 72 положительной определенности не наблюдается.

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

Как работает метод Левенберга-Марквардта - 74

Если, конечно, матрица Гессе положительно определена. Если нет — то как и раньше можно в качестве метрики использовать исправленный гессиан, либо некоторую матрицу, к нему в каком-либо смысле близкую. Встречается также рекомендация использовать в качестве метрики матрицу Как работает метод Левенберга-Марквардта - 75, которая по построению гарантированно является положительно определенной. К сожалению, мне не известно хоть сколь-нибудь строгого обоснования данного выбора, но в качестве эмпирической рекомендации он упоминается довольно часто.

В качестве иллюстрации давайте посмотрим, как ведет себя метод на все той же функции Розенброка, причем мы будем рассматривать ее в двух ипостасях — как простую функцию, записанную в форме

Как работает метод Левенберга-Марквардта - 76,

и как задачу наименьших квадратов

Как работает метод Левенберга-Марквардта - 77

Как работает метод Левенберга-Марквардта - 78
Так ведет себя метод со сферическим доверительным регионом.
Как работает метод Левенберга-Марквардта - 79
Так тот же метод ведет себя в том случае, если форма доверительного региона задается матрицей, построенной по правилу Давидона-Флетчера-Пауэла. Влияние на сходимость имеется, но куда скромнее, чем в аналогичном случае при использовании линейной модели целевой функции.
Как работает метод Левенберга-Марквардта - 80
А это уже поведение метода, примененного к задаче наименьших квадратов. Сходится за 5 итераций. Только пожалуйста, не делайте из этого вывода, что вторая формулировка для функций такого вида всегда лучше первой. Это не так, просто в этом конкретном случае случае так вышло.

Заключение

Метод Левенберга-Марквардта является, на сколько мне известно, первым методом, основанным на идее доверительного региона. Он весьма неплохо показал себя на практике при решении задачи наименьших квадратов. Сходится метод в большинстве случаев (виденных мной) довольно быстро (о том, хорошо это или плохо я говорил в предыдущей статье). Однако при минимизации функций общего вида выбирать сферу в качестве доверительного региона — вряд ли наилучший из возможных вариантов. Кроме того, существенным недостатком метода (в его базовой формулировке, которая здесь и была описана) является то, что размер доверительного региона задается неявно. Недостаток проявляется в том, что зная значение Как работает метод Левенберга-Марквардта - 81 мы, конечно, можем в текущей точке посчитать Как работает метод Левенберга-Марквардта - 82 просто вычислив длину шага Как работает метод Левенберга-Марквардта - 83. Однако когда мы перейдем в новую точку, этому же значению Как работает метод Левенберга-Марквардта - 84 будет уже соответствовать совсем другая величина доверительного региона. Таким образом, мы лишаемся возможности определения “характерной для задачи” величины доверительного региона и вынуждены в каждой новой точке определять его размер по-новому. Это может быть существенным, когда для сходимости требуется достаточно большое количество итераций, а вычисление значения функции обходится недешево. Подобные проблемы решаются в более продвинутых методах, основанных на идее доверительного региона.

Но это уже совсем другая история.

Автор: alexkolzov

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js