David Molnar (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} ephermata) wrote,@ 2005-12-20 21:14:00 |
|
Human oracles
A while back, a friend asked me if human beings are "Turing machines or limited function machines?"
I decided to interpret "limited function machines" as asking whether human beings are finite automata or pushdown automata. As it turns out, we have some evidence that humans are not.
In particular, Swiss-German has language constructs that imply its speakers can recognize the language
{a^n b^n c^n d^n | n in N}, but this language is not context-free. So whatever kind of machine Swiss-German speakers "are," they can't be pushdown automata, because Swiss-German speakers decide a language pushdown automata cannot.
The original paper is
Stuart M. Shieber , 'Evidence against the context-freeness of natural language ', Linguistics and Philosophy , pp. 333-343 , 1985.
(Edit: Thanks to the anonymous commenter for catching an error in the earlier reference and definition of the language.)
There's an online resource explaining it at http://ucrel.lancs.ac.uk/acl/J/J84/J
So this leads to a question - what exactly is the class of problems that can be solved efficiently (or, if you like, the class of languages that can be efficiently decided) by humans?
Ellen Ullman has an essay in the _Best American Science Writing 2005_ that also touches on this question. In "Dining With Robots," she talks about how her 1979 introductory programming class used baking a cake as an example of a recipe, and by extension, a kind of computer program. Then later, she contrasts this with an actual recipie out of _The Art of French Cooking_, Volume I, by Julia Child.
Ullman points out that in the real recipe book, there are many terms that depend implicitly on human experience, such as what a "nice brown" or a "rosy center" mean in the context of cooking beef. The rest of the essay explains an argument that artificial intelligence is difficult because humans just have so much tacit, difficult-to-articulate knowledge.
After reading the essay, I wondered if we could somehow have humans help out with robotic cooking. After all, I've seen The ESP Game and PeekaBoom, in which humans collaborate to solve image recognition problems that are difficult for computers. I've solved my fair share of CAPTCHAs to get free stuff or make blog posts, and as far as I can tell, most of them weren't doing anything useful. Besides slow me down, that is. So why not build a human-assisted cooking machine? Instead of typing in meaningless words to get free stuff, now you have to determine from a photograph whether a cut of beef has a rosy center.
Of course, this is a bit of a pipe dream. Still, a friend of mine recently pointed me to a service that makes it slightly more possible. Amazon's Mechanical Turk allows you to write applications that make calls to humans. You pay the human a certain amount of money (usually a few cents), and Amazon collects a percentage. In return, Amazon provides the API, puts up the web site, and advertises to potential problem-solvers.
www.mturk.com
What will be really interesting is if we can get people on cell phones to use something like the site. Then everyone bored on a bus or in a car or elsewhere might be willing to help out.
There's some discussion of how you can tackle the security issues that come up. The ESP Game and Peekaboom handle this in part by recognizing that non-colluding cheaters usually won't pick the same wrong answer. For an overview of that work, see Luis von Ahn's web page at
http://www.cs.cmu.edu/~biglou/resea
There's also a paper written by some colleagues of mine at DoCoMo
"Secure Distributed Human Computation"
C. Gentry, Z. Ramzan, S. Stubblebine
www.docomolabs-usa.com/pdf/PS2004-032.pd
Finally, there's even applications of human input to search problems. (Just in case you thought this was all about language and cooking!) Michael Mitzenmacher and others have done work on human-guided search strategies. You can see some of his papers here:
http://www.eecs.harvard.edu/~michaelm/L
Probably there is more such work. Anyone have good links?
Two things strike me as interesting about this type of work. First, it's an implementation of the old idea of an oracle Turing Machine with a new type of oracle. Instead of looking at an NP oracle or a carefully crafted oracle, we use a human. Second, we are still in the stages where the formalization of the problem is being worked out; this gives us a chance to see how different formalizations reflect different approaches. That, in turn, gives insight into one of the overarching concerns of computer science: how to represent and reason about problems.
A while back, a friend asked me if human beings are "Turing machines or limited function machines?"
I decided to interpret "limited function machines" as asking whether human beings are finite automata or pushdown automata. As it turns out, we have some evidence that humans are not.
In particular, Swiss-German has language constructs that imply its speakers can recognize the language
{a^n b^n c^n d^n | n in N}, but this language is not context-free. So whatever kind of machine Swiss-German speakers "are," they can't be pushdown automata, because Swiss-German speakers decide a language pushdown automata cannot.
The original paper is
Stuart M. Shieber , 'Evidence against the context-freeness of natural language ', Linguistics and Philosophy , pp. 333-343 , 1985.
(Edit: Thanks to the anonymous commenter for catching an error in the earlier reference and definition of the language.)
There's an online resource explaining it at http://ucrel.lancs.ac.uk/acl/J/J84/J
So this leads to a question - what exactly is the class of problems that can be solved efficiently (or, if you like, the class of languages that can be efficiently decided) by humans?
Ellen Ullman has an essay in the _Best American Science Writing 2005_ that also touches on this question. In "Dining With Robots," she talks about how her 1979 introductory programming class used baking a cake as an example of a recipe, and by extension, a kind of computer program. Then later, she contrasts this with an actual recipie out of _The Art of French Cooking_, Volume I, by Julia Child.
Ullman points out that in the real recipe book, there are many terms that depend implicitly on human experience, such as what a "nice brown" or a "rosy center" mean in the context of cooking beef. The rest of the essay explains an argument that artificial intelligence is difficult because humans just have so much tacit, difficult-to-articulate knowledge.
After reading the essay, I wondered if we could somehow have humans help out with robotic cooking. After all, I've seen The ESP Game and PeekaBoom, in which humans collaborate to solve image recognition problems that are difficult for computers. I've solved my fair share of CAPTCHAs to get free stuff or make blog posts, and as far as I can tell, most of them weren't doing anything useful. Besides slow me down, that is. So why not build a human-assisted cooking machine? Instead of typing in meaningless words to get free stuff, now you have to determine from a photograph whether a cut of beef has a rosy center.
Of course, this is a bit of a pipe dream. Still, a friend of mine recently pointed me to a service that makes it slightly more possible. Amazon's Mechanical Turk allows you to write applications that make calls to humans. You pay the human a certain amount of money (usually a few cents), and Amazon collects a percentage. In return, Amazon provides the API, puts up the web site, and advertises to potential problem-solvers.
www.mturk.com
What will be really interesting is if we can get people on cell phones to use something like the site. Then everyone bored on a bus or in a car or elsewhere might be willing to help out.
There's some discussion of how you can tackle the security issues that come up. The ESP Game and Peekaboom handle this in part by recognizing that non-colluding cheaters usually won't pick the same wrong answer. For an overview of that work, see Luis von Ahn's web page at
http://www.cs.cmu.edu/~biglou/resea
There's also a paper written by some colleagues of mine at DoCoMo
"Secure Distributed Human Computation"
C. Gentry, Z. Ramzan, S. Stubblebine
www.docomolabs-usa.com/pdf/PS2004-032.pd
Finally, there's even applications of human input to search problems. (Just in case you thought this was all about language and cooking!) Michael Mitzenmacher and others have done work on human-guided search strategies. You can see some of his papers here:
http://www.eecs.harvard.edu/~michaelm/L
Probably there is more such work. Anyone have good links?
Two things strike me as interesting about this type of work. First, it's an implementation of the old idea of an oracle Turing Machine with a new type of oracle. Instead of looking at an NP oracle or a carefully crafted oracle, we use a human. Second, we are still in the stages where the formalization of the problem is being worked out; this gives us a chance to see how different formalizations reflect different approaches. That, in turn, gives insight into one of the overarching concerns of computer science: how to represent and reason about problems.
