In his 1950 paper “Computing Machinery and Intelligence,” Alan Turing introduced the idea of machine-learning, including subfields that remain vital 60 years later: stochastic local search, genetic algorithms, supervised learning and reinforcement learning. But he didn’t comment on one of the most important developments of recent years–the power of massive amounts of data to solve problems through unsupervised learning.
Let’s define some terms. Supervised learning means that a teacher gives the right answers: “8 x 7 = 56.” Reinforcement learning means the teacher asks, “What is 8 x 7?” and gives a reward for the right answer, or a rebuke for a mistake. But in unsupervised learning the student is given, say, the complete set of multiplication exams for the last 20 years–some problems with the right answers, some with the wrong ones–and it is up to the student to make sense of it all.
One might think that this approach would be the worst kind of teaching–avoided at all costs. Not so when the student is a computer, however. A computer, for instance, can remember everything and work at blinding speed, so it gains a huge advantage by not having to wait for the teacher. And when data appear “in the wild”–or generated for free on the Web–it can be just the thing for the computer as student.
Consider the task of building a program to correct spelling errors. A supervised approach would start with a dictionary of known words and have a teacher instruct the program on each correct word. But new words are coined all the time, and standard dictionaries don’t yet know “Wii” or “iPhone.” An unsupervised approach would have the computer read billions of Web pages and sort the correctly spelled new terms from the typos. This approach sounds like chaos, but in fact it works quite well and is used in practice by search engines today.
Or consider programming a computer to translate from Chinese to English. A decade ago, it was thought that supervised learning was the way to do this: A team of linguists created dictionaries and grammar rules and taught them to the computer. Today most computer translation systems are built with unsupervised training. The computer is shown hundreds of millions of examples of translations from Chinese to English, and eventually the computer detects patterns: This word in Chinese corresponds to this word in English; this phrase in Chinese corresponds to this phrase in English except when it is followed by one of these phrases; and so on.
Crucial to this approach is the transition from small data sets to large. With only a million words of training data, the resulting systems turn out very poor. But with hundreds of millions of words of training data, computer translation systems cross a threshold and become quite competent–although it still doesn’t take more than two or three sentences to realize they are not perfect.
Words are not the only data from which computers can learn. There is also scene completion, which is found in image-processing.
Suppose you want to remove an ex-spouse from a photo. Can a program automatically fill in the proper background to take the place of the ex-spouse? When programs were given unsupervised training with thousands of images, they could not solve the problem. But rather than give up, researchers added millions of photos, and suddenly the computer learned to perform scene completion quite well. And again there was a data threshold beyond which the programs performed well.
The same lesson applies to other types of data and other domains. Genomic data, medical images, geographic data–in every case there have been recent advances in unsupervised learning made possible by the accumulation of data crossing a threshold.
How is this all possible? In his story “The Library of Babel,” Jorge Luis Borges imagines a library that contains every possible book. Whatever questions a patron might have, if it could be answered in a book, it would be on the shelves of the library. In a way, the Internet is approaching the Library of Babel: If it is a question someone else has thought of before, chances are the answer is somewhere on the Internet. And as in the Library of Babel, for every right answer there is a wrong answer too. The trick to unsupervised learning is being able to tell the difference, at least most of the time. That can, in general, be done by starting with what you are confident is true and building out Webs of trust from there.
Did Turing foresee the power of unsupervised learning and the existence of a data threshold? It is hard to say. He seemed to be pragmatic and open-minded toward new approaches: When considering whether it would be best to teach a computer chess or English first, he said, “both approaches should be tried.” He understood that human-level intelligence would require billions of units of information, and he appreciated that this would be a large number–particularly compared to computers’ tiny capacities in his era–as well as a finite one, within grasp in a few decades time. But in the end there is no clear evidence that even Turing could foresee the radical transition that can occur when we move from mere thousands of examples up to billions. It does, however, fit in with his philosophy in three ways.
First, it gives a route toward human-level intelligence, at least for tasks for which sufficient data are available, and is an example of his assertion that “Machines take me by surprise with great frequency. This is largely because I do not do sufficient calculation to decide what to expect them to do.”
Second, the leap forward in unsupervised learning fits in with his work on cryptanalysis; his Banburismus technique uses letter frequencies to select the most probable interpretation of a coded message in a way that is similar to the techniques used today to do spelling correction, speech recognition and other tasks.
Third, it gives us a simple universal machine that can be applied to any number of tasks with the right data. Turing’s mathematical construct, the Universal Turing Machine, does this in a general sense for all programs, but an unsupervised learning machine does it in a practical sense for a wide variety of problems. I think he would have been surprised and pleased.
Back to The AI Report
Peter Norvig is director of research at Google. He is a Fellow of the Association for the Advancement of Artificial Intelligence and the Association for Computing Machinery and co-author of Artificial Intelligence: A Modern Approach, the leading textbook in the field. Previously he was head of computational sciences at NASA and a faculty member at USC and Berkeley.