Метод обратного распространения ошибки схема

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

Открытие метода обратного распространения ошибки стало одним из наиболее значимых событий в области искусственного интеллекта. В актуальном виде он был предложен в 1986 году Дэвидом Э. Румельхартом, Джеффри Э. Хинтоном и Рональдом Дж. Вильямсом и независимо и одновременно красноярскими математиками С. И. Барцевым и В. А. Охониным. С тех пор для нахождения градиентов параметров нейронной сети используется метод вычисления производной сложной функции, и оценка градиентов параметров сети стала хоть сложной инженерной задачей, но уже не искусством. Несмотря на простоту используемого математического аппарата, появление этого метода привело к значительному скачку в развитии искусственных нейронных сетей.

Суть метода можно записать одной формулой, тривиально следующей из формулы производной сложной функции: если $f(x) = g_m(g_{m-1}(ldots (g_1(x)) ldots))$, то $frac{partial f}{partial x} = frac{partial g_m}{partial g_{m-1}}frac{partial g_{m-1}}{partial g_{m-2}}ldots frac{partial g_2}{partial g_1}frac{partial g_1}{partial x}$. Уже сейчас мы видим, что градиенты можно вычислять последовательно, в ходе одного обратного прохода, начиная с $frac{partial g_m}{partial g_{m-1}}$ и умножая каждый раз на частные производные предыдущего слоя.

Backpropagation в одномерном случае

В одномерном случае всё выглядит особенно просто. Пусть $w_0$ — переменная, по которой мы хотим продифференцировать, причём сложная функция имеет вид

$$f(w_0) = g_m(g_{m-1}(ldots g_1(w_0)ldots)),$$

где все $g_i$ скалярные. Тогда

$$f'(w_0) = g_m'(g_{m-1}(ldots g_1(w_0)ldots))cdot g’_{m-1}(g_{m-2}(ldots g_1(w_0)ldots))cdotldots cdot g’_1(w_0)$$

Суть этой формулы такова. Если мы уже совершили forward pass, то есть уже знаем

$$g_1(w_0), g_2(g_1(w_0)),ldots,g_{m-1}(ldots g_1(w_0)ldots),$$

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

• берём производную $g_m$ в точке $g_{m-1}(ldots g_1(w_0)ldots)$;

• умножаем на производную $g_{m-1}$ в точке $g_{m-2}(ldots g_1(w_0)ldots)$;

• и так далее, пока не дойдём до производной $g_1$ в точке $w_0$.

Проиллюстрируем это на картинке, расписав по шагам дифференцирование по весам $w_i$ функции потерь логистической регрессии на одном объекте (то есть для батча размера 1):

Собирая все множители вместе, получаем:

$$frac{partial f}{partial w_0} = (-y)cdot e^{-y(w_0 + w_1x_1 + w_2x_2)}cdotfrac{-1}{1 + e^{-y(w_0 + w_1x_1 + w_2x_2)}}$$

$$frac{partial f}{partial w_1} = x_1cdot(-y)cdot e^{-y(w_0 + w_1x_1 + w_2x_2)}cdotfrac{-1}{1 + e^{-y(w_0 + w_1x_1 + w_2x_2)}}$$

$$frac{partial f}{partial w_2} = x_2cdot(-y)cdot e^{-y(w_0 + w_1x_1 + w_2x_2)}cdotfrac{-1}{1 + e^{-y(w_0 + w_1x_1 + w_2x_2)}}$$

Таким образом, мы видим, что сперва совершается forward pass для вычисления всех промежуточных значений (и да, все промежуточные представления нужно будет хранить в памяти), а потом запускается backward pass, на котором в один проход вычисляются все градиенты.

Почему же нельзя просто пойти и начать везде вычислять производные?

В главе, посвящённой матричным дифференцированиям, мы поднимаем вопрос о том, что вычислять частные производные по отдельности — это зло, лучше пользоваться матричными вычислениями. Но есть и ещё одна причина: даже и с матричной производной в принципе не всегда хочется иметь дело. Рассмотрим простой пример. Допустим, что $X^r$ и $X^{r+1}$ — два последовательных промежуточных представления $Ntimes M$ и $Ntimes K$, связанных функцией $X^{r+1} = f^{r+1}(X^r)$. Предположим, что мы как-то посчитали производную $frac{partialmathcal{L}}{partial X^{r+1}_{ij}}$ функции потерь $mathcal{L}$, тогда

$$frac{partialmathcal{L}}{partial X^{r}_{st}} = sum_{i,j}frac{partial f^{r+1}_{ij}}{partial X^{r}_{st}}frac{partialmathcal{L}}{partial X^{r+1}_{ij}}$$

И мы видим, что, хотя оба градиента $frac{partialmathcal{L}}{partial X_{ij}^{r+1}}$ и $frac{partialmathcal{L}}{partial X_{st}^{r}}$ являются просто матрицами, в ходе вычислений возникает «четырёхмерный кубик» $frac{partial f_{ij}^{r+1}}{partial X_{st}^{r}}$, даже хранить который весьма болезненно: уж больно много памяти он требует ($N^2MK$ по сравнению с безобидными $NM + NK$, требуемыми для хранения градиентов). Поэтому хочется промежуточные производные $frac{partial f^{r+1}}{partial X^{r}}$ рассматривать не как вычисляемые объекты $frac{partial f_{ij}^{r+1}}{partial X_{st}^{r}}$, а как преобразования, которые превращают $frac{partialmathcal{L}}{partial X_{ij}^{r+1}}$ в $frac{partialmathcal{L}}{partial X_{st}^{r}}$. Целью следующих глав будет именно это: понять, как преобразуется градиент в ходе error backpropagation при переходе через тот или иной слой.

  Вы спросите себя: надо ли мне сейчас пойти и прочитать главу учебника про матричное дифференцирование?

Встречный вопрос. Найдите производную функции по вектору $x$:

$$f(x) = x^TAx, Ain Mat_{n}{mathbb{R}}text{ — матрица размера }ntimes n$$

А как всё поменяется, если $A$ тоже зависит от $x$? Чему равен градиент функции, если $A$ является скаляром? Если вы готовы прямо сейчас взять ручку и бумагу и посчитать всё, то вам, вероятно, не надо читать про матричные дифференцирования. Но мы советуем всё-таки заглянуть в эту главу, если обозначения, которые мы будем дальше использовать, покажутся вам непонятными: единой нотации для матричных дифференцирований человечество пока, увы, не изобрело, и переводить с одной на другую не всегда легко.

Мы же сразу перейдём к интересующей нас вещи: к вычислению градиентов сложных функций.

Градиент сложной функции

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

$$left[D_{x_0} (color{#5002A7}{u} circ color{#4CB9C0}{v}) right](h) = color{#5002A7}{left[D_{v(x_0)} u right]} left( color{#4CB9C0}{left[D_{x_0} vright]} (h)right)$$

Теперь разберёмся с градиентами. Пусть $f(x) = g(h(x))$ – скалярная функция. Тогда

$$left[D_{x_0} f right] (x-x_0) = langlenabla_{x_0} f, x-x_0rangle.$$

С другой стороны,

$$left[D_{h(x_0)} g right] left(left[D_{x_0}h right] (x-x_0)right) = langlenabla_{h_{x_0}} g, left[D_{x_0} hright] (x-x_0)rangle = langleleft[D_{x_0} hright]^* nabla_{h(x_0)} g, x-x_0rangle.$$

То есть $color{#FFC100}{nabla_{x_0} f} = color{#348FEA}{left[D_{x_0} h right]}^* color{#FFC100}{nabla_{h(x_0)}}g$ — применение сопряжённого к $D_{x_0} h$ линейного отображения к вектору $nabla_{h(x_0)} g$.

Эта формула — сердце механизма обратного распространения ошибки. Она говорит следующее: если мы каким-то образом получили градиент функции потерь по переменным из некоторого промежуточного представления $X^k$ нейронной сети и при этом знаем, как преобразуется градиент при проходе через слой $f^k$ между $X^{k-1}$ и $X^k$ (то есть как выглядит сопряжённое к дифференциалу слоя между ними отображение), то мы сразу же находим градиент и по переменным из $X^{k-1}$:

Таким образом слой за слоем мы посчитаем градиенты по всем $X^i$ вплоть до самых первых слоёв.

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

Градиенты для типичных слоёв

Рассмотрим несколько важных примеров.

Примеры

1. $f(x) = u(v(x))$, где $x$ — вектор, а $v(x)$ – поэлементное применение $v$:

   $$vbegin{pmatrix}
   x_1
   vdots
   x_N
   end{pmatrix}
   = begin{pmatrix}
   v(x_1)
   vdots
   v(x_N)
   end{pmatrix}$$

   Тогда, как мы знаем,

   $$left[D_{x_0} fright] (h) = langlenabla_{x_0} f, hrangle = left[nabla_{x_0} fright]^T h.$$

   Следовательно,

   $$begin{multline*}
   left[D_{v(x_0)} uright] left( left[ D_{x_0} vright] (h)right) = left[nabla_{v(x_0)} uright]^T left(v'(x_0) odot hright) =\[0.1cm]
   = sumlimits_i left[nabla_{v(x_0)} uright]_i v'(x_{0i})h_i
   = langleleft[nabla_{v(x_0)} uright] odot v'(x_0), hrangle.
   end{multline*},$$

   где $odot$ означает поэлементное перемножение. Окончательно получаем

   $$color{#348FEA}{nabla_{x_0} f = left[nabla_{v(x_0)}uright] odot v'(x_0) = v'(x_0) odot left[nabla_{v(x_0)} uright]}$$

   Отметим, что если $x$ и $h(x)$ — это просто векторы, то мы могли бы вычислять всё и по формуле $frac{partial f}{partial x_i} = sum_jbig(frac{partial z_j}{partial x_i}big)cdotbig(frac{partial h}{partial z_j}big)$. В этом случае матрица $big(frac{partial z_j}{partial x_i}big)$ была бы диагональной (так как $z_j$ зависит только от $x_j$: ведь $h$ берётся поэлементно), и матричное умножение приводило бы к тому же результату. Однако если $x$ и $h(x)$ — матрицы, то $big(frac{partial z_j}{partial x_i}big)$ представлялась бы уже «четырёхмерным кубиком», и работать с ним было бы ужасно неудобно.

2. $f(X) = g(XW)$, где $X$ и $W$ — матрицы. Как мы знаем,

   $$left[D_{X_0} f right] (X-X_0) = text{tr}, left(left[nabla_{X_0} fright]^T (X-X_0)right).$$

   Тогда

   $$begin{multline*}
   left[ D_{X_0W} g right] left(left[D_{X_0} left( ast Wright)right] (H)right) =
   left[ D_{X_0W} g right] left(HWright)=\
   = text{tr}, left( left[nabla_{X_0W} g right]^T cdot (H) W right) =\
   =
   text{tr} , left(W left[nabla_{X_0W} (g) right]^T cdot (H)right) = text{tr} , left( left[left[nabla_{X_0W} gright] W^Tright]^T (H)right)
   end{multline*}$$

   Здесь через $ast W$ мы обозначили отображение $Y hookrightarrow YW$, а в предпоследнем переходе использовалось следующее свойство следа:

   $$
   text{tr} , (A B C) = text{tr} , (C A B),
   $$

   где $A, B, C$ — произвольные матрицы подходящих размеров (то есть допускающие перемножение в обоих приведённых порядках). Следовательно, получаем

   $$color{#348FEA}{nabla_{X_0} f = left[nabla_{X_0W} (g) right] cdot W^T}$$

3. $f(W) = g(XW)$, где $W$ и $X$ — матрицы. Для приращения $H = W — W_0$ имеем

   $$
   left[D_{W_0} f right] (H) = text{tr} , left( left[nabla_{W_0} f right]^T (H)right)
   $$

   Тогда

   $$ begin{multline*}
   left[D_{XW_0} g right] left( left[D_{W_0} left(X astright) right] (H)right) = left[D_{XW_0} g right] left( XH right) =
   = text{tr} , left( left[nabla_{XW_0} g right]^T cdot X (H)right) =
   text{tr}, left(left[X^T left[nabla_{XW_0} g right] right]^T (H)right)
   end{multline*} $$

   Здесь через $X ast$ обозначено отображение $Y hookrightarrow XY$. Значит,

   $$color{#348FEA}{nabla_{X_0} f = X^T cdot left[nabla_{XW_0} (g)right]}$$

4. $f(X) = g(softmax(X))$, где $X$ — матрица $Ntimes K$, а $softmax$ — функция, которая вычисляется построчно, причём для каждой строки $x$

   $$softmax(x) = left(frac{e^{x_1}}{sum_te^{x_t}},ldots,frac{e^{x_K}}{sum_te^{x_t}}right)$$

   В этом примере нам будет удобно воспользоваться формализмом с частными производными. Сначала вычислим $frac{partial s_l}{partial x_j}$ для одной строки $x$, где через $s_l$ мы для краткости обозначим $softmax(x)_l = frac{e^{x_l}} {sum_te^{x_t}}$. Нетрудно проверить, что

   $$frac{partial s_l}{partial x_j} = begin{cases}
   s_j(1 — s_j), & j = l,
   -s_ls_j, & jne l
   end{cases}$$

   Так как softmax вычисляется независимо от каждой строчки, то

   $$frac{partial s_{rl}}{partial x_{ij}} = begin{cases}
   s_{ij}(1 — s_{ij}), & r=i, j = l,
   -s_{il}s_{ij}, & r = i, jne l,
   0, & rne i
   end{cases},$$

   где через $s_{rl}$ мы обозначили для краткости $softmax(X)_{rl}$.

   Теперь пусть $nabla_{rl} = nabla g = frac{partialmathcal{L}}{partial s_{rl}}$ (пришедший со следующего слоя, уже известный градиент). Тогда

   $$frac{partialmathcal{L}}{partial x_{ij}} = sum_{r,l}frac{partial s_{rl}}{partial x_{ij}} nabla_{rl}$$

   Так как $frac{partial s_{rl}}{partial x_{ij}} = 0$ при $rne i$, мы можем убрать суммирование по $r$:

   $$ldots = sum_{l}frac{partial s_{il}}{partial x_{ij}} nabla_{il} = -s_{i1}s_{ij}nabla_{i1} — ldots + s_{ij}(1 — s_{ij})nabla_{ij}-ldots — s_{iK}s_{ij}nabla_{iK} =$$

   $$= -s_{ij}sum_t s_{it}nabla_{it} + s_{ij}nabla_{ij}$$

   Таким образом, если мы хотим продифференцировать $f$ в какой-то конкретной точке $X_0$, то, смешивая математические обозначения с нотацией Python, мы можем записать:

   $$begin{multline*}
   color{#348FEA}{nabla_{X_0}f =}\
   color{#348FEA}{= -softmax(X_0) odot text{sum}left(
   softmax(X_0)odotnabla_{softmax(X_0)}g, text{ axis = 1}
   right) +}\
   color{#348FEA}{softmax(X_0)odot nabla_{softmax(X_0)}g}
   end{multline*}
   $$

Backpropagation в общем виде

Подытожим предыдущее обсуждение, описав алгоритм error backpropagation (алгоритм обратного распространения ошибки). Допустим, у нас есть текущие значения весов $W^i_0$ и мы хотим совершить шаг SGD по мини-батчу $X$. Мы должны сделать следующее:

1. Совершить forward pass, вычислив и запомнив все промежуточные представления $X = X^0, X^1, ldots, X^m = widehat{y}$.
2. Вычислить все градиенты с помощью backward pass.
3. С помощью полученных градиентов совершить шаг SGD.

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

Обучаемые параметры – матрицы $U$ и $W$. Как найти градиенты по ним в точке $U_0, W_0$?

$$nabla_{W_0}mathcal{L} = nabla_{W_0}{left({vphantom{frac12}mathcal{L}circ hcircleft[Wmapsto g(XU_0)Wright]}right)}=$$

$$=g(XU_0)^Tnabla_{g(XU_0)W_0}(mathcal{L}circ h) = underbrace{g(XU_0)^T}_{ktimes N}cdot
left[vphantom{frac12}underbrace{h’left(vphantom{int_0^1}g(XU_0)W_0right)}_{Ntimes 1}odot
underbrace{nabla_{hleft(vphantom{int_0^1}g(XU_0)W_0right)}mathcal{L}}_{Ntimes 1}right]$$

Итого матрица $ktimes 1$, как и $W_0$

$$nabla_{U_0}mathcal{L} = nabla_{U_0}left(vphantom{frac12}
mathcal{L}circ hcircleft[Ymapsto YW_0right]circ gcircleft[ Umapsto XUright]
right)=$$

$$=X^Tcdotnabla_{XU^0}left(vphantom{frac12}mathcal{L}circ hcirc [Ymapsto YW_0]circ gright) =$$

$$=X^Tcdotleft(vphantom{frac12}g'(XU_0)odot
nabla_{g(XU_0)}left[vphantom{in_0^1}mathcal{L}circ hcirc[Ymapsto YW_0right]
right)$$

$$=ldots = underset{Dtimes N}{X^T}cdotleft(vphantom{frac12}
underbrace{g'(XU_0)}_{Ntimes K}odot
underbrace{left[vphantom{int_0^1}left(
underbrace{h’left(vphantom{int_0^1}g(XU_0)W_0right)}_{Ntimes1}odotunderbrace{nabla_{h(vphantom{int_0^1}gleft(XU_0right)W_0)}mathcal{L}}_{Ntimes 1}
right)cdot underbrace{W^T}_{1times K}right]}_{Ntimes K}
right)$$

Итого $Dtimes K$, как и $U_0$

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

Backpropagation для двуслойной нейронной сети

Если вы не уследили за вычислениями в предыдущем примере, давайте более подробно разберём его чуть более конкретную версию (для $g = h = sigma$)Рассмотрим двуслойную нейронную сеть для классификации. Мы уже встречали ее ранее при рассмотрении линейно неразделимой выборки. Предсказания получаются следующим образом:

$$
widehat{y} = sigma(X^1 W^2) = sigmaBig(big(sigma(X^0 W^1 )big) W^2 Big).
$$

Пусть $W^1_0$ и $W^2_0$ — текущее приближение матриц весов. Мы хотим совершить шаг по градиенту функции потерь, и для этого мы должны вычислить её градиенты по $W^1$ и $W^2$ в точке $(W^1_0, W^2_0)$.

Прежде всего мы совершаем forward pass, в ходе которого мы должны запомнить все промежуточные представления: $X^1 = X^0 W^1_0$, $X^2 = sigma(X^0 W^1_0)$, $X^3 = sigma(X^0 W^1_0) W^2_0$, $X^4 = sigma(sigma(X^0 W^1_0) W^2_0) = widehat{y}$. Они понадобятся нам дальше.

Для полученных предсказаний вычисляется значение функции потерь:

$$
l = mathcal{L}(y, widehat{y}) = y log(widehat{y}) + (1-y) log(1-widehat{y}).
$$

Дальше мы шаг за шагом будем находить производные по переменным из всё более глубоких слоёв.

1. Градиент $mathcal{L}$ по предсказаниям имеет вид

   $$
   nabla_{widehat{y}}l = frac{y}{widehat{y}} — frac{1 — y}{1 — widehat{y}} = frac{y — widehat{y}}{widehat{y} (1 — widehat{y})},
   $$

   где, напомним, $ widehat{y} = sigma(X^3) = sigmaBig(big(sigma(X^0 W^1_0 )big) W^2_0 Big)$ (обратите внимание на то, что $W^1_0$ и $W^2_0$ тут именно те, из которых мы делаем градиентный шаг).

2. Следующий слой — поэлементное взятие $sigma$. Как мы помним, при переходе через него градиент поэлементно умножается на производную $sigma$, в которую подставлено предыдущее промежуточное представление:

   $$
   nabla_{X^3}l = sigma'(X^3)odotnabla_{widehat{y}}l = sigma(X^3)left( 1 — sigma(X^3) right) odot frac{y — widehat{y}}{widehat{y} (1 — widehat{y})} =
   $$

   $$
   = sigma(X^3)left( 1 — sigma(X^3) right) odot frac{y — sigma(X^3)}{sigma(X^3) (1 — sigma(X^3))} =
   y — sigma(X^3)
   $$

3. Следующий слой — умножение на $W^2_0$. В этот момент мы найдём градиент как по $W^2$, так и по $X^2$. При переходе через умножение на матрицу градиент, как мы помним, умножается с той же стороны на транспонированную матрицу, а значит:

   $$
   color{blue}{nabla_{W^2_0}l} = (X^2)^Tcdot nabla_{X^3}l = (X^2)^Tcdot(y — sigma(X^3)) =
   $$

   $$
   = color{blue}{left( sigma(X^0W^1_0) right)^T cdot (y — sigma(sigma(X^0W^1_0)W^2_0))}
   $$

   Аналогичным образом

   $$
   nabla_{X^2}l = nabla_{X^3}lcdot (W^2_0)^T = (y — sigma(X^3))cdot (W^2_0)^T =
   $$

   $$
   = (y — sigma(X^2W_0^2))cdot (W^2_0)^T
   $$

4. Следующий слой — снова взятие $sigma$.

   $$
   nabla_{X^1}l = sigma'(X^1)odotnabla_{X^2}l = sigma(X^1)left( 1 — sigma(X^1) right) odot left( (y — sigma(X^2W_0^2))cdot (W^2_0)^T right) =
   $$

   $$
   = sigma(X^1)left( 1 — sigma(X^1) right) odotleft( (y — sigma(sigma(X^1)W_0^2))cdot (W^2_0)^T right)
   $$

5. Наконец, последний слой — это умножение $X^0$ на $W^1_0$. Тут мы дифференцируем только по $W^1$:

   $$
   color{blue}{nabla_{W^1_0}l} = (X^0)^Tcdot nabla_{X^1}l = (X^0)^Tcdot big( sigma(X^1) left( 1 — sigma(X^1) right) odot (y — sigma(sigma(X^1)W_0^2))cdot (W^2_0)^Tbig) =
   $$

   $$
   = color{blue}{(X^0)^Tcdotbig(sigma(X^0W^1_0)left( 1 — sigma(X^0W^1_0) right) odot (y — sigma(sigma(X^0W^1_0)W_0^2))cdot (W^2_0)^Tbig) }
   $$

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

Автоматизация и autograd

Итак, чтобы нейросеть обучалась, достаточно для любого слоя $f^k: X^{k-1}mapsto X^k$ с параметрами $W^k$ уметь:

• превращать $nabla_{X^k_0}mathcal{L}$ в $nabla_{X^{k-1}_0}mathcal{L}$ (градиент по выходу в градиент по входу);
• считать градиент по его параметрам $nabla_{W^k_0}mathcal{L}$.

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

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

Но это лишь начало

Метод обратного распространения ошибки позволяет удобно посчитать градиенты, но дальше с ними что-то надо делать, и старый добрый SGD едва ли справится с обучением современной сетки. Так что же делать? О некоторых приёмах мы расскажем в следующей главе.

Метод обратного распространения ошибок (англ. backpropagation) — метод вычисления градиента, который используется при обновлении весов в нейронной сети.

Обучение как задача оптимизации

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

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

где ошибка.

В качестве примера, обучим сеть на объекте , таким образом, значения и равны 1, а равно 0. Построим график зависимости ошибки от действительного ответа , его результатом будет парабола. Минимум параболы соответствует ответу , минимизирующему . Если тренировочный объект один, минимум касается горизонтальной оси, следовательно ошибка будет нулевая и сеть может выдать ответ равный ожидаемому ответу . Следовательно, задача преобразования входных значений в выходные может быть сведена к задаче оптимизации, заключающейся в поиске функции, которая даст минимальную ошибку.

В таком случае, выходное значение нейрона — взвешенная сумма всех его входных значений:

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

Дифференцирование для однослойной сети

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

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

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

Для каждого нейрона , его выходное значение определено как

Входные значения нейрона — это взвешенная сумма выходных значений предыдущих нейронов. Если нейрон в первом слое после входного, то входного слоя — это просто входные значения сети. Количество входных значений нейрона . Переменная обозначает вес на ребре между нейроном предыдущего слоя и нейроном текущего слоя.

Функция активации нелинейна и дифференцируема. Одна из распространенных функций активации — сигмоида:

у нее удобная производная:

Находим производную ошибки

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

Только одно слагаемое в зависит от , так что

Если нейрон в первом слое после входного, то — это просто .

Производная выходного значения нейрона по его входному значению — это просто частная производная функции активации (предполагается что в качестве функции активации используется сигмоида):

По этой причине данный метод требует дифференцируемой функции активации. (Тем не менее, функция ReLU стала достаточно популярной в последнее время, хоть и не дифференцируема в 0)

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

Тем не менее, если произвольный внутренний слой сети, нахождение производной по менее очевидно.

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

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

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

Если собрать все месте:

и

Чтобы обновить вес используя градиентный спуск, нужно выбрать скорость обучения, . Изменение в весах должно отражать влияние на увеличение или уменьшение в . Если , увеличение увеличивает ; наоборот, если , увеличение уменьшает . Новый добавлен к старым весам, и произведение скорости обучения на градиент, умноженный на , гарантирует, что изменения будут всегда уменьшать . Другими словами, в следующем уравнении, всегда изменяет в такую сторону, что уменьшается:

Алгоритм

• — скорость обучения
• — коэффициент инерциальности для сглаживания резких скачков при перемещении по поверхности целевой функции
• — обучающее множество
• — количество повторений
• — функция, подающая x на вход сети и возвращающая выходные значения всех ее узлов
• — количество слоев в сети
• — множество нейронов в слое i
• — множество нейронов в выходном слое

fun BackPropagation:
   init 
   repeat :
       for  =  to :
            =  
           for :
                = 
           for  =  to :
               for :
                    = 
           for :
                = 
                = 
   return 

Недостатки алгоритма

Несмотря на многочисленные успешные применения обратного распространения, оно не является универсальным решением. Больше всего неприятностей приносит неопределённо долгий процесс обучения. В сложных задачах для обучения сети могут потребоваться дни или даже недели, она может и вообще не обучиться. Причиной может быть одна из описанных ниже.

Паралич сети

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

Локальные минимумы

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

Примечания

• Алгоритм обучения многослойной нейронной сети методом обратного распространения ошибки
• Neural Nets
• Understanding backpropagation

См. также

• Нейронные сети, перцептрон
• Стохастический градиентный спуск
• Настройка глубокой сети
• Практики реализации нейронных сетей

Источники информации

• https://en.wikipedia.org/wiki/Backpropagation
• https://ru.wikipedia.org/wiki/Метод_обратного_распространения_ошибки

Для
обучения многослойной сети в 1986 г.
Руммельхартом и Хинтоном (Rummelhart D.E.,
Hinton G.E., Williams R.J., 1986) был предложен алгоритм
обратного распостранения ошибок (error
back propagation). Многочисленные публикации
о промышленных применениях многослойных
сетей с этим алгоритмом обучения
подтвердили его принципиальную
работоспособность на практике.

В
начале возникает резонный вопрос — а
почему для обучения многослойного
персептрона нельзя применить уже
известное d -правило Розенблатта? Ответ
состоит в том, что для применения метода
Розенблатта необходимо знать не только
текущие выходы нейронов y, но и требуемые
правильные значения Y. В случае многослойной
сети эти правильные значения имеются
только для нейронов выходного слоя.
Требуемые значения выходов для нейронов
скрытых слоев неизвестны, что и
ограничивает применение d -правила.

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

Перейдем
к подробному рассмотрению этого
алгоритма. Для упрощения обозначений
ограничимся ситуацией, когда сеть имеет
только один скрытый слой. Матрицу весовых
коэффициентов от входов к скрытому слою
обозначим W, а матрицу весов, соединяющих
скрытый и выходной слой — как V. Для
индексов примем следующие обозначения:
входы будем нумеровать только индексом
i, элементы скрытого слоя — индексом j, а
выходы, соответственно, индексом k.

Пусть
сеть обучается на выборке (Xa,Ya), a =1..p.
Активности нейронов будем обозначать
малыми буквами y с соотвествующим
индексом, а суммарные взвешенные входы
нейронов — малыми буквами x.

Таблица
1. Алгоритм обратного распространения
ошибки.

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

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

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

В
завершение сделаем замечание относительно
настройки порогов нейронов. Легко
заметить, что порог нейрона может быть
сделан эквивалентным дополнительному
весу, соединенному с фиктивным входом,
равным -1. Действительно, выбирая =Q,
=-1
и начиная суммирование с нуля, можно
рассматривать нейрон с нулевым порогом
и одним дополнительным входом:

Дополнительные
входы нейронов, соответствующие порогам,
изображены на Рис. 1 темными квадратиками.
С учетом этого замечания, все изложенные
в алгоритме обратного распространения
формулы суммирования по входам начинаются
с нулевого индекса.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Поскольку я столкнулся с существенными затруднениями в поисках объяснения механизма обратного распространения ошибки, которое мне понравилось бы, я решил написать собственный пост об обратном распространении ошибки реализовав алгоритм Word2Vec. Моя цель, — объяснить сущность алгоритма, используя простую, но нетривиальную нейросеть. Кроме того, word2vec стал настолько популярным в NLP сообществе, что будет полезно сосредоточиться на нем.

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

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

• линейная алгебра (в частности матричное умножение)
• правило цепочки дифференцирования функций от многих переменных

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

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

1. Что такое алгоритм обратного распространения

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

В таком контексте, обратное распространение — это эффективный алгоритм нахождения оптимальных весов нейронной сети, то есть тех, которые оптимизируют функцию потерь.
Стандартный способ нахождения этих весов, применение алгоритма градиентного спуска, который подразумевает нахождение частных производных функции потерь по всем весам.
Для тривиальных задач в которых всего две переменных, легко представить как работает градиентный спуск, если вы посмотрите на рисунок, то увидите трехмерный график функции потерь, как функции весов w1 и w2.

Рисунок 1. Визуальное объяснение алгоритма градиентного спуска.

Вначале мы не знаем оптимальные значения, то есть не знаем какие значения w1 и w2 минимизируют функцию потерь.

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

2. Word2Vec

Задача алгоритма word2vec, найти эмбеддинги слов в заданном текстовом корпусе, другими словами, это методика поиска представлений слов в низкой размерности. Как следствие, когда мы говорим о word2vec, мы обычно говорим о приложениях NLP.

Например, модель word2vec обученная со скрытым слоем размерности [N, 3], где N -количество слов в словаре, даст трехмерные эмбеддинги слов. Это значит что, например, слово ‘квартира’, будет представлено трехмерным вектором действительных чисел, который будет близок (воспринимайте это как Евклидову метрику), к представлению аналогичного слова, такого как ‘дом’. Другими словами, word2vec это техника отображения слов в числа.

В контексте word2vec используются две основные модели: мешок слов (CBOW) и скипграммы (skip-gram). Сначала мы рассмотрим простейшую модель, CBOW, с окном из одного слова, затем перейдем к окну из нескольких слов и наконец рассмотрим модель skip-gram.

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

3. Простая модель CBOW

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

Рисунок 2. Топология модели Continuous Bag-of-Words модели с контекстом из одного слова

Один входной слой, один скрытый слой и выходной слой, функция активации скрытого слоя
a = 1 (identity function, или функция линейной активации, хотя последнее неправильно).
В качестве функции активации выходного слоя используется Softmax.

Входной слой представлен one hot encoding вектором, длина которого совпадает с размером массива слов, все элементы данного вектора равны нулю, кроме элементов, индексы которых совпадают с индексами слов из контекста, по данным индексам значения вектора равны 1.

Пример: словарь [‘мама’, ‘мыла’, ‘раму’, ‘маша’, ‘ела’, ‘кашу’]
OneHot(‘маша’) = [0, 0, 0, 1, 0, 0]
OneHot([‘мама’, ‘маша’]) = [1, 0, 0, 1, 0, 0]
OneHot([‘мама’, ‘ела’, ‘кашу’]) = [1, 0, 0, 0, 1, 1]

Перейдем к весам, весовые коэффициенты между входным и скрытым слоем представлены матрицей W размера , матрица между скрытым и выходным слоем размером , где V — размер словаря, N — размер эмбеддинг вектора (то есть, те вектора которые и пытается найти word2vec)

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

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

3.1 Функция потерь (Loss function)

Исходя из топологии на рисунке 1, давайте запишем как посчитать значения скрытого и выходного слоев, при входе x:

где, h — сумма на скрытом слое, u — сумма на выходном слое, y — выход сети.

Теперь, предположим, мы обучаем модель по паре целевое слово, контекстное слово (wt, wc). Целевое слово представляет собой идеальное предсказание нейронной сети, в виде onehot encoding вектора.

Функция потерь должна будет оценить выходной слой, относительно onehot вектора wt (целевого слова).

Поскольку значения softmax можно интерпретировать как условные вероятности целевого слова, то учитывая контекстное слово функцию потерь можно записать в следующем виде:

$$display$$begin{equation*} mathcal{L} = -log mathbb{P}(w_t|w_c)=-log y_{j^*} =-log[mathbb{S}textrm{oftmax}(u_{j^*})]=-logleft(frac{exp{u_{j^*}}}{sum_i exp{u_i}}right), end{equation*}$$display$$

, где j* — ожидаемая позиция правильно предсказанного слова.
Добавление функции логарифма является стандартным подходом. Из данного выражения мы получаем уравнение (1):

$$display$$begin{equation} bbox[lightblue,5px,border:2px solid red]{ mathcal{L} = -u_{j^*} + log sum_i exp{(u_i)}. } label{eq:loss} end{equation} >(1)$$display$$

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

3.2 Алгоритм обратного распространения для модели CBOW

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

В первом разделе мы уже обсудили что в мире нейронный сетей эта проблема решается использованием градиентного спуска. На рисунке (1) показано как применить этот метод и обновить матрицы весов W и W`. Нам нужно найти производные и

Я считаю что самый простой способ понять как это сделать, это записать соотношения между функцией потерь и матрицами весов. Глядя на уравнение (1) ясно что функция потерь зависит от весов W и W`, через переменную u=[u1, …., uV], или

$$display$$begin{equation*} mathcal{L} = mathcal{L}(mathbf{u}(W,W’))=mathcal{L}(u_1(W,W’), u_2(W,W’),dots, u_V(W,W’)) . end{equation*}$$display$$

Получить производные можно из правила цепочки для функций многих переменных:

$$display$$begin{equation} frac{partialmathcal{L}}{partial W’_{ij}} = sum_{k=1}^Vfrac{partialmathcal{L}}{partial u_k}frac{partial u_k}{partial W’_{ij}} label{eq:dLdWp} end{equation} >(2)$$display$$

и

$$display$$begin{equation} frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^Vfrac{partialmathcal{L}}{partial u_k}frac{partial u_k}{partial W_{ij}} . label{eq:dLdW} end{equation} >(3)$$display$$

И это большая часть алгоритма обратного распространения, на данный момент нам просто нужно определить уравнения (2) и (3) для нашего случая.

Начнем с уравнения (2), обратите внимание что вес Wij, относится к матрице W, и соединяет нейрон i в скрытом слое с нейроном j в выходном слое, и соответственно оказывает влияние только на выход uj (соответственно и на yj).

Рисунок 3. (a) Выходной узел зависит от общего узла скрытого слоя только через элемент матрицы . (b) Но кроме того, этот же выходной узел зависит от общего входного узла через N элементов матрицы W.

Следовательно, среди всех производных , только одна, где k=j, будет отличаться от 0.

Уравнение (4):

$$display$$begin{equation} frac{partialmathcal{L}}{partial W’_{ij}} = frac{partialmathcal{L}}{partial u_j}frac{partial u_j} {partial W’_{ij}} label{eq:derivative#1} end{equation} >(4)$$display$$

Давайте посчитаем , уравнение (5):

$$display$$begin{equation} frac{partialmathcal{L}}{partial u_j} = -delta_{jj^*} + y_j := e_j label{eq:term#1} end{equation} >(5)$$display$$

, где — дельта Кронекера, функция двух целых переменных, которая равна 1, если они равны, и 0 в противном случае.

В уравнении (5) мы ввели вектор e размерности N (размер словаря), который мы используем чтобы снизить сложность обозначений, этот вектор представляет собой разницу между полученным и ожидаемым результатом, то есть это вектор ошибок предсказания.

Для второго члена правой части уравнения (4) мы получим уравнения (6):

$$display$$begin{equation} frac{partial u_j}{partial W’_{ij}} = sum_{k=1}^V W_{ik}x_k label{eq:term#2} end{equation} >(6)$$display$$

После подставновки уравнений (5) и (6) в уравнение (4) мы получим уравнение (7):

$$display$$begin{equation} bbox[white,5px,border:2px dotted red]{ frac{partialmathcal{L}}{partial W’_{ij}} = (-delta_{jj^*} + y_j) left(sum_{k=1}^V W_{ki}x_kright) } label{eq:backprop1} end{equation} >(7)$$display$$

Мы можем найти выполнить аналогичное упражнение для поиска производной , однако на этот раз отметим что после задания входа Xk, выход yj нейрона j зависит от всех элементов матрицы W соединенных со входом, как видно на рисунке 3(b). Поэтому мы должны оценивать все элементы в сумме. Прежде чем перейти к оценке , полезно перезаписать выражение для элемента uk из вектора u как:

$$display$$begin{equation*} u_k = sum_{m=1}^Nsum_{l=1}^VW’_{mk}W_{lm}x_l . end{equation*}$$display$$

Из этого уравнения легко вывести , поскольку единственный выживший член производной будет с индексами l=i и m=j, или же в виде уравнения (8):

$$display$$begin{equation} frac{partial u_k}{partial W_{ij}} = W’_{jk}x_i . label{eq:term#3} end{equation} >(8)$$display$$

Наконец применив уравнения (5) и (8) мы получим результат, уравнение (9):

$$display$$begin{equation} bbox[white,5px,border:2px dotted red]{ frac{partial mathcal{L}}{partial W_{ij}} = sum_{k=1}^V (-delta_{kk^*}+y_k)W’_{jk}x_i } label{eq:backprop2} end{equation} >(9)$$display$$

3.3 Градиентный спуск на основе полученных выше результатов

Теперь, когда у нас есть уравнения (7) и (9), у нас есть все необходимое для реализации одной итерации обучения нейросети на базе алгоритма обратного распространения ошибки, применяя градиентный спуск. Каждая итерация должна немного приближать к минимуму функцию потерь. После задания скорости обучения , мы можем обновить наши веса следующим образом:

3.4 Итерация алгоритма

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

4. Алгоритм обратного распространения для контекста из нескольких слов в модели CBOW

Мы уже знаем как работает алгоритм обратного распространения для модели CBOW с одним словом на входе. Теперь увеличим сложность и добавим в контекст несколько слов. Рисунок (4) показывает как выглядит нейросеть теперь. Вход теперь представляет собой серию OneHot Encoded векторов слов входящих в контекст. Количество слов в контексте является параметром который мы можем задавать при инициализации word2vec. Скрытый слой получает усреднение из всех контекстных слов.

Рисунок 4. Топология модели CBOW с контекстом из нескольких слов

Уравнения модели CBOW с несколькими контекстными словами являются обобщением уравнений модели CBOW с одним контекстным словом.

Обратите внимание, что для удобства мы ввели определение ‘усредненный’ входной вектор

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

$$display$$begin{equation} mathcal{L} = -logmathbb{P}(w_o|w_{c,1},w_{c,2},dots,w_{c,C})=-u_{j^*} + log sum_i exp{(u_i)}. end{equation} >(12)$$display$$

Снова выпишем уравнения по правилу цепочки, аналогично предыдущим:

$$display$$begin{equation} frac{partialmathcal{L}}{partial W’_{ij}} = sum_{k=1}^Vfrac{partialmathcal{L}}{partial u_k}frac{partial u_k}{partial W’_{ij}} end{equation} >(13)$$display$$

и

$$display$$begin{equation} frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^Vfrac{partialmathcal{L}}{partial u_k}frac{partial u_k}{partial W_{ij}} . end{equation} >(14)$$display$$

Производные функции потерь по весам такие же как для модели CBOW с одним словом на входе, с единственным отличием, что мы заменим входной вектор из одного слова на усредненный вектор из слов контекста. Выведем эти уравнения начиная с производной по

$inline$begin{equation} frac{partialmathcal{L}}{partial W’_{ij}} = sum_{k=1}^Vfrac{partialmathcal{L}}{partial u_k}frac{partial u_k}{partial W’_{ij}} = frac{partialmathcal{L}}{partial u_j}frac{partial u_j}{partial W’_{ij}} = (-delta_{jj^*} + y_j) left(sum_{k=1}^V W_{ki}overline{x}_kright) end{equation} > (15)$inline$

Теперь запишем производную по :

$$display$$begin{equation} frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^Vfrac{partialmathcal{L}}{partial u_k}frac{partial}{partial W_{ij}}left(frac{1}{C}sum_{m=1}^Nsum_{l=1}^V W’_{mk}sum_{c=1}^C W_{lm}x_l^{(c)}right)=frac{1}{C}sum_{k=1}^Vsum_{c=1}^C(-delta_{kk^*} + y_k)W’_{jk}x_i^{(c)} . end{equation} >(16)$$display$$

Подведя итог имеем следующее:

$$display$$begin{equation} bbox[white,5px,border:2px dotted red]{ frac{partialmathcal{L}}{partial W’_{ij}} = (-delta_{jj^*} + y_j) left(sum_{k=1}^V W_{ki}overline{x}_kright) } label{eq:backprop1_multi} end{equation} >(17)$$display$$

и

$$display$$begin{equation} bbox[white,5px,border:2px dotted red]{ frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^V(-delta_{kk^*} + y_k)W’_{jk}overline{x}_i . } label{eq:backprop2_multi} end{equation} > (18)$$display$$

5. Алгоритм обратного распространения для модели Skip-gram

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

Рисунок 5.Топология Skip-gram модели.

Уравнения skip-gram модели следующие:

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

Для модели skip-gram функция потерь зависит от переменных
через:

$$display$$begin{equation*} mathcal{L} = mathcal{L}(mathbf{u_1}(W,W’), mathbf{u_2}(W,W’), dots, mathbf{u_C}(W,W’))\=mathcal{L}(u_{1,1}(W,W’), u_{1,2}(W,W’), dots, u_{C,V}(W,W’)) end{equation*}$$display$$

Соответственно правило цепочки выглядит так:

$$display$$begin{equation*} frac{partialmathcal{L}}{partial W’_{ij}} = sum_{k=1}^Vsum_{c=1}^Cfrac{partialmathcal{L}}{partial u_{c,k}}frac{partial u_{c,k}}{partial W’_{ij}} end{equation*}$$display$$

и

$$display$$begin{equation*} frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^Vsum_{c=1}^Cfrac{partialmathcal{L}}{partial u_{c,k}}frac{partial u_{c,k}}{partial W_{ij}} . end{equation*}$$display$$

Посчитаем , получим:

$$display$$begin{equation*} frac{partialmathcal{L}}{partial u_{c,j}} = -delta_{jj_c^*} + y_{c,j} := e_{c,j} end{equation*}$$display$$

Аналогично модели CBOW получаем:

$$display$$begin{equation*} frac{partialmathcal{L}}{partial W’_{ij}} = sum_{k=1}^Vsum_{c=1}^Cfrac{partialmathcal{L}}{partial u_{c,k}}frac{partial u_{c,k}}{partial W’_{ij}} = sum_{c=1}^Cfrac{partialmathcal{L}}{partial u_{c,j}}frac{partial u_{c,j}}{partial W’_{ij}} = sum_{c=1}^C(-delta_{jj_c^*} + y_{c,j}) left(sum_{k=1}^V W_{ki}x_kright) end{equation*}$$display$$

Производная по самая сложная, но выполнимая:

$$display$$begin{equation*} frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^Vsum_{c=1}^Cfrac{partialmathcal{L}}{partial u_{c,k}}frac{partial}{partial W_{ij}}left(sum_{m=1}^Nsum_{l=1}^V W’_{mk} W_{lm}x_lright)=sum_{k=1}^Vsum_{c=1}^C (-delta_{kk_c^*} + y_{c,k})W’_{jk}x_i . end{equation*}$$display$$

Подведя итог, для модели skip-gram мы имеем:

$$display$$begin{equation} bbox[white,5px,border:2px dotted red]{ frac{partialmathcal{L}}{partial W’_{ij}} = sum_{c=1}^C(-delta_{jj_c^*} + y_{c,j}) left(sum_{k=1}^V W_{ki}x_kright) } label{eq:backprop1_skip} end{equation} >(21)$$display$$

и

$$display$$begin{equation} bbox[white,5px,border:2px dotted red]{ frac{partialmathcal{L}}{partial W_{ij}} = sum_{k=1}^Vsum_{c=1}^C (-delta_{kk_c^*} + y_{c,k})W’_{jk}x_i . } label{eq:backprop2_skip} end{equation} >(22)$$display$$

6. Что дальше

Мы подробно рассмотрели как работает алгоритм обратного распространения в случае word2vec. Однако рассмотренная реализация неэффективна для больших текстовых корпусов. В оригинальной статье [2] применяются некоторые трюки для преодоления этих проблем (иерархический softmax, negative sampling), однако я не буду на них останавливаться подробно. Вы можете найти подробное описание по ссылке [1].

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

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

Надеюсь увидеть вас там!

Дополнительные ссылки

[1] X. Rong, word2vec Parameter Learning Explained, arXiv:1411.2738 (2014).
[2] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient Estimation of Word Representations in Vector Space, arXiv:1301.3781 (2013).

Метод обратного распространения ошибки — метод обучения многослойного перцептрона. Впервые метод был описан в 1974 г. Полем Дж. Вербосом^[1], а также независимо и одновременно А. И. Галушкиным^[2]. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом^[3] и независимо и одновременно С. И. Барцевым и В. А. Охониным (Красноярская группа)^[4]. Это итеративный градиентный алгоритм, который используется с целью минимизации ошибки работы многослойного перцептрона и получения желаемого выхода.

Основная идея этого метода состоит в распространении сигналов ошибки от выходов сети к её входам, в направлении, обратном прямому распространению сигналов в обычном режиме работы. Барцев и Охонин предложили сразу общий метод («принцип двойственности»), приложимый к более широкому классу систем, включая системы с запаздыванием, распределённые системы, и т. п.^[5]

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

Cигмоидальные функции активации[]

Наиболее часто в качестве функций активации используются следующие виды сигмоид:

Функция Ферми (экспоненциальная сигмоида):

Рациональная сигмоида:

Гиперболический тангенс:

где s — выход сумматора нейрона,  — произвольная константа.

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

Функция оценки работы сети[]

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

Метод наименьших квадратов далеко не всегда является лучшим выбором оценки. Тщательное конструирование функции оценки позволяет на порядок поысить эффективность обучения сети, а также получать дополнительную информацию — «уровень уверенности» сети в даваемом ответе^[6].

Описание алгоритма[]

Файл:Neuro.PNG

Алгоритм обратного распространения ошибки применяется для многослойного перцептрона. У сети есть входы , выходы Outputs и внутренние узлы. Перенумеруем все узлы (включая входы и выходы) числами от 1 до N. Обозначим через вес, стоящий на ребре, соединяющем i-ый и j-ый узлы, а через  — выход i-го узла. Если у нас m тестовых примеров с целевыми значениями выходов , , то функция ошибки, полученная по методу наименьших квадратов, выглядит так:

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

где

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

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

Если же j-й узел — не на последнем уровне, то у него есть выходы; обозначим их через Children(j). В этом случае

,

и

.

Ну а  — это в точности аналогичная поправка, но вычисленная для узла следующего уровня (будем обозначать ее через  — от она отличается отсутствием множителя . Поскольку мы научились вычислять поправку для узлов последнего уровня и выражать поправку для узла более низкого уровня через поправки более высокого, можно уже писать алгоритм. Именно из-за этой особенности вычисления
поправок алгоритм называется алгоритмом обратного распространения ошибки (backpropagation). Краткое резюме проделанной работы:

• для узла последнего уровня

• для внутреннего узла сети

• для всех узлов

Получающийся алгоритм представлен ниже. На вход алгоритму, кроме указанных параметров, нужно также подавать в каком-нибудь формате структуру сети. На практике очень хорошие результаты показывают сети достаточно простой структуры, состоящие из двух уровней нейронов — скрытого уровня (hidden units) и нейронов-выходов (output units); каждый вход сети соединен со всеми скрытыми нейронами, а результат работы каждого скрытого нейрона подается на вход каждому из нейронов-выходов. В таком случае достаточно подавать на вход количество нейронов скрытого уровня.

Алгоритм[]

Алгоритм:
BackPropagation

1. Инициализировать маленькими случайными значениями.
2. Повторить NUMBER_OF_STEPS раз:

   Для всех d от 1 до m:

   1. Подать на вход сети и подсчитать выходы каждого узла.
   2. Для всех

      .

   3. Для каждого уровня l, начиная с предпоследнего:

      Для каждого узла j уровня l вычислить

      .

   4. Для каждого ребра сети {i, j}

      .

3. Выдать значения .

Математическая интерпретация обучения нейронной сети[]

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

Обучение нейронной сети характеризуется четырьмя специфическими ограничениями, выделяющих обучение нейросетей из общих задач оптимизации: астрономическое число параметров, необходимость высокого параллелизма при обучении, многокритериальность решаемых задач, необходимость найти достаточно широкую область, в которой значения всех минимизируемых функций близки к минимальным. В остальном проблему обучения можно, как правило, сформулировать как задачу минимизации оценки. Осторожность предыдущей фразы («как правило») связана с тем, что на самом деле нам неизвестны и никогда не будут известны все возможные задачи для нейронных сетей, и, быть может, где-то в неизвестности есть задачи, которые несводимы к минимизации оценки. Минимизация оценки — сложная проблема: параметров астрономически много (для стандартных примеров, реализуемых на РС — от 100 до 1000000), адаптивный рельеф (график оценки как функции от подстраиваемых параметров) сложен, может содержать много локальных минимумов.

Недостатки алгоритма[]

Несмотря на многочисленные успешные применения обратного распространения, оно не является панацеей. Больше всего неприятностей приносит неопределенно долгий процесс обучения. В сложных задачах для обучения сети могут потребоваться дни или даже недели, она может и вообще не обучиться. Причиной может быть одна из описанных ниже.

Паралич сети[]

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

Локальные минимумы[]

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

Размер шага[]

Внимательный разбор доказательства сходимости^[3] показывает, что коррекции весов предполагаются бесконечно малыми. Ясно, что это неосуществимо на практике, так как ведет к бесконечному времени обучения. Размер шага должен браться конечным, и в этом вопросе приходится опираться только на опыт. Если размер шага очень мал, то сходимость слишком медленная, если же очень велик, то может возникнуть паралич или постоянная неустойчивость. П. Д. Вассерман^[7] описал адаптивный алгоритм выбора шага, автоматически корректирующий размер шага в процессе обучения. В книге А. Н. Горбаня^[8] предложена разветвлённая технология оптимизации обучения.

См. также[]

• Сигмоид
• Многослойный перцептрон

Литература[]

1. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. — М.: «Мир», 1992.

1. Хайкин С. Нейронные сети: Полный курс. Пер. с англ. Н. Н. Куссуль, А. Ю. Шелестова. 2-е изд., испр. — М.: Издательский дом Вильямс, 2008, 1103 с.

Внешние ссылки[]

1. Копосов А.И., Щербаков И.Б., Кисленко Н.А., Кисленко О.П., Варивода Ю.В. и др. Отчет по научно-исследовательской работе «Создание аналитического обзора информационных источников по применению нейронных сетей для задач газовой технологии». — Москва: ВНИИГАЗ, 1995.

1. Миркес Е. М., Нейроинформатика: Учеб. пособие для студентов с программами для выполнения лабораторных работ. Красноярск: ИПЦ КГТУ, 2002, 347 с. Рис. 58, табл. 59, библиогр. 379 наименований. ISBN 5-7636-0477-6

Примечания[]