Chain Rule

Univariate Chain Rule

• Univariate Chain Rule: If $f(x)$ and $x(t)$ are two univariate functions, then
$$ \begin{equation} \frac{\partial}{\partial t}f(x(t)) = \frac{\partial f}{\partial x}\frac{\partial x}{\partial t} \end{equation} $$

Univariate Chain Rule Example

Univariate Chain Rule Example

Univariate Chain Rule

• We can represent the computations using a computational graph.
• Nodes represent all the inputs and computed quantities.
• Edges represent which nodes are computed directly as a function of which other nodes.

Multivariate Chain Rule

• Problem: what if the computation graph has a fan-out $> 1$
• This requires the multivariate Chain Rule.

$L_2$ Regularized Regression

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

Multiclass Logistic Regression

$$ \begin{eqnarray} z_l &=& \sum_j w_{lj}x_j + b_l \nonumber \\ y_k &=& \frac{e^{z_k}}{\sum_l e^{z_l}} \nonumber \\ \mathcal{L} &=& -\sum_{k}t_k\log y_k \nonumber \end{eqnarray} $$

Multivariate Chain Rule

• Suppose we have a function $f(x,y)$ and functions $x(t)$ and $y(t)$.
• All the variables here are scalar-valued.

Multivariate Chain Rule Example

Multivariate Chain Rule Example

Backpropagation

Multivariate Chain Rule

• In the context of backpropagation:



• In our notation:
$$ \begin{equation} t' = x'\frac{dx}{dt} + y'\frac{dy}{dt} \end{equation} $$

Patterns in Gradient Flow

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

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

Vector Form

• Computation graphs showing individual units are cumbersome.
• As you might imagine, we typically draw graphs over vectorized variables.



• We pass messages back analogous to the ones for scalar-valued nodes.

Vector Form

• Consider this computation graph:



• Backprop rules:
$$ \begin{equation} z_{j}' = \sum_{k}y_k'\frac{\partial y_k}{\partial z_j} \mbox{ or } \mathbf{z}' = \frac{\partial \mathbf{y}^T}{\partial \mathbf{z}}\mathbf{y}' \end{equation} $$
• 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}\|_2^2 \nonumber \end{eqnarray} $$

Backpropagation Implementation: Modular API

    class ComputationalGraph(object):
      # ...
      def forward(inputs):
        # 1. [pass inputs to input gates]
        # 2. forward the computational graph
        for gate in self.graph_nodes_topologically_sorted():
          gate.forward()
        return loss # final gate in the graph outputs the loss
      def backward(loss):
        for gate in reversed(self.graph_nodes_topologically_sorted()):
          gate.backward() # chain rule applied
        return input_gradients
  

Backpropagation: PyTorch Example

    class Multiply(torch.autograd.Function):
      @staticmethod
      def forward(ctx, x, y):
        ctx.save_for_backward(x,y)
        z = x * y
        return z
      @staticmethod
      def backward(ctx, grad_z):
        x, y = ctx.saved_tensors
        grad_x = y * grad_z # dz/dx * dL/dz
        grad_y = x * grad_z # dz/dy * dL/dz
        return grad_x, grad_y
  

MLP Gradients (Optional)

Recap: Multilayer Neural Network

Loss Function

• Maximum Likelihood Estimate:
$$ \mathbf{\theta}^* = \underset{\theta}{\operatorname{arg max}}\prod_i p(y_i=c|\mathbf{x}_i) $$
• Classification:
$$ l = l(\mathbf{x},\mathbf{\theta};y) = \sum_i -\log f(\mathbf{x}_i)_y $$

Output Layer Gradient

Output Layer Gradient Continued...

Hidden Layer Gradient

Activation Function Gradient

Linear Activation

Sigmoid Activation

Tanh Activation

Rectified Linear Unit Activation

Gradient of Parameters

Gradient of Parameters

Backpropagation Algorithm

• Assuming Forward Propagation is already done.
• compute output gradient (before activation)
$$ \nabla_{\mathbf{a}^{(L+1)}(\mathbf{x})} -\log f(\mathbf{x})_y \Longleftarrow -(\mathbf{e}(y)-\mathbf{f}(\mathbf{x})) $$
• for $k$ from $L+1$ to 1
• compute gradients of hidden layer parameter
$$ \begin{eqnarray} \nabla_{\mathbf{W}^{(k)}} -\log f(\mathbf{x})_y &\Longleftarrow& (\nabla_{\mathbf{a}^{(k)}} -\log f(\mathbf{x})_y) \mathbf{h}^{(k-1)}(\mathbf{x})^T \nonumber \\ \nabla_{\mathbf{b}^{(k)}} -\log f(\mathbf{x})_y &\Longleftarrow& \nabla_{\mathbf{a}^{(k)}} -\log f(\mathbf{x})_y \nonumber \end{eqnarray} $$
• compute gradient of hidden layer below
$$ \begin{equation} \nabla_{\mathbf{h}^{(k-1)}} -\log f(\mathbf{x})_y \Longleftarrow \mathbf{W}^{(k)^T}\left(\nabla_{\mathbf{a}^{(k)}} -\log f(\mathbf{x})_y\right) \end{equation} $$
• compute gradient of hidden layer below (before activation)
$$ \begin{equation} \nabla_{\mathbf{a}^{(k-1)}} -\log f(\mathbf{x})_y \Longleftarrow \left(\nabla_{\mathbf{h}^{(k-1)}} -\log f(\mathbf{x})_y\right) \odot [\dots,g'(a^{(k-1)}(\mathbf{x})_j),\dots] \nonumber \end{equation} $$