Error back propagation algorithm using Word2Vec as an example

Since I encountered significant difficulties in finding an explanation of the back propagation mechanism of the error that I would like, I decided to write my own post about the back propagation of the error using the Word2Vec algorithm. My goal is to explain the essence of the algorithm using a simple but non-trivial neural network. In addition, word2vec has become so popular in the NLP community that it will be useful to focus on it.

This post is connected with another, more practical post that I recommend reading, it discusses the direct implementation of word2vec in python. In this post, we will focus mainly on the theoretical part.

Let's start with the things that are necessary for a true understanding of back propagation. In addition to concepts from machine learning, such as the loss function and gradient descent, two more components from mathematics come in handy:

• linear algebra (in particular matrix multiplication)
• rule of the chain of differentiation of functions from many variables

If you are familiar with these concepts, then further considerations will be simple. If you have not mastered them yet, you can still understand the basics of backpropagation.

First, I want to define the concept of back propagation, if the meaning is not clear enough, it will be disclosed in more detail in the following paragraphs.

1. What is a backpropagation algorithm?

Within the framework of a neural network, the only parameters involved in training the network, that is, to minimize the loss function, are weights (here I mean weights in the broad sense, including displacements). Weights change at each iteration until we get to the minimum of the loss function.

, — , , .
, , .
, , , , w1 w2.

1. .

, w1 w2 .

, . , $$$\partial\mathcal{L}/\partial w_1$ $$$\partial\mathcal{L}/\partial w_2$, , . $$$\eta$, .

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\times N$, $$$W’$ $$$N\times V$, V — , N — ( , word2vec)

y t, , , , , .

, .

3.1 (Loss function)

1, , x:

$$

$$\begin{eqnarray*} \textbf{h} = & W^T\textbf{x} \hspace{7.0cm} \\ \textbf{u}= & W'^T\textbf{h}=W'^TW^T\textbf{x} \hspace{4.6cm} \\ \textbf{y}= & \ \ \mathbb{S}\textrm{oftmax}(\textbf{u})= \mathbb{S}\textrm{oftmax}(W'^TW^T\textbf{x}) \hspace{2cm} \end{eqnarray*}$$

, h — , u — , y — .

, , , (wt, wc). , onehot encoding .

, onehot wt ( ).

softmax , :

$$

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

, j* — .
. (1):

$$

$$\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)$$

.

3.2 CBOW

, , W W` . , .

. (1) W W`. $$$\partial \mathcal{L}/\partial{W}$ $$$\partial \mathcal{L}/\partial{W’}$

, . (1) W W`, u=[u1, ...., uV],

$$

$$\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*}$$

:

$$

$$\begin{equation} \frac{\partial\mathcal{L}}{\partial W'_{ij}} = \sum_{k=1}^V\frac{\partial\mathcal{L}}{\partial u_k}\frac{\partial u_k}{\partial W'_{ij}} \label{eq:dLdWp} \end{equation} \>(2)$$

$$

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

, (2) (3) .

(2), Wij, W, i j , uj ( yj).

3. (a) $$$y_j$ $$$h_i$ $$$W'_{ij}$ $$$W'$. (b) , $$$x_k$ N $$$W_{k1}\dots W_{kN}$ W.

, $$$\partial u_k/\partial W'_{ij}$, , k=j, 0.

(4):

$$

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

$$$\partial \mathcal{L}/\partial u_j$, (5):

$$

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

, $$$\delta_{jj^*}$ — , , 1, , 0 .

(5) e N ( ), , , .

(4) (6):

$$

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

(5) (6) (4) (7):

$$

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

$$$\partial\mathcal{L}/\partial W_{ij}$, Xk, yj j W , 3(b). . $$$\partial u_k/\partial W_{ij}$, uk u :

$$

$$\begin{equation*} u_k = \sum_{m=1}^N\sum_{l=1}^VW'_{mk}W_{lm}x_l\ . \end{equation*}$$

$$$\partial u_k/\partial W_{ij}$, l=i m=j, (8):

$$

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

(5) (8) , (9):

$$

$$\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)$$

3.3

, (7) (9), , . . $$$\eta>0$, :

$$

$$\begin{eqnarray} W_{\textrm{new}} & = W_{\textrm{old}} - \eta \frac{\partial \mathcal{L}}{\partial W} \nonumber \\ W'_{\textrm{new}} & = W'_{\textrm{old}} - \eta \frac{\partial \mathcal{L}}{\partial W'} \nonumber \\ \end{eqnarray}$$

3.4

. , . , . , . , , , .

4. CBOW

CBOW . . (4) . OneHot Encoded . word2vec. .

4. CBOW

CBOW CBOW .

$$

$$\begin{eqnarray} \textbf{h} = & \frac{1}{C} W^T \sum_{c=1}^C\textbf{x}^{(c)} = W^T\overline{\textbf{x}}\hspace{5.8cm} \nonumber \\ \textbf{u}= & W'^T\textbf{h}= \frac{1}{C}\sum_{c=1}^CW'^T W^T\textbf{x}^{(c)}=W'^T W^T\overline{\textbf{x}} \hspace{2.8cm} \nonumber \\ \textbf{y}= & \ \ \mathbb{S}\textrm{oftmax}(\textbf{u})= \mathbb{S}\textrm{oftmax}\left( W'^T W^T\overline{\textbf{x}}\right) \hspace{3.6cm} \nonumber \end{eqnarray}$$

, '' $$$\overline{\textbf{x}}=\sum_{c=1}^C\textbf{x}^{(c)}/C$

, . :

$$

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

, :

$$

$$\begin{equation} \frac{\partial\mathcal{L}}{\partial W'_{ij}} = \sum_{k=1}^V\frac{\partial\mathcal{L}}{\partial u_k}\frac{\partial u_k}{\partial W'_{ij}} \end{equation} \>(13)$$

$$

$$\begin{equation} \frac{\partial\mathcal{L}}{\partial W_{ij}} = \sum_{k=1}^V\frac{\partial\mathcal{L}}{\partial u_k}\frac{\partial u_k}{\partial W_{ij}}\ . \end{equation} \>(14)$$

CBOW , , . $$$W’_{ij}$

$$∂L∂W′ij=∑Vk=1∂L∂uk∂uk∂W′ij=∂L∂uj∂uj∂W′ij=(−δjj∗+yj)(∑Vk=1Wki¯xk)(15)$\begin{equation} \frac{\partial\mathcal{L}}{\partial W'_{ij}} = \sum_{k=1}^V\frac{\partial\mathcal{L}}{\partial u_k}\frac{\partial u_k}{\partial W'_{ij}} = \frac{\partial\mathcal{L}}{\partial u_j}\frac{\partial u_j}{\partial W'_{ij}} = (-\delta_{jj^*} + y_j) \left(\sum_{k=1}^V W_{ki}\overline{x}_k\right) \end{equation} \> (15)$

$$$W_{ij}$:

$$

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

:

$$

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

$$

$$\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}\overline{x}_i . } \label{eq:backprop2_multi} \end{equation} \> (18)$$

5. Skip-gram

CBOW, , . :

5. Skip-gram .

skip-gram :

$$

$$\begin{eqnarray*} \textbf{h} = & W^T\textbf{x} \hspace{9.4cm} \\ \textbf{u}_c= & W'^T\textbf{h}=W'^TW^T\textbf{x} \hspace{4cm} c=1, \dots, C \hspace{0.7cm}\\ \textbf{y}_c = & \ \ \mathbb{S}\textrm{oftmax}(\textbf{u})= \mathbb{S}\textrm{oftmax}(W'^TW^T\textbf{x}) \hspace{2cm} c=1, \dots, C \end{eqnarray*}$$

( $$$\textbf{u}_c$) , $$$\mathbf{y}_1=\mathbf{y}_2\dots= \mathbf{y}_C$. :

$$

$$\begin{eqnarray*} \mathcal{L} = -\log \mathbb{P}(w_{c,1}, w_{c,2}, \dots, w_{c,C}|w_o)=-\log \prod_{c=1}^C \mathbb{P}(w_{c,i}|w_o) \\ = -\log \prod_{c=1}^C \frac{\exp(u_{c,j^*})}{\sum_{j=1}^V \exp(u_{c,j})} =-\sum_{c=1}^C u_{c,j^*} + \sum_{c=1}^C \log \sum_{j=1}^V \exp(u_{c,j}) \end{eqnarray*}$$

skip-gram $$$C\times V$
:

$$

$$\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*}$$

:

$$

$$\begin{equation*} \frac{\partial\mathcal{L}}{\partial W'_{ij}} = \sum_{k=1}^V\sum_{c=1}^C\frac{\partial\mathcal{L}}{\partial u_{c,k}}\frac{\partial u_{c,k}}{\partial W'_{ij}} \end{equation*}$$

$$

$$\begin{equation*} \frac{\partial\mathcal{L}}{\partial W_{ij}} = \sum_{k=1}^V\sum_{c=1}^C\frac{\partial\mathcal{L}}{\partial u_{c,k}}\frac{\partial u_{c,k}}{\partial W_{ij}}\ . \end{equation*}$$

$$$\partial \mathcal{L}/\partial u_{c,j}$, :

$$

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

CBOW :

$$

$$\begin{equation*} \frac{\partial\mathcal{L}}{\partial W'_{ij}} = \sum_{k=1}^V\sum_{c=1}^C\frac{\partial\mathcal{L}}{\partial u_{c,k}}\frac{\partial u_{c,k}}{\partial W'_{ij}} = \sum_{c=1}^C\frac{\partial\mathcal{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_k\right) \end{equation*}$$

$$$W_{ij}$ , :

$$

$$\begin{equation*} \frac{\partial\mathcal{L}}{\partial W_{ij}} = \sum_{k=1}^V\sum_{c=1}^C\frac{\partial\mathcal{L}}{\partial u_{c,k}}\frac{\partial}{\partial W_{ij}}\left(\sum_{m=1}^N\sum_{l=1}^V W'_{mk} W_{lm}x_l\right)=\sum_{k=1}^V\sum_{c=1}^C (-\delta_{kk_c^*} + y_{c,k})W'_{jk}x_i . \end{equation*}$$

, skip-gram :

$$

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

$$

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

6.

word2vec. . [2] ( softmax, negative sampling), . [1].

, word2vec.

The next step is to implement these equations in your favorite programming language. If you like Python, I already implemented these equations in my next post .

Hope to see you there!

Sitelinks

[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).