From: Wade T.Smith (wade_smith@harvard.edu)
Date: Thu 12 Dec 2002 - 03:23:56 GMT
Human or Computer? Take This Test
By SARA ROBINSON
http://www.nytimes.com/2002/12/10/science/physical/10COMP.html?pagewanted=
print&position=top
As chief scientist of the Internet portal Yahoo, Dr. Udi Manber had a
profound problem: how to differentiate human intelligence from that of a
machine.
His concern was more than academic. Rogue computer programs masquerading
as teenagers were infiltrating Yahoo chat rooms, collecting personal
information or posting links to Web sites promoting company products.
Spam companies were creating havoc by writing programs that swiftly
registered for hundreds of free Yahoo e-mail accounts then used them for
bulk mailings.
"What we needed," said Dr. Manber, "was a simple way of telling a human
user from a computer program."
So, in a September 2000 conference call, Dr. Manber discussed the
problem with a group of computer science researchers at Carnegie Mellon
University. The result was a long-term project that is just now
beginning to bear fruit.
The roots of Dr. Manber's philosophical conundrum lay in a paper written
50 years earlier by the mathematician Dr. Alan Turing, who imagined a
game in which a human interrogator was connected electronically to a
human and a computer in the next room. The interrogator's task was to
pose a series of questions that determined which of the other
participants was the human. The human helped him, while the computer did
its best to thwart him.
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."
Copyright The New York Times Company
===============================================================
This was distributed via the memetics list associated with the
Journal of Memetics - Evolutionary Models of Information Transmission
For information about the journal and the list (e.g. unsubscribing)
see: http://www.cpm.mmu.ac.uk/jom-emit
This archive was generated by hypermail 2.1.5 : Thu 12 Dec 2002 - 03:26:10 GMT