# How can data points be enough to learn a function?

Given any number of points, there are an infinite number of functions these points can be samples from. For $n$ points, any polynomial of degree $> n$ can be used to generate these points.

If there are an infinite number of functions, how does the net know which one to approximate? I know that ideal NN's are universal function approximators, but obviously real ones have limitations based on their architecture. But architecture limitations aside, how does the net "choose" which function to approximate? For any error function, there are infinite functions (again, architecture limitations aside) that would give you zero training error.

I know that not all error functions are convex, and they often have multiple minimas. But I'm pretty sure someone showed a while back that all the minimas tend to have relatively the same performance.

Do neural networks implicitely maybe make some sort of assumption on the function it tries to approximate? Maybe some sort of minimization of complexity of the approximated function? I don't see how data points are sufficient for learning...

## 4 Answers

The learnability of functions is a very deep subject. Indeed, the whole field of Computational learning theory is based around answering when this is possible and how.

Typically, you need to assume the true function comes from some parameterised model class, such as fixed structure neural networks, then consider how much data is needed so that with high probability, the generalisation error is small. As you note, you need to restrict the flexibility of the class of functions you consider. It's not possible to fit an arbitrary real function from data, since it can always vary unpredictably anywhere you don't exactly have data points.

In learning theory, the standard notion of the flexibility of a class is the VC dimension. Bounds on the error in the predictions from a fitted function depend directly on the VC constant. The case of neural networks has been heavily studied.

I would like to use an example to answer your question.

Suppose We have some data points, $(1,1),(2,2),(3,3),\cdots, (1000,1000)$, can we (now we use human learning not machine learning...) learn a function from them?, We may say, yes, it should may be $y=x$.

Now, do we have infinite data points and learned a function? No, we only have very limited number of data points, but we learned a function from it. We may also feel our approximation is pretty accurate, since all the data we have seen is perfectly fit our approximation.

From the example we learned, sometimes, the function we want to learn in real world may not be super complicated and few data points are sufficient.

An other example, suppose we want to learn a function to describe human height and weight, do we need all human's data? or some sample should be good enough?

• But what makes a $y = x$ any more correct than a 1000 degree polynomial approximation? If your metric for what makes an approximation good is how well it fits the data, don't both functions fit the data perfectly and so are equally good? – Phidias Apr 3 '17 at 2:44
• This is why you use out of sample data to test your model fits. – Matthew Drury Apr 3 '17 at 3:07
• @FarhadYusufali think about we are capturing some physical relationship in the world (say relationship between height and weight), it should be in certain form (say linear) but not some very high order polynomial. – hxd1011 Apr 3 '17 at 13:28
• @hxd1011 Why? I'm looking for mathematical justification... – Phidias Apr 3 '17 at 18:08
• @FarhadYusufali I think your question is more philosophical than mathematical. You may want to think the role of assumption in any research. "all models are wrong but some are useful" – hxd1011 Apr 3 '17 at 18:10

You are right. For a set of training samples, there are many different functions that can explain these samples. Each learning method favors some of these functions according to its hypothesis space and its hyperparameters. For example, a neural network with drop-out chooses a different function than the same NN without drop-out.

On the other hand, I would say that many machine learning algorithms are pragmatic methods, that is they try to find a model that produces suitable outputs, though their learned function are not exactly the correct function which generates the data.

I would like to add another point here. The best function is not always the function that gives you zero training error since such a function is prone to overfitting. In other words, it tries to model noises in the training data or fake regularities in data due to the limited number of training samples. In fact, regularization techniques such as drop-out are introduced to prevent the learning method to favor too complex functions.

This will be a rather long elaboration on @hxd1011 answer. Suppose we observe $$D = (1,1),(2,2),(3,3),⋯,(1000,1000)$$ There is a mathematical justification why we choose $y = x$ over some high degree polynomial. It's called bayesian Occam's Razor. From Bayes theorem $$p(m|D) \propto p(D|m)p(m)$$ where $p(m|D)$ is a probability that we are dealing with a model $m$ having observed data $D$.

Likelihood

Now consider some complex model $m_C$ that can be fitted to many observed datasets, we have $$\sum_{D' \in \mathbb{D}}p(D'|m_C) = 1$$ so if $|\mathbb{D}|$ is large, we expect each probability of observing a dataset $p(D'|m_{C})$ to be, on average, smaller than for some simpler model $m_S$. So since $y=x$ is a simple model, and observed data is coherent with it, we assign it higher probability, i.e.

$$p(D|m_S) > p(D|m_C) \implies p(m_S|D) > p(m_C|D)$$

assuming the same prior on models $p(m_C) \simeq p(m_S)$

Prior

Of course, from the whole set of simpler models that fit our data well, we still prefer some of them more than others. For example, the observed data also fits a model $m_{S2}$ as

$$y = \begin{cases} -1 &\mbox{if } x = 1001 \\ x & \mbox{otherwise}\end{cases}$$

and here the prior $p(m)$ comes into play, where we usually prefer "more natural" models, of course this is less mathematical and more subjective.