Kernelization trick, for neural networks

Question

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.)

Answer 1

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.

Answer 2

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.

Answer 3

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.