Допустим, у вас есть дар полета (или вы едете на вертолете). Вы также шпион (как в фильмах о Джеймсе Бонде). Вам дается топография длинной узкой долины, как показано на изображении, и вам дается место встречи для встречи с потенциальным помощником, обладающим интеллектом, полезным для вашей цели. Единственная имеющаяся у вас информация о месте встречи следующая:

«Встретимся у самой нижней координаты« этой длинной долины »через 4 часа»

Как вы собираетесь найти самую низкую точку координат? Более того, как вы собираетесь найти его в оговоренный период времени?

Что ж, для сложных нейронных сетей с очень большими параметрами поверхность ошибок нейронной сети очень похожа на своего рода длинную узкую долину. Найти «минимумы» в долине может быть довольно сложно, когда у вас есть такие патологические искривления в вашей топографии.

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

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

Из-за этого этот пост должен быть немного длинным.

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

Ограничения градиентного спуска

Нет ничего принципиально неправильного в алгоритме градиентного спуска (точнее, стохастического градиентного спуска (SGD)]. Фактически, мы доказали, что это довольно эффективно для некоторых примеров с прямой связью, которые мы использовали в прошлом. Проблема SGD возникает, когда у нас есть «глубокие» нейронные сети, которые имеют более одного скрытого слоя. Особенно, когда Сеть достаточно большая.

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

Обратите внимание, что на иллюстрации много минимумов и максимумов. Давайте быстро рассмотрим процесс обновления веса в SGD.

Проблема с использованием SGD для иллюстраций заключается в следующем:

  • Поскольку SGD использует метод оптимизации первого порядка, он предполагает, что поверхность ошибки всегда выглядит как плоскость (то есть в направлении спуска) и не учитывает кривизну.
  • Когда есть квадратичная кривизна, мы применяем некоторые приемы, чтобы гарантировать, что SGD не просто отскакивает от поверхности, как показано в уравнении обновления веса.
  • Мы контролируем значение импульса с помощью некоторого заранее определенного альфа и управляем скоростью, применяя скорость обучения эпсилон.
  • Альфа и эпсилон буферизируют скорость и направление SGD и замедляют оптимизацию до тех пор, пока мы не сойдемся. Мы можем только настроить эти гиперпараметры, чтобы получить хороший баланс скорости и эффективности SGD. Но они все равно нас тормозят.
  • В больших сетях с патологическими искривлениями, как показано на рисунке, настройка этих гиперпараметров является довольно сложной задачей.
  • Ошибка в SGD может внезапно начать расти, когда вы двигаетесь в направлении градиента, когда вы пересекаете длинную узкую долину. Фактически, SGD может практически остановиться, прежде чем вообще сможет добиться какого-либо прогресса.

Нам нужен лучший метод для работы с большими или глубокими нейронными сетями.

Оптимизация второго порядка приходит на помощь

SGD - это задача оптимизации первого порядка. Методы первого порядка - это методы, которые имеют линейные локальные кривые. При этом мы предполагаем, что можем применять линейные приближения для решения уравнений. Вот некоторые примеры методов первого порядка:

  • Градиентный спуск
  • Субградиент
  • Сопряженный градиент
  • Случайный координатный спуск

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

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

Если вы новичок в квадратичных приближениях, я рекомендую вам проверить эту Лекцию Академии Хана о квадратичных приближениях.

Преимущество метода второго порядка состоит в том, что он не должен игнорировать кривизну поверхности ошибки. Из-за того, что учитывается кривизна, считается, что методы второго порядка имеют лучшие ступенчатые характеристики.

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

Ниже приведены некоторые методы второго порядка.

  • Метод Ньютона
  • Квазиньютон, Гаусс-Ньютон
  • BFGS, (L) BFGS

Давайте посмотрим на метод Ньютона, который является базовым и немного более интуитивно понятным по сравнению с другими.

Эй! Ньютон, какой у вас метод?

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

Давайте сначала посмотрим на метод Ньютона, использующий первую производную функции.

Допустим, у нас есть функция f (x) = 0, и у нас есть некоторое начальное решение x_0, которое мы считаем неоптимальным. Затем метод Ньютона предлагает нам сделать следующее

  1. Найдите уравнение касательной в точке x_0
  2. Найдите точку, в которой касательная линия пересекает ось x, и назовите эту новую точку как x_1.
  3. Найдите проекцию x_1 на функцию f (x) = 0, которая также находится в x_1.
  4. Теперь повторите итерацию с шага 1, заменив x_0 на x_1.

Действительно так просто. Предостережение заключается в том, что метод не сообщает вам, когда следует остановиться, поэтому мы добавляем 5-й шаг следующим образом:

5. Если x_n (текущее значение x) равно или меньше порогового значения, мы останавливаемся.

Вот изображение, изображающее вышесказанное:

Вот анимация, которая показывает то же самое:

Полином первой степени, одномерный:

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

Полином второй степени, одномерный

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

Многочлен второй степени, многомерный

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

Матрица Гессе - это квадратная матрица частных производных второго порядка от скаляра, которая описывает локальную кривизну функции с несколькими переменными.

В частности, в случае нейронной сети, гессиан представляет собой квадратную матрицу с количеством строк и столбцов, равным общему количеству параметров в нейронной сети.

Гессиан для нейронной сети выглядит следующим образом:

Почему теоретически подход, основанный на Гессе, лучше, чем SGD?

Теперь оптимизация второго порядка с использованием метода Ньютона итеративного нахождения оптимального 'x' - это умный прием для оптимизации поверхности ошибки, потому что, в отличие от SGD, где вы помещаете плоскость в точку x_0, а затем определяете ступенчатый скачок, при оптимизации второго порядка мы находим точно подходящую квадратичную кривую в точке x_0 и непосредственно находим минимумы кривизны. Это в высшей степени эффективно и быстро.

Но !!! Однако эмпирически можно ли теперь представить себе вычисление гессиана для сети с миллионами параметров? Конечно, это становится очень неэффективным, поскольку объем памяти и вычислений, необходимых для вычисления гессиана, также имеет квадратичный порядок. Так что, хотя в теории это круто, на практике - отстой.

Нам нужен хак для взлома! И ответ, кажется, кроется в сопряженных градиентах.

Сопряжение градиентов, хитрый трюк.

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

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

Если вам нужно подробное введение в методы сопряженных градиентов, прочтите статью Джонатана Ричарда Шевчука Введение в метод сопряженных градиентов без мучительной боли. Я считаю это довольно подробным и полезным. Я бы посоветовал вам изучить статью в свободное время, чтобы получить более глубокое представление о сопряженных градиентах.

Самый простой способ объяснить сопряженный градиент (CG) следующий:

  • CG Descent применим к любой квадратичной форме.
  • CG использует значение «альфа» размера шага, подобное SGD, но вместо фиксированного альфа мы находим альфа с помощью алгоритма линейного поиска.
  • CG также нуждается в «бета» скалярном значении, которое помогает найти следующее направление, которое «сопряжено» с первым направлением.

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

Для решения уравнения Ax = b мы можем использовать следующий алгоритм:

  • Здесь r_k - остаточная стоимость,
  • p_k - сопряженный вектор и,
  • x_k + 1 итеративно обновляется предыдущим значением x_k и скалярным произведением размера шага alpha_k и сопряженного вектора p_k.

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

Алгоритм оптимизации без гессиана

Теперь, когда мы разобрались с алгоритмом компьютерной графики, давайте посмотрим на последний хитрый прием, который позволяет нам избавиться от гессенской теории.

ЦИТИРОВАНИЕ: Оптимизация без использования Гессе - это метод, принятый для нейронных сетей Джеймсом Мартеном из Университета Торонто в статье Глубокое обучение с помощью бесплатной оптимизации по Гессену.

Начнем с разложения функции Тейлора второго порядка:

Здесь нам нужно найти лучший delta_x, а затем перейти к x + delta_x и продолжать итерацию до схождения. Другими словами, этапы оптимизации без гессиана следующие:

Алгоритм:

  1. Начните с i = 0 и повторите
  2. Пусть x_i будет некоторым начальным субоптимальным x_0, выбранным случайным образом.
  3. При текущем x_n, учитывая расширение Тейлора, показанное выше, вычислить градиент f (x_n) и гессиан f (x_n)
  4. Учитывая расширение Тейлора, вычислите следующий x_n + 1 (который есть не что иное, как delta_x), используя алгоритм сопряженного градиента.
  5. Повторяйте шаги 2–4, пока текущий x_n не сойдется.

Важное понимание: Обратите внимание, что в отличие от метода Ньютона, где гессиан необходим для вычисления x_n + 1, в алгоритме без гессиана нам не нужен гессиан для вычисления x_n + 1. Вместо этого мы используем сопряженный градиент.

Умный прием: поскольку гессиан используется вместе с вектором x_n, нам просто нужна аппроксимация гессиана вместе с вектором, и нам НЕ нужен точный гессиан. Аппроксимация гессиана вектором намного быстрее, чем вычисление самого гессиана. Проверьте следующие рассуждения.

Взгляните еще раз на гессен:

Здесь i-я строка содержит частные производные вида

Где «i» - это индекс строки, а «j» - индекс столбца. Следовательно, скалярное произведение матрицы Гессе и любого вектора:

Вышеупомянутое дает производную по направлению от «e» относительно «w» в направлении «v».

Затем, используя конечные разности, мы можем оптимизировать вышеуказанное следующим образом:

Фактически, подробное объяснение и методика быстрого умножения гессиана на вектор доступны в статье Барака А. Перлмуттера из Siemens Corporate Research под названием Быстрое точное умножение гессиана.

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

Чтобы понять влияние метода оптимизации, посмотрите следующую иллюстрацию.

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

Судя по всему, быть шпионом непросто…