Сравнительный анализ алгоритмов первого и второго порядков для обучения глубоких искусственных нейронных сетей

Размещено на http://www.allbest.ru/

АО «Концерн «Созвездие» (АО «Концерн «Созвездие»)

Сравнительный анализ алгоритмов первого и второго порядков для обучения глубоких ИНС

А.Б. Муравник

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

Методы первого порядка (градиентные методы): преимущества и недостатки

Если целевая функция ограничена снизу и дифференцируема, то алгоритм поиска точки ее минимума можно построить, используя информацию о ее градиенте. Поэтому указанные методы называются градиентными. Такие методы являются методами линейной аппроксимации на каждом шаге, поскольку целевая функция на каждом шаге заменяется гиперплоскостью (в случае одной независимой переменной - прямой), касательной к ее графику в текущей точке. Применяя любой из методов первого порядка, мы предполагаем непрерывность самой целевой функции f и ее градиента, а каждый из этих методов основан на итерационной процедуре, определяемой формулой x(k+1) = x(k)+бkS(k), где k - номер шага (итерации), бk - величина шага, а S(k) - вектор в направлении x(k+1) ? x(k).

Методы первого порядка отличаются друг от друга лишь способом задания шага бk, в то время как S(k) определяется путем решения задачи оптимизации целевой функции в направлении S(k), а это направление зависит от того, каким именно образом аппроксимируется целевая функция. Выбором указанного направления определяется каждый конкретный метод первого порядка.

Метод Коши (наискорейшего спуска)

В этом методе в качестве направления S(k) (направление поиска) выбирается антиградиент целевой функции, т.е. направление, противоположное направлению наибольшего возрастания ее значения.

Методы сопряженных градиентов (направлений)

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

Особенности градиентных методов

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

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

Методы второго порядка (Ньютоновские методы): преимущества и недостатки

Методы второго порядка (Ньютоновские методы) используют информацию не только о градиенте целевой функции, но и о ее матрице Гессе (разумеется, в предположении о двукратной дифференцируемости целевой функции). В отличие от методов первого порядка, использующих линейную аппроксимацию целевой функции для выбора направления поиска (на каждой итерации), Ньютоновские методы используют для этого ее квадратичную аппроксимацию, получаемую Тейлоровским разложением вплоть до членов второго порядка. Если минимум целевой функции существует, то он достигается там же, где и минимум квадратичной формы ц(x), порождаемой указанным разложением. Если матрица Гессе Н(х(k)) целевой функции, вычисленная в точке х(k), является положительно определенной, то точка х(k+1) минимума функции ц(x), а значит, и искомого минимума целевой функции, единственна и может быть найдена из условия, что ее градиент равен нулевому вектору, что дает следующую формулу для ее вычисления: х(k+1) = х(k) - Н-1(х(k))?f(х(k)). Таким образом, направление поиска принимает вид - Н-1(х(k))?f(х(k)), что, вообще говоря, составляет тупой угол с вектором градиента (т.н. Ньютоновское направление).

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

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

Модификации классического метода Ньютона

Все модификации метода Ньютона основаны на следующем общем принципе: там, где возможно использовать Ньютоновское направление, используется оно, а отклонения от него используются только тогда, когда его использовать невозможно. На каждой итерации сначала строится некоторая «связанная» с матрицей Гессе положительно определенная матрица Hk (а если сама матрица Гессе положительно определена, то она и берется в качестве Hk), а затем направление спуска S(k) определяется из следующего условия: HkS(k) = -?f(х(k)) либо, что эквивалентно, S(k) = (вkI - Н(х(k-1)))-1?f(х(k-1)), где I - единичная матрица порядка n, а вk - параметр, выбираемый так, чтобы в точке х(k-1) матрица Hk = вkI - Н(х(k-1)) была положительно определена. Так как Hk положительно определена, то направление S(k) обязательно будет направлением спуска.

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

Особенности Ньютоновских методов

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

Основной недостаток методов второго порядка - значительный, сравнительно с градиентными методами, рост вычислительных затрат (а это не только расходует машинное время, но и приводит к значительным вычислительным погрешностям). Даже в тех случаях, когда решение находится всего за одну итерацию, для этой итерации требуется вычислить n частных производных первого порядка и n(n+1)/2 производных второго порядка. Если же требуется еще и обратимость матрицы Гессе, то количество необходимых вычислительных операций достигает (по порядку) n3, что на два порядка больше, чем для методов сопряженных направлений.

Это обстоятельство обусловливает интерес к разнообразным комбинациям методов первого и второго порядка.

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

Данный метод является комбинацией методов Ньютона (второго порядка) и Коши (первого порядка), суть которой заключается в следующем: вдали от точки минимума направление поиска определяется методом Коши, а в окрестности точки минимума -методом Ньютона. Чтобы найти направление поиска, решается система линейных уравнений (J(х(k))T J(х(k))+лkI)S(k) = -J(х(k)) F(х(k)), где F - невязка, J - якобиан, а скалярная величина лk определяет как величину, так и направление векторного параметра S(k). Когда лk = 0, направление S(k) совпадает с этим же направлением из метода Ньютона-Гаусса. Если лk ?, то S(k) стремится к вектору с нулевыми компонентами и направлению наискорейшего спуска.

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

Приложение к нейросетям

Задача об обучении ИНС (в том числе - глубокой, т.е. имеющей более одного скрытого слоя), трактуемая в рамках теории оптимизации и экстремальных задач, есть задача с целевой функцией вида суммы квадратов (поскольку задача обучения ИНС - минимизировать ошибку обучения, представляющую собой сумму квадратов отклонений значений ИНС от заданных значений обучающей выборки). Таким образом, исходя из вышеизложенного, есть основания ожидать наибольшей эффективности указанного метода в задачах обучения глубоких ИНС (см., напр., [3,5]).

Это полностью подтверждается обучением глубоких (19-13-12, 30-40-12, 40-15-12, 35-15-12 и 25-12-12) ИНС в задаче классификации, выполненным в [2] (ср. [1]): сравнительно с алгоритмом сопряженных градиентов (метод первого порядка), скорость обучения ИНС при помощи алгоритма Левенберга-Марквардта (метод второго порядка) возросла на порядок. Более того, обучить некоторые глубокие ИНС с архитектурой, обладающей хорошими обобщающими способностями (100% правильных решений задач классификации) методом сопряженных градиентов вообще невозможно, а применение алгоритма Левенберга-Марквардта эту задачу решает.

Заключение

Сравнительный анализ методов первого и второго порядков поиска экстремума приводит к следующим выводам относительно их применимости в задачах обучения глубоких искусственных нейронных сетей:

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

для задач обучения ИНС (являющихся, с точки зрения теории экстремальных задач, задачами минимизации квадратичных функций) методы второго порядка дают решение за одну итерацию;

у некоторых глубоких (многослойных) ИНС, наиболее подходящих для задач классификации, архитектура настолько сложна, что они не поддаются обучению методами первого порядка (но поддаются обучению методами второго порядка);

при переходе от методов первого порядка к методам второго порядка вычислительные затраты возрастают лавинообразно, что составляет существенный недостаток методов второго порядка;

применительно к задачам обучения глубоких ИНС, вызывают наибольший интерес (и демонстрируют наибольшую эффективность) алгоритмы, объединяющие преимущества методов первого и второго порядка следующим образом: вдали от точки минимума направление поиска определяется методом первого порядка, а в окрестности точки минимума - методом второго порядка.

Литература

1. Данильченко М.Н., Пядухова К.В., Голубинский А.Н. Нейросетевая модель управления связью и радиоэлектронным подавлением в интегрированной системе // XXIV международная научно-техническая конференция «Радиолокация, навигация, связь». - Т. 5. - Воронеж: ООО «Вэлборн». 2018. - С. 361- 368.

2. Данильченко М.Н., Рябков Н.М., Пядухова К.В., Голубинский А.Н. Классификация уровня формирования с использованием искусственных нейронных сетей // XXV международная научно-техническая конференция «Радиолокация, навигация, связь» (в печати).

3. Захарова Е.М. Обзор методов многомерной оптимизации / Захарова Е.М., Минашина И.К. // Информационные процессы, 2014, Т. 4, №3. - С. 256-274

4. Ловецкий К.П., Севастьянов Л.А., Паукшто М.В., Бикеев О.Н. Математический синтез оптических наноструктур. М.: Российский университет дружбы народов, 2008. - 123 с.

Аннотация

Для задач обучения глубоких искусственных нейронных сетей сравниваются два класса алгоритмов поиска экстремума: методы первого порядка и методы первого порядка.

Ключевые слова: глубокие ИНС; задачи обучения; методы поиска экстремума.

Размещено на Allbest.ru