Backpropagation

Backpropagation

• 배경설명
• 이미 1970년대 소개되었으나, 1986년 논문(by David Rumelhart, Geoffrey Hinton, and Ronald Williams.)이 나오기 전까지 중요성이 인지되지 않았음. 
• backpropagation works far faster than earlier approaches.
• 목적: 특정 입력값이 최종 결과에 얼마만큼의 영향을 미치는 지 계산하기 위해.
• Reverse-mode differentiation에 대한 쉽고 친절한 설명
• 약간은 수식이 많고 난해한 설명이지만 참고 가능.
• Ranzato, DL tutorial@CVPR2014 (2014 June)
• Softmax loss function에 대한 derivative

$$L = -\sum_j y_j \log p_j, \\
p_j = \frac{e^{o_j}}{\sum_k e^{o_k}},$$ where $o$ is a vector.
$$\frac{\partial p_j}{\partial o_i} = p_i(1 - p_i),\quad i = j$$
and
$$ \frac{\partial p_j}{\partial o_i} = -p_i p_j,\quad i \neq j.$$
$$ \begin{eqnarray*}
\frac{\partial L}{\partial o_i} &=& -\sum_ky_k\frac{\partial \log p_k}{\partial o_i}=-\sum_ky_k\frac{1}{p_k}\frac{\partial p_k}{\partial o_i}\\
&=&-y_i(1-p_i)-\sum_{k\neq i}y_k\frac{1}{p_k}({{-p_kp_i}})\\
&=&-y_i(1-p_i)+\sum_{k\neq i}y_k({{p_i}})\\
&=&-y_i+y_ip_i+\sum_{k\neq i}y_k({p_i})\\
&=&p_i\left(\sum_ky_k\right)-y_i\\
&=&p_i-y_i
\end{eqnarray*} $$

또는 다음과 같이 표현되기도 함.
$$ \frac{\partial L_i }{ \partial f_k } = p_k - \mathbb{1}(y_i = k) $$
(즉, 정확한 라벨(k)에 대한 score 값에 대해서, 해당 도출된 확률($p_k$)의 역을 이용해서 gradient가 표시되며, 이는 loss를 줄일 수 있는 방향을 나타낸다는 직관적인 해석 가능.)

• sigmoid function에 대한 derivative

$$ \frac{dy}{dx}= y(1-y) $$

• CS231n에서 나온 binary logistic regression classifier의 log likelihood 관련 loss function에 대한 derivative 계산

$$ L_i = \sum_j y_{ij} \log(\sigma(f_j)) + (1 - y_{ij}) \log(1 - \sigma(f_j)), $$ where $\sigma(\cdot)$ is the sigmoid function.

$$ \begin{eqnarray*}
L_i &=& \sum_j y_{ij} \log(\frac{1}{1+e^{-f_j}}) + (1 - y_{ij}) \log(1 - \frac{1}{1+e^{-f_j}})\\
&=& \sum_j (-1)y_{ij} \log(1+e^{-f_j}) + (1 - y_{ij})(\log(e^{-f_j}) - \log(1+e^{-f_j}))\\
&=& \sum_j (-1)y_{ij} \log(1+e^{-f_j}) + (1 - y_{ij})(-f_j) + (y_{ij} -1)\log(1+e^{-f_j}))\\
&=& \sum_j f_j(y_{ij}-1) + (-1)\log(1+e^{-f_j}))\\
&=& \sum_j f_jy_{ij} + (-1)(f_j+\log(1+e^{-f_j}))\\
&=& \sum_j f_jy_{ij} + (-1)\log(e^{f_j}+1)
\end{eqnarray*} $$
Therefore,
$$ \begin{eqnarray*}
\frac{\partial L_i}{\partial f_j} &=& \sum_j y_{ij} + (-1)\frac{1}{e^{f_j}+1}(e^{f_j})\\
&=&\sum_j y_{ij} + (-1)\frac{1}{1 + \frac{1}{e^{f_j}}}\\
&=& \sum_j y_{ij} + (-1)\frac{1}{1 + e^{-f_j}} \\
&=& \sum_j y_{ij} - \sigma(f_j)
\end{eqnarray*} $$