Реализация алгоритма обратного распространения ошибки

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

Открытие метода обратного распространения ошибки стало одним из наиболее значимых событий в области искусственного интеллекта. В актуальном виде он был предложен в 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 едва ли справится с обучением современной сетки. Так что же делать? О некоторых приёмах мы расскажем в следующей главе.

Поскольку я столкнулся с существенными затруднениями в поисках объяснения механизма обратного распространения ошибки, которое мне понравилось бы, я решил написать собственный пост об обратном распространении ошибки реализовав алгоритм 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).