Author: Daniel Tunkelang

Last summer, my colleague Vladimir Zelevinsky worked with two interns, Robin Stewart (MIT) and Greg Scott (Tufts), on a novel approach to information exploration. They call it “idea navigation”: the basic idea is to extract subject-verb-object triples from unstructured text, group them into hierarchies, and then expose them in a faceted search and browsing interface. I like to think of it as an exploratory search take on question answering.

We found out later that Powerset developed similar functionality that they called “Powermouse” in their private beta and now call “Factz”. While the idea navigation prototype is on a smaller scale (about 100k news articles from October 2000), it does some cool things that I haven’t seen on Powerset, like leveraging verb hypernyms from WordNet.

Click on the frame below to see the presentation they delivered at CHI ’08.

Idea Navigation: Structured Browsing for Unstructured Text

The other day, in between braving the Hulk and Spiderman rides at Endeca Discover ’08, I was chatting with Peter Morville about one of my favorite pet peeves in faceted search implementations: the confounding of clarification and refinement. To my delight, he posted about it at findability.org today.

What is the difference? I think it’s easiest to understand by thinking of a free-text search query as causing you to be dropped at some arbitrary point on a map. Our planet is sparsely populated, as pictured below, so most of the area of the map is off-road. Hence, if you’re dropped somewhere at random, you’re really in the middle of nowhere. Before you start trying to find nearby towns and attractions, your first task is to find a road.

How does this metaphor relate to clarification vs. refinement? Clarification is the process of finding the road, while refinement leverages the network of relationships in your content (i.e., the network of roads connecting towns and cities) to enable navigation and exploration.

“Did you mean…” is the prototypical example of clarification, while faceted navigation is the prototypical example of refinement. But it is important not to confuse the concrete user interfaces with their intentions. The key point, on which I’m glad to see Peter agrees, is that clarification, when needed, is a prerequisite for refinement, since it gets the user and the system on the same page. Refinement then allows the user to fully exploit the relationships in the data.

Last night, I had the privilege of speaking to fellow CMU School of Computer Science alumni at Fidelity’s Center for Advanced Technology in Boston. Dean Randy Bryant, Associate Director of Corporate Relations Dan Jenkins, and Director of Alumni Relations Tina Carr, organized the event, and they encouraged me to pick a provocative subject.

Thus encouraged, I decided to ask the question: Is Search Broken?

Slides are here as a PowerPoint show for anyone interested, or use the embedded SlideShare show below.

http://static.slideshare.net/swf/ssplayer2.swf?doc=is-search-broken-1212417896205639-9

| View | Upload your own

I just received an announcement from the SIG-IRList about the flickling challenge, a “game” designed around known-item image retrieval from Flickr. The user is given an image (not annotated) and the goal is to find the image again from Flickr using the system.

I’m not sure how well it will catch on with casual gamers–but that is hardly its primary motivation. Rather, the challenge was designed to help provide a foundation for evaluating interactive information retrieval–in a cross-language setting, no less. Details available at the iCLEF 2008 site or in this paper.

I’m thrilled to see efforts like these emerging to evaluate interactive retrieval–indeed, this feels like a solitaire version of Phetch.

A couple of weeks ago, my colleague Luis Von Ahn at CMU launched Games With a Purpose,

Here is a brief explanation from the site:

When you play a game at Gwap, you aren’t just having fun. You’re helping the world become a better place. By playing our games, you’re training computers to solve problems for humans all over the world.

Von Ahn has made a career (and earned a MacArthur Fellowship) from his work on such games, most notably the ESP Game and reCAPTCHA. His games emphasize tagging tasks that are difficult for machines but easy for human beings, such as labeling images with high-level descriptors.

I’ve been interested in Von Ahn’s work for several years, and most particularly in a game called Phetch, a game which never quite made it out of beta but strikes me as one of the most ambitious examples of “human computation”. Here is a description from the Phetch site:

Quick! Find an image of Michael Jackson wearing a sailor hat.
Phetch is like a treasure hunt — you must find or help find an image from the Web.

One of the players is the Describer and the others are Seekers. Only the Describer can see the hidden image, and has to help the Seekers find it by giving them descriptions.

If the image is found, the Describer wins 200 points. The first to find it wins 100 points and becomes the new Describer.

A few important details that this description leaves out:

• The Seeker (but not the Describer) has access to search engine that has indexed the images based on results from the ESP Game.
• A Seeker loses points (I can’t recall how many) for wrong guesses.
• The game has a time limit (hence the “Quick!”).

Now, let’s unpack the game description and analyze it in terms of the Human-Computer Information Retrieval (HCIR) paradigm. First, let us simplify the game, so that there is only one Seeker. In that case, we have a cooperative information retrieval game, where the Describer is trying to describe a target document (specifically, an image) as informatively as possible, while the Seeker is trying to execute clever algorithms in his or her wetware to retrieve it. If we think in terms of a traditional information retrieval setup, that makes the Describer the user and the Seeker the information retrieval system. Sort of.

A full analysis of this game is beyond the scope of a single blog post, but let’s look at the game from the Seeker’s perspective, holding our assumption that there is only one Seeker, and adding the additional assumption that the Describer’s input is static and supplied before the Seeker starts trying to find the image.

Assuming these simplifications, here is how a Seeker plays Phetch:

• Read the description provided by the Describer and uses it to compose a search.
• Scan the results sequentially, interrupting either to make a guess or to reformulate the search.

The key observation is that Phetch is about interactive information retrieval. A good Seeker recognizes when it is better to try reformulating the search than to keep scanning.

Returning to our theme of evaluation, we can envision modifying Phetch to create a system for evaluating interactive information retrieval. In fact, I persuaded my colleague Shiry Ginosar, who worked with Von Ahn on Phetch and is now a software engineer at Endeca, to elaborate such an approach at HCIR ’07. There are a lot of details to work out, but I find this vision very compelling and perhaps a route to addressing Nick Belkin’s grand challenge.