What characterizes a function that is easy to learn?

Question

When performing machine learning, the performance of the machine learning method is dependent on the original function $f$ that we are trying to learn (let's forget for a moment the non-deterministic error and focus on the properties of $f$).

I have a conceptual question. What would make a function easy to learn? For instance, a linear function can be easily learnt by linear methods such as linear regression and SVM. But in the general case, what would make a function easier to learn for decision trees or a neural network?

I believe feature engineering helps us move to a feature space in which the function we want to approximate is easier to represent. But what properties exactly are we trying to achieve for this function?

Answer 1

If we have infinite data and unlimited computational power, any function can be approximated with a very complicated model, such as, neural network with infinite hidden unit.

In real world, when we have limited data / samples from the function and limited computational power, simple functions (say, linear function, piecewise functions) may easier to learn. This is because the samples can be more "representative to the function". Think about a line, 2 samples from the line, would fix the function. However, it is tricky to define what is "simple function", because it is heavily depending on what models we use.

For example, a simple sine function is "easy" to learn with Fourier basis, but "hard" to learn with polynomial basis. On the other hand, a linear function is hard to learn with "Fourier basis". Similarly, a piecewise constant function is easy to learn with tree. etc.

Therefore, it is impossible to say easy or hard, the function is "easy to learn" when you have enough data, and you choose the "appropriate" class of function to approximate.

Answer 2

Different learners / classifiers, by their nature, assume that the response function is of a specific character. Consider this figure (copied from the Scikit-learn page on classifier comparison; click on it for a larger version):

In particular, notice that Linear SVM (the third column from the left) outputs parallel bands with varying possible orientations, Decision Tree and Random Forrest models (the sixth and seventh from the left) chop the space into regions with borders strictly parallel to the axes, and QDA (far right column) induces a curve from the family of conic sections. (All the classifiers assume the pattern of the response function has some certain nature, but those are the easiest to see / most distinctive in the figure.)

The result of this fact is that a learner will do best if the kind of pattern it is designed to work with approximates the true pattern better than any other learner you try. As @hxd101 notes, "If we have infinite data and unlimited computational power, any function can be approximated with a [sufficiently] complicated [version of any] model [type]". However, short of that, the best matching learner will tend to outperform.

To answer your question explicitly, the converse of the aforementioned facts is that, for whatever learner you are using, the function that will be easiest to learn is the one that perfectly matches what the learner is designed to detect. Or put in a different way, there will be no single function type that is easiest to learn irrespective of the model type you use to try to learn it. Feature engineering will help if it moves the pattern towards the best matching type or makes the information in the data easier for the model to extract.

Answer 3

Learnability, e.g. in the PAC (probably approximately correct) framework, is usually not defined in terms of what you call the original function but in terms of the hypothesis space. That is you pick a hypothesis class (e.g. the class of linear functions) and this class is then learnable if with high probability you can choose a big enough sample that allows you to find a function from your hypothesis class that is either optimal or closely approximates the optimal hypothesis. For example, all finite hypothesis classes are PAC learnable (e.g. classes that are represented on your computer).

The hypothesis class encodes your prior knowledge about the problem at hand. If your question is whether you can find the original function without any prior knowledge then the so-called “No Free Lunch” theorem of machine-learning states that PAC-learning is impossible without restricting the hypothesis class. "The “No Free Lunch” theorem states that there is no one model that works best for every problem." (First introduced here.)

In this sense, the more you know about your function, the easier to learn.