Top Site Map

Deadline for HCOMP 2011 extended: Submission due on April 29th

2011-04-15T17:04:00.000-07:00

Due to a significant number of requests, and a number of conflicts with other conferences and workshops, we decided to extend the submission deadline for HCOMP 2011. The new deadline is April 29th.

If you want to know more, you can see the call for papers and workshop announcement.

Video from NYC Crowdsourcing Meetup

2011-04-15T08:29:00.000-07:00

On April 13th, we hosted at NYU Stern the NYC Crowdsourcing Meetup. For those who missed it, you can now download an audio-only podcast version or watch the video from the event together with the slide presentations:

The speakers at the event:

John Horton, Staff Economist of oDesk. John talked on issues of matching employers with contractors in an online marketplace. Specifically he described mechanisms for forcing contractors to give an accurate description of their skills, avoiding issues of over-tagging a profile with irrelevant keywords or over-claiming qualifications.
Amanda Michel, Director of Distributed Reporting at ProPublica. Amanda talked about the crowdsourcing efforts of ProPublica, and how they use the crowd to enable better journalistic investigation of topics they are researching. At some point during the presentation, Amanda quoted from one of their studies "ProPublica pulled a random sample of 520 of the roughly 6,000 approved projects to examine stimulus progress around the country. That sample is large enough to estimate national patterns with a margin of error of plus or minus 4.5 percentage points." Honestly, a tear came down my eye when I compared that with the corresponding practices of Greek newsrooms that typically operate with samples of n=1 or n=0.
Todd Carter, CEO and Co-Founder of Tagasauris. Todd described Tagasauris, a system for annotating and tagging media files. Todd described the annotation effort for Magnum Photos, (sample photos in their collection include the Afghan refugee girl, Merilyn Monroe on top of the vent, and many other iconic photos). A highlight was the discovery of a "lost" set of images from the shooting of the movie "American Graffiti". These images, shot by Dennis Stock, were in the Magnum archive but were not possible to find as they were lacking any tags and description. After the annotation effort from Tagasauris, the lost set of photos were re-discovered.
Panos Ipeirotis, representing AdSafe Media. I talked about our efforts in AdSafe, on using crowdsourcing in order to create machine learning systems for classifying web pages.

It was a lively and successful event. If there is enough interest and participants, I think this is an event that can be repeated periodically.

NYC Crowdsourcing Meetup: April 13th, 6.30pm

2011-04-10T08:16:00.000-07:00

Join us for its first ever New York City Crowdsourcing meetup hosted by NYU and sponsored by CrowdFlower:

When: Wednesday, April 13, 6:30-9pm
Where: NYU Stern School of Business, Room M3-110, 44 West 4th Street, New York, NY 10012

Pizza, beer, and thought provoking conversation about the future of work. Come listen, ask, and debate how crowdsourcing is changing everything from philanthropy and urban planing to creative design and enterprise solutions.

Confirmed Speakers:

Lukas Biewald, CEO and Co-Founder of CrowdFlower
Todd Carter, CEO and Co-Founder of Tagasauris
John Horton, Chief Economist of oDesk
Panos Ipeirotis, Associate Professor at Stern School of Business, NYU
Amanda Michel, Director of Distributed Reporting at ProPublica
Bartek Ringwelski, CEO and Co-Founder of SkillSlate
Trebor Scholz, Associate Professor in Media & Culture at The New School University

Tutorial on Crowdsourcing and Human Computation

2011-04-05T13:08:00.000-07:00

Last week, together with Praveen Paritosh from Google, we presented a 6-hour tutorial at the WWW 2011 conference, on crowdsourcing and human computation. The title of the tutorial was "Managing Crowdsourced Human Computation".

My slides from the tutorial are available now on Slideshare:

Once Praveen gets clearance from Google, we will post his slides as well.

Judging from all the crap that I get to review lately, I was getting pessimistic about the quality of research on crowdsourcing. However, while preparing the tutorial, I realized the massive amount of high-quality research that is being published. We had 6 hours for the tutorial, and we did not have enough time to cover many really interesting papers. I had to refer people to other, more "specialized" tutorials (e.g., on linguistic annotation, on search relevance, etc), which I mention at the end of the slides.

Special thanks go to my PhD student, Jing Wang, for her slides on market design, Matt Lease for his excellent list of pointers for crowdsourcing resources, Omar Alonso for his tutorial slides on crowdsourcing for search relevance, Alex Quinn and Ben Bederson for their survey on human computation, and Winter Mason for sharing his slides from his CSDM keynote. And all the other researchers for making crowdsourcing and human computation an exciting field for research!

Last but not least: Luis von Ahn with Edith Law will be presenting another tutorial on human computation during AAAI, in San Francisco on August 8th. We will be organizing the HCOMP 2011 workshop in conjunction with AAAI as well! The submission deadline is April 22nd! Do not forget to submit!

An ingenious application of crowdsourcing: Fix reviews' grammar, improve sales

2011-04-05T05:41:00.000-07:00

I have been doing research on the economic impact of product reviews for a while. One thing that we have noticed is that the quality of the reviews can have an impact on product sales, independently of the polarity of the review.

High-quality reviews improve product sales

A well-written review tends to inspire confidence about the product, even if the review is negative. Typically such reviews are perceived as objective and thorough. So, if we have a high-quality, but negative, review this may serve as a guarantee that the negative aspects of the product are not that bad after all. For example, a negative review such as "horrible battery life... in my tests battery lasts barely longer than 24 hours..." may be perceived as positive by other customers that consider a 24-hour batter life to be more than sufficient.

In our recent (award-winning) WWW2011 paper "Towards a Theory Model for Product Search", we noticed that demand for a hotel increases if the online reviews on TripAdvisor and Travelocity are well-written, without spelling errors; this holds no matter if the review is positive or negative. In our TKDE paper "Estimating the Helpfulness and Economic Impact of Product Reviews: Mining Text and Reviewer Characteristics", we observed similar trends for products sold and reviewed on Amazon.com.

And what can we do knowing this?

Being in a business school, these findings were considered informative but not deeply interesting. Do not forget, the focus of researchers in business schools is centered on causality and on policy-making. Yes, we know that it is important for the reviews to be well-written and informative if we want the product to sell well. But if we cannot do anything about this, it is not deeply interesting. It is almost like knowing that during the cold months the demand for summer resorts drops!

But here comes the twist...

The crowdsourcing solution

Last week, over drinks during the WWW conference, I learned about a fascinating application of crowdsourcing that attacked exactly this issue.

An online retailer noticed that indeed products with high-quality reviews are selling well. So, they decided to take action. They used Amazon Mechanical Turk to improve the quality of its reviews. Using the Find-Fix-Verify pattern, they used Mechanical Turk to examine a few millions of product reviews. (Here are the archived versions of the HITs: Find, Fix, Verify... and if you have not figured out the firm name by now, it is Zappos :-) ) For the reviews with mistakes, they fixed the spelling and grammar errors! Thus they effectively improved the quality of the reviews on their website. And, correspondingly, they improved the demand for their products!

While I do not know the exact revenue improvement, I was told that it was substantial. Given that the e-tailer spent at least 10 cents per review, and that they examined approximately 5 million reviews, this is an expense of a few hundred thousand dollars. (My archive on MTurk-Tracker kind of confirms these numbers.) So, the expected revenue improvement should have been at least a few million dollars!

Ethical? I would say yes. Notice that they are not fixing the polarity or the content of the reviews. They just change the language to be correct and error-free. I can see the counter-argument that the writing style allows us to judge if the review is serious or not. So, artificially improving the writing style may be considered as interference with the perceived objectivity of the user-generated reviews.

But is it ingenious? Yes! It is one of these solutions that is sitting in front of you but you just cannot see it. And this is what makes it ingenious.

Crowdsourcing goes professional: The rise of the verticals

2011-03-22T12:25:00.000-07:00

Over the last few months, I see a trend. Instead of letting end-users interact directly with the crowd (e.g., on Mechanical Turk), we see a rise of the number of solutions that target a very specific vertical.

CastingWords: Audio transcription
SpeakerText: Video transcription
Serv.io Translate: Translation (by CloudCrowd)
Serv.io Edit: Proofreading (by CloudCrowd)
CrowdFlower Business Listing Verification
CrowdFlower Search Relevance
CrowdFlower Product Categorization
BetterOCR: Improving Optical Character Recognition
Tagasauris: Photo tagging
MediaPiston: Targeted content generation

Add services like Trada for crowd-optimizing paid advertising campaigns, uTest for crowd-testing software applications, etc. and you will see that for most crowd applications there is now a professionally developed crowd-app.

Why do we see these efforts? This is the time that most people realize that crowdsourcing is not that simple. Using Mechanical Turk directly is a very costly enterprise and cannot be done effectively by amateurs: The interface needs to be professionally designed, quality control needs to be done intelligently, and the crowd needs to be managed in the same way that any employee is managed. Most companies do not have time or the resources to invest in such solutions. So, we see the rise of such verticals that address the most common tasks that were accomplished on Mechanical Turk.

(Interestingly enough, if I remember correctly, the rise of vertical solutions was also a phase during web search. In the period in which AltaVista started being spammed and full of irrelevant results, we saw the rise of topic-specific search engines that were trying to eliminate the problems of polysemy by letting you search only for web pages within a given topic.)

For me, this is the signal that crowdsourcing will stop being the fad of the day. Amateurish solutions will be shunned, and most people will find it cheaper to just use the services of the verticals above. Saying "oh, I paid just $[add offensively low dollar amount] to do [add trivial task] on Mechanical Turk" will stop being a novelty and people will just point to a company that does the same thing professionally and in a large scale.

This also means that the crowdsourcing space will become increasingly "boring." All the low-hanging fruits will be gone. Only people that are willing to invest time and effort in the long term will get into the space.

And it will be the time that we will get to separate the wheat from the chaff.

Uncovering an advertising fraud scheme. Or "the Internet is for porn"

2011-03-16T10:50:00.000-07:00

You have heard about fraud and online advertising. You may have seen the Wall Street Journal video "Porn Sites Scam Advertisers", or even read the story at today's Wall Street Journal about "Off Screen, Porn Sites Trick Advertisers" (Hint: to avoid the WSJ paywall, search the title of the article through Google News and click from there, to read the full article).

Since I am intimately familiar with the story covered by WSJ (i.e., I was part of the team at AdSafe that uncovered it), I thought it would be also good to cover the technical aspects in more detail, uncovering the way in which this advertising fraud scheme operated.

It is long but (I think) interesting. It is a story of a one-man-making-a-million-dollar-per-month fraud scheme. It shows how a moderately sophisticated advertising fraud scheme can generate very significant monetary benefits for the fraudster: Profits of millions of dollars per year.

If you want to skip the technical sleuthing details, you can skip directly to the overall picture and the discussion.

Disclaimer: In the story below, I will only mention by name the sites performing the fraudulent activities. All the brand names that you see are just for illustration purposes. They are not the ones affected by this case of fraud. Also remember that this is a personal blog. The views and opinions that I express here are my own and do not necessarily represent the views of AdSafe or the views of New York University.

The erroneous classifier

It all started while working at AdSafe. For those not familiar with AdSafe: The role of AdSafe is to provide brand protection services to online advertisers. In plain English, AdSafe analyzes website content and can block ads from appearing on individual web pages with content inappropriate for a brand. Porn, hate speech, gambling, celebrity gossip, torrents, are among the many categories that we detect.

On a nice Monday, the data science team gets the notification: The web page classifier was detecting a large number of porn web pages within legitimate, clean, big-brand-name websites. Think of websites such as BabyCenter, MSN MoneyCentral, HGTV, and so on. These sites would never have anything racy in their pages. However, we could see them being classified as having hard-core porn!

Why do we detect porn in clean sites? None of the pages within the sites contained anything offensive. No porn, no offensive material. Nothing. The website was clean as it gets. What was going on?

The invisible iframe hosting

The lifesaver was a technique developed at AdSafe: The key to the solution was the ability to read the address of the top frame that was hosting the ad(*). We were detecting porn because the ads that were supposed to appear within a "clean publisher" site were appearing within the frame of a porn website. Think of HGTV as an illustrative, but not the real, example of such a "clean publisher."

(*) For the technically curious: reading the address of the top frame is a challenging problem. For security reasons, browsers do not allow cross-domain scripting. So, it is not possible to just call the "top" object and read its properties. We have a proprietary solution for this.

By using this technique, we got our explanation: The HGTV website was appearing within an iframe of a porn website. In our case, the porn website was www.hqtubevideos.com.

WTF? This made no sense. Why would the porn website display HGTV (and the associated ads) within an iframe? Why would the porn site generate this "invisible" traffic towards HGTV? Just so that HGTV would get paid for the CPM ads? Or was the porn site trying to decrease the clickthrough rate of HGTV and ruin the performance the CPC campaigns? Did the porn website love HGTV so much and it was trying to increase its traffic? No way. Did HGTV employ a porn website to increase its traffic? No way, either.

Made no sense whatsoever.

Checking the structure of the porn website

So, we decided to investigate. Let's see what is going on. First, we go and see the HTML source of www.hqtubevideos.com/play.html that was the top frame what we were detecting. Here is the source:

The highlighted part shows an interesting redirection. We go to the www.hqtubevideos.com/index.php, but with the parameter ?x=1 at the end.

Loading the page www.hqtubevideos.com/index.php without this parameter loads a "vanilla" porn website. A few semi-suspicious attempts to add the website in the bookmarks in the beginning. Then porn pictures and links to affiliate sites. Plenty of porn but nothing to set an alarm. So far, so good.

They key, though, is this parameter ?x=1. Loading the www.hqtubevideos.com/index.php?x=1 we see a key part added in the website, at the very bottom. Here is the corresponding source.

Aha! A 0x0 iframe, loading the following URLs:

The first URL seems to be loading some randomized hashid. Ignore.

The second URL, www.hqtubevideos.com/counter2.php, is a little bit more interesting and puzzling:

What is going on? Why would a porn site link to these domains? What is the connection?

The parked domains

We started by doing a whois to figure out the ownership of this domains. Unfortunately, the registration information for the hqtubevideos is private and protected. However, the registration info for all the other domains is available. Not surprisingly, we see a common ownership for all these seven domains:

Registrant:
Thomas Schneider
519 S. York Road
Dillsburg, Pennsylvania 17019
United States
Registered through: GoDaddy.com, Inc. (http://www.godaddy.com)
Domain Name: RELAXHEALTH.COM
Created on: 11-Mar-09
Expires on: 11-Mar-12
Last Updated on: 10-Jan-11
Administrative Contact:
Schneider, Thomas garret.and@gmail.com
519 S. York Road
Dillsburg, Pennsylvania 17019
United States
7174327575 Fax --
Technical Contact:
Schneider, Thomas garret.and@gmail.com
519 S. York Road
Dillsburg, Pennsylvania 17019
United States
7174327575 Fax --
Domain servers in listed order:
NS1.ROLENEWS.COM
NS2.ROLENEWS.COM

Now we start seeing something being uncovered. Would this guy, Thomas Schneider, be behind this? Too easy to be true. We went and did a reverse whois to find other domains that contained the email garret.and@gmail.com. And here we are: The email is associated with the registration of 89 other domains, which are registered under a variety of last names, but all listing garret.and@gmail.com as the contact email:

aboutclimax.com
aboutclinical.com
aboutcouples.com
abouterectile.com
abouterection.com
achieveday.com
achievedrugs.com
afterdeaths.com
afterdrugs.com
associatedmagazine.com
atlantea.org
baldnesshealth.com
basehealth.com
becomeerect.com
begineducate.com
behaviordesire.com
beingdizzy.com
bestcialis.com
bestclimax.com
bigcouples.com
bodychemical.com
bodyclimax.com
bodyday.com
bundlehealth.com
calnam.com
cancerdamage.com
carecouples.com
carloschongdds.com
ceaifa.com
cialisc.com
cigarettesfinder.com
clubofheads.com
coacaz.com
college-grants1.com
college-scholarships1.com
collinshall.com
conditionnews.com
couponvi.com
criminaldefenseattorneys2.com
criminaldefenselawfirms1.com
detailedhealth.com
drinkershealth.com
drinkingmagazine.com
eurovision-2008.com
experiencemedical.com
fantasiesmagazine.com
fearhealth.com
gendergibe.org
government-grants1.org
groupovienna.net
hardballdollars.com
hawgsandpaws.org
impotencemagazine.com
letscurepeyronies.com
levitrav.com
medicationmagazine.com
moorehabitat.org
nighttimemagazine.com
ownmeds.com
panimarock.com
playmeds.com
powerfulselling.com
printcoupons1.com
propeciav.com
relationshipmeds.com
relaxhealth.com
rml-inc.com
rxvis.com
savewhalompark.com
sex-tvs.com
shopwizz.biz
signbysign.com
steve-magic.com
styleandmore.net
syncsql.com
takemedical.com
taylor-training.com
testosteronehealth.com
thedongman.com
traumamedical.com
twohealth.com
viagracomp.com
viagraeds.com
viagramagazine.com
viagravi.com
washealth.com
waymagazine.com
weightmedical.com
worldcuplive1.com

Let's see what we have so far: The owner of a porn domain loads in a set of 0x0 iframes, a set of other websites, all operated by the same owner. But still, no clear motivation. Also, the connection with the publishers that we checked remains elusive.

Re-directions within the parked domains

Now, let's see what is going on within these URL calls, such as www.takemedical.com/go_with_post.php. Here is the HTML source of one of those URLs:

Interesting. Another redirection. The site automatically submits a search form, searching for the term "hihijiji". Loading the page in the browser with the GET method (as opposed to the POST method indicated in the form), takes us to the normal page of a parked domain.

But let's submit with the POST method:

curl www.takemedical.com/search.php -d token=hihijiji

Ha! The result is different:

<iframe frameborder="No" height="1" src="index2.php" width="1"> </iframe>

We uncovered a hidden URL. This is the point where everything will start falling into place.

Re-directions and generating click fraud with normal click patterns

Within this hidden URL is where all the interesting things are happening! Let's load www.takemedical.com/index2.php and see the network activity. (In Chrome, go to Tools, Developer Tools, and then to the Network tab.). Here is the screenshot:

Indeed, here is where all the action is happening: These innocent sounding parked domain load all sorts of ad sites, and then "clicks" on the ads. By click, we do not mean any actual click. Instead the site loads the URL in the ad, that is typically a redirection to the ad server, which then redirects to the advertised URL. After this "click" within the iframe we finally have the publisher website (the "HGTV" that we mentioned before)!

Interestingly enough, the click fraud was very well-done: It was not loading all the time the same website. Sometimes it was mevio, other times it was tremor, other times bodyarchitect.tv, and so on. And once we have been redirected enough times from the same IP address, the final redirect was going to find.fm, to execute a straight-forward search. Clever! Engage in fraud, but be careful not to trigger any alarms.

Also, notice that the traffic patterns for the clicks are not bot-generated. These are actual users. With real and different web browsers. Different IP addresses. Different times of the day, following the usual traffic patterns per region. Good job: these click-fraud patterns are the least likely to be caught as they have patterns very similar to normal traffic.

For those interested in the details, here is the set of screenshots with the redirects:

Update (3/17/2011): Initially, I did not want to post screenshots with the actual ad networks that were being defrauded, as it was not my intention to involve them in the story. However, since they were mentioned in the Wall Street Journal article already, and they have taken measures against this, I am posting them now. Here are the screenshots with ad loads from the networks. Warning: NSFW.

The role of parked domains: Laundering traffic

At this point, we now know how this person makes money. Clearly, there is click-fraud: the scammer is employing click-fraud services to click on the pay-per-click ads "displayed" in his parked domains. If some of the ads are also pay-per-impression, he may also get paid for these invisible impressions that happen within the 0x0 iframe.

Why the parked domains though? Why not doing the same directly within the porn site? The answer is simple: Traffic laundering.

What do I mean by "traffic laundering"? First, the ad networks are unlikely to place many ads within a porn site. On the other hand, they have ad-placement services for parked domains. Second, the publishers that get the traffic from the parked domains see in the referral URLs some legitimately-sounding domain names, not a porn site. Even if they go and check the site, they will only see an empty site full of ads. Nothing too suspicious. Hats off to the scammer. Clever scheme.

You think we are done? No. There is one more piece in the puzzle. How does the scammer attract visitors to the porn site?

Generating traffic through an adult traffic exchange

The other interesting part: The porn website does not really contain porn! There are a few images but most of the links are to other porn website that actually host the video. In other words, the scammer does not even pay the cost of hosting porn!

However, according to QuantCast and Compete, the website has a pretty significant number of unique visitors per month. Here is the traffic over the last year:

This porn website gets 500K to 1M unique visitors per month! That is a lot of traffic for a website without any real content! So, how does the guy get all the traffic?

The answer surprised me. Apparently, there is an exchange (yes, my dear readers, an exchange!) for buying and selling adult traffic! Its name: TrafficHolder.com

Do you want to buy traffic for people interested in midget sex? The price is $2.94 per thousand visitors. Interested in latex? The cost is $2.54 per thousand visitors. Interested in HD video? $3.54 per thousand visitors. (The running price catalog and the available traffic volume is available at http://www.trafficholder.com/cgi-bin/traffic/manager/buying100.cgi)

How do the porn sites sell traffic to each other? Through pop-ups, pop-unders, by causing the first click to the website to redirect to the buyer's site. The term for this traffic is "skimmed traffic"

Following the trail, we figured out the source of the traffic for hqtubevideos.com: It was coming from the (very popular, apparently) website www.pornoxo.com. The reports from QuantCast and Compete confirm that PornoXo gets approximately 1 million unique visitors per month. If you visit the PornoXo.com website, you will see that the first click will create a pop-under that loads the page hqtubevideos.com/play.html. This is the page responsible for all the fraud that I described above.

Based on the exchange prices and the visitorship at PornoXo, this traffic has a cost of $3K/month for hqtubevideos.com, which is significant. So, we need to figure out how the scammer recovers this cost.

How much money are we talking about?

So, the key question now: How much money the hqtubevideos.com generates through the scheme? To get a feeling of how much fraud is going on, please do the following:

Open Chrome
Open the options, and then Tools, then Developer Tools. This will load the monitoring tool.
Switch to the "Network" tab
Visit http://www.hqtubevideos.com/play.html and see what is being loaded in the background (my own counting was approximately 1 ad loading per 10 seconds)

Let's do some back-of-the-envelope, very conservative, approximations:

The site gets 500K-1M visitors per month
The cost of this traffic is approximately $1.5K to $3K per month
Each unique visit loads 7 sites, which then generate clicks. Let's assume that there is no reload of the invisible sites, to keep the estimates low.

Assuming 500K visitors and that just one click out of the seven sites goes through, this is 500K clicks per month (low estimate)
Assuming 1M visitors and that all clicks, in all 7 sites, go through, this is 7M clicks per month (high estimate)

The a low-end estimate for CPC click costs is 30 cents, out of which we can assume that the scammer gets, say, 10 cents.
This generates a total income of $50K to $700K per month
The scheme is running for 8 months now, generating total revenue of $400K to $5M so far. (And you thought that investment bankers were getting paid a lot...)

Notice that these approximations assume that the site only generates the direct clicks discussed above. You will notice that there is no end in the loading of ads, if you leave the website open for a while. Given that the site visitors come from PornoXo, there is a good chance they will keep watching the porn video at PornoXo, leaving hqtubevideos to load the ads in the background.

But even with the modest estimates listed above, we are talking about a business that generates tens of thousands of dollars, with really minimum requirements. This is a scheme that a single person can set up in a week...

Overall picture

Trying to put all pieces together, I created the following graphical summary to see what is going on:

Let's follow the flow of the users:

Scammer buys user traffic from PornoXo.com and sends it to HQTubeVideos.
HQTubeVideos loads, in invisible iframes, some parked domains with innocent-sounding names (relaxhealth.com, etc)
In the parked domains, ad networks serve display and PPC ads.
The click-fraud sites click on the ads that appear within the parked domains.
The legitimate publishers gets invisible/fraudulent traffic through the (fraudulently) clicked ads from parked domains.
Brand advertisers place their ad on the websites of the legitimate publishers, which in reality appear within the (invisible) iframe of HQTubeVideos.
AdSafe detects the attempted placement within the porn website, and prevents the ads of the brand publisher from appearing in the legitimate website, which is hosted within the invisible frame of the porn site.

Notice how nicely orchestrated is the whole scheme: The parked domains "launder" the porn traffic. The ad networks place the ads in some legitimately-sounding parked domains, not in a porn site. The publishers get traffic from innocent domains such as RelaxHealth, not from porn sites. The porn site loads a variety of publishers, distributing the fraud across many publishers and many advertisers.

Who has the incentives to fight this?

And now let's see who has the incentives to fight this. It is fraud, right? But I think it is well-executed type of fraud. It targets and defrauds the player that has the least incentives to fight the scam.

Who is affected? Let's follow the money:

The big brand advertisers (Continental, Coca Cola, Verizon, Vonage,...) pay the publishers and the ad networks for running their campaigns.
The publishers pay the ad network and the scammer for the fraudulent clicks.
The scammer pays PornoXo and TrafficHolder for the traffic.

The ad networks see clicks on their ads, they get paid, so not much to worry about. They would worry if their advertisers were not happy. But here we have a piece of genius:

The scammer did not target sites that would measure conversions or cost-per-acquisition. Instead, the scammer was targeting mainly sites that sell pay-per-impression ads and video ads. If the publishers display CPM ads paid by impression, any traffic is good, all impressions count. It is not an accident that the scammer targets publishers with video content, and plenty of pay-per-impression video ads. The publishers have no reason to worry if they get traffic and the cost-per-visit is low.

Effectively, the only one hurt in this chain are the big brand advertisers, who feed the rest of the advertising chain.

Do the big brands care about this type of fraud? Yes and no, but not really deeply. Yes, they pay for some "invisible impressions". But this is a marketing campaign. In any case, not all marketing attempts are successful. Do all readers of Economist look at the printed ads? Hardly. Do all web users pay attention to the banner ads? I do not think so. Invisible ads are just one of the things that make advertising a little bit more expensive and harder. Consider it part of the cost of doing business. In any case, compared to the overall marketing budget of these behemoths, the cost of such fraud is peanuts.

The big brands do not want their brand to be hurt. If the ads do not appear in places inappropriate for the brand, things are fine. Fighting the fraud publicly? This will just associate the brand with fraud. No marketing department wants that.

Note also that the fraudster does not target a single publisher, does not target a single advertiser. The damage is amortized so nicely that nobody feels that it is a big deal. A mastery of the long tail...

Well, but what if fraud is big? What if big bucks are wasted? Maybe some newspapers would like to investigate. Let's break the big story. What would be the effect? Publicizing that a significant source of their income (online advertising) is a dangerous thing, full of fraud? Who would like to shoot himself in the foot?

Fraud as (harmless?) parasite

Really. Genius. Defraud a lot of rich guys a little bit, and ensure that nobody has the incentives to really fight and chase the fraud.

The guy essentially realized that this type of fraud is really behaving like a parasite within a much bigger ecosystem. And it is a parasite that is so costly to remove that it makes sense to leave it there. As long as the parasite does not annoy the host too much, things will be fine.

Only if fraud becomes really big there will be the real incentive to fight advertising fraud. Until then, you know how to make $500K/month...

Do Mechanical Turk workers lie about their location?

2011-03-14T16:41:00.000-07:00

A few weeks back, Dahn Tamir graciously allowed me to take a peek at the data that he has been gathering about this workers on Mechanical Turk. He has assigned tasks over time to more than 50,000 workers on Mechanical Turk, so I consider his data to be one of the most representative samples of workers.

One of the nice tasks that he has been running is a simple HIT in which he asks workers to report their location. At the same time, in this task, Dahn was recording the IP of the worker. Why the task was nice? Because there is absolutely no incentive for the workers to be truthful. The submission will be accepted and paid no matter what. In a sense, it is a test that check if workers will be truthful in cases where it is not possible to check their accuracy.

So, we used this test to check how sincere are the workers: We can simply geocode the IP address and find out the actual location of the worker. (With some degree of error, but good enough for approximation purposes.) For the workers that reported to be based in the US (approximately 22,000 workers), the HIT was asking for the zip code of the worker, making it easy to assign an approximate long/lat location.

To measure how accurately the worker report their location, we measured the distance between the location of the IP and the location of the zip code. The plot below shows the distribution of the differences:

As you can see, most of the workers were pretty truthful about their location. The difference in distance was less than 10 miles for more than 60% of the workers: this difference can be easily explained by the limited accuracy of the geocoding API's and by the approximation of using zipcode locations.

Of course, the flip side of the coin is that a significant fraction of the workers were essentially lying about their location: For 10% of the workers (i.e., ~2250 of them) the IP address was more than 100 miles away from the reported zip code. For 2% of the workers (i.e., ~500 workers) the distance was more than 1000 miles away.

The biggest lier? A worker from Chennai, India who reported a zip code corresponding to Tampa in Florida. The IP was a cool 9500 miles away from the reported location!

The Road to Serfdom, ACM Edition

2011-03-10T22:01:00.000-08:00

<rant>

A couple of days back, I got the following email from ACM:

Dear Moderator/Chairs,

This is being sent to everyone with the chairs cc'd as the last and final requeset for the eform below to be completed or your panel overview abstract will be removed from the WWW 2011 Companion Publication and will NOT appear in the ACM DL.

Your prompt and immediate attention to the form below is needed.

permission release form URL: ....

ACM Copyrights & Permissions

Given that this was the "last and final requeset"[sic], I assumed that somehow I missed the previous requests. So, I checked my email to find out how late I was. Nope. Nothing in the archive, nothing in the trash, nothing in the spam, no entry in the delivery log. This was the first notification sent by ACM. They have just forgotten about this. But since they were running late, why not just threaten the authors? It is so much easier to pass the blame to others and be the first one to be aggressive.

What happened ACM, did you start get advice on customer service from your pals at Sheridan Printing, who tend to send requests like this?

But I should not have been so surprised. This email just reflects the overall attitude of ACM. I have experienced this many times in the past. Anyway, I decided to sign the e-form, without firing back.

Donating copyright to ACM

Signing the form was a mechanic action before. However, after reading Matt Blaze's post on copyright and academic publishing, I decided to read the form a little bit more carefully, to see exactly what I was signing.

As usual, we start with a transfer of copyright to ACM. The authors agree to transfer all their copyright rights to ACM, blah blah...

Wait a minute! Why does ACM needs to own the copyright? No good reason. To publish and distribute the article, ACM just needs a non-exclusive license to print and distribute. There is no need to own the copyright.

If we follow ACM's logic, any artist that wants to see their work exhibited in any museum, they need to give up the ownership of their work and give full ownership of their creations to the museum. For free. Without expecting any royalties back in return. Ever. Furthermore, the museum instead of promoting the work, they would lock it in a "patron members access only". For all others, the museum would demand a separate entrance ticket to show each of the collection pieces. (Say, for a friendly price of $5 to see each painting?) .

Anyway, let's not belabor the point with copyright. We know that ACM's policy sucks. We know that ACM is a bureaucracy serving just itself and not its members or the profession. Let's move on.

Let's move to the point that really got me fired up.

Protecting ACM from liability

What got me really pissed was the last part of the agreement:

Liability Waiver

* Your grant of permission is conditional upon you agreeing to the terms set out below.

I hereby release and discharge ACM and other publication sponsors and organizers from any and all liability arising out of my inclusion in the publication, or in connection with the performance of any of the activities described in this document as permitted herein. This includes, but is not limited to, my right of privacy or publicity, copyright, patent rights, trade secret rights, moral rights or trademark rights.

All permissions and releases granted by me herein shall be effective in perpetuity unless otherwise stipulated, and extend and apply to the ACM and its assigns, contractors, sublicensed distributors, successors and agents.

So, not only we should donate "voluntarily" ownership of our copyright to ACM . We also need to protect ACM from any liability.

In other words, ACM wants to get all the upside from owning the copyright, without ever distributing royalties to the contributing authors. (Not that it would be worth much. It is a matter of principle and a signal of respect to the authors, not an issue of monetary importance.) At the same, ACM also wants the authors to provide guarantee that if there is any problem with the copyright, the author will be the one liable for the damages.

All the upside for ACM, no revenue to the authors. All the downside to the authors, no obligations for ACM.

Thank you ACM for caring so much about your members. You will not be missed when you disappear.

Yours truly,
A lifetime member of ACM.

PS: In retrospect, the title of the post is offensive: From Wikipedia's definition of serfdom: "Serfdom included the forced labor of serfs bound to a hereditary plot of land owned by a lord in return for protection". In other words, the slave owners took the product of slaves' work, but in return they provided the protection and military support, to defend the slaves that were working the land. ACM also wants the slaves to "protect the land" as well. I owe an apology to the slave owners for the comparison.

</rant>

The promise and fear of an assembly line for knowledge work

2011-03-03T11:41:00.000-08:00

Last week, together with Amanda Michel from ProPublica, we were presenting at the CAR 2011 conference (CAR stands for Computer-Assisted Reporting), on how to best use Mechanical Turk for a variety of tasks pertaining to data-driven journalism.

We discussed issues of quality assurance, how TurkIt-like workflow-based tasks can generate nice outcomes, and briefly touched upon the CrowdForge work from Niki Kittur and the team at CMU, showing that crowdsourcing can potentially generate intellectual outcomes comparable to those of trained humans.

The discussion after the session was a mix of excitement and fear. We have observed in the past how "assembly line" work for industrial production lead to massive productivity improvements and was the basis for much of the progress in the 19th and 20th century. But that was for mechanical work. Yes, it replaced centuries old crafts of the blacksmiths, carpenters, potters, but that was just part of progress.

What happens if we see now the assembly line extended into tasks that were traditionally considered creative and intellectual in nature? What would be the effect of an assembly line for knowledge work?

A few months back, I quoted Marx and Engels who, back in 1848, wrote in their Communist manifesto:

the work of the proletarians has lost all individual character, and, consequently, all charm for the workman. ... [The workman] becomes an appendage of the machine, and it is only the most simple, most monotonous, and most easily acquired knack, that is required of him

(Btw, TIME magazine liked that connection enough to put it into their own article about Mechanical Turk.)

But how likely it is to see this style of work to be extended further in the intellectual field? Are these Mechanical Turk experiments something generalizable, or just cute proof-of-concept experiments?

I was reminded of this question today, when I realized that many intellectual tasks are already commoditized:

The article "Inside the multimillion-dollar essay-scoring business: Behind the scenes of standardized testing" gives a dreadful view of now essays are being scored for the standardized tests.

Based on the description of the article, the (human-based) scoring process "goes too fast; relies on cheap, inexperienced labor; and does not accurately assess student learning." Needless to say, the workers were not exactly enthusiastic about their work. Match that with the computer-assisted scoring of essays, and you have an MTurk-like environment for much more intellectually-demanding tasks...

After reading this essay-scoring mill story, I started feeling a little bit uneasy. The MTurk-style work seems too far away to be in my future, so the discussion is always, ahem, academic. But the essay scoring brought the concept a little bit too close for comfort.

What was the main factor for Watson's success? Hardware, software, or data?

2011-02-17T12:06:00.000-08:00

I can think of three thinks that may have allowed Watson to win Jeopardy:

Hardware: From a comment at Shtetl-Optimized, "The hardware Watson was running on is said to be capable of 80 teraflops. According to the TOP500 list for November 2000, the fastest supercomputer (ASCI White) was capable of 4.9 teraflops." So, computers became 40x faster over the last 10 years. Is this the winning factor?
Software: A couple of months back Noam Nissan reported: "while improvements in hardware accounted for an approximate 1,000 fold increase in calculation speed over a 15-year time-span, improvements in algorithms accounted for an over 43,000 fold increase." So, maybe it is just the better NLP and machine learning algorithms that played the crucial role in this success.
Data: 10 years back we did not have Wikipedia, and its derivatives, such as Wiktionary, WikiQuote, Wikispecies, DBPedia, etc. Such resources add a tremendous value for finding connections between concepts.

My gut feeling says that the crucial factor is the development of the data resources that allowed Watson to answer such trivia questions. Without discounting the importance of hardware and software development, without having such tremendously organized and rich data sources, it would not be possible for Watson to answer any of these questions. The IBM WebFountain was around for a while, but trying to structure the unstructured web data, and get meaning out of such data, is much harder than taking and analyzing the nicely organized data in DBPedia.

To paraphrase a loosely-related quote: Better data usually beats better algorithms.

Browsers of Mechanical Turk workers

2011-02-16T11:14:00.000-08:00

Yesterday, Michael Bernstein asked on Twitter:

I recalled that my favorite go-to source for Turk statistics, Dahn Tamir, used Mechanical Turk a couple of years back to examine the connection between browser use and political orientation.

I asked Dahn if he had collected more extensive data. He is running tasks using a very large number of workers, so his sample would have been representative.

I was not disappointed: Dahn had data from approximately 19,000 workers, based on 75,000 worker requests from the last 6 months, recording the "user-agent" part of the HTTP request. For each workerid, we counted how many different user-agents we have seen. The maximum was 19, with an average value of 1.3.

Then, measured the workerid's per user-agent string. If a worker had registered multiple user-agent strings, we split the credit across browsers. For example, if the same workerid had one session with IE8 and one with IE9, then we gave 0.5 credit to IE8 and 0.5 credit to IE9.

I processed further the data using the UserAgentString API and I generated this Google spreadsheet.

After processing the data, here are the high level results:

Operating System Usage

Yep, most (~85%-90%) of MTurk workers use Windows. I found very surprising the prevalence of Windows XP!

Browser Usage

I found very interesting the relatively low percentage of IE users.

For reference, here are the most common versions for each of the most-used browsers by Mechanical Turk workers:

One of the good news is that most MTurk workers tend to use new versions of the browsers with good support for the latest web technologies (css, javascript, etc). Interestingly, though, a very significant fraction uses Windows XP!

In the future, we may repeat the measurements by also keeping statistics about Javascript versions, plugins, flash support etc.

Until then, enjoy and code safely, knowing that you do not have to support IE6 and IE7 in your MTurk HITs.

3rd Human Computation Workshop (HCOMP 2011), San Francisco, August 7 or 8

2011-02-13T21:20:00.000-08:00

I am just posting this here, to build some awareness about HCOMP 2011, the 3rd Human Computation Workshop, which will be organized together with AAAI in San Francisco, on August 7 or 8. You can also find more detailed information about the workshop at http://www.humancomputation.com. The submission deadline is ~~April 22~~ April 29th.

Human Computation is the study of systems where humans perform a major part of the computation or are an integral part of the overall computational system. Over the past few years, we have observed a proliferation of related workshops, new courses, and tutorials, scattered across many conferences.

In this 3rd Human Computation Workshop (HCOMP 2011), we hope to draw together participants across disciplines -- machine learning, HCI, mechanism and market design, information retrieval, decision-theoretic
planning, optimization, computer vision -- for a stimulating full-day workshop at AAAI in the beautiful San Francisco this summer. There will be presentation of new works, lively discussions, poster and demo sessions, and invited talks by Eric Horvitz, Jennifer Wortman and more. There will also be a 4-hour tutorial called "Human Computation: Core Research Questions and State of the Art" at AAAI on August 7, which will give newcomers and current researchers a bird�s eye view of the research landscape of human computation.

Call for Papers

3rd Human Computation Workshop (HCOMP 2011)
co-located with AAAI 2011
August 7 or 8, San Francisco, CA
http://www.humancomputation.com

Human computation is a relatively new research area that studies how to build intelligent systems that involves human computers, with each of them performing computation (e.g., image classification, translation, and protein folding) that leverage human intelligence, but challenges even the most sophisticated AI algorithms that exist today. With the immense growth of the Web, human computation systems can now leverage the abilities of an unprecedented number of Internet users to perform complex computation. Various genres of human computation applications are available today, including games with a purpose (e.g., the ESP Game) that generates useful data through gameplay, crowdsourcing marketplaces (e.g., Amazon Mechanical Turk) that coordinate workers to perform tasks for monetary rewards, and identity verification systems (e.g. reCAPTCHA) that generate useful data through users performing computation for access to online content.

Despite the variety of human computation applications, there exist many common core research issues. How can we design mechanisms for querying human computers in such a way that incentivizes or encourages truthful responses? What are the techniques for aggregating noisy outputs from multiple human computers? How do we effectively assign tasks to human computers to match their particular expertise and interests? What are some programming paradigms for designing algorithms that effectively leverage the humans in the loop? How do we build human computation systems that involve the joint efforts of both machines and humans, trading off each of their particular strengths and weaknesses? Significant advances on such questions will likely need to draw many disciplines, including machine learning, mechanism and market design, information retrieval, decision-theoretic planning, optimization, human computer interaction, etc.

The workshop recognizes the growing opportunity for AI to function as an enabling technology in human computation systems. At the same time, AI can leverage technical advances and data collected from human
computation systems for its own advancement. The goal of HCOMP 2011 is to bring together academic and industry researchers from diverse subfields in a stimulating discussion of existing human computation applications and future directions of this relatively new subject area. The workshop also aims to broaden the scope of human computation to more than the issue of data collection to a broader definition of human computation, to study systems where humans perform a major part of the computation or are an integral part of the overall computational system.

Topics

Topics of interest include, but are not limited to:

Programming languages, tools and platforms to support human computation
Domain-specific challenges in human computation
Methods for estimating the cost, reliability, and skill of labelers
Methods for designing and controlling workflows for human computation tasks
Empirical and formal models of incentives in human computation systems
Benefits of one-time versus repeated labeling
Design of manipulation-resistance mechanisms in human computation
Concerns regarding the protection of labeler identities
Active learning from imperfect human labelers
Techniques for inferring expertise and routing tasks
Theoretical limitations of human computation

Format

The workshop will consist of several invited talks from prominent researchers in different areas related to human computation, selected presentations of technical and position papers, as well as poster and demo sessions, organized by theme.

Submission

Technical papers and position papers may be up to 6 pages in length, and should follow AAAI formatting guidelines. For demos and poster presentations, authors should submit a short paper or extended abstract (up to 2 pages). We welcome early work, and particularly encourage submission of visionary position papers that are more forward looking. Papers must be submitted electronically via CMT. The submission deadline is April 22, 2010.

Workshop Website

For more details, please consult our workshop website.

Organizers

Luis von Ahn (co-chair)
Panagiotis Ipeirotis (co-chair)
Edith Law
Haoqi Zhang
Jing Wang

Program Committee

Foster Provost
Winter Mason
Eric Horvitz
Ed Chi
Serge Belongie
Paul Bennett
Jennifer Wortman
Yiling Chen
Kristen Grauman
Raman Chandrasekar
Rob Miller
Deepak Ganesan
Chris Callison-Burch
Vitor R. Carvalho
David Parkes

Notes from "Crowdsourcing in Search and Data Mining" (CSDM) workshop

2011-02-09T18:18:00.000-08:00

I was attending the Crowdsourcing in Search and Data Mining workshop at the WSDM 2011 conference in Hong Kong. I kept some (informal) notes about the workshop:

Invited talk - Winter Mason, presenting his work on "Individual vs. Group Success in Social Networks".

Winter started by presenting a summary of his HCOMP 2009 paper on how payment on Mechanical Turk affect quality and speed of completion (hint: affects speed, does not affect quality). Then he moved to talk on how agents can collaborate to solve complex problems. How structure of the communication network affect the results? How the position in the network affects the performance of an individual? The participants were playing a game, where they were attempting to discover oil in a map. The users could see where their neighbors searched for oil in the field. So, they were kind of guiding each other in discovering oil. As part of the experiment, the underlying, invisible graph connecting the players was changed, to see the results. Typically the players were copying each other more, as the clustering coefficient of the graph increased (i.e, less exploration). However, this did not have a statistically significant effect in "finding the peak of oil production" and all graph structured performed similarly in terms of overall success, although there was some non-significant decrease in performance. This work points the direction to a lot of interesting future research: When should we let people talk to each other vs let them work independently? What is the structure of the solution space that indicates that people should collaborate vs explore independently (e.g., if there is a "hard to find" peak of oil production, and many areas with moderate oil production that are easier to find, you want people to explore independently; if there is a single peak, collaboration helps)

Guido Zuccon, Teerapong Leelanupab, Stewart Whiting, Joemon Jose and Leif Azzopardi. Crowdsourcing Interactions - A proposal for capturing user interactions through crowdsourcing.

The main question is how to capture behavior of users of search engines, when you do not have a search engine available (ala Google, Microsoft, Yahoo, etc). The alternative is to have something done on the lab, but the population is homogeneous and expensive if you want to create a big data set.

The author described how they build a task-oriented system on top of MTurk, intermediating on top of Bing, and examined how users used the search engine to identify answers to the questions posed (taken by IIR track of TREC).

Richard McCreadie, Craig Macdonald and Iadh Ounis. Crowdsourcing Blog Track Top News Judgments at TREC.

The authors describe their experiences crowdsourcing relevance evaluations. "Find interesting stories on day d, for category c". Basic setup: display the results to the user, and measure speed, cost, and level of agreement (quality of assessments). They observe everything in the server, and they conclude that MTurk is good, cheap, and fast. To ensure quality they need at least three assessors per document. Workers seemed to just skip through the documents (~15 seconds per document) but the results seemed pretty consistent with the overall TREC results.

Carsten Eickhoff and Arjen de Vries. How Crowdsourcable is Your Task?

The authors list their experiences of how they fell in love with crowdsourcing, but then they realized (surprise!) that there are cheaters out to get you and submit junk. Their major conclusions: the inherent reputation metrics on Turk are pretty much useless, and gold testing tends to be good in specific cases (well-defined, unambiguous answers). They suggest to make the HITs more "creative" and less "mechanical" to be less susceptible to spam. Novelty helps, as refreshes the mind of the worker.

Christopher Harris. You�re Hired! An Examination of Crowdsourcing Incentive Models in Human Resource Tasks.

How can we structure a resume screening HIT, in order to achieve both good precision and recall? HR screening is mainly a recall task (you do not want to lose good candidates). The initial worker screening included a English skill test, plus an "attention to detail" task, which examines that workers pay attention. The author presents an experiment with different treatment conditions in terms of incentives (no incentive, bonus always, bonus only on performance framed as negative). The basic result: incentives for performance increase completion time, and positive incentives increase performance.

Jing Wang, Siamak Faridani and Panagiotis Ipeirotis. Estimating Completion Time for Crowdsourced Tasks Using Survival Analysis Models.

An analysis of the MTurk market, to identify how long it takes a task to be completed. Effect of price: 10x price, gives a 40% speedup. Effect of grouping HITS: 1000 HITs grouped get done 7x faster than 1000 sequential HITs. The slides are available online.

Raynor Vliegendhart, Martha Larson, Christoph Kofler, Carsten Eickhoff and Johan Pouwelse. Investigating Factors Influencing Crowdsourcing Tasks with High Imaginative Load.

[jet lag was hitting pretty hard at that point, and I had to take off and get some rest...]

Invited talk - Thore Graepel: The Smarter Crowd: Active Learning, Knowledge Corroboration, and Collective IQs

Some ideas on how to use graphical models to model users and their expertise to match them with appropriate items to work on. Basic idea: user modeling helps in understanding the workers, and can improve active learning.

Omar Alonso. Perspectives on Infrastructure for Crowdsourcing.

Description of techniques that facilitate the development of advanced crowdsourcing systems (e.g., Mapreduce, reputation systems, workflows etc). Can we devise a general computation system for the HPU (human processing unit), building on existing paradigms for computational systems? What are the fundamental building blocks that we need?

Abhimanu Kumar and Matthew Lease. Modeling Annotator Accuracies for Supervised Learning.

This paper examines where to allocate the labeling effort when building a machine learning task. Basic idea: If we know the quality of the workers, most of the solutions work pretty similarly.

Invited talk - Panos Ipeirotis: Crowdsourcing using Mechanical Turk: Quality Management and Scalability

I described our experiences in building systems for managing quality when dealing with imperfect human annotators (from our HCOMP 2010 paper), and on how to efficiently allocate resources in labeling when using the data to build machine learning models (KDD 2008 and working paper). I used plenty of examples from our AdSafe experience, and gave a brief glimpse into our latest explorations in using the use of psychology and biology to influence worker behavior.

Conclusions and Best Paper

The day ended with some overall discussion about the problems that we face with crowdsourcing. The discussion focused significantly on what we can do to separate inherent uncertainty in the signal from uninformative noise, and on how to be able to get the "informed minority" to get the truth out, without being drowned by the "tyranny of majority" (a good example is the question "Is Obama a Grammy winner?", where most people will intuitively say "no" but the correct answer is "yes"; in redundancy based approaches it is likely that the noise with bury the signal). Also people expressed concern that everyone is building his own little system from scratch, reinventing the wheel, instead of having a more coordinated effort to share experiences, and infrastructure. Also the paper "How Crowdsourcable is Your Task?" got the most-innovative paper award, and the discussion continued over beers and other distilled beverages....

The unreasonable effectiveness of simplicity

2011-02-06T15:56:00.000-08:00

There are a few techniques, which are extremely easy to understand and implement. At the same time, they appear to be extremely basic and should be very easy to beat with more advanced techniques. However, this is often not the case. Consider the following examples:

Majority voting and aggregating discrete votes.

Let's say that we are trying to label objects using discrete labels (e.g., is this blog comment "spam" or "not spam"). For each object, we get multiple people to look at it, and label it, the current practice today on Mechanical Turk.

The simplest aggregation technique: Use the majority vote as the correct answer.

This seems a ridiculously easy baseline to beat. We can model quality of the workers. We can control for the varying difficulty of the examples that need to be rated. We can control for the different types of expertise of the workers, and match them with the examples that are best for them. Plenty of papers were published around this topic.

What is the improvement? Modest at best, and non-existent most of the time. The only (real) improvement, in most cases, means kicking out the spammers and take the majority vote across the good workers. Do we need any advanced technique for that? No. A few gold cases here and there (ala Crowdflower), or a simple comparison of how often one workers agrees with the majority, is typically enough.

Why is that? Because majority vote is a simple model. No parameters to estimate. For anything more advanced, we need a lot of data for the model to generate robust parameter estimates. The errors introduced by incorrect parameter estimates typically alleviates the advantages of the more complex modeling.

Averages and aggregating continuous probability estimates

Now consider the case of combining forecasts from multiple sources. For example, we want to predict the weather, and we have multiple sources each with its own forecast. Or we have many stock market analysts, covering the same stock and making predictions for future performance.

Consider the simplest way to aggregate: average across all estimates $p_i$.

$\hat p = \frac{1}{N} \cdot \sum_i^N p_i$

Very straightforward. As in the case of aggregating discrete labels, it is trivial to improve, in theory.

This topic has a long history in the literature, and there are even meta-studies that examine the effectiveness of the various approaches. See for example the survey-style studies:

The Effects of Averaging Subjective Probability Estimates Between and Within Judges, by Ariely et al. and
Combining probability distributions from experts in risk analysis by Clemen and Winkler.

Both studies reach similar conclusions: You can definitely improve simple averages, but most of the time the improvement is marginal, and you lose robustness. From Clemen and Winkler: "...simple combination rules (e.g., simple average) tend to perform quite well. More complex rules, sometimes outperform the simple rules, but they can be somewhat sensitive, leading to poor performance in some instances."

Sometimes a simple baseline algorithm is so good for practical purposes, that any improvements have only academic interest. I know that we have papers to write, careers to advance, and grants to get, but sometimes it is good to stop and think: "What did I gain, compared to a simpler alternative? Does it make sense to introduce so much additional complexity for the sake of some minor improvement?"

Amazon Reacts: Spammers Kicked Out of MTurk!

2010-12-23T22:14:00.000-08:00

I got a notification in the comments of the blog post about spam on MTurk that Amazon seems to have taken seriously the spam problem reported in my previous blog post.

Broken Turk wrote:

Have you seen the site? It looks as if MTurk liked your research?

(Link to top paying HITs, no spam!)

(Turker Nation post)

Indeed, I checked the available HITs and all the spam HITs seem to have magically disappeared! It seems that all the negative publicity convinced the guys at MTurk that spam IS a problem.

I will consider that the goal of the blog post is now achieved. Amazon listened!

Good job Amazon!

Mechanical Turk: Now with 40.92% spam.

2010-12-16T15:49:00.000-08:00

At this point, Amazon Mechanical Turk has reached the mainstream. Pretty much everyone knows about the concept. Post small tasks online, pay people cents, and get thousands of micro-tasks completed.

Unfortunately, this resulted in some unfortunate trends. Anyone who frequents just a little bit the market will notice the tremendous number of spammy HITs. (HIT = a task posted for completion in the market; stands for Human Intelligence Task). "Test if the ads in my website work". "Create a Twitter account and follow me". "Like my YouTube video". "Download this app". "Write a positive review on Yelp". A seemingly endless amount of spam HITs come to the market, mainly with the purpose of spamming "social media" metrics.

So, with Dahn Tamir and Priya Kanth (MS student at NYU), we decided to examine how big is the problem. How many spammers join the market? How many spam HITs are there?

Using the data from Mechanical Turk Tracker, we picked all the requesters that first joined the market in September 2010 and October 2010. Why new ones? Because we assumed that long term requesters are not spammers. (But this remains to be verified.)

This process resulted in 1733 new requesters that first appeared in the marketplace in September and October 2010. We then took all the HITs that these requesters posted in the market. This was a total of 5842 HIT groups. The activity patterns of the new requesters were similar to those of the general requester population.

The next step was to post these HITs on Mechanical Turk, and asked workers to classify them as spam or not, using the following guidelines:

Use the following guidelines to classify the HIT as SPAM:
SEO: Asks me to give a fake rating, vote, review, comment, or "like" on Facebook, YouTube, DIGG, etc., or to create fake mail or website accounts.
Fake accounts: Asks me to create an account on Twitter, Facebook, and then perform a likely spam action.
Lead Gen: Asks me to go to a website and sign up for a trial, complete an offer, fill out a form requesting information, "test" a data-entry form, etc.
Fake clicks: Asks me to go to a website and click on ads.
Fake ads: Asks me to post an ad to Craigslist or other marketplace.
Personal Info: Asks me for my real name, phone number, full mailing address or email.
You can also use your intuition to classify the HIT
Please DO NOT classify as spam, HITs that are legitimate in nature but priced offensively low.

Interestingly enough, we got a ridiculous amount of spam from the worker side. Even with 99% approval rate and 1000 HITs as qualification, we got plenty of spammers giving us random data.

Since spam was a big problem, we posted the HIT using CrowdFlower and we used a set of 100 manually classified HITs as gold. (Without Crowdflower, we had to manually kick out the spammers and repost the HITs. So, Crowdflower saved the day.)

We asked 11 workers to classify each HIT, and we ignored votes from the untrusted workers (that failed to answer correctly at least 75% of the gold tests). So, with 11 trusted workers working on each HIT, we were reasonably sure that the majority vote across these 11 votes resulted in an accurate HIT classification.

I also ran the "get another label" code and I noticed that all the workers were of reasonable quality. Since the results were similar to those of the majority vote, I decided to keep things simple and go with the majority vote as the correct answer.

The results

The results were disturbing. Out of the total of 5841 HITs, a total of 2390 HITs, or 40.92% were marked as spam HITs.

This is not good! 40% of the HITs from new requesters are spam!

Our next test was to examine whether there are accounts that post a mix of spam and not spam HITs. The analysis indicated that this is not the case. Very few accounts post both spam HITs and legitimate HITs:

The plot illustrates that 31.83% of the new requesters post only spam HITs.

In total, 757 out of the 1733 new requesters posted at least a one spam HIT, and 552 accounts were posting only spam HITs. 56.46% of the new requesters post no spam HITs. This nice separation indicates that it is easy to separate spam requesters from legitimate ones. There are not that many requesters that post both spam HITs and legitimate ones.

So, 31.8% of the new requesters are clear spammers, and 40.92% of the new HITs are spam-related! This is clearly a problem.

Spam HITs and pricing

So, what are the quantitative characteristics of the spam HITs?

First of all, they tend to contain much fewer "HITs available" compared to the legitimate HITs. 95% of the spam HITs contain just a single HIT, while only 75% of the legitimate HITs have one HIT available.

On the other hand, spammers tend to post HITs with higher rewards (perhaps because they do not pay?). Approximately 80% of the legitimate HITs are priced below one dollar, while only 60% of the spam HITs are priced below this threshold. Actually, many of the best paying HITs tend to be spam-related ones.

By combining the two charts above, we can plot the total value of the spam vs not spam HITs.

Overall, the findings are not really surprising: Most of the spam HITs require large number of workers to complete a task. They want 1000 users to click an ad, not a single user to click a thousand times at a single ad. Therefore, I suspect that most of these spam HITs have a very significant amount of redundancy, (which unfortunately we cannot observe). This means that the total value of the posted spam HITs is most probably much higher than the total value of the legitimate HITs.

What to do?

These trends are very worrisome:

40% of the HITs from new requesters are spam.
30% of the new requesters are clear spammers.
The spam HITs have bigger value than the legitimate ones.

It is very clear that active action should be taken against spam requesters.

According to our measurements, we see approximately 1500 new HITs arriving in the market every day (from all requesters), and approximately 30 new requester accounts join the market every day. It should be trivial to review all the HITs manually by posting them to MTurk for review.

But even if this manual inspection is expensive, this is a task that can be very easily automated. In our current work, we realized that it is very easy to accurately classify HITs as spam or not. A simple SVM linear classifier that uses bag of words as features can achieve a 95% true positive and 95% true negative rate. With a moderately advanced scheme, it should be possible to have a strong system in place pretty quickly.

For whomever is interested, the data is available here

The disheartening part was the response of Amazon when we informed them about the issue. They pretty much assured us that everything is fine, and they believed there is no problem! For me, this was more problematic than the existence of spam.

Why Amazon ignores spam?

To answer this question, I have asked Amazon for access to the data to investigate further. Unfortunately, I was denied access. (It does not pay to criticize Amazon.) Interestingly enough, the MTurk guys share data with other academics.

The key piece for answering this question, which I cannot get from my data: Do spammers pay the workers?

If the spam requesters do not pay the workers, then Amazon should be more proactive in battling spammer requesters. Workers need to be protected! It is easy to see that it is a death spiral otherwise. The more spammers can get away with getting work done and not paying, the less the workers will trust new requesters. Legitimate new requesters will face a significant uphill battle to convince the workers about their intentions, they will abandon their plans, and let the spammers prevail. We have a market for lemons on the inverse.

If the spam requesters pay the workers, then there is a cynical explanation: Amazon does not take an active role in cleaning the market because they simply profit from the spam. And it is part of the growth. And nobody within the MTurk division would cut in half the growth rate at this point.

However, this would be an incredibly short-sighted approach. With the amount of spam in the worker side, and the amount of spam in the requester side, then Mechanical Turk would slowly turn into a market where spammers requester talk to spammer workers... Ah yes, and academics running experiments...

Sharing code, API's, and a Readability API

2010-12-12T22:30:00.000-08:00

Yesterday, I received an email from a student that wanted to have access to some code that we used in our recent TKDE paper "Estimating the Helpfulness and Economic Impact of Product Reviews: Mining Text and Reviewer Characteristics".

Specifically, the student wanted to estimate the readability test scores for the reviews. For those not familiar with readability tests, they are simple formulas that examine the text and estimate what is the necessary level education required in order to read and understand a particular piece of text.

I tried to send the code, but then I realized that it had some dependencies to some old libraries, which have been deprecated. At that point, I realized that it would be a pain to send the code to the student, then give instructions about all the dependencies etc. On the other hand, not sending the code is simply unacceptable.

Sharing code as an API

This got me thinking: How can we make the code to be robust to changes? How can we share the code in a way that it can be easily used by others? Given that all software packages today have web API's, why not creating API's for our own (research) code?

Since I have never tried in the past to do some serious web programming, I decided that I can spend a few hours to familiarize myself with the basics and make my library to be a set of RESTful API calls.

Apparently, it was not that difficult. I uploaded the code to the Google App Engine, and I wrote a small servlet that was taking as input the text, and was returning the readability metric of choice. Almost an assignment for a first-year student learning about programming.

Readability API

After a few hours of coding, I managed to generate a first version of the demo at http://ipeirotis.appspot.com/readability.html. I also created a basic API which can be easily used to estimate the readability scores of various texts.

I followed the example of bit.ly and I allowed the API calls to return simple txt format, so that it can be possible to embed the Readability API calls in many places. For example, I really enjoy calling bit.ly within Excel or within R, in order to shorten URLs. Now, it is possible to do the same in order to compute readability scores.

For example, if we want to compute the SMOG score for for the text "I do not like them in a box. I do not like them with a fox" and get back the score in simple text, you just need to call:

http://ipeirotis.appspot.com/readability/GetReadabilityScores?output=txt&metric=SMOG&text=I%20do%20not%20like%20them%20in%20a%20box.%20I%20do%20not%20like%20them%20with%20a%20fox.

The result is the SMOG score for the text, which in this case is 3.129. You can play with the demo and type whatever text you want, and see the documentation if you want to use the code. Of course, the source code is also available.

Future Plans

I actually like this idea and the result. I will be trying to port more of my code online, and make it available as an API. With the availability of sites such as Google App Engine, we do not have to worry about servers being taken down, or upgrades in OS, etc. The code can remain online and functioning. Now, let's see how easy it will be to port some non-trivial code.

Excerpts from "The Communist Manifesto"

2010-12-06T17:08:00.000-08:00

... A class of laborers, who live only so long as they find work, and who find work only so long as their labor increases capital.

These laborers, who must sell themselves piecemeal, are a commodity, like every other article of commerce, and are consequently exposed to all the vicissitudes of competition, to all the fluctuations of the market.

Owing to the extensive use of machinery, and to the division of labor, the work of the proletarians has lost all individual character, and, consequently, all charm for the workman.

He becomes an appendage of the machine, and it is only the most simple, most monotonous, and most easily acquired knack, that is required of him.

Excerpts from "The Communist Manifesto", 1848

162 years later, the Communist Manifesto, by Marx and Engels, finds a new meaning in the online world of Amazon Mechanical Turk.

Wisdom of the Crowds: When do we need Independence?

2010-11-28T21:04:00.000-08:00

I have been thinking lately about the conditions and assumptions for the wisdom of crowds to work. Surowiecki, in this popular book, gave the following four conditions for the crowd to arrive at
the correct decision.

Diversity of opinion: Each person should have private information even if it's just an eccentric interpretation of the known facts.
Independence: People's opinions aren't determined by the opinions of those around them.
Decentralization: People are able to specialize and draw on local knowledge.
Aggregation: Some mechanism exists for turning private judgments into a collective decision.

The part that got me mostly puzzled is the independence assumption. Actually, I can support pretty much any thesis. I can argue that independence is necessary. I can argue that we do not really need independence so much. And I can argue that independence is evil. And I will do all these things below.

Independence is necessary

It is not difficult to understand why, in some cases, independence is necessary. If the contributions from the crowd are not independent, then it we may easily observe a herding behavior. Daniel Tunkelang discusses a nice, instructional example (from the book Networks, Crowds, and Markets, by David Easley and Jon Kleinberg), in which the influence of the crowd can lead often to incorrect decisions, while independence can easily avoid erroneous outcomes.

The paper "Limits for the Precision and Value of Information from Dependent Sources" by Clemen and Winkler shows that in the presence of positive correlation, when we aggregate information from multiple dependent sources, the resulting accuracy does not increase as we would expect.

The figure below shows in the x-axis the number of dependent sources, and in the y-axis the equivalent number of independent sources, for various correlation coefficients ?.

Even at moderate levels of ?, we see how strong are the limitations. With ?=0.4 it is almost impossible to go above two independent sources. And if we have noisy input, we often need a large number of independent sources to separate signal from noise.

In other words, it is better to have a couple of independent opinions, rather than having thousands of correlated voices.

Lack of independence: Perhaps not so bad

We have examples where lack of independence is not always bad.

For example, according to the paper "Measuring the Crowd Within" by Vul and Pashler, even asking the same person for a second time and getting the average can lead to improved outcomes.

Or take the other poster-child application of wisdom of crowds: prediction markets (or markets, in general). In these markets, people trade based on their personal information. However, they can always see (and get influenced?) by the aggregated opinion of the crowd, as this is reflected in the market prices. And empirical evidence illustrates that (prediction) markets work surprisingly well, despite (or because of) the lack of independence. Prior work has even demonstrated that even non-public information spreads quickly through the market (and the SEC checks for insider trading if they detect unusual activity before the public release of sensitive information.)

Wikipedia is another example: People do see what everyone else has done so far, before adding the extra information.

One paper that I found to be of interest is the Na�ve Learning in Social Networks and the Wisdom of Crowds by Golub and Jackson. The authors address the following question: "for which social network structures will a society of agents who communicate and update na�vely come to aggregate decentralized information completely and correctly?". The results are based on the ideas of convergence for Markov Chains. One of the basic result says that the Pagerank-score of a node in the network defines the weight of the node's influence in the final outcome.

In all these cases, the participants get information from the crowd, they do not just follow blindly. So, there is some benefit in interacting.

Independence is bad

Going even further, we have cases where complete independence of participants is bad!

This typically happens when participants know only parts of the overall information. Through communication, it is possible to identify the complete picture, but lack of communication leads to suboptimal outcomes. Consider the example in Proposition 2 from the paper "We can't disagree forever" by Geanakoplos and Polemarchakis:

We have a 4-sided dice, with mutually exclusive outcomes A, B, C, and D, each one occurring with probability 0.25.
In reality, the dice rolled 1. But nobody knows that. Instead the knowledge of the players is:

Player 1 knows that the event "A or B" happened
Player 2 knows that the event "A or C" happened

Both players can bet on whether "A or D" happened.

So, look what happens

No independence: If player 1 can communicate directly with player 2, they can figure out that event A happened, and they are certain that "A or D" occurred with probability 1.0
Independence: If player 1 cannot communicate, then both players assign a probability of 0.5 to the event "A or D". This is despite the fact that they collectively own enough information to figure out that A happened, and there is a market to trade the event. In other words, the market fails to aggregate the available information.

So, we have a scenario where the inability to spread information actually results in a bad outcome. However, if we allowed the participants to be non-independent, we could have an improved outcome.

Influence vs Information Spread

So, we can see actual examples where spread of information (and hence, lack of independence) can be both good and bad. Lack of independence, can lead to groupthink: and the individual voices get drowned in a sea of correlated opinions. At the other extreme, lack of communication leads to suboptimal outcomes.

The paper by Plott and Sunder "Rational Expectations and the Aggregation of Diverse Information in Laboratory Security Markets" discusses the issue in the context of security markets and examines how market design affects the information aggregation properties of markets. (Thanks for David Pennock for the pointer.)

The paper by Ostrovsky "Information Aggregation in Dynamic Markets with Strategic Traders" (in EC'09, I think also forthcoming in Econometrica) provides a rigorous theoretical framework on what are the conditions for information to be aggregated in a market: essentially we have "separable" securities for which all the available information can be aggregated, and non-separable ones that do not have this property. However, I do not have the necessary background to fully understand and present the ideas in the paper. And I cannot see how to connect this with the literature of information spreading in social networks.

In a more intuitive sense, it seems that we need information to spread and not just influence.

Unfortunately, I cannot grasp the full picture, despite the fact that I tried to look the problem from different angles (Ironic, eh?).

I still not fully understand the implications of the above in the design of processes that involve human input. Does it make sense to show to people what other people have contributed so far? Will we see effects of anchoring? Or will we see the establishment of a common ground and get people to coordinate better and understand each other's input?

How can we quantify and put in a common framework all the above?

Mechanical Turk, "Interesting Tasks," and Cognitive Dissonance

2010-11-23T23:21:00.000-08:00

It is a well-known fact that the wages on Mechanical Turk are horribly low. We can have endless discussions about this, and my own belief is that it is due to the lack of a strong worker reputation system. Others believe that this is due to the global competition for unskilled labor. And others are agnostic, saying that everything is a matter of supply and demand.

Other people try to explain the low wages by looking at the motivation of the workers: Quite a few people find the tasks on Mechanical Turk to be interesting. Ergo, they are willing to work for less.

Perfectly normal right? The task is interesting, people are willing to do it for less money. Sounds reasonable. Right? RIGHT? Well, be careful: correlation does not imply causation!

Enter the region of social psychology (thanks Konstantinos!): The theory of cognitive dissonance indicates that the causation may go in the entirely opposite direction: The wages are low, so people justify their participation by saying the work is interesting!

This surprising result is due to the paper "Cognitive Consequences of Forced Compliance" from Festinger and Carlsmith (1959). It is one of the classic papers in psychology.

What did Festinger and Carlsmith say?

That people that get low payment to do boring tasks, will convince themselves that they do this because the task is interesting. Otherwise, the conflict in their mind will be just too big: why do they work on such a boring task when the payment is horrible?

In contrast, if someone gets paid well to do the same boring task, they will consider the task boring. These well-paid participant can easily justify that they do the work for the money, (so it makes sense to do a boring job).

Amazingly enough, Festinger and Carlsmith verified this experimentally. Here is the experimental setup description from the Wikipedia entry that describes this intriguing experiment:

Students were asked to spend an hour on boring and tedious tasks (e.g., turning pegs a quarter turn, over and over again). The tasks were designed to generate a strong, negative attitude.

Once the subjects had done this, the experimenters asked some of them to do a simple favor. They were asked to talk to another subject (actually an actor) and persuade them that the tasks were interesting and engaging.

Some participants were paid $20 (inflation adjusted to 2010, this equates to $150) for this favor, another group was paid $1 (or $7.50 in "2010 dollars"), and a control group was not asked to perform the favor.

When asked to rate the boring tasks at the conclusion of the study (not in the presence of the other "subject"), those in the $1 group rated them more positively than those in the $20 and control groups.

The researchers theorized that people experienced dissonance between the conflicting cognitions, "I told someone that the task was interesting", and "I actually found it boring." When paid only $1, students were forced to internalize the attitude they were induced to express, because they had no other justification. Those in the $20 condition, however, had an obvious external justification for their behavior (i.e., high payment), and thus experienced less dissonance.

So, when you read surveys (mine included) that indicate that Mechanical Turk workers participate on the platform because they "find the tasks interesting", (and so it makes sense to pay low wages), please have this alternative explanation in mind:

Turkers convince themselves that the work is interesting, otherwise they would be completely crazy sitting there doing mind-boggling boring work, just to earn wage of a couple of bucks per hour.

NYC, I Love You(r Data)

2010-11-23T17:22:00.000-08:00

Last year, I experimented with the NYC Data Mine repository as a source of data for our introductory course on information systems (for business students, mainly non-majors). The results of the assignment were great, so I repeated it this year.

The goal of the assignment was to teach them how to grab and run database queries against large datasets. As part of an assignment, the students had to to go the NYC Data Mine repository, pick two datasets of their interest, join them in Access, and perform some analysis of interest. The ultimate goal was to get them to use some real data, and use them to perform an analysis of their interest.

Last year, some students took the easy way out and joined the datasets manually(!) on the borough values (Manhattan, Bronx, Brooklyn, Queens, Staten Island). This year, I explicitly forbid them from doing so. Instead, I explicitly asked them to join only using attributed with a large number of values.

The results are here and most of them are well-worth reading! The analyses below is almost like a tour guide on the New York's data sightseeings :-) The new generation of Nate Silver's is coming.

Enjoy the projects:

Academia and Concern for the Environment! Is there a correlation between how much you recycle and how well students perform in school? Are kids who are more involved in school activities more likely to recycle? Does school really teach us to be environmentally conscious? To find out the answers check out our site!
An Analysis of NYC Events: One of the greatest aspects about New York are the fun festivals, street fairs and block parties where you can really take in the culture. Our charts demonstrate which time to visit New York or what boroughs to attend events. We suggest that tourists and residents check out our research. Also organizers of events or people who make there money from events should also consult our analysis.
How are income and after school programs related?: This study is an analysis of how income levels are related to the number of after school programs in an area. The correlation between income and number of school programs was interesting to analyze across the boroughs because while they did follow a trend, the different environments of the boroughs also had an exogenous effect. This is most evident in Manhattan, which can be seen in the study.
Restaurant Cleanliness in Manhattan What are the cleanest and dirtiest restaurants in Manhattan? What are the most common restaurant code violations? We analyzed data on restaurant inspection results and found answers to these questions and more.
Ethnic Dissimilarity's Effect on New Business: This analysis focuses on the relationship between new businesses and specific ethnic regions. Do ethnically dominated zip codes deter or promote business owners of differing ethnicities to open up shop?
Does The Perception Of Safety In Manhattan Match With Reality? People�s perception of events and their surroundings influence their behavior and outlook, even though facts may present a different story. In this regard, we took a look at the reported perception of people�s safety within Manhattan and compared it to the actual crime rates reported by the NYPD. The purpose of our study was to evaluate the difference between the actual crime rate and perceived safety of citizens and measure any discrepancy.
Women's Organizations love food stores!: We have concluded that a large percentage of women's organizations are located near casual dining and takeout restaurants as well as personal and professional service establishments compared to what we originally believed would be shopping establishments.
Hispanics love electronics!: Our goal for this project is to analyze the relationship between electronic stores and demographics in a particular zip code. We conducted a ratio analysis instead of a count analysis to lessen the effects of population variability as to create an "apples to apples" comparison. From our analysis, it can be seen that there is a greater presence of electronic stores in zip codes with a higher proportion of Hispanics.
Political Contributions and Expenditures: A comprehensive analysis of the political contributions and expenditures during the 2009 elections. The breakdown of who, in what areas of Manhattan contribute as well as how candidates spend their money are particularly interesting!
How Dirty is Your Food? Our goal for this project is to analyze the various hygiene conditions of restaurants in New York City. We cross referenced the inspection scores of the restaurants with the cuisine they serve to find out if there was any correlation between these two sets of data. By ranking the average health score of the various cuisines, we can determine which kinds of cuisines were more likely to conform to health standards.
Want to Start a Laundromat? An Electronic Store? The best possible places to start a Laundromat and an electronic store. For Laundromats we gave the area that had the lowest per capita income, as we noticed a trend that Laundromats do better in poorer neighborhoods. For electronic stores we found the lowest saturated areas that have the highest per capita income.
Where to Let Your Children Loose During the Day in NYC: For this analysis, we wondered whether there was a correlation between how safe people felt in certain areas in New York and the availability of after-school programs in the different community boards.
Best Place to Live in Manhattan After Graduation: We analyzed what locations in Manhattan, classified by zip code, would be the best to live for a newly graduate. We used factors like shopping, nightlife, gyms, coffeehouses, and more! Visit the website to get the full analysis.
Political Contributions and Structures: Our report analyzes the correlation between political contributions and structures in New York in varying zip codes.
Best Places to Eat and Find Parking in New York City: Considering the dread of finding parking in New York City, our analysis is aimed at finding the restaurants with the largest number of parking spaces in their vicinities.
Are the Cleanest Restaurants Located in the Wealthiest Neighborhoods? Our analysis between property value and restaurant rating for the top and bottom ten rated restaurants by zip codes in New York City
Analysis of Popular Baby Names
Restaurant Sanitary Conditions: Our team was particularly interested in the various cuisines offered in various demographic neighborhoods, grouped by zip codes. We were especially curious about the sanitary level of various cuisines offered by restaurants. The questions we wanted to answer were:
- What zip codes had the highest rated restaurants? What type of cuisines are found in these zip codes?
- What zip codes had the lowest rated restaurants? What type of cuisines are found in these zip codes?
Does having more community facilities improve residents' satisfaction with city agencies? Does having more public and private community facilities in NYC such as schools, parks, libraries, public safety, special needs housing, health facilities, etc lead to greater satisfaction with city services? On intuition, the answer is a resounding YES! With more facilities, we would enjoy our neighborhood better and develop a better opinion of New York City services. But how accurate is this intuition? In this analysis, we put that to the test.
Housing Patterns in Manhattan: The objective of our analysis was to identify factors which play a role in determining vacancy rates in Manhattan�s community districts. We inferred that vacancy rates are representative of the population�s desire to live in a particular district. We examined determining factors of why people want to live in a particular district including: quality of education, health care services, crime control in each district, etc.
Analysis of Cultural Presence and Building Age by Zip Code: Manhattan is a hub for cultural organizations and opportunities for community involvement. But does the amount of "community presence" differ based on area that you live? Is there any relationship between the year that buildings in various areas were built, and the available programs for students and cultural organizations for the general public in that area? We analyzed whether a relationship existed between the number of cultural organizations and after school programs available in a zip code, and the average year that the buildings in the zip code were built. To further our analysis we looked at whether the age of buildings in areas with greatest "cultural presence" affected the sales price of the buildings.
Analysis of Baby Names across the Boroughs: We decided to analyze the Baby Names given in 2008 across the boroughs of Manhattan, the Bronx and Brooklyn. We found the most popular names in each Borough, along with top names specific to each borough that were unpopular in other Boroughs. We also found certain factors that could be a determining factor in the naming of these babies.
Analysis of New York City Street Complaints: We analyzed the different kinds of street complaints made in New York City, how the city tends to respond to them, and which streets have the most overall complaints when you also bring building complaints into the picture. This analysis taught us that Broadway has the most street complaints but it also piqued our interest in conducting even further analyses.
Campaign Contributions and Community Service Programs The goal of our analysis was to determine if there is a correlation between contributions by NYC residents to election candidates and community service programs. We wanted to see if people who are more financially invested in elections are also more inclined to be involved in their neighborhoods through community programs.
Public Libraries in Queens: We looked at how many public libraries there were in each zip code in Queens. We also looked at the number of people and racial composition in each zip code, to see if these factors are related.
Sidewalk Cafe Clustering: Our study�s goal is to understand where sidewalk cafes cluster and some potential reasons why they cluster. We start by looking at what areas of the city are most populated with sidewalk cafes. Then we look to see if there are any trends related to gender or race demographics. We finally look to see if there is any influence on property value on the abundance of sidewalk cafes.

The surprise in this year: Most students could not understand what is the "CSV" data file. Many of them thought it was some plain text, and did not try to use it. (Hence the prevalence of electronic and laundromat analyses, which were based on datasets available in Excel format.) I guess next year I will need to explain that as well.

Introductory Research Course: Replicate a Paper

2010-11-19T00:06:00.000-08:00

The transition to the happy life of a tenured professor meant that I get to be involved in the wonderful part of the job: Getting to sit in school-wide committees.

Fortunately, I was assigned in an extremely interesting committee: We get to examine the PhD program for the school, see the best practices, see what works and what does not, and try to reconcile everything into a set of recommendations for the faculty to examine. The double benefit for me is that I get to understand how the other departments operate in the school, a thing which, for a computer scientist in a business school, was still kind of a mystery to me.

Anyway, as part of this task, I learned about an interesting approach to teach starting PhD students about research:

A course in which students pick a paper and get to replicate it.

I think this is a great idea. First of all, I am a big fan of learning-by-doing.

For example, to understand how an algorithm works, you need to actually implement it. Not get the code and re-run the experiments. Implement everything, going as deeply as possible. In C, in Java, in Perl, in Python, in MatLab, in Maple, in Stata, it does not matter. For theory, the same thing: replicate the proofs. Do not skip the details. For data analysis, the same. Get your hands dirty.

During such a process, it is great to have someone to serve as a sounding board. Ask questions about the basics. Why do we follow this rule of thumb? What is the assumption behind the use of this method? Asking these questions is much easier while working on replicating someone else's work, rather then when working on your own research and trying to get a paper out.

Myself, I still write code for this very same reason. I need to see how the algorithm behaves. I need to see the small peculiarities in behavior. This observation gets me to understand better not only the algorithm itself but also other techniques that are employed by the algorithm. I am trying to understand econometrics a little bit deeper the last few months, and I do the same. Frustrating? Yes. Slow? Yes. Helpful? You bet!

So, at the end of the seminar, if the students can replicate the results of the paper, great: They learned what it takes to create a paper and most probably understood deeper a few other topics in the way.

If the results are different than in the original paper, then perhaps this is the beginning of a deeper investigation. Why things are different? Tuning? Settings? Bugs? Perhaps uncovering something not seen by the authors?

Even if the data from the authors are not available, the students should be able to reproduce and get similar results perhaps with different data sets. If the results with different data sets are qualitative different, then the paper is essentially not reproducible. (And replicability is not reproducibility.)

And in any case, no matter if the students can replicate the results or not, no matter if the paper is reproducible or not, the lesson from such an exercise can be valuable.

Often the student who understands better the paper, falls in love with a topic, and gets to learn more and more about the area. Following the footsteps of someone is often the first step to find your own path.

I think this seminar will make it to the final set of recommendations to the school. I am wondering how many other schools have such a course.

Update1: Needless to say, this is a class, not something that students try on their own. Therefore, the professor should pick a set of papers which are educational and useful to replicate. This can be either an easy "classic" paper, or an "important new" result, or even a paper that forces the students to use particular tools and data sources. The students choose from a predefined set, not from the wild.

Update2: Thanks to Jun, a commenter below, we have now a reference to the originator of the idea. Apparently, Gary King has published a paper in 2006, titled ""Publication, Publication", in "Political Science and Politics". From the abstract: "I show herein how to write a publishable paper by beginning with the replication of a published article. This strategy seems to work well for class projects in producing papers that ultimately get published, helping to professionalize students into the discipline, and teaching them the scientific norms of the free exchange of academic information. I begin by briefly revisiting the prominent debate on replication our discipline had a decade ago and some of the progress made in data sharing since."

Cease and desist...

2010-10-28T08:15:00.000-07:00

This was just too funny to resist posting.

Here is the background: As part of the core undergraduate introductory class "Information Technology in Business and Society", students have to create a website. To make things more interesting, I ask them to pick a few queries on Google, and try to create a website that will show up on the top of the results for these queries. Essentially it is a mix of technical skills with the ability to understand how pages are ranked and how to analyze the "competition" for these keywords.

So, a student of mine (John Cintolo), created a website about "Hit Club Music Summer 2010", with links to YouTube videos. No copyright infringment or anything illegal.

And one day later, he gets a "cease and desist" letter from HotNewClubSongs. It has so many gems that I will list it here, for your viewing pleasure.

To whom it may concern

It has come to my attention that your website "Hit Club Music Summer 2010" on this URL has potential to threaten my Alexa page ranking. As a consequence, this may cause our website to lose vital income which is generated from ad-space and it will not be tolerated. Due to the nature of your actions I am requesting a formal take-down of your website due to copyright infringement as the music posted on your "http://www.youtube.com" links is not endorsed by the rightful authors, as counseled by my attorney. Considering that you are also going through the New York University server, your actions may cost you and your educational institution unless you cease the aforementioned copyright infringement. If you continue hosting your service I will be forced to file a civil suit in which you will be charged for any lost advertisement revenue, averaging $0.52 per day.

In addition, your html markup shows your ineptitude in online web design, making your website an inefficient option for visitors who truly care about the Club Songs Industry. The listing of the dates on your monthly playlists go in ascending order rather than descending. This is just one of the many flaws of your clearly haphazardly designed website. However, I will give you neither my website URL nor my constructive criticism, for you are clearly trying to make money in an industry which doesn�t have room for your lack of music and website design knowledge. My page viewers have complimented me numerous times on the layout and content of my page.

You may contact me at this e-mail for any further concerns, although it is clear there is not much more to say. Your carelessness, inefficiency, and utter incompetence have gotten you into this hole, and unless you find a way out by October 31st, when my ad-space revenue comes in, further action will be taken. Also, for legal purposes, when and where was this website created? In the chance that it was created before September 30th, 2010, a law suit will be filed for the obvious decrease in revenue from my ads last month, totaling $7.34.

Thank you for your time,

HotNewClubSongs- A Forerunner in the Club Music Industry

Needless to say, I congratulated the student for achieving the goals of the assignment, and offered to cover the damages :-)

Student websites

2010-10-26T15:57:00.000-07:00

Can Crowdsourcing Scale? The Role of Active Learning

2010-10-25T21:55:00.000-07:00

Nobody is denying the fact that crowdsourcing becoming mainstream. People use Mechanical Turk for all sorts of applications. And many startups create business plans assuming that crowdsourcing markets will be able to provide enough labor to complete the tasks that will be posted in the market.

And at this point, things become a little tricky.

Can crowdsourcing markets scale? MTurk can tag a thousand images within a few hours. But what will happen if we place one million images in the market? Will there be enough labor to handle all of the posted tasks? How long will the task take? And what will be the cost?

Scaling by combining machine learning with crowdsourcing

Unless you can come up with ingenious ideas, the acquisition of data comes at a cost. To reduce cost, we need to reduce the need for humans to label data. To reduce the need for humans, we need to automate the process. To automate the process, we need to build machine learning models. To build machine learning models, we need humans to label data.... Infinite loop? Yes and no.

The basic idea is to use crowdsourcing in conjunction with machine learning. In particular, we leverage ideas from active learning: The idea behind active learning is to use humans only for the uncertain cases, and not for everything. Machine learning can take care of the simple cases, and ask humans to help for the most important and ambiguous cases.

We also need to have one extra thing in mind: Crowdsourcing generates noisy training data, as opposed to the perfect data that most active learning algorithms expect from humans. So, we need to perform active learning not only towards identifying the cases that are ambiguous for the model, but also figure out which human labels are more likely to be noisy, and fix them. And we also need to be proactive in identifying the quality of the workers.

In any case, after addressing the quality complications, and once we have enough data, we can use the acquired data to build basic machine learning models. The basic machine learning models can then take care of the simple cases, and free humans to handle the more ambiguous and difficult cases. Then, once we collect enough training data for the more difficult cases, we can then build an even better machine learning model. The new model will then automate an even bigger fraction of the process, leaving humans to deal with only the harder cases. And we repeat the process.

This idea was at the core of our KDD 2008 paper, and since then we have significantly expanded these techniques to work with a wider variety of cases (see our current working paper: Repeated Labeling using Multiple Noisy Labelers.)

Example: AdSafe Media.

Here is an example application, deployed in practice through AdSafe Media: Say that we want to build a classifier that recognizes porn pages. Here is an overview of the process, which follows the process of our KDD paper:

We get a few web pages labeled as porn or not.
We get multiple workers to label each page, to ensure quality.
We compute the quality of each labeler, fix biases, and get better labels for the pages.
We train a classifier that classifies pages as porn or not.
For incoming pages, we classify them using the automatic classifier.

If the classifier is confident, we use the outcome of the classifier
If the classifier is not confident, the page is directed to humans for labeling (the more ambiguous the page, the more humans we need)

Once we get enough new training data, we move to Step 4 again.

Benefits: Once the classifier is robust enough, there is no need to use humans to handle basic tasks. The classifier takes care of the majority of tasks, ensuring that the speed of classification is high, and that the cost is low. (Even at a 0.1 cents per page, humans are simply too expensive when we deal with billions of pages.) Humans are reserved to handle pages that are difficult to classify. This ensures that for the difficult cases there is always someone to provide feedback, and this crowdsourced feedback ensures that the classifier improves over time.

Other example: SpeakerText.

According to the press, SpeakerText is using (?) this idea: they use an automatic transcription package to generate a first rough transcript, and then use humans to improve the transcription. The high quality transcriptions can be then used to train a better model for automatic speech recognition. And the cycle continues.

Another example: Google Books.

The ReCAPTCHA technique is used as as the crowdsourcing component for digitizing books for the Google Books project. As you may have imagined, Google is actively using optical character recognition (OCR) to digitize the scanned books and make them searchable. However, even the best OCR software will not be able to recognize some words from the scanned books.

ReCAPTCHA uses the millions of users on the Internet (most notably, the 500 million Facebook users) as transcribers that fix whatever OCR cannot capture. I guess that Google reuses the fixed words in order to improve their internal OCR system, so that they can reach their goal of digitizing 129,864,880 books a little bit faster.

The limit?

I guess the Google Books and ReCAPTCHA project are really testing the scalability limits of this approach. The improvements in the accuracy of machine learning systems start being marginal once we have enough training data, and we need orders of magnitude more training data to see noticeable improvements.

Of course, with 100 million books to digitize, even an "unnoticeable" improvement of 0.01% in accuracy corresponds to 1 billion more words being classified correctly (assuming 100K words per book), and results in 1 billion less ReCAPTCHA's needed. But I am not sure how many ReCAPTCHA's are needed in order to achieve this hypothetical 0.01% improvement. Luis, if you are reading, give us the numbers :-)

But in any case, I think that 99.99% of the readers of this blog would be happy to hit this limit.

A Plea to Amazon: Fix Mechanical Turk!

2010-10-20T22:56:00.000-07:00

It is now almost four years since I started experimenting with Mechanical Turk. Over these years I have been a great evangelist of the idea.

But as Mechanical Turk becomes mainstream, it is now time for the service to get the basic stuff right. The last few weeks I found myself repeating the same things again and again, so I realized that it is now time to write these things down...

Mechanical Turk, It is Time to Grow Up

The beta testing is over. If the platform wants to succeed, it needs to evolve. Many people want to build on top of MTurk, and the foundations are lacking important structural elements.

Since the beginning of September, I have met with at least 15 different startups describing their ideas and their problems in using and leveraging Mechanical Turk. And hearing their stories, one after the other, I realized: Every single requester has the same problems:

Scaling up
Managing the complex API
Managing execution time
Ensuring quality

These problems were identified years ago. And the problems were never addressed.

The current status quo simply cannot continue. It is not good for the requesters, it is not good for the workers, it is not good for even completing the tasks. Amazon, pay attention. These are not just feature requests. These are fundamental requirements for any marketplace to function.

Amazon likes to present the hands-off approach to Mechanical Turk as a strategic choice: In the same way that EC2, S3, and many other web services are targeted to developers, in the same way Mechanical Turk is a neutral clearinghouse of labor. It provides just the ability to match requesters and workers. Everything else is the responsibility of the two consenting parties.

Too bad that this hands-off approach cannot work for a marketplace. The badly needed aspects can be easily summarized in four bullet points:

Below, I discuss these topics in more detail.

Requesters Need: A Better Interface To Post Tasks

A major task of a marketplace is to reduce overhead, friction, transaction costs, and search costs. The faster and easier it is to transact, the better the market. And MTurk fails miserably on that aspect.

I find it amazing that the last major change on Mechanical Turk for the requesters was the introduction of a UI to submit batch tasks. This was back in the summer of 2008. George Bush was the president, Lehman Brothers was an investment bank, Greece had one of the highest growing GDP's in Europe, Facebook had less than 100 million users, and Twitter was still a novelty. It would take 8 more months for FourSquare to launch.

It is high time to make it easier to requesters to post tasks. It is ridiculous to call the command-line tools user-friendly!

What is the benefit of having access to a workforce for microtasks, if a requester needs to hire a full time developer (costing at least $60K) just to deal with all the complexities? How many microtasks someone should execute to recoup the cost of development?

If every requester, in order to get good results, needs to: (a) build a quality assurance system from scratch, (b) ensure proper allocation of qualifications, (c) learn to break tasks properly into a workflow, (d) stratify workers according to quality, (e) [whatever else...], then the barrier is just too high. Only very serious requesters will devote the necessary time and effort.

What is the expected outcome of this barrier? We expect to see a few big requesters and a long tail of small requesters that are posting tiny tasks. (Oh wait, this is the case already.) In other words: It is very difficult for small guys to grow.

Since we are talking about allowing easy posting of tasks: Amazon, please take a look at TurkIt. Buy it, copy it, do whatever, but please allow easy implementation of such workflows in the market. Very few requesters have simple, one-pass tasks. Most requesters want to have crowdsourced workflows. Give them the tools to do so easily.

MTurk is shooting themselves in the foot by encouraging requesters to build their own interfaces and own workflow systems from scratch! For many many HITs, the only way to have a decent interface is to build it yourself in an iframe. What is the problem with iframe? Doing that, MTurk makes it extremely easy for the requester to switch labor channels. The requester who has build an iframe-powered HIT can easily get non-Turk workers to work on these HITs. (Hint: just use different workerid's for other labor channels and get the other workers to visit directly the iframe html page to complete the task.) Yes, it is good for the requester in the long term not to be locked in, but I guess all requesters would be happier if they did not have to build the app from scratch.

Requesters Need: A True Reputation System for Workers

My other big complaint. The current reputation system on Mechanical Turk is simply bad. "Number of completed HITs" and "approval rate" are easy to game.

Requesters need a better reputation profile for workers. Why? A market without a reputation mechanism turns quickly into a market for lemons: When requesters cannot differentiate easily good from bad workers, they tend to assume that every worker is bad. This results in good workers getting paid the same amount as the bad ones. With so low wages, good workers leave the market. At the end, the only Turkers that remain in the market are the bad ones (or the crazy good ones willing to work for the same payment as the bad workers.)

This in turn requires the same task to be completed from many workers, way too many times to ensure quality. I am not against redundancy! (Quite the opposite!) But it should be a technique for taking moderate quality input to generate high quality output. A technique for capturing diverse points of view for the same HIT. Repeated labeling should NOT be the primary weapon against spam.

The lack of a strong reputation system hurts everyone, and hurts the marketplace! Does Amazon want to run a market for lemons? I am sure that the margins will not be high.

Here are a few suggestions on what a worker reputation mechanism should include.

Have more public qualification tests:Does the worker have the proper English writing skills? Can the worker proofread?Most marketplaces (eLance, oDesk, vWorker, Guru), allow participants to pass certification tests to signal their quality and knowledge in different areas. Same should happen on Turk. If Amazon does not want to build such tests, let requesters make their own qualification tests available to other requesters for a fee? Myself, I would pay to use the qualifications assigned by CastingWords and CrowdFlower. These requesters would serve as the certification authorities for MTurk, in the same way that universities certify abilities for the labor markets.
Keep track of working history: For which requester did the worker work in the past? How many HITs, for what payment? For how long? Long history of work with reputable requesters is a good sign. In the real world, working history matters. People list their work histories in their resumes. Why not on MTurk?
Allow rating of workers: What is the rating that the worker received for the submitted work? Please allow requesters to rate workers. We have it everywhere else. We rate films, books, electronics, we rate pretty much everything.
Disconnect payment from rating: Tying reputation to acceptance rate is simply wrong. Currently, we can either accept the work and pay, or reject the work and refuse to pay. This is just wrong. We do not rate restaurants based on how often the customers refused to pay for the food! I should not have to reject and not pay for the work, if the only thing that I want to say is that the quality was not perfect. Rejecting work should be an option reserved for spammers. It should never be used against honest workers that do not meet the expectations of the requester.
Separate HITs and ratings by type: What was the type of the submitted work? Transcription? Image tagging? Classification? Content generation? Twitter spam? Workers are not uniformly good in all types of tasks. Writing an article requires a very different set of skills from those required for transcription, which in turn are different than the skills for image tagging. Allow requesters to see the rating across these different categories. Almost as good as the public qualification tests.
And make all the above accessible from an API, for automatic hiring decisions.

It cannot be that hard to do the above! Amazon.com runs a huge marketplace with thousands of merchants, for years. The guys as Amazon know how to design, maintain, and protect a reputation system for a much bigger marketplace. How hard can it be to port it to Mechanical Turk?

(Amazon's response about the reputation system... )

In a recent meeting, I asked this same question: Why not having a real reputation system?

The MTurk representative defended the current setup, with the following argument:

On the Amazon.com marketplace, the (large number of) buyers can rate the (small number of) merchants, but not vice versa. So, the same thing happens on MTurk. The (large number of) workers can rate the (small number of) requesters using TurkerNation and TurkOpticon. So the opposite should not happen: requesters should not rate workers.

I felt that the answer made sense: two-sided reputation systems indeed have deficiencies. They often lead to mutual-admiration schemes, so such systems end up being easy to hack (not that the current system is too hard to beat.) So, I was satisfied with the given answer... For approximately 10 minutes! Then I realized: Humbug!

There is no need for a reputation system for product buyers on Amazon.com's marketplace! It is not like eBay, where a buyer can win the auction and never pay! The reputation of the buyer on Amazon.com is irrelevant. On Amazon, when a buyer buys a product, as long as the credit card payment clears, the reputation of the buyer simply does not matter. There is no uncertainty, and no need to know anything about the buyer.

Now let's compare the Amazon.com product marketplace with MTurk: The uncertainty on MTurk is about the workers (who are the ones selling services of uncertain quality). The requester is the buyer in the MTurk market. So, indeed, there should not be a need for a reputation system for requesters, but the workers should be rated.

And at that point, people will protest: Why do we have the Hall of Fame/Shame on Turker Nation, why do we have TurkOpticon? Does Panos consider these efforts irrelevant and pointless?

And here is my reply: The very fact that we have such systems means that there is something very wrong with the Mturk marketplace. I expand below.

Workers Need: A Trustworthiness Guarantee for Requesters

Amazon should really learn from its own marketplace on Amazon.com. Indeed, on Amazon.com, it is not possible to rate buyers. Amazon simply ensures that when a buyer buys a product online, the buyer pays the merchant. So, Amazon, as the marketplace owner, ensures the trustworthiness of at least one side of the market.

Unfortunately, MTurk does not really guarantee the trustworthiness of the requesters. Requesters are free to reject good work and not pay for work they get to keep. Requesters do not have to pay on time. In a sense, the requesters are serving as the slave masters. The only difference is that on MTurk the slaves can choose their master.

And so, Turker Nation and TurkOpticon were born for exactly this reason: To allow workers to learn more about their masters. To learn which requesters behave properly, which requesters abuse their power.

However, this generates a wrong dynamic in the market. Why? Let's see how things operate.

The Requester Initiation Process

When new requesters come to the market, they are treated with caution by the experienced, good workers. Legitimate workers will simply not complete many HITs of a new requester, until the workers know that the requester is legitimate, pays promptly, and does not reject work unfairly. Most of the good workers will complete just a few HITs of the newcomer, and then wait and observe how the requester behaves.

Now, try to be on the requester's side.

If the requester posts small batches, things may work well. A few good workers do a little bit of good work, and the results come back like magic. The requester is happy, pays, everyone is happy. The small requester will come back after a while, post another small batch, and so on. This process generates a large number of happy small requesters.

However, what happens when the newcomers post big batches of HITs? Legitimate workers will do a little bit of work and then wait and see. Nobody wants to risk a mass rejection, which can be lethal for the reputation of the worker. Given the above, who are the workers who will be willing to work on HITs of the new, unproven requester? You guessed right: Spammers and inexperienced workers. Result? The requester gets low quality results, gets disappointed and wonders what went wrong.

In the best case, the new requesters will seek expert help, (if they can afford it). In the worst case, the new requesters leave the market and use more conventional solutions.

At this point, it should be clear that just having a subjective reputation system for requesters is simply not enough. We need a trustworthiness guarantee for the requesters. Workers should not be afraid of working for a particular requester.

Online merchant in the Amazon marketplace do not need to check the reputation of the people the sell to. Amazon ensures that the byers are legitimate and not fraudsters. Can you imagine if every seller on Amazon had to check the credit score and the trustworthiness of every buyer they sell to? What did you say? It would be a disaster? That people would only sell to a few selected buyers? Well, witness the equivalent disaster on Mechanical Turk.

So, what is needed for the requesters? Since the requester is essentially the "buyer", there is no need to have subjective ratings. The worker should see a set of objective characteristics of the requester, and decide whether to pick a specific posted HIT or not. Here are a few things that are objective:

Show speed of payment: The requester payment already goes into an Amazon-controlled "escrow" account. The worker should know how fast the requester typically releases payment.
Show the rejection rate for the requester: Is a particular requesters litigious and reports frequently the work of the workers as spam?
Show the appeal rate for the requester: A particular requester may have high rejection rate just due to an attack from spammers. However, if the rejected workers appeal and win frequently, then there is something wrong with the requester.
Disallow the ability to reject work that is not spam: The requester should not be able to reject submitted work without paying. Rejection should be a last-resort mechanism, reserved only for obviously bad work. The worker should have the right to appeal (and potentially have the submitted work automatically reviewed by peers). This should take out a significant uncertainty in the market, allowing workers to be more confident to work with a new requester.
Show total volume of posted work: Workers want to know if the requester is going to come back to the market. Volume of posted work and the lifetime of the worker in the market are important characteristics: workers can use this information to decide whether it makes sense to invest the time to learn the tasks of the requester.
Make all the above accessible from an API: Let other people build worker-facing applications on top of MTurk.

So, a major role of a marketplace is to instill a sense of trust. Requesters should trust the workers to complete the work, and workers should not have to worry about unreasonable behavior of the workers. This minimizes the search costs associated with finding a trustworthy partner in the market.

Let's see the final part that is missing.

Workers Need: A Better User Interface

As mentioned earlier, beyond trust, the other important role of the market is to minimize as much as possible transaction overhead and search costs. The transacting parties should find each other as fast as possible, fulfill their goals, and move on. The marketplace should almost be invisible. In this market, where requesters post tasks and the tasks wait for the workers, it is important to make it as easy as possible for workers to find tasks the workers want to work on.

Current Problem: Unpredictable Completion Times

Unfortunately, currently the workers are highly restricted by the current interface, in their ability to find tasks. Workers cannot search for a requester, unless the requester put their name in the keywords. Also workers have no way to navigate and browse through the available tasks, to find things of interest.

At the end, workers end up using mainly two main sorting mechanisms: See the most recent HITs, or see the HITgroups with the most HITs. This means that workers use priority queues to pick the tasks to work on.

What is the result when tasks are being completed following priorities? The completion times of the tasks follow a power-law! (For details on the analysis, see the preprint of the XRDS report "Analyzing the Amazon Mechanical Turk Marketplace".) What is the implication? It is effectively impossible to predict the completion time of the posted tasks. For the current marketplace (with a power-law exponent a=1.5), the distribution cannot even be used to predict the average waiting time: the theoretical average is infinite, i.e., in practice the mean completion time is expected to increase continuously as we observe the market for longer periods of time.

The proposed solutions? So easy, so obvious solutions, that it even hurts to propose them:

Have a browsing system with tasks being posted under task categories. See for example, the main page for oDesk, where tasks are being posted under one or more categories. Is this really hard to do?
Improve the search engine. Seriously, how hard is it to include all the fields of a HIT into the search index? Ideally it would be better to have a faceted interface on top, but I would be happy to just see the basic things done right.
Use a recommender system to propose HITs to workers. For this suggestion, I have to credit ba site on the Internet, with some nifty functionality: it monitors your past buying and rating history, and then recommends products that you may enjoy. It is actually pretty nice and helped that online store to differentiate itself from its competitors. Trying to remember the name of the site... The recommendations look like that:

It would be a good idea to have something like that on the Amazon Mechanical Turk. Ah! I remembered! The name of the site with the nice recommendations is Amazon! Seriously. Amazon cannot have a good recommender system for its own market?

Competition waits

Repeat after me: A labor marketplace is not the same thing as a computing service. Even if everything is an API, the design of the market still matters.

It is too risky to assume that MTurk can simply a bare-bones clearinghouse for labor, in the same way that S3 can be a bare-bones provider of cloud storage. There is simply no sustainable advantage and no significant added value. Network effects are not strong (especially in the absence of reputation), and just clearing payments and dealing with Patriot Act and KYC is not a significant added value.

Other marketplaces already do that, build API's, and have better design as well. It will not be difficult to get to the micro segment of the crowdsourcing market, and it may happen much faster than Amazon expects. Imho, oDesk and eLance are moving towards the space by having strong APIs for worker management, and good reputation systems. Current MTurk requesters that create their HITs using iframes, can very easily hire eLance and oDesk workers instead of using MTurk.

The recent surge of microcrowdsourcing services indicates that there are many who believe that the position of MTurk in the market is ready to be challenged.

Is it worth trying to challenge MTurk? Luis von Ahn, looking at an earlier post of mine, tweeted:

MTurk is TINY (total market size is on the order of $1M/year): Doesn't seem like it's worth all the attention.

I will reply with a prior tweet of mine:

Mechanical Turk is for crowdsourcing what AltaVista was for search engines. We now wait to see who will be the Google.

Mechanical Turk and Data Driven Journalism: The Case of ProPublica

2010-10-15T08:41:00.000-07:00

Last year, in a Mechanical Turk Meetup in New York, I met with Amanda Michel of Propublica, a "non-profit newsroom that produces investigative journalism in the public interest".

ProPublica had a set of very interesting ideas on how to use crowdsourcing, to improve their practices and increase their reporting reach. Amanda had some great ideas on how to use crowdsourcing, starting with operational aspects of data-driven journalism, up to more ambitious goals. What was common, in all efforts, was a simple goal: Find, reveal, and fight corruption. When you meet with such people, it is hard not to be inspired. So, over last year I kept interacting with ProPublica on how to use Mechanical Turk for their goals.

Take a simple example. ProPublica was facing a significant data integration problem. For one of their projects, they wanted to extract data from hundreds of different city, country, and state databases. Needless to say, building an integration system of such scale is difficult and beyond the reach of many advanced IT companies. Definitely not a problem that a journalism organization could solve for the purpose of writing a single story. How Mechanical Turk could help? The Turkers could be the ones interacting with the databases, creating an effective, human-powered hidden-web crawler, that was up and running in a couple of days.

Mechanical Turk became quickly an integral part of ProPublica's newsroom operations. It became so valuable, that ProPublica today published an article describing how they are using Amazon�s Mechanical Turk to do data-driven reporting and they made public the ProPublica's Guide to Mechanical Turk. It goes step by step through all the challenges that a newcomer on Mechanical Turk may face, and shows how to best approach the tool. Needless to say, these links are being passed around on Twitter like crazy.

ProPublica is a great case study, not because they did something artistic or fancy, but because they kept their focus razor-sharp in integrating crowdsourcing to their operations. The 10,000 sheep will be passed around virally and inspire ideas, but mainstream adoption will come after reading success stories like the one from ProPublica. At the end of the day, people want to know how to get things done.

I kept the best part for the end. From this article:

ProPublica has received a Special Distinction Award from the Knight-Batten Awards for Innovations in Journalism. ProPublica's Distributed Reporting Project was honored for "systematizing the process of crowdsourcing, conducting experiments, polishing their process and tasking citizens with serious assignments." The judges called it "a major step forward with how we understand crowdsourcing."

Be a Top Mechanical Turk Worker: You Need $5 and 5 Minutes

2010-10-11T22:15:00.000-07:00

The current reputation system on Mechanical Turk is simply inadequate. The only built-in reputation metrics are the number of completed HITs and the approval rate.

Some people believe that they are adequate as a basic filtering mechanism. They are not.

For example, ask for all workers in your HITs to have 1000 completed HITs and 99% approval rate. You believe that you will only get high quality workers? You are wrong!

I tried to filter workers using just these metrics. I failed. Spammers got me again. (And once in, spammers submit a lot of crap. It costs nothing.) I questioned why. How can it be? And then I realized: It is trivial to beat these metrics.

Let's see the effort it takes to beat the system.

The mission: Become a top Turker, 100% approval rate and 1000 completed HITs.

Step 1: Login as a requester. Post a task, with 1000 HITs. Each HIT pays 1 cent. Total cost: $15. Out of these, $10 go to the worker, $5 go to Amazon. The title of the HIT: "Write a 500 word review". No sane worker will touch these HITs. Done. Logout.
Step 2: Login as worker, using a different email. Complete and submit the 1000 HITs created in Step 1. You just need to click submit 1000 times. Bored? iMacro and Greasemonkey can help. Done. Logout.
Step 3: Login as a requester again. Approve all submitted HITs. Pay the $15. Amazon gets $5. The worker account has the remaining $10. Done. Logout.

Your worker account is a top Turker now. 1000 completed HITs and 100% approval rate. Congratulations! You have a license to spam.

The Explosion of Micro-Crowdsourcing Services

2010-10-10T21:18:00.000-07:00

In my last post, I expressed my surprise for the sudden explosion of the research-oriented workshops in computer science conferences that are explicitly focused on the concept of crowdsourcing.

I should also note though, that there is a parallel explosion of similar micro-crowdsourcing services. Here is a list of services that I have ran into:

Some of the companies above are serious, some are new and upcoming, some are copycats, and some are there just to facilitate spamming.

I thought of doing a more detailed comparison (similar to the report that Brent Frei prepared last year for the more general area of paid crowdsourcing) but then I realized that I do not trust enough half of these companies to even give them my email.

This growing list makes it clear that we enter the bubble period. Bubbles are not necessarily negative. During bubble periods you see many innovations coming into the industry from many different parties. While most of the entrants in the market will die sooner rather than later, I except to see interesting things coming out of this.

Do not forget that the dotcom bubble generated the Pets.com failures but also gave birth to Google, who replaced the early dominant players, such as Lycos and Altavista.

The Explosion of Crowdsourcing Workshops

2010-10-08T22:22:00.000-07:00

Over the last couple of years, there has been an explosion of workshops that look at the topic of crowdsourcing from the academic point of view, within the broader computer science field. Here are the ones that I am aware of:

Human Computation Workshop (HCOMP 2009), with KDD 2009
Workshop on Crowdsourcing for Search Evaluation, with SIGIR 2010
Second Human Computation Workshop (HCOMP 2010), with KDD 2010
Advancing Computer Vision with Humans in the Loop (ACVHL), with CVPR 2010
Creating Speech and Language Data With Amazon�s Mechanical Turk, with NAACL 2010
Computational Social Science and the Wisdom of Crowds, with NIPS 2010
The People�s Web Meets NLP: Collaboratively Constructed Semantic Resources, with COLING 2010
Workshop on Ubiquitous Crowdsourcing, with UBIComp 2010
Enterprise Crowdsourcing Workshop, with ICWE 2010
Collaborative Translation: technology, crowdsourcing, and the translator perspective, with AMTA 2010
Workshop on Crowdsourcing and Translation,
Crowdsourcing for Search and Data Mining, with WSDM 2011

(If you think that I missed a relevant workshop, drop me a line, and I will add it to the list above)

In addition to the workshops above, we also have the CrowdConf 2010 conference, organized by CrowdFlower, with some academic presence but overall targeted mainly to industry.

Yes, one workshop in 2009, followed by ten (at least!) additional workshops in 2010, and who knows how many more in 2011. (I am already aware of 3 planned workshops, in addition to the one in WSDM 2011.)

I am deeply interested in the topic and I already feel that I am losing track of the venues that I need to follow.

Mechanical Turk Requester Activity: The Insignificance of the Long Tail

2010-10-07T22:47:00.000-07:00

The Pareto principle says that 80% of the effects come from 20% of the causes. It is a favorite anecdote to cite that 20% of the employees in an organization do 80% of the work, or that 20% of the customers are those that generate 80% of the profits.

In online settings, such inequalities are often amplified. For Wikipedia we have the 1% rule, where 1% of the contributors (this is 0.003% of the users) contribute two thirds of the content. In the Causes application on Facebook, there are 25 million users, but only 1% of them contribute a donation.

So, adapting this question for Mechanical Turk, we want to see: What is the distribution of activity across requesters?

The Activity Distribution: The (Insignificance of the) Long Tail of Requesters

To analyze the level of participation, for the XRDS paper, we took the requesters that posted a task on Mechanical Turk from January 2009 until April 2010, and we ranked them according to the total reward amount of the posted HITs. Then, we measured what percentage of the rewards comes from the top the requesters in the market. Here is the resulting plot:

Indeed, the result shows that Mechanical Turk is closer to the "1% rule" of Wikipedia, than to the general 80-20 principle. As in Wikipedia, the top 1% of the requesters, contribute two thirds of the activity in the market.

By reading the graph, we see the following:

Castingwords, the top requester across the 10K requesters in the dataset, accounts for 10% of the dollar-weighted activity (!).
The top 0.1% of the requesters (i.e., the top-10 requesters) account for 30% of the dollar-weighted activity.
The top 1% of the requesters account for 60% of the dollar-weighted activity.
The top 10% of the requesters account for 90% of the dollar-weighted activity.
The long tail of the 90% of the requesters is effectively insignificant.

A closer look at the distribution of requester activity shows that the activity per requester follows roughly a log-normal distribution.

The average level of posted rewards is $58. This corresponds to an average level of activity of just four dollars per month.
The median is just $1.60. Yes, this is not a typo: 1.6 dollars. In other words, 50% of the requesters never post more than a couple of dollars worth of tasks.
Only a small fraction of requesters (less than 1%) posted 1000 dollars worth of tasks or more over the period from January 2009 till April 2010.

The lognormal distribution of activity, also shows that requesters increase their participation exponentially over time: They post a few tasks, they get the results. If the results are good, they increase by a percentage the size of the tasks that they post next time. This multiplicative behavior is the basic process that generates the lognormal distribution of activity.

I would like to try is to check if this model indeed corresponds to reality. Do we see a geometric growth in activity as the requester stays in the market for longer? Do we observe "deaths" of requesters? (The Fader-Hardie model may be a nice, simple model to try.) What is the expected future activity of a requester?

Such questions may be useful for guiding decisions of workers when deciding whether to invest time and effort to get a good reputation for a given requester (e.g., by completing qualification tests or completing the basic HITs that unlock access to the "protected" HITs.)

What Tasks Are Posted on Mechanical Turk?

2010-10-07T21:28:00.000-07:00

A few months back, I got an invitation from Michael Bernstein (of Soylent fame) to write a small article about Mechanical Turk for the student magazine of ACM, the ACM XRDS (aka Crossroads). I could have written a summary of past research, a position paper, or anything that I find interesting.

Instead of summarizing and resubmitting already published material, I decided to push myself and start analyzing some data that I have been collecting about the Mechanical Turk marketplace. In the past, I analyzed the data about the demographics of the workers on Mechanical Turk. However, we have limited analysis for the requester side of the market, and for the type of tasks being posted.

My goal was to put some very preliminary analysis in place, just to scratch the surface of a variety of a questions that I have heard over time. Hopefully this will push me to start working more towards getting the answers, and will inspire some interesting new questions for the students and others that read the article. A preprint of the paper is available through the NYU Faculty Digital Archive and the print version should appear sometime early in 2011.

Data Set

I have been collecting data about the marketplace through my Mechanical Turk Tracker. The tracker collects complete snapshots of the marketplace, every hour, starting from January 2009. For the analysis, I took the data from the period of January 2009 till April 2010: The snapshots has a total of:

165,368 HIT groups
6,701,406 HITs
9,436 requesters
$529,259 rewards

These numbers, of course, do not account for the redundancy of the posted HITs, or for HITs that were posted and disappeared between our hourly crawls. Nevertheless, they should be good approximations (within an order of magnitude) of the activity of the marketplace.

Top Requesters

The first question that I looked at was an analysis of the tasks that are being posted on Mechanical Turk. One way to understand what types of tasks are being completed in the marketplace is to find the �top� requesters and analyze the HITs that they post. By ranking requesters according to the sum of the posted rewards, we get the following list, showing the level of activity and the type of tasks that these requesters post. (Note: To avoid skewing the data towards one-shot requesters, I excluded from the list a requesters that were active only for small periods of time or requesters that posted only a small number of HITs. The goal was to find not only the requesters that post big tasks, but also requesters that do that consistently over time.)

So, transcription, classification, and content generation seems to be a common activity on Mechanical Turk. This indicates that people have developed sufficient best practices and can actually get quality work done. (If not, they would not be posting so many tasks.)

Top Keywords

We also wanted to get a feeling of the tasks that are being posted in the market, across all requesters. The table below shows the top-50 most frequent HIT keywords in the dataset, ranked by total reward amount, # of HITgroups, and # of HITs.

Beyond the tasks identified before, we also see data collection, image tagging, website feedback, and usability tests to be common tasks being posted in the marketplace.

In future posts, I will post further analysis of other aspects of the AMT marketplace.

Worker Evaluation in Crowdsourcing: Gold Data or Multiple Workers?

2010-09-15T18:41:00.000-07:00

Evaluating the quality of workers on crowdsourcing environments is standing problem.

The two most common approaches for dealing with the problem are:

Use "gold" data: Give to the workers questions for which we already know the answers and see how the workers are performing. (Crowdflower is using this approach.)
Use multiple workers: Give the same answer to multiple workers and then use a latent class model ala Dawid & Skene to estimate the quality of the workers.

The nice thing about the two approaches is that they can be seamlessly combined into a unified algorithm.

What was not clear to me, though, was the relative importance of the two. How much better and faster can we estimate the quality of the workers if we use gold data? What is the rate of improving the quality estimation as we add more gold data? Generating high-quality gold data is an expensive process, so having good answers to these questions is important.

Being a professor, the moment these questions came up, I knew what I had to do: Ask a PhD student to give me the answers! (Thanks Jing!) So, I am just the messenger here, Jing did all he work and the analysis. You know where to send your thanks.

The assumptions: We have examples belonging to 2 categories. The examples are equally distributed in the two categories (i.e., 50% in each). We created a set of workers with their quality picked randomly and uniformly from the range (55% correct) to (100% correct), for an average quality of ~77%. The workers assigned (noisy) labels to the examples, with an accuracy directly proportional to their quality.

We examined the performance of the Dawid & Skene algorithm, which we modified to take into consideration the existence of gold data. We measured two things:

Classification error: How well the algorithm estimates the correct class of the examples
Quality estimation error: How well the algorithm estimates the quality of the workers

We experimented with having 0% gold examples in the data, 25% gold, 50% gold, and 75% gold.

Results on classification error

So, we measured the accuracy of estimating the correct class of each example. The results are listed below:

3 workers per example

5 workers per example

10 workers per example

One immediate observation is that the value of having gold data is limited when we have significant number of workers per label. With 10 workers per example, no matter if we have gold data, the difference is minimal. Even with just 5 workers, the additional value of gold data is small.

The cases where it makes sense to use gold data is when we have only small number of workers per label. (Not an uncommon case!)

An interesting observation, though, is that we can achieve the same effect by simply forcing workers to work on more examples. Once a worker has given us 30 answers, the completely unsupervised algorithm can work almost as well as the algorithm that uses 75% gold data. This holds even when we have just 3 workers per example.

Of course, on an environment like Mechanical Turk, forcing workers to work on a large number of HITs may not be feasible. But we can always bundle multiple questions in a single HIT, achieving the same result.

OK, so gold data do not seem to be very useful in for getting better accuracy in class estimation.

But, it should help in estimating the quality of workers, right?

Results on worker quality estimation

For the quality estimation, we also calculated the error when having 100% gold examples. (This is the lower bound for the estimation error, of course.)

3 workers per example

5 workers per example

10 workers per example

As expected, with 10 workers per example, we gain almost nothing in terms of quality estimation when we use gold data.

With 3-5 workers per example, having gold data improves the quality estimation in a rather consistent manner. Again, though, we observe that if we have each worker completing a large enough number of assignments, we can get most of the benefits of having gold data, without actually having gold data.

Why gold data then?

So, given the results above, someone would ask: Why do we even need gold data? The unsupervised approach seems to work very well!

In reality there are a few reasons for which we may still need to have gold data:

Imbalanced datasets: When we have very imbalanced data sets, the estimation becomes more challenging. For imbalanced data, we need to quickly and preemptively test workers using data from all categories, rather than waiting for the occasional object from the minority category to appear. To give an example: if we monitor a security camera trying to detect the presence of people in prohibited areas, we want to ensure that the workers will be tested early on with images that have people in them. Otherwise it may take a long time to get a reliable estimate of their ability to classify correctly examples from the minority class.
Very low quality of workers: When workers have very low quality, we need more workers per example and more labels per worker to replicate the results above. In this case, having gold data allows us quickly to get rid of the workers that do not meet quality standards. This is very useful on high-noise environments like the "unprotected" Amazon Mechanical Turk marketplace (by unprotected I mean without using qualification tests or other quality assurance mechanisms).
Giving confidence to non-technical people: If you say that you test the workers with known examples, everyone understands the process. If you say that you rely on agreement between workers, or on latent class models ("what?") and on expectation maximization or Bayesian estimation ("come again?") , most people will start feeling uncomfortable. Everyone understands random tests, not everyone is willing to let unsupervised methods to direct the quality assurance process. So, even if the gold examples do not help much, it is a very reassuring factor for people that just want to know that there is a familiar, understandable, and easy-to-explain quality control mechanism in place.
Calibrating results and giving feedback: One of the final reasons for having gold data is to be able to calibrate workers and give them feedback about the expected coding standards. For example, when rating pages as porn or not and into degrees of severity, different people have different levels of sensitivity. If we have enough "sensitive" workers in the workforce, we may end up with results that are consistent but shifted upwards in terms of severity. (Or vice versa if the coders are more tolerant, the results may be shifted downwards.) This can, incorrectly, give the impression that all data collected through crowdsourcing are wrong. However, if the final user of the data provides a few gold data as anchor points, the Dawid & Skene code gives back results that are more in line with expectations. At the same time, these gold data points can be used to give immediate feedback to the workers about their errors and implicitly direct them to use the expected rating guidelines and self-calibrate.

In practice, the last two reasons are often more important than the technical aspects of estimation. So, before starting any big crowdsourcing annotation project, spend some time and create some gold data. Or, alternatively, take a small dataset and label it using a large number of workers per example. Then verify the outcome, correct and calibrate some of the unexpected results, and run Dawid & Skene again. The generated data will be close enough to gold. Having such gold data will pay back the effort and cost multiple times during the overall process.

Analytics for Class Lectures

2010-09-14T08:52:00.000-07:00

The classes for the new academic year have started, so naturally I started thinking about teaching-related topics.

Mining video interactions

A few days back, FXPal released TalkMiner, a system for indexing and searching video of lecture broadcasts. One of the interesting ideas is that it is possible to mine the interactions of students with the video, to see what are the topics of interest for the students, what parts of the class get skipped, and so on. From the blog post of FXPal:

The Berkeley webcasting system (developed by our president Larry Rowe while he was a professor there) showed that

� students almost always watched the lectures on-demand rather than in real-time, and they rarely watched the entire lecture. Students use the webcasts to study for exams � we could see this clearly by patterns of usage � and, they primarily wanted to review selected material covered by the instructor. In one class we discovered that for over 50% of the lectures, students watched less than 10 minutes from a 50-minute lecture and students watched the entire lecture only 10% of the time. Consequently, for using the system, effective search is a big issue.

At Stern, all the classes get recorded and are available to students for reviewing the class material. The students get access to a layout like the following and have the ability to rearrange the layout, emphasizing the slides, or the video. (You can see a lecture of mine; login: scribe and password: Scribe987!)

It seems to be a natural next step to show to the instructor the patterns of interaction that students have with the videos. It would be very interested to see what parts of the class go largely unexamined and which ones are played again and again. Needless to say, these are either complicated topics, or topics that the instructor did not explain clearly.

Mining search queries using transcripts

Another interesting idea is to also have transcripts of the class. (For example, for this lecture [login: scribe and password: Scribe987!] see the transcript, done by CastingWords for $0.75/min.) This would allow students to search the class not only using text in the slides but also to recall particular points of the class discussion. This is especially important for courses that have a significant component of in-class discussion. We already know, from web search, that query logs are important source of information. Doing the same for class content would easily identify what students are looking for in the class recordings.

One problem with transcription is that it is rather expensive. CastingWords and SpeakerText seem to charge one or two dollars per minute for human-verified transcriptions. (Fully-automatic solutions are not ready for prime time, as the automatic transcription of these YouTube videos shows. Make sure to click the "cc" button and then "transcribe audio".) With approximately 28 lectures a semester, 75 minutes each, at 1-2 dollars per minute, we have a cost of $2000 to $4000 per semester. At this cost level, it is certainly more beneficial to hire an extra TA rather than provide the transcription of the lecture to the students.

Mining class participation

Another thing that I would love to have is the ability to transcribe not only what the instructor said but also who are the students that contributed to the discussion, together with what they said. This would allow not only to track and quantify participation but also uncover some patterns that may not be obvious to the instructor.

For example, take a look at this diagram below, created as part of the yearly teaching evaluation that we undergo at Stern:

The diagram was created by an evaluator who sat in my class, tracked the composition of the student body, where each student was sitting in the amphitheater, how many times they raised their hand, and how many times I asked them to answer a question. (To answer the inevitable question: No, the teaching feedback is not focused only on such analyses. In my earlier years, the feedback was focused more on substantial issues, e.g., structuring lectures and discussions, encouraging participation, etc. Now, with feedback and experience, the more substantial and important issues are addressed. So we focus on such, seemingly more superficial, but also important, stuff...)

The results? I was paying significantly more attention to the left part of the amphitheater: I asked 80% of the time students sitting in the left, and only 20% of the time I asked students on the right. Also, the percentage of female students participating in the discussion was significantly lower: 50% for male students participated, but only 21% of the female students did.

These are patterns that are hard to understand while teaching, but would be easier to find out if we had detailed transcripts of the class discussion together, potentially, with a standardized seat chart. I was also told that some universities (the rumor is about Harvard Business School) use software to track student participation. However, I was not able to locate any such software offerings.

Moving forward

The ability to videotape lectures has been around for a while and is being used extensively for distance learning applications. (Columbia Engineering had a well-established distance learning program when I joined the PhD program back in 1999.) However, it was mainly a broadcast mechanism, and not a medium for providing feedback to the instructor (and even to the students who can see that they are lacking in terms of participation).

It would be interesting to start having such technologies for providing feedback on teaching. Analytics have been changing many industries. Education has been surprisingly behind in that respect.

Reputation Integration and the Future of Reviews

2010-08-07T22:29:00.000-07:00

Last week I was at Google for the annual Google Faculty Summit. While discussing research challenges related to social media and shopping, a common theme and questions emerged: How can we evaluate the trustworthiness of the reviews that abound on the Internet?

Past Performance predicts Future Performance

Current solutions focus on the trustworthiness and history of a reviewer in each site. For example, Amazon has the reviewer rank, which is computed using the amount of reviews contributed, the helpful votes that they amassed, and other secret-sauce factors. Other sites, like Yelp, follow similar approaches to identify the best reviewers.

Of course, knowing the good reviewers is very valuable: Unlike investments, past performance is a strong indicator of future performance. Reviewers that wrote good reviews in the past are likely to write good reviews in the future. Or, more general, high-quality users in the past are likely to be high-quality in the future.

So, problem solved! We just need to know which user has high quality!

Network Effects and Closed Reputation Platforms

Well, at this point we have a problem. Today, we treat site-specific user profiles as separate individuals. A profile of a user on Amazon is not connected to the corresponding reviewer profile in Epinions, in NewEgg, in B&H. So, reviewers that have written tens of reviews and amassed thousands of helpful votes will be insignificant newbies if they decide to write some reviews on B&H website. Similarly, a person that has contributed plenty of reviews and discussions on Chowhound over the years, will be an insignificant newbie on Yelp. The result? We cannot trust the reviews of these individuals, even if they have proven themselves trustworthy in the past!

This is a lock-in associated with network effects, which is similar to the lock-in that happens under closed and proprietary standards. For example, Microsoft has achieved domination in Office Productivity software by keeping proprietary the file formats for Office. Since no other office productivity suite could inter-operate with Office, smaller players could simply not compete: the minority of users that did not use Office could not exchange files with the Office users. Under such scenarios, either we see a market split into isolated markets (the case of reputation-based sites today), or a single dominant player (e.g., in Office).

Closed Standards and Networks Effects

Interestingly enough, under closed standards, when the market ends up being fragmented, this is not optimum. An excellent example is the SMS market in the United States. Before 2000, the different telecoms did not allow their subscribers to send SMS messages to subscribers of other companies. The main rationale was to force users to adopt the network already chosen by their friends, if they wanted to text each other. So the market looked like that:

Interesting approach but the result was not ideal: texting in the US was essentially non-existent before 2000. (I vividly remember when I arrived in the US how nobody was using SMS to communicate with each other. In Europe sending SMS was commonplace.) However, once the networks decided to cooperate and allow SMS to flow freely across networks, the market took off, attracting more players and being much more useful.

In other words, if we do not have a monopoly, closed networks are suboptimal. Fragmented markets for goods with network effects are almost never optimal, even for the current dominant players.

The Need for Open Reputation and Reputation Integration

I believe that we see a similar case in the reputation identities. Identities are fragmented across sites and users have little incentive to contribute high-quality content in sites in which they do not have established presence: Nobody pays attention to them in any case.

This also makes it difficult to start from scratch any website that requires the existence of trustworthy reviews in order to attract viewers. Visitors will not come as there are no trustworthy reviews, and reviewers already established in other sites will not join.

So, it is important to start thinking on how to integrate reputations across different websites. It is simply not optimal to have fragmented identities. Even though there are privacy concerns for anonymous profiles, there should be at least the capability to connect identities across sites for users that do not try to preserve their anonymity. By integrating profiles across websites, we can allow reputation to flow across websites and creating a better, comprehensive profile of the participants in today's Internet.

This can allow participants to build their reputation profiles without worrying about lock in. OpenID moves towards the right direction. Next versions should allow explicit, distributed connection of profiles, without requiring a dominant players to control the profile. (Thank you for the offer, Facebook. I will pass.)

Third-party services can play this role as well. By identifying profiles across sites that belong to the same individual, we can quickly learn about the identity of a new contributor. The history can follow the users that are not worried about anonymity. Such strong reputation signals can help improve any existing site that relies on user contributed content. In the presence of strong reputations, low-quality contributors will simply never have a chance of getting a dominant position in the marketplace.

As I mentioned in my earlier blog post, lack of credible reputation mechanisms simply degenerates any market into a market for lemons. In the attention economy, lack of strong reputation signals simply gives the incentives to spammer to come and pollute. Reputation integration mechanisms can solve this issue.

Cross-posted at the Reppify blog (disclaimer: I am an advisor for Reppify)

Mechanical Turk, Low Wages, and the Market for Lemons

2010-07-27T20:18:00.000-07:00

In HCOMP this year, one of the memorable and discussed presentations (although highly unconventional) was by M. Six Silberman who discussed the "Sellers' problems in human computation markets". The basic question: can we protect the workers there from exploitation and from sweatshop salaries?

Luis von Ahn posted a similar post on his blog. In the comments of the blog post, someone suggested that the low wages on Mechanical Turk is simply the result of high supply of workers and low demand for their work. As there is more supply, the salaries drop. And having minimum wages, would interfere with the free market.

I actually disagree with this interpretation. First of all, there is no oversupply of labor on Mechanical Turk. The distribution of completion times (follows a power law), suggests that the market operates at maximum capacity. My gut instinct actually tells me that there are not enough workers available for the posted work, not vice versa.

I can hear the protests: If there is not enough supply of workers, why don't requesters simply increase the offered prices?

My explanation: The requesters already pay minimum wages for work that is worth minimum wage. How is that possible given the effective hourly rate of $2/hour?

The basic problem: Spammers. Given that many large tasks attract spammers, most requesters rely on redundancy to ensure quality. So instead of having a single worker to do a task, they get 5 workers to work on it. This increases the effective rate from $2/hr to $10/hr.

Effectively, what Amazon Mechanical Turk is today is a market for lemons, following the terminology of Akerlof's famous paper, for which he got the 2001 Nobel prize.

A market for lemons is a market where the sellers cannot evaluate beforehand the quality of the goods that they are buying. So, if you have two types of products (say good workers and low quality workers) and cannot tell who is whom, the price that the buyer is willing to pay will be proportional to the average quality of the worker. So the offered price will be between the price of a good worker and a low quality worker. What a good worker would do? Given that good workers will not get enough payment for their true quality, they leave the market. This leads the buyer to lower the price even more towards the price for low quality workers. At the end, we only have low quality workers in the market (or workers willing to work for similar wages) and the offered price reflects that.

This is exactly what is happening on Mechanical Turk today. Requesters pay everyone as if they are low quality workers, assuming that extra quality assurance techniques will be required on top of Mechanical Turk.

So, how can someone resolve such issues? The basic solution is the concept of signalling. Good workers need a method to signal to the buyer their higher quality. In this way, they can differentiate themselves from low quality workers. Unfortunately, Amazon has not implemented a good reputation mechanism. The "number of HITs worked" and the "acceptance percentage" are simply not sufficient signalling mechanisms.

Here are some ideas:

Allowing workers to get endorsements from reputable requesters (to avoid scam rings like on eBay)
Allowing requesters to post machine readable feedback on the performance of the workers, disconnecting evaluation from the approval rate.
Certifications and qualification tests that indeed measure ability on different tasks (e.g., language abilities, reading comprehension tests, etc)
Publishing the reputation history of the workers, so that requesters can evaluate the quality of the worker.

Of course, similar measures can be adopted for requesters! There is a symmetric market for lemons on that side! Scam requesters post HITs, behave badly, and cause good workers to avoid any newcomer. New requesters then get only low quality workers, get disappointed with the quality of the results and they leave the market.

In other words, Amazon can only gain by taking the time to build a more robust reputation system on top of Mechanical Turk. Trust is at the very core of marketplaces. If Mechanical Turk wants to "grow up", then a good reputation system for both sides of the market is grossly overdue.

Peer Reviewing for Oral Presentations?

2010-07-27T10:39:00.000-07:00

Everyone who has attended a conference knows that the quality of the talks is very uneven. There are talks that are highly engaging, entertaining, and describe nicely the research challenges and solutions. And there are talks that are a waste of time. Either the presenter cannot present clearly, or the presented content is impossible to digest within the time frame of the presentation.

So, my question is: Why don't we have peer reviewing for oral presentations?

We already have reviewing for the written part. The program committee examines the quality of the written paper and vouch for its technical content. However, by looking at a paper it is impossible to know how nicely it can be presented. Perhaps the seemingly solid but boring paper can be a very entertaining presentation. Or an excellent paper may be written by a horrible presenter.

Why not having a second round of reviewing, where the authors of accepted papers submit their presentations (slides and a YouTube video) for presentation to the conference. The paper will be accepted and be included in the proceedings anyway but having a paper does not mean that the author gets a slot for an oral presentation.

Under an oral presentation peer review, a committee looks at the presentation, votes on accept/reject and potentially provides feedback to the presenter. The best presentations get a slot on the conference program. This also allows the conference to accept more papers that are worthy of inclusion to the proceedings, without worrying about capacity constraints.

Some other side benefits of this scheme:

Presentations are accessible in an archival format
Authors have hard incentives to be better presenters
The time of the attendees in conferences is not wasted in clearly sub-par presentations.

And if someone says that this system is biased towards good and sleek presenters, I would argue that the system is already biased towards good authors. A well-written paper will eventually have a higher impact than one that is badly written. Same thing for presentations.

Learning to communicate properly the results of our research should be a goal, not an afterthought.

Liveblogging from HCOMP 2010

2010-07-26T12:31:00.000-07:00

Following last year's practice, I am blogging about the workshop this year as well. (If I do it well for a few more years, I hope to be a tenured blogger for HCOMP.)

The workshop was very well-attended, despite the strong competition for attention (there are 14 workshops at KDD this year).

8.40am, Invited Talk

The workshop started with an invited talk by Ross Smith from Microsoft, who talked about "Using Games to Improve Productivity in Software Engineering". He described how Microsoft used games internally to improve the quality of its products.

He particularly emphasized the attempts on using engineers to help with the localization/internationalization of the Microsoft products. One of the things that was interesting was the pride that engineers had when translating the messages into their own native language. The "my-work-is-in-the-product-that-you-are-using-mom"-factor was a strong motivation for engineers to contribute their time and effort to such volunteer efforts.

Ross also covered a variety of behavioral aspects of the process. For example, leaderboards has different effect, depending on how competitive the workers are in this particular country. When people compete, they have a positive factor. However, if someone has big difference than the rest, this is typically a demotivating factor, as many workers know that they cannot reach the top in any case.

Another interesting factor is that games should not be similar to the duties of the worker. If a programmer writes C++, then playing a game that requires the worker to write C++ is bad. First, the programmer may spend time in the game that he would have otherwise spend programming. Second if a worker is way too good in a task, and spends a lot of time there, other workers cannot compete easily and get demotivated.

An interesting aspect going forward is that games are increasingly being used to tap into the "discretionary" time of the workers, so there is now competition to make the games more interesting, more attractive, more meaningful etc. For example, currently workers accumulate points in the games, and their reward is that these points are translated into dollars that can be donated to disaster relief efforts.

Finally, games should not come with a mandate from the management. (Luis von Ahn mentioned that when you say "play the game" people do not.) The counterexample was Japan, in which the linguistic pride to get the applications translated into Japanese worked (despite? due to?) the clear mandate from the management to play the game that aids into the localization of Microsoft products.

9:10am, Session 1: Market Design

Task Search in a Human Computation Market
Lydia Chilton (University of Washington) (*** presenting)
John Horton (Harvard University)
Robert Miller (MIT CSAIL)
Shiri Azenkot (University of Washington)

The paper described how workers tend to search for tasks on Amazon Mechanical Turk. The analysis indicated that "Most HITs Available" and "Most Recently Posted" are the most commonly ranking techniques for users to find tasks. By monitoring HITs and scraping the website every 30 seconds, the authors figured out how quickly different tasks are being done.

Plus they run a survey, trying to target rankings that are NOT frequently chosen by workers and compared "best case" scenario and "worst case" scenario. Interestingly enough, there is almost a 30x factor in the rate of completion. This explains all the gaming that is going on today, where major requesters keep posting HITs within their HITgroups to keep their HITs in the first page.

This paper really highlights the negative aspects of the prioritization schemes currently used on Mechanical Turk. Allowing workers to find easier tasks to work on, and employing some randomization in the presentation, Mechanical Turk can really contribute to more predictable completion times for the tasks.

The Anatomy of a Large-Scale Human Computation Engine
Shailesh Kochhar (Metaweb Technologies) (*** presenting)
Stefano Mazzocchi (Metaweb Technologies)
Praveen Paritosh (Metaweb Technologies)

This paper described Rabj, the platform used by Metaweb to improve the quality of FreeBase by having humans to look at the ambiguous cases, that cannot be handled well by automatic techniques. The basic goal is to take a system that is 99% accurate, and improve precision well above 99%

Metaweb did not use Mechanical Turk for this task. Instead, they hired people through oDesk, by first training them for a day, so that they can do their tasks properly and then let them work. By building some long term relationship, they were able to improve the quality of the results, without employing too complicated solutions for solving the worker quality problem. They use the oDesk API as well, and pay an hourly wage that varies from $5 to $15 per hour, depending

One thing that was interesting is that they are paying per hour, and not per piece. This is a conscious choice. The distribution of completion times for various tasks follows a lognormal distribution. At the very tail, we have the hard tasks that need a lot of time. These are actually the tasks that MetaWeb cares a lot to get right. Paying by piece means that workers have the incentives to do these tasks quickly, and move to the next. Paying for time means that workers can spend some time more in such hard tasks. The quality control process of Metaweb includes testing workers for throughput (if a worker is very significantly slower than the others gets warned and then dismissed).

Sellers' problems in human computation markets
M. Six Silberman (University of California, Irvine) (*** presenting)
Joel Ross (University of California, Irvine)
Lilly Irani (University of California, Irvine)
Bill Tomlinson (University of California, Irvine)

M. Six Silberman discussed the problems that workers (aka sellers) face in the marketplace of Mechanical Turk. There are bad requesters that reject good work and do not pay, or try to scam workers. Given the increasing number of workers that rely on Turk for income, it is not surprising that workers start demanding guarantees of fairness. The paper even points to a "Turker Bill of Rights". Tools like Turkopticon help in that respect. (Btw, readers that are interested in the labor law aspects of crowdsourcing, should definitely read the paper "Working the Crowd: Employment and Labor Law in the Crowdsourcing Industry" by Alek Felstiner.)

One interesting aspect of this presentation was its slideless nature. The speaker just read the conclusions from his notes. Although I found the mode of presentation difficult to follow, I think the message was clear: Do we care about the workers? Do we pay them fairly? There was significant discussion afterwards, and I bet this is the only place in KDD (or in any other CS conference) where people engaged into discussion about the fairness of minimum wage laws, issues of immigration and labor, and so on :-)

10 am, Session 2: Human Computation in Practice[Coffee, Demos & Posters, all in parallel]

In the next session, we had a set of very interesting demos and posters. I did not have time to see them all, so find below my notes about each one of them,

Frontiers of a Paradigm -- Exploring Human Computation with Digital Games
Markus Krause (University of Bremen)
Aneta Takhtamysheva (University of Bremen)
Marion Wittstock (University of Bremen)
Rainer Malaka (University of Bremen)

Markus had a very interesting game, for discovering synonyms and antonyms. You control a spaceship, and you try to shoot down the antonyms of the word given to you, and you try to collect the synonyms. This was a real arcade game, with graphics, collision detection, and so on. Markus mentioned that he writes it in Flash, because it is fast, and because there are websites where you post your game for people to procrastinate, and then you get effortlessly users. He routinely gets 3 million players a month. Even very simply games (e.g., click the boxes) get 5000 users to play them.

GiveALink Tagging Game: An Incentive for Social Annotation
Li Weng (Indiana University)
Filippo Menczer (Indiana University)

This was a game to find words/tags that will take you from one page to another, essentially uncovering the semantic connections between pages.

Crowdsourcing Participation Inequality: A SCOUT Model for the Enterprise Domain
Osamuyimen Stewart (IBM Research)
David Lubensky (IBM Research)
Juan M. Huerta (IBM Research)
Julie Marcotte (IBM GBS)
Cheng Wu (IBM Research)
Andrzej Sakrajda (IBM Research)

Mutually Reinforcing Systems
John Ferguson (University of Glasgow)
Marek Bell (University of Glasgow)
Matthew Chalmers (University of Glasgow)

A Note on Human Computation Limits
Paul Rohwer (Indiana University)

This a case study of two attempts to crowdsource writing a novel. The first attempt by Penguin Books and De Montfort University used a wiki to crowd source a novel. The result was a failure. No organization, disconnected elements, incoherent result. When BBC attempted the same a couple of years later, the result was a success. The difference? BBC assigned a curator, who overlooked the process. Lesson? Any attempt to harness the wisdom of the crowds needs a reliable aggregator that will kick out the junky contributors and their contributions, keeping only the good contributions from the crowd.

Reconstructing the World in 3D: Bringing Games with a Purpose Outdoors
Kathleen Tuite (University of Washington)
Noah Snavely (Cornell University)
Dun-Yu Hsiao (University of Washington)
Adam Smith (UC Santa Cruz)
Zoran Popovic (University of Washington)

Interesting real-life game: The goal is to cover and create a 3D reconstruction of a city. Players get points when they go out, take a photo, and cover a part of a city/building that was not covered before. Using the images, they can reconstruct in 3D the buildings without gaping holes.

Improving Music Emotion Labeling Using Human Computation
Brandon G. Morton (Drexel University)
Jacquelin A. Speck (Drexel University)
Erik M. Schmidt (Drexel University)
Youngmoo E. Kim (Drexel University)

A game in which you listen to a song and try to guess the tempo and sentiment of the song, and agree with a co-listener. There is a continuous, intermittent feedback about the choice of the other player. The player that moves first to the agreed location gets extra points as influencer. I make it sound more complicated that it seems. I played it and it was very very intuitive and easy to play.

Webpardy: Harvesting QA by HC
Hidir Aras (University of Bremen)
Markus Krause (University of Bremen)
Andreas Haller (University of Bremen)
Rainer Malaka (University of Bremen)

Measuring Utility of Human-Computer Interaction
Michael Toomim (University of Washington)
James A. Landay (University of Washington)

A very interesting study about how the design of a HIT can influence participation. They change HIT parameters (price/design/etc) and examine for how long users will keep doing HITs. Reminded me a little bit of Dan Ariely's work on how motivation affects desire to work on a task.

Translation by Iterative Collaboration between Monolingual Users
Chang Hu (University of Maryland)
Benjamin B. Bederson (University of Maryland)
Philip Resnik (University of Maryland)

A demo that showed how two monolingual humans can collaborate to translate a document. They start with a human translation, and the human examines which part of the human translation do not make sense. After rephrasing and sending back (again through machine translation), the other human check if the translation makes sense and whether it corresponds to the original sentence that was translated. What I missed was how users can get motivated to participate in this system.

11:00am, Session 3: Task and Process Design

Sentence Recall Game: A Novel Tool for Collecting Data to Discover Language Usage Patterns
Jun Wang (Syracuse University) ****
Bei Yu (Syracuse University)

This game worked as follows: The user looks at a sentence, then the sentence disappears, and the user has to type the sentence again. Typically people cannot retype the exact sentence but type something similar. The main outcome is that through this game we can discover paraphrases and (especially when played by non-natives) typical mistakes in specific language constructs.

Word Sense Disambiguation via Human Computation
Nitin Seemakurty (Carnegie Mellon University)
Jonathan Chu (Carnegie Mellon University)
Luis von Ahn (Carnegie Mellon University)
Anthony Tomasic (Carnegie Mellon University) *****

The goal of this game is to disambiguate words (e.g., think of the different meanings of "bass" in "I can hear bass sounds" and "I like grilled bass"). The idea follows the ESP game, and asks users to type alternate words for the given underlined word in a phrase. If two people agree, then move on. Taboo words appear when their usage does not allow the disambiguation of a word (e.g., the word is associated with two senses). The experimental results clearly showed the fact that users are learning over time and perform better.

Quality Management on Amazon Mechanical Turk
Panagiotis G. Ipeirotis (New York University)
Foster Provost (New York University)
Jing Wang (New York University)

For many tasks on Mechanical Turk, there are spammers submitting wrong results. Using repeated labeling and an algorithm like Dawid and Skene, we can estimate the error rates of the workers. The question is, can we infer from the confusion matrixes who is a spammer? Error rate alone is not enough: Spammers that put everything in the majority class have lower rates than honest but imperfect workers. Also, biased workers who are systematically off (e.g., more conservative or more liberal than other workers) end up having very high error rates. The solution is to compensate for the errors and see how the assigned class looks like after compensating for the errors. If the corrected labels are concentrated in one class, the worker is good. If they are spread across all classes, the worker is bad.

Exploring Iterative and Parallel Human Computation Processes

Greg Little (MIT) ****
Lydia B. Chilton (University of Washington)
Max Goldman (MIT CSAIL)
Robert C. Miller (MIT CSAIL)

The TurkIt toolkit introduced the idea of iterative tasks, introducing the ideas of iterative elimination voting, the idea of iternative tasks in which workers build on each others results, and so on. This paper examines the outcomes of different task designs. Basic question: Does it make sense to run tasks in parallel, or does it make sense to let workers build on each other's results? For description of images, iterative tends to be better, as people really build on each other's results. Similarly for transcriptions of highly noisy results. However, for tasks with shorter answers (e.g., coming up with company names) there is an interesting tradeoff: Iterative process tends to have higher average, but parallel has higher variance. If you are interested in the max and not in the average rating of the responses, then parallel is better. Iterative will find the consensus, but it will not be great. Parallel will generate some disasters, but also some gems. So if the goal is to find the "best", then parallel processes (i.e., independence) should work best. However, if you are afraid of disastrous outcomes, then workers should interact to eliminate outliers.

Toward Automatic Task Design: A Progress Report
Eric Huang (Harvard University)
Haoqi Zhang (Harvard University) ****
David C. Parkes (Harvard University)
Krzysztof Z. Gajos (Harvard University)
Yiling Chen (Harvard University)

The final talk of the workshop focused on optimizing task design, an area that I see as having significant potential for follow-up work. The basic question asked is: How should we design optimally a task for crowdsourcing, given a set of constraints? What will generate best quality? What design aspects will improve speed? In a sense, how can we start moving crowdsourcing from an ad-hoc execution, into a mode in which we specify the task, and a black box optimizer selects all the appropriate aspects of the design for us. The paper gave some first results on predicting the quality and quantity of tags assigned to an image and showed that designs that are predicted to be optimal before execution indeed perform much better than designs that are suboptimal.

12:00noon, Concluding Remarks

Yours truly, at the end, was assigned with the task of coming up with conclusions and describing the overall themes. I think the keyword is this workshop was "Design". Design for individual tasks (either games or MTurk HITs), and design of processes in handling such crowdsources tasks in marketplaces. One theme that I would have liked to see more is incentive designs to motivate people to participate and contribute. But I was very happy overall.

After the concluding remarks there was some discussion of quality control and examining the robustness of crowdsourcing systems to manipulation attacks. While we have no definite answers on how to guarantee protection from coordinated attacks in the absence of ground truth, in the current settings we rarely see extensive collusion and coordination across attackers. Most of the current spammers are there to make an easy buck, and not to spend extensive amounts of time trying to scam pennies. (There are better targets for that.)

Of course, having ground truth for verification of answers and for worker evaluation can help significantly in that respect: Luis von Ahn mentioned the attack on reCAPTCHA from the 4chan clan, which randomly entered the word "penis" as one of the two words, hoping to fill in the digitizations of books with the word "penis". (Given that they were failing in 50% of the attempts, it was easy to isolate them and remove their entries.)

The problem of handling a completely anonymous crowd, without any ground truth knowledge, and getting good results is hard to solve. Perhaps some security people will need to take a look and examine the theoretical guarantees.

Detecting Spammers on Mechanical Turk, Part II

2010-07-04T05:51:00.000-07:00

In my previous post, I gave a brief overview of different techniques used to improve the quality of the results on Amazon Mechanical Turk. The main outcome of these techniques is a matrix that describes the error rate of each worker.

For example, consider the task of categorizing webpages as porn or not. We have three target categories:

G-rated: Pages appropriate for a general audience, children included.
PG-rated: Pages with adult themes but without any explicit sexual scenes, appropriate only for children above 13
R-rated: Pages with content appropriate for adults only.

In this case, the confusion matrix of a worker, inferred using the techniques described in my previous post, would look like:

$ \left( \begin{array}{ccc} Pr[G \rightarrow G] & Pr[G \rightarrow PG] & Pr[G \rightarrow R] \\ Pr[PG \rightarrow G] & Pr[PG \rightarrow PG] & Pr[PG \rightarrow R] \\ Pr[R \rightarrow G] & Pr[R \rightarrow PG] & Pr[R \rightarrow R] \end{array} \right) $

where $Pr[X \rightarrow Y]$ is the probability that the worker will give the answer $Y$ when given a question where the correct answer is $X$. (The sum of the elements in each line should sum up to 1.)

And here is the question that seems trivially easy: Given the confusion matrix, how can we detect the spammers?

Computing the Error Rate

The simple answer is: Just sum up the elements out of the diagonal! Since every non-diagonal element corresponds to an error, if the sum is high, the worker is a spammer. Of course, this ignores the fact that class priors will often differ. So, instead of giving equal weights to each category, we weight the errors according to the class priors (i.e., how often we expect to see each correct answer).

$\\ Pr[G] (Pr[G \rightarrow PG] + Pr[G \rightarrow R]) + \\ Pr[PG] (Pr[PG \rightarrow G] + Pr[PG \rightarrow R]) + \\ Pr[R] (Pr[R \rightarrow G] + Pr[R \rightarrow PG]) $

For example, if in confusion matrix is

$\left( \begin{array}{ccc} 0.5 & 0.3 & 0.2 \\ 0.2 & 0.6 & 0.2 \\ 0.1 & 0.1 & 0.8 \end{array} \right) $

and the class priors are 80% $G$, 15% $PG$, and 5% $R$, then the weighted error rate is

$80\% \cdot (0.3 + 0.2) + 15\% \cdot (0.2 + 0.2) + 5\% \cdot (0.1 + 0.1) = 0.47$

Notice that the error rates for the first line, which correspond to category $G$, got weighted more heavily.

Unfortunately, this method does not work very well.

When we started using this technique, we ended up marking legitimate workers as spammers (false positives), and classifying spammers as legitimate workers (false negatives). Needless to say, both mistakes were hurting us. Legitimate workers were complaining and (understandably) badmouthing us, and spammers kept polluting the results.

Let me give some more details on how such errors appear.

False Negatives: Strategic Spammers and Uneven Class Priors

Spammers on Mechanical Turk are often smart and lazy. They will try to submit answers that seem legitimate but without spending too much time. (Otherwise, they may as well do the work :-)

In our case, we were categorizing sites as porn or not. Most of the time the sites were not porn, and only 10%-20% of the time we had sites that were falling into one of the porn categories. Some workers noticed this fact, and realized that they could keep their error rate low by simply classifying everything as not-porn.

Following the standard way of computing an error rate, these workers were faring much better than legitimate workers that were misclassifying some of the not-porn sites.

Here is an illustration. With three categories (G-, PG13-, and R-rated), the confusion matrix for a spammer looks like this:

$\left( \begin{array}{ccc} 1.0 & 0.0 & 0.0 \\ 1.0 & 0.0 & 0.0 \\ 1.0 & 0.0 & 0.0 \end{array} \right) $

With class priors are 80% in G, 15% in PG13, and 5% in R, the weighted error rate of the spammer is:

$80\% \cdot (0.0 + 0.0) + 15\% \cdot (1.0 + 0.0) + 5\% \cdot (1.0 + 0.0) = 0.2$

Compare this overall error rate with the one of a legitimate worker, with rather modest error rates:

$\left( \begin{array}{ccc} 0.8 & 0.2 & 0.0 \\ 0.1 & 0.8 & 0.1 \\ 0.0 & 0.25 & 0.75 \end{array} \right) $

The error rate for this legitimate worker is:

$80\% \cdot (0.2 + 0.0) + 15\% \cdot (0.1 + 0.1) + 5\% \cdot (0.25 + 0.0) = 0.2025$

Yes, the legitimate worker appears to be worse than the spammer!

False Positives: Biased Workers

The second type of error is when we classify honest workers as spammers. Interestingly enough, when we started evaluating workers, the top "spammers" ended up being members of the internal team. Take a look at the error rate of this worker:

$\left( \begin{array}{ccc} 0.35 & 0.65 & 0.0 \\ 0.0 & 0.0 & 1.0 \\ 0.0 & 0.0 & 1.0 \end{array} \right) $

The error rate is:

$80\% \cdot (0.6 + 0.0) + 15\% \cdot (0.0 + 1.0) + 5\% \cdot (0.0 + 0.0) = 0.67$

The error rate would imply that this worker is essentially random. A clear case of a worker that should be banned.

After a careful inspection though, you can see that this is not the case. This is the confusion matrix of a worker that tends to be much more conservative than others and classifies 65% of the "G" pages as "PG13". Similarly, all the pages tat are in reality "PG13" are classified as "R". (This worker was a parent with young children and was much more strict on what content would pass as "G" vs "PG13.)

In a sense, this is a a pretty careful worker! Even though this worker does mix up R and PG13 pages, there is a very clear separation between G and PG13/R pages. Still the error rate alone would put this worker very clearly in the spam category.

Solution: Examine Ambiguity not Errors

You will notice that one thing that separates spammers from legitimate workers is the information provided by their answers. A spammer that gives the same reply all the time does not give us any information. In contrast, when the biased worker gives the answer "PG13", we know that this corresponds to a page that in reality belongs to the "G" class. Even if the answer is wrong, we can always guess the correct answer!

So, by "reversing" the errors, we can see how ambiguous are the answers of a worker, and use this information to decide whether to reject a worker or not.

You can find more details about the process in our HCOMP 2010 paper "Quality Management on Amazon Mechanical Turk".

You can also find a demo of the algorithm at http://qmturk.appspot.com/ and you can plug your own data to see how it works. The code will take as input the responses of the workers, the misclassification costs, and the "gold" data points, if you have any. The demo returns the confusion matrix for each worker, and the estimated "cost" of each worker. The output is plain text and kind of ugly but you can find what you need.

The code is also open source and available at Google Code.

If you have any questions, just drop me an email!

Detecting Spammers on Mechanical Turk, Part I

2010-06-02T20:08:00.000-07:00

Anyone who has tried to use Mechanical Turk for any large scale task knows what is the biggest problem: Spammers!

Many people try initially to post small tasks on Turk and are amazed to get back high-quality results of high quality, very quickly, and with very small cost. Then, they post similar, but much larger, tasks and they realize that now the results are pretty much crap. Spammers start giving random answers, and since they spend no effort, they can easily be the most prolific workers! For example, in the Snow et al. 2008 paper, almost 40% of the submissions came from spam workers, according to Bob Carpenter's analysis.

Unfortunately, this problem is widespread, and tends to discourage new requesters. People just want to get things done on Mechanical Turk, they do not want to spend their time fighting spammers.

Spam Protection Measures: Qualification tests and "best of 3" policy

Qualification tests: Some people, to avoid spammers, use qualification tests. While some measures, such as qualification tests help, they are not a panacea. Determined spammers simply pass the qualification test, and proceed with spamming. Nevertheless, it is a good idea to have a qualification test, as it also tends to filter out workers that come and complete only a couple of HITs. The main disadvantage is that you need programming or use of the command-line tools to create and require a qualification test (i.e., the web interface is not enough).

Best of Three: Other requesters use a "best of 3" (or "2+1") policy: if two workers agree on their answer, the answer is accepted. This technique is relatively widespread across seasoned requesters (and drives some legitimate workers crazy).

Why do legitimate workers hate this verification mechanism? Because every time a worker does not agree with the other two, the submission gets rejected. This drops the acceptance ratio, an important reputation characteristics on Mechanical Turk.

Interestingly, the "best of 3" strategy led to an interesting counter-strategy from spammers: they come in pairs and vote concurrently at the same task, giving the same votes. This defeats the simple "best of 3" approach. (Update: Josh in the comments suggests a good strategy to avoid this: Randomize the HITs by picking examples from a pool, instead of having "static" HITs. This is a generally good suggestion, even if someone uses the more sophisticated tools described below.)

While the "best of 3" approach ensures some basic quality of the data, it does not work well in the long run. Legitimate workers tend to avoid such HITs, as their approval rating can plummet if there are a couple of spammers lurking around. Also, legitimate workers get penalized too severely for honest mistakes.

Spam Protection Measures: Using "gold standard" data and/or unsupervised EM algorithm

A better approach for detecting the quality of the workers is to perform the analysis over a larger set of HITs, rather than operating on single HITs, as "best of 3" does.

Using gold standard: One approach, followed often, is to slip into the stream of HITs some tasks with known correct answers. By comparing the answer given by the worker with the correct answer, we can compute the "confusion matrix" for each worker. In other words, we can see how often a worker gives answer B when the correct answer is A, how often workers says B when correct answer is B, and so on.

Using unsupervised, expectation maximization algorithm: Using gold standard works well when we have in our disposal plenty of such "gold" cases. Unfortunately, this is not always possible, especially when we want to post new tasks frequently. In this case, it makes sense to use the iterative expectation-maximization algorithm proposed by Dawid and Skene:

Initialize the error-rates of the workers (e.g., assume all workers are perfect)
Initialize the most likely class for each example (e.g., using majority vote)
Compute the confusion matrix (aka error rates) for each worker: Compare the answers given by the worker with the estimated correct answers.
Compute the most likely class for each example: Use the answers given by the workers, and weight the answers using the confusion matrix for each worker.
Go to step 3, until convergence

Interestingly enough, the supervised and unsupervised techniques can be naturally combined: In step 4, for all the examples for which we know the correct answer, we simply do not update the class label. Trivially easy. (In a dual fashion, we can also incorporate trusted workers by not updating the error rates in step 3.) By providing some known data, the algorithm can actually estimate with less data the quality of the workers and the correct labels for the unknown examples.

The outcome of these algorithms is:

The correct label for each example
The confusion matrix for each worker

If you want to try this algorithm, go to our demo at http://qmturk.appspot.com/

As the output of this process, we know for each worker its corresponding confusion matrix. So, for a task with 3 possible answers, A, B, C, the confusion matrix would look like:

$ \left( \begin{array}{ccc} Pr[A \rightarrow A] & Pr[A \rightarrow B] & Pr[A \rightarrow C] \\ Pr[B \rightarrow A] & Pr[B \rightarrow B] & Pr[B \rightarrow C] \\ Pr[C \rightarrow A] & Pr[B \rightarrow C] & Pr[C \rightarrow C] \end{array} \right) $

where $Pr[A \rightarrow B]$ is the probability that the worker will classify an object that belongs to class A into class B. Of course, a perfect worker will have a confusion matrix that is perfectly diagonal

$ \left( \begin{array}{ccc} Pr[A \rightarrow A] = 1 & Pr[A \rightarrow B] = 0 & Pr[A \rightarrow C] = 0 \\ Pr[B \rightarrow A] = 0 & Pr[B \rightarrow B] = 1 & Pr[B \rightarrow C] = 0 \\ Pr[C \rightarrow A] =0 & Pr[B \rightarrow C] = 0 & Pr[C \rightarrow C] = 1 \end{array} \right) $

Interestingly enough, the opposite question is not trivial to answer: How can we identify spammers, by examining their confusion matrices? The answer in the next blog post.

Accepted Papers for HCOMP 2010

2010-05-28T21:35:00.000-07:00

The list of accepted papers for HCOMP 2010 is now available. We received a total of 35 submissions (18 long paper submissions, 11 short paper submissions and 6 demo submissions). This was a healthy increase compared to last years numbers (12 long, 9 short, 9 demos).

Unfortunately, due to the half-day duration of the workshop, we had space for only 8 papers (4 long and 4 short). We really had to make very hard decisions to fit as many papers as possible in the program. We reduced the length of the talks, "downgraded" some papers to short, some others to posters, and at the end of the day we even had to reject papers that had no reject ratings! Quite a few of the rejected papers were interesting and I would love the opportunity to talk to the authors about their work. Let's hope that next time we will manage to get a full day for the workshop in order to accommodate the demand. Having acceptance rates of ~25% for a workshop is simply too low.

I expect to see a very exciting program! If you can be in DC on July 25th, you should make the effort to come to the workshop!

Special thanks go to Chandra for running the show this year!

Below, I list the accepted papers, with links to the unofficial versions that the authors posted on their websites. Once we have the camera-ready versions available, I will put the proper links.

Long Papers

Toward Automatic Task Design: A Progress Report
Eric Huang, Haoqi Zhang, David Parkes, Krzysztof Gajos, Yiling Chen
Abstract: A central challenge in human computation is in understanding how to design task environments that effectively attract participants and coordinate the problem solving process. In this paper, we consider a common problem that requesters face on Amazon Mechanical Turk: how should a task be designed so as to induce good output from workers? In posting a task, a requester decides how to break down the task into unit tasks, how much to pay for each unit task, and how many workers to assign to a unit task. These design decisions affect the rate at which workers complete unit tasks, as well as the quality of the work that results. Using image labeling as an example task, we consider the problem of designing the task to maximize the number of quality tags received within given time and budget constraints. We consider two different measures of work quality, and construct models for predicting the rate and quality of work based on observations of output to various designs. Preliminary results show that simple models can accurately predict the quality of output per unit task, but are less accurate in predicting the rate at which unit tasks complete. At a fixed rate of pay, our models generate different designs depending on the quality metric, and optimized designs obtain significantly more quality tags than baseline comparisons.
Exploring Iterative and Parallel Human Computation Processes
Greg Little, Lydia Chilton, Max Goldman, Robert Miller
Abstract: Services like Amazon's Mechanical Turk have opened the door for exploration of processes that outsource computation to humans. These human computation processes hold tremendous potential to solve a variety of problems in novel and interesting ways. However, we are only just beginning to understand how to design such processes. This paper explores two basic approaches: one where workers work alone in parallel and one where workers iteratively build on each other's work. We present a series of experiments exploring tradeoffs between each approach in several problem domains: writing, brainstorming, and transcription. In each of our experiments, iteration increases the average quality of responses. The increase is statistically significant in writing and brainstorming. However, in brainstorming and transcription, it is not clear that iteration is the best overall approach, in part because both of these tasks benefit from a high variability of responses, which is more prevalent in the parallel process. Also, poor guesses in the transcription task can lead subsequent workers astray.
Task Search in a Human Computation Market
Lydia Chilton, John Horton, Robert Miller, Shiri Azenkot
Abstract: "In order to understand how a labor market for human computation functions, it is important to know how workers search for tasks. This paper uses two complementary methods to gain insight into how workers search for tasks on Mechanical Turk. First, we perform a high frequency scrape of 36 pages of search results and analyze it by looking at the rate of disappearance of tasks across key ways Mechanical Turk allows workers to sort tasks. Second, we present the results of a survey in which we paid workers for self-reported information about how they search for tasks. Our main findings are that on a large scale, workers sort by which tasks are most recently posted and which have the largest number of tasks available. Furthermore, we find that workers look mostly at the first page of the most recently posted tasks and the first two pages of the tasks with the most available instances but in both categories the position on the result page is unimportant to workers. We observe that at least some employers try to manipulate the position of their task in the search results to exploit the tendency to search for recently posted tasks. On an individual level, we observed workers searching by almost all the possible categories and looking more than 10 pages deep. For a task we posted to Mechanical Turk, we confirmed that a favorable position in the search results do matter: our task with favorable positioning was completed 30 times faster and for less money than when its position was unfavorable. "
The Anatomy of a Large-Scale Human Computation Engine
Shailesh Kochhar, Stefano Mazzocchi, Praveen Paritosh
Abstrat: In this paper we describe RABJ, an engine designed to simplify collecting human input. We have used RABJ to collect over 2.3 million human judgments to augment data mining, data entry, data validation and curation problems at Freebase over the course of a year. We illustrate several successful applications that have used RABJ to collect human judgment. We describe how the architecture and design decisions of RABJ are affected by the constraints of content agnosticity, data freshness, latency and visibility. We present work aimed at increasing the yield and reliability of human computation efforts. Finally, we discuss empirical observations and lessons learned in the course of a year of operating the service.

Short Papers

Sellers' problems in human computation markets
M. Six Silberman, Joel Ross, Lilly Irani, Bill Tomlinson
Abstract: "Tools for human computers" is an underexplored design space in human computation research, which has focused on techniques for buyers of human computation rather than sellers. We characterize the sellers in one human computation market, Mechanical Turk, and describe some of the challenges they face. We list several projects developed to approach these problems, and conclude with a list of open questions relevant to sellers, buyers, and researchers.
Sentence Recall Game: A Novel Tool for Collecting Data to Discover Language Usage Patterns
Jun Wang, Bei Yu
Abstract: Recently we ran a simple memory test experiment, called sentence recall, in which participants were asked to recall sentences that they had just seen on the screen. Many participants, especially non-native English speakers, made various deviations in their recalled sentences. Some deviations represent alternative ways to express the same meaning, but others suggest that there are missing pieces in the participants' language knowledge. The deviation data, on the one hand, can provide individual users valuable feedback on their language usage patterns that they may never notice, on the other hand, can be used as training data for automatically discovering language usage patterns in a subpopulation of language learners. This paper presents our attempts to create an enjoyable sentence recall game for collecting a large amount of deviation data. Our results show that the game is fun to play and the collected deviation data can reveal common language usage patterns among non-native speakers.
Quality Management on Amazon Mechanical Turk
Panagiotis Ipeirotis, Jing Wang, Foster Provost
Abstract: Crowdsourcing services, such as Amazon Mechanical Turk, allow for easy distribution of small tasks to a large number of workers. Unfortunately, since manually verifying the quality of the submitted results is hard, malicious workers often take advantage of the verification difficulty and submit answers of low quality. Currently, most requesters rely on redundancy to identify the correct answers. However, redundancy is not a panacea. Massive redundancy is expensive, increasing significantly the cost of crowdsourced solutions. Therefore, we need techniques that will accurately estimate the quality of the workers, allowing for the rejection and blocking of the low-performing workers and spammers. However, existing techniques cannot separate the true (unrecoverable) error rate from the (recoverable) biases that some workers exhibit. This lack of separation leads to incorrect assessments of a worker's quality. We present algorithms that improve the existing state-of-the-art techniques, enabling the separation of bias and error. Our algorithm generates a scalar score representing the inherent quality of each worker. We illustrate how to incorporate cost-sensitive classification errors in the overall framework and how to seamlessly integrate unsupervised and supervised techniques for inferring the quality of the workers. We present experimental results demonstrating the performance of the proposed algorithm under a variety of settings.
Human Computation for Word Sense Disambiguation
Nitin Seemakurty, Jonathan Chu, Luis von Ahn, Anthony Tomasic
Abstract: One formidable problem in language technology is the word sense disambiguation (WSD) problem: disambiguating the true sense of a word as it occurs in a sentence (e.g., recognizing whether the word "bank" refers to a river bank or to a financial institution). This paper explores a strategy for harnessing the linguistic abilities of human beings to develop datasets that can be used to train machine learning algorithms for WSD. To create such datasets, we introduce a new interactive system: a fun game designed to produce valuable output by engaging human players in what they perceive to be a cooperative task of guessing the same word as another player. Our system makes a valuable contribution by tackling the knowledge acquisition bottleneck in the WSD problem domain. Rather than using conventional and costly techniques of paying lexicographers to generate training data for machine learning algorithms, we delegate the work to people who are looking to be entertained.

Poster/Demos

Frontiers of a Paradigm: Exploring Human Computation with Digital Games
Markus Krause
GiveALink Tagging Game: An Incentive for Social Annotation
Li Weng, Filippo Menczer
Crowdsourcing Participation Inequality; A SCOUT Model for the Enterprise Domain
Osamuyimen Stewart, David Lubensky, Juan Huerta, Julie Marcotte, Cheng Wu, Andrzej Sakrajda
Mutually Reinforcing Systems: A Method For The Acquisition Of Specific Data From Games With By-Products
John Ferguson, Marek Bell, Matthew Chalmers
A Note on Human Computation Limits
Paul Rohwer

Demos

Reconstructing the World in 3D: Bringing Games with a Purpose Outdoors
Kathleen Tuite, Noah Snavely, Zoran Popovic, Dun-Yu Hsiao, Adam Smith
Improving Music Emotion Labeling Using Human Computation
Brandon Morton, Jacquelin Speck, Erik Schmidt, Youngmoo Kim
Webpardy: Harvesting QA by HC
Hidir Aras, Markus Krause, Andreas Haller, Rainer Malaka
Measuring Utility of Human-Computer Interactions
Michael Toomim, James Landay
Translation by Iterative Collaboration between Monolingual Users
Chang Hu, Benjamin Bederson, Philip Resnik

Prediction Optimizers

2010-05-21T16:00:00.000-07:00

The announcement of the Google Prediction API created quite a lot of discussion about the future of predictive modeling. The reactions were mainly positive, but there was one common concern: Google Predict API operates as a black box. You give the data, you train, you get predictions. No selection of the training algorithm, no parameter tuning, no nothing. Black box. Data in, predictions out.

So, the natural question arises: Is it possible to do machine learning like that? Can we trust something if we do not understand the internals of the prediction mechanism?

Declarative query execution and the role of query optimizers

For me this approach, being trained as a database researcher, directly corresponds to the approach of a query optimizer. In relational databases, you upload your data, and issue declarative SQL queries to get answers. The internal query optimizer selects how to evaluate the SQL query in order to return the results in the fastest possible manner. Most of the users of relational databases today do not even know how a query is executed. Is the join executed as a hash-join or as a sort-merge join? In which order do we join the tables? How is the GROUP BY aggregation computed? I bet that 99% of the users have no idea, and they do not want to know.

Definitely, knowing how a database works can help. If you know that you will perform mainly lookup queries on a given column, you want to build an index. Or create a histogram with the distribution statistics for another column. Or create a materialized view for frequently executed queries. But even these tasks today are increasingly automated. The database tuning advisor on SQL Server routinely suggests indexes and partitionings for my databases that I would never thought of building. (And I have a PhD in databases!)

Declarative predictive modeling

I see an exact parallel of this approach in the Google Prediction API. You upload the data and Google selects for you the most promising model. (Or, more likely, they build many models and do some form of meta-learning on top of these predictions.) I would call this a "prediction optimizer" making the parallel with the query optimize that is built within every relational database system today. My prediction (pun intended) is that such prediction optimizers will be an integral part of every predictive analytics suite in the future.

Someone may argue that it would be better to have the ability to hand tune some parts. For example, if you know something about the structure of the data, you may pass hints to the "prediction optimizer", indicating that a particular learning strategy is better. This has a direct correspondence in the query optimization world: if you know that a particular execution strategy is better, you can pass a HINT to the optimizer as part of the SQL query.

Can we do better? Yes (but 99% of the people do not care)

The obvious question is, can we do better than relying on a prediction optimizer to build a model? The answer is pretty straightforward: Yes!

In fact, if you build any custom solution for handling your data, it will be significantly better than any commercial database. Databases have a lot of extra baggage (e.g., transactions) that are not useful in all applications but are slowing down execution considerably. I will not even go to the discussion about web crawlers, financial trading systems, etc. However, these solutions come at a cost (time, people, money...). Many people just want to store and manage their data. For them, existing database systems and their behind-the-scenes optimizers are good enough!

Similarly, you can expect to see many people building predictive models "blindly" using a blackbox approach, relying on a prediction optimizer to handle the details. If people do not care about hash joins vs. sort-merge joins, I do not think that anyone will care if the prediction came from a support vector machine with a radial basis function, from a random forest, or from a Mechanical Turk worker (Yes, I had to put MTurk in the post).

The future

I know that predictions, especially about the future, are hard, but here is my take: We are going to see a market for predictive modeling suites, similar to the market for databases. Multiple vendors will built (or have already built) similar suites. In the same way that today Oracle, Microsoft, IBM, Teradata and so on, compete for the best SQL engine, we will see competition for such turnkey solutions for predictive modeling. You upload the data and then the engines complete for scalability, speed of training, and for the best ROC curve.

Let's see: Upload-train-predict. Waiting for an answer...

Google Prediction API: Commoditization of Large-Scale Machine Learning?

2010-05-19T21:50:00.000-07:00

Today Google has announced the availability of the Google Prediction API: In brief, it allows users to upload massive data sets into the Google Datastore and then let Google built a supervised machine learning model (aka classifier) from the data. This is simply big news!

Google seems to promise great simplicity: Upload data in CSV format and Google takes care of the rest. They select the appropriate model for the data, train the model, report accuracy statistics, and let you classify new instances. Building classifiers from large-scale datasets becomes trivial.

While I have not had the chance to access the API, this seems to be a game changer. The ability to scale models to work with massive datasets was beyond the reach of many, and now suddenly becomes a commodity. Research labs that wanted to built classifiers as tools (and not as the focus of their research) will be able to do so without requiring much expertise. Similarly, startups will be able to use a scalable machine learning infrastructure, without having access to an inhouse expert.

In a sense, it seems to bring machine learning to the masses, bringing the performance baseline to very high level. If Google Predict is "good enough", will people seek for more advanced solutions? The optimizer of MySQL pretty much sucks but it is "good enough" for many.

Will Google Predict make large-scale machine learning a commodity? Does it mean that the value is now in having the data and in feature engineering? Unclear, but definitely a plausible scenario.

I will withhold further commentary until I manage to get access to the API. But I am excited!

Google Scholar now Supports Email Alerts

2010-05-09T19:55:00.000-07:00

While searching Google Scholar, I noticed a new icon:

By clicking this button, you can create an email alert, which notifies you for any new papers that may appear for the given query. You can use it:

For normal queries, getting notifications for queries such as [author:lastname] or [intitle:titleword], or by any other query on Google Scholar
For citation queries, getting information about new papers that cite a given paper. For that, you need to first go to the "Cited by X" page, and then click the alert icon.

At the end, you get a nice list of alerts that can notify you when new papers of a particular author appear on Google Scholar, when new papers about a topic get indexed, or when a paper gets cited (the almighty citation!). Here is how the alert list looks like:

I tries to find some official announcement for this feature and I could not find anything. Not sure if this is rolled out to everyone but it is certainly very very useful!

My Citation Tracker tool becomes less useful now, but I am glad that we will stop trying to implement this feature on top of Google Scholar and Google will start doing it natively. Next step Google: RSS alerts!

Crowdsourcing: Not just a cost saver

2010-05-04T19:13:00.000-07:00

Whenever I am discussing crowdsourcing, people tend to ask about the "killer app" for crowdsourcing. In my mind, a new technology is being used first for cost reduction, then due to the afforded flexibility, and finally to achieve tasks that were previously infeasible.

As with many technologies (e.g., VoIP), the first applications of crowdsourcing tend to focus on cost reduction. Label images, moderate comments, verify addresses, collect emails... All tasks that were traditionally done by low-paid interns, are now crowdsourced, for significant cost savings. Although these applications tend to be useful, it is hard to see applications focused on cost cutting to be the ones that will drive the wide adoption of crowdsourcing. In any case, if someone has big tasks like that, they can always contact an outsourcing shop in a developing country, and achieve similar rates.

So, flexibility of deployment tends to be another angle that tends to drive the adoption of crowdsourcing. Pretty much as in the case of cloud computing, crowdsourcing can come pretty handy for companies that need significant resources for just a small period of time. LiveOps was a pioneer of this model, applying "crowdsourcing" before the terms was invented, to dynamically staff call centers for telemarketing companies, handling sudden spikes in demand, and so on.

However, the really interesting applications are those that are truly being enabled by such technology. One such idea was given to me by Amanda Michel of Propublica, last September after a Mechanical Turk Meetup: Propublica wanted to monitor the spending of stimulus money, and examine if the projects assigned to different contractors were being completed properly. By analyzing the collected data, it would be possible to identify systematic problems or outright corruption.

Of course, collecting such data would have been impossible for a journalist, or even for a team of journalists. However, using crowdsourcing it would be pretty easy for local residents to check if a bridge has been fixed, if a road was properly paved, and so on. I loved the idea! It was a clear demonstration of how to take an infeasible task, and use crowdsourcing to make it feasible. Even better: it was encouraging the involvement of citizens and their active collaboration with the government. A win-win project!

Interestingly enough, a recent article on BusinessWeek, indicates that the Obama administration is also employing crowdsourcing for the same task! From the article: "It's the surest way to prevent, say, a convicted contractor from reincorporating a new company under his wife's name and applying for stimulus money, explains Earl Devaney, the special inspector general who oversees stimulus spending. "Only local folks can connect those kinds of dots," he says.

Indeed! If only we had such ideas in Greece...

KDD Accepted Papers, Deadlines for HCOMP 2010 and SNAKDD 2010 workshops

2010-05-03T15:26:00.000-07:00

The accepted papers for KDD 2010 are now posted and available at http://www.kdd.org/kdd2010/papers.shtml

As a reminder, the KDD this year will take place in Washington DC, from July 25th to July 28th.

I would also like to draw your attention to two KDD workshops that I am involved with, the Human Computation Workshop (HCOMP 2010) and the Workshop on Social Network Mining and Analysis (SNAKDD 2010). Both have submission deadlines on May 7th. It is pretty easy to travel to DC, so if you have any cool idea, or demo that would be appropriate for these workshops, please submit!

For those too bored to visit the respective websites, here are the call for papers:

Human Computation Workshop (HCOMP 2010) - Call for Papers

Most research in data mining and knowledge discovery relies heavily on the availability of datasets. With the rapid growth of user generated content on the internet, there is now an abundance of sources from which data can be drawn. Compared to the amount of work in the field on techniques for pattern discovery and knowledge extraction, there has been little effort directed at the study of effective methods for collecting and evaluating the quality of data.

Human computation is a relatively new research area that studies the process of channeling the vast internet population to perform tasks or provide data towards solving difficult problems that no known efficient computer algorithms can yet solve. There are various genres of human computation applications available today. Games with a purpose (e.g., the ESP Game) specifically target online gamers who, in the process of playing an enjoyable game, generate useful data (e.g., image tags). Crowdsourcing marketplaces (e.g. Amazon Mechanical Turk) are human computation applications that coordinate workers to perform tasks in exchange for monetary rewards. In identity verification tasks, users need to perform some computation in order to access some online content; one example of such a human computation application is reCAPTCHA, which leverages millions of users who solve CAPTCHAs every day to correct words in books that optical character recognition (OCR) programs fail to recognize with certainty.

Human computation is an area with significant research challenges and increasing business interest, making this doubly relevant to KDD. KDD provides an ideal forum for a workshop on human computation as a form of cost-sensitive data acquisition. The workshop also offers a chance to bring in practitioners with complementary real-world expertise in gaming and mechanism design who might not otherwise attend this academic conference.

The first Human Computation Workshop (HComp 2009) was held on June 28th, 2009, in Paris, France, collocated with KDD 2009. The overall themes that emerged from this workshop were very clear: on the one hand, there is the experimental side of human computation, with research on new incentives for users to participate, new types of actions, and new modes of interaction. This includes work on new programming paradigms and game templates designed to enable rapid prototyping, allow partial completion of tasks, and aid in reusability of game design. On the more theoretic side, we have research modeling these actions and incentives to examine what theory predicts about these designs. Finally, there is work on noisy results generated by such games and systems: how can we best handle noise, identify labeler expertise, and use the generated data for data mining purposes?

Learning from HComp 2009, we have expanded the topics of relevance to the workshop. The goal of HComp 2010 is to bring together academic and industry researchers in a stimulating discussion of existing human computation applications and future directions of this new subject area. We solicit papers related to various aspects of both general human computation techniques and specific applications, e.g. general design principles; implementation; cost-benefit analysis; theoretical approaches; privacy and security concerns; and incorporation of machine learning / artificial intelligence techniques. An integral part of this workshop will be a demo session where participants can showcase their human computation applications. Specifically, topics of interests include, but are not limited to:

Abstraction of human computation tasks into taxonomies of mechanisms
Theories about what makes some human computation tasks fun and addictive
Differences between collaborative vs. competitive tasks
Programming languages, tools and platforms to support human computation
Domain-specific implementation challenges in human computation games
Cost, reliability, and skill of labelers
Benefits of one-time versus repeated labeling
Game-theoretic mechanism design of incentives for motivation and honest reporting
Design of manipulation-resistance mechanisms in human computation
Effectiveness of CAPTCHAs
Concerns regarding the protection of labeler identities
Active learning from imperfect human labelers
Creation of intelligent bots in human computation games
Utility of social networks and social credit in garnering data
Optimality in the context of human computation
Focus on tasks where crowds, not individuals, have the answers
Limitations of human computation

Workshop on Social Network Mining and Analysis - Call for Papers

Social networks research has come a long way since the notable �six-degree separation� experiment. In recent years, social network research has advanced significantly, thanks to the prevalence of the online social websites and the availability of a variety of offline large-scale social network systems such as collaboration networks. These social network systems are usually characterized by the complex network structures and rich accompanying contextual information. Researchers are increasingly interested in addressing a wide range of challenges residing in these disparate social network systems, including identifying common static topological properties and dynamic properties during the formation and evolution of these social networks, and how contextual information can help in analyzing the pertaining social networks. These issues have important implications on community discovery, anomaly detection, trend prediction and can enhance applications in multiple domains such as information retrieval, recommendation systems, security and so on.

The fourth SNA-KDD '2010 aims to bring together practitioners and researchers with a specific focus on the emerging trends and industry needs associated with the traditional Web, the social Web, and other forms of social networking systems. Both theoretical and experimental submissions are encouraged. The interesting topics include (1) data mining advances on the discovery and analysis of communities, on personalization for solitary activities (like search) and social activities (like discovery of potential friends), on the analysis of user behavior in open fora (like conventional sites, blogs and fora) and in commercial platforms (like e-auctions) and on the associated security and privacy-preservation challenges; (2) social network modeling, scalable, customizable social network infrastructure construction, dynamic growth and evolution patterns identification and discovery using machine learning approaches or multi-agent based simulation.

The fourth SNA-KDD '2010 solicits contributions on social network analysis and graph mining, including the emerging applications of the Web as a social medium. Papers should elaborate on data mining methods, issues associated to data preparation and pattern interpretation, both for conventional data (usage logs, query logs, document collections) and for multimedia data (pictures and their annotations, multi-channel usage data). Topics of interest include but are not limited to:

Communities discovery and analysis in large scale online and offline social networks
Personalization for search and for social interaction
Recommendations for product purchase, information acquisition and establishment of social relations
Data protection inside communities
Misbehavior detection in communities
Web mining algorithms for clickstreams, documents and search streams
Preparing data for web mining
Pattern presentation for end-users and experts
Evolution of patterns in the Web
Evolution of communities in the Web
Dynamics and evolution patterns of social networks, trend prediction
Contextual social network analysis
Temporal analysis on social networks topologies
Search algorithms on social networks
Multi-agent based social network modeling and analysis
Application of social network analysis
Anomaly detection in social network evolution

Yahoo!'s Key Scientific Challenges: Your student is a winner!

2010-04-15T10:03:00.000-07:00

I got the following email:

Dear Panos,

The judging is done. From an outstanding group of 200 proposals, twenty-two exceptional PhD students have been selected to be part of Yahoo!�s 2010 Key Scientific Challenges (KSC) Program. Your student, Nikolay Archak has been chosen to receive this very competitive award. Congratulations!

Supporting the academic community is a top priority at Yahoo!. We created the KSC Program to support a limited number of outstanding PhD students who we believe are doing research in very important and challenging areas. The Program provides each student with $5,000 of unrestricted funds for the support of their research activities (e.g., conference fees and travel, lab materials, professional society membership dues, etc.). The funds are distributed through the university and paid directly to the student for use at their discretion. As part of this program, the student also receives an exclusive invitation to a unique workshop (most likely to be held in August at our location in Sunnyvale, California), where we will focus on novel disciplines and important technical challenges for the Internet research community, slanted specifically for graduate students whose innovative work is just emerging. We think that the opportunity to interact with Yahoo! scientists and other top graduate students in an informal and supportive environment without having to submit papers for review will provide a unique forum for open and stimulating discussion of work in its early stages.

Students will also have the opportunity to work with select datasets through our Webscope program. Yahoo! will cover all travel expenses to the KSC Workshop independent of the $5,000 award.

We are excited to be able to support these students with KSC grants, and we look forward to having them as part of our broad research alliance of outstanding students and faculty. Please feel free to contact Jamie Lockwood at jamieloc@yahoo-inc.com if you have any questions regarding our KSC Program.

I offer you my warmest congratulations. We eagerly look forward to hosting Nikolay at our KSC Workshop as part of the Yahoo! family.

Best regards,

Ken Schmidt

Director, Academic Relations

Nikolay is not a stranger to winning competitions. He has won in the past 3 times the TopCoder competition, ended up 2nd two more times. He also has a streak of accepted publications, including a single-authored paper at WWW2010 this year.

Nikolay, congratulations!

Stop Publishing!

2010-04-10T21:40:00.000-07:00

The last few months, I feel that I have an endless queue of reviewing tasks to complete. WWW, followed by DBRank, followed by EC, followed by KDD, followed by VLDB, followed by WebDB, plus an NSF panel, plus some journal reviews, and I have rejected invitations for a few additional conferences including SIGIR, SIGMOD, and a few others. This puts my count at least 40 reviews over the last 4-5 months. (Just to break even, I will need to submit 10-12 papers.)

Needless to say, having such a reviewing load means that I cannot really do a good job in reviewing. My reviews have been declining in quality, signalling that I need to learn to say no.

At the same time, I also notice that the other reviews that are being submitted are not that great either. While on the one hand I feel happy ("OK, I am not that bad"), on the other hand I feel that this cannot be good. If nobody has time to review thoroughly, what is the whole point of peer reviewing?

One solution is to accept fewer invitations for PCs, allowing for more time per paper. However, I know that without volunteering time and effort for reviewing the system cannot work! There are simply not that many reviewers available!

Part of this problem is, of course, the increased need to get papers published: For tenure, for getting a job, even for being admitted to a PhD program! I feel that there is something wrong when, to be admitted to a PhD program, you need to have already research experience. This increased need for more and more publications, overloads the reviewing system which unfortunately has a limited capacity.

Unfortunately, it is not easy to reverse this trend. The incentives are setup in a way to encourage quantity of publications, preferably in good venues. Once the paper gets accepted in a good venue, the goal is achieved. This encourages publications that are "good enough" to pass the reviewing process, not papers that have stellar quality. And with the increased noise in the reviewing process, the distinction between "good enough to be published" and "what the hell, send it, we may get lucky" is getting blurrier and blurrier. In fact, I have cases in my papers that the reviewers did such a poor job that I never understood at the end if my paper was worth getting published, or I got just lucky.

I noticed though a positive development! Through the Greek University Reform Forum, I learned that:

The German Research Society (DFG) has introduced new guidelines for applications and evaluations of proposals, which will be valid as of July 1, 2010.

A rough-and-ready translation of the main points:
Applicants should cite in their CV only up to FIVE publications, those which are most relevant for the proposal at hand;
In reports about running projects, a maximum of TWO publications PER YEAR. In case of projects with more than one PIs, a maximum of THREE publications PER YEAR.
The goal of the new guideleines is to put emphasis on quality instead of quantity and to stop the flood of publishing for the sake of the numbers.

It has caused quite some stir here in Germany and the voices to enforce such rules also for decisions on faculty positions are getting louder.

While some of these ideas are already in place (e.g., NSF also allows only five publications in the CV), the idea of "counting" only two publications per year for each project is definitely a step towards the right direction. It is not going to be trivial to reverse the "get as many publications in top venues as possible" trend, but every step towards de-emphasizing quantity counts.

After all, Pollock was also getting paid by the piece when he worked for the Federal Art Project, but none of his famous paintings come from that period.

Getting High Quality Results on MTurk

2010-03-31T19:16:00.000-07:00

In a previous post, an anonymous commenter left a pretty interesting comment, which I think is worth repeating:

On the subject of higher pay not rendering better work, there are some AMT requesters who pay well, and in the instructions for the task, put in bold print a note that says something along the lines of:

"We pay very well for these tasks, because we expect perfect, error-free work. You don't have to rush through these tasks to make money doing them, so slow down and take your time. Poor quality work WILL be rejected and you WILL be blocked from working for us in the future if your work is poor."

My gut feeling, as a task worker at AMT, is that this is an effective method for increasing the quality of the work (high pay, plus a message reminding the worker to take their time because they don't HAVE to rush through these tasks to make money as an incentive, plus the motivating threat of having work rejected and getting blocked as a disincentive to rushing) but it would be neat to see it officially demonstrated.

Anyone tried this or willing to try? I would be very interesting in hearing the results.

Citation Tracker: Now with an API

2010-03-15T11:42:00.000-07:00

A few months back I announced the availability of Citation Tracker, a tool that allows monitoring of your publications for incoming citations and mentions on the web. We received plenty of suggestions and we have been trying to implement them, with the hope of moving out of the alpha version by the end of the year.

Today, although we are still in alpha, I am happy to announce that we reached a major milestone: Citation Tracker now has a public API available!

We have posted documentation online and a sample PHP client for those that want to experiment. For details you can see the online documentation, but here is some brief description of the things that you can do through the API:

Publications: Add, remove, get, and edit publications. Pretty self-explanatory

Add publications
Delete publication
Edit publication
Get publications

Monitoring: Add, remove, get, and edit monitoring channels. A monitoring channel is an citation-oriented site (such as Google Scholar, Libra, SSRN), or a general web search engine (Google, Bing, Ask, Yahoo). We monitor these sites for new results that match the publications and return back the new citations (or mentions, if we refer to general web results).

Add monitoring channel
Delete monitoring channel
Get active monitoring channels
Update monitoring channel

Citations: Get, update, and edit citations or web mentions, as returned by the different monitoring channels.

Get citations
Update citation state (new, accepted, discarded, review-later)
Update citation

Although we are still in alpha, NYU Library started using the tool and the API for creating a new service on top. I am sure that other people will have ideas of what they can do with the API. Enjoy and let me know if you have any feedback.

The New Demographics of Mechanical Turk

2010-03-09T17:06:00.000-08:00

Past surveys on the demographics on Mechanical Turk users indicated that most of the workers come from the US, are younger and more educated than the general population, and work on MTurk as a way to get some spare cash.

Since the last survey, a few things have changed. First, Amazon allows now workers in India to get paid in cash in rupees, essentially encouraging many people from India to start using Mechanical Turk as workers. Second, the recession has affected many households, leaving many people at home looking for cash to cover their needs. These two forces has changed the demographics of the participants, so a new survey was needed to capture the new demographics of the Mechanical Turk workers.

So, in February 2010, I conducted a new survey on Mechanical Turk, paying the workers10 cents for participating.

The first major change was the country of origin. In the past 70%-80% of the workers were coming from the US, but now the percentage is closer to 50% and it may decrease even more. India is now a major contributor of workers, with almost 35% of the workers coming from the subcontinent. The remaining workers come from 66 different countries. The exact numbers in the survey:

United States: 46.80%
India: 34.00%
Miscellaneous: 19.20%

The analysis also indicated that the profile of the Indian workers is quite different from the profile of the U.S-based workers. So, below I present the results broken down by country.

Gender Breakdown

The first analysis focus on the gender breakdown. Across US-based workers, there are significantly more females than males, while the situation is reversed for Indian workers.

The main reason for the overrepresentation of females in the US-based workforce is the nature of the tasks and work on Mechanical Turk. Most participants in the US use Mechanical Turk as a supplementary source of income, and often Mechanical Turk is used by stay-at-home parents, unemployed and underemployed workers, and so on. Since females are more likely to fit into these categories, there is a corresponding increase in representation. On the contrary, more Indian workers treat Mechanical Turk as a primary (or at least significant) source of income, and we see more males working on Mechanical Turk.

Age Distribution

In terms of age distribution, there is definitely an overrepresentation of younger workers, compared to the general population of Internet users. While this holds both for the US and for India, we see an even higher skew towards younger workers among Indians.

Educational Level

We also asked the Mechanical Turk workers to declare their educational level. In general, the (self-declared) educational level of the workers is higher than the general US and Indian population. There are two factors that may contribute to this. First, many of the workers are younger than the overall population and, ceteris paribus, this leads to higher educational level. Finally, while we may not necessarily discount the possibility of false disclosure, there are no incentives that would bias workers towards lying in this survey.

Income Level

We were also interested to examine the income level of the workers on Mechanical Turk. In the US, the shape of the distribution roughly matches the income distribution in the general US population. However, it is noticeable that the income level of US workers on Mechanical Turk is shifted towards lower income levels. For example, while 45% of the US Internet population has income below $60K/yr, the corresponding percentage across US-based Mechanical Turk workers is 66.7%. (This finding is consistent with the earlier surveys that compared income levels on MTurk workers with income level of the general US population of Internet users.) The picture is drastically different across US-based and Indian workers. Workers based in India have significantly lower incomes, as expected, and more than 55% of the workers declared an income of less than $10K/year.

Marital Status, Children, and Household Size

In terms of marital status and household size, the answers tend to match the age demographic of the workers reported earlier. The majority of the workers, both in India and in the US, do not have children, and a significant fraction of them are single. An interesting contrast is the household size, which seems more to reflect cultural norms than anything specific to Mechanical Turk: While more Indian workers are single and without children, they seem to stay in houses with larger number of household members, compared to US workers: Indian workers either stay with their family, or they tend to have a comparatively larger number of roommates, compared to US workers.

Level of Engagement on Mechanical Turk

We also asked a set of questions for evaluating the level of engagement of Mechanical Turk workers on the marketplace. Since we did not detect significant deviations across countries, we will be reporting the results in aggregate form, without separating by country of origin of the worker. In general most workers spend a day or less per week working on Mechanical Turk, and tend to complete 20-100 HITs per week. Correspondingly, this generates a relatively low income stream for Mechanical Turk work, which is often less than $20 per week. Of course, there are a few workers that devote a significant amount of time and effort, completing thousands of HITs, and generating a respectable income of more than $1000/month. For these workers, Mechanical Turk tends to be the primary source of income, of course. For Indian-based workers, such salary levels are typically satisfactory for the type of work that is available on Mechanical Turk (i.e., tedious tasks that do not require significant specialized skills)

Motivations for Participating on Mechanical Turk

To understand better why people participate on Mechanical Turk, we asked for both qualitative (i.e., free text) and a set of structured questions. The main structured question that we asked was the following:

Why do you complete tasks in Mechanical Turk? Please check any of the following that applies:
Fruitful way to spend free time and get some cash (e.g., instead of watching TV)
For "primary" income purposes (e.g., gas, bills, groceries, credit cards)
For "secondary" income purposes, pocket change (for hobbies, gadgets, going out)
To kill time
I find the tasks to be fun
I am currently unemployed, or have only a part time job

The answers were quite different across Indian and US-workers. Very few Indian workers participate on MTurk for "killing time", and significantly more Indians treat MTurk as a primary source of income. (Not surprising given the average income level of an Indian worker vs the income level of the US workers.)

While these graphs are ok, I would actually encourage everyone to go through the textual responses of the workers. Below you can find the data embedded in a Google Spreadsheet. Go through the column "EngagementQ1" and I am sure that you will enjoy reading all the answers given by the workers.

More Details

The set of blog posts about the demographics of Mechanical Turk have been a little bit too popular, reaching a point where people were asking me how to cite these surveys. While I thought that pointing to the blog would be enough, I was surprised to find out that many people consider a blog post to be too "informal" to cite.

Although I find this academic conservatism kind of funny, I am not sure whether such type of work should appear in an academic conference, journal, or magazine. Maybe a magazine-style journal would be ok but I am still not 100% convinced.

Anyway, as a compromise, I now created a working paper with the results of these demographic studies, and now whomever is interested can cite the "official" working paper with the results on the demographics of Mechanical Turk. (As you will notice, it is essentially this blog post, pasted in a PDF file.) As an added value, you can also find there the Excel spreadsheet with all the results and perform your own analyses and studies.

I would like to consider this working paper as a true working paper, i.e., update it over time with the most current results, if I consider this necessary. Until then, enjoy the current results and let me know if there are other questions that you would like to see answered.

Why Mechanical Turk Allows Only US-based Requesters?

2010-02-24T13:17:00.000-08:00

Many people read the blog from outside the United States. All these readers learn about Mechanical Turk and are excited about the concept, so they want to try it out. Unfortunately, no such luck! You need a US credit card to be able to fund the account (or you need to work as a Turker to accumulate the amount necessary to fund your own tasks.)

So, many people are asking: Why Amazon does not open the service internationally? Why restrict Mechanical Turk only to people that have US credit cards?

This was kind of puzzling to me as well, given that other Amazon Web Services (e.g., EC2, S3, etc) are open to international customers. Why other web services are open but MTurk is not?

Today I met with John Hoskins, Senior Manager of Business Development of Mechanical Turk, and asked the very same question. The answer was clarifying: For all other web services, the customer is consuming Amazon services and pays Amazon. For Mechanical Turk, Amazon receives funds from requesters and then distributes them to workers.

This flow of payments forces Amazon to comply with the US Patriot Act, especially the provisions about money laundering and financing of terrorist activities. The basic idea, known as the "Know Your Customer (KYC)" doctrine, is that Amazon should know from whom they get money and to whom they send the money. This is possible for US credit cards and for US bank accounts, due to the regulations of the US banking system. (I also guess that this is also possible for India, given that Amazon now pays workers in India using rupees.)

I find it kind of fascinating that Mechanical Turk could be used as a venue for money laundering but, in retrospect, not unlikely. In fact, given the relatively low fees that Amazon charges for funds to change hands, it is almost appealing. I can easily see a person posting one million $10 do-nothing HITs, available only to a single qualified worker, who can then consume them and get paid "clean" money.

I guess the news is a disappointment for many aspiring international requesters, but there is some hope: If you can open a US-based credit card (e.g., have a pre-paid credit card or a gift credit card), then it should be possible to open a Mechanical Turk requester account. Or, simply go and use CrowdFlower that will serve as an intermediary and submit your tasks to Mechanical Turk, providing many other value-added services along the way (thanks to S�rgio Nunes for reminding me about that!).

Universities and Intellectual Property: A Minefield?

2010-01-26T14:10:00.000-08:00

One of the things that I never understood at NYU is what are the rights that the university has on the work produced by the faculty members and students.

Following the intellectual properly law, there are four basic types of intellectual properly:

Copyright
Patents
Trademarks
Trade Secrets

If someone works for a corporation, things are pretty clear. Any paper, before being published needs to get approval. Any developed algorithms and code written is the intellectual property of the company and the company owns the copyright for the code, and can treat the algorithms as a trade secret. The company may also patent useful inventions and register some valuable trademarks. But, in all these cases, everything that is being produced within the corporation is work made for hire and owned by the corporation. The employee has typically no ownership of the produced work and it is commonly prohibited for the employee to work for another company or provide any sort of consulting services..

For the work of faculty, I always felt that everything falls into a grey area. Most of the work is made public as soon as possible. Code is often released as open source, following some pretty liberal licensing scheme, or even released to the public domain. Papers are written and publicized without much, if any, vetting and the algorithms and methods described there are typically in the public domain. The only case where a university has some control over intellectual property is when a patent is filed and granted.

Now, the great confusion arises when the faculty wants to work with a corporation and the university allows faculty members to engage into consulting agreements. Who owns and controls the expertise and discoveries of the faculty member?

Let's say that myself, Panos, invented an algorithm in area X, wrote a paper, and published the code in an open source format. Corporation A, comes to me and asks me to consult them on area X. What is the control that my employer, NYU, has on my work? Yes, Corporation A wants to hire me because of the IP that I produced while at NYU. This IP though is publicly available, so I do not really transfer anything protected under copyright law.

I have asked this question to our own tech transfer office. Unfortunately, I did not get back a clear answer. They told me that I cannot transfer code and that any patent is owned by NYU. Correct, these are indeed intellectual property assets. (Although for the case of open source code, this is again confusing.) But what about the expertise that a faculty member develops? In corporations this is often protected using some no-compete clauses in the employment contract, effectively preventing employees from directly transferring know-how. In universities, there is no such provision.

I find this merging of academic and corporate worlds to be particularly confusing and I find this to be a potential minefield. Who owns what? Any ideas? Any experiences? How other universities treat the concept of tech transfer?

Did you find this helpful?

2010-01-25T20:59:00.000-08:00

Last week, the New York Times Sunday magazine had an article titled The Reviewing Stand, starting with the following:

Here�s a challenge for students of expository writing: review a popular product on Amazon and aim to get your review chosen by readers as �most helpful.� It�s dead hard. The product review, as a literary form, is in its heyday. Polemical, evocative, witty, narrative, exhortative, furious, ironic, off the cuff....

What I found amusing was the fact that, after reading this article, I got a notification that the journal version of the paper Estimating the Helpfulness and Economic Impact of Product Reviews: Mining Text and Reviewer Characteristics, co-authored with my frequent co-author, Anindya Ghose, has been accepted for publication at the IEEE Transactions on Knowledge and Data Engineering (TKDE) journal.

As the title suggests, one of the problems that we attack in the paper is how to predict the usefulness of a product review. For example, if you go on Amazon, you will see, on top of many reviews, how many people considered a particular product review helpful:

So, the question is: Can we predict how helpful a particular review will be?

Our first attempts to address this problem appeared in the WITS 2006 and the ICEC 2007 papers. Following the scientific zeitgeist, a large number of other papers appeared these years, all tackling the question of predicting helpfulness of reviews. (See the actual paper for references.)

What I found rather surprising was the relative easiness of the task. A few relatively straightforward features can be used to predict with good accuracy whether a review will be deemed helpful or not.

Check the readability of the article, as measured by one of the many readability metrics, check the number of spelling errors, and measure basic statistics of the text, such as review length. Using just the readability and the fraction of spelling errors in the article we can estimate with 70%-80% accuracy whether a review will be deemed helpful or not.
Check the history of the reviewer. If the reviewer has been writing helpful reviews in the past, it is highly likely that reviews in the future will also be helpful. Also, if a reviewer has disclosed personal details (name, location, etc) the reviews are more likely to be helpful. Again, using just reviewer history and disclosure details, we get 70%-80% accuracy, as measured with the AUC metric.
Check the "subjectivity" of the review. We call a review objective if it contains mainly information that can be found in the product description and specs. A subjective review contains information that depends on the personal experiences of the reviewer. Helpful reviews tend to contain a mix of both.

Interestingly enough, all three feature sets seem to have equivalent predictive power. Even using them all together does not seem to increase substantially the predictive performance.

While preparing the final version of the paper, I also checked other papers that were attacking the same problem. While many papers were trying to predict helpfulness using textual features, I noticed that a few papers were using a set of alternative and interesting features:

Coverage of product features. Many products can be considered an aggregation of multiple product features. For example, a digital camera has resolution, size, battery life, sensor size, etd. How many product features are being discussed in the review? This feature tends to have predictive power, according to (Liu et al, EMNLP 2007).
Dynamics of reviews. Reviews that are posted early on get a higher fraction of helpful votes. In contrast, later reviews need to be more informative and comprehensive to attract the same fraction of helpful votes (Liu et al, EMNLP 2007).
Controversy. The helpfulness of a review depends not only on its own content but also on how controversial is the product under consideration (Danescu-Niculescu-Mizil, WWW 2009).
Social network of reviewers. If reviewer A trusts the reviews of reviewer B, then the reviews of B are likely to be more helpful than the reviews of A. ("Exploiting Social Context for Review Quality Prediction"; by Lu, Tsaparas, Ntoulas, and Polanyi; WWW 2010)

Although I have not seen a paper combining all the above features in order to predict the helpfulness of a review (or for ranking reviews by helpfulness), I guess that these set of features will bring predictive accuracy pretty close to its limit for this task.

What is next? I guess personalized recommendations are going to appear sooner or later, matching users with reviews that are more likely to benefit them. (Update: See Eugene's comment below for related papers.) For example, a beginner in photography will be interested in a different type of review when buying an SLR, compared to a seasoned professional. We already know that reviews from similar users can be used for recommending products (see Netflix) so it is not unlikely that different types of reviews will be deemed helpful by different types of users.

So, did you find this blog post useful?

Prisoner's Dilemma and Mechanical Turk

2009-12-05T16:33:00.000-08:00

I have been reading lately, about the differences between mathematical models of behavior and real human behavior. So, I decided to try on Mechanical Turk the classical game theory model of Prisoner's Dilemma. (See also Brendan's nice explanations and diagrams if you have never been exposed to game theory before.)

From Wikipedia:

In its classical form, the prisoner's dilemma ("PD") is presented as follows:

Two suspects are arrested by the police. The police have insufficient evidence for a conviction, and, having separated both prisoners, visit each of them to offer the same deal. If one testifies (defects from the other) for the prosecution against the other and the other remains silent (cooperates with the other), the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both remain silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a five-year sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the betrayal before the end of the investigation. How should the prisoners act?

If we assume that each player cares only about minimizing his or her own time in jail, then the prisoner's dilemma forms a non-zero-sum game in which two players may each cooperate with or defect from (betray) the other player. In this game, as in all game theory, the only concern of each individual player (prisoner) is maximizing his or her own payoff, without any concern for the other player's payoff. The unique equilibrium for this game is a Pareto-suboptimal solution, that is, rational choice leads the two players to both play defect, even though each player's individual reward would be greater if they both played cooperatively.

My first attempt was to post to Mechanical Turk this dilemma in a setting of the following game:

You are playing a game together with a stranger. Each of you have two choices to play: "trust" or "cheat".
If both of you play "trust", you win $30,000 each.
If both of you play "cheat", you get $10,000 each.
If one player plays "trust" and the other plays "cheat", then the player that played "cheat" gets $50,000 and the player that played "trust" gets $0.
You cannot communicate during the game, and CANNOT see the final action of the other player. Both actions will be revealed simultaneously.

What would you play? "Cheat" or "Trust"?

Basic game theory predicts that the participants will choose "cheat" resulting in a suboptimal equilibrium. However, participants on Mechanical Turk did not behave like that. Instead, 48 out of the 100 participants decided to play "trust", which is above the 33% observed in the lab experiments of (Shafir and Tversky, 1992).

Next, I wanted to make the experiment more realistic. Would anything change if instead of playing an imaginary game, I promised actual monetary benefits to the participants? So, I modified the game, and asked the participants to play against each other. Here is the revised task description.

You are playing a game against another Turker. Your action here will be matched with an action of another Mechanical Turk worker.

Each of you have two choices to play: "trust" or "cheat".
If both of you play "trust", you both get a bonus of $0.30.
If both of you play "cheat", you both get a bonus of $0.10.
If one Turker plays "trust" and the other plays "cheat", then the Turker that played "cheat" gets a bonus of $0.50 and the Turker that played "trust" gets nothing.
What is your action? "Cheat" or "Trust"?

I asked 120 participants to play the game, paying just 1 cent for the participation. Interestingly enough, I had a perfect split in the results. 60 Turkers decided to cheat, and 60 Turkers decided to cheat. The final result was 20 pairs of trust-trust, 20 pairs of cheat-cheat, and 20 pairs of cheat-trust.

In other words, the theory prediction that people will be locked in a non-optimal equilibrium was not correct, neither in the "imaginary" game, nor in the case where the workers had to gain some actually monetary benefit.

Finally, I decided to change the payoff matrix, and replicate the structure of the TV game show "Friend or Foe". There, participants get $50K each if they cooperate, $0 if they do not, and if one chooses trust and the other cheat, the "cheat" gets $100K and the "trust" gets $0.

You are playing a game together with a stranger.

Each of you have two choices to play: "trust" or "cheat".
If both of you play "trust", you both win $50,000.
If both of you play "cheat", you both get $0.
If one player plays "trust" and the other plays "cheat", then the player that played "cheat" gets $100,000 and the player that played "trust" gets $0.
You cannot communicate during the game, and CANNOT see the final action of the other player. Both actions will be revealed simultaneously.

What would you play? "Cheat" or "Trust"?

Interestingly enough, in this setting ALL 100 players ended up playing "trust", which was quite different from the previous game and from the behavior of the players in the TV show, where, in almost 25% of the played games, both players chose "cheat" ending up with $0, and in 25% of the games the players collaborated and played "trust" getting $50K each.

So, in my final attempt, I asked Turkers to play this "Friend of Foe" game, having monetary incentives. Here is the task that I posted on Mechanical Turk.

You are playing a game against another Turker. Your action here will be matched with an action of another Mechanical Turk worker.

Each of you have two choices to play: "trust" or "cheat".
If both of you play "trust", you both get a bonus of $0.50.
If both of you play "cheat", you both get $0.
If one Turker plays "trust" and the other plays "cheat", then the Turker that played "cheat" gets a bonus of $1.00 and the Turker that played "trust" gets nothing.
What is your action? "Cheat" or "Trust"?

In this game, 33% of the users decided to cheat, resulting in 6/50 games where both players got nothing, 23/50 games where both players got a 50 cent bonus, and 21/50 games where one player got $1 and the other player got nothing.

I found the difference in behavior between the imaginary game and the actual one to be pretty interesting. Also, the deviation from the predictions of the game-theoretic model is striking.

Although I am not the first to actually observe that, this deviation got me wondering: Why do we use elaborate game theory models for modeling user behavior, when not even the simplest such models do not correspond to reality? How can someone take seriously the concept of an equilibrium when a game, introduced in the intro chapter of every game theory textbook, simply does not correspond to reality? Do we really understand the limitations of our tools, or mathematical and analytic elegance end up being more important than reality?