# Learning capacity: Deep Learning vs Traditional (Shallow) Learning

I am currently doing a course in coursera in which Andrew Ng draws the following image:

Does anybody know any references/reasoning that justify the drawn graph? Were any experiments conducted to obtain it? If so, could you point me to them?

I have already asked in the coursera forum and sent an e-mail to the support team with no avail.

Thank you

I believe this statement can be supported with the concept of VC dimension. This blogpost provides a simplified explanation of the term. VC dimension can be understood as an ability of a classifier to learn complex dependencies in the data. From other hand, models with a huge VC bound tend to overfit on small amounts of data.

However, the plot you provided here depicts what is happening when our training set grows indefinitely - the win situation for models with a large VC dimension.

The VC bound of neural networks is something like polynomial from number of weights and connections between them. While VC dimension of a SVM classifier is linear to the dimensionality of the space it operates in.

Thus, neural networks can benefit more from larger amounts of training data. And the more weights you have, the better will be the result. Of course, given that the number of training samples is at least 10 times more than number of weights (a rule of thumb), so you do not face overfitting. That is why data augmentation and regularization are so important in deep learning.

This image comes from the personal experience of computer scientists working with Deep learning networks for quite sometime now. This holds true for all the deep learning work one does, where the increase in the size of the dataset and with a well defined problem, scales better than traditional ML, simply because of the capabilities a deep learning network provides.

There are a number of reasons why deep learning scales better with more data than traditional machine learning, in particular in areas of computer vision and speech recognition (where deep learning has been most successful).

Many traditional machine learning models (nearest neighbors, naive bayes, tree based models, kernel machines etc.) assume that predictions of for a new point should be somewhat close to neighbors of that point or that the output can be interpolated (in some way) from those neighboring points. However, in high dimensions, there often are no (obvious) neighbors. (Often called the curse of dimensionality.)

That means that traditional machine learning often can "only" generalize well locally. If you want to generalize non-locally, you need to introduce dependencies between the regions of the input space by introducing additional assumptions into your model.

To me this is most obvious in object recognition. Throwing together a bunch of random pixel rarely (never) gives you an image of an actual object. That is because most objects we care about in object recognition only make up a tiny portion of all possible images in $$\mathbb{R}^3$$. To be more efficient we should make additional assumptions about the input space.

A convolutional neural network architecture, for example, shares parameters and applies the convolutional kernels at every input pixel. That is the assumption that features/objects should be the same, independent of the location in the image. This assumption makes CNNs a lot(!) more scalable and generalize better to the task of object recognition at the same time.

RNNs make similar assumptions for sequence data.

Large neural networks can therefore scale to more data more efficiently. Traditional machine learning models, on the other hand, will be "outpaced" by the exponential challenge of the curse of dimensionality because their capacity is somewhat linearly related to the number of diverse inputs. Neural networks, given the right assumptions (i.e. the right NN for the right task), can generalize to exponentially many more regions of interest with the same number of inputs.

At the end of chapter 5 in the "Deep Learning" there is an introduction to the challenges of traditional machine learning and some references to experiments supporting these hypotheses.

This plot is just a conceptual sketch. It is used to convey a message at page 10 of "2018 Machine Learning Yearning (Draft version) - Andrew Ng". I checked "2016 Deep Learning - Ian Goodfellow, et al." and many seminal papers on deep learning and did not find a real example.

A hidden assumption:

A key assumption of this sketch is the number of model parameters, if the number of parameters is kept constant and similar for deep and shallow models, this plot occurs. Otherwise, for arbitrarily large training data (right side of the plot), any universal learner, as simple as a neural net with only one hidden layer (link), can perform as well as any deep learner if the number of parameters is allowed to increase arbitrarily.

Power of deep learning:

The literature that justifies the power of deep learning is quite technical; for example this paper, and this paper. To proceed, "capacity" of a model must be understood first. Roughly speaking, capacity of a model is the most complex function that it can represent; one formalization of this concept is "VC dimension". In theory, if capacity of a shallow model with $$m$$ parameters is $$O(c)$$, capacity of its deep counterpart with $$m$$ parameters that are spread across $$d$$ layers is roughly $$O(c^{d})$$. This is an exponential growth in capacity with respect to depth $$d$$. As a result, with more training data, a deep model does not reach its capacity as fast as a shallow model with the same amount of parameters. This is what the sketch tries to convey.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 7, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.44322463870048523, "perplexity": 525.4061993625148}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-43/segments/1634323588053.38/warc/CC-MAIN-20211027022823-20211027052823-00307.warc.gz"}