MIT 6.790 — Lecture 16

Sparse Representations: NNs vs. Kernels

Remark. These notes are not particularly well-written, as they gloss over most of the computational details and only summarize the main conceptual points of this lecture, occasionally using mathematical informalities.

§ NNs vs. Kernels

Recall from Lecture 6 and Lecture 12 that neural networks and kernel methods are both linear models over the hidden layers of a neural network encode the features that define the kernel.

The purpose of this lecture is to roughly explain how neural networks may be advantageous relative to kernel methods when the model being learned has a sparse representation.

A model is said to have a sparse representation if it is a map $\mathbb{R}^d \to \mathbb{R}$ for which only $r \ll d$ of the $d$ input dimensions are relevant. For example, $f \colon \mathbb{R}^{1000} \to \mathbb{R}$ via $f(x) := x_1 + x_1x_2 + x_1x_2x_3$ has a sparse representation, with $r = 3$ and $d = 1000$ .

§ Kernel Performance

In the $f \colon \mathbb{R}^{1000} \to \mathbb{R}$ toy example, kernel methods will produce a hypothesis $h(x) := w^{\top} \phi(x)$ , where $\phi(x)$ is a vector of dimension at least $\binom{1000}{3} = O(1000^3)$ . Therefore, learning this hypothesis requires $O(1000^3)$ samples. (Justification ommitted.)

That's a lot of samples! Can NNs do better?

§ NN Performance

The advantage of NNs is the following:

Kernel methods use SGD to directly attack the question, “Which of the $O(1000^3)$ features are relevant?”
A neural network ultimately uses SGD to answer the same question, but it does so incrementally.
- Its first layer uses SGD to answer the question, “Which $r = 3$ of the $d = 1000$ input dimensions are relevant?”
- Then the deeper hidden layers need only use SGD to answer the question, “Which of the $O(r^3)$ features are relevant?”
- The advantage for NNs is especially evident given sparse representations (i.e., $r \ll d$ ).

Reminder. The first hidden layer does not encode the same set of $O(1000^3)$ features that the kernel encodes! A single neuron in the first hidden layer can only represent $\mathrm{ReLU}(w^{\top}x)$ , after all—not even close to anything like $x_1x_2x_3$ . It is only the final output of all of the hidden layers together that is capable of learning all $O(1000^3)$ features.

Remark. Technically, as Lecture 12 describes, a linear combination of the neurons in just a single hidden layer of an NN is capable of approximating any continuous function arbitrarily well, so such a combination could represent all $O(1000^3)$ features, so long as enough neurons are used.

But in practice, using just a single layer is infeasible; recalling Lecture 13, the number of parameters in an NN can be reduced by increasing the number of hidden layers.

Let's explain, now, how SGD allows NNs to answer the first question—“Which $r = 3$ of the $d = 1000$ input dimensions are relevant?”—using the weights $W \in \mathbb{R}^{m \times 1000}$ between its input layer and its width- $m$ first hidden layer.

The point is that each iteration of SGD might shift any individual weight of $W$ by $O((1000m)^{-1})$ , rather than $O(1000^{-3})$ , because there are only $1000m$ parameters in $W$ . So here's what happens:

The term $x_1$ inside of $f(x)$ incentivizes increasing the weights of $w_{j, 1}$ within $O(1000m)$ SGD iterations.
Now that $w_{j, 1}$ is large, the term $x_1x_2$ incentivizes increasing the weights of $w_{j, 2}$ within another $O(1000m)$ SGD iterations.
With $w_{j, 1}$ and $w_{j, 2}$ large, the term $x_1x_2x_3$ incentivizes increasing the weights of $w_{j, 3}$ after $O(1000m)$ more SGD iterations.

So it only takes $O(dmr)$ SGD iterations to identify which $r$ input dimensions are relevant, after which only $O(r^3)$ SGD steps are needed to determine which of the $O(r^3)$ features over those dimensions are relevant.

Remark. In the first $O(1000m)$ SGD iterations, there is little incentive to increase the weights of $w_{j, 2}$ or $w_{j, 3}$ . This is because $w_{j, 1}$ is not large enough—more precisely, the $\frac{\partial \mathcal{R}}{\partial w_{j, 2}}$ update is proportional to $w_{j, 1}$ .

Thus, NNs perform best for staircase functions, whose terms each extend the previous by one coordinate; it is easier to learn $f(x) = x_1 + x_1x_2$ than $f(x) = x_1 + x_2x_3$ .