Microsoft and Yahoo, kissing behemoths

It looks like we have a Microsoft-Yahoo deal. If you smack two amorous giants together enough times, I guess you are going to get a love child.

I doubt Google has much to fear from the laggard that likely will result. Just as two wrongs don't make a right, combining two struggling organizations is unlikely to fix dysfunction.

I hope I am wrong. If the deal provides focus rather than distractions, if it allows both organizations to rapidly iterate on, develop, and deploy products people actually want, it has some chance of succeeding.

But, as separate groups, both organizations barely can control the internal squabbling of hordes of product managers, "none f-ing getting anything done", as Carol Bartz colorfully put it. Combined, someone will have to keep these beasts from pulling on and tripping over each other while they desperately pursue the leader of the pack.

Update: Excellent commentary on the deal by Danny Sullivan, Jason Calacanis, and Saul Hansell.

Facebook versus Google?

Greg Sterling has some good thoughts on why Facebook and Google are not in competition:

Currently the use cases for Facebook and for search are quite different.

Facebook is entertaining, Facebook is fun, Facebook kills time, Facebook enables me to keep in touch with people. But Facebook, generally speaking, is not "useful" in the sense that Google is.

For its part, Google delivers information efficiently but is generally not "entertaining" or "fun."

It's very likely that the two sites will simply co-exist fulfilling different types of needs and interests ... Neither can be expected to fundamentally undermine the core business of the other.

But what are Facebook and Google's core businesses?

It is true that the uses of Facebook and Google differ. People mostly seem to go to Facebook because they find it entertaining. People mostly go to Google because it is useful.

But, the core business of both, where they get their revenue, is from advertising. And, while Google's search advertising does quite well, they have struggled much more in non-search advertising. And non-search advertising is the problem Facebok needs to solve.

Toward the end of the Fred Vogelstein's Wired article (which Greg Sterling references), Fred pinpoints the critical area of conflict:

Facebook [is] confronted with a difficult challenge: turning [their] massive user base into a sustainable business.

[Google] inked a disastrous $900 million partnership with MySpace in 2006, a failure that taught them how hard it is to make money from social networking. And privately, [Googlers] don't think Facebook's staff has the brainpower to succeed where they have failed.

"If [Facebook] found a way to monetize all of a sudden, sure, that would be a problem," says one highly placed Google executive. "But they're not going to."

Google's thin client distraction

Recently, Chris O'Brien at the San Jose Mercury News wrote:

It's getting harder every day to articulate what Google is. Is it a Web company? A software company? Something else entirely?

It's not just that it's hard to see how [Google's operating systems] fit into Google's stated mission. It's also that it's hard to explain to someone exactly what they are, or why they might, or might not, want to use them. Or to communicate why they are different from or better than any other things out there.

These new products have the whiff of engineers building things for other engineers, rather than you and me.

Even worse, these new products have the whiff of executives being unable to let go of their past battles.

For decades, Google CEO Eric Schmidt led Sun and Novell in mostly failed attempts to build thin client computers. At Google, Eric appears to be doing it again.

But Google is not a computer company. It is an advertising company. Google makes its money from advertising.

It is not as if there isn't enough to do in advertising. Despite Google's success in making search advertising more useful and helpful, most other advertising remains awful.

Fixing advertising not only would be lucrative, but also it directly fits into Google's mission to "organize the world's information and make it universally accessible and useful." At their best, ads provide useful information about interesting products and services. Right now, most contextual and display advertisements are more annoying than useful. It doesn't have to be that way.

If Google could be the solution to annoying advertising, it could reap all the rewards. Instead, Google is being led off by its generals to fight the last war.

Time effects in recommendations

The best paper award at the recent KDD 2009 conference went to Yehuda Koren's "Collaborative Filtering with Temporal Dynamics" (PDF).

The paper is a great read, not only because Yehuda is part of the team currently winning the Netflix Prize, but also because it has some surprising conclusions about how to deal with changing preferences and interests over time.

In particular, it is common in recommender systems to favor recent activity, such as more recent ratings by a user, either by only using the last N data points or by weighting more recent data more heavily. But Yehuda found that ineffective on the Netflix data:

The consistent finding was that prediction quality improves as we moderate ... time decay, reaching [the] best quality when there is no delay at all. This is despite the fact that users do change their taste and rating scale over the years.

Underweighting past action loses too much signal along with the lost noise, which is detrimental given the scarcity of data per user .... We require an accurate modeling of each point in the past, which will allow us to distinguish between persistent signal that should be captured and noise that should be isolated .... for understanding the customer ... [and] modeling other customers.

As in some of Yehuda's past work, he combines two models, one a latent factor model, the other an item-item approach. The models yielded "the best results published so far" on the Netflix data set by allowing them to represent temporal effects such as finding stronger relationships between items related in a short timeframe, handling that people tend to give higher ratings to older movies (if they bother to rate them at all), allowing for people to shift to giving higher or lower ratings on average over time, and capturing that people tend to use the same rating for multiple items rated in a short timeframe.

The paper is full of other cute tidbits too, like that they tried to detect day of the week effects -- do people rate lower on Mondays? -- but could not. They also discovered an unusual jump in the average rating in the data in 2004, which they hypothesize was due to features launched on the Netflix.com site that started showing people more movies they liked. Definitely worth a read.

Ad fatigue and relevance

At the recent Ad Auctions Workshop, I had a paper (PDF) and talk (PDF) that argued for discounting relevant advertisements more than we currently do.

To briefly summarize, if seeing bad ads causes people to look at ads less in the future (aka ad fatigue), then we should change our pricing in advertising auctions to promote relevant, useful ads. Likewise, we should charge bad ads more to compensate for the damage they cause.

The paper is not trying to be definitive. The paper only shows that ad fatigue could matter, not that it does actually matter. More work needs to be done to measure how much ad fatigue actually exists.

But, I hope this paper might motivate others to look more at ad fatigue, think more about long-term revenue instead of short-term revenue, and consider how it might be beneficial in the long-term to lower our pricing on relevant and useful advertisements.

The paper was done with Chris Meek from Microsoft Research and Max Chickering at Microsoft. It reports on a side project I did a year ago while at Microsoft Live Labs.

New Google study on speed in search results

Googler Jake Brutlag recently published a short study, "Speed Matters for Google Web Search" (PDF), which looked at how important it is to deliver and render search result pages quickly.

Specifically, Jake added very small delays (100-400ms) to the time to serve and render Google search results. He observed that even these tiny delays, which are low enough to be difficult for users to perceive, resulted in measurable drops in searches per user (declines of -0.2% to -0.6%).

Please see also my Nov 2006 post, "Marissa Mayer at Web 2.0", which summarizes a claim by Googler Marissa Mayer that Google saw a 20% drop in revenue from an accidentally introduced 500ms delay.

Update: To add to the Marissa Mayer report above, Drupal's Dries Buytaert summarized the results of a few A/B tests at Amazon, Google, and Yahoo on the impact of speed on user satisfaction. As Dries says, "Long story short: even the smallest delay kills user satisfaction."

Update: In the comments, people are asking why the effect in this study oddly appears to be an order of magnitude lower than the effects seen in previous tests. Good question there.

Update: By the way, this study is part of a broader suite of tools and tutorials Google has gathered as part of an effort to "make the web faster".

The $1M Netflix Prize has been won

An ensemble of methods from four teams has passed the criteria to win the Netflix Prize.

Other teams have 30 days to beat it, but, no matter what happens, the $1M prize will be claimed in the next month.

Congratulations to the winning team and all the competitors. It was a goal that some thought impossible without additional data, but remarkable persistence has proven the impossible possible.

Please see also my earlier post, "On the front lines of the Netflix Prize", which summarizes an article that describes some of the algorithms that brought the winning team to where it is now.

Update: In an extremely close finish, a different team, The Ensemble, took the prize. Remarkable not only to see another team qualify for the grand prize, but then to see BellKor beaten with only four minutes left in the contest.

Congratulations to all, especially those who shared knowledge and joined together to help the winning teams. The winners discovered a solution to a problem that many thought might never be solved.

Update: It appears it is still unclear who ultimately will be declared the winner of the $1M prize.

Update Good article on the current state of the contest in the New York Times.

Update: Adding to this, there is a colorful story about the nailbiting finish in a blog post from the Pragmatic Theory team (part of the "BellKor's Pragmatic Chaos" submission).

Update: Three months later, Netflix awards the prize to BellKor and starts a second contest.

Is mobile search going to be different?

In an amusingly titled WWW 2009 paper, "Computers and iPhones and Mobile Phones, oh my!" (PDF), a quartet of Googlers offer some thoughts on where mobile search may be going.

In particular, based on log analysis of iPhone searches, they claim search on mobile devices is not likely to differ from normal web search once people upgrade to the latest phones. They go on to predict that an important future feature for mobile search will be providing history and personalization synchronized across all of a person's computers and mobile devices.

Some excerpts:

We have consistently found that search patterns on an iPhone closely mimic search patterns on computers, but that mobile search behavior [on older phones] is distinctly different.

We hypothesize that this is due to the easier text entry and more advanced browser capabilities on an iPhone than on mobile phones. Thus we predict that as mobile devices become more advanced, users will treat mobile search as an extension of computer-based search, rather than approaching mobile search as a tool for a distinct subset of information needs.

For [newer] high end phones, we suggest search be a highly integrated experience with computer-based search interfaces .... in terms of personalization and available feature set .... For example, content that was searched for on a computer should be easily accessible through mobile search (through bookmarks, search summaries), and vice versa.

This similarity in queries [also] indicates that we can use the vast wealth of knowledge amassed about conventional computer based search patterns, and apply it to the emerging high-end phone search market, to quickly gain improvements in search quality and user experience.

Optimizing broad match in web advertising

A paper out of Microsoft Research, "A Data Structure for Sponsored Search" (PDF), has a couple simple but effective optimizations in it that are fun and worth thinking about.

First, a bit of explanation. When trying to match advertisers to search queries, search engines often (90%+ of the time) use broad match, which only requires a subset of the query terms to match. For example, if an advertiser bids for their ads to show on searches for "used books", the ad might also show on searches for [cheap used books], [gently used books], and [used and slightly traumatized books].

You can do this match using a normal inverted index, but it is expensive. For example, on the search for [cheap used books], you need to find all ads that want any of the terms (cheap OR used OR books), then filter out ads that wanted other terms (e.g. an ad that bid on "new books" need to be filtered out at this step). For very popular keywords such as "cheap", many ads can end up being retrieved in the first step only to be filtered in the second.

The clever and nicely simple idea in this paper is to use past data on the frequency of keywords to drop popular terms from the index whenever we possibly can. For example, let's say an advertiser bids for "the great wall of china", we can index the ad only under the lowest frequency word (e.g. "china") and not index under any of the other words. Then, on a search for [the awesomeness], we no longer have to retrieve then filter that ad.

The authors then extend this to deal with bids where all the keywords are popular (e.g. "the thing"). In the paper, they discuss a model that attempts to estimate the cost of throwing multiple words into the index (e.g. indexing "the thing") versus doing the query for each word separately.

The end result is an order of magnitude improvement in performance. All the irrelevant data you get from indexing everything wastefully pulls in many ad candidates that need to be filtered. In this case as well as others, it very much pays off to be careful about what you index.

Please see also my earlier post, "Caching, index pruning, and the query stream", that discusses a SIGIR 2008 paper out of Yahoo Research that explores some vaguely related ideas on index pruning for core search.

How much can you do with one server?

At a time when many of us are working with thousands of machines, Paul Tyma provides a remarkable example of how much you can do with just one.

Paul runs the clever Mailinator and Talkinator services. Mailinator lets people receive e-mail to arbitrary addresses under mailinator.com, mostly for disposable e-mail for avoiding spammers or annoying registration requirements. Talkinator is an instant messaging system for easily setting up and joining chat rooms.

Both are examples of removing the login friction normally associated with an application (in this case, mail and instant messaging) to discover a new application with different properties and uses.

In an older post, "The Architecture of Mailinator", Paul describes how he optimized the single server running the service to handle 6M e-mails/day. To summarize, the system is custom-built to the task, all unnecessary goo removed, and focuses on robustness while accepting a very small probability of message loss.

Recently, Paul updated that older post. Now they are processing 2M e-mails/hour on a single machine, 3.1T of data per month, and might have to expand to a second machine, not because the one machine cannot handle the load, but because two machines is the cheapest way of getting the extra bandwidth they need.

Paul also posted details on the architecture of Talkinator, which also is highly optimized to run well on a single server. If you take a peek at that, don't miss his amusing second post where he tested running on a 5W tiny plug-in server.

I am not advocating spending as much effort as Paul does on minimizing server costs. But, his work an inspirational counter-example to the common tendency to throw hardware at the problem. It is an enjoyable tale of building much by staying simple, both in the application features and the underlying architecture.

Approaching the limit on recommender systems?

An article at the upcoming UMAP 2009 conference, "I like it... I like it not: Evaluating User Ratings Noise in Recommender Systems" (PDF), looks at inconsistencies when people rates movies.

What is particularly interesting about the article is that the authors argue that "state-of-the-art recommendation algorithms" are nearing the lower bound on accuracy imposed by inconsistencies in ratings, which they and previous work refer to as the "magic barrier".

Natural variability in people's opinions limits how accurate recommender systems can be. According to this paper, we may be almost at that limit already.

Update: For more on this topic, it turns out one of the authors of the paper, Xavier Amatriain, has a blog post, "Netflix Prize: What if there is no Million $ ?", with a good comment thread.

On the front lines of the Netflix Prize

Robert Bell, Jim Bennett, Yehuda Koren, and Chris Volinsky have an article in the May 2008 IEEE Spectrum, "The Million Dollar Programming Prize", with fun tales of their work in the Netflix Prize along with a summary of the techniques that are performing best.

Some excerpts:

The nearest neighbor method works on the principle that a person tends to give similar ratings to similar movies. [For example, if] Joe likes three movies ... to make a prediction for him, [we] find users who also liked those movies and see what other movies they liked.

A second, complementary method scores both a given movie and viewer according to latent factors, themselves inferred from the ratings given to all the movies by all the viewers .... Factors for movies may measure comedy versus drama, action versus romance, and orientation to children versus orientation toward adults. Because the factors are determined automatically by algorithms, they may correspond to hard-to-describe concepts such as quirkiness, or they may not be interpretable by humans at all .... The model may use 20 to 40 such factors to locate each movie and viewer in a multidimensional space ... then [we predict] a viewer's rating of a movie according to that movie's score on the dimensions that person cares about most.

Neither approach is a panacea. We found that most nearest-neighbor techniques work best on 50 or fewer neighbors, which means these methods can't exploit all the information a viewer's ratings may contain. Latent-factor models have the opposite weakness: They are bad at detecting strong associations among a few closely related films, such as The Lord of the Rings trilogy.

Because these two methods are complementary, we combined them, using many versions of each in what machine-learning experts call an ensemble approach. This allowed us to build systems that were simple ... easy to code and fast to run.

Another critical innovation involved focusing on which movies a viewer rated, regardless of the scores. The idea is that someone who has rated a lot of fantasy movies will probably like the Lord of the Rings, even if that person has rated the other movies in the category somewhat low ... This approach nicely complemented our other methods.

Please see also my earlier post, "Netflix Prize at KDD 2008", which points at papers with more details than the IEEE article, including another recent paper by Yehuda Koren.

The siren song of startups

Over at the blog of the Communications of the ACM, I have a new post on "The Siren Song of Startups".

The article tries to get readers thinking more carefully about why they might and might not want to join a startup.

If you like the post, you might enjoy my other posts over at blog@CACM: "Enjoying Reading Research", "What To Do With Those Idle Cores?", and "What is a Good Recommendation Algorithm?"

Yahoo CEO Carol Bartz on personalization

Interesting tidbit on personalization in a Q&A with Yahoo CEO Carol Bartz:

Yahoo! is the place where millions of people come every day to see what is happening with the people and the things that matter most to them.

That could mean what's happening in the world -- like breaking news, sports scores, stock quotes, last night's TV highlights -- and your world -- like your email, photos, groups, fantasy leagues.

Based on what we know about you ... we can bring you both those worlds. So I think our clear strength is "relevance" -- whether that means knowing what weather to give you or serving up headlines you'll be interested in. It's all about really getting you.

So Yahoo wants to filter and recommend relevant content based on what it knows about you. Is this a new goal for Yahoo?

Two years ago, Yahoo co-founder Jerry Yang spoke about "better tailoring Yahoo's iconic Web portal to individual users, with the help of technology that predicts what they want."

Four years ago, Yahoo CEO Terry Semel said that one of the "four pillars" of Yahoo was "personalization technology to help users sort through vast choices to find what interests them" and Yahoo executive Lloyd Braun called it one of Yahoo's "secret weapons".

Five years ago, Yahoo CEO Terry Semel said, "Personalization will also play more of a role on the Yahoo home page in the coming months" and "painted a picture in which users could tailor the Yahoo home page to suit their particular interests," adding, "We want the home page to be totally personalized."

Making Yahoo content more relevant and useful to people would be fantastic. Personalization is a way to make the site more relevant and useful. But this idea clearly has been around the halls of Yahoo for some time. The key is going to be executing on it quickly.

Please see also my May 2006 post, "Yahoo home page cries out for personalization".

Update: Three weeks later, Forbes Magazine quotes Carol Bartz as admitting that Yahoo's troubles have been "an execution problem ... we are really working on (moving) from 'we can do this, we can do this' to 'we did do this.'"

She also has several other quotes in that same article that seem quite promising for the future of Yahoo, including that "none of us hate ads ... we just hate crappy ads" and that we should see Yahoo doing personalization and recommendations of news and other home page content soon. Great to hear it.

Update: Seven months later, Carol Bartz pumps personalization but admits that "we have been letting great data ... fall to the floor."

Update: One year later, Carol Bartz says, "Tomorrow's Yahoo is going to be really tailored" and "I want it to learn about me ... and cull through the massive amount of information that's out there to find exactly what I want." But, as ex-Yahoo Jeremy Zawodny comments, "The problem is that Yahoo execs have been saying this for literally years now. When will it come true?"

Danny Sullivan on Microsoft search

Danny Sullivan has a couple great posts ([1] [2]) on Microsoft renaming its search engine to Bing, the new features and improvements in relevance coming along with the launch, and what it might mean for Google and Yahoo.

Danny is wise in the ways of search. His words are well worth reading.

Update: To be clear, just because I think Danny's posts are well worth reading doesn't mean I agree with him on everything. In fact, quite the opposite, I usually find the most interesting articles to be the ones that make a convincing argument on something with which I disagree.

One particular point of disagreement I have with Danny is on whether Microsoft's Bing needs to be different or better than Google to succeed. Many, including Danny, have said that being good enough isn't enough because of the power of Google's brand. I'm not sure that's true.

Until now, we haven't been able to tell who is right since Microsoft's search has been noticeably weaker than Google's. But, as Rafe Needleman noted, as did Danny, the name change to Bing comes with substantial improvements to relevance.

So, I think we're about to get the first real test of whether being about as good as Google is enough to see people using Microsoft's search engine.

Update: A week later, Danny Sullivan has a Q&A with Nick Eaton. Interesting how low Danny sets the bar for success for Microsoft's Bing, saying, "They're roughly at 10 percent [market share], I think that they could count themselves really successful if they got themselves to 15 or 20."

Update: Three weeks later, an article in the NY Post claims, "Co-founder Sergey Brin is so rattled by the launch of Microsoft's rival search engine that he has assembled a team of top engineers to work on urgent upgrades to his Web service." Frankly, I find that a little hard to believe, at least as phrased. Seeing as Microsoft is getting closer, I would expect Googlers are redoubling their efforts to stay ahead in core search, but I doubt that Sergey, Larry, or Eric are deeply rattled by some new competition.

Google Suggest and the right ad

In "Google Kills a Sacred Cow", Anders Bylund at the Motley Fool has an interesting take on Google's decision to show advertising in their search suggestion feature.

An excerpt:

You know how you get suggestions on ... the query you're typing into a Googlish search box? That suggestion list just became context-sensitive, more personalized, and more likely to send you to your destination without ever seeing a page of search results.

Oh, and you'll see advertising in that box, too. If you never see a results page, you might still send revenue Big G's way.

Yahoo recently promised to kill the typical "10 blue links" results in favor of more dynamic presentations. Google immediately took that idea one step further and did away with results altogether for many searches.

While Yahoo, Microsoft's MSN/Live/Kumo/whatever, Time Warner's AOL, and IAC/InterActiveCorp's Ask.com depend on exposing users to as many ads as possible by keeping them on their sites, Google is going the other way. All it takes is one ad -- the right ad in the right place -- and Google's cash flow is secure.

All it takes is one ad, the right ad in the right place.

Long ago, when I was at Amazon working on personalization, we used to joke that the ideal Amazon site would not show a search box, navigation links, or lists of things you could buy. Instead, it would just display a giant picture of one book, the next book you want to buy.

When you overwhelm people with choices, the important becomes lost in the mediocrity. Showing as many ads as possible just encourages ad fatigue. The focus of web advertising should be on getting the right ad in the right place. The focus should be on relevance.

The datacenter is the new mainframe

For a while, I have been planning on writing a post comparing large scale clusters with the mainframes of yore, a piece that would be full of colorful references to timesharing, scheduling and renting compute resources, and other tales that would date me as the fossil that I am.

Fortunately, Googlers Luiz Andre Barroso and Urs Holzle recently wrote a fantastic long paper, "The Datacenter as a Computer" (PDF), that not only spares me from this task, but covers it with much more data and insight than I ever could.

Some excerpts:

New large datacenters ... cannot be viewed simply as a collection of co-located servers. Large portions of the hardware and software resources in [our] facilities must work in concert to efficiently deliver good levels of Internet service performance, something that can only be achieved by a holistic approach to their design and deployment.

In other words, we must treat the datacenter itself as one massive warehouse-scale computer (WSC).

Much like an operating system layer is needed to manage resources and provide basic services in a single computer, a system composed of thousands of computers, networking, and storage also requires a layer of software that provides an analogous functionality at this larger scale.

[For example] resource management ... controls the mapping of user tasks to hardware resources, enforces priorities and quotas, and provides basic task management services. Nearly every large-scale distributed application needs ... reliable distributed storage, message passing, and cluster-level synchronization.

The paper goes on to describe the challenges of making an entire datacenter behave like it is one large compute resource to applications and programmers, including discussing the existing application frameworks and need for further tools.

Do not miss Figure 1.3 that shows latency, bandwidth, and capacity to resources in the data center. It includes an insightful look at latency to local and remote memory and the equivalent latencies but drastically different capacities of local and remote disk for programs running in the cluster. As the authors say, a key challenge is to expose these differences when they matter and hide them when they don't.

There are also thought-provoking tidbits on minimizing interference between jobs on the cluster and maximizing utilization, two goals that often are at odds with each other.

Much of the rest of the paper covers the cost and efficiency issues of data centers more generally, nicely and concisely summarizing much of the recent publicly known work on power, cooling, and infrastructure.

One small thing it does not mention is the ability to rent resources (e.g. EC2) on a WSC, much like buying time on the old mainframes, and the impact that could have on utilization, especially once we allow variable pricing and priorities.

[Google paper found via James Hamilton]

Update: A couple weeks later, security guru Bruce Schneier writes, "Cloud computing is nothing new. It's the modern version of the timesharing model from the 1960s."

Update: Seven months later, Amazon launches variable pricing for low priority jobs on EC2.

The potential of behavioral targeted advertising

An important WWW 2009 paper out of MSR Asia, "How much can Behavioral Targeting Help Online Advertising?" (PDF), looks at how much value we can get from targeting ads to past behavior. It is a must read for anyone interested in personalized advertising.

Some excerpts:

To our best knowledge, this work is the first systematic study for [behavioral targeting] (BT) on real world ad click-through [logs].

[We] empirically answer ... whether BT truly as the ability to help online advertising ... how much BT can help ... [and] which BT strategy can work better than others.

We observe that the users who clicked the same ad can be over 90 times more similar than the users who clicked different ads .... [which verifies] the basic assumption of BT.

We observe that .... the ads CTR can be improved as high as 670% by the simple user segmentation strategies used for behavioral targeted advertising .... [More] advanced user representation and user segmentation algorithms [yielded improvements of] more than 1,000%.

Through comparing different user representation strategies for BT, we draw the conclusion that user search behavior, i.e. user search queries, can perform several times better than user browsing behavior, i.e. user clicked pages. Moreover, only tracking the short term user behaviors are more effective than tracking the long term user behaviors.

One issue with the study is that it looks only at coarse-grained user segments, at most 160 segments, not fine-grained, one-to-one, personalized advertising. I would suspect there would be added benefit from fine-grained, personalized targeting to past behavior rather than clustering users into large groups. In fact, as Figure 5 in the paper shows, they do not appear to have hit the point of diminishing returns even on splitting into more segments.

Another issue is that they explicitly did not look at using demographic data or locality. It is possible that many of the BT user segments might be grouped roughly by locality, having derived it from search or browsing behavior. If that is true, then much of the gains they saw from BT could be reaped much more easily by targeting the ads to implicit local information. And, if we target to locality, then the additional gains we could expect from behavior targeting then might be much smaller.

But, limitations aside, it is a great paper. The authors clearly and cleanly state their key question -- what is the value of behavioral targeting for advertising? -- and then analyzes a massive historical log to convincingly derive the likely value. It also provides much guidance for those who might seek to build these or similar systems.

The paper has an interesting conclusion that recent search queries are the most useful indicators of people's interests when targeting ads. Yahoo's Andrei Broder said something similar recently when thinking about targeting advertising. It is also worth noting that others who were looking at the value of personalized search came to similar conclusions ([1] [2]).

For more on fine-grained personalized advertising, please see my earlier posts, "What to advertise when there is no commercial intent?" and "A brief history of Findory".

Exploiting spammers to make computers smarter

Googlers Rich Gossweiler, Maryam Kamvar, and Shumeet Baluja had a fun paper at WWW 2009, "What's Up CAPTCHA? A CAPTCHA Based On Image Orientation" (PDF), that asks people to rotate images correctly to prove they are human rather than the norm of deciphering distorted text.

Some brief excerpts from their paper:

We present a novel CAPTCHA which requires users to adjust randomly rotated images to their upright orientation ... Rotating images to their upright orientation is a difficult task for computers .... [Our] system ... results in a 84% human success rate and .009% bot success rate.

The main advantages of our CAPTCHA technique over traditional text recognition techniques are that it is language-independent, does not require text-entry (e.g. for mobile devices), and employs another domain for CAPTCHA generation beyond character obfuscation.

The paper goes on to say that "no algorithm has yet been developed to successfully rotate the set of images used in our CAPTCHA system." The key word there is "yet." As soon as there is a strong incentive for people to develop better algorithms for this problem, better algorithms will be developed.

But, as Luis von Ahn insightfully pointed out in a recent interview in New Scientist, it is a perfectly fine outcome if spammers find a way to break this new image-based CAPTCHA technique. By doing so, they are helping us make computers smarter.

From the New Scientist article:

"If [the spammers] are really able to write a programme to read distorted text, great – they have solved an AI problem," says von Ahn. The criminal underworld has created a kind of X prize for OCR.

Security groups ... [then] can ... switch for an alternative CAPTCHA system -- based on images, for example -- presenting the eager spamming community with a new AI problem to crack ... Image orientation is difficult for computers. But if [image-based] CAPTCHA becomes common, it won't be long before spammers turn their attention to cracking the problem, with potential fringe benefits to cameras and image editing software.

Speech recognition CAPTCHAs are already being used, and image labelling ones could follow, says von Ahn. AI researchers are already working in both these areas, but they could soon be joined by spammers also helping advance the technology.

Perhaps it is time to start designing CAPTCHAs in a different way -- pick problems that need solving and make them into targets to be solved by resourceful criminals.

More Microsoft layoffs

It is being widely reported ([1] [2] [3] [4] [5]) that Microsoft did another large round of layoffs today.

Microsoft never has done layoffs on this scale. It is a difficult thing to do well. For more on that, please see my earlier post, "Layoffs and tech layoffs".