Нейрокомпьютерные системы



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


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

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}
- плохое направление спуска, т.е. движение вдоль него приводит к слишком маленькому шагу либо вообще не дает улучшения.




Содержание  Назад  Вперед