Сверточная сеть на python. Часть 2. Вывод формул для обучения модели +65



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

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


Это просто частная производная функции потерь $E$ по выходу модели.

$\begin{array}{rcl} \dfrac{\partial E}{\partial y^{l}_{i}} &=& \dfrac{\partial \frac{1}{2}\sum_{i=0}^{n}(y^{truth}_i-y^l_i)^2}{\partial y^{l}_{i}} \\ &=&\dfrac{\partial \frac{1}{2}((y^{truth}_0-y^l_0)^2+\ldots+(y^{truth}_i-y^l_i)^2+\ldots+(y^{truth}_n-y^l_n)^2)}{\partial y^{l}_{i}} \\ &=& \dfrac{\partial \frac{1}{2}(y^{truth}_i-y^l_i)^2}{\partial y^{l}_{i}} = \frac{1}{2}\cdot2\cdot(y^{truth}_i-y^l_i)^{2-1}\cdot\frac{\partial (y^{truth}_i-y^l_i)}{\partial y^{l}_{i}} \\ &=& (y^{truth}_i-y^l_i)\cdot(-1)=y^l_i-y^{truth}_i \end{array}$


С производной $\partial \frac{1}{2}(y^{truth}_i-y^l_i)^2$ в числителе обращаемся как с производной от сложной функции: $(u^n)'=nu^{n-1}\cdot u' $. Здесь, кстати, видно, как сокращаются $\frac{1}{2}$ и $2$, и становится понятно, зачем в формуле мы изначально добавили $\frac{1}{2}$

Сначала я использовал среднеквадратическое отклонение, но для задачи классификации лучше применить cross-entropy (ссылка с объяснением). Ниже формула для backprop, попытался максимально подробно написать вывод формулы:

$\begin{array}{rcl} \dfrac{\partial E}{\partial y^{l}_{i}}&=&\dfrac{\partial (-\sum_{i=0}^{n}(y^{truth}_i\cdot ln(y^l_i))}{\partial y^{l}_{i}}\\ &=&\dfrac{\partial (-(y^{truth}_0 ln(y^l_0)+\ldots+y^{truth}_i ln(y^l_i)+\ldots+y^{truth}_n ln(y^l_n))}{\partial y^{l}_{i}}\\ &=&\dfrac{\partial (-y^{truth}_i ln(y^l_i))}{\partial y^{l}_{i}}=-\dfrac{y^{truth}_i}{y^l_i} \end{array}$


Помним, что $\large ln(x)'=\frac{1}{x}$

Вывод формулы backprop через функции активации

… через ReLU


$ f'_{ReLU}=\frac{\mathrm{\partial} y^l_i}{\mathrm{\partial} x^l_i}= \left\{\begin{matrix} 1, & if\enspace x^l_i > 0\\ 0, & otherwise\\ \end{matrix}\right. $


где $\large \frac{\partial y^{l}_i}{\partial x^l_i}$ — обозначение backprop через функцию активации.

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

… через сигмоиду


$\begin{array}{rcl} f'_{sigmoid}&=&\dfrac{\mathrm{\partial} }{\mathrm{\partial} x^l_i}\left ( \dfrac{1}{1+e^{-x^l_i}} \right )=\dfrac{\mathrm{\partial} }{\mathrm{\partial} x^l_i} ( 1+e^{-x^l_i} )^{-1}\\ &=&-( 1+e^{-x^l_i} )^{-2}(-e^{-x^l_i})=\dfrac{e^{-x^l_i}}{(1+e^{-x^l_i})^2}\\ &=&\dfrac{1}{1+e^{-x^l_i}} \cdot \dfrac{e^{-x^l_i}}{1+e^{-x^l_i}}=\dfrac{1}{1+e^{-x^l_i}} \cdot \dfrac{(1+e^{-x^l_i})-1}{1+e^{-x^l_i}}\\ &=&\dfrac{1}{1+e^{-x^l_i}} \cdot \left (\dfrac{1+e^{-x^l_i}}{1+e^{-x^l_i}}-\dfrac{1}{1+e^{-x^l_i}}\right )=\dfrac{1}{1+e^{-x^l_i}} \cdot \left (1-\dfrac{1}{1+e^{-x^l_i}}\right )\\ &=&f_{sigmoid} \cdot(1-f_{sigmoid}) \end{array}$


Здесь нужно помнить, что $(e^{u(x)})'=e^{u(x)} \cdot (u(x))'$
При этом $\large f_{sigmoid}=\frac{1}{1+e^{-x^l_i}}$ — это формула сигмоиды

Далее обозначим $ \large \frac{\partial E}{\partial x^l_i} $ как $\large \delta ^l_i $ (где $\large \frac{\partial E}{\partial x^l_i} = \frac{\partial E}{\partial y^l_i} \frac{\partial y^l_i}{\partial x^l_i}$)

… также через softmax (или здесь)


Эти расчеты показались мне немного сложнее, так как функция softmax для i-того выхода зависит не только от своего $x^l_i$, но и от всех других $x^l_j \enspace \forall i,j \in (0,...,n)$, сумма которых лежит в знаменателе формулы для прямого прохожденя через сеть. Поэтому и формула для backprop “распадается” на две: частная производная по $x^l_i$ и $x^l_j$:

$\begin{array}{rcl} \dfrac{\partial y^l_i}{\partial x^l_i}&=&\dfrac{\partial }{\partial x^l_i}\left(\dfrac{e^{x^l_i}}{\sum_{k=0}^{n}e^{x^l_k}}\right)= \dfrac{e^{x^l_i}\cdot \sum_{k=0}^{n}e^{x^l_k} - e^{x^l_i}\cdot e^{x^l_i}}{\left(\sum_{k=0}^{n}e^{x^l_k}\right)^2}\\ &=&\dfrac{e^{x^l_i}\cdot \left( \sum_{k=0}^{n}e^{x^l_k} - e^{x^l_i}\right)}{\sum_{k=0}^{n}e^{x^l_k}\cdot \sum_{k=0}^{n}e^{x^l_k}}= y^l_i\cdot \dfrac{\sum_{k=0}^{n}e^{x^l_k} - e^{x^l_i}}{\sum_{k=0}^{n}e^{x^l_k}}\\ &=&y^l_i\cdot \left(\dfrac{\sum_{k=0}^{n}e^{x^l_k}}{\sum_{k=0}^{n}e^{x^l_k}} - \dfrac{e^{x^l_i}}{\sum_{k=0}^{n}e^{x^l_k}}\right)=y^l_i\cdot(1-y^l_i) \end{array}$


Применяем формулу $\large \left ( \frac{u}{v} \right )' = \frac{u'v-uv'}{v^2}$ где $u =e^{x^l_i}$ и $\large v = \sum_{k=0}^{n}e^{x^l_k}$
При этом $\large \frac{\partial}{\partial x^l_i} \sum_{k=0}^{n}e^{x^l_k}= \frac{\partial(e^{x^l_0} +\ldots+ e^{x^l_i} +\ldots+ e^{x^l_n})}{\partial x^l_i}= \frac{\partial e^{x^l_i}}{\partial x^l_i} = e^{x^l_i}$

И частная производная по $x^l_j$:

$\begin{array}{rcl} \dfrac{\partial y^l_i}{\partial x^l_j}&=&\dfrac{\partial}{\partial x^l_j}\left(\dfrac{e^{x^l_i}}{\sum_{k=0}^{n}e^{x^l_k}}\right)=\dfrac{0\cdot \sum_{k=0}^{n}e^{x^l_k} - e^{x^l_i}\cdot e^{x^l_j}}{\left(\sum_{k=0}^{n}e^{x^l_k}\right)^2}\\ &=&\dfrac{e^{x^l_i}\cdot e^{x^l_j}}{\sum_{k=0}^{n}e^{x^l_k}\cdot \sum_{k=0}^{n}e^{x^l_k}}=-y^l_i\cdot y^l_j \end{array}$


Исходя из формулы выше, есть нюанс с тем, что должна возвращать функция (в коде) при обратном распространении ошибки для $\large \frac{y^l}{x^l} $ при softmax, так как в этом случае для расчета одной $y_i^l$ используются все $x^l$, или, другими словами, каждая $x_i^l$ влияет на все $y^l$:

В случае softmax $\large \frac{\partial E}{\partial x^l_i}$ будет равен $\large \sum_{k=0}^{n} \frac{\partial E}{\partial y^l_k} \frac {\partial y^l_k} {\partial x^l_i}$ (появилась сумма!), то есть:

$\frac{\partial E}{\partial x^l_i}= \frac{\partial E}{\partial y^l_0} \frac {\partial y^l_0} {\partial x^l_i} + ... + \frac{\partial E}{\partial y^l_1} \frac {\partial y^l_1} {\partial x^l_i} + ... + \frac{\partial E}{\partial y^l_n} \frac {\partial y^l_n} {\partial x^l_i} \qquad \forall i \in (0,...n) $


При этом значения $\large \frac{\partial E}{\partial y^l_k}$ для всех $k$ у нас есть, это backprop через лосс функцию. Осталось найти $\large \frac {\partial y^l_k} {\partial x^l_i}$ для всех $k$ и всех $i$ — то есть это матрица. Ниже матричное умножение в “развернутом” виде, чтобы лучше было понятно, почему $\large \frac {\partial y^l_k} {\partial x^l_i}$ — матрица и откуда появляется матричное умножение.

$ \begin{bmatrix} &\frac{\partial E}{\partial x^{l}_{0}} &\frac{\partial E}{\partial x^{l}_{1}} & ... &\frac{\partial E}{\partial x^{l}_{n}} \end{bmatrix} = \\= \scriptsize \begin{bmatrix} & (\frac{\partial E}{\partial y^{l}_{0}}\frac{\partial y^{l}_{0}}{\partial x^{l}_{0}}+\frac{\partial E}{\partial y^{l}_{1}}\frac{\partial y^{l}_{1}}{\partial x^{l}_{0}}+\ldots+\frac{\partial E}{\partial y^{l}_{n}}\frac{\partial y^{l}_{n}}{\partial x^{l}_{0}}) & (\frac{\partial E}{\partial y^{l}_{0}}\frac{\partial y^{l}_{0}}{\partial x^{l}_{1}}+\frac{\partial E}{\partial y^{l}_{1}}\frac{\partial y^{l}_{1}}{\partial x^{l}_{1}}+\ldots+\frac{\partial E}{\partial y^{l}_{n}}\frac{\partial y^{l}_{n}}{\partial x^{l}_{1}}) & ... & (\frac{\partial E}{\partial y^{l}_{0}}\frac{\partial y^{l}_{0}}{\partial x^{l}_{n}}+\frac{\partial E}{\partial y^{l}_{1}}\frac{\partial y^{l}_{1}}{\partial x^{l}_{n}}+\ldots+\frac{\partial E}{\partial y^{l}_{n}}\frac{\partial y^{l}_{n}}{\partial x^{l}_{n}}) \end{bmatrix} \\= \begin{bmatrix} &\frac{\partial E}{\partial y^{l}_{0}} &\frac{\partial E}{\partial y^{l}_{1}} & ... &\frac{\partial E}{\partial y^{l}_{n}} \end{bmatrix} \begin{bmatrix} &\frac{\partial y^{l}_{0}}{\partial x^{l}_{0}} &\frac{\partial y^{l}_{0}}{\partial x^{l}_{1}}&...&\frac{\partial y^{l}_{0}}{\partial x^{l}_{n}}\\ &\frac{\partial y^{l}_{1}}{\partial x^{l}_{0}} &\frac{\partial y^{l}_{1}}{\partial x^{l}_{1}}&...&\frac{\partial y^{l}_{1}}{\partial x^{l}_{n}}\\ &...&...&...&...\\ &\frac{\partial y^{l}_{n}}{\partial x^{l}_{0}} &\frac{\partial y^{l}_{n}}{\partial x^{l}_{1}}&...&\frac{\partial y^{l}_{n}}{\partial x^{l}_{n}}\\ \end{bmatrix}$


Речь шла как раз об этой последней в разложении матрице — $\large \frac{\partial y^l}{\partial x^l}$. Посмотрите, как при перемножении матриц $\large \frac{\partial E}{\partial y^l}$ и $\large \frac{\partial y^l}{\partial x^l}$ мы получаем $\large \frac{\partial E}{\partial x^l}$. А значит, выходом функции backprop (в коде) для softmax должна быть матрица $\large \frac{\partial y^l}{\partial x^l}$, при умножении на которую уже рассчитанного на тот момент $\large \frac{\partial E}{\partial y^l}$, мы и получим $\large \frac{\partial E}{\partial x^l}$.

Бэкпроп через полносвязную сеть



Вывод формулы backprop для обновления матрицы весов $w^l$ fc-сети


$\begin{array}{rcl} \dfrac{\partial E}{\partial w^l_{ki}}&=&\dfrac{\partial E}{\partial y^l_i}\dfrac{\partial y^l_i}{\partial x^l_i}\dfrac{\partial x^l_i}{\partial w^l_{ki}}=\delta^l_i \cdot \dfrac{\partial x^l_i}{\partial w^l_{ki}}=\delta^l_i \cdot \dfrac{\partial \left (\sum^m_{k'=0}w^l_{k'i}y^{l-1}_{k'}+b^l_i \right)}{\partial w^l_{ki}}\\ &=&\delta^l_i \cdot \dfrac{\partial \left (w^l_{0i}y^{l-1}_{0}+\ldots+w^l_{ki}y^{l-1}_{k}+...w^l_{mi}y^{l-1}_{m}+b^l_i \right)}{\partial w^l_{ki}}=\delta^l_i \cdot y^{l-1}_k\\ &&\forall i \in (0,...,n) \enspace \forall k \in (0,...,m) \end{array}$


Раскладываем сумму в числителе и получаем, что все частные производные равны нулю, кроме случая $ \large \frac{\partial w^l_{ki}y^{l-1}_{k}}{\partial w^l_{ki}} $, что равняется $ y^{l-1}_k $. Этот случай происходит, когда $ k'=k $. Штрих здесь для обозначения “внутреннего” цикла по $k$, то есть это совсем другой итератор, не связанный с $k$ из $ \large \frac{\partial E}{\partial w^l_{ki}} $

И вот так это будет выглядеть матричном виде:

$\frac{\partial E}{\partial w^l}=\left(y^{l-1} \right)^T \cdot \delta^l \\ \tiny (m \times n) \enspace \enspace \enspace (m \times 1) \enspace \enspace (1 \times n)$


Размерность матрицы $ y^{l-1} $ равна $(1 \times m)$, и для того, чтобы произвести матричное умножение, матрицу следует транспонировать. Ниже привожу матрицы полностью, в “развернутом” виде, чтобы выкладки казались яснее.

$\begin{bmatrix} & \frac{\partial E}{\partial w^{l}_{00}} & \frac{\partial E}{\partial w^{l}_{01}} & ... & \frac{\partial E}{\partial w^{l}_{0n}} \\ & \frac{\partial E}{\partial w^{l}_{10}} & \frac{\partial E}{\partial w^{l}_{11}} & ... & \frac{\partial E}{\partial w^{l}_{1n}} \\ &... & ... & ... & ... \\ & \frac{\partial E}{\partial w^{l}_{m0}} & \frac{\partial E}{\partial w^{l}_{m1}} & ... & \frac{\partial E}{\partial w^{l}_{mn}} \end{bmatrix} = \begin{bmatrix} & y^{l-1}_0\delta^{l}_0 & y^{l-1}_0\delta^{l}_1 & ... & y^{l-1}_0\delta^{l}_n \\ & y^{l-1}_1\delta^{l}_0 & y^{l-1}_1\delta^{l}_1 & ... & y^{l-1}_1\delta^{l}_n \\ &... & ... & ... & ... \\ & y^{l-1}_m\delta^{l}_0 & y^{l-1}_m\delta^{l}_1 & ... & y^{l-1}_m\delta^{l}_n \end{bmatrix} \\ \qquad \qquad \qquad \qquad \qquad \qquad = \begin{bmatrix} & y^{l-1}_0 \\ & y^{l-1}_1 \\ & ... \\ & y^{l-1}_m \end{bmatrix} \begin{bmatrix} & \delta^{l}_0 & \delta^{l}_1 & ... & \delta^{l}_n \end{bmatrix}$



Вывод формулы backprop для обновления матрицы $ b^{l} $


Для bias все вычисления очень схожи с предыдущим пунктом:

$\begin{array}{rcl} \dfrac{\partial E}{\partial b^l_{i}}&=&\dfrac{\partial E}{\partial y^l_i}\dfrac{\partial y^l_i}{\partial x^l_i}\dfrac{\partial x^l_i}{\partial b^l_{i}}=\delta^l_i \cdot \dfrac{\partial x^l_i}{\partial b^l_{i}}\\ &=&\delta^l_i \cdot \dfrac{\partial \left (\sum^m_{k'=0}w^l_{k'i}y^{l-1}_{k'}+b^l_i \right)}{\partial b^l_{i}}=\delta^l_i\\ &&\forall i \in (0,...,n) \end{array}$


Понятно, что $ \large \frac{\partial \left (\sum^m_{k'=0}w^l_{k'i}y^{l-1}_{k'}+b^l_i \right)}{\partial b^l_{i}} =1 $

В матричном виде тоже все довольно просто:

$\frac{\partial E}{\partial b^l}=\delta^l\\ \tiny (1 \times n) \enspace \enspace (1 \times n)$


Вывод формулы backprop через $y^{l-1} $


В формуле ниже сумма по $i$ возникает от того, что каждый $ y^{l-1}_k$ соединен с каждым $ x^{l}_i$ (помним, что слой называется полносвязной)

$\begin{array}{rcl} \dfrac{\partial E}{\partial y^{l-1}_{k}}&=&\sum_{i=0}^{n} \delta^l_i \cdot \dfrac{\partial x^l_i}{\partial y^{l-1}_{k}}=\sum_{i=0}^{n} \delta^l_i \cdot \dfrac{\partial \left (\sum^m_{k'=0}w^l_{k'i}y^{l-1}_{k'}+b^l_i \right)}{\partial y^{l-1}_{k}}\\ &=&\sum_{i=0}^{n} \delta^l_i \cdot \dfrac{\partial \left (w^l_{0i}y^{l-1}_{0}+\ldots+w^l_{ki}y^{l-1}_{k}+...w^l_{mi}y^{l-1}_{m}+b^l_i \right)}{\partial y^{l-1}_{k}}\\ &=&\sum_{i=0}^{n} \delta^l_i \cdot w^l_{ki}\\ &&\forall i \in (0,...,n) \enspace \forall k \in (0,...,m) \end{array}$


Раскладываем числитель и видим, что все частные производные равны нулю, кроме того случая, когда $k'=k$:

$\frac{\partial \left (w^l_{0i}y^{l-1}_{0}+\ldots+w^l_{ki}y^{l-1}_{k}+...w^l_{mi}y^{l-1}_{m}+b^l_i \right)}{\partial y^{l-1}_{k}} = \frac{\partial w^l_{ki}y^{l-1}_{k}}{\partial y^{l-1}_{k}} = w^l_{ki}$


И в матричном виде:

$\frac {\partial E} {\partial y^{l-1}}=\delta^l \cdot (w^l)^{T}\\ \tiny (1 \times m) \enspace \enspace \enspace (1 \times n) \enspace (n \times m)$


Далее матрицы в “раскрытом” виде. Замечу, что индексы самой последней матрицы я намеренно оставил в том виде, в каком они были до транспонирования, чтобы лучше было видно, какой элемент куда перешел после транспонирования.

$\begin{bmatrix} & \frac{\partial E}{\partial y^{l-1}_{0}} & \frac{\partial E}{\partial y^{l-1}_{1}} & ... & \frac{\partial E}{\partial y^{l-1}_{m}} \end{bmatrix} =\\ \scriptsize \begin{bmatrix} & (\delta^{l}_1w^{l}_{00}+\delta^{l}_2w^{l}_{01}+\ldots+\delta^{l}_nw^{l}_{0n}) & (\delta^{l}_1w^{l}_{10}+\delta^{l}_2w^{l}_{11}+\ldots+\delta^{l}_nw^{l}_{1n}) & ... & (\delta^{l}_1w^{l}_{m0}+\delta^{l}_2w^{l}_{m1}+\ldots+\delta^{l}_nw^{l}_{mn}) \end{bmatrix} = \\ \enspace \enspace = \begin{bmatrix} & \delta^{l}_0 & \delta^{l}_1 & ... & \delta^{l}_n \end{bmatrix} \begin{bmatrix} & w^{l}_{00} & w^{l}_{01} & ... & w^{l}_{0n} \\ & w^{l}_{10} & w^{l}_{11} & ... & w^{l}_{1n} \\ &... & ... & ... & ... \\ & w^{l}_{m0} & w^{l}_{m1} & ... & w^{l}_{mn} \end{bmatrix}^T \\= \begin{bmatrix} & \delta^{l}_0 & \delta^{l}_1 & ... & \delta^{l}_n \end{bmatrix} \begin{bmatrix} & w^{l}_{00} & w^{l}_{10} & ... & w^{l}_{m0} \\ & w^{l}_{01} & w^{l}_{11} & ... & w^{l}_{m1} \\ &... & ... & ... & ... \\ & w^{l}_{0n} & w^{l}_{1n} & ... & w^{l}_{mn} \end{bmatrix}$


Далее обозначаем $ \large \frac{\partial E}{\partial y^{l-1}_{k}} $ как $ \delta^{l-1}_k $, и все формулы для обратного распространения ошибки через последующие слои полносвязной сети вычисляются аналогичным образом.

Бэкпроп через макспулинг


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

Вот реализация макспулинга на python:

code_demo_maxpool.py
ссылка на git
import numpy as np

y_l = np.array([
	[1,0,2,3],
	[4,6,6,8],
	[3,1,1,0],
	[1,2,2,4]])

other_parameters={
	'convolution':False,
	'stride':2,
	'center_window':(0,0),
	'window_shape':(2,2)
}

def maxpool(y_l, conv_params):
	indexes_a, indexes_b = create_indexes(size_axis=conv_params['window_shape'], center_w_l=conv_params['center_window'])
	stride = conv_params['stride']
	# выходные матрицы будут расширяться по мере добавления новых элементов
	y_l_mp = np.zeros((1,1)) # матрица y_l после операции макспулинга
	y_l_mp_to_y_l = np.zeros((1,1), dtype='<U32') # матрица для backprop через слой макспулинга (внутри матрицы будет храниться текст)
	# в зависимости от типа операции меняется основная формула функции
	if conv_params['convolution']:
		g = 1 # операция конволюции
	else:
		g = -1 # операция корреляции
	# итерация по i и j входной матрицы y_l из предположения, что размерность выходной матрицы будет такой же
	for i in range(y_l.shape[0]):
		for j in range(y_l.shape[1]):
			result = -np.inf
			element_exists = False
			for a in indexes_a:
				for b in indexes_b:
					# проверка, чтобы значения индексов не выходили за границы
					if i*stride - g*a >= 0 and j*stride - g*b >= 0 					and i*stride - g*a < y_l.shape[0] and j*stride - g*b < y_l.shape[1]:
						if y_l[i*stride - g*a][j*stride - g*b] > result:
							result = y_l[i*stride - g*a][j*stride - g*b]
							i_back = i*stride - g*a
							j_back = j*stride - g*b
						element_exists = True
			# запись полученных результатов только в том случае, если для данных i и j были произведены вычисления
			if element_exists:
				if i >= y_l_mp.shape[0]:
					# добавление строки, если не существует
					y_l_mp = np.vstack((y_l_mp, np.zeros(y_l_mp.shape[1])))
					# матрица y_l_mp_to_y_l расширяется соответственно матрице y_l_mp
					y_l_mp_to_y_l = np.vstack((y_l_mp_to_y_l, np.zeros(y_l_mp_to_y_l.shape[1])))
				if j >= y_l_mp.shape[1]:
					# добавление столбца, если не существует
					y_l_mp = np.hstack((y_l_mp, np.zeros((y_l_mp.shape[0],1))))
					y_l_mp_to_y_l = np.hstack((y_l_mp_to_y_l, np.zeros((y_l_mp_to_y_l.shape[0],1))))
				y_l_mp[i][j] = result
				# в матрице y_l_mp_to_y_l хранятся координаты значений,
				# которые соответствуют выбранным в операции максипулинга ячейкам из матрицы y_l
				y_l_mp_to_y_l[i][j] = str(i_back) + ',' + str(j_back)
	return y_l_mp, y_l_mp_to_y_l

def create_axis_indexes(size_axis, center_w_l):
	coordinates = []
	for i in range(-center_w_l, size_axis-center_w_l):
		coordinates.append(i)
	return coordinates

def create_indexes(size_axis, center_w_l):
	# расчет координат на осях ядра свертки в зависимости от номера центрального элемента ядра
	coordinates_a = create_axis_indexes(size_axis=size_axis[0], center_w_l=center_w_l[0])
	coordinates_b = create_axis_indexes(size_axis=size_axis[1], center_w_l=center_w_l[1])
	return coordinates_a, coordinates_b

out_maxpooling = maxpool(y_l, other_parameters)
print('выходная матрица:', '\n', out_maxpooling[0])
print('\n', 'матрица с координатами для backprop:', '\n', out_maxpooling[1])

Пример выхода работы скрипта


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

Бэкпроп через сверточную сеть



Вывод формулы backprop для обновления ядра свертки


$\begin{array}{rcl} \dfrac{\partial E}{\partial w^l_{ab}}&=&\sum_{i}\sum_{j} \dfrac{\partial E}{\partial y^l_{ij}}\dfrac{\partial y^l_{ij}}{\partial x^l_{ij}}\dfrac{\partial x^l_{ij}}{\partial w^l_{ab}}\\ &=&^{(1)}\sum_{i}\sum_{j} \dfrac{\partial E}{\partial y^l_{ij}}\dfrac{\partial y^l_{ij}}{\partial x^l_{ij}}\cdot \dfrac{\partial \left( \sum_{a'=-\infty}^{+\infty} \sum_{b'=-\infty}^{+\infty} w^l_{a'b'} \cdot y^{l-1}_{(is-a')(js-b')}+b^l \right)}{\partial w^l_{ab}}\\ &=&^{(2)}\sum_{i}\sum_{j} \dfrac{\partial E}{\partial y^l_{ij}}\dfrac{\partial y^l_{ij}}{\partial x^l_{ij}} \cdot y^{l-1}_{(is-a)(js-b)} \\ &&\forall a \in (-\infty,...,+\infty) \enspace \forall b \in (-\infty,...,+\infty) \end{array}$


(1) здесь просто подставляем формулу для $x^l_{ij}$, штрихи над $a'$ и $b'$ просто обозначают, что это другой итератор.
(2) здесь раскладываем сумму в числителе по $a$ и $b$:

$\small \sum_{i}\sum_{j} \frac{\partial E}{\partial y^l_{ij}}\frac{\partial y^l_{ij}}{\partial x^l_{ij}} \frac{\partial \left( w^l_{-\infty, -\infty} \cdot y^{l-1}_{(is+\infty)(js+\infty)}+\ldots+w^l_{ab} \cdot y^{l-1}_{(is-a)(js-b)}+\ldots+w^l_{\infty, \infty} \cdot y^{l-1}_{(is-\infty)(js-\infty)}+b^l \right)}{\partial w^l_{ab}}$


то есть все частные производные в числителе, кроме тех, для которых которых $a'=a, b'=b$, будут равны нулю. При этом $ \large \frac {\partial w^l_{ab} \cdot y^{l-1}_{(is-a)(js-b)}} {\partial w^l_{ab}}$ равен $ y^{l-1}_{(is-a)(js-b)} $

Все выше относится к конволюции. Формула backprop для кросс-корреляции выглядит аналогично, за исключением смены знака при $a$ и $b$:

$\frac{\partial E}{\partial w^l_{ab}}= \sum_{i}\sum_{j} \frac{\partial E}{\partial y^l_{ij}}\frac{\partial y^l_{ij}}{\partial x^l_{ij}} \cdot y^{l-1}_{(is+a)(j+b)}$


Здесь важно увидеть, что в итоговой формуле не участвует само ядро свертки. Происходит некое подобие операции свертки, но с участием уже $ \large \frac {\partial E} {\partial x^l_{ij}} $ и $ y^{l-1}$, причем в роли ядра выступает $ \large \frac {\partial E} {\partial x^l_{ij}} $, но все-таки это мало напоминает свертку, особенно при значении шага больше единицы: тогда $ \large \frac {\partial E} {\partial x^l_{ij}} $ “распадается” по $ y^{l-1}$, что совсем перестает напоминать привычную свертку. Этот “распад” происходит от того, что параметры $i$ и $j$ итерируются внутри цикла формулы. Посмотреть, как все это выглядит, можно с помощью демонстрационного кода:

code_demo_convolution_back_dEdw_l.py
ссылка на git
import numpy as np

w_l_shape = (2,2)

# если stride = 1
dEdx_l = np.array([
	[1,2,3,4],
	[5,6,7,8],
	[9,10,11,12],
	[13,14,15,16]])

# если stride = 2 и 'convolution':False (при конволюции и кросс-корреляци x_l получаются разного размера)
# dEdx_l = np.array([
# 	[1,2],
# 	[3,4]])

# если stride = 2 и 'convolution':True
# dEdx_l = np.array([
# 	[1,2,3],
# 	[4,5,6],
# 	[7,8,9]])

y_l_minus_1 = np.zeros((4,4))

other_parameters={
	'convolution':True,
	'stride':1,
	'center_w_l':(0,0)
}

def convolution_back_dEdw_l(y_l_minus_1, w_l_shape, dEdx_l, conv_params):
	indexes_a, indexes_b = create_indexes(size_axis=w_l_shape, center_w_l=conv_params['center_w_l'])
	stride = conv_params['stride']
	dEdw_l = np.zeros((w_l_shape[0], w_l_shape[1]))
	# в зависимости от типа операции меняется основная формула функции
	if conv_params['convolution']:
		g = 1 # операция конволюции
	else:
		g = -1 # операция корреляции
	# итерация по a и b ядра свертки
	for a in indexes_a:
		for b in indexes_b:
			# размерность матрицы для демонстрации конволюции равноа размерности y_l, так как эта матрица либо равна либо больше (в случае stride>1) матрицы x_l
			demo = np.zeros([y_l_minus_1.shape[0], y_l_minus_1.shape[1]])
			result = 0
			for i in range(dEdx_l.shape[0]):
				for j in range(dEdx_l.shape[1]):
					# проверка, чтобы значения индексов не выходили за границы
					if i*stride - g*a >= 0 and j*stride - g*b >= 0 					and i*stride - g*a < y_l_minus_1.shape[0] and j*stride - g*b < y_l_minus_1.shape[1]:
						result += y_l_minus_1[i*stride - g*a][j*stride - g*b] * dEdx_l[i][j]
						demo[i*stride - g*a][j*stride - g*b] = dEdx_l[i][j]
			dEdw_l[indexes_a.index(a)][indexes_b.index(b)] = result # перевод индексов в "нормальные" для извлечения элементов из матрицы w_l
			# вывод матрицы demo для отслеживания хода свертки
			print('a=' + str(a) + '; b=' + str(b) + '\n', demo)
	return dEdw_l

def create_axis_indexes(size_axis, center_w_l):
	coordinates = []
	for i in range(-center_w_l, size_axis-center_w_l):
		coordinates.append(i)
	return coordinates

def create_indexes(size_axis, center_w_l):
	# расчет координат на осях ядра свертки в зависимости от номера центрального элемента ядра
	coordinates_a = create_axis_indexes(size_axis=size_axis[0], center_w_l=center_w_l[0])
	coordinates_b = create_axis_indexes(size_axis=size_axis[1], center_w_l=center_w_l[1])
	return coordinates_a, coordinates_b

print(convolution_back_dEdw_l(y_l_minus_1, w_l_shape, dEdx_l, other_parameters))
Пример выхода работы скрипта



Вывод формулы backprop для обновления весов bias


Аналогично предыдущему пункту, только заменяем $w_{ab}^l$ на $b^l$. Будем использовать один bias для одной карты признаков:

$\begin{array}{rcl} \dfrac{\partial E}{\partial b^l}&=&\sum_{i}\sum_{j} \dfrac{\partial E}{\partial y^l_{ij}}\dfrac{\partial y^l_{ij}}{\partial x^l_{ij}}\dfrac{\partial x^l_{ij}}{\partial b^l}\\ &=& \small \sum_{i}\sum_{j} \dfrac{\partial E}{\partial y^l_{ij}}\dfrac{\partial y^l_{ij}}{\partial x^l_{ij}}\cdot \dfrac{\partial \left( \sum_{a=-\infty}^{+\infty} \sum_{b=-\infty}^{+\infty} w^l_{ab} \cdot y^{l-1}_{(is-a)(js-b)}+b^l \right)}{\partial b^l}\\ &=& \sum_{i}\sum_{j} \dfrac{\partial E}{\partial y^l_{ij}}\dfrac{\partial y^l_{ij}}{\partial x^l_{ij}} \end{array}$


то есть, если разложить сумму по всем $i$ и $j$, мы увидим, что все частные производные по $\partial b^l$ будут равны единице:

$\frac{\partial \left( \sum_{a=-\infty}^{+\infty} \sum_{b=-\infty}^{+\infty} w^l_{ab} \cdot y^{l-1}_{(is-a)(js-b)}+b^l \right)}{\partial b^l}=1$


Для одной карты признаков всего один bias, который “связан” со всеми элементами этой карты. Соответственно, при корректировке значения bias должны учитываться все значения из карты, полученные при обратном распространении ошибки. В качества альтернативного варианта можно брать столько bias для отдельной карты признаков, сколько элементов находится в этой карте, но в таком случае параметров bias будем слишком много — больше, чем параметров самих ядер свертки. Для второго случая также легко посчитать производную — тогда каждая $\large \frac{\partial E}{\partial b^l_{ij}} $ (обратите внимание, у bias уже появились подстрочные индексы $ij$) будет равна каждой $\large \frac{\partial E}{\partial x^l_{ij}}$.

Вывод формулы backprop через слой конволюции


Здесь все аналогично предыдущим выводам:

$\begin{array}{rcl} \dfrac{\partial E}{\partial y^{l-1}_{ij}}&=&\sum_{i'}\sum_{j'} \dfrac{\partial E}{\partial y^l_{i'j'}}\dfrac{\partial y^l_{i'j'}}{\partial x^l_{i'j'}}\dfrac{\partial x^l_{i'j'}}{\partial y^{l-1}_{ij}}\\ &=&\sum_{i'}\sum_{j'} \dfrac{\partial E}{\partial y^l_{i'j'}}\dfrac{\partial y^l_{i'j'}}{\partial x^l_{i'j'}} \cdot \dfrac{\partial \left( \sum_{a=-\infty}^{+\infty} \sum_{b=-\infty}^{+\infty} w^l_{ab} \cdot y^{l-1}_{(i's-a)(j's-b)}+b^l \right)}{\partial y^{l-1}_{ij}}\\ &=&\sum_{i'}\sum_{j'} \dfrac{\partial E}{\partial y^l_{i'j'}}\dfrac{\partial y^l_{i'j'}}{\partial x^l_{i'j'}} \cdot w^{l}_{(i's-i)(j's-j)}\\ &&\forall i,j \in размерность \enspace матрицы \enspace y^{l-1} \end{array}$


Раскладывая сумму в числителе по $a$ и $b$, получим, что все частные производные равны нулю, кроме того случая, когда $i's-a=i$ и $j's-b=j$, и, соответственно, $a=i's-i$, $b=j's-j$. Это справедливо только для конволюции, для кросс-корреляции должно быть $i's+a=i$ и $j's+b=j$ и, соответственно, $a=i-i's$ и $b=j-j's$. И тогда итоговая формула в случае кросс-корреляции будет выглядеть так:

$\frac{\partial E}{\partial y^{l-1}_{ij}}= \sum_{i'}\sum_{j'} \frac{\partial E}{\partial y^l_{i'j'}}\frac{\partial y^l_{i'j'}}{\partial x^l_{i'j'}} \cdot w^{l}_{(i-i's)(j-j's)}$


Получившиеся выражения — это та же самая операция свертки, причем в качестве ядра выступает знакомое нам ядро $w^l$. Но, правда, все похоже на привычную свертку только если stride равен единице, в случаях же другого шага, получается уже что-то совсем другое (аналогично случаю backprop для обновления ядра свертки): матрица $w^l$ начинает “ломаться” по всей матрице $ \large \frac {\partial E} {\partial x^l} $, захватывая разные ее части (опять-таки потому, что индексы $i'$ и $j'$ при $w^l$ итерируются внутри цикла формулы).

Здесь можно посмотреть и потестировать код:

code_demo_convolution_back_dEdy_l_minus_1.py
ссылка на git
import numpy as np

w_l = np.array([
	[1,2],
	[3,4]])

# если stride = 1
dEdx_l = np.zeros((3,3))

# если stride = 2 и 'convolution':False (при конволюции и кросс-корреляци x_l могут получиться разного размера)
# dEdx_l = np.zeros((2,2))

# если stride = 2 и 'convolution':True
# dEdx_l = np.zeros((2,2))

y_l_minus_1_shape = (3,3)

other_parameters={
	'convolution':True,
	'stride':1,
	'center_w_l':(0,0)
}

def convolution_back_dEdy_l_minus_1(dEdx_l, w_l, y_l_minus_1_shape, conv_params):
	indexes_a, indexes_b = create_indexes(size_axis=w_l.shape, center_w_l=conv_params['center_w_l'])
	stride = conv_params['stride']
	dEdy_l_minus_1 = np.zeros((y_l_minus_1_shape[0], y_l_minus_1_shape[1]))
	# в зависимости от типа операции меняется основная формула функции
	if conv_params['convolution']:
		g = 1 # операция конволюции
	else:
		g = -1 # операция корреляции
	for i in range(dEdy_l_minus_1.shape[0]):
		for j in range(dEdy_l_minus_1.shape[1]):
			result = 0
			# матрица для демонстрации конволюции
			demo = np.zeros([dEdx_l.shape[0], dEdx_l.shape[1]])
			for i_x_l in range(dEdx_l.shape[0]):
				for j_x_l in range(dEdx_l.shape[1]):
					# перевод индексов в "нормальные" для извлечения элементов из матрицы w_l
					a = g*i_x_l*stride - g*i
					b = g*j_x_l*stride - g*j
					# проверка на вхождение в диапазон индексов ядра свертки
					if a in indexes_a and b in indexes_b:
						a = indexes_a.index(a)
						b = indexes_b.index(b)
						result += dEdx_l[i_x_l][j_x_l] * w_l[a][b]
						demo[i_x_l][j_x_l] = w_l[a][b]
			dEdy_l_minus_1[i][j] = result
			# вывод матрицы demo для отслеживания хода свертки
			print('i=' + str(i) + '; j=' + str(j) + '\n', demo)
	return dEdy_l_minus_1

def create_axis_indexes(size_axis, center_w_l):
	coordinates = []
	for i in range(-center_w_l, size_axis-center_w_l):
		coordinates.append(i)
	return coordinates

def create_indexes(size_axis, center_w_l):
	# расчет координат на осях ядра свертки в зависимости от номера центрального элемента ядра
	coordinates_a = create_axis_indexes(size_axis=size_axis[0], center_w_l=center_w_l[0])
	coordinates_b = create_axis_indexes(size_axis=size_axis[1], center_w_l=center_w_l[1])
	return coordinates_a, coordinates_b

print(convolution_back_dEdy_l_minus_1(dEdx_l, w_l, y_l_minus_1_shape, other_parameters))
Пример выхода работы скрипта


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

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




К сожалению, не доступен сервер mySQL