Datawocky

Traveling: In India this week

I'm on vacation, traveling in India. First stop Mumbai -- the main event is Lakme India Fashion Week. My wife, Kaushie Adiseshan, is a fashion designer. She is showing the latest collection from her line, Pink Elf, on the runway today. She's a veteran -- having shown several times at LIFW and San Francisco Fashion Week -- but there are aways butterflies before the event.

I'm looking forward to the parties after! Last time the entire Indian cricket team showed up -- let's see what we get today.

Update: The show was fantastic, as was the party hosted by Neeta Lulla at Henry Tham's last night. Bollywood superstar Aishwarya Rai was at the party!

Update 2: By popular request, here are some photos from the after-party.

More data usually beats better algorithms

I teach a class on Data Mining at Stanford. Students in my class are expected to do a project that does some non-trivial data mining. Many students opted to try their hand at the Netflix Challenge: to design a movie recommendations algorithm that does better than the one developed by Netflix.

Here's how the competition works. Netflix has provided a large data set that tells you how nearly half a million people have rated about 18,000 movies. Based on these ratings, you are asked to predict the ratings of these users for movies in the set that they have not rated. The first team to beat the accuracy of Netflix's proprietary algorithm by a certain margin wins a prize of $1 million!

Different student teams in my class adopted different approaches to the problem, using both published algorithms and novel ideas. Of these, the results from two of the teams illustrate a broader point. Team A came up with a very sophisticated algorithm using the Netflix data. Team B used a very simple algorithm, but they added in additional data beyond the Netflix set: information about movie genres from the Internet Movie Database (IMDB). Guess which team did better?

Team B got much better results, close to the best results on the Netflix leaderboard!! I'm really happy for them, and they're going to tune their algorithm and take a crack at the grand prize.  But the bigger point is, adding more, independent data usually beats out designing ever-better algorithms to analyze an existing data set. I'm often suprised that many people in the business, and even in academia, don't realize this.

Another fine illustration of this principle comes from Google. Most people think Google's success is due to their brilliant algorithms, especially PageRank. In reality, the two big innovations that Larry and Sergey introduced, that really took search to the next level in 1998, were:

1. The recognition that hyperlinks were an important measure of popularity -- a link to a webpage counts as a vote for it.
2. The use of anchortext (the text of hyperlinks) in the web index, giving it a weight close to the page title.

First generation search engines had used only the text of the web pages themselves. The addition of these two additional data sets -- hyperlinks and anchortext -- took Google's search to the next level. The PageRank algorithm itself is a minor detail -- any halfway decent algorithm that exploited this additional data would have produced roughly comparable results.

The same principle also holds true for another area of great success for Google: the AdWords keyword auction model. Overture had previously proved that the model of having advertisers bid for keywords could work. Overture ranked advertisers for a given keyword based purely on their bids. Google added some additional data: the clickthrough rate (CTR) on each advertiser's ad. Thus, to a first approximation, Google ranks advertisers by the product of their bid and their CTR (this was true in the first version of AdWords; they now use more considerations). This simple change made Google's ad marketplace much more efficient than Overture's. Notice that the algorithm itself is quite simple; it is the addition of the new data that made the difference.

To sum up, if you have limited resources, add more data rather than fine-tuning the weights on your fancy machine-learning algorithm. Of course, you have to be judicious in your choice of the data to add to your data set.

Update: Thanks for all the comments. Some of them raise interesting issues, which I'd like to address in a follow-up post. I'm traveling without good internet access until the weekend, so it will have to wait until I get back. Stay tuned!

Update 2: There's now a follow-up post that addresses some of the issues raised in the comments.

Update 3:  Here's another illustration of the same point: Simple math using lots of data is way more accurate than comScore's analysis in predicting Google's earnings.

Enumerating User Data Collection Points

The New York Times had a great piece yesterday by Louise Story, titled To Aim Ads, Web is Keeping a Closer Eye on You. The piece enumerates data collection points: opportunities for internet companies to collect data on users -- data that might enable better ad targeting. The piece comes out with some eye-popping numbers, such as: Yahoo collects data on each user 2520 times a month, on average!

Now, that's a very interesting statistic, and this piece makes a great contribution by putting for the first time a tangible measure on data collection. Let's take a closer look at the methodology, outlined in a post by Story on the NYTimes blog Bits. The methodology was jointly developed with ComScore. At the highest level, many web companies operate their own web properties in addition to an ad network that serves ads on third-party sites, so let's first look at just the owned-and-operated properties. Here's the salient bit:

The comScore study tallied five types of “data collection events” on the Internet for 15 large media companies. Four of these events are actions that occur on the sites the media companies run: Pages displayed, search queries entered, videos played, and advertising displayed. Each time one of those four things occurs, there is a conversation between the user’s computer and the server of the company that owns the site or serves the ad. The fifth area that comScore looked at was ads served on pages anywhere on the Web by advertising networks owned by the media companies.

By this metric, the number of data collection points per person per month at Yahoo is 699 (the difference between this number and the previous 2520 number is to Yahoo's off-site ad serving on its ad network). There are a few problems with this analysis:

1. It assigns the same value to every data collection event. Search events reveal way more intent than  content page impressions, so that's certainly not accurate. However, let's leave this issue aside for the moment, and assume we are just enumerating data collection events, not actually measuring their value. More on that in a later post.
2. There is some doublecounting going on here. Advertising is displayed on pages, so counting both the page view and the ad impressions on it as unique data collection events is not accurate. In fact, the data collected based on the page view is often used to target the ad impression. There is sometimes additional information from ads, but only when ads are actually clicked -- but since clickthroughs on display ads are very low (in the 0.1% range), we can safely ignore that additional information, given the gross approximations we are making in this analysis.
3. Finally, the same problem as in (2) applies to ads served by the ad networks on third-party sites, except it's probably even worse. Each page on average has 2-3 ad units. So, the ads-served might be overcounting actual page view events by a factor of 2-3.

If we recalculate the numbers after making the adjustments required by (2) and (3), it appears we will end up with numbers that are a factor of 2 to 3 (or even more) smaller than the comScore/NYTimes estimates. Also, the reduction will be larger for Yahoo and AOL/Ad.com than for Google, because Google serevs many fewer display ads and is less affected by adjustment (2) -- although adjustment (3) is still applicable since content ages often have more than 1 adsense unit.

I would love to hear more from comScore and Louise Story about their methodology and whether I missed something in my analysis here.

Datawocky

My favorite poem of all time is Lewis Carroll's "Jabberwocky." Here's how it starts:

`Twas brillig, and the slithy toves
  Did gyre and gimble in the wabe:
All mimsy were the borogoves,  
    And the mome raths outgrabe.

Here's the whole poem.

Jabberwocky is a unique poem because it uses many nonsense words, such as "brillig", "slithy" and so on, that you'll find in no English dictionary. Yet despite this, if you read the poem and let yourself sink into it, you can actually get a pretty good understanding of its meaning -- sometimes you can even figure out what the nonsense word actually means!

Likewise, it's sometimes difficulty to analyze data one piece at a time. But if you have a large amount of data, there are often surprising and useful patterns you can unearth. And the more data you start with, the more likely you'll find something useful.

Thanks to the internet, the amount of data that is available to analyze is increasing at a rapid pace. Terabytes of web server and activity logs accumulate every day at the more popular websites. Out of these have emerged some interesting patterns, such as collaborative filtering (which Amazon.com uses to recommend products based on comparing your activity with those of other users). The web itself is a big source of data, giving rise to patterns such as PageRank to determine popularity. And social media, including social networks and collaborative content efforts, such as Wikipedia, provide more grist for the data mill.

There's a whole specialty of Computer Science devoted to analyzing large amounts of data: it's called Data Mining. I co-teach a class on Data Mining at the Computer Science Department at Stanford. Data Mining is closely related to and borrows ideas from Statistics, but what sets the two apart is the emphasis on large data -- terabytes of it.

In this blog, I'll discuss data mining, but with special emphasis on the areas that I find most fascinating: search, social media, and advertising. I'll periodically talk about data mining techniques, but more often about their consequences.