A Computer Scientist in a Business School

Utility of Money and the St. Petersburg Paradox

2009-11-06T23:06:00.006-05:00

Consider the following game:

We will flip a fair coin, until a tail appears for the first time.

If the tail appears in the first throw, you win $2^1=2$ dollars.
If the tail appears in the second throw, you win $2^2=4$ dollars.
If the tail appears in the third throw, you win $2^3=8$ dollars.
...
If the tail appears in the $n$-throw, you win $2^n$ dollars.

What is the amount of money that someone should risk to enter this game? (This question works best when given to a person that claims to never play a lottery, roulette, or any gambling game, because the expected return is lower than the bet.)

Computing the expected return of this game, we have:

$E=\frac{1}{2}\cdot 2+\frac{1}{4}\cdot 4 + \frac{1}{8}\cdot 8 + \cdots = 1+1+1+ \cdots =\infty$

In other words, the expected utility is infinity, and a rational player should be willing to gamble an arbitrarily large amount of money to enter this game.

Can you find anyone willing to bet $1,000 to play this game? Or $10,000? Or even $100? Yes, I did not think so.

This paradox is called the St. Petersburg Paradox, posed in 1713 by Nicholas Bernoulli and solved in 1738 by Daniel Bernoulli. Since then, a number of potential explanations appeared.

The most common approach is to use expected utility theory. In this case, we introduce a utility function $U(x)$, which describes the "satisfaction" that someone would get by having $x$ amount of money.

Utility of Money: The basic idea is that people do not bet based on the absolute amounts of the return but rather based on the utility of the award. The value of an additional $100 when I have $100 in the bank is much higher compared to the case when I have $1,000,000 in the bank. This means that the "utility of money" function is a concave function of the available funds.

Just for demonstration, below you can see such a concave utility-of-money function that we have computed as part of a research project:

This concavity also partially explains the "risk aversion" that most people have: they prefer certainty over uncertainty. This means that they will reject even a reasonable bet with positive expected return. Why? Notice that the utility gained by winning is smaller than the decrease in utility that results from losing the bet. The higher the concavity, the higher the risk aversion.

If you want to read more about utility of money and its applications to portfolio management, insurance, and analysis of other cases, take a look at this book chapter.

So, next time that someone claims never to engage in any bet with a negative expected return, give the setting of the Bernoulli paradox with the positive expected return and observe the reactions...

What is the (Real) Cost of Open Access?

2009-10-25T23:34:00.001-04:00

After the transformation of Communications of ACM, I find myself increasingly interested in the articles that are published in CACM. As expected, one of the common ways to demonstrate my interest is by sharing the URL for the paper, on Twitter, on Facebook, on the blog, or by sharing the link with friends and colleagues. Unfortunately, CACM has a closed-access policy, effectively preventing anyone without a ACM membership or without a university account from actually reading the papers. Same thing for papers published in conferences and journals, but there I can typically find the paper in the home page of the author. For CACM, this is often not the case.

Needless to say, I hate closed access policies. While I can understand the shortsightedness of for-profit publishers, I fail to see why ACM has not adopted at least a "semi" Open Access model, making, say, the current issue of Communications of ACM available to the public. Or by giving public access to papers published 10 or 20 years back in the different journals and conferences.

The stated goal of the association is to promote the field. By restricting access, ACM simply does not work towards this goal!

The main argument that I hear is that publishing has some costs. But I am really trying to understand what are these costs. What is the magnitude of these costs? And who is being paid? Almost like the health-care debate, we are told that something is expensive but we have no idea of who ends up getting the money.

Let's examine the potential cost factors:

Printing: I understand that printing on paper has costs. But covering the the cost of printing seems easy: Amortize it across the print subscribers. (Or even abolish print versions.)

Servers for distribution: What is the cost of electronically distributing papers? The cost of running a server, should not be a concern. At the worst case, NSF should provide funds for that. I find it hard to think that NSF would turn down a request for funding a server that provides open access to scientific journals!

Submission handling: The cost of the submission website? I doubt that it is above $5K per year, per journal. Ask for a nominal submission fee (say $50 per paper) to cover this. The cost for the copy-editors? We can do much better without them, thank you. (Seriously, why do we still have copyeditors?)

Admin cost: The only cost that I can think of is the cost of the admin staff. But how much is it? I honestly have no idea! Is it so high that the ACM member subscriptions cannot cover the cost? I am trying to find the budget of ACM but I cannot find anything public.

Are there other hidden costs?

If anyone has pointers or extra information, please let me know. I am really trying to understand the real costs of high-quality electronic publishing.

When Noise is Your Friend: Smoothed Analysis

2009-10-11T22:20:00.001-04:00

Have you ever encountered the phrase "the algorithm has exponential running time, in the worst-case scenario, but in practice we observed it to be pretty efficient"? It is the phrase that divides theoreticians and practitioners. Many theoretical computer scientists focus on the analysis of the worst case complexity, generating often results that contradict practice.

For example, the simplex algorithm for linear programming is well known to be pretty efficient in practice. In theory, the worst-case complexity of simplex is exponential, classifying the simplex algorithm as a "non-efficient" algorithm. However, simplex has exponential running time only for very special cases. Most practitioners would even argue that you will never encounter such strange cases in practice. Only an adversary could potentially design such inputs.

Similarly, the Traveling Salesman Problem is a hallmark example of an NP-complete problem, i.e., unlikely to have an efficient algorithm anytime soon. However, there are many implementations of TSP that can provide almost optimal solutions for TSP, for pretty big inputs.

K-means is another such algorithm. It has a horrible worst-case scenario but ask the millions of people that use it for clustering. One of the most efficient clustering algorithms, despite its wost-case exponential complexity.

So, how can we reconcile theory and practice?

A very nice approach towards this reconciliation is the case of smoothed analysis. I first learned about this approach for analyzing algorithms by attending the (fascinating) job talk of Jon Kelner. Jon showed that if you pertubate a little bit the input before feeding it to the simplex algorithm, then it is almost impossible for the pertubed input to generate an exponential running time. In other words, by adding a little bit of noise in the data, there is the guarantee that we avoid the "tricky" parts of the input space.

What is the beauty of this approach? It explains why in many cases "inefficient" algorithms work well in practice: Most real data contain noise, and this noise can actually be beneficial! The other big lesson is that sometimes an algorithm ends up having a horrible worst-case performance just due to a small number of potential inputs, that are almost adversarial. Adding noise, may take care of these strange cases.

The last issue of Communications of ACM, has a great review article by Spielman and Teng on Smoothed Analysis. Explains the difference between worst-case, average-case, and smoothed analysis, and points to a wide variety of problems that have been analyzed using this technique. Highly recommended!

Rationality, P=NP, Prediction Markets, and a Paradox

2009-09-28T18:58:00.001-04:00

I got the idea for this post after reading the post of Dick Lipton on betting on the P=NP problem. The discussion in the comments was extensive, mainly touching the issues of risk aversion, the inability of humans to estimate properly small probabilities, and so on. (Wolfers and Snowberg argue that it is due to the inability of human to understand very small probabilities.) The discussion continued in the Overcoming Bias blog and there one of the comments, being tongue-in-cheek, caught my eye:

probabilities must agree with logic on certainly-true and certainly-false statements, which means that the probability of logical truths has to be 1, and logical falsehoods have to be 0.

So,if P=NP is a decidable problem, it is either true or false. So, a fully rational agent, participating in the market, should know whether P=NP. It is not a matter of probabilities! All the information to make the decision is available. So, if the market has one or more rational players, the market should converge to a price of 0 or 1 immediately, depending on the state of the problem. Right?

So, which of the following is true?

There are no rational agents. So, all the analysis of prediction markets that assume rationality of traders is incomplete.
There are rational agents. The market does not converge to 0 or 1 because the P=?NP problem is undecidable.
There are rational agents but the return from the risk-free rate until reaching the time to settlement exceeds the return from the market. So, the market gives information on how long it will take for the problem to be officially solved.
If your laptop cannot find the solution, neither can the market.

OK, back to more serious work.

Citation Tracker: Monitoring Citations to your Publications

2009-09-14T15:20:00.003-04:00

One of the common pastimes of academics is checking services such as Google Scholar to see the number of papers that cite our work. Quite often the statistics from Google Scholar, or from other services such as Web of Science, are used to create a citation report that is used for promotion and tenure purposes.

While Google Scholar is extremely valuable for finding papers that cite a particular piece of work, it has some shortcomings, especially when creating a citation report for promotion. First, Google Scholar does not differentiate between peer-reviewed (journal, conference, or workshop papers), and other publications (such as tech reports, or term papers); so, when preparing a citation report, I have to go over the list of papers, keeping the "legitimate" citations and removing the citations that are not admissible. Second, Google Scholar is noisy sometimes, and lists twice the same paper, or splits citations for the same paper into two different entries; some other times it does not include papers that are possible to find through a web search.

Another feature that I would really like to see is the ability to find the "new" citations for a given paper, creating the appropriate alerts. A simple RSS feed would work wonders, but it is not there.

Of course, Google Scholar also does not monitor the web to find other types of documents that may mention a particular paper. PhD seminars, or even blog posts, are things that I would like to keep track of when monitoring who cites my own work. Especially for such volatile pages, I typically want to keep a copy so that I can retrieve them a few years later, when compiling my promotion packet.

For this reason, over the summer, I created a tool that can augment Google Scholar and monitor Google Scholar (and other services like Libra, CiteSeerX, SSRN), and also monitor the Web (Google, Bing, Ask) for mentions of the paper.

You can access a pre-alpha version at http://www.citation-tracker.com

Some of the features:

Import publications from Google Scholar, DBLP, BibTeX, and manually.
Review the citations for each paper, and decide which ones to keep, which to discard, and which ones to examine later.
Monitor citation services (Google Scholar, Libra, CiteSeerX, SSRN) and see notifications when new citations to your papers appear.
Generate automatically a citation report, listing the papers that cite your work.

I have been using the service over the last few weeks and it seems reasonably stable. I import my papers using Google Scholar, "accept" the existing citations, and then wait to see about the new citations that pop up every now and then. I find it pretty useful for finding new papers that cite my work.

Over the last few days I even started importing papers from other researchers that I consider relevant to my work, and for which I want to see what new papers cite them.

Feel free to login and play with the system. Needless to say, it is an early release so I expect to see bugs here and there. If you see any bug, or if you would like to see a new feature, please add a note using the "feedback" tab that is visible on the side of the screen.

Enjoy!

The different attitudes of computer scientists and economists

2009-09-06T12:25:00.021-04:00

I was reading Noam Nisan's blog post about the different attitudes of computer scientists and economists. Noam hypothesizes that economists emphasize research on “what is” while computer scientists emphasize on “what can be”, and offers the view of an algorithmic game theorist.

I have my own interpretation on this topic, mainly from the data mining point of view.

Economists are interested in suggesting policies (i.e., suggest to people, "what to do"). Therefore, it is important to built models that assign causality. Computer scientists are rarely interested in the issue of causality. Computer scientists control the system (the computer) and algorithms can be directed to perform one way or another. In contrast, economists cannot really control the system that they study. They do not even know how the system behaves.

When a computer scientist proposes an algorithm, the main focus is to examine the performance of the algorithm under different settings of incoming data. How the (computer) system will behave is controlled. When an economist suggests a policy, it is highly unclear how the underlying (rational?) agents will behave. Therefore, it is important to figure out what exactly "causes" the behavior of the agents, and figure out what policies can change this behavior.

One area that gets closer to economics in this respect is the area of data mining and machine learning. Get the data, and learn how the underlying system behaves. For example, get data about credit card transactions and learn which of them are fraudulent. However, there is a significant difference in focus: Computer scientists are mainly focused on predictive modelling. As long as the system can "predict" the outcome on unseen data, things are ok. A black box with perfect predictive performance is great. Explanatory models are rarely the focus. In the best case, someone may want to understand the internals of the predictive model but even if the model can be understood (e.g., read the rules or the decision tree), these rules are rarely causal in nature.

Let me give you an example: Suppose that you are trying to predict price per square feet for houses. As one independent variable (feature) you add average size of the house in the area. What the predictive model will find? That places that have smaller houses also have higher price per square foot. Unexpected? Not really. Houses in urban areas are typically smaller and more expensive compared to the their suburban and rural counterparts.

For a predictive model, this information is absolutely sufficient; the average house size is a valuable feature for predictive purposes. Think however what would happen is someone was devising policy based on this feature. A house builder would try to build smaller houses in rural areas, hoping that the resulting prices would be higher. Or a politician in Manhattan would encourage construction of bigger apartments, since the experiments have shown that if average house size is increased, the prices will drop. Absurd? Yes.

Even funnier things can come up if someone uses country-wide data to predict demand for apartments using apartment prices. The result will show that increasing prices actually increases demand, even though we would expect the opposite. (Just the effect of prices increasing in places where there is higher demand.)

Predictive modeling can survive (or even thrive) by exploiting such strange correlations. A causal model that captures correlations and presents them as causes can wreak havoc.

So, an economist will try to build a model that will generate causal relationships. In the case above, a model based on supply and demand is more likely to result in a model that captures the true "causes" of increased apartment prices. A house builder can see these effects and make a more informed decision on how to build. Similarly, for a politician that is trying to encourage building more affordable housing.

Often, causal models are called "structural" in economics [not sure where the term comes from; I have seen a few different interpretations]. They typically start by modelling the micro-behavior of agents, and then proceed to explain the behavior of a large system comprising of the interactions of such agents. A benefit of such models is that assumptions are easier to check, test, and challenge. In contrasts to "statistical" models, such models tend to generate relationships that are easier to consider "causal".

An advantage of causal models over predictive models is that causal models are valid even if the underlying data distribution changes. Causal models are supposed to be robust, as long as the behavior of the agents remains the same. A predictive model works under the assumption that the "unseen" data follow the same distribution as the "training" data. Change the distribution of the unseen data, and any performance guarantee for the predictive models disappears.

Update 1: This is not an attempt to downgrade the importance of predictive models. Most of the results presented by Google after a query are generated using predictive modeling algorithms. You get recommendations from Amazon and Netflix as the outcome of predictive algorithms. Your inbox remains spam-free due to the existence of the spam filter, again a system built using predictive modeling techniques. It is too hard, if not impossible, to build "causal" models for these applications.

Update 2: An interesting example of a company deriving policy based on their predictive model is American Express. They realized that the feature "customer buys in a 99c store" is correlated with higher delinquency rates. So, AmEx decided to decrease the credit limit for such customers. Of course, the result will be that potentially affected customers will stop visiting such stores, decreasing the value of this policy for AmEx. Furthermore, this action may cause even more economic stress to these customers that are now "forced" to buy from more expensive stores, and this may result in a much higher default rate for AmEx. This "unexpected" outcome is the effect of devising policy based on non-causal variables.

If AmEx had a variable "customer in economic distress", which arguably has a causal effect on default rates, then it would be possible to perform this action, without the ability of customers to game the system. However, since AmEx relied on a variable "customer buys in a 99c store" that is the outcome of the variable "customer in economic distress" it is possible for consumers to simply change their behavior in the face of economic distress.

Workshop on Information in Networks (WIN)

2009-08-27T16:26:00.003-04:00

For those of you interested in the study of networked data, I would like to bring your attention to the "Workshop on Information in Networks (WIN)", a workshop organized by my colleagues Sinan Aral, Foster Provost, and Arun Sundararajan. It will take place on September 25-26, 2009. From the description:

The purpose of WIN is to bring together leading researchers studying ‘information in networks’ – its distribution, its diffusion, its value, and its influence on social and economic outcomes – in order to lay the foundation for ongoing relationships and to build a lasting multidisciplinary research community.

I should emphasize that the phrase "bring together leading researchers" is not a the standard template used in many call for papers. The lineup of speakers is truly outstanding! I would be very hard pressed to find any conference that would have such a lineup of invited speakers:

Lada Adamic, University of Michigan
Albert-Laszlo Barabasi, University of Notre Dame, Northeastern University
Ronald Burt, University of Chicago
Damon Centola, MIT
Pedro Domingos , University of Washington
Christos Faloutsos, Carnegie Mellon
James Fowler, University of California, San Diego
Sanjeev Goyal, University of Cambridge
Bernardo Huberman, HP Labs
Matthew Jackson, Stanford University
Michael Kearns, University of Pennsylvania
Jon Kleinberg, Cornell University
Rachel Kranton, Duke University
David Lazer, Harvard University
Jure Leskovec, Stanford
Michael Macy, Cornell University
Alex (Sandy) Pentland, MIT
Duncan Watts, Yahoo! Research

It is really as good as it gets. If you are interested in networked data and can be in New York on September 25-26, then this is an event that you must attend!

Get a Consent Form (for IRB) on MTurk using Qualification Tests

2009-08-11T01:16:00.005-04:00

I was browsing through the various qualification tests on Mechanical Turk, checking what requesters ask and how they structure the tests. The one test that caught my eye was designed by Daniel Velleman and David Beaver from the Linguistics department of The University of Texas at Austin.

Here is the test:

"Which sentence do you prefer?" eligibility form
This qualification will allow you to participate in our English language research HIT, "Which sentence do you prefer?"
Is English your first language?
Yes
No
Do you (or did you) have at least one parent or caregiver
whose first language was English?
Yes
No

Please read this information

You are invited to participate in a survey, entitled "Which sentence do you prefer?" The study is being conducted by Daniel Velleman and David Beaver in the Linguistics department of The University of Texas at Austin.

Calhoun 501
1 University Station B5100
Austin, TX 78712-0198
(512) 471-1701

The purpose of this study is to examine English speakers' preferences about the order in which written information is presented. Your participation in the survey will contribute to a better understanding of the English language. We estimate that it will take about a minute of your time to complete each question. You are free to contact the investigator at the above address and phone number to discuss the survey.

Risks to participants are considered minimal. There will be no costs for participating. You will be paid for each HIT you complete, but will not otherwise benefit from participating. Your Amazon account information will be kept while we collect data for tracking purposes only. A limited number of research team members will have access to the data during data collection. This information will be stripped from the final dataset.

Your participation in this survey is voluntary. You may decline to answer any question and you have the right to withdraw from participation at any time without penalty. If you wish to withdraw from the study or have any questions, contact the investigator listed above.

If you have any questions, please email Daniel Velleman at ut.linguistics.mturk@gmail.com. You may also request a hard copy of the survey from the contact information above.

This study has been reviewed and approved by The University of Texas at Austin Institutional Review Board. If you have questions about your rights as a study participant, or are dissatisfied at any time with any aspect of this study, you may contact - anonymously, if you wish - the Institutional Review Board by phone at (512) 471-8871 or email at orsc@uts.cc.utexas.edu.

IRB Approval Number: 2009-03-0123
I understand want to participate in this study.

It is indeed a very clever idea to leverage a qualification test, to get workers to fill-in a consent form, and satisfy at the same time the requirement of the Institutional Review Board.

Perhaps the trick will be useful to other researchers that want to run human studies on Mechanical Turk. (I still believe that for this study an IRB is not required, but this is not the point of this post.)

Top Requesters on Mechanical Turk

2009-08-05T19:15:00.006-04:00

Today I had a chat with Dahn Tamir about all things MTurk. He was particularly interested in the archive of all requesters that I have collected over the last 7 months. So, I queried the database, computed some basic statistics and sent him the results.

Then I thought: why not exporting the live results as well? A few php lines later, the leaderboard with the top Mechanical Turk requesters was born and is now available at http://hyperion.stern.nyu.edu/mturk/requesters.php

You can see for each requester the total number of projects they have posted on Mechanical Turk since January 2009, the total number of HITs, and the total value of the posted HITs. If you are also interested in whether the requester is still active, you can see when was the last time that they posted a HIT.

By clicking on their names, you can see the archive of the last 100 tasks that they have posted and by clicking at the requesterid you get to Amazon and you can see the tasks that are available now.

Enjoy!

When to Post Tasks on Mechanical Turk?

2009-08-04T12:00:00.011-04:00

People that have experience with Mechanical Turk know that getting long tasks done on Mechanical Turk is tricky. While it is relatively easy to get small tasks done quickly, it is much more difficult to estimate how long a big task will take. The "estimated time" given by the Mechanical Turk interface is really crappy and provides pretty much no guidance if you expect your task to last longer than a day.

Naturally questions like this arise: When is it best to post a task? How can I minimize my waiting time?

Trying to understand better how tasks are being completed on Mechanical Turk, I started crawling Mechanical Turk every few minutes collecting data about the HITs, the requesters, how long each HIT is available and so on.

Queue

The first outcome of this effort was the Mechanical Turk Monitor, a visualization tool that shows how many projects are available at any given time, how many HITs, and the available rewards (see the old post).

Arrival process and Serving process

This tool was effectively showing the size of the "queue". However, it did not reveal neither how many tasks arrive per day on MTurk, nor how much work gets done on MTurk every day. So, last week I decided to display this information, and show the activity of the requesters and the corresponding activity of Turkers every day:

Activity of requestors: How many tasks are posted per day
Activity of Turkers: How many tasks are completed per day

Posting Activity

Now, we can start scratching the surface on how things get done on Mechanical Turk. A first pass is to see the statistics for what is being posted over time:

The x-axis depicts time, and the y-axis is the value of the HITs being posted every day. The blue line depicts the total value of the HITs being posted. One immediate observation is that there is some significant periodicity. Taking the 7-day average (red line) smooths significantly the curve. This indicates that there is some strong weekly periodicity.

Let's take a look at the distribution of posting activity over the days of the week:

The plot shows the distribution of the activity for every day of the week. By activity, we define the total value of HITs being posted on each day. As we can see, weekends tend to be significantly more quiet than weekdays. In fact, even Mondays tend to be relatively quiet, perhaps because requesters prepare their HITs that are then being posted on Tuesdays :-)

Well, the plot is not very surprising. Lots of activity during the workdays, less activity over the weekends.

Workers Activity

The interesting result though comes when we look at the activity of the Turkers:

It seems that Turkers are not in sync with the requesters. In fact, the activity on Saturdays us comparable to the activity during the weekdays. Surprisingly, Mondays tend to see significantly less activity. (Perhaps due to the small number of tasks being posted over the weekend?).

Conclusion

What is clear is that there is a relative lag between the activity of requesters and workers. Although it is hard to figure out causality from these figures, it seems that Fridays and Saturdays are good days to post tasks on Mechanical Turk. Relatively low competition for the attention of workers, and significant level of workers activity during Saturday.

So, now you know: Post your HITs on Friday and go away...

Workshops: Official or Unofficial Proceedings?

2009-07-31T11:00:00.001-04:00

In the process of organizing DBRank 2010, we had to answer the following question: Should the proceedings for the workshop be "official" or "unofficial"?

Official workshop proceedings are undergoing the same process as the conference papers: Specific camera-ready format, submission by a given date to the proceedings chair, and then are officially hosted at the digital library of the publisher, with all the metadata, digital identifiers (DOI), and so on. (For DBRank 2010, that would be IEEE Xplore.) For buraucratic purposes, these papers are considered "publications."

Unofficial proceedings are, well, unofficial. Typically the workshop chair posts the papers up to the website, and potentially brings printed copies for distribution at the workshop. There is no official publisher, there is no DOI assigned to the papers, and in principle this is not more of a publication than a paper posted to a website.

So, should workshops have official or unofficial proceedings?

There are some arguments aganst official proceedings:

Increasingly, there is a significant conflict between workshop and conference publications. With some workshops allowing 8- or even 10-page workshop papers, it becomes hard for the authors of these papers to publish the same work in a conference, as there is typically significant overlap. Most database conferences will consider any past paper that is 3 pages or longer, to be a prior publication, and the conference version should have significant new content in order to be considered a "new" paper.
As conference become increasingly competitive many authors submit to workshops papers that could not "make it" to a conference. A workshop is typically easier to get into, and at the end "you get a paper" out of it. Needless to say, this pretty much violates the spirit of workshops that are supposed to be places for new, relatively immature research, not an archival publication.

On the other hand, there are advantages in having official proceedings:

It makes the workshop more attractive in the eyes of many authors. Authors get an official timestamp for their work and can point to a paper that has at least been lightly refereed, instead of pointing to a technical report or working paper.
It makes it easier for someone to locate the papers that were presented in the workshop. The websites for the workshops are not always hosted in "stable" websites and they disappear for various reasons. (For example, the websites for WebDB'99, WebDB 2000, WebDB 2001, and WebDB 2003 are not available any more, because the organizers have moved to different institutions.)

So, what to do? Official or unofficial?

Is Amazon Mechanical Turk a black market?

2009-07-30T12:57:00.014-04:00

According to Wikipedia, a black market is: "a market where all commerce is conducted without regard to taxation, law or regulations of trade". How is this related to Mechanical Turk?

Today, I received an email, asking about the tax and employment issues regarding Amazon Mechanical Turk. What are the rules about posting tasks on Mechanical Turk? How should these tasks be handled by accounting and human resources departments?

Unfortunately, Amazon did not design Mechanical Turk in a requester-friendly way. In an effort to relieve their accounting and HR department from a big overhead, Amazon transferred to the requesters the risk of violating the US Tax Code and engaging into illegal employment activities.

How can this happen? The key issue is whether there is an employer-employee relationship between the requesters and the workers on Mechanical Turk. The crucial question is:

When you submit funds to your Mechanical Turk account, who are you paying? Amazon.com or the worker?

If it is Amazon, then you are simply letting Amazon deal with all the tax and employment issues associated with the worker: Amazon needs to verify that the worker is eligible for employment, takes care of tax issues, and so on. In this case, hiring someone for a micro-task on Amazon is the same as getting an agency to provide cleaning services to your home: you do not need to care if the person coming to clean your place is eligible for employment, whether the taxes are properly withheld from the paycheck and so on. It is the agency's task to take care of that.

However, Amazon does not follow this route. According to the terms and conditions, paragraph 6.a:

In addition to the disclosures described in our Privacy Notice, we will disclose to Requesters [....] Provider Tax Information. "Provider Tax Information" means tax identification information of Providers, such as a Social Security Number or Employer Identification Number. Requesters use Provider Tax Information to fill out an IRS Form 1099 and send it to Providers. If you are a Requester and want Provider Tax Information from us to complete IRS Form 1099s for Providers you have paid, you must provide us with your company name and employer identification number ("Requester Tax Information"). You hereby consent to disclosure of Provider Tax Information, Requester Tax Information, and other data as described in this Section 6 and our Privacy Notice.

This provision is there because a requester that paid a worker more than 600USD per year, is required to submit 1099-MISC tax forms to these workers. In other words, this tiny provision means that the employer-employee relationship is not between Amazon and the worker but between the requester and the worker. This is in contrast to other marketplaces (e.g., Rent-A-Coder), where the requester pays the marketplace provider, and then the marketplace provider contracts individually the workers, taking care of tax issues, issues of employment authorization and so on.

What are the implications of this policy?

Requesters may be open to the risk of violating employment laws. It is possible that a requester is illegally employing US-based workers that do not have the right to work in the US.
Requesters may be open to the risk of violating the US tax code. The requester needs to keep track of how much they paid each individual worker (out of potentially thousands of workers), and send 1099-MISC tax forms to the workers that did more than 600USD worth of HITs over the year for the requester.

OK, these are the risks. What are the potential counter arguments and how can somene avoid these issues?

The employment-eligibility issue: Amazon pays in cash only people that have US bank accounts. This means that the person, if US-based, is legally in the US. I do not know if Amazon checks for employment eligibility (they should). If the person is not US-based, then Amazon pays through gift cards: From what I know, gift cards are not considered compensation, as we regularly give gift cards as awards to students, without worrying about their eligibility to work, and our accounting department never worried about this practice. So, the issue of illegal employment seems to be rather controlled but it would be nice if Amazon took explictly care of that. Yes, it is a big headache for the HR department of Amazon to handle thousands of micro-contractors, but this is the price to pay for running this service.

The tax issue: At the very least, Amazon should have an automatic service to take care of this issue rather than leaving requesters scramble to track all the micro-payments and send the paperwork. It is trivial: If a given requester-worker pair generated more than 600USD worth of HITs over the year, request tax information and send the 1099-MISC forms on their behalf.

A better solution: Request tax and employment-eligibility information from workers BEFORE they can work on the MTurk marketplace. Also, request tax information from all the requesters BEFORE they can post any tasks on MTurk. Then submit the tax forms automatically at the end of the year.

An even better solution: Adopt the Rent-A-Coder model, and consider the MTurk workers as Amazon contractors. Then requesters buy services from Amazon, in the same way they buy computing power on EC2, storage on S3, and so on. In this case, it is very simple to add the MTurk expense under the "software services" line in the accounting report.

How Prices Evolve in Prediction Markets?

2009-07-14T14:32:00.018-04:00

Last week, Nikolay presented our paper on "Modeling Volatility in Predictions Markets" at the EC'09 conference. One of the questions that we are answering in this paper is, "what is the most likely price of a prediction market contract at some point in the future?"

Let's start with the expected price. If we assume that the markets are efficient, then the current price of the contract is the best possible estimate for the future expected price. However, the current price is NOT the most likely price in the future. In fact the probability of the contract will have the same price in the future is decreasing with time. Why? Because the final price of the contract as we get closer to the expiration will get closer to 0 or 1, as the uncertainty about the outcome decreases over time. So, while the expected price will be equal to the current price, most of the future prices will be closer to 0 and 1.

Below you can see some 3d plots of the "future price density" as a function of the future price P and the time to expiration t. We assume that "now" is t=0 and the contract expires at t=1.

If the current price is 0.5, then the future price density, as a function of the future price P and the time to expiration t, is:

As you can see, the possible prices, when we are close to t=0, are clustered around the current price (in this case 0.5). Then, as we move closer to the expiration, the probability density moves closer to 0 and 1. As this contract had price 0.5, the plot is completely symmetric around the axis P=0.5.

If we have a current contract price at 0.4, then the density becomes more skewed towards 0:

And here is an even more skewed plot, with the current contract price at 0.25:

Just in case you want to create your own plots, here is the Maple code:

with(stats);

normpdf:=(x,mu,sigma)->statevalf[pdf,normald[mu,sigma]](x);

spdf:=x -> normpdf(x,0,1);

normicdf:=(p,mu,sigma)->statevalf[icdf,normald[mu,sigma]](p);

sicdf:=x->normicdf(x,0,1);

f:= (pnow,pfuture,lambda) -> spdf ( sqrt(1/lambda) * sicdf(pnow) - sqrt(1/lambda-1) * sicdf(pfuture))*sqrt(1/lambda-1)/spdf(sicdf(pfuture));

plot3d(eval((f(p,P,t)), {p=0.5}), P=0..1, t=0.1..0.75, axes=boxed, shading=zhue, orientation=[-120, 50]);

So, what can we do with these results? One application is to price the X contracts on Intrade: In the "X" contracts, the question is about the future price movement of a prediction market contract (e.g., "will the contract for Democrats winning the 2012 election be above 0.75 on December 31st, 2010?").

These X contracts are similar to the existing "call" and "put" options on the stock market, where people try to guess where the price of a stock will be in the future. There is a significant difference, though: When a trader prices and trades a call/put option for a share, (e.g., using the vanilla Black-Scholes formula) the trader needs to guess the future volatility of the share price. Through this process, the trade gives to the public valuable information about the future volatility of share price. For prediction markets, trading an X contract does not reveal the same information. Our work shows what the exact form of future price distributions, without the need to provide any volatility estimates. (Volatility can be largely determined by the current price and time to expiration; see the past blog post and the EC'09 paper for details.) So, pricing an X contract requires just to plug in the current price, time to expiration, and strike price (information that is already public) to find the "correct" price for the X contract.

So, am I saying that the X contracts are completely useless? No. But the information revealed by trading these contracts is significantly less compared to the information revealed by trading options on stocks.

Books, Journals, Conferences, Blogs

2009-07-04T07:27:00.002-04:00

I was reading the overview on Open Access Overview by Peter Suber, and I ran into the following paragraph:

Scholarly journals do not pay authors for their articles, and have not done so since the first journals were launched in London and Paris in 1665. Journals took off because they were more timely than books. For readers, journals were better than books for learning quickly about the recent work of others, and for authors they were better than books for sharing new work quickly with the wider world and, above all, for establishing priority over other scientists working on the same problem. They gave authors the benefit of a fast, public time-stamp on their work. Because authors were rewarded in these strong, intangible ways, they accepted the fact that journals couldn't afford to pay them. Over time, journal revenue grew but authors continued in the tradition of writing articles for impact, not for money.

It was amusing to see that there was this transition from books to journals, for pretty much the same reason that in computer science we have seen a transition from journals to conferences. I am wondering if the senior scholars of the day were commenting on this transition in the same way that Mike Trick commented on the similar tension between journal and conference publications:

if a subgroup chooses a method of evaluation antithetical to the mores of the rest of academe, don’t be surprised if the group gets little respect outside their narrow group

So may be a few years from now, we will see a similar problem as people will start leaving "traditional" peer-reviewing behind, opting for new modes of publication, such as self-publishing. Michael Nielsen has an excellent article on the disruption of scientific publishing. Micheal points to the high quality blog posts from high-quality researchers:

Look at Terry Tao’s wonderful series of posts explaining one of the biggest breakthroughs in recent mathematical history, the proof of the Poincare conjecture. Or Tim Gowers recent experiment in “massively collaborative mathematics”, using open source principles to successfully attack a significant mathematical problem. Or Richard Lipton’s excellent series of posts exploring his ideas for solving a major problem in computer science, namely, finding a fast algorithm for factoring large numbers.

So, does the future of publication rely on self-publishing? Daniel Lemire may be right saying:

To me, the single most important recent event in academic publishing has been the publication by Perelman of his solution to the Poincarré conjecture on arxiv. This is truly a historical event.

Will this change alter fundamentally the way academia works? I do not think so. It will simply mean that every scholar will be very careful about the quality of the work that is self-published. When everyone can speak, people will only listen to those that generate content of high quality, effectively ignoring those that publish for the sake of publishing.

LiveBlogging from HCOMP 2009

2009-06-29T08:18:00.007-04:00

I am now attending HCOMP2009, the workshop on Human Computation that I previously advertised in this blog.

Overall, the workshop was well-attended with more than 40 people in the audience, pretty much filling the room. Below you can find the notes that I was keeping during the workshop. (See also the associated tweets.) I hope that they capture nicely some of the discussion for those of you that could not be there.

######################################################################

The workshop started with introductions, and then Luis von Ahn described MonoLingo, a human powered system for translation, using people that know ONLY ONE language. Monolingo relies on the fact that machine translation is pretty good at this point, but not perfect. So MonoLingo starts by by translating each word using a dictionary, giving multiple interpretations for each word. The human then (who is a native speaker of the target language) selects the translation for each word and forms the sentence that makes most sense.

To give the incentives to users to participate, MonoLingo appears to be a language learning site: as the user learns the language, makes small translations posed as exercises. Such small translations are used to contribute to a larger translation task.

The system reminded me a little bit of the crowdsourced-powered New York startup SpeakLike, that I have seen at the New York Tech Meetup.

I was also wondering how to best integrate MonoLingo with the more advanced machine translation systems, e.g., Google Translate, which generate significantly better translations than the word-by-word translation(s) generated by MonoLingo. Perhaps a more iterative approach (e.g., using the TurkIt toolkit and ideas) might actually work wonders in this task, where people take turns to improve the overall translation.

######################################################################

The second talk of the workshop described "Herd It: Designing a social game to tag music" by Luke Barrington, Douglas Turnbull, Damien O’Malley, and Gert Lanckriet.

HerdIt uses an active learning approach to tag music. Users tag music online and then a machine learning algorithm is trained to tag a few more songs etc. (The approach reminds me of our own KDD08 paper on active learning using multiple noisy labelers.)

The HerdIt game starts playing the music and the players sees bubbles floating around each one with a tag (e.g., rock, pop, romantic, ballad etc). The players gets more points when they hit the bubble that corresponds to the more popular tags. The authors also added quizzes in the game (e.g., a song plays and the question "the singer has long hair?" appears). For the quizzed, there is a parimutuel prediction market running in the background, where users bet on different outcomes/answers and the winners split the common pool for the bet.

The HerdIt game, reminds me a little bit of MajorMiner, a music game introduced by Michael Mandel, a classmate of mine at Columbia University.

######################################################################

The third talk described "KissKissBan: A Competitive Human Computation Game for Image Annotation" by Chien-Ju Ho, Tao-Hsuan Chang, Jong-Chuan Lee, Jane Yung-Jen Hsu, and Kuan-Ta Chen.

The authors are building on and improving the ESP game. They try to solve the "coalition problem" (people develop a strategy of typing a "common" word, e.g., "the" and proceeding to the next image) and the problem of limited data diversity of tags if you have a limited user base.

The basic idea is to make the the 2-player ESP game, a 3-player game: a new type of player is introduced, named "blocker". The blocker is trying to prevent the other two users from proceeding by typing the "obvious taboo" words that the other two players may type to describe the depicted image. The more words the blocker catches, the better the score of the blocker. This encourages the diversity of tags, since the two "matcher" players will attempt non-obvious tags to describe the image. The blocker can also observe what words the "match" users are using across images. So if two players develop a cheating strategy and type some unrelated word often (e.g., "the") the blocker can catch that behavior and put such words in the "blocked" list. KissKissBan uses a zero-sum approach where the blocker gets the points that are being lost by the matchers. So the blocker has the incentive of entering many words that are then used by the matchers. I suspect that the blocker also loses points by entering words that are NOT used by the matcher players.

Unfortunately, it does not seem to work if the matchers have access to a communication channel beyond the game (e.g., skype or being in the same room). Also, I would have liked to see some discussion of cheating strategies that can be used in such games.

######################################################################

The third talk was the paper "Community-based Game Design: Experiments on Social Games for Commonsense Data Collection" by Yen-Ling Kuo, Kai-Yang Chiang, Cheng-Wei Chan, Jong-Chuan Lee, Rex Wang, Edward Yu-Te Shen, and Jane Yung-Jen Hsu.

The authors describe a game-based an approach for building "common-sense" ontologies using "virtual pets" that are being "fed knowledge" by the friends of the player (e.g., in a Facebook-like setting). The game has some quiz-like templates (e.g., "______--likes to--______") which are then filled in by friends of the player using sensible values (e.g., "a student--likes to--have no homework"). To make it fun, the pets compete online playing such quizzes and they become smarter, getting "smart points". The smarter pets that have the most knowledge and give the most sensible answers appear in the leaderboards. The pets get points when they give the same answers as the pets of other owners. The game is named "Rapport Game".

Sounded fun having a very distinct East Asian flavor, reminding me of a social-networking-enabled Tamagochi...

######################################################################

After the break, we attended the demos and posters. Unfortunately, the time was not enough to really check the large number of posters and demos that were available.

From the demos, I liked TurkIt a lot, not so much for the library and toolkit, but mainly for introducing the idea of "iterative tasks": People that have used Mechanical Turk know that it is very hard to get people to do a good job in tasks that have free responses. Having a voting round after the submission (e.g., "Is this answer good or not") discourages fraud but does not generate high-quality results; it simply generates results that are "good enough". TurkIt introduces the idea of iterations, essentially soliciting multiple rounds of submissions, where users vote whether the "new" submission is better than the "old" one. Looking at the handwriting recognition task is pretty revealing why the approach works well: The first submitter takes a first pass, leaving blanks wherether the transcription is difficult. The second submitter fills-in (some of) the blanks, the third improves even more and so on. When there is no further improvement, the task ends. Very nice idea, I will be using it in the future.

I also learned about the internal crowdsourcing efforts at IBM (basic conclusion: giving a prize like iPod works much better than trying to motivate people through other marketing and management efforts... a good lesson for people trying to deploy enterprise prediction markets...)

######################################################################

In the second part of the workshop, we have seen some discussion on the role of game theory in the design of the human computation games.

The position paper by Shaili Jain and David Parkes "The Role of Game Theory in Human Computation Systems" gave an outline of promising directions for future research in this area.

The basic idea is that human computation may benefit by using game theoretic concepts to improve the design of the games. The basic argument is that the use of game theory also solved problems in settings like P2P networks, where game theory has been used to avoid the problem of free riding. Shaili gave a brief introduction to game theoretic analysis of some games and systems (e.g., PhotoSlap, ESP game and Yahoo Answers).

The talk advocated a modeling of user actions (e.g., in the ESP games players select "easy" or "difficult" words), the corresponding costs and benefits for the users, and how these affect the outcome of the game. The nice outcome is that game theory helps predict the equilibrium of such games, essentially predicting what the stable state of these games will be.

Some of the intriguing open questions:

How to quantify "fun"
How to introduce altruism in the models.
How to generate game theoretic models for the games described in the GWAP taxonomy (games with output agreement, input agreement, and inversion-problem games).
How to use game theoretic concepts of "population games" to model large number of agents that interact.

The high-level conclusion of the talk: It is good to build a game-theoretic model of each game, so that we can see how robust is the game to pertubations of design options.

#####################################################################

The game-theory discussion continued with the paper "On Formal Models for Social Verification" by Chien-Ju Ho and Kuan-Ta Chen.

The authors described how to use game theory to show the effect of sequential verification vs parallel verification. Parallel verification is the process in which two users submit an answer for a question, and if it matches they get a reward. Sequential is the process in which the user submits an answer that needs to match a pre-given "correct" answer. (e.g., "Guess what is the original question for this answer", which allows a sanity check of the answers). The paper provides the corresponding equilibria that result from these mechanisms.

######################################################################

The paper "Efficient Human Computation: the Distributed Labeling Problem" by Ran Gilad-Bachrach, Aharon Bar Hillel, and Liat Ein-dor tackled the following problem: Using humans we can collect labels and tags that describe an object (e.g., an image). When the number of possible labels is large, then we will start seeing consistency problems as different labelers are not coordinated. The labelers may provide correct answers but due to polysemy they end up giving superficially different labels, even though they mean the same thing ("truck" and "lorry"). Or due to homonymy they give the same label even though they mean different things (e.g. "greyhound" the dog, and "greyhound" the bus company).

The authors describe graph-theoretic algorithms that can be used to resolve such problems and provide bounds about the optimality of the proposed approaches. The question arised of how to deal with the fact that the same user may not be self-consistent over time. Also the question on how to deal with users of various degrees of reliability.

######################################################################

The last talk of the workshop was "Financial Incentives and the Performance of Crowds" by Winter Mason and Duncan J. Watts. The authors examine how Turkers respond to various levels of payment. Confirming my own observations, generally Turkers work more for higher pay but do not do much better work in terms of quality. So, paying higher gets more things done but the quality remains statistically the same (my own observation indicates that HITs paying more than 50 cents also tend to attract spammers, effectively decreasing the overall quality!)

In a test of anchoring, authors asked users if they felt that they have been fairly compensated. Interestingly enough, they felt that they were underpaid, valuing their work 2-3 cents more per HIT compared to the payment --- interesting enough, the difference was consistent across levels of payment (e.g., a 5 cent HIT is worth 10, a 10 cent HIT is worth 15 etc). So it may make sense to start giving a low-payment for the HITs at first, and once the psychological anchor is established, increase the payment to satisfy the workers that felt that the initial payment was small :-)

#####################################################################

The overall themes that emerged from the workshop were rather clear: One the one hand, there is the experimental side of human computation, where researchers are trying to devise new incentives for users to participate, new types of actions, and new modes of interaction. On the other hand, we have the more abstract/theoretic side, where researchers are trying to model these actions and incentives to examine what theory predicts about these designs. Also, there is work that examines what to do with the noisy results that are being generated by such games and systems: how can we best handle the noise and use the generated data for data mining purposes?

The final question over dinner was where to organize the next instance of the workshop? There are so many disciplines coming together in this line of work that finding a commonly acceptable venue might be a challenge. Will the CHI people contine coming to KDD? Or will data miners attend CHI to attend this workshop? What about the WWW conference? Would be a good match? I personally favor KDD, but we will have to wait and see the result of the human computation on this issue...

(We also have the wiki with the bibliography in the area http://hcomp2009.wikispaces.com/ which we will have to curate and organize better to reflect the results of this workshop.)

Google Fusion Tables: Databases on the Cloud

2009-06-09T19:56:00.014-04:00

From the Google Research Blog: Google Fusion Tables.

Now it is possible to upload tabular data sets on Google, let other people use the data, and provide easy-to-use visualizations. No complicated joins or other heavy-duty relational stuff but there is functionality to connect (fuse) tables. There is also functionality embedded to discuss the contents of the data set.

Here is an early example. I took the data from a survey of Mechanical Turkers and imported it in Google Tables. Here is the resulting intensity map that shows the distribution of workers per country:

and the "lift" of the distribution of workers per state (we are comparing actual population percentage with percentage of Turkers):

I am truly excited about this feature. Just the idea that it will be possible to release "live" data sets, without having to set up complicated web interfaces, worrying about security, SQL injections, and so on, makes this absolutely wonderful for me.

For comparison, see the corresponding visualizations from Many Eyes:

But the flexibility of Google Tables for data management counters the relative lack of visualization options.

My only real complaint: The 100Mb limit. I was ready to upload my Mechanical Turk archive (see the related blog post) there, and let other people use it. Unfortunately, it is larger than the 100Mb limit. If only I could use the extra storage that I bought from Google for my Gmail account...

Acceptance Rate: 100%

2009-06-02T03:02:00.005-04:00

I have been thinking lately about the concept of binary decisions, mainly in the context of paper reviewing. Most of the time, the decision for a paper is binary: Accept a paper or not.

Any binary decision that depends on some explicit or implicit threshold will always be problematic. Whatever is threshold+epsilon gets in, whatever is threshold-espilon is out. An epsilon difference generates significantly different outcomes. To make things worse, the area around the threshold is typically densely populated. No matter where we put the threshold, papers with small differences in quality, even under perfect quality assesment, get very different treatments.

Here is an alternative. Allow all authors to decide whether to publish their papers or not. With one condition. They will also publish together the reviews for the paper. The paper got 3 strong rejects and the authors still want to publish the paper? Fine!

If such a system was in place, then most of the authors would seek to get good reviews instead of trying to pass the threshold and get into the publish-land.

Going a step further? Keep the reviewed versions of the paper together with reviews of earlier versions. Did the authors address the comments? They can have a statement describing that. Later reviewers can take a look and see whether this is the case. This policy would also encourage submissions of only high-quality results.

This can also be matched with the requirement for the reviews to come from at least some high quality reviewers, but I will leave this for another post.

Evaluation Feedback and Stakhanovist Research Profiles

2009-05-25T09:00:00.000-04:00

Every year, after the Spring semester, we receive a report with our annual evaluation, together with feedback and advice for career improvement (some written, some verbal). Part of the feedback that I received this year:

You get too many best paper awards, and you do not have that many journal papers. You may want to write more journal papers instead of spending so much time polishing the conference papers that you send out.
You are a member of too many program committees. You may consider reviewing less and write more journal papers instead.

I guess that having a Stakhanovist research profile (see the corresponding ACM articles) is a virtue after all.

(*) Alexey Stakhanov was a miner in Soviet Union, who cut 102 tons of coal during a six-hour shift with a pneumatic drill, when the average production being 6-7 tons. Stakhanov's record created the Stakhanovite movement where workers were encouraged to exceeded production targets, typically trying to overcome previous production records.

Public Paper Reviews

2009-05-18T19:36:00.003-04:00

I am now trying to review a journal paper. Unfortunately, the paper is completely unreadable, being a long list of definitions, "lemmas," and "theorems" (the quotes are intentional). Even more unfortunate is the fact that the author does not give any background but rather cites some recently published paper of his, which contain all the necessary background.

Trying to understand the paper, I attempted to read the published paper. Well, no luck! The paper was also horribly written. I started wondering who in his right mind decided to accept this paper to an ACM journal, and what the reviewers were saying. I simply cannot believe that anyone in his right mind would actually read such papers, and even try to write any meaningful review afterwards. Most probably the reviewers gave up and agreed after many revisions to allow the paper to be published, hoping that they will never have to read the paper again. Or may be I am wrong and the paper is indeed a hidden gem?

So, how can we avoid such cases? Here is my not so original suggestion: Publish the (anonymous) reviews together with each paper!

I cannot see anything negative with that. It will make everyone happier. People that write high-quality reviews would not mind seeing their names being published together with the reviews. Other reviewers will see what is a high-quality review and hopefully will try to imitate the style.

In fact, the practice of publishing a commentary for each paper is not new. I have seen many papers in statistics being published with eponymous commentary. Often, reading the reviews is more interesting than reading the paper.

Furthermore, the reviews will offer a quick overview of the contributions and shortcomings of the paper. It will also allow the reader to understand what lead to the acceptance of the paper. Was it a new idea? An excellent experimental evaluation? Or just the reviewers could not even read the paper and just gave up, giving a lukewarm "accept"?

Google App Engine and Java: First Impressions

2009-04-20T23:32:00.006-04:00

Over the last few days I have been playing with Google App Engine, the infrastructure provided by Google for building applications in the cloud. To give some context, I tried to build a crawler that will retrieve and store historic information from a marketplace.

I have already built this application and it was running on my local Linux machine, storing information into a SQL database. However, I was getting unconfortable seeing the database growing significantly and running big queries was interfering with other users who was using the database machine for their own projects. So, I decided to see how easy is to port such a vanilla project into the cloud.

My impressions so far:

Ease of programming

It was pretty easy to follow the provided tutorials and get a basic application up and running pretty soon. It may be a good way to introduce students to (web) programming. The Eclipse plugin hides very significant fraction of the complexity, and allows the programmer to focus on the application development.

Database support

No SQL database anymore. While we still save "entities" and there is support for relationships across entities, Google data storage is based on BigTable, not on a SQL database. This means no joins. You can always implement your own version of a join but this is not how the Google datastore is supposed to be used. Slowly you realize that denormalization is desirable and often absolutely necessary. For someone like me that likes a fully normalized scheme, making sure that we do not have inconsistencies anywhere, it felt almost too messy: too much information replicated everywhere, need to be extra careful not to have anomalies, and so on. I can see a significant learning curve for migrating databases into such an environment. Giving up joins is not easy... (Our MBA students who keep all their data in a single spreadsheet, will feel right at home ;-) But it is not that bad. Personally, it helped me to consider the entities in the Google datastore as materialized views of some underlying relations, and use lazy updating techniques to keep the data consistent.

30-second limit

By far the most annoying aspect of the Google App Engine is the limit of 30 seconds execution time for any process. Nothing can run for more than 30 seconds. Since I wanted to build a crawler, I had to re-think the infrastructure. It was necessary to break the task into smaller chunks that can be completed within the 30 second limit.

To achieve this, I buily a "task queue" structure that was keeping track of the pages that need to be fetched, and this queue was stored as a persistent structure in the datastore. Then, the "crawler" process was picking URLs from the queue, and was fetching whatever pages can be fetched within the 30 second limit, storing the retrieved pages to the Google datastore. Pretty annoying the fact that the 30 second limitation also includes the time to fetch the page. Often, I was timing out just because the remote server was slow to send the requested page.

Finally, to get the crawler running "all the time", I scheduled a cron job that was starting the "30-second crawler" process every minute. Almost like trying to travel a trip with a car that can run for every 30 seconds at a time, and can be restarted every minute. Not very elegant, not the most efficient, but it works for lightweight tasks.

Quota system

Google App Engine allows applications to run for free, as long as they stay below some usage quota. Once the app exceeds its daily allocated free quota, it gets billed, up to a maximum specified limit.

In other words you pay for CPU usage. This is in direct contrast to Amazon EC2 that charges by the "wall time" a virtual machine is running. Since Google App Engine charges only for the actually consumed resources it encourages code that is as efficient as possible and spends as few resources as possible.

Artists say that the limitations of a medium are a major force for creativity. I have to say that the quota system has the same effect. I found myself thinking and rethinking of how I can make the process as efficient as possible. Since I actually see all the time the exact amount of resources spent for each process, I am compelled to make the processes as efficient as possible. This is not the case for regular desktop programming. OK, it takes 2 seconds instead of 0.1. So what? I have plenty of resources, and I can afford being sloppy. When I am being billed for the consumed resources, I have a pretty immediate incentive to write the best code possible.

I may be overreaching here, but I see the concept of being billed according to CPU usage a force that will encourage deeper learning in Computer Science. The effect of optimization is immediate, measurable, and it is often necessary to optimize, just to get your process running.

I remember the stories of the old-timers and how they were trying to super-optimize their code, so that the mainframe can execute the code overnight and they can get the results back. Well, the mainframe is back!

LiveOps and Human Computation

2009-04-08T20:51:00.004-04:00

When we talk about human computation, the canonical examples are either the Games with a Purpose from Luis von Ahn, or Amazon's Mechanical Turk.

Recently, though I learned about LiveOps, a company that allows "micro-outsourcing" of small tasks, such as handling a telephone call, or taking a pizza order in a drivethrough. Quoting Jonathan Zittrain who wrote a paper Ubiquitous Human Computing:

We are in the initial stages of distributed human computing that can be directed at mental tasks the way that surplus remote server rackspace or Web hosting can be purchased to accommodate sudden spikes in Internet traffic (von Ahn 2005; Hewlett Packard (HP) 2008) or PCs can be arranged in grid computing configurations, each executing code in an identical virtual environment (International Business Machines (IBM) 2006). At some fast food drivethroughs, the microphone and speaker next to the marquee menu are patched through to an order-taker thousands of miles away. That person types up the requested order and dispatches it back to a screen in the food preparation area of the restaurant while the car is idling (Richtel 2006). Services like LiveOps recruit workers for such mental contracting tasks (LiveOps 2008a). Applicants to LiveOps navigate a fully automated hours-long vetting system that tests their skills and suitability. Out of 2,000 applicants per week, roughly 40 emerge for a second round of interviews by LiveOps managers (LiveOps 2008b).

Those who succeed and become contractors for firms like LiveOps encounter an unusual combination of freedom and control. They can work whenever they like, wherever they like, for as much or as little time as they like. When they log in to work they choose from a menu of assignments tailored to their skill and reputation levels. These might include taking pizza orders, placing sales calls, lobbying for a political candidate, or handling customer service inquiries. Then there is the control: every call and transaction is measured and recorded. Interactions can be monitored live by fellow LiveOps mentors or official LiveOps managers, or pulled up later as part of a larger assessment of contractors’ work. Judgments are developed and recorded about contractors’ performance, such that an incoming pizza order can be routed to the best pizzaorder- taker – who may not be the same as the best political campaigner (Hornik 2007). Contractors can be de-accredited at any time.

I find the similarities with Mechanical Turk striking but I can clearly see how LiveOps differentiates itself by handling tasks that are not suitable for the Mechanical Turk platform. I also find it mildly entertaining that I am using LiveOps as an example in class when we talk about VoIP, but I never thought of actually digging deeper to see how they work.

On a tangentially related note, if you want to find papers related to human computation, you can visit a wiki that we created at http://hcomp2009.wikispaces.com/. Feel free to add more papers, add notes to the current papers, or simply send suggestions on how to improve it. In the Human Computation Workshop (HComp 2009) we are trying to bring together people who are interested in all aspects of human computation, and the wiki is just one part of this effort.

Fitting a Power-Law with Censored Data

2009-03-19T10:33:00.015-04:00

A few days back, I was describing how to model the distribution of waiting times for Mechanical Turk. There, I described how to use the maximum likelihood estimator to infer the parameter of the power-law, using as input to the estimator the duration of the completed tasks.

However, this approach introduces a bias: There are tasks that we observed that have not finished yet. Take a look for example at the two distribution plots for the completion time of tasks on Mechanical Turk:

You see that there is a "cutoff" in the pdf plot at some point between 512 and 1024 hours. Similarly, we see a sudden drop in the cdf plot. This is just the effect of keeping only the completed tasks, ignoring the tasks that are still running.

By using only the completed tasks, we effectively ignore the information provided by the incomplete tasks: knowing that a task has not finished after running for $U$ hours, gives us information that the duration of the task will be at least $U$: This is valuable information. Such data points are called censored. Let me give some background on censored data for readers not familiar with the concept.

What do you mean by calling a data point censored?

In general, we call a data point censored when we cannot get the exact value for the data point, but we can provide a lower bound for its value, or an upper value, or both. According to the type of bounds, the data points are classified as: right censored (lower bound), left censored (upper bound), and interval censored (both lower and upper bound).

By far the most typical type of censored data is the right censored data. The duration of the unfinished tasks on Mechanical Turk are right censored. In a salary survey if the income is marked as "100K+ per year" is also a right censored data point. The lifetime of a patient treated by a drug who is still alive at the end of the study is also a right censored data point.

A left censored point is an observation for which we know its maximum possible value. In a salary survey if the income is marked as "Less than 10K+ per year" this is a left censored data point.

How can we modify a maximum likelihood estimator to use censored data points?

Deriving the simple MLE estimator (no censored data points)

Let's see first how we derive a maximum likelihood estimator. I will use as an example the continuous power-law distribution but the process is largely the same for other distributions as well. For the continuous power law, the probability density function is

$Pr(x=x_i) = (\alpha-1) \cdot {x_i}^{-\alpha}$

First, let's say that we observe $n$ data points with values $x_1, \ldots, x_n$. We assume that the data points come indeed from a continuous power-law and we are trying to estimate the most likely parameter $\alpha$ that generated these points.

The likelihood of observing these data points is the probability of seeing the the value $x_1$ and the value $x_2$ and the value $x_3$, ... and the value $x_n$. So, assuming independence across the points, the likelihood function is:

$L(\alpha) = \prod_{i=1}^n Pr(x=x_i) $

By substituting the value $Pr(x=x_i)$ with the power-law instantiation, we have:

$L(\alpha) = \prod_{i=1}^n (\alpha-1) \cdot {x_i}^{-\alpha}$

We need to find the $\alpha$ that maximizes $l(\alpha)$. Instead of maximizing $l(\alpha)$ directly, we opt to maximize the logarithm which is also maximized at the same value, and it much easier to work with analytically:

$l(\alpha) = \ln(L(\alpha)) = \sum_{i=1}^n \ln\left( (\alpha-1) \cdot {x_i}^{-\alpha} \right)$

which results in:

$l(\alpha) = n \ln(\alpha-1) - \alpha \sum_{i=1}^n \log(x_i)$

To find the value of $\alpha$ that maximizes $l(\alpha)$, we take the derivative with respect to $\alpha$ and set the derivative equal to 0:

$\frac{d}{d \alpha}l(\alpha) = 0$

$n \frac{1}{\alpha-1} - \sum_{i=1}^n \log(x_i) = 0$

So the MLE estimator is:

$\alpha = 1 + n \left[\sum_{i=1}^n \ln(x_i) \right]^{-1}$

Let's move on now to the case of censored data.

Deriving the MLE estimator with right censored data

Now, let's say that we observe $n$+$m$ data points drawn from the distribution: We have $n$ completed tasks, with duration values $x_1, \ldots, x_n$ and $m$ non-completed tasks that had duration $u_1, \ldots, u_m$ when we observed them but they were still going on (and so their final duration is going to be longer than the currently observed one --- right censored points).

Again, we assume that the data points come indeed from a continuous power-law and we are trying to estimate the most likely parameter $\alpha$ that generated these points.

Now the likelihood of observing these data points is slightly different. We need to accommodate the fact that the duration for the censored observations will be longer than the currently observed one. So we get this version, (for more details see also the related Wikipedia entry) boldfacing the part that deals with the censored data:

$L(\alpha) = \prod_{i=1}^n Pr(x=x_i) \cdot$ $ \mathbf{\prod_{i=1}^m Pr(x>u_i)}$

Since $Pr(x>u_i) = {u_i}^{-(\alpha-1)}$ the likelihood becomes:

$L(\alpha) = \prod_{i=1}^n (\alpha-1) {x_i}^{-\alpha} \cdot \prod_{i=1}^m {u_i}^{-\alpha+1}$

Analogously to the case above, we take the log:

$l(\alpha) = \ln(L(\alpha))$

which becomes:

$l(\alpha) =n \ln(\alpha-1) -\alpha \sum_{i=1}^n \ln(x_i) + \sum_{i=1}^m \ln(u_i) -\alpha \sum_{i=1}^m \ln(u_i)$

and set the derivative equal to 0:

$\frac{d}{d \alpha}l(\alpha) = 0$

$n \frac{1}{\alpha-1} -\sum_{i=1}^n \ln(x_i) -\sum_{i=1}^m \ln(u_i) = 0$

So, here is the MLE estimator that uses censored data points as well:

$\alpha= 1 + n \left[ \sum_{i=1}^n \ln(x_i) +\sum_{i=1}^m \ln(u_i)\right]^{-1}$

As you will see the MLE estimator with censored data also contains the factor $\sum_{i=1}^m \ln(u_i) \right$ but the normalizing constant is still $n$ and not $n+m$.

So, what is the difference? For power laws, the higher the fraction of censored points, the lower the exponent, i.e., the tail is heavier: an expected outcome as the censored data points tend to represent unobserved tail points. For example, for Mechanical Turk, the exponent without censored data points is 1.35 and with censored data points is 1.29. Not a big difference in this case, but there are situations where this correction can change significantly the overall analysis (e.g., if the exponent is close to 2).

Turker Demographics vs Internet Demographics

2009-03-16T16:53:00.007-04:00

My post about the demographics of Mechanical Turk workers is one of the most popular posts on this blog, and I often see the results being discussed in other forums as well. One of the common questions that I see is: "How these demographics compare to the general Internet population?"

Apparently, this is not a very easy question to answer. It is relatively hard to find publicly available data about the demographics of Internet users. Fortunately, I found some data from ComScore, dating back to June 2008. I also had data about Mechanical Turk from two separate surveys that I ran on October 2008 and on December 2008 (both asking 1000 Turkers). The results across the two MTurk surveys were rather consistent, indicating that the results are rather trustworthy.

So, how Turkers compare to the general US Internet population? The short answers:

Turkers are younger. 54% of Turkers are between 21-35 years old, compared to 22% of the general population.
Turkers are mainly female. 70% of the Turkers are female, compared to 50% of the general population.
Turkers have lower income. 65% of Turkers have household income less than 60K, compared to 45% of the general population.
Turkers have smaller families. 55% of Turkers do not have children, compared to the 40% of the general population.
Geographical distribution of Turkers and Internet users is similar.
Race composition of Turkers and Internet users is similar, although there are slightly more Asians on Mechanical Turk.

Of course, the last two bullets may be simply the result of the first: Younger people have lower income, do not have children, and live in smaller households.

For those of you that would like to have a more detailed look at the statistics, here is the corresponding table:

	June 2008	October 2008	December 2008
	Internet	Turks	Turks
Total Audience	100	100	100
Persons - Age
Persons: 15+	85.9	100	100
Persons: 18+	80.1	99.6	99.5
Persons: 21+	74.3	92.9	91.1
Persons: 35+	52.4	39.3	37.1
Persons: 50+	24.3	11.2	10.7
Persons: 55+	16.2	5.2	5.4
Persons: 2-11	9.5	0	0
Persons: 2-17	19.9	0.2	0.4
Persons: 6-11	7.4	0	0
Persons: 6-14	12	0	0
Persons: 9-14	8.9	0	0
Persons: 12-17	10.4	0.2	0.4
Persons: 12-24	22.9	19	21.5
Persons: 12-34	38	57.8	60
Persons: 12-49	66.2	87.4	88.2
Persons: 18-24	12.5	18.7	21.1
Persons: 18-34	27.6	57.5	59.7
Persons: 18-49	55.8	87.2	87.8
Persons: 21-34	21.9	53.3	53.9
Persons: 21-49	50	82.9	82
Persons: 25-34	15.1	38.8	38.6
Persons: 25-49	43.2	68.4	66.7
Persons: 25-54	51.3	75.2	72.3
Persons: 35-44	18.7	22.4	21.5
Persons: 35-49	28.2	29.7	28.1
Persons: 35-54	36.2	36.4	33.7
Persons: 35-64	46.8	41.4	38.8
Persons: 45-54	17.6	14	12.2
Persons: 45-64	28.1	19	17.4
Persons: 55-64	10.5	5	5.2
Persons: 65+	5.7	0.7	1.1
Males - Age
All Males	49.5	28	36.6
Male: 15+	42.1	28	36.6
Male: 18+	39.1	27.8	36.3
Male: 21+	36.1	24.7	32.4
Male: 35+	25.7	9.5	11.3
Male: 50+	12	2.8	2.6
Male: 55+	8.1	1.4	1.1
Male: 2-11	4.9	0	0
Male: 2-17	10.4	0.1	0.2
Male: 6-11	3.9	0	0
Male: 6-14	6.3	0	0
Male: 9-14	4.5	0	0
Male: 12-17	5.5	0.1	0.2
Male: 12-24	11.6	7.5	9.1
Male: 12-34	18.9	17.3	24.2
Male: 12-49	32.5	25	33.9
Male: 18-24	6.1	7.4	8.9
Male: 18-34	13.4	17.2	23.9
Male: 18-49	27.1	24.9	33.7
Male: 21-34	10.4	15.2	21.1
Male: 21-49	24.1	22.9	30.8
Males: 25-34	7.3	9.8	15
Male: 25-49	20.9	17.6	24.8
Male: 25-54	24.8	19	26.3
Males: 35-44	9.1	6	8
Male: 35-49	13.7	7.7	9.7
Male: 35-54	17.5	9.1	11.2
Male: 35-64	22.6	10.6	12.3
Male: 45-54	8.4	3.1	3.2
Male: 45-64	13.5	4.5	4.3
Males: 55-64	5.1	1.4	1.1
Males: 65+	3	0	0.1
Females - Age
All Females	50.5	72	63.4
Female: 15+	43.8	72	63.4
Female: 18+	41	71.9	63.3
Female: 21+	38.2	68.2	58.7
Female: 35+	26.8	29.8	25.8
Female: 50+	12.3	8.3	8.1
Female: 55+	8.1	3.8	4.3
Female: 2-11	4.6	0	0
Female: 2-17	9.5	0.1	0.1
Female: 6-11	3.6	0	0
Female: 6-14	5.7	0	0
Female: 9-14	4.5	0	0
Female: 12-17	4.9	0.1	0.1
Female: 12-24	11.3	11.5	12.3
Female: 12-34	19.1	40.5	35.9
Female: 12-49	33.6	62.4	54.3
Female: 18-24	6.4	11.5	12.2
Female: 18-34	14.2	40.5	35.8
Female: 18-49	28.7	62.4	54.1
Female: 21-34	11.5	38.1	32.8
Female: 21-49	25.9	60	51.2
Females: 25-34	7.8	28.9	23.6
Female: 25-49	22.3	50.9	41.9
Female: 25-54	26.5	56.2	46
Females: 35-44	9.5	16.4	13.4
Female: 35-49	14.5	21.9	18.4
Female: 35-54	18.7	27.3	22.4
Female: 35-64	24.1	30.8	26.5
Female: 45-54	9.2	10.9	9
Female: 45-64	14.6	14.5	13.1
Females: 55-64	5.4	3.6	4.1
Females: 65+	2.6	0.7	1
HH Income (US)
HHI USD: Less than 15,000	6	11.4	12.9
HHI US: Under $25K	9.3	22.8	23.1
HHI US: Under $60K	44.5	64.8	60.5
HHI US: $60K+	55.5	34.8	39.1
HHI US: $75K+	43	22.7	27.5
HHI USD: 15,000 - 24,999	3.4	11.4	10.1
HHI USD: 25,000 - 39,999	9.9	21.8	18.9
HHI USD: 40,000 - 59,999	25.3	20.2	18.6
HHI USD: 60,000 - 74,999	12.6	12.1	11.6
HHI USD: 75,000 - 99,999	17.7	10.2	11.5
HHI USD: 100,000 or more	25.3	12.5	16
Region (US)
Region US:West North Central	7.6	5.8	7.5
Region US:Mountain	6.9	6.4	7.4
Region US:Pacific	15.4	13.3	15.7
Region US:New England	5.5	6.4	4.7
Region US:Mid Atlantic	14.2	13.9	15.8
Region US:South Atlantic	18.7	19.2	19.9
Region US:East South Central	5.1	8.3	5.2
Region US:West South Central	10.5	10.7	9
Region US:East North Central	16.1	15.7	14.8
Children
Children:No	39.3	52.7	57.6
Children:Yes	60.7	47.3	42.3
HH Size
HH Size: 1	4.4	17.7	17.3
HH Size: 2	24.2	28.9	30.6
HH Size: 3	21.4	19.7	19.2
HH Size: 4	25.3	20.5	21.9
HH Size: 5+	24.8	12.9	10.7
HH Size: 1-2	28.5	46.6	47.8
HH Size: 3+	71.5	33.5	32.7
Race
Race:White	87.3	82.7	82
Race:Black	8	6.5	5.3
Race:Asian	1.6	5.7	6.8
Race:Other	3.1	4.9	5.8

Mechanical Turk: Profitable or Not?

2009-03-11T00:02:00.014-04:00

I was chatting with a couple of students of mine, who are trying to build a startup using Mechanical Turk. So, they asked me what is the value of the tasks that are being posted every day on Mechanical Turk.

Since I have the archive of the tasks posted on MTurk for the last couple of months, this was an easy question to answer. A simple query on the database, find the new HITs posted every hour, group by day, and here is the plot:

Long story short, the average value of HITs posted in any day is around \$2000. I have not analyzed the distribution of the values, but it seems to be (not surprisingly) a power-law or a lognormal.

The 2K/day value means that the average revenue per day for Amazon is around 200 per day (10% of the requester's payment), or 6K/month. This hardly covers the expense of dedicating a developer to the service!

It seems that Mechanical Turk is not generating any significant revenue for Amazon. It is also unlikely that it generates any profit. And we know these days what happens to products that are not generating profits...

Thankfully Amazon uses Mechanical Turk for its own purposes, so there are second-degree benefits for Amazon to keep the service around. I truly hope though that the service will attract more customers soon.

Update: I should also clarify that my figures are slight underestimates of the actual figures: I can only "see" Mechanical Turk through the eyes of an average worker. So I cannot see if a requester asks multiple people to complete the same HIT and, sometimes, I cannot observe the details for HITs for which I have not passed the qualification test. I still think that the numbers will be at the same order of magnitude.

Update 2: If you want more details see my previous post on the dynamics of Mechanical Turk and the chart at http://hyperion.stern.nyu.edu/mturk/ that shows the available HITs and rewards at any given time.

Human Computation Workshop (HCOMP 2009)

2009-03-06T21:39:00.003-05:00

Are you interested in Mechanical Turk and applications? Do you think that the ESP Game and ReCAPTHA's are great ideas and have some ideas that you want to share with the world? Or you are just interested in learning about human computation in general?

Now you can! We (an embarrassingly long list of organizers) are organizing a half-day workshop at KDD 2009 in Paris this year. The workshop will be on June 28th, and submissions are due on April 18, 2009 8pm Eastern Time. You can find more details about the submission requirements and find other useful information at http://www.hcomp2009.org

Below you can is the complete Call for Papers, for those that enjoy reading such stuff:

Human Computation Workshop (HCOMP 2009)
KDD-09 Workshop, Paris France
June 28, 2009

We invite you to participate in the first annual Human Computation Workshop
(HCOMP 2009), to be held on June 28th in conjunction with the KDD-09
conference (http://www.sigkdd.org/kdd2009/) in Paris, France.

Human computation is a 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. The goal of this half-day workshop is to bring
together academic and industry researchers in a stimulating discussion of
existing human computation applications (e.g. games, CAPTCHAs, Mechanical
Turk) 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.

Detailed information about the workshop and submission procedures can be
found at http://www.hcomp2009.org. We solicit long papers (at most nine
pages), short papers (at most four pages) and demos. Demo submissions must
include either a previously published paper or a one page extended abstract.
Deadline for submission is April 18, 2009 8pm Eastern Time.

Organizing Committee
---------------------
Paul Bennett (Microsoft Research)
Raman Chandrasekar (Microsoft Research)
Max Chickering (Microsoft Live Labs)
Panos Ipeirotis (New York University)
Edith Law (Carnegie Mellon University)
Anton Mityagin (Microsoft Live Labs)
Foster Provost (New York University)
Luis von Ahn (Carnegie Mellon University)