>Human or Computer? Take This Test
>NYT December 10, 2002
>By SARA ROBINSON
>
>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."
>
>http://www.nytimes.com/2002/12/10/science/physical/10COMP.html


VICUG-L is the Visually Impaired Computer User Group List.
To join or leave the list, send a message to
[log in to unmask]  In the body of the message, simply type
"subscribe vicug-l" or "unsubscribe vicug-l" without the quotations.
 VICUG-L is archived on the World Wide Web at
http://maelstrom.stjohns.edu/archives/vicug-l.html