Skip to main content
5 of 7
Clarified the best algorithm is any element of Pareto front.
yters
  • 1.4k
  • 2
  • 13
  • 21

Why can we not find the generally superior machine learning algorithm in practice?

There are many machine learning algorithms. The no free lunch theorem (NFLT) says, in theory, all these algorithms are exactly equal according to an error function over all possible problem domains. In practice, this doesn't matter because we are only dealing with a very small subset of these problem domains.

In practice, this often involves a tradeoff between multiple objectives. Making a problem multi-objective instead of single objective often causes it to become much more complex and difficult. There is no longer a single best solution, but there are still better and worse solutions. One way of describing the set of better solutions is with the notion of "Pareto optimality," which is the set of solutions that dominate all other solutions in all objectives, but do not dominate each other. These optimal solutions describe a surface in a graph of the solutions known as the "Pareto front." The following Figure is an example of a Pareto front where solutions A-H dominate all other solutions, but not each other.Example Pareto front of Pareto optimal solutions for a two objective problem.

That being the case, if we ask "what is the best ML algorithm?" we cannot say "None, b/c NFLT," since we are asking about the best ML algorithm in practice. If the NFLT does not matter in practice, then there must be a best ML algorithm, in practice. If there is a set of algorithms that describe the Pareto front, then the best algorithm is any member of this set.

What is this best practical algorithm? There does not seem to be one, to the best of our knowledge. Even "magical" general ML algorithms such as deep learning or extreme boosting have many knobs to twiddle, and are only good for the right kind of problem. There is no one size fits all ML paradigm.

Yet, there must be one, since data scientists are able to match the right algorithm to the right problem and achieve outstanding results, such as Google's search capabilities. Whatever it is that powers the data scientist brain must be relatively simple, since human DNA can be compressed to 4 MB, not much bigger than, and often quite smaller than, many ML frameworks when zipped.

Furthermore, the data scientist brain algorithm is an extremely powerful program. For a binary prediction problem of $N$ predictions, there are $2^N$ different possible predictions. To be right more than half the time, we need to eliminate more than $2^{N-1}$ possibilities. We also have to do this in polynomial time. Both feats seem astounding for any reasonably sized $N$, especially since so many important problems are NP-Complete or worse in the general case.

Since we aren't dealing with a halting problem (data scientists reliably halt on good solutions), even some kind of assisted enumeration of 4MB programs in a Turing complete language would seem to hit on this master algorithm sooner or later.

Is there a CS explanation for this discrepancy, or flaw in my reasoning, that the super powerful and extremely quick master algorithm is <= 4MB, yet despite all our searching we've been unable to find it?

yters
  • 1.4k
  • 2
  • 13
  • 21