The genius behind Google’s immense prosperity is AdSense and AdWords — Google’s brilliant program to match advertising with consumers via the textual content on web pages and search results. Not only has Google developed very sophisticated algorithms for ranking web pages, they have also developed very sophisticated algorithms for matching ads to users.

The Googlers aren’t the only ones doing this. All the major search contenders (Yahoo, et al) are selling similar services.

What we are seeing is only the first steps of what might be called computational advertising. The aim is to use computational power to match the expanding universe of ads and advertisers with the expanding universe of consumers with the right ad at the right time in the right place and the right frequency and the right way for them to respond. There are an infinite number of solutions — the optimal arrangement for one person may be ads  — and so the black art of computing a deal with be a big deal.

Yahoo has an entire initiative focused on computational advertising, which they define as “a new scientific sub-discipline, at the intersection of information retrieval, machine learning, optimization, and microeconomics.” Recently Andrei Broder at Yahoo! Research gave a talk on Computational Advertising. His abstract reads:

The central challenge of computational advertising is to find the “best match” between a given user in a given context and a suitable advertisement. The context could be a user entering a query in a search engine (“sponsored search”) , a user reading a web page (“content match” and “display ads”), a user watching a movie on a portable device, and so on. The information about the user can vary from scarily detailed to practically nil. The number of potential advertisements might be in the billions. Thus, depending on the definition of “best match” this challenge leads to a variety of massive optimization and search problems, with complicated constraints.

Based on the abstract Geeking with Greg says:

From the way Andrei is framing the problem — matching advertisements not only to content, but also to what we know about each user — Andrei clearly is talking about personalized advertising.

Personalized advertising is a tremendous computational challenge. Traditional contextual advertising matches ads to static content. We only have to do the match infrequently, then we can show a selection of the ads that we think will work well for a given piece of content to everyone who views that content.

With personalized advertising, we match ads to content and each user’s interests, and then show different ads for each user. Like with all personalization, caching no longer works. Each user sees a different page. With personalized advertising, targeting ads now means we have to find matches in real-time for each page view and each user.

Greg later heard the talk, and reports that he was disappointed by its lack of depth and details on how you actually optimize the matching of ads and content. This is an indication of the difficulty of the challenge, but also hints at the power it might unleash if done well.

For example, on one slide, Andrei criticized Google AdSense for showing ads for Libby shoes on an article about Dick Cheney and Scooter Libby, saying that the match is spurious. But, Andrei did not say what would be a better ad to show for that news article. In response to my question later, Andrei did say that perhaps no ad is appropriate in that case, but he did not expand on this to talk about how to detect, in general, when it might be undesirable to show ads because of lack of value and commercial intent. When I did a follow-up question after the talk, he expanded briefly into ideas around personalized advertising — showing ads that might interest this user based on this person’s history rather than ads targeting the current content — and an advertising engine that explores and attempts to learn what ads might be effective, but not in any depth.