Партан-методы

Для исправления недостатков наискорейшего спуска разработаны итерационный и модифицированный партан-методы.

Итерационный партан-метод ( \[ k \] -партан) строится следующим образом. В начальной точке \[ w^0 \] вычисляется градиент оценки \[ E \] и делается шаг наискорейшего спуска - для этого используется одномерная оптимизация. Далее снова вычисляется градиент \[ E \] и выполняется спуск (т.е. перемещение в направлении антиградиента), и описанный процесс повторяется \[ k \] раз. После \[ k \] шагов наискорейшего спуска получаем точку \[ w^k \] и проводим одномерную оптимизацию из \[ w^0 \] в направлении \[ s = w^k - w^0 \] с начальным шагом \[ \alpha = 1 \] . После этого цикл повторяется.

Модифицированный партан-метод требует запоминания дополнительных параметров. Он строится следующим образом. Из \[ w^0 \] делается два шага наискорейшего спуска. Получаем \[ w^1 \] и \[ w^2 \] . Далее выполняем одномерную оптимизацию в направлении \[ w^2 - w^0 \] . Получаем \[ w^3 \] . Далее выполняется наискорейший спуск из \[ w^3 \] . Получаем \[ w^4 \] . Выполняем одномерную оптимизацию из \[ w^2 \] в направлении \[ w^4 - w^2 \] . Получаем \[ w^5 \] и~т.д. Таким образом, четные \[ w^{2k} \] получаем наискорейшим спуском из \[ w^{2k-1} \] , нечетные \[ w^{2k+1} \] - одномерной оптимизацией из \[ w^{2k-2} \] в направлении \[ s = w^{2k} - w^{2k-2} \] (начальный шаг \[ \alpha = 1 \] ). Как показала практика, модифицированный партан-метод в задачах обучения работает лучше, чем \[ k \] -партан.

Одношаговый квазиньютоновский метод и сопряженные градиенты

В тех случаях, когда является положительно определенной матрица \[ D_2 \] вторых производных оценки \[ E \] , наилучшим считается ньютоновское направление

\[ \begin{align*} s = - D_2^{-1}\nabla E. \end{align*} \]

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

1. Время. Поиск всех вторых производных функции \[ E \] и обращение матрицы \[ D_2 \] требует больших вычислительных затрат.
2. Память. Для решения задач большой размерности \[ N \] требуется хранить \[ N^2 \] элементов матрицы \[ D_2^{-1} \] — это слишком много.
3. Матрица \[ D_2 \] не всегда является положительно определенной.

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

Простейший и весьма эффективный метод основан на \[ BFGS \] формуле (Брайден-Флетчер-Гольдфард-Шанно) и использует результаты предыдущего шага. Обозначим:

\[ s_k \] - направление спуска на \[ k \] -шаге;

\[ \alpha_k \] - величина \[ k \] шага ( \[ k \] -й шаг - сдвиг на \[ \alpha_k s_k \] );

\[ g_k \] - градиент функции оценки в начальной точке \[ k \] -го шага;

\[ y_k=g_k - g_{k-1} \] - изменение градиента в результате \[ k \] -го шага.

\[ BFGS \] - формула для направления спуска на \[ k+1 \] -м шаге имеет вид:

\[ \begin{align*} s_{k+1} = - g_{k+1}+[(s_k,g_{k+1})y_k+(y_k,g_{k+1})s_k]/(y_k,s_k)-\\ - h_ks_k(s_k,g_{k+1})/(y_k,s_k) - s_k(y_k,y_k)\cdot(s_k,g_{k+1})/(y_k,s_k)^2, \end{align*} \]

где \[ (x,y) \] - скалярное произведение векторов \[ x \] и \[ y \] .

Если одномерную оптимизацию в поиске шага проводить достаточно точно, то новый градиент \[ g_{k+1} \] будет практически ортогонален предыдущему направлению спуска, т.е. \[ (s_k,g_{k+1})=0 \] . При этом формула для \[ s_{k+1} \] упрощается:

\[ \begin{align*} s_{k+1} = - g_{k+1} + s_k(y_k,g_{k+1}) /(y_k,s_k). \end{align*} \]

Это - формула метода сопряженных градиентов (МСГ), которому требуется достаточно аккуратная одномерная оптимизация при выборе шага.

В описанных методах предполагается, что начальное направление спуска \[ s_0 = -g_0 \] . После некоторой последовательности из \[ k \] шагов целесообразно возвращаться к наискорейшему спуску - проводить рестарт. Он используется в тех случаях, когда очередное \[ s_{k+1} \] - плохое направление спуска, т.е. движение вдоль него приводит к слишком маленькому шагу либо вообще не дает улучшения.