Ох уж этот метод Ньютона

в 19:01, , рубрики: trust-region, Алгоритмы, градиентный спуск, математика, машинное обучение, метод доверительного региона, метод ньютона, методы оптимизации

О методах численной оптимизации написано много. Это и понятно, особенно на фоне тех успехов, которые в последнее время демонстрируют глубокие нейронные сети. И очень отрадно, что хотя бы часть энтузиастов интересуется не только тем, как забомбить свою нейросеточку на набравшей в этих ваших интернетах популярность фреймворках, но и тем, как и почему все это вообще работает. Однако мне в последнее время пришлось отметить, что при изложении вопросов, связанных с обучением нейросетей (и не только с обучением, и не только сетей), в том числе на Хабре, все чаще впроброс используется ряд “хорошо известных” утверждений, справедливость которых, мягко говоря, сомнительна. Среди таких сомнительных утверждений:

  1. Методы второго и более порядков плохо работают в задачах обучения нейросетей. Потомучто.
  2. Метод Ньютона требует положительной определенности матрицы Гессе (вторых производных) и поэтому плохо работает.
  3. Метод Левенберга-Марквардта — компромисс между градиентным спуском и методом Ньютона и вообще эвристичекий.

и т.д. Чем продолжать этот список, лучше перейдем к делу. В этом посте рассмотрим второе утверждение, поскольку его я только на Хабре встречал как минимум дважды. Первый вопрос затрону только в той части, что касается метода Ньютона, поскольку он куда более обширен. Третий и остальные оставим до лучших времен.

Центром нашего внимания будет задача безусловной оптимизации Ох уж этот метод Ньютона - 1, где Ох уж этот метод Ньютона - 2 — точка векторного пространства, или просто — вектор. Естественно, что эту задачу решить тем проще, чем больше мы знаем об Ох уж этот метод Ньютона - 3. Обычно она предполагается дифференцируемой по каждому аргументу Ох уж этот метод Ньютона - 4, причем столько раз, сколько требуется для наших грязных дел. Хорошо известно, что необходимым условием того, что в точке Ох уж этот метод Ньютона - 5 достигается минимум, является равенство градиента функции Ох уж этот метод Ньютона - 6 в этой точке нулю. Отсюда моментально получаем следующий метод минимизации:

Решить уравнение Ох уж этот метод Ньютона - 7.

Задача, мягко говоря, непростая. Точно не проще, чем исходная. Однако на этом моменте сразу можно отметить связь между задачей минимизации и задачей решения системы нелинейных уравнений. Эта связь нам еще аукнется при рассмотрении метода Левенберга-Марквардта (когда до него доберемся). А пока вспомним (или узнаем), что одним из наиболее часто применяемых методов для решения систем нелинейных уравнения является метод Ньютона. Заключается он в том, что для решения уравнения Ох уж этот метод Ньютона - 8 мы, начиная с некоторого начального приближения Ох уж этот метод Ньютона - 9, строим последовательность

Ох уж этот метод Ньютона - 10 – явный метод Ньютона

или

Ох уж этот метод Ньютона - 11 – неявный метод Ньютона

где Ох уж этот метод Ньютона - 12 – матрица, составленная из частных производных функции Ох уж этот метод Ньютона - 13. Естественно, что в общем случае, когда система нелинейных уравнений просто дана нам в ощущениях, требовать что-либо от матрицы Ох уж этот метод Ньютона - 14 мы не вправе. В случае, когда уравнение представляет собой условие минимума для какой-то функции, то мы можем утверждать, что матрица Ох уж этот метод Ньютона - 15 симметрична. Но не более.

Метод Ньютона для решения систем нелинейных уравнений весьма неплохо изучен. И вот ведь штука — для его сходимости не требуется положительная определенность матрицы Ох уж этот метод Ньютона - 16. Да и не может требоваться — иначе ему была бы грош цена. Вместо этого существуют другие условия, которые обеспечивают локальную сходимость данного метода и которые мы здесь рассматривать не будем, отправляя заинтересованных к специализированной литературе (или в комментарии). Получаем, что утверждение 2 неверно.

Так?

И да, и нет. Засада здесь в слове локальная перед словом сходимость. Оно означает, что начальное приближение Ох уж этот метод Ньютона - 17 должно быть “достаточно близким” к решению, в противном случае на каждом шаге мы будем все дальше и дальше удаляться от оного. Что же делать? Я не буду вдаваться в детали того, как эту проблему решают для систем нелинейных уравнений общего вида. Вместо этого вернемся к нашей задаче оптимизации. Первая ошибка утверждения 2 на самом деле в том, что обычно говоря о методе Ньютона в задачах оптимизации имеют ввиду его модификацию — демпфированный метод Ньютона, в котором последовательность приближений строится по правилу

Ох уж этот метод Ньютона - 18 – явный демпфированный метод Ньютона

Ох уж этот метод Ньютона - 19 – неявный демпфированный метод Ньютона

Здесь последовательность Ох уж этот метод Ньютона - 20 является параметром метода и ее построение представляет собой отдельную задачу. В задачах минимизации естественным при выборе Ох уж этот метод Ньютона - 21 будет требование, чтобы на каждой итерации значение функции f уменьшалось, т.е. Ох уж этот метод Ньютона - 22. Возникает закономерный вопрос: а существует ли вообще такое (положительное) Ох уж этот метод Ньютона - 23? И если ответ на этот вопрос положителен, то Ох уж этот метод Ньютона - 24 называют направлением спуска. Тогда вопрос можно поставить таким образом:
когда направление, генерируемое методом Ньютона, является направлением спуска?
И для ответа на него придется посмотреть на задачу минимизации с другого бока.

Методы спуска

Для задачи минимизации вполне естественным кажется такой подход: начиная с некоторой произвольной точки, выберем некоторым образом направление p и сделаем в этом направлении шаг Ох уж этот метод Ньютона - 25. Если Ох уж этот метод Ньютона - 26, то возьмем Ох уж этот метод Ньютона - 27 в качестве новой начальной точки и повторим процедуру. Если направление выбирается произвольно, то такой метод иногда называют методом случайного блуждания. Можно в качестве направления брать вектора единичного базиса — то есть делать шаг только по одной координате, такой метод называют методом покоординатного спуска. Стоит ли говорить, что они неэффективны? Для того, чтобы такой подход хорошо работал, нам нужны некоторые дополнительные гарантии. Для этого введем вспомогательную функцию Ох уж этот метод Ньютона - 28. Думаю, вполне очевидно, что минимизация Ох уж этот метод Ньютона - 29 полностью эквивалентна минимизации Ох уж этот метод Ньютона - 30. Если Ох уж этот метод Ньютона - 31 дифференцируема, то Ох уж этот метод Ньютона - 32 представима в виде

Ох уж этот метод Ньютона - 33

и если Ох уж этот метод Ньютона - 34 достаточно мало, то Ох уж этот метод Ньютона - 35. Можем теперь попробовать подменить задачу минимизации Ох уж этот метод Ньютона - 36 задачей минимизации ее приближения (или модели) Ох уж этот метод Ньютона - 37. Кстати, все методы, основанные на использовании модели Ох уж этот метод Ньютона - 38 называются градиентными. Но вот ведь беда, Ох уж этот метод Ньютона - 39 – линейная функция и, следовательно, минимума у нее нет. Для разрешения этой проблемы добавим ограничение на длину шага, который мы хотим сделать. В данном случае это вполне естественное требование — ведь наша модель более-менее корректно описывает целевую функцию только в достаточно малой окрестности. В результате получаем дополнительную задачу условной оптимизации:

Ох уж этот метод Ньютона - 40

У этой задачи есть очевидное решение: Ох уж этот метод Ньютона - 41, где Ох уж этот метод Ньютона - 42 – множитель, гарантирующий выполнение ограничения. Тогда итерации метода спуска примут вид

Ох уж этот метод Ньютона - 43,

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

Исходя из свойств построенной модели целевой функции мы можем утверждать, что найдется такое Ох уж этот метод Ньютона - 45, пусть даже очень маленькое, что если Ох уж этот метод Ньютона - 46, то Ох уж этот метод Ньютона - 47. Примечательно, что в данном случае направление, в котором мы будем двигаться, никак не зависит от величины радиуса этой сферы. Тогда мы можем избрать один из следующих путей:

  1. Подбирать по некоторой методике величину Ох уж этот метод Ньютона - 48.
  2. Поставить задачу выбора соответствующего значения Ох уж этот метод Ньютона - 49, обеспечивающее уменьшение значения целевой функции.

Первый подход характерен для методов доверительного региона, второй приводит к постановке вспомогательной задачи т.н. линейного поиска (LineSearch). В данном конкретном случае различия между этими подходами невелики и рассматривать их мы не будем. Вместо этого обратим внимание на следующее:

а почему, собственно, мы ищем смещение Ох уж этот метод Ньютона - 50, лежащее именно на сфере?

В самом деле, мы вполне могли бы заменить это ограничение требованием, например, чтобы p принадлежало поверхности куба, то есть выполнялось Ох уж этот метод Ньютона - 51 (в данном случае это не слишком разумно, но почему бы и нет), или некоторой эллиптической поверхности? Это уже кажется вполне логичным, если вспомнить про проблемы, возникающие при минимизации овражных функций. Суть проблемы в том, что вдоль одних координатных линий функция изменяется существенно быстрее, чем вдоль других. Из-за этого мы получаем, что если приращение должно принадлежать сфере, то величина Ох уж этот метод Ньютона - 52, при которой обеспечивается “спуск”, должна быть очень маленькой. А это ведет к тому, что достижение минимума потребует очень большого количества шагов. Но если вместо этого взять в качестве окрестности подходящий эллипс, то эта проблема как по волшебству сойдет на нет.

Условием принадлежности точки эллиптической поверхности может быть записано в виде Ох уж этот метод Ньютона - 53, где Ох уж этот метод Ньютона - 54 – некоторая положительно определенная матрица, также называемая метрикой. Норму Ох уж этот метод Ньютона - 55 называют эллиптической нормой, индуцированной матрицей Ох уж этот метод Ньютона - 56. Что это за матрица и откуда ее взять — рассмотрим позднее, а сейчас приходим к новой задаче.

Ох уж этот метод Ньютона - 57

Квадрат нормы и множитель 1/2 здесь исключительно для удобства, чтобы не возиться с корнями. Применив метод множителей Лагранжа, получим связанную задачу безусловной оптимизации

Ох уж этот метод Ньютона - 58

Необходимым условием минимума для нее является

Ох уж этот метод Ньютона - 59, или Ох уж этот метод Ньютона - 60, откуда

Ох уж этот метод Ньютона - 61

Ох уж этот метод Ньютона - 62

Ох уж этот метод Ньютона - 63

Опять видим, что направление Ох уж этот метод Ньютона - 64, в котором мы будем двигаться, не зависит от значения Ох уж этот метод Ньютона - 65 – только от матрицы Ох уж этот метод Ньютона - 66. И снова, мы можем либо подбирать Ох уж этот метод Ньютона - 67, что чревато необходимостью вычисления Ох уж этот метод Ньютона - 68 и явного обращения матрицы Ох уж этот метод Ньютона - 69, либо решать вспомогательную задачу по поиску подходящего смещения Ох уж этот метод Ньютона - 70. Поскольку Ох уж этот метод Ньютона - 71, решение у этой вспомогательной задачи гарантированно существует.

Так что же это должна быть за матрица B? Мы ограничимся умозрительными представлениями. Если целевая функция Ох уж этот метод Ньютона - 72 – квадратичная, то есть имеет вид Ох уж этот метод Ньютона - 73, где Ох уж этот метод Ньютона - 74 положительно определена, то вполне очевидно, что наилучшим кандидатом на роль матрицы Ох уж этот метод Ньютона - 75 является гессиан Ох уж этот метод Ньютона - 76, поскольку в этом случае потребуется одна итерация построенного нами метода спуска. Если же H не является положительно определенной, то она не может являться метрикой, и построенные с ней итерации являются итерациями демпфированного метода Ньютона, но не являются итерациями метода спуска. Наконец мы можем дать строгий ответ на

Вопрос: обязана ли матрица Гессе в методе Ньютона быть положительно определенной?
Ответ: нет, не обязана ни в стандартном, ни в демпфированном методе Ньютона. Но если это условие выполнено, то демпфированный метод Ньютона является методом спуска и обладает свойством глобальной, а не только локальной сходимости.

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

Ох уж этот метод Ньютона - 77

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

Ох уж этот метод Ньютона - 78

А это мы получаем, если доверительный регион имеет форму эллипса, задаваемого обратной матрицей Гессе. Это не что иное, как итерации демпфированного метода Ньютона.

Остался нераскрытым только вопрос о том, что делать, если матрица Гессе не является положительно определенной. Вариантов много. Первый — забить. Может, вам повезет и итерации Ньютона сойдутся и без этого свойства. Такое вполне реально, особенно на финальных этапах процесса минимизации, когда вы уже достаточно близки к решению. В таком случае можно использовать итерации стандартного метода Ньютона, не утруждая себя поисками допустимой для спуска окрестности. Либо использовать итерации демпфированного метода Ньютона и в случае Ох уж этот метод Ньютона - 79, то есть в случае, когда полученное направление не является направлением спуска, поменять его, скажем, на антиградиент. Только не надо явным образом проверять, является ли гессиан положительно определенным по критерию Сильвестра, как это делалось здесь!!!. Это расточительно и бессмысленно.
Более тонкие методы предполагают построение матрицы, в некотором смысле близкую к матрице Гессе, но обладающую свойством положительной определенности, в частности, путем коррекции собственных значений. Отдельную тему составляют квазиньютоновские методы, или методы переменной метрики, которые гарантируют положительную определенность матрицы B и не требуют вычисления вторых производных. В общем, подробное обсуждение этих вопросов сильно выходит за рамки данной статьи.

Да, и кстати, из сказанного следует, что демпфированный метод Ньютона при положительной определенности гессиана — градиентный метод. Как и квазиньютоновские методы. И многие другие, основанные на раздельном выборе направления и величины шага. Так что противопоставлять метод Ньютона градиентным терминологически неверно.

Подытожим

Метод Ньютона, о котором часто вспоминают при обсуждении методов минимизации — это как правило вовсе не метод Ньютона в его классическом понимании, а метод спуска с метрикой, задаваемой обратным гессианом целевой функции. И да, он сходится глобально в случае, если гессиан всюду положительно определен. Это возможно только для выпуклых функций, которые в практике встречаются гораздо реже, чем хотелось бы, так что в общем случае без соответствующих модификаций применение метода Ньютона (все же не будем отрываться от коллектива и продолжим называть его так) не гарантирует правильного результата. Обучение нейросетей, даже неглубоких, обычно приводит к невыпуклым задачам оптимизации с множеством локальных минимумов. И здесь новая засада. Метод Ньютона обычно сходится (если сходится) быстро. В смысле очень быстро. И это, как ни странно, плохо, поскольку мы за несколько итераций приходим к локальному минимуму. А он для функций со сложным рельефом может быть намного хуже глобального. Градиентный спуск с линейным поиском сходится гораздо медленнее, но с большей вероятностью “перескакивает” хребты целевой функции, что очень важно на ранних этапах минимизации. Если вы уже неплохо уменьшили величину целевой функции, а сходимость градиентного спуска существенно замедлилась, то здесь изменение метрики вполне может ускорить процесс, но это — для конечных стадий.

Разумеется, данный аргумент не универсален, не бесспорен и в ряде случаев даже неверен. Как и само утверждение о том, что градиентные методы лучше всех работают в задачах обучения.

Автор: alexkolzov

Источник

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


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