What's really revolutionary about machine learning?

What's really different about machine learning? Compared to 20th century AI, how is machine learning revolutionary (as opposed to evolutionary)?

I'm going to argue that the real revolution in machine learning is that allows humans to "outsource" problems that are in the computational complexity class NP. Specifically, it allows humans to perform a task in NP by solving a problem in P. I'll describe what these terms mean—and how I get to this conclusion. But the relevance of this observation is that, if it's true, it gives a very fine point to how exactly machine learning augments human capabilities.

Background: Machine learning

Here's a chart that compares traditional program to machine learning.

In traditional programming, we give the computer data and a program. The computer runs the program, hydrating it with the data, to give you some output.

Now machine learning, we give the computer some data and some example output. This example output is what we would expect our program to produce. So, if we're interested in image classification, we'd take some images and we label them "cat" and "dog." Now the computer synthesizes a program that produces this output.

We just have to show the source data and we have to show it the output we expect. Then, of course we can take that program and apply it to new data that we haven't seen before.

This paradigm really shines when we can get the computer to produce a program that we couldn't have written ourselves. Now we don't need to know how to write a program in order to write it.

Remember, in traditional programming, some human has written the program. That's a pain. People make mistakes when they write programs. And humans don't even know how to write programs for some things. Consider image recognition. If you have a photo, and the photo has a building in it, recognizing and pointing to the building is easy for any human. But we can't describe how we did that. How did we recognize it as a building? We could even say, "that's a very 80's building." What about the building makes it 80s? Our difficulty in describing how we perform these tasks make it difficult to write programs that do the job for us. [1]

So, for problems like this where we can't easily describe our methodology for doing a task, machine learning can help us synthesize a program from example outputs.

Is that the whole revolution in machine learning? Sure, maybe this paradigm is easier for the programmer. But it also produces new types of errors. The models that machine learning produces are opaque, and they're difficult to debug. They can fail in unexpected ways. Sometimes really harmful ways. So what is the real revolution here? Is it just that we're "letting the computer do programming for us"? or is there something else?

P vs NP

To talk about this more, we first have to introduce the concept of P vs NP.

The core concept here is that some problems are much easier than others. Writing a symphony is much more difficult than enjoying a symphony. Anyone can sit down and listen to a symphony. Sitting down to write one is much more difficult.

If you have a program, you can discuss its time complexity—how long it takes to run. P and NP are complexity classes. In broad strokes, a program that can be run quickly is said to be "in P" (it can run in polynomial time), whereas a program that cannot be run quickly is "in NP" (the fastest known algorithm runs in non-polynomial time).

So, we would say listening to a symphony is "in P," whereas writing a symphony is "in NP." Remember, cognition is itself a kind of computation! [2]

Regarding the examples of hard-to-write programs, we can imagine that writing a program might be in NP. But if you have a computer handy, verifying that a given program does the thing it's supposed to do is in P. So maybe you can already see where this argument is going.

Machine learning reduces NP problems to P

Machine learning in general may reduce humans' problems to P, letting the computer do all of the work that's in NP. Perhaps this, more than program synthesis per se, is the fundamental shift in machine learning.

If this is the case, machine learning's core innovation is not its statistical methods. Nor that machine learning algorithms “emulate human cognition” [3] (though it is possible that human cognition is statistical for the same reason machine learning is statistical: because certain statistical methods are especially well suited to solving problems in NP). Instead, what makes machine learning special is that it lets humans outsource problems that are in NP.

More precisely, the theory here is that, for some human task in NP, there exists a model that can perform that task such that the human's job in training that model is in P. We're not measuring the complexity of the algorithm itself! Nobody is claiming that machine learning algorithms are performing tasks in P that humans can only do in NP. The claim instead is that the human's job in is in P.

So what?

So what? Well, if this is the case, it would put a fine point on the idea that machine learning expands human capacity. Specifically, it would allow us to articulate how machine learning expands human capability.

To make this case, what we would have to do is find a (human) task that's in NP. Say we want to write a symphony. We would have to, somehow, describe the computational complexity of this task. We would at least have to say what complexity class it belongs to.

Then, we would have to train an algorithm to write a symphony. We would want to estimate the complexity of the human's job in training this algorithm.

If the target task is in NP, and the human's job in training a classifier to do that task is in P, then we have compelling evidence to support this claim. We could do this experiment for a variety of tasks; the more we do, the stronger our evidence that this P-to-NP task transfer describes the specific route by which machine learning expands humans' capabilities.

Now what?

The hard part here would be measuring the complexity of human tasks. Good luck with that!

Footnotes:

[1] A program is essentially a description of a methodology.

[2] I don't mean that the brain is literally a computer. Computation is a very general concept that potentially underlies almost all physical phenomena; see edge.org's conversation with Stephen Wolfram.

[3] The claim that machine learning algorithms—even neural networks—model human cognition has always been a dubious one. Neural networks are 1940s-era models of the brain, including only cartoon models of neurons. They don't model neurotransmitters, which are certainly relevant to the way the human brain does computation.