Dr. Turing suggested that a machine could be said to think if the human interrogator could not distinguish it from the other human. He went on to predict that by 2000, computers would be able to fool the average interrogator over five minutes of questioning at least 30 percent of the time.
Although the Turing test, as it is now called, spawned a vibrant field of research known as artificial intelligence, his prediction has proved false. Today's computers are capable of feats Dr. Turing never imagined, yet in many simple tasks, a typical 5-year-old can outperform the most powerful computers.
Indeed, the abilities that require much of what is usually described as intelligence, like medical diagnosis or playing chess, have proved far easier for computers than seemingly simpler abilities: those requiring vision, hearing, language or motor control.
''Abilities like vision are the result of billions of years of evolution and difficult for us to understand by introspection, whereas abilities like multiplying two numbers are things we were explicitly taught and can readily express in a computer program,'' said Dr. Jitendra Malik, a professor specializing in computer vision at the University of California at Berkeley.
Dr. Manuel Blum, a professor of computer science at Carnegie Mellon who took part in the Yahoo conference, realized that the failures of artificial intelligence might provide exactly the solution Yahoo needed. Why not devise a new sort of Turing test, he suggested, that would be simple for humans but would baffle sophisticated computer programs.
Dr. Manber liked the idea, so with his Ph.D. student Luis von Ahn and others Dr. Blum devised a collection of cognitive puzzles based on the challenging problems of artificial intelligence. The puzzles have the property that computers can generate and grade the tests even though they cannot pass them. The researchers decided to call their puzzles Captchas, an acronym for Completely Automated Public Turing Test to Tell Computers and Humans Apart (on the Web at www.captcha.net).
One puzzle, called Gimpy, consists of a display of seven distorted, overlapping words chosen at random from a dictionary of simple words. Solving the puzzle requires identifying three of the seven words and typing them into the box provided. The Carnegie Mellon group also created a simplified version of Gimpy -- a single distorted word displayed against a complicated background. It is now part of Yahoo's registration process.
Another Captcha, called Sounds, consists of a distorted, computer-generated sound clip containing a word or sequence of numbers. To solve the puzzle, a user must listen to the clip and type the word or numbers into the box provided.
The idea of using puzzles to prevent automated registrations was not new. Other e-commerce sites, including the AltaVista search engine and eBay's PayPal service, were experiencing problems like Yahoo's and independently came up with Captcha-like puzzles. Through its acquisitions, Hewlett-Packard holds a patent on text-based Captchas.
Still, researchers credit Dr. Blum for the breadth of his vision. Dr. Blum ''did a great thing by recognizing that this problem is much more than solving a nuisance for Yahoo and AltaVista,'' said Dr. Andrei Broder, who helped develop the AltaVista puzzle and is now at I.B.M.
As a cryptographer, Dr. Blum was familiar with the constant efforts of cryptographic researchers to advance the field by cracking codes to discover their weaknesses.
He hoped to start a similar dynamic for Captchas, spurring researchers to try to create better Captchas while building computer programs that crack existing ones.
''Captchas are useful for companies like Yahoo, but if they're broken it's even more useful for researchers,'' Dr. Blum said. ''It's like there are two lollipops and no matter what you get one of them.''
In October Dr. Blum got his wish. Dr. Malik of Berkeley and Greg Mori, a student, devised a computer program that could crack Gimpy -- both the simple version used by Yahoo and the harder one on Captcha's Web site.
Since its inception two years ago, the Captcha effort has been building. Several research teams have joined the Captcha effort, trying to make and break Captchas and even using the ideas behind Captchas for new lines of research.
Researchers at the Palo Alto Research Center modified a program used for scanning text to create a program that could solve certain types of Yahoo-Gimpy puzzles, says Dr. Henry Baird, who was in charge of that effort. The group is also developing a new text-based Captcha called Baffletext that it hopes to license to e-commerce sites.
Inspired by the themes behind Captchas, Dr. Doug Tygar, a professor of computer science at Berkeley, and his student Monica Chew are developing alternatives to passwords that are tailored to human skills. Humans have trouble remembering long, random strings of characters, yet they excel at remembering faces and objects, noted Dr. Tygar.
Dr. Malik said he first became interested in the effort after attending a Captcha conference at the Palo Alto center in January. After he and his former student Dr. Serge Belongie, now at the University of California at San Diego, developed a new object recognition technique modeled to have some of the properties of human vision, Dr. Malik decided that Captchas were ideal for testing their method.
The Yahoo-Gimpy cracking program, written by Mr. Mori, takes a version of the easy Gimpy, a distorted word displayed in a cluttered background, and finds some points along the boundary of each letter, using standard techniques of computer vision theory.
Then, applying the Malik-Belongie method, it makes a radial chart for each point indicating where the other boundary points are in relation to it. The charts of boundary points for that letter are compared with the charts of boundary points for all 26 possible letters. The closest match is usually the correct answer.
Using various tricks to make it run faster, the program can crack an easy Gimpy puzzle in a few seconds, and it gets the right answer over 80 percent of the time.
For the harder version of Gimpy, the researchers devised a program that examines entire words instead of individual letters, so its performance is in minutes rather than seconds, and it gets the puzzle right only about a third of the time. Still, the program will need on average only three tries to get the right answer.
Dr. Malik and Mr. Mori are exploring ways of improving the performance of their program on Gimpy that will also improve their general technique of recognizing objects in a cluttered background.
''We want to keep working on this in a principled way so we can use the same technique on an outdoor scene with buildings, trees and cars,'' Dr. Malik said.
The general technique, he said, will have many practical applications, like automated recognition of military targets or detection of trademark infringements on the Internet.
Meanwhile, Yahoo will have to install a new Captcha that is resistant to Dr. Mori's program. This task will fall to Dr. Manber's successor, since Dr. Manber moved to a new position last month as chief algorithms officer for Amazon.com. There, he said, he plans to continue his collaborations with academic researchers.
''I'd love to foster more cooperation between industry and academica,'' he said. ''It's great for everybody.''
No comments:
Post a Comment