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

Question

TL;DR Our mind is a superior meta-machine learning algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have. Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover. However, despite our best efforts, no algorithm we've discovered has even approached this meta-capability. Is there a CS grounded explanation for this? The NFLT is not applicable because it does not apply in practice, and the human mind is an instance of said meta-algorithm.

---

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.

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?

Answer 1

Say that you want to minimize $f\left(x\right)$ where $x{\in}\left[0,100\right]$. What's the best solution strategy?

There's no free lunch...

In the general case, you basically just have to compute $f\left(0\right){\dots}f\left(100\right)$, then check for the largest value.

"No free lunch" means that, given the above problem, no one can provide a faster, reliable algorithm to optimize it beyond naively trying from $x=0$ to $x=100$.

... after you've eaten them all...

Say that you already had an optimization algorithm that called for you evaluating $f\left(0\right){\dots}f\left(100\right)$ twice. If you drop that done to once, then you've had your free lunch.

"No free lunch" applies once you've done all of this stuff already. So, it's less of a theory and more of a statement about optimality.

...and haven't missed anything

Say that $f\left(x\right)$ is well-behaved, where $$ \begin{array}{ccccr} &&\left|f\left(x\right)-f\left(x-1\right)\right|<10 && \forall x \\ \end{array} $$ ; then you can construct new evaluation strategies where you try to minimize the number of evaluations by identifying points that can't be minimal and skipping them.

It's hard to know what you might be missing

In machine learning cases where you're analyzing the real world, we don't really have an analytical problem statement. Physics isn't perfectly accurate; measurements aren't perfectly reliable; and things can change.

So, you're right that data scientists can usually improve algorithms in real-world cases.

Human brains are good at human problems due to extreme selection bias

Regarding,

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.

Historically, this oddity was discussed in "The Unreasonable Effectiveness of Mathematics in the Natural Sciences" (1960). The Wikipedia page discusses some common responses.

Personally, my take is that we and our science co-evolved, so evolutionary pressures have favored compatibility. Our brains are pretty well wired to think in ways that were both do-able and practical to our ancestors.

Answer 2

There are many dimensions that "intelligence" could potentially be measured on. We already know of some artificial intelligence schemes that do better than humans on some dimensions.

It's true that we don't have artificial intelligence schemes that do better than humans, on the sorts of problems that tend to arise in practice as part of everyday human life and experience. On the other hand, humans have had hundreds of millions of years to evolve and adapt. Artificial intelligence has only been around for maybe half a decade. That might be one possible explanation.

---

Separately: The question seems to be based on several misconceptions. Let me point out a few things you've written, and try to clarify the misconceptions:

The point is that our mind is a superior algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have.

Our mind is better for some tasks, but not all. There are other tasks where machines are better. For instance, machines are superior at chess, or at adding up small integers billions of times in a row without making a single error. Humans are superior at making other people laugh, cry, or feel better about themselves, or at folding laundry.

For instance, machines can solve Connect Four perfectly, but most people can't. Thus, if we allow "performance at Connect Four" as one of the dimensions that we're measuring Pareto-optimality at, machines are Pareto-optimal: they dominate humans in at least one dimension.

Now what you're probably really asking is, why do humans dominate machines in most dimensions? But to make that question well-defined, we have to define what is the set of all dimensions. What's probably implicit in that question is the assumption that you mean "the set of all dimensions we (humans) care about", or "the set of all dimensions that are meaningful to us (humans)". Now consider that the human brain has had hundreds of millions of years to evolve and get better at the dimensions that humans care about or that matter to us, whereas artificial intelligence hasn't.

Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover.

Actually, no, that doesn't follow. Let's suppose for the sake of argument that an entire human organism can be described in 4MB of data (after compression; let's not quibble about whether that's actually biologically correct; and let's not worry about the fact that Kolmogorov complexity is primarily meaningful in an asymptotic sense, and ignore those issues), or equivalently, 32 megabits of data.

That means that a program that behaves like a human would require 32,000,000 bits of data to describe. So, you're asking: Why is it hard to find such a program? Perhaps implicit in your question is: How many programs can there be? How hard can it be to find the right one?

The answer is: it might be very very hard. There are $2^{32,000,000}$ possible programs (of that length). That's an enormously large space -- and it's a space where maybe all but one of them are useless, and only one is any good. Trying all of the possibilities is way beyond feasible: like, you couldn't do it within the lifetime of the universe, even if you imagine a universe full of supercomputers, where each atom in the known universe has the computational power of one of today's supercomputers. $2^{32,000,000}$ is an unimaginably large number.

So, it shouldn't be such a great surprise that it might be hard to find an example of such a program explicitly. Just because we know that it exists doesn't make it easy to find such a thing.

For instance, even if space aliens had landed 150 years ago and told us that there exists a proof of Fermat's last theorem, it still would have taken close to 150 years to find the proof. Just knowing that a proof exists doesn't really help you in finding it. I bet that the Latex source file for the papers that prove Fermat's last theorem correct could be compressed to less than 4MB. Even if I tell you that there exists a proof whose Kolmogorov complexity is at most 4MB, it's still not at all easy to find that proof.