Deriving gradients using the backpropagation idea

(Difference between revisions)
 Revision as of 08:02, 29 May 2011 (view source)Cyfoo (Talk | contribs) (Created page with "== Introduction == In the section on the backpropagation algorithm, you were briefly introduced to backpropagation as a means of deriving gradien...")← Older edit Revision as of 08:05, 29 May 2011 (view source)Cyfoo (Talk | contribs) Newer edit → Line 26: Line 26:
• $a^{(l)}_i$ is the activation of the $i$th unit in the $l$th layer
• $a^{(l)}_i$ is the activation of the $i$th unit in the $l$th layer
• $A \bullet B$ is the Hadamard or element-wise product, which for $r \times c$ matrices $A$ and $B$ yields the $r \times c$ matrix $C = A \bullet B$ such that $C_{r, c} = A_{r, c} \cdot B_{r, c}$
• $A \bullet B$ is the Hadamard or element-wise product, which for $r \times c$ matrices $A$ and $B$ yields the $r \times c$ matrix $C = A \bullet B$ such that $C_{r, c} = A_{r, c} \cdot B_{r, c}$ -
• $f^{(l})$ is the activation function for units in the $l$th layer +
• $f^{(l)}$ is the activation function for units in the $l$th layer Line 51: Line 51: - [[File:Backpropagation Method Example 1.png]] + [[File:Backpropagation Method Example 1.png | 400px]] === Example 2: Smoothed topographic L1 sparsity penalty in sparse coding  === === Example 2: Smoothed topographic L1 sparsity penalty in sparse coding  === Line 60: Line 60: We would like to find $\nabla_s \sum{ \sqrt{Vss^T + \epsilon} }$. As above, let's see this term as an instantiation of a neural network: We would like to find $\nabla_s \sum{ \sqrt{Vss^T + \epsilon} }$. As above, let's see this term as an instantiation of a neural network: - [[File:Backpropagation Method Example 2.png]] + [[File:Backpropagation Method Example 2.png | 600px]]

Introduction

In the section on the backpropagation algorithm, you were briefly introduced to backpropagation as a means of deriving gradients for learning in the sparse autoencoder. It turns out that together with matrix calculus, this provides a powerful method and intuition for deriving gradients for more complex matrix functions (functions from matrices to the reals, or symbolically, from $\mathbb{R}^{r \times c} \rightarrow \mathbb{R}$.

First, recall the backpropagation idea, which we present in a modified form appropriate for our purposes below:

1. For $l = n_l, n_l-1, n_l-2, \ldots, 2$
For each node i in layer l, set
$\delta^{(l)}_i = \left( \sum_{j=1}^{s_{l+1}} W^{(l)}_{ji} \delta^{(l+1)}_j \right) \bullet \frac{\partial}{\partial z^{(l)}_i} f^{(l)} (z^{(l)}_i)$
2. Compute the desired partial derivatives,
\begin{align} \nabla_{W^{(l)}} J(W,b;x,y) &= \delta^{(l+1)} (a^{(l)})^T, \\ \end{align}

Quick notation recap:

• l is the number of layers in the neural network
• nl is the number of neurons in the lth layer
• $W^{(l)}_{ji}$ is the weight from the ith unit in the lth layer to the jth unit in the (l + 1)th layer
• $z^{(l)}_i$ is the input to the ith unit in the lth layer
• $a^{(l)}_i$ is the activation of the ith unit in the lth layer
• $A \bullet B$ is the Hadamard or element-wise product, which for $r \times c$ matrices A and B yields the $r \times c$ matrix $C = A \bullet B$ such that $C_{r, c} = A_{r, c} \cdot B_{r, c}$
• f(l) is the activation function for units in the lth layer

Notice that we don't consider an objective function in this case, and we allow each layer to have a different activation function f(l). This will be useful in allowing us to compute the gradients of functions of matrices.

The method

To compute the gradient with respect to some matrix X of a complicated function of matrices, it may be helpful to consider the function as a complicated multi-layer neural network, if possible. We will use two functions from the section on sparse coding to illustrate this.

Example 1: Objective for weight matrix in sparse coding

Recall the objective function for the weight matrix A, given the feature matrix s:

$J(A; s) = \lVert As - x \rVert_2^2 + \gamma \lVert A \rVert_2^2$

We would like to find the gradient of J with respect to A, or in symbols, $\nabla_A J(A)$. Since the objective function is a sum of two terms in A, the gradient is the sum of gradients of each of the individual terms. The gradient of the second term is trivial, so we will consider the gradient of the first term instead.

The first term, $\lVert As - x \rVert_2^2$, can be seen as an instantiation of neural network taking s as an input, and proceeding in four steps, as described and illustrated in the paragraph and diagram below:

1. Apply A as the weights from the first layer to the second layer.
2. Subtract x from the activation of the second layer, which uses the identity activation function.
3. Pass this unchanged to the third layer, via identity weights. Use the square function as the activation function for the third layer.
4. Sum all the activations of the third layer.

Example 2: Smoothed topographic L1 sparsity penalty in sparse coding

Recall the smoothed topographic L1 sparsity penalty on s in sparse coding:

$\sum{ \sqrt{Vss^T + \epsilon} }$

We would like to find $\nabla_s \sum{ \sqrt{Vss^T + \epsilon} }$. As above, let's see this term as an instantiation of a neural network: