Kernelization trick, for neural networks

I've been learning about neural networks and SVMs. The tutorials I've read have emphasized how important kernelization is, for SVMs. Without a kernel function, SVMs are just a linear classifier. With kernelization, SVMs can also incorporate non-linear features, which makes them a more powerful classifier.

It looks to me like one could also apply kernelization to neural networks, but none of the tutorials on neural networks I've seen have mentioned this. Do people commonly use the kernel trick with neural networks? I presume someone must have experimented with it to see if it makes a big difference. Does kernelization help neural networks as much as it helps SVMs? Why or why not?

(I can imagine several ways to incorporate the kernel trick into neural networks. One way would be to use a suitable kernel function to preprocess the input, a vector in $\mathbb{R}^n$, into a higher-dimensional input, a vector in $\mathbb{R}^{m}$ for $m\ge n$. For multiple-layer neural nets, another alternative would be to apply a kernel function at each level of the neural network.)

• The kernel trick works when your computational access to your data points consists of computing inner products. I'm not sure that's the case for neural networks. – Yuval Filmus Oct 19 '13 at 20:12

I think you might be confusing the terminology in a way that is making the issue confusing. SVMs work by defining a linear decision boundary, i.e., a hyperplane. We can define this hyperplane in terms of inner products between the points. Therefore, if we define this inner product to be in some high-dimensional, or even infinite dimensional space, what looks like a hyperplane in this new space is a not necessary linear in the original feature space. So everything is still linear, the only thing we've done is to implicitly (via the new inner-product) embed the points in some higher dimensional space. Maybe you already know all this.

There are 2 issues to consider with respect to neural networks. The first was brought up by @Yuval Filmus, because of the hidden layer neural networks depend on more than just the inner products between the points. If you remove the hidden layer, you just have something like logistic regression, of which there are kernelized versions. Maybe there is a way to get around this, but I don't see it.

Secondly, you mention preprocessing the input by projecting into a higher, but not infinite, dimensional space. Neural networks define a decision surface and this surface is not constrained to be linear. This means the gain from projecting the points into a higher dimensional space will be different, i.e., it may make it easier to find a good set of weights, but we haven't necessarily made our model any more powerful. This follows from the Universal approximation theorem that tells us given a large enough number of hidden units we can approximate any function (under some restrictions). This last statement is rather vacuous and I kind of hate to mention it. By not telling you anything about how to find the right weights it doesn't bring much to the table from an application perspective.

• Thank you. Yes. I know we can think of SVMs as mapping the original inputs to some higher (or even infinite) dimensional space, then doing a linear decision boundary in that higher dimensional space. So, can we do that with neural networks too? Can we map the inputs to a higher dimensional space, then treat that as the actual input to a neural network? I presume we can (and I presume we could also do this at each layer, if we wanted). And, if we can, my real question is: does this offer as big an improvement to neural networks (in practice) as it does for SVMs? Why or why not? – D.W. Oct 21 '13 at 16:04
• I know about the Universal approximation theorem, but that doesn't really answer the question (as you indicated). What I care about is how well neural works tend to work in practice. I am wondering whether preprocessing the inputs via a kernelization trick might make neural networks tend to work better in practice. Of course there are no guarantees and there will always be situations where anything you do could make things worse, but I'm wondering about typical behavior, in practice (in the same sense that we say kernelization tends to make SVMs significantly more effective, in practice). – D.W. Oct 21 '13 at 16:05
• @D.W. The reason kernelization makes SVMs more effective is because it allows them to define non-linear decision boundaries. Neural networks can already define non-linear decision boundaries, so the only benefit of projecting your data into a higher dimensional space would be to make the optimization problem easier. – alto Oct 21 '13 at 23:59

The kernel trick is possible for SVMs because of a special property of the learning process for SVMs. Neural networks don't seem to have that property (as far as I can tell).

Let $x_1,\dots,x_n \in \mathbb{R}^d$ be the points in the training set. Normally, you'd expect that a machine learning algorithm would look at the values of the $x_i$'s. However, the SVM learning process has a rather remarkable property. It doesn't need to know the values of the $x_i$'s. It is sufficient to be able to compute $x_i \cdot x_j$ for any desired pair of input points (i.e., to compute the dot-product for any pair of input vectors of your choice); that's all the SVM learning process needs.

This special property of the SVM learning process allows us to use the kernel trick. We can define a kernel function $K$ so that $K(x_i,x_j)$ is the dot-product of some non-linear transformation of the inputs. If we're transforming the input vectors via a nonlinear transformation $\phi : \mathbb{R}^d \to \mathbb{R}^m$ (for some $m > d$), then we define $K(x_i,x_j) = \phi(x_i) \cdot \phi(x_j)$. The next cool property is that, for some nonlinear transformations $\phi$, you can compute $K(x_i,x_j)$ more efficiently than computing $\phi(x_i),\phi(x_j)$ explicitly and then computing their dot-product; you can compute $K(x_i,x_j)$ in $O(d)$ time (say) rather than $O(m)$ time.

Unfortunately, neural networks don't seem to have any way to take advantage of this cool trick, because the learning process for neural networks seems to depend upon more than just the values $x_i \cdot x_j$ (or $K(x_i,x_j)$); it requires the full values of all the $x_i$'s. So, while we can indeed pre-transform the inputs to the nonlinear network via some nonlinear function if we want, there doesn't seem to be any way to use the kernel trick to make this more efficient, like we can do for SVMs.

I would like to share some observations I have made. Input dimension: 144. I have trained a neural network, and during training, the output of the hidden layers were given as input for logistic regression, and the mean value of loss function after fitting the model was plotted.

We can see that with increase in layer size, the features, or the output of the hidden layers are becoming linearly separable. While this is the purpose of learning the kernelised feature vector, neural network seems to be doing this internally.