Tag Archives: ordering

A Recent History of the Bake-Off

The Web and I share a common obsession at the moment: bake-off style preference ordering. What is bake-off style preference ordering (or BOSPO, for the sake of ridiculousness)?

BOSPO involves ordering a long list of items by comparing two items at once. Kitten War is my favorite example. Assume you have several million kitten pictures, and you need to order them from cutest to least cute. No one has the time or mental fortitude to sit down and create a full ordering of a million-plus pictures. However, anyone can look at just two kittens and pick the cuter one. After lots and lots of such comparisons, one can order the pictures according to the percentage of head-to-head comparisons which they win. Cuter kittens rise to the top, and the less cute, uh… sink to the bottom.

Just yesterday, Stephen Colbert joined the online BOSPO fray by promoting spookyordooky.com on his show. Here’s how it works:
1. You submit a picture of yourself in your Halloween costume. (Optional)
2. You see two costume pictures and choose the one that is “spooky.” The other is dooky by implication, I assume.
3. Repeat 2 until tired.
4. An ordering emerges. Presumably, Spooky or Dooky uses win percentage as its ordering metric. However, it may use something more sophisticated like the Elo rating system. The Elo system was just brought into the public consciousness as “The Algorithm” behind Facemash in the movie The Social Network.

Speaking of Facemash, TechCrunch reports a Facebook app with similar capabilities already exists: ULikeN

Of course, my favorite BOSPO implementation is my own creation: Lepidoptera. Lepidoptera is a persistent online to-do list prioritizer. That means you can keep an ongoing to-do list, re-prioritize it every day and access it anywhere you can get Internet access.

The comparison engine that drives Lepidoptera not only attempts to order your items (in this case, things you need to do) in the right order, but it also chooses the best two items to maximize the information it gains with each comparison. It also avoids bombarding you with the same items and same comparisons, so the task of comparing does not become tiresome.

Lepidoptera is not the first prioritizer on the Web, but I believe it is the most complete, the most user-friendly and the only one that will persistently store your information. I was inspired to build it by research similar to BOSPO that I heard about here at UCSD, my own difficulty prioritizing my to-do list, and yes, by Kitten War.

Take a look at all these apps and add more links if you know of more BOSPOs out there.

UPDATE: The Algorithm for Facemash in The Social Network

Original post: The Algorithm for Facemash in The Social Network

After some Googling, it would appear that the Facemash algorithm corresponds to the Elo rating system. Thus, the equations involved are:
Ea = 1/(1 + 10^((Rb -Ra)/400))
Eb = 1/(1 + 10^((Ra -Rb)/400))

The Mathematical Details section of the wiki article explains the implementation of the algorithm.
Thanks to this Quora article for the most relevant links.

I’m surprised to see this algorithm treated with such reverence in the movie. While it is sophisticated and useful, and has been used in official chess rankings for decades, it has recently taken a beating at the hands of modern data miners. As of 10/8/2010, ninety teams have developed more predictive methods than Elo ratings for handicapping chess matches: see the Kaggle contest leaderboard.

The Algorithm for Facemash in The Social Network

In the Facebook movie The Social Network, Mark Zuckerberg builds a website to compare the attractiveness of girls. Behind the scenes, we’re made to believe, an algorithm originally developed to rank chess players is employed to rank these women by their attractiveness.

The equations driving the algorithm are shown briefly, written on young Zuck’s dorm room window. From my (possibly incorrect) memory the two equations look like this:
Ea = 1/(1 + 10 * (Ra-Rb) * 400)
Eb = 1/(1 + 10 * (Rb-Ra) * 400)

My interpretation of the left hand of each equation is that these are expectations. I would assume Ea is the expectation that Girl A will win the match. Eb would thus be the expectation that Girl B would win. This is where my puzzlement with these equations begins. Surely Ea and Eb cannot be independently calculated.

My guess as to Ra and Rb are that these are the rates at which Girl A and Girl B have been winning their other matches. For example, if Girl A had won half her matches, Ra would be 0.50. Similarly, if Girl B has won only one of five matches, Rb would be 0.20.

That made sense to me for the brief moment it was displayed in the movie, but actually playing with the equations yields non-useful results. For example, assume Girl A has won 5 of 10 matches, and Ra is 0.50. Assume Girl B has won 2 of 8 matches, and Rb is 0.25. You might expect the algorithm to return something along the lines of Ea = .67 and Eb = .33. In other words, it is twice as likely that Girl A will win as compared to Girl B winning.

Instead the results are nonsensical. Ea = 0.000999 and Eb = -0.001001. Obviously, these cannot be interpreted as expectations/probabilities.

My guess is that one of the following issues is occurring:
1) My memory of the equations is incorrect.
2) The equations are gibberish – meant to look math-y enough for the brief moment they are onscreen.
3) I’m misconstruing the E and/or R terms.

I’m interested, because I happen to be building a number of websites that use a “bake-off” method very similar to that of Facemash. Currently, I’m working on Lepidoptera – an online to-do list with bake-off priority contests.

I searched for awhile for formal algorithms to perform ordering based on head-to-head contest results and came up empty. So the algorithm I use is based on my own best reasoning. I’d like to understand the Facemash algorithm so I can compare results.

Anyone else interested in figuring this out? Leave me comments or blog back.