Datawocky

Twittering live from All Things D Conference

Kara Swisher and Walt Mossberg sure know how to throw a conference. The All Things D conference organized by them is my all-time favorite among tech conferences. This year's edition, D6, is happening at Carlsbad (near San Diego) this Tuesday through Thursday. As in the past, there's a stellar line-up this year too, including Bill Gates, Steve Ballmer, Jeff Bezos, and Mark Zuckerberg.

The highlight at last year's conference was Bill Gates and Steve Jobs sharing the stage after many, many years, A big part of the charm is the eclectic mix of attendees and speakers, including George Lucas and Martha Stewart.

I'm spending the day today driving down from the bay area to Carlsbad. If you read this blog and are at the conference, please say hello.

I'll be twittering live from the conference. If you'd like to follow me, my twitter id is anand_raj.

Are Machine-Learned Models Prone to Catastrophic Errors?

A couple of days ago I had coffee with Peter Norvig. Peter is currently Director of Research at Google. For several years until recently, he was the Director of Search Quality -- the key man at Google responsible for the quality of their search results. Peter also is an ACM Fellow and co-author of the best-selling AI textbook Artificial Intelligence: A Modern Approach. As such, Peter's insights into search are truly extraordinary.

I have known Peter since 1996, when he joined a startup called Junglee, which I had started together with some friends from Stanford. Peter was Chief Scientist at Junglee until 1998, when Junglee was acquired by Amazon.com. I've always been a great admirer of Peter and have kept in touch with him through his short stint at NASA and then at Google. He's now taking a short leave of absence from Google to update his AI textbook. We had a fascinating discussion, and I'll be writing a couple of posts on topics we covered.

It has long been known that Google's search algorithm actually works at 2 levels:

1. An offline phase that extracts "signals" from a massive web crawl and usage data. An example of such a signal is page rank. These computations need to be done offline because they analyze massive amounts of data and are time-consuming. Because these signals are extracted offline, and not in response to user queries, these signals are necessarily query-independent. You can think of them tags on the documents in the index. There are about 200 such signals.
2. An online phase, in response to a user query. A subset of documents is identified based on the presence of the user's keywords. Then, these documents are ranked by a very fast algorithm that combines the 200 signals in-memory using a proprietary formula.

The online, query-dependent phase appears to be made-to-order for machine learning algorithms. Tons of training data (both from usage and from the armies of "raters" employed by Google), and a manageable number of signals (200) -- these fit the supervised learning paradigm well, bringing into play an array of ML algorithms from simple regression methods to Support Vector Machines. And indeed, Google has tried methods such as these. Peter tells me that their best machine-learned model is now as good as, and sometimes better than, the hand-tuned formula on the results quality metrics that Google uses.

The big surprise is that Google still uses the manually-crafted formula for its search results. They haven't cut over to the machine learned model yet. Peter suggests two reasons for this. The first is hubris: the human experts who created the algorithm believe they can do better than a machine-learned model. The second reason is more interesting. Google's search team worries that machine-learned models may be susceptible to catastrophic errors on searches that look very different from the training data. They believe the manually crafted model is less susceptible to such catastrophic errors on unforeseen query types.

This raises a fundamental philosophical question. If Google is unwilling to trust machine-learned models for ranking search results, can we ever trust such models for more critical things, such as flying an airplane, driving a car, or algorithmic stock market trading? All machine learning models assume that the situations they encounter in use will be similar to their training data. This, however, exposes them to the well-known problem of induction in logic.

The classic example is the Black Swan, popularized by Nassim Taleb's eponymous book. Before the 17th century, the only swans encountered in the Western world were white. Thus, it was reasonable to conclude that "all swans are white." Of course, when Australia was discovered, so were the black swans living there. Thus, a black swan is a shorthand for something unexpected that is outside the model.

Taleb argues that black swans are more common than commonly assumed in the modern world. He divides phenomena into two classes:

1. Mediocristan, consisting of phenomena that fit the bell curve model, such as games of chance, height and weight in humans, and so on. Here future observations can be predicted by extrapolating from variations in statistics based on past observation (for example, sample means and standard deviations).
2. Extremistan, consisting of phenomena that don't fit the bell curve model, such as the search queries, the stock market, the length of wars, and so on. Sometimes such phenomena can sometimes be modeled using power laws or fractal distributions, and sometimes not. In many cases, the very notion of a standard deviation is meaningless.

Taleb makes a convincing case that most real-world phenomena we care about actually inhabit Extremistan rather than Mediocristan. In these cases, you can make quite a fool of yourself by assuming that the future looks like the past.

The current generation of machine learning algorithms can work well in Mediocristan but not in Extremistan. The very metrics these algorithms use, such as precision, recall, and root-mean square error (RMSE), make sense only in Mediocristan. It's easy to fit the observed data and fail catastrophically on unseen data. My hunch is that humans have evolved to use decision-making methods that are less likely blow up on unforeseen events (although not always, as the mortgage crisis shows).

I'll leave it as an exercise to the interested graduate student to figure out whether new machine learning algorithms can be devised that work well in Extremistan, or prove that it cannot be done.

Why the World Needs a New Database System

The internet and its usage are generating vast amounts of data. The volume of new data being generated today is unprecedented in human history. Much intelligence might be gleaned by intelligently mining this trove; yet most companies today archive most of their data and process only a tiny sliver of it. For example, most internet companies I know with significant traffic archive all usage data older than a couple of months. Who knows what gems of insight they're missing?

Over the past few years, the hardware platform that can tackle very high data volumes has been identified. It is the cluster of commodity Linux nodes interconnected using commodity gigabit ethernet. Google popularized the platform and introduced Map Reduce, which today is the best tool available for serious data crunching on  massive scale. The Hadoop project makes Map Reduce available to the rest of us.

Yet the Map Reduce paradigm has its limitations. The biggest problem is that it involves writing code for each analysis. This limits the number of companies and people that can use this paradigm. The second problem is that joins of different data sets is hard. The third problem is that Map Reduce works on files and produces files; after a while the number of files multiplies and it becomes difficult to keep track of things. What's lacking is a metadata layer, such as the catalog in database systems. Don't get me wrong; I love Map Reduce, and there are applications that don't need these things, but increasingly there are applications that do.

Database systems have been the workhorses of conventional (small to medium scale) data analysis applications for a couple of decades now. They have some advantages over Map Reduce. SQL is a standard for ad-hoc data analysis without actually writing code. There's a big ecosystem around SQL: people familiar with SQL, tools that work with SQL, application frameworks, and so on. Joins are straightforward in SQL, and databases provide implementations such as hash joins that scale well to big data. There is a large body of knowledge around query optimization that allows declaratively specified SQL queries to be optimized for execution in nontrivial ways. There is support for concurrency, updates, and transactions. There is a metadata catalog that allows people and programs to understand the contents of the database.

No one has been able to make database systems scale to the data volumes we are seeing today at an affordable price point. Sure, there is Teradata, with their custom designed hardware/software solution. They are the only serious game in town for sophisticated analysis of data in the terabytes. But the entry price point is in the several millions of dollars, and if your data size increases, the price per incremental terabyte is also at nosebleed levels. Also, proprietary hardware ignores the inexorable logic of Moore's law.

What the world needs is a database system natively designed and architected from the ground up for the new hardware platform: commodity clusters. Such a system greatly expands the number of companies and people that can do data analysis on terabytes of data. I'm delighted that Aster Data this week launched exactly such a database system this week. I led the seed round investment in Aster Data and sit on their board, so I've been waiting for this launch with great anticipation.

Aster comes with impressive testimonials from early customers. MySpace has been using Aster for several months now to analyze their usage data. Their data set has grown from 1 terabyte to 100 terabytes in just 100 days -- adding 1 terabyte a day. No other database installation in the world has grown at this rate. The growth is enabled by the commodity hardware platform underneath -- just add a server or a rack as the data grows. Another early adopter is Aggregate Knowledge, whose dataset has also grown at an impressive rate.

There's an interesting backstory to my involvement with Aster. When I taught the Distributed Databases course at Stanford in 2004, my TA was a bright young PhD student named Mayank Bawa. I was very impressed with Mayank's intellectual abilities and his can-do attitude. While working on the course we got to discussing how there is a shift happening in hardware platforms, but no database systems vendor has created a system targeting the new hardware platform. A few months later, Mayank told me he intended to start a company to build just such a database, along with two other Stanford graduate students: Tassos Argyros and George Candea. It was a brain dead simple investment decision for me.

Mayank, Tassos and George are among the best thinkers I know on the topic of large scale data analytics. They have been exceedingly thoughtful in the architecture of their new database. They have some really nifty stuff in there, including incremental scalability, intelligent data partitioning, and query optimization algorithms. One of the coolest demos I've seen is when they run a large query that touches terabytes of data, and then kill several of the nodes in the system that are actively processing the query. The system transparently migrates query processing, and out pop the results. This kind of behavior is essential when you're dealing with queries that can take several minutes to hours to execute, increasing the likelihood of failures during query processing, especially when using commodity nodes.

The LAMP stack, with MySQL as the base, has transformed and democratized web application development. In a similar vein, I expect that we will see the emergence of a stack that democratizes large-scale data analytics applications. Aster Data could well be the foundation of that stack.

Data, Algorithms, and Powerset

Powerset finally launched their search engine last night. It's been over two years in the making, and the company has much hype surrounding their natural language technology. 

The new search engine has received mixed reviews. For example, while Mike Arrington at TechCrunch fell in love at first sight, the comments following the post tell a very different story. The most balanced review I've seen so far is from Danny Sullivan at Search Engine Land.

Disclosure: My company Kosmix also builds search technology, albeit of a very different kind. I don't consider Kosmix in any way to be a PowerSet competitor, and in this post I'm wearing my blogger hat and not my Kosmix hat. Moreover, this post is not really about PowerSet at all, but about data and algorithms, using PowerSet as the example du jour.

To boil down both my personal experience playing with PowerSet and what I'm seeing in the reviews: some of the features (like the Factz) are cool. The biggest weakness is that PowerSet today searches only two data sets: Wikipedia and Freebase. And while these are both very large and very useful datasets, they're not nearly enough to answer many real-world user queries.

The TechCrunch comments and Danny Sullivan's posts both contain examples that point out the strengths and weaknesses of PowerSet's search. Here's an example from my own personal experience: in my previous post, I used the phrase "new wine in an old bottle". I was curious about the origin of this phrase (since I had also heard people say "old wine in a new bottle" -- which came first?) So I typed the search "origin of expression new wine in old bottle" into both PowerSet and Google. Google nailed it in the first result (from Yahoo Answers), while Powerset was lost. Ditto for "How old was Gandhi when he was killed?"

While people can argue about the applicability of natural language processing to search, to the quality of PowerSet's implementation, and so on, I have a much simpler point of view. I believe PowerSet has some pretty cool IP in its algorithms and has done as good a job as they possibly can with it. The problem is, they don't have enough data to work with. (Another way of saying this is, PowerSet's index is a SubSet of Google's index.)

The primary reason Google's search is useful is that there is lots and lots of data on the web, and Google indexes  so much of it.  Yes, Google's search algorithms are fantastic, but they wouldn't work anywhere as well if they didn't have so much data underneath them. Consider my search about new wine and old bottles. The reason Google nails it is because there's a page on the web that uses the exact phrase I typed into the search box. Same for the Gandhi example. The cool thing for Google is, people who search often use phrases in the same was as people who write web pages (especially on community sites such as Yahoo Answers). Instead of doing any NLP, they just need to index a really huge corpus of text and look for near-exact matches.

To use a phrase from an earlier post on this blog, "More data usually beats better algorithms". And nowhere is that more true than it is in search. (The natural question to ask is, why not both more data and better algorithms? The answer in this case is that many of the techniques seem to rely on the structure and general cleanliness of Wikipedia and Freebase, so it's not clear how well they will scale to the web as a whole.)

What of PowerSet? I for one really love their Wikipedia search, and will use them to search Wikipedia and Freebase. As Danny Sullivan points out in his post, perhaps the right business model for PowerSet lies in enterprise search rather than in web search.

Why Yahoo Glue is a Bigger Deal than You Think

Yahoo's India team quietly launched Yahoo Glue out of the glare of the media circus around Yahoo these days.  Glue has been noticed by a few commentators (e.g., TechCrunch), who mostly see it as response to Google's Universal Search (or Ask's search interface). They might be missing the point. Glue is fundamentally different from Universal Search and represents a whole new way of thinking about search.

The fundamental distinction is: where do the results come from? Google's Universal Search searches across Google's properties: web search, image search, YouTube, Scholar, Google News, and so on.  Glue, on the other hand, includes not just Yahoo properties (web search, Yahoo! Answers, Flickr), but also pulls in results from WebMD, HowStuffWorks, and even (ironically) Google Blog Search and YouTube. For example, compare Universal Search (diabetes) with Glue (diabetes). In this respect, Glue bears more similarity to mashups such  as Addict-o-Matic than to Universal Search.

The Web today is a far different place from what it was when Google's search paradigm was invented. The web was then a collection of documents; it is now a collection of applications. Applications such as Facebook, MySpace, YouTube, and Yelp. Each application has its own deep collection of data, and we tend to think of them as being different information types rather than just "web pages". Yet the search model flattens each of these rich interactive services into a collection of web pages that can be indexed -- that's really putting very new wine in a very old bottle.

The one-index-fits-all model forces a linear ranking of incomparable types, such as images, videos, how-to content, facts, and opinion. That's really comparing apples to oranges. The correct way is to deal with each of these information sources as a first class citizen, with its own kind of data and interaction paradigm. Let them compete for real estate on a 2-dimensional search results page (as opposed to 1-dimensional list), and may the best ones win.

Of course, there are many technical challenges to be solved in getting there.  Sending each query to every web application is a recipe for disaster; and dealing with many different APIs is not conducive to scaling. To keep themselves relevant, however, search engines must evolve from indexes to intelligent routers of searches to third-party applications. 

Removing Friction at the Bottom of the Pyramid

Dharavi is a slum of over a million souls packed into a single square mile in the heart of Mumbai, India. It holds the dubious distinction of being the largest slum in Asia.  Families of 15 crowd into 300-square-feet tenements, sharing the space with many more mice. It's hard to imagine the people of Dharavi as consumers moving up the economic ladder, but that is precisely what is happening.

Kashyap Deorah moved back to India from the US recently, and has spent the last several months visiting Dharavi to understand its micro-economy. Every street in Dharavi is home to an electronics dealer. The main business is used cell phones and prepaid SIM cards; India now has over 246 million cell phone subscribers, with the number growing at a scorching pace. One of the hottest items is -- hold your breath -- used flat screen LCD televisions! Surprising, yet clear enough when you think about it: space is at a premium, so slum-dwellers behave rationally in opting for flat screen televisions.

This anecdote illustrates the demand for used consumer durables of all kinds among the upwardly-mobile masses in India. McKinsey has published a fantastic study on how the rapidly expanding Indian economy is creating new consumers. This study divides Indian households into 5 segments based on household income: Globals, Strivers, Seekers, Aspirers, and Deprived. The Globals are the super-rich elite; the Strivers and Seekers constitute the middle class; and the Deprived are the destitute  outside the pale of consumption.

The most interesting class are the Aspirers: these are not quite destitute or middle-class, but are upwardly mobile and aspire to enter the middle class. Today, only 5% of Indian households are in the middle class, 41% are Aspirers, and 54% are Deprived. In 2025, the study expects the middle class to have swelled to 41% of households, the Aspirers to remain steady at 36%, while the Deprived drop to 22% of households. What is happening is a massive shift of households from Aspirers to middle class and from Deprived to Aspirers. The people of Dharavi are among today's Aspirers and tomorrow's middle class.

Aspirers cannot afford new cell phones, or televisions, or washing machines. But there is huge demand for used cell phones, televisions, and consumer durables of all kinds. In India today, the market for used consumer durables is extremely inefficient, and relies primarily on word-of-mouth. A free flow of information about demand and supply can make the market efficient, and also help millions of people take their first steps to becoming consumers.

Given the almost universal penetration of cell phones among Aspirers in India, the natural solution would seem to be a solution that uses mobile phones to help people buy and sell used goods. Kashyap has started a company named Chaupaati Bazaar (named after a famous beachside bazaar in Mumbai) to do just this. The problem is challenging: create a used goods market, make it work entirely through SMS and voice (no web interface), make it work for a semi-literate user base speaking many languages, and figure out the business model. Not a challenge for the faint-hearted, but something that could really make a difference if it can be made to work. I'm proud to join Chaupaati's Board of Directors as its lead investor.

Dr. C.K. Prahalad is famous for coining the phrase "fortune at the bottom of the pyramid." The bottom of the pyramid consists of the poorest section of the world's population, who are not viewed as a viable market by most consumer products companies. There are 4 billion people at the bottom of the pyramid, out a world population of 6 billion. This is an opportunity to use technology to eliminate friction at the bottom of the pyramid, enabling at least some of those people to climb the rung to the middle class.

Using Twitter to Share Factoids

I started using Twitter a couple of weeks ago. Many people use Twitter to post status updates, but here's how I've decided to use it: I'll post factoids about data I find interesting: either through personal observation, or because I read or heard it somewhere. For example, I spent the day today at the Digital Hollywood conference in LA, where I got an opportunity to post (from my cell phone) factoids as I heard them from various speakers and panelists. I was also on a panel called "Advertising NEXT" at Digital Hollywood today, on which more in a separate post.

My Twitter posts appear on the right hand column of the blog. You can also see them (and, if you like, subscribe to them either via RSS or your mobile) via this link. And let me know what you think.