Two ways to understand overfitting (and don't peek!)

Assorted comments on overfitting

The very first time I was introduced to the notion of overfitting -- by three diagrams of regression curves on scatter plots labelled as you may guess -- I became very uncomfortable. I was probably eleven years old, and did not understand Bayesian statistics, did not realize that seeing 51 heads out of a hundred didn't imply that the coin genuinely had a heads rate of 0.51.

Or rather: I didn't realize that I did realize that. If you had made me bet on the number of heads that would come up in the next hundred flips, I would not provide odds that would indicate an honest belief of seeing 51 heads.

(Because deep down, I had a non-uniform prior.)

And the same principle applies to drawing regression curves. You may insist that your curve with all its squiggles is "unbiased" or give any one of the terms (one for every squiggle) used to describe non-Bayesian estimators, but ultimately -- that's not the curve you'll bet on. You know it's just far more likely that those squiggles are the result of noise which will not be the same (or knowably correlated) in the next sample, than for them to actually be a determining feature.

Yes, maybe the 79th coin toss will always be a tail because of a tiny AI hidden in the coin that counts, or maybe it was the result of factors that affected the 79th coin toss that you just didn't measure. While your data should affect your beliefs, they shouldn't completely overrule your priors.

And that's the key idea behind overfitting (and really the Bayesian notion of probability in general) -- how will your model, based on your data, of perform if you exposed it to data it hasn't yet seen. Because using it on data it hasn't seen is the point of your model -- that is your purpose in building it.

So overfitting occurs when a model learns features specific to your particular data set that don't generalize well. There are two ways this can occur:

• The training set is a biased sample: E.g. MNIST digits are all centered (but suppose you're testing on non-centered digits), or your medical database is all from a particular country. 
• There is noise: I mean, of course there's noise -- it's a statistical problem. Even if the world were deterministic, you still don't have all the information in the world. And you should avoid your model using this noise to make predictions, since noise is, by definition, unpredictable.

The first is a more tractable problem -- it can often be solved by data augmentation (if you have a very good picture of exactly how the data set is biased) or transfer learning (if there's a good chance the model is picking up on important features so you can just train it on the ones it missed). It's important to develop interesting transfer learning algorithms to solve this anyway, as the way humans learn often involves biased samples (e.g. personal experience) and reasoning capacity to unbias their knowledge. 

(Not that humans do always do this -- people often do form beliefs based on mere personal experience, but humans are capable of reasoning more clearly.)

The second is a problem that requires algorithmic solutions that hint our neural network towards Bayesian solutions. Solutions like "well, parameters are just a priori unlikely to be very large, so let's penalize that" (Lasso/Ridge regression), or more complicated (to explain in a simple Bayesian way) regularization algorithms like cross-validation and early stopping.

Another unclassified comment on overfitting: it's very easy to mistakenly "peek" at the test data. Simply in the act of saying "hey, this model works well on the test data, let's choose it" you are already performing a simple algorithm that checks several models and chooses them based on their performance on the test data -- i.e. you are kinda training the model on the test data, even if it is not seen in your code, just in your choice of hyperparameters.

That's why developing some kind of "theory" of hyperparameter optimization and regularization techniques is of importance, so you actually have a theoretical justification for picking your models. 

(Of course, this is hard. We've always been picking models, haven't we? For example when we decide to model something as belonging to a particular family of distributions so we only have to optimize in a 1-dimensional parameter space instead of the literal theory-space. In a sense, machine learning is the way to avoid modeling, due to the universal approximation theorem -- and the hope is that we can eventually make the priors as human-like as possible, which is the eventual goal of hyperparameter optimization and regularization algorithms.) 

Machine learning as function approximation; statistical and cognitive motivations

The most general formulation of machine learning is that it is the attempt to approximate (or "learn") some mathematical object. For example:

• Regression attempts to approximate a function.
• Classification attempts to approximate an equivalence relation.
• Dimensionality reduction attempts to approximate a parameterization.
• Generative neural networks attempt to approximate a distribution (i.e. a sampler).
• Representation attempts to approximate a compression algorithm.
• Game-theoretic learning (e.g. reinforcement learning, no-regret learning) attempts to approximate a distribution of strategies. 
• Neural networks in NLP attempt to approximate a vector space that effectively represents desired relationships between words.

The Data Science course addresses several "toy algorithms" that discover low-order or simplified approximations. There are two -- different -- explanations of what more "AI-esque" machine learning is, which also lead to two different motivations for machine learning, and two different ways to understand each neural network architecture and each of some ideas in machine learning.

1. The statistical motivation -- machine learning is a non-linear generalisation of "linear" statistical techniques (data mining) like linear regression, PCA and linear decision boundaries. One can always do these linear techniques with some transformation of the data that makes relationships linear (while making sure the transformation is not absurd), but you need a way to "train" what the right such function is. In this sense, machine learning acts as a function approximator.
2. The cognitive science motivation -- a computer should be able to do whatever a brain can, but how exactly does a brain do the stuff it does? To take a simple example, the brain can recognise digits -- well, whatever the brain does, it takes an image as input and outputs a digit, i.e. it's a function. So once again, we need a function approximator.

Great. So machine learning is about making function (or object) approximators. The basic idea is that we're looking for a function that minimises the overall error for a population of data -- it's basically a calculus of variations problem, isn't it? Well, except it isn't, because we don't have access to the entire population, so we need to avoid overfitting (i.e. we need to consider a Bayesian prior). This is also what we meant by "making sure the transformation is not absurd" as we mentioned.

As a general rule, I'd say that if a feature of human brains are present at birth, we should expect to have to hard-code it, while if a feature is learned by humans, we should definitely get our AI to learn it, too (this is the "converse" of a general rule I have when trying to organize knowledge about biology in my head, which is we pretend that evolution is not an algorithm but a hard-coding, simply because actually trying to simulate an evolutionary algorithm in a highly complicated environment is hard). So for example, the transformations that a spatial transformer network finds acceptable are hard-coded, because we didn't actually need to stand on our head or squish our eyes with a truncheon to learn how to read squished-up text. 

Anyway, we want a universal function approximator -- a system that can generate a function arbitrarily close to any given function given sufficiently many parameters. A basic example of such a system is polynomial regression, but for most applications this has the wrong Bayesian prior (it gives zero prior probabilities to high-order polynomials, but most machine learning applications require functions with heavy non-local effects).

Another function approximator is a neural network. That a neural network (even of single layer) is a universal approximator is called the universal approximation theorem, i.e. functions can be written as linear combinations of some scaled and translated sigmoid functions.

(Exercise: explain why the universal approximation theorem is true for the sigmoid function. What other kinds of functions is it true for? It's actually not that hard at all. If you do get stuck, check out the visuals in Michael Nielson's e-book. A rigorous proof can be found here.)

In fact, the universal approximation theorem is not actually particularly important at all to the success of neural networks -- like we said, plenty of systems are universal approximators, but they don't have the right Bayesian prior (and this matters when you have limited data). The single-layer neural network actually has a bad implied prior for many tasks, which is why we usually study "deep" neural networks, which have a surprisingly good prior.

I have seen many explanations as to why this is so: deep learning means doing things in steps, deep learning corresponds to decomposing "hierarchy" or "structure" in the world and our world is "inherently hierarchial", etc. But honestly, these all seem like terrible rationalizations -- I don't even see how these claims are testable. You would need to create a system that isn't "inherently hierarchial" and demonstrate that deep learning doesn't do very well on it (which, as far as I can see, makes no sense). The right way to "explain why deep learning works so well" is to compute the implied prior and find out how it scales with depth.

Someone do this.