by Derry Tanti Wijaya
“Milk drinkers are turning to powder”—here is a classic example of a sense that is tricky for humans to interpret but next to impossible for machines. As humans we instinctively know that milk drinkers can’t become powder just by drinking milk; otherwise nobody would be brave (or stupid) enough to drink it. We have the intelligence to know a more plausible alternative is that the said milk drinkers are simply switching to powdered milk.
Imagine now a computer that can read and understand this phrase the way humans do (think Threepio in Star Wars or that depressed robot in the Hitchhiker’s Guide to the Galaxy). Unfortunately, as of yet, there is no such computer that can read and understand sentences the way we do. An example of computers’ lack of ability to understand humans was observed, and elegantly articulated by Gary Marcus, a writer for The New Yorker. He discovered that Google does not know that the answer to the simple enough, albeit weird question, “can an alligator run the hundred-meter hurdles?” is no (alligators, no matter how determined, can’t run hurdles). Google instead returns a page from the Florida Gators track and field website. The writer claims that the alligator question is hard for computers to understand because they “require common sense, something that still eludes machines”. Common sense states that milk drinkers are humans and humans don’t spontaneously change to powder just by drinking milk. The “disappointed” alligators are animals and therefore can’t sign up for the race – plus their legs are simply too short to run hurdles.
To overcome this lack of common sense in machines we built a machine, at the Read the Web group in Carnegie Mellon University, that can read and learn common sense knowledge about the world. Such common sense knowledge can in turn improve the ability of machines to understand human language. The machine is called NELL, short for Never Ending Language Learner. To learn in a never ending fashion, NELL uses a semi-supervised machine-learning algorithm that, at its simplest, starts from a dozen or so human-provided examples for a category, goes to the Web to find mentions of these examples, extracts patterns surrounding the mentions, and uses the extracted patterns to predict more examples of the same category. For example, for the category of mountain, given an example such as Kilimanjaro, NELL finds mentions of Kilimanjaro in web documents such as “… hiking mount Kilimanjaro …” and extracts the pattern surrounding the mention (in this case “… hiking mount …”). If NELL then sees this pattern occurring with other entity such as “hiking mount Rainier”, NELL can predict Rainier to be another example of the category mountain. The process then repeats using thenewly predicted examples to extract even more patterns and make further predictions. This cool mechanism allows NELL to continuously read online text 24/7 and learn more common sense facts about the world without human supervision. The result is a knowledge graph of entities and the categories and relations of these entities. NELL, for example, has learned on its own that the entity Disney is of the category company, whose C.E.O. is Robert Iger and whose headquarters is located in Burbank.
Another core feature of NELL enabling it to read and learn well is coupled learning, which is inspired by the way humans learn. We do not learn things in isolation. We learn, for example, that if a thing is a piece of furniture lying about in our living room, it cannot at the same time be a mountain lying somewhere in the Himalayas. These categories (mountain and furniture) are, in other word, mutually exclusive. NELL uses the idea of mutual exclusivity to make its prediction more accurate. For instance, once it predicts that chair is a type of furniture, it will not predict chair as a type of mountain (although chair convincingly shares similar patterns to mountains such as “climbing the …”, as in “climbing the Himalayas” vs. “climbing the chair”). The idea of coupled learning also makes learning easier. For example, learning that Krzyzewski coaches (instead of exorcises) the Blue Devils is easier if we also know that Krzyzewski is a person and that the Blue Devils is a sports team (and not a congregation of blue-colored devils). Using these two ideas: semi-supervised and coupled learning, NELL is able to run continuously on its own and accurately extract common sense facts about the world.
Besides reading and learning 24/7, NELL also has the ability to think by itself. For NELL, this thinking means the ability to reason or making inferences over the knowledge graph that it has previously built. By doing a random walk on the graph, NELL is discovering common sense rules about the world. For example, if an athlete plays in a team and if the team plays in a league, then this means that the athlete also plays in the league. NELL is beginning to learn on its own such common sense rules that come naturally to us humans.
NELL is still far from perfect; there is still the question of semantic drift over time: once NELL learns a wrong entity for a category, say Java cookie for the category food, it may drift to learn other wrong examples, such as computer file for the category food because computer file shares many similar patterns in web documents to the wrong “cookie”. NELL is therefore in urgent need if the ability to reflect and ponder upon its learned “common sense”. There is also the question of applying the knowledge NELL has acquired and NELL’s inference engine to make conclusions about sentences in the world that will showcase its ability to understand human language. We believe that NELL can soon conclude—much to the relief of the milk drinkers everywhere—that the milk drinkers will still be pretty much alive even after “turning to powder”!
Derry Tanti Wijaya is a 2010 fellow of the Fulbright Science & Technology Award, from Indonesia, and a PhD Candidate in the Language Technologies Institute at Carnegie Mellon University.