Backpropagation

CSE 891: Deep Learning

Vishnu Boddeti

Wednesday September 16, 2020

Univariate Backpropagation

Example: univariate least squares regression

Forward Pass:

$$ \begin{eqnarray} z &=& wx+b \nonumber \\ y &=& \sigma(z) \nonumber \\ \mathcal{L} &=& \frac{1}{2}(y-t)^2 \nonumber \\ \mathcal{R} &=& \frac{1}{2}w^2 \nonumber \\ \mathcal{L}_{reg} &=& \mathcal{L} + \lambda\mathcal{R} \nonumber \end{eqnarray} $$

Backward Pass:

$$ \begin{eqnarray} \mathcal{L}'_{reg} &=& 1 \nonumber \\ \mathcal{R}' &=& \mathcal{L}_{reg}'\frac{d \mathcal{L}}{d \mathcal{R}} \nonumber \\ &=& \mathcal{L}_{reg}'\lambda \nonumber \\ \mathcal{L}' &=& \mathcal{L}_{reg}'\frac{d \mathcal{L}}{d \mathcal{L}} \nonumber \\ &=& \mathcal{L}_{reg}' \nonumber \\ y' &=& \mathcal{L}'\frac{d \mathcal{L}}{dy} \nonumber \\ &=& \mathcal{L}'(y-t) \nonumber \\ \end{eqnarray} $$

$$ \begin{eqnarray} z' &=& y'\frac{dy}{dz} \nonumber \\ &=& y'\sigma'(z) \nonumber \\ w' &=& z'\frac{\partial z}{\partial w}+\mathcal{R}'\frac{d \mathcal{R}}{dw} \nonumber \\ &=& z'x + \mathcal{R}'w \nonumber \\ b' &=& z'\frac{\partial z}{\partial b} \nonumber \\ &=& z' \end{eqnarray} $$

Multivariate Backpropagation

Example: Multilayer Perception (multiple outputs)

Forward Pass:

$$ \begin{eqnarray} z_i &=& \sum_{j}w^{(1)}_{ij} + b^{(1)}_i \nonumber \\ h_i &=& \sigma(z_i) \nonumber \\ y_k &=& \sum_{i}w^{(2)}_{ki}h_i+b^{(2)}_k \nonumber \\ \mathcal{L} &=& \frac{1}{2}\sum_k(y_k-t_k)^2 \nonumber \end{eqnarray} $$

Backward Pass:

$$ \begin{eqnarray} \mathcal{L}' &=& 1 \nonumber \\ y' &=& \mathcal{L}'(y_k-t_k) \nonumber \\ w^{(2)}_{ki} &=& y_k' h_i \nonumber \\ b^{(2)}_{k} &=& y_k' \nonumber \\ h_i' &=& \sum_k y_k' w^{(2)}_{ki} \nonumber \\ z_i' &=& h_i' \sigma'(z_i) \nonumber \\ w^{(1)}_{ij} &=& z_i' x_j \nonumber \\ b^{(1)}_i &=& z_i \nonumber \end{eqnarray} $$

Vector Form

Consider this computation graph:

Backprop rules:
where $\frac{\partial \mathbf{y}}{\partial \mathbf{z}}$ is the Jacobian matrix: $\mathbf{J} = \frac{\partial \mathbf{y}}{\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \dots & \frac{\partial y_1}{\partial x_n} \\\ \vdots & \ddots & \vdots \\\ \frac{\partial y_n}{\partial x_1} & \dots & \frac{\partial y_n}{\partial x_n} \end{bmatrix}$

MLP Backpropagation

Example: Multilayer Perception (vector form)

Forward Pass:

$$ \begin{eqnarray} \mathbf{z} &=& \mathbf{W}^{(1)}\mathbf{x}+\mathbf{b}^{(1)} \nonumber \\ \mathbf{h} &=& \sigma(\mathbf{z}) \nonumber \\ \mathbf{z} &=& \mathbf{W}^{(2)}\mathbf{h}+\mathbf{b}^{(2)} \nonumber \\ \mathcal{L} &=& \frac{1}{2}\||\mathbf{t}-\mathbf{y}\|| \nonumber \end{eqnarray} $$

Backward Pass:

$$ \begin{eqnarray} \mathcal{L}' &=& 1 \nonumber \\ \mathbf{y}' &=& \mathcal{L}'(\mathbf{y}-\mathbf{t}) \nonumber \\ \mathbf{W}^{(2)} &=& \mathbf{y}'\mathbf{h}^T \nonumber \\ \mathbf{b}^{(2)} &=& \mathbf{y}' \nonumber \\ \mathbf{h}' &=& \mathbf{W}^{(2)T}\mathbf{y}' \nonumber \\ \mathbf{z}' &=& \mathbf{h}'\odot\sigma'(\mathbf{z}) \nonumber \\ \mathbf{W}^{(1)} &=& \mathbf{z}'\mathbf{x}^T \nonumber \\ \mathbf{b}^{(1)} &=& \mathbf{z}' \nonumber \end{eqnarray} $$