Персональный сайт Red Stone:redstonewill.com
Ранее я публиковал статью, в которой популярно объяснял математический принцип и процесс вывода алгоритма градиентного спуска, рекомендую вам взглянуть. Ссылка выглядит следующим образом:
Мы знаем, что алгоритм градиентного спуска использует градиенты для оптимизации первого порядка, в то время как алгоритм оптимизации Ньютона, который я представил сегодня, использует оптимизацию второго порядка. В этой статье основное внимание будет уделено объяснению основных концепций и процессу вывода метода Ньютона, а также сравнению градиентного спуска с методом Ньютона.
1. Метод Ньютона решения корней уравнения.
Иногда, в случае сложного уравнения, решить его корни общими методами непросто. Метод Ньютона может аппроксимировать более точные корни уравнения с помощью итерационного метода и идеи непрерывной аппроксимации.
Основной идеей метода Ньютона для нахождения корней является разложение Тейлора первого порядка. Например, для уравнения f(x) = 0 мы выполняем разложение Тейлора первого порядка в любой точке x0:
Пусть f(x) = 0, и подведя его к приведенной выше формуле, можно получить:
Обратите внимание, что здесь используется приближение, и полученный x не является корнем уравнения, а является приблизительным решением. Однако x ближе к корням уравнения, чем x0. Результаты, как показано ниже:
Затем решите его итеративно, приняв x за x0, и найдите следующую позицию ближе к корню уравнения. Итеративную формулу можно записать в виде:
После определенного количества допустимых итераций сходимость в корнях уравнения обычно гарантируется. Динамическая демонстрация всего итеративного процесса сходимости приведена ниже.
2. Метод выпуклой оптимизации Ньютона.
В предыдущем разделе было показано, как метод Ньютона решает корни уравнения, свойство, которое можно применять к задачам оптимизации выпуклых функций.
В машинном обучении и глубоком обучении проблема оптимизации функции потерь обычно основана на градиентном спуске по первой производной. Теперь, с другой точки зрения, попытка минимизировать функцию потерь на самом деле является максимальной задачей, соответствующей первой производной функции f'(x) = 0. То есть, если мы находим точку x, где f'(x) = 0, функция потерь минимизируется, и цель оптимизации модели достигается.
Теперь цель состоит в том, чтобы вычислить x, соответствующий f'(x) = 0, корень f'(x) = 0. Преобразовав в корневую проблему, вы можете использовать метод Ньютона из предыдущего раздела.
В отличие от предыдущего раздела, во-первых, выполните разложение Тейлора второго порядка для f (x) в точке x0:
Приведенная выше формула верна, если f(x) приблизительно равно f(x0). Пусть f(x) = f(x0) и возьмем производную от (x - x0), получим:
Кроме того, хотя x не является оптимальной точкой решения, x ближе к корню f'(x) = 0, чем x0. Таким образом, можно получить оптимизированную итеративную формулу:
С помощью итерационной формулы можно непрерывно находить приблизительный корень f'(x) = 0, тем самым достигая цели оптимизации по минимизации функции потерь.
3. Градиентный спуск против метода Ньютона
Теперь напишите обновленные формулы для градиентного спуска и метода Ньютона соответственно:
Алгоритм градиентного спуска представляет собой аппроксимацию функции в позиции xn, то есть прямой линии. Вычислите градиент, чтобы определить направление следующей оптимизации, противоположное направлению градиента. Метод Ньютона заключается в аппроксимации функции в положении xn функцией второго порядка, то есть квадратичной кривой. Вычислите градиент и вторую производную, чтобы определить следующее направление оптимизации. Схематические диаграммы оптимизации первого порядка и оптимизации второго порядка выглядят следующим образом:
Градиентный спуск, оптимизация первого порядка:
Метод Ньютона, оптимизация второго порядка:
Вышесказанное является отличием методов оптимизации градиентного спуска от метода Ньютона. Так чей эффект оптимизации лучше?
Во-первых, давайте посмотрим на преимущества метода Ньютона. Во-первых, в формуле итеративного обновления метода Ньютона нет фактора обучения параметра, поэтому нет необходимости выбирать соответствующий фактор обучения посредством перекрестной проверки. Во-вторых, считается, что метод Ньютона может использовать информацию о самой кривой, и он легче сходится (меньше итераций), чем метод градиентного спуска. На следующем рисунке показан пример минимизации целевого уравнения.Красная кривая решена итеративно методом Ньютона, а зеленая кривая решена методом градиентного спуска. Очевидно, что метод Ньютона оптимизируется быстрее.
Затем давайте рассмотрим недостатки метода Ньютона. Мы заметили, что в итерационной формуле метода Ньютона помимо решения первой производной вычисляется и вторая производная. С матричной точки зрения первая производная и вторая производная соответствуют матрице Якоби и матрице Гессе соответственно.
Матрица Якоби:
Матрица Гессе:
Метод Ньютона требует вычисления не только гессиана, но и обратного гессиана. Когда объем данных относительно невелик, скорость работы не сильно пострадает. Однако, когда количество данных велико, особенно в глубоких нейронных сетях, вычисление матрицы Гессе и ее обратной требует очень много времени. В целом скорость оптимизации метода Ньютона не такая высокая, как у алгоритма градиентного спуска. Поэтому большинство современных стратегий оптимизации функций потерь нейронной сети основаны на градиентном спуске.
Стоит отметить, что уже есть некоторые улучшенные алгоритмы для устранения недостатков метода Ньютона. Такие улучшенные алгоритмы в совокупности называются квазиньютоновскими алгоритмами. Наиболее представительными из них являются BFGS и L-BFGS.
Алгоритм BFGS использует приближенный метод для вычисления обратной матрицы Гессе, что эффективно повышает скорость работы. Однако всю аппроксимированную обратную матрицу Гессе все же необходимо хранить, а объем памяти велик.
Алгоритм L-BFGS является усовершенствованием алгоритма BFGS, ему не нужно хранить приблизительную обратную матрицу Гессе, а напрямую получает направление поиска текущего раунда с помощью итеративного алгоритма, что значительно снижает затраты на пространство.
В целом в практических приложениях более широко используются алгоритмы оптимизации, основанные на градиентном спуске, такие как RMSprop, Adam и др. Однако усовершенствованные алгоритмы метода Ньютона, такие как BFGS и L-BFGS, также имеют свои особенности и большую практичность.