July 13, 2011

Computers That Actually Compute Sentences?

MIT researchers have started designing computers that understand the meaning of a sentence.

Regina Barzilay, associate professor of computer science and electrical engineering at MIT, along with colleagues developed a system that generated scripts for installing a piece of software on a Windows computer by reviewing instructions posted on Microsoft's help site.

The team augmented a machine-learning system so that it could use a player's manual to guide the development of a game-playing strategy in the computer game "Civilization."

"Games are used as a test bed for artificial-intelligence techniques simply because of their complexity," Branavan, who was first author on both Association for Computational Linguistics (ACL) papers, said in a statement.

"Every action that you take in the game doesn't have a predetermined outcome, because the game or the opponent can randomly react to what you do. So you need a technique that can handle very complex scenarios that react in potentially random ways."

Barzilay said game manuals have "very open text.  They don't tell you how to win. They just give you very general advice and suggestions, and you have to figure out a lot of other things on your own."

As the computer takes various actions during the game, different words appear on screen, and it can look for instances of those words in the instruction set.

It can also search surrounding text for associated words and develop a hypotheses about what actions those words correspond to.

The researchers said the system was able to reproduce 80 percent of the steps that a human reading the same instructions would execute. 

The team also tested a more-sophisticated machine-learning algorithm that eschewed textual input but used additional techniques to improve its performance.  This algorithm won just 62 percent of its games.

"If you'd asked me beforehand if I thought we could do this yet, I'd have said no," Eugene Charniak, University Professor of Computer Science at Brown University, said in a statement. "You are building something where you have very little information about the domain, but you get clues from the domain itself."


Image Caption: "Civilization" is a strategy game in which players build empires by, among other things, deciding where to found cities and deploy armies. Image courtesy of Sid Meier's Civilization V


On the Net: