Ох уж этот метод Ньютона
О методах численной оптимизации написано много. Это и понятно, особенно на фоне тех успехов, которые в последнее время демонстрируют глубокие нейронные сети. И очень отрадно, что хотя бы часть энтузиастов интересуется не только тем, как забомбить свою нейросеточку на набравшей в этих ваших интернетах популярность фреймворках, но и тем, как и почему все это вообще работает. Однако мне в последнее время пришлось отметить, что при изложении вопросов, связанных с обучением нейросетей (и не только с обучением, и не только сетей), в том числе на Хабре, все чаще впроброс используется ряд “хорошо известных” утверждений, справедливость которых, мягко говоря, сомнительна. Среди таких сомнительных утверждений:
- Методы второго и более порядков плохо работают в задачах обучения нейросетей. Потомучто.
- Метод Ньютона требует положительной определенности матрицы Гессе (вторых производных) и поэтому плохо работает.
- Метод Левенберга-Марквардта — компромисс между градиентным спуском и методом Ньютона и вообще эвристичекий.
и т.д. Чем продолжать этот список, лучше перейдем к делу. В этом посте рассмотрим второе утверждение, поскольку его я только на Хабре встречал как минимум дважды. Первый вопрос затрону только в той части, что касается метода Ньютона, поскольку он куда более обширен. Третий и остальные оставим до лучших времен.
Центром нашего внимания будет задача безусловной оптимизации
Решить уравнение
Задача, мягко говоря, непростая. Точно не проще, чем исходная. Однако на этом моменте сразу можно отметить связь между задачей минимизации и задачей решения системы нелинейных уравнений. Эта связь нам еще аукнется при рассмотрении метода Левенберга-Марквардта (когда до него доберемся). А пока вспомним (или узнаем), что одним из наиболее часто применяемых методов для решения систем нелинейных уравнения является метод Ньютона. Заключается он в том, что для решения уравнения
или
где
Метод Ньютона для решения систем нелинейных уравнений весьма неплохо изучен. И вот ведь штука — для его сходимости не требуется положительная определенность матрицы
Так?
И да, и нет. Засада здесь в слове локальная перед словом сходимость. Оно означает, что начальное приближение
Здесь последовательность
когда направление, генерируемое методом Ньютона, является направлением спуска?
И для ответа на него придется посмотреть на задачу минимизации с другого бока.
Методы спуска
Для задачи минимизации вполне естественным кажется такой подход: начиная с некоторой произвольной точки, выберем некоторым образом направление p и сделаем в этом направлении шаг
и если
У этой задачи есть очевидное решение:
в котором мы узнаем широко известный метод градиентного спуска. Параметр
Исходя из свойств построенной модели целевой функции мы можем утверждать, что найдется такое
- Подбирать по некоторой методике величину
. - Поставить задачу выбора соответствующего значения
, обеспечивающее уменьшение значения целевой функции.
Первый подход характерен для методов доверительного региона, второй приводит к постановке вспомогательной задачи т.н. линейного поиска (LineSearch). В данном конкретном случае различия между этими подходами невелики и рассматривать их мы не будем. Вместо этого обратим внимание на следующее:
а почему, собственно, мы ищем смещение
В самом деле, мы вполне могли бы заменить это ограничение требованием, например, чтобы p принадлежало поверхности куба, то есть выполнялось
Условием принадлежности точки эллиптической поверхности может быть записано в виде
Квадрат нормы и множитель 1/2 здесь исключительно для удобства, чтобы не возиться с корнями. Применив метод множителей Лагранжа, получим связанную задачу безусловной оптимизации
Необходимым условием минимума для нее является
Опять видим, что направление
Так что же это должна быть за матрица B? Мы ограничимся умозрительными представлениями. Если целевая функция
Вопрос: обязана ли матрица Гессе в методе Ньютона быть положительно определенной?
Ответ: нет, не обязана ни в стандартном, ни в демпфированном методе Ньютона. Но если это условие выполнено, то демпфированный метод Ньютона является методом спуска и обладает свойством глобальной, а не только локальной сходимости.
В качестве иллюстрации посмотрим, как выглядят доверительные регионы в случае минимизации всем известной функции Розенброка методами градиентного спуска и методом Ньютона, и как форма регионов влияет на сходимость процесса.
Вот так ведет себя метод спуска со сферическим доверительным регионом, он же — градиентный спуск. Все как по учебнику — мы застряли в каньоне.
А это мы получаем, если доверительный регион имеет форму эллипса, определяемого матрицей Гессе. Это не что иное, как итерации демпфированного метода Ньютона.
Остался нераскрытым только вопрос о том, что делать, если матрица Гессе не является положительно определенной. Вариантов много. Первый — забить. Может, вам повезет и итерации Ньютона сойдутся и без этого свойства. Такое вполне реально, особенно на финальных этапах процесса минимизации, когда вы уже достаточно близки к решению. В таком случае можно использовать итерации стандартного метода Ньютона, не утруждая себя поисками допустимой для спуска окрестности. Либо использовать итерации демпфированного метода Ньютона и в случае
Более тонкие методы предполагают построение матрицы, в некотором смысле близкую к матрице Гессе, но обладающую свойством положительной определенности, в частности, путем коррекции собственных значений. Отдельную тему составляют квазиньютоновские методы, или методы переменной метрики, которые гарантируют положительную определенность матрицы B и не требуют вычисления вторых производных. В общем, подробное обсуждение этих вопросов сильно выходит за рамки данной статьи.
Да, и кстати, из сказанного следует, что демпфированный метод Ньютона при положительной определенности гессиана — градиентный метод. Как и квазиньютоновские методы. И многие другие, основанные на раздельном выборе направления и величины шага. Так что противопоставлять метод Ньютона градиентным терминологически неверно.
Подытожим
Метод Ньютона, о котором часто вспоминают при обсуждении методов минимизации — это как правило вовсе не метод Ньютона в его классическом понимании, а метод спуска с метрикой, задаваемой гессианом целевой функции. И да, он сходится глобально в случае, если гессиан всюду положительно определен. Это возможно только для выпуклых функций, которые в практике встречаются гораздо реже, чем хотелось бы, так что в общем случае без соответствующих модификаций применение метода Ньютона (все же не будем отрываться от коллектива и продолжим называть его так) не гарантирует правильного результата. Обучение нейросетей, даже неглубоких, обычно приводит к невыпуклым задачам оптимизации с множеством локальных минимумов. И здесь новая засада. Метод Ньютона обычно сходится (если сходится) быстро. В смысле очень быстро. И это, как ни странно, плохо, поскольку мы за несколько итераций приходим к локальному минимуму. А он для функций со сложным рельефом может быть намного хуже глобального. Градиентный спуск с линейным поиском сходится гораздо медленнее, но с большей вероятностью “перескакивает” хребты целевой функции, что очень важно на ранних этапах минимизации. Если вы уже неплохо уменьшили величину целевой функции, а сходимость градиентного спуска существенно замедлилась, то здесь изменение метрики вполне может ускорить процесс, но это — для конечных стадий.
Разумеется, данный аргумент не универсален, не бесспорен и в ряде случаев даже неверен. Как и само утверждение о том, что градиентные методы лучше всех работают в задачах обучения.