Theoretical Speculations as to Why Neural Networks have Replaced Kernel-Based Methods

Question

I have been reading about the history of statistical and machine learning algorithms, and am particularly interested in the reasons as to why neural networks have "replaced" kernel-based methods in many applications.

As I understand, kernel-based methods (e.g., SVM, Gaussian Process) were the dominant choice of machine learning algorithms for many years – even when neural networks existed. I tried to do some readings and find out the reasons :

• Why were kernel-based methods originally developed?
• Why do kernel-based methods "work"?
• Why were kernel-based methods able to perform successfully in real world applications?

Based on these readings, I have identified the following theoretical properties of Kernels which might in part answer the above questions:

• Cover's Theorem: Cover's Theorem states that patterns that are difficult to separate in lower dimensions might be better separable when projected into higher dimensions. Thus, kernel-based methods try to learn these projection/mapping functions.

• Mercer's Theorem: Supposedly, Mercer's Theorem guarantees the existence of this mapping function.

• Kernel Trick and the Representer Theorem: I do not fully understand what these are, but it seems that both of these serve to facilitate the computations required in kernel-based methods.

• Kernel-Based Methods as Non-Parametric Models: Non-Parametric Models can be considered to potentially have an infinite number of model parameters. Thus, with regards to the bias-variance tradeoff, when compared to parametric regression models with many terms; kernel-based methods may have the ability to better capture higher levels of complexity within the data without suffering as much from the pitfalls of high variance. Kernel-based methods as such do not have model parameters that need to be explicitly estimated and the machine learning process is about deciding optimal hyperparameter values.

On the other hand, the main theoretical result pertaining to neural networks seems to be the Universal Approximation Theorem. Different versions of the Universal Approximation Theorem exist (e.g., more recent statements of this theorem make claims multilayered and finite depth neural networks) – the original statement of this theorem states that a 2-layered neural network with infinite depth can approximate any function to an arbitrary level of precision:

This is said to be closely related to the Kolmogorov-Arnold Representation Theorem, which states that "every multivariate continuous function can be represented as a superposition of the 2-argument addition and continuous functions of one variable":

But at the end of the day, what lead to neural networks becoming the dominant class of machine learning algorithms and outperforming kernel-based methods in many real world applications? One could argue that this was solely based on empirical reasons and circumstantial evidence, e.g., neural networks just tend to outperform kernel-based methods - but are there any mathematical theorems which can attempt to better explain the downfall of kernel-based methods and the fast-paced rise of neural networks?

Answer 1

• First of all, not only neural networks are universal approximators. There is nothing special about them, they just proved to work quite well for a class of problems.
• Kernel based methods generally don't scale well. Neural networks gained popularity in the time when we (a) improved our computers, so we were able to run bigger neural networks and do this in reasonable time, (b) with Internet, we gained access to large amounts of data (images, text) to train them. Kernel methods don't scale for large datasets, while in many cases it is the data not the algorithms that lead to improvements (Halevy, Norvig, and Pereira, 2009). Neural networks do scale.
• Neural networks gained popularity because they flourished for tasks related to image classification and natural language processing, traditional machine learning, including kernel based methods, don't generally do well for such tasks. Those are also the tasks where neural networks do well today, while for example for tabular data traditional machine learning seems to be commonly used.

Answer 2

Your question is more theoretically founded, but goes in the same direction as this one. You might want to check the answers there (disclaimer: one of them is mine).

In order to answer your question from the last paragraph, I believe it is useful to identify conceptual basic blocks in machine learning:

• feature selection
• feature transformation
• parameter optimisation

Regarding feature selection: Objects from the real world can be described by a very high number of features (or variables), potentially in the millions or even more (think of images with megapixel resolution). The number of real-world features is, in all practically relevant applications, much higher than the amount of data (observations, points) you have, so the curse of dimensionality kicks in. You cannot learn reliably using all the available features. You need to select the relevant ones.

The feature transformation is used for the purpose you precisely identified in your question (Cover's theorem etc.).

Parameter optimisation concerns finding (or at least approximating) the optimal parameters of the model, leading to the best performance on new, unseen data.

Now, regarding neural networks and kernel-based methods, specifically support vector machines, they approach these three problems from a different angle, and I personally wouldn't say that one approach is uniformly better over all of the three.

In particular, to my knowledge, support vector machines still beat neural networks (and everything else, as long as you don't know which distribution lies behind the data) regarding the third point. They solve a quadratic programming problem and are guaranteed to find (or at least approach in the limit) the best separating hyperplane. On the other hand, neural networks perform gradient descent over a non-convex function, with many local optima, and offer only a "best effort" solution. But, finding the optimal solution in SVMs comes at a computational price: In order to find it, SVMs require pair-wise dot products in the feature space (the kernel matrix), so the complexity rises at least quadratically with the number of points. This makes them impractical for large data sets, with millions of observations.

Regarding the second point, feature transformation, SVMs do it using the kernel, while neural networks typically use multiple layers with many non-linear neurons. Computationally, computing the kernel is usually more efficient than propagating the signal through the layers, but this advantage of the SVMs is usually not enough to cancel out the above mentioned complexity in the optimisation part.

Also, in kernel-based methods, the feature selection part is left out. You need to do it manually, or use a different algorithm for preprocessing your data in a way that produces meaningful features. Neural networks, especially convolutional ones, elegantly combine the feature selection and the feature transformation part in a same architecture, making them easy to deploy and require less human expert input.

To summarise: It's a combination of computational complexity issues and ease of use that give the neural networks an advantage, at least for large and high-dimensional data sets.

In the answer here I give a short historical overview regarding the development of kernel-based methods in relation to neural networks, which you might also find relevant.

Update:

To give you a feeling how the methods differ regarding computational time, let us consider a classification task on a toy "two moons" dataset:

For small datasets, an SVM is faster and even more accurate than a neural network:

But, as the number of samples surpasses ~10,000, SVMs become computationally too expensive:

Notice that the scale is logarithmic, so the slope of a curve actually tells you about the power by which the computational time rises with the sample size. For neural networks it is almost linear, but for SVMs it is about quadratic.

(I also included a linear SVM and a logistic regression for comparison, but bear in mind that these cannot properly classify this data set).