О методах обучения
многослойных нейронных сетей
прямого распространения.
Часть 3: Градиентные методы второго порядка.
Е.С.Борисов
среда, 2 марта 2016 г.
Этот текст является прололжением
статьи
о методах обучения многослойных нейронных сетей прямого распространения. Здесь мы поговорим о применении
градиентных методов оптимизации второго порядка для обучения нейронных сетей.
1. Введение.
В
первой части этой статьи
мы формально поставили задачу обучения
классификатора $h$ как задачу минимизации функции потери в пространстве весов.
\begin{equation}
\min_W E(h(X,W),C)
\label{eq:ermin}
\end{equation}
А так же рассмотрели
градиентные методы первого порядка
для решения этой задачи.
Далее мы займёмся градиентными методами оптимизации второго порядка для обучения нейронных сетей прямого распространения.
2. Градиентные методы второго порядка.
Градиентные методы первого порядка
для решения задачи используют только вектор градиента $\nabla E$, т.е. направления набольшего роста целевой функции.
В отличии от них, градиентные методы второго порядка помимо вектора градиента используют ёще
и информацию о кривизне целевой функции, для этого используется гессиан $H$ - матрица вторых производных целевой функции.
В этом случае параметры сети изменяються по следуещей формуле.
$$
W:= W - \Delta W
$$
$$
\Delta W = H^{-1} \cdot g
$$
где $g$ - вектор градиента
$$
g = \nabla E =
\left[
\begin{array}{ c }
\frac {\partial E}{\partial w_1 } \\
\vdots \\
\frac {\partial E}{\partial w_n } \\
\end{array}
\right]
$$
$H$ - гессиан, матрица вторых производных целевой функции $E$
$$
H =
\left[
\begin{array}{ c c c }
\frac {\partial^2 E}{\partial w_1\partial w_1} & \ldots & \frac {\partial^2 E}{\partial w_1\partial w_n} \\
\vdots & \ddots & \vdots \\
\frac {\partial^2 E}{\partial w_n\partial w_1} & \ldots & \frac {\partial^2 E}{\partial w_n\partial w_n} \\
\end{array}
\right]
$$
Здесь мы можем столкнутся с некоторыми затруднениями при вычислении гессиана $H$, потому как это может оказаться очень затратной процедурой.
По этому мы обойдём эту задачу и вместо гессиана $H$ будем вычислять его приближение исходя
из значений первой производной функции потери и изменения параметров $\Delta W$.
Такой подход известен как квазиньютоновские методы.
Методы обучения второго порядка могут быть существенно эффективнее чем метод градиентного спуска,
однако они требуют больше ресурсов памяти и не всегда получается их применять.
Далее мы рассмотрим один из таких методов - BFGS.
3. метод BFGS
Метод BFGS или алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (Broyden–Fletcher–Goldfarb–Shanno)
для вычисления обратного гессиана $H^{-1}$ использует изменение значений градиента $\nabla E$ и изменения весов $\Delta W$.
Вектор градиента функции ошибки $g=\nabla E$ вычисляется с помощью обычной процедуры
обратного распространения ошибки, изложенной
в предыдущей части этой статьи.
Обратный гессиан $V\approx H^{-1}$ это матрица размера $n\times n$ (где $n$ - длинна вектора градиента $g$).
Значения $V$ вычисляются на каждом шаге алгоритма следующим образом.
$$V_0 := 1$$
\begin{equation}
V_{k+1} := V_k - \frac{ V_k \cdot s \cdot s^T \cdot V_k}{s^T\cdot V_k\cdot s} + \frac{r \cdot r^T}{s^T\cdot s}
\label{eq:inv_hes}
\end{equation}
где $r = \Delta g_k = g_k - g_{k-1}$ - изменение градиента, $s = \Delta W_k = W_k - W_{k-1}$ - изменение весов
3.1 Общая схема агоритма
- инициализировать веса $W$ (случайными малыми значениями)
и задать начальное значение приближения обратного гессиана $H^{-1} \approx V_0 = 1$
- вычисляем значение градиента $g$
- коректируем веса
$\Delta W := g\cdot \tau$
$W := W - \Delta W$,
где $\tau = 0.01$ - параметр скорости обучения
- сохраняем старое значение градиента $g_{old}:=g$
вычисляем новое значение градиента $g(W)$
и изменение градиента $\Delta g := g - g_{old}$
- вычисляем приближенное значение обратного гессиана $V(\Delta g,\Delta W)$ по (\ref{eq:inv_hes})
- вычисляем изменение весов и корректируем параметры
$\Delta W := V \cdot g$
$W := W - \Delta W$
- вычисляем ошибку $E(W)$
- если результат $E(W)$ удовлетворительный
то конец работы
- переход на п.4
Далее мы рассмотрим метод Левенберга-Марквардта.
4. метод Левенберга-Марквардта
Рассмотрим функцию ошибки сети на всей учебной выборке
$$
e = d - o =
\left[
\begin{array}{ c }
e_{11} \\
\vdots \\
e_{M1} \\
e_{12} \\
\vdots \\
e_{MP}
\end{array}
\right]
$$
здесь
$o$ - выход сети,
$d$ - учебный (идеальный) выход,
$M$ - количество выходов,
$P$ - количество примеров.
Метод Левенберга-Марквардта вычисляет приближение гессиана $H$ с помощью якобиана $J$ (матрицы первых производных функции ошибки $e$)
следующим образом.
$$
H \approx J^T \cdot J + \mu \cdot I
$$
где
$J$ - якобиан, матрица первых производных функции ошибки,
$\mu$ - параметр,
$I = (J^T \cdot J) \circ E$ - диагональная матрица из элементов главной диагонали $(J^T \cdot J)$,
$\circ$ - поэлементное умножение матриц (Hadamard product).
Вектор градиента вычисляется следующим образом.
$$
g = J^T \cdot e
$$
Если собрать всё вместе то получаем следующую формулу для изменения весов сети.
\begin{equation}
\Delta W = (J^T \cdot J + \mu \cdot I) ^{-1} \cdot J^T \cdot e
\label{eq:lma}
\end{equation}
4.1 Составные части матрицы якобиана
Якобиан $J$ или матрица частных производных функции ошибки сети по всем её параметрам и на всей учебной выборке,
её размер - $(P \cdot M) \times T$, где $P$ - количество примеров, $M$ - количество выходов сети, $T$ - количество параметров сети,
Далее мы последовательно разберём якобиан $J$ на составные части.
Матрица якобиана $J$ состоит из следующих блоков.
$$
J = \left[ \frac{\partial e}{\partial w} \right] =
\left[\begin{array}{ c }
J_1 \\
\vdots \\
J_P
\end{array}
\right]
$$
где $J_p$ часть якобиана для примера $p$, она состоит из следующих частей.
$$
J_p = [ J_p^1 \ldots J_p^L ]
$$
где $J_p^l$ часть якобиана для примера $p$, слоя сети $l$, она состоит из следующих частей.
$$
J_p^l = \left[\begin{array}{ c }
\frac{\partial e_1(p)}{\partial W^l} \\
\vdots \\
\frac{\partial e_M(p)}{\partial W^l}
\end{array}
\right]
$$
где $\frac{\partial e_m(p)}{\partial W^l}$ часть якобиана для примера $p$, слоя сети $l$, выхода сети $m$, она состоит из следующих частей.
$$
\frac{\partial e_m(p)}{\partial W^l} =
\left[
\frac{\partial e_m(p)}{\partial w_{11}^l}
\ldots
\frac{\partial e_m(p)}{\partial w_{1k}^l }
\frac{\partial e_m(p)}{\partial w_{21}^l }
\ldots
\frac{\partial e_m(p)}{\partial w_{tk}^l }
\right]
$$
т.е. это есть развёрнутая в строку матрица для слоя $l$
$$
\left[\begin{array}{ c c c }
\frac{\partial e_m(p)}{\partial w_{11}^l } & \ldots & \frac{\partial e_m(p)}{\partial w_{1k}^l }\\
\vdots & \ddots & \vdots \\
\frac{\partial e_m(p)}{\partial w_{t1}^l } & \ldots & \frac{\partial e_m(p)}{\partial w_{tk}^l }
\end{array}
\right]
$$
При построении якобиана $J$, элементы $J$ для весов и сдвигов будем компоновать отдельно.
$$
J = \left[ \frac{\partial e}{\partial W} \frac{\partial e}{\partial B} \right]
$$
Далее мы разберём способ вычисления элементов якобиана $J$.
4.2 вычисление элементов якобиана
Процедура вычисление элементов якобиана $J$ для функции ошибки $e$ нейронной сети похожа на метод
обратного распространения ошибки, изложенный
в предыдущей части этой статьи.
Рассмотрим её подробнее.
Определим состояние нейрона $s$ и выход нейрона $y$ следующим образом.
Состояние нейрона $j$ слоя $l$ на примере $p$ :
$$
s_{j(l)}(p) = \sum\limits_i w^l_{ji} \cdot y_{i(l-1)}(p)
$$
Активированный $f()$ выход нейрона нейрона $j$ слоя $l$ на примере $p$ :
$$
y_{j(l)}(p) = f\left( s_{j(l)}(p) \right)
$$
Элемент якобиана это значение производной функции ошибки $e$ для примера $p$, выхода $m$, веса $w_{ji}$ слоя $l$ :
$$
\frac{\partial e_m(p)}{\partial w_{ji}^l } = -
\frac{\partial o_m(p)}{\partial y_{j(l)} }
\cdot \frac{\partial y_{j(l)}(p)}{\partial s_{j(l)} }
\cdot \frac{\partial s_{j(l)}(p)}{\partial w^l_{ji} }
$$
Разберём части последнего соотношения отдельно, начнём с конца.
Последняя часть - вход $i$ нейрона $j$ слоя $l$ на примере $p$
$$\frac {\partial s_{j(l)}(p) }{ \partial w^l_{ji} } = y_{i(l-1)}(p) $$
эта часть определена.
Вторая часть - значение производной ф-ции активации для нейрона $j$ слоя $l$ на примере $p$
$$ \frac{ \partial y_{j(l)}(p) }{ \partial s_{j(l)} } = \partial f_{j(l)}(p) $$
эту часть мы можем вычислить.
Первая часть - производная (нелинейной) функции, описывающей преобразование
сигнала между выходом нейрона $j$ слоя $l$ и выходом сети $m$ на примере $p$
$$ \frac {\partial o_m(p) }{ \partial y_{j(l)} } = \partial F_{mj(l)}(p) $$
процедуру вычисления этой части мы рассмотрим ниже.
Таким образом, элемент якобиана для выхода $m$, веса $w_{ji}$ слоя $l$ на примере $p$ можно записать как
$$
\frac{\partial e_m(p)}{\partial w_{ji}^l } = - \partial F_{mj(l)}(p) \cdot \partial f_{j(l)}(p) \cdot y_{i(l-1)}(p)
$$
При этом - для сдвига $y_{i(l-1)}(p) = 1$, т.е. вход сдвига нейрона $j$ всегда равен $1$
$$
\frac{\partial e_m(p)}{\partial b_j^l } = - \partial F_{mj(l)}(p) \cdot \partial f_{j(l)}(p)
$$
4.3 процедура LMA backProp
В предыдущем разделе мы определили основные составные части элемента якобиана $\frac{\partial e}{\partial w}$,
здесь нам предстоит определить недостающую часть $\partial F_{mj(l)}(p)$ -
производную функции, описывающей преобразование сигнала между выходом нейрона $j$ слоя $l$ и выходом сети $m$ на примере $p$.
Делать мы это будем следующим образом.
Введём $\delta$ для каждого нейрона $j$ слоя $l$, выхода сети $m$ на примере $p$.
$$
\delta_{mj(l)}(p) := - \partial F_{mj(l)}(p) \cdot \partial f_{j(l)}(p)
$$
где $\partial f_{j(l)}(p)$ -значение производной ф-ции активации для нейрона $j$ слоя $l$ на примере $p$.
Для нейрона $j$
выходного слоя, выхода сети $m$ и примера $p$ значение $\delta_{mj}(p)$ определяется следующим образом.
$$
\delta_{mj}(p) =
\left\{\begin{array}{ l c }
- \partial f_j(p) , & m=j \\
0 , & -
\end{array}
\right.
$$
здесь $\delta_{mj}(p)$ это $P$ диагональных матриц размера $M \times M$, где $P$ - кол-во примеров, $M$ - кол-во выходов.
Для нейрона $k$
скрытого слоя $l$, выхода сети $m$ и примера $p$ значение $\delta_{mk(l)}(p)$ определяется следующим образом.
$$
\delta_{mk(l)}(p) = \sum_{i(l+1)}\left( w^{l+1}_{k(l)i} \cdot \delta_{mi}(p) \right) \cdot \partial f_{k(l)}(p)
$$
в матричном виде (для каждого примера $p$)
$$
\delta^l(p) = \delta^{l+1}(p) \cdot W^l \circ \left(\partial f^{l}(p)\right)^T
$$
в данном случае $\delta_{mj}(p)$ это $P$ матриц размера $M \times K$,
где $P$ - кол-во примеров, $K$ - кол-во нейронов в слое $l$,
$\circ$ - поэлементное умножение матриц (Hadamard product).
Для
выходного слоя с состоянием нейронов $s$ и активацией $softmax(s)$ значение $\delta_{mj}(p)$ определяется следующим образом.
$$softmax(s) = \frac{\exp(s_i)}{\sum\limits_j\exp(s_j)}$$
$$
\delta_{mj}(p) =
\left\{\begin{array}{ l c }
- s_j(p)\cdot(1-s_j(p)) , & m=j \\
s_m(p)\cdot s_j(p) , & - \\
\end{array}
\right.
$$
Таким образом значения элементов якобиана имеют следующий вид.
\begin{equation}
\frac{\partial e_m(p)}{\partial w_{ji}^l } = \delta_{mk(l)}(p) \cdot y_{i(l-1)}(p)
\label{eq:lma2}
\end{equation}
Далее приведём общую схему алгоритма Левенберга-Марквардта обучения ИНС.
4.4 Общая схема алгоритма обучения Левенберга-Марквардта
- инициализировать веса $W$ (случайными малыми значениями) и параметр $\mu$
- вычисляем значение якобиана $J$ по (\ref{eq:lma2})
- вычисляем изменение параметров: $\Delta W(J,\mu)$ по (\ref{eq:lma})
- корректируем параметры: $W_{new}:=W-\Delta W$
- вычисляем ошибку $E(W_{new})$
- если ошибка выросла то увеличиваем параметр $\mu:=\mu\cdot 10$ и переход на п.3
- сохраняем результат $W := W_{new}$, уменьшаем параметр $\mu := \mu / 10$
- если результат $E(W_{new})$ удовлетворительный то конец работы
- переход на п.2
5. Реализации.
В этом разделе мы представим реализации описанных выше методов.
Тестировать их будем на нескольких наборах точек (в двух классах) .
Каждый набор точек перед запуском процедуры обучения случайным образом делиться на три части:
учебный, контрольный и тестовый.
5.1 Первый набор.
Рис.: учебный набор |
Рис.: контрольный набор |
Рис.: тестовый набор
Далее представим результаты для разных методов обучения.
Метод BFGS, будем использовать
нейронную сеть с двумя обрабатывающими слоями: входной слой 2 нейрона, первый обрабатывающий слой 10 нейронов с активацией ReLU,
второй слой - 2 нейрона (по числу классов) с активацией softmax.
Сеть достигла порога ошибки за 1747 эпох, результаты представлены ниже.
Метод LMA, будем использовать
нейронную сеть с двумя обрабатывающими слоями: входной слой 2 нейрона, первый обрабатывающий слой 25 нейронов с активацией tanh,
второй слой - 2 нейрона (по числу классов) с активацией экспоненциальный сигмоид.
Сеть достигла порога ошибки за 393 эпох, результаты представлены ниже.
5.2 Второй набор.
Рис.: учебный набор |
Рис.: контрольный набор |
Рис.: тестовый набор
Далее представим результаты для разных методов обучения.
Метод BFGS, будем использовать
нейронную сеть с двумя обрабатывающими слоями: входной слой 2 нейрона, первый обрабатывающий слой 10 нейронов с активацией ReLU,
второй слой - 2 нейрона (по числу классов) с активацией softmax.
Сеть обучалась 2500 эпох, результаты представлены ниже.
Метод LMA, будем использовать
нейронную сеть с двумя обрабатывающими слоями: входной слой 2 нейрона, первый обрабатывающий слой 25 нейронов с активацией tanh,
второй слой - 2 нейрона (по числу классов) с активацией экспоненциальный сигмоид.
Сеть достигла порога ошибки за 369 эпох, результаты представлены ниже.
Реализация в системе Octave [
здесь].
Список литературы
- Е.С.Борисов Основные модели и методы теории искусственных нейронных сетей. - http://mechanoid.kiev.ua
- Е.С.Борисов О методах обучения многослойных нейронных сетей прямого распространения. ч.1 Общие положения - http://mechanoid.kiev.ua
- Е.С.Борисов О методах обучения многослойных нейронных сетей прямого распространения. ч.2 Градиентные методы первого порядка - http://mechanoid.kiev.ua
- Осовский С. Нейронные сети для обработки информации. — М.: Финансы и статистика, 2002.
- А.А.Ферцев, Ускорение обучения нейронной сети для распознавания изображений с помощью технологии NVIDIA CUDA, Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2012, выпуск 1(26), 183–191
- Hao Yu, Bogdan M. Wilamowski Levenberg–Marquardt Training
- GNU Octave -- http://www.gnu.org/software/octave
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.