• People do product search with many different intentions, and there are as many non-buying intent searches as buying intent searches. Within buying intents, users can be in different position in buying process (awareness / desire / interests / purchase)
• People tend to browse more in product search environment than in typical web search. He didn’t mention specific reason, yet rich interface with many controls and visual elements, different search intent (searching for fun) were suggested.
• Search context (product category) matters a lot. Search queries take different characteristics, so are post-query behaviors. For instance people go much deeper down the ranked list when buying clothes, with many more side-by-side comparisons. Ranking, user interface, even spell corrections should be customized accordingly.
• Amazon is also a marketplace with lots of vendors, and the realtime update of all the product information including availability is critical. This also causes many complexities. For instance, how can we set the price for sorting the list of items?
• Rich structure inherent for product search is a blessing, yet should be used with care. Each field has different characteristic. For instance, how would you incorporate both title and full-text of a book for ranking? Also, structured information can be missing or incorrect in many cases, both for manual and automated generation.
• Behavioral data is useful, yet again requires caution. Product rating can suffer from individual bias and small sample size. Click count cannot be equated with signal of relevance. Can we say that multiple clicks are always better than single or no click?

It was certainly an interesting talk, with many food for thoughts. At the last part of his talk, he presented the idea of information-seeking funnel (more on his workshop paper), which drew an analogy from product shopping. (reminding me of information foraging theory ) The point here is that users should go through with different process in getting to the information desired, and the system should be able to identify and support each step appropriately.

In this framework, many modes of search behavior are combined into the goal-completion. The first challenge would be identifying user’s current stage without the interruption of flow, yet given the amount of information web search engines collect per user, this wouldn’t be an impossible goal. Another challenge would be transferring the context across different stages. For instance, how can we condition user’s search in ‘Asking’ stage on what we learned from ‘Exploring’ stage? This wouldn’t be trivial even after we know that they belong to the same information goal.

Gary’s keynote was particularly enchanting, providing a good overview on HCIR research as well as ongoing challenges. I went on looking up his HCIR overview lecture at MIT, and found it also interesting. There he describes HCIR model as follows:

Think of IR from the perspective of active human with information needs, information skills, powerful IR resources (including other humans), situated in global and connected communities — all of which evolve over time.

What an engaging description! He also outlines several challenges for HCIR research, some of which includes:

• How can we shift the focus of research from retrieval to understanding and problem solving?
• What are sensible ways to combine several different modes of evaluation? (lab + field study + simulation)
• How can we evaluate user’s whole interaction with the system, beyond query-based effectiveness measures?

In the following sessions, we saw many works with great diversity. There were many tasks — health information finding, search over e-government, known-item finding in personal collection, exploratory search in paper archives. People mostly employed user study to study various aspects of given tasks, although there were log-based studies and simulation studies as well.

These are certainly different studies from what I’ve seen in SIGIR or CIKM, where people focus on improving well-known performance metrics for some of ‘major’ search domains, such as web search, and the role of user is minimized, if any. While I certainly think that the field of IR can benefit from richer understanding and modeling of users in general, I think HCIR can also benefit from the emphasis of  traditional IR on comparative evaluation over standard tasks.

From this perspective, I found HCIR Challenge this year as an interesting effort in the right direction. We saw the demo of several systems which solved the information availability problem over Citeseer corpus. While traditional demos just showed the operation of a single system, the focus here was to evaluate a set of systems over a set of possible tasks. Another important point was that people (workshop participants) did the evaluation, instead of relying on some metric.

While going through with coast-to-coast travel to participant in one-day workshop wasn’t a choice I was sure about, it certainly provided me with new perspectives on the field. Kudos to organizers who did a great job! Hopefully we’ll see more of interesting researches which address some of the challenges above.

p.s. Rob Capra in UNC posted a SIGIR forum report, which gives a nice summary of the workshop.

Establishing one’s own style may not be an easy feat, since I can’t think of many people who I consider as a researcher with distinctive ‘style’. Yet I know of a person who has a distinctive style of research (both in terms of writing and presentation) — Leif Azzopardi. Here are his recent papers which have been quite inspirational to me:

• Accessibility in Information Retrieval
• Usage Based Effectiveness Measures
• Query Side Evaluation: An empirical study of effectiveness and effort
• Retrievability: An Evaluation Measure for Higher Order Information Access Tasks
• The Economics in Interactive Information Retrieval

Keyword Search, Associative Browsing and Faceted Navigation are three major techniques of information access. Google provide search, browsing (find-similar links) and navigation (filtering by time and types), and there exists many domain-specific collections of structured data (e.g., Amazon, IMDB and Yelp!) which supports all three methods in different forms. In this post, I’ll compare these method, and consider ways to combine these method in a single search scenario.

Comparing Three Methods

In essence, these three modes of information access can be considered as some kind filtering and ranking of given items. Search involves both filtering by query terms and ranking by textual match between items and query and possibly other criteria. Associative browsing provides ranking based on match between one item and others, and faceted navigation is filtering by a set of conditions defined in terms of metadata values.

Each of these methods have different requirement from collection perspective. Keyword search assumes that reasonable query-item similarity and overall goodness measures can be defined for the collection. Associative browsing requires item-item similarity measures. Faceted navigation requires well-defined sets of metadata which can collectively provide reasonable specificity.

From user perspective, each of them requires different kind of knowledge and effort from the user. Search assumes that users can type in keyword, yet users can’t even start otherwise. Associative browsing assumes that user can choose a relevant item among suggestions, yet users have no control over which items are suggested. Finally, faceted navigation requires users to choose a facet of interest, which is not always easy if users do not have knowledge of the domain.

Consider an example of user trying to find a trail for hiking. If she knows of a right keyword, she’ll type them in to narrow down the candidates, or she might just pick one of criteria suggested in faceted navigation interface. After she found an appropriate trail, she can browse into nearby trails by associative browsing feature.

Interface for three access methods in alltrails.com

Likewise, since each user might have different ability and preference, it will be helpful to provide all these mechanisms, and let the user to mix and match the methods as they want. An important question is: how can a system provide a reasonable combination of these methods?

Combining Three Methods

While providing three methods within a system would be a matter of implementation, an open question remains about the sensible combination of three methods within a single search session. Previous works on faceted navigation has been consistently arguing the importance of integrating faceted navigation with keyword search, where  the facet display is dynamically updated according to the set of items returned as search results. Another example found from Marti Hearst’s search UI book is updating facet filter when search term matches a specific filter.  Finally, many work on associative browsing assumes that keyword search is used as an entry point, so that users can subsequently browse into the item they desired, continuing from from search results.

That being said, FXPAL paper on exploratory search I mentioned on previous post seems to open up another set of possibilities for combining three methods based on selective application of contextual knowledge, i.e. queries and documents issued or judged so far. Assume that users are willing to make judgments on which items were relevant or non-relevant. Although their original proposal was to use these judgments for refining keyword query, yet these set of documents can possibly be used to determine metadata values or ranges that can be used for faceted navigation. This will certainly ease the difficulty in specifying appropriate values for facets.

Let’s go back to the trail-finding example. Initially it might be hard for a user to know exactly what are appropriate length and difficulty of trail for her. However, after looking at several trails she liked, she now has better idea on those facet values. Although she can browse through all the items and manually update facet values, the system can make it much easier by automatically updating facet values based on trails she preferred.

Looking Forward

The idea of combining multiple access methods is certainly appealing for users, because users can start searching regardless of what they know, improving their understanding along the way.  If the system further let them use their knowledge for refining their expression of information needs, it will be even more powerful. A sensible combination should be able to provide all the benefit of each method — specificity of keyword query, transparency of faceted navigation and little cognitive overhead of associative browsing.

Recently I got requests for codes implementing the PRM-S, and I started implementing it using the Galago search engine. Galago is a Java-based search engine & framework for IR research, developed by Trevor Strohman, and being maintained and improved by some of my fellow researchers in CIIR (especially Sam and Marc). Being intended for IR education and research, it has a flexible and extensible architecture, which allows the implementation of retrieval models like the PRM-S to be done in a page of code.

Let’s look at what’s PRM-S, and how it can be implemented in Galago.

PRM-S

In PRM-S, we assume that each document is composed of several fields (e.g. emails). Previous work tried to use the structure by using the weighted combination of field-level scores, such as the mixture of field language models, or BM25F. (More detailed introduction of these models can be found in my paper.)

PRM-S is similar to previous retrieval models exploiting the field structure of documents, but with a key difference in that it allows each field to have weights depending on the field and query-term. For example, while previous work allowed to explain the notion of one field being more important than another (e.g. title is more important than body), yet not the case where each field has a different importance for each query-term. To see why this is a useful thing to do, please refer to my previous post about this model.

In terms of estimation, mapping probabilities are determined based on the Bayesian classification of query-term into one of field-level language models. The following excerpt from my ECIR slide shows (1) the calculation of mapping probability (MP), and (2) the corresponding retrieval model where field-level query-likelihood scores are combined using MP as weights.

As you can see above, the implementation of the mapping probabilities (MP) requires the field-level collection frequency of each query-term, and the length of each field. And then the MP can be used as weights in a field-level mixture language model. In what follows, I’ll introduce steps for implementing such retrieval model within the Galago search engine framework.

Our Goal : Transforming a Simple Query into a PRM-S Query

Like its predecessor the Indri, the Galago is a based on the combination of inference network and language modeling approaches for IR, although an arbitrary retrieval model to be implemented thanks to its flexible architecture. In Galago, you can construct a complex query by building a hierarchy of nodes. More details can be found in Don Metzler’s Indri query language description.

Let’s start by defining what we want to do clearly. Given a simple query like ‘meg ryan romance’ against a movie collection composed of fields such as {title, genre, cast, team, plot}, our goal is to transform it into the following structured query.

#combine(
#combine:0=0.407:1=0.382:2=0.187 ( meg.cast  meg.team  meg.title )#combine:0=0.601:1=0.381:2=0.017 ( ryan.cast  ryan.team  ryan.title )#combine:0=0.927:1=0.070:2=0.002 ( romance.genre  romance.title  romance.plot ))

In Galago, such transformation can be done by implementing Traversal interface, which defines how a given query can be transformed into another query. Since each query is represented as a hierarchy of nodes, we are essentially performing a graph-to-graph transformation here.

Getting the Length of Each Field

Before we construct actual retrieval model, we first need to get the length of each field that will be used as a denominator in calculating MP.

In Galago, you can fetch some information from a part of the index by creating an appropriate node structure. In our case, we first fetch a field list from user’s query, and then create an all node for each fields which iterates through all the occurrences of extents. And the term count can be calculated using the xcount method, which returns the  occurrences count of a given expression.

Constructing the Retrieval Model

To complete the implementation, we need to construct the following node (circle) structure with corresponding parameters (table). Here, each arrow denotes a parent-child relationship between nodes. (A node can contain multiple children in Galago)

To look at the structure from bottom-up, we first create two extent nodes whose function is to read the information from corresponding index files. Here, the first node is for reading positions of a term (from “posting” file), and the second node is for reading positions of a field (from “extents” file). While the extent node returns a set of start and end positions for each extent, a term is considered as an extent with size 1 in Galago, so we use the extent node for representing both terms and extents.

Given these two extent nodes, we then create an inside node whose function is to return the number of times the left extent is contained by the right node. If the extents are identical, then they are counted. In our case, since the left child has positions of a term and the right one has positions of an extent, the output of the inside node is the count of a specific term within an extent. (e.g. How many times ‘meg’ occurred in cast field? “<cast> meg </cast> <title> meg says hello </title>”  returns the count = 1)

We then need to convert the count into the score that can be used as a input for other operators. In Galago, a feature node is responsible for turning a raw expression count into a score. While this can be done in many different ways, we used the query-likelihood score with Dirichlet smoothing in our example.

The code below shows how the node structure as above can be built. For each query-term (outer loop) and field (inner loop), you can see that a feature node is created and a mapping probability is calculated, which are then used to create a combine node. Here, Combine nodes return a normalized weighted sum of the scores produced by each child node. The weights are specified through the parameter object. The weights are specified as in an array, where index 0 defines the weight of the first child node, index 1 defines the weight of the second, and so on. It is important to note that the weights are normalized by the total weight sum.

Using PRM-S in Galago

Given the implementation as above, you can use the PRM-S using the following query syntax, which then is transformed into a structured query with mapping probabilities built-in. While PRM-S is not checked-in to Galago source repository at this point, it will be available for use within a week or two.

Here I introduced the PRM-S briefly, and then explained how I implemented it using the Galago. Please let me know  if you have any questions or comments.

p.s. Special thanks to Sam and Marc for helping me in learning Galago and implementing this!

References

[1] A Probabilistic Retrieval Model for Semi-structured Data _[paper]
Jinyoung Kim, Xiaobing Xue and W. Bruce Croft, Proceedings of the 31st European Conference on Information Retrieval (ECIR), Tolouse, France, Apr. 6-9, 2009, pp. 228-239.

[2] Retrieval Experiments using Pseudo-Desktop Collections _[paper]
Jinyoung Kim and W. Bruce Croft, Proceedings of the 18th ACM Conference on Information and Knowledge Management (CIKM), Hong Kong, China, Nov. 2-6, 2009, pp. 1297-1306.

My previous research internship at Microsoft Bing (with Vitor Carvalho) gave me a good exposure to web search research, and I’m hoping to extend my experience in that area further throughout this summer. I’ll be working on the general problem of user modeling and search personalization.

The summer at Seattle and Puget sound area was lovely as ever.

Drop me a line if you’ll be around Seattle area this summer!

The article starts by mentioning the vision of lifelogging, and making the distinction of lifelogging from other PIM activities as follows:

… Note that we distinguish between lifelogging and other more deliberate activities involving the capture of personal data (such as digital photography and blogging) that involve the effortful selective capture and display of digital materials for a particular audience. In contrast, lifelogging seeks to be effortless and all-encompassing in terms of data capture. …

They outline potential benefits for memory by describing the ways such systems might support “the five Rs,” or the activities they call recollecting (past experience), reminiscing (emotional events), retrieving (specific information), reflecting (to gain different perspective), and remembering intentions (prospective events). It was interesting for me that the application of lifelogging system can extend to almost all uses of human memory.

Then they argue that, despite early positive results, more recent research should make us skeptical, adding that records may be less useful than we might first think. They further point out that many lifelogging systems lack an explicit description of potential value for users, focusing instead on technical challenges. For instance, they say, even when—contrary to lifelogging principles—we deliberately choose to save digital memorabilia, we seldom access them.

As a solution, lifelogging research, they suggest, should  build on understanding of human memory and when and how memory fails, focusing on addressing those difficulties. Another point is that the design of a system should depend on the type of memory (Five R’s) it tries to support. They provide the following examples:

• It is well known in the psychological literature that there are strong connections between these autobiographical memories and visual images. This suggests that the interfaces for such systems should focus on images as the backbone of their design.
• Systems for retrieval need not be concerned with recollection, but rather with efficient ways of searching though large heterogeneous collections of data and so provide access to metadata that might support effective search.
• Systems for reflection might be different still where abstraction is important, offering flexible and novel methods for viewing personal data in ways that might surprise, provoke, or educate users.
• Designing systems to support remembering intentions need to focus on delivering timely cues in appropriate contexts if they are to provide effective reminders.

As I noted in my previous post, the general lesson here seems to be that any system intended for human should be designed with the consideration of the intended use first. Jef Raskin’s message is painfully relevant here.

Once the product’s task is known, design the interface first; then implement to the interface design

In the end, Lifelogging is a burgeoning field of research, which people are just starting to get excited about in the real world ( Visit http://quantifiedself.com/ ), and this kind of feedback will be very helpful for its growth.

• Things That Make Us Smart by Donald Norman
• The Humane Interface by Jef Raskin

As an IR graduate student who have mostly known the world of retrieval models and TREC-style evaluations, these books help me understand the cognitive characteristics of a user, and how a computer system should be designed to be usable and useful.

Don Norman’s book provide the viewpoint that a user interface is a representation of given task, and argues that it should have the following characteristics to be considered ideal:

• Capture important features of the represented world while ignoring the irrelevant
• Is appropriate for the person, enhancing the process of interpretation
• Is appropriate for the task, enhancing the ability to make judgments,  to discover relevant regularities and structures

Also, the book introduces two kinds of cognition as follows:

• Experiential mode leads to a state in which we perceive and react to the events around us, efficiently and effortlessly. This is the mode of expert behavior, being a key component of efficient performance.
• Reflective mode is that of comparison and contrast, of thought, of decision making. this is the mode that leads to new ideas, novel responses.

This distinction is useful in designing cognitive artifacts because tools for experiential mode behavior should not require reflection (e.g. the design of interface for everyday use should feel natural). Also,since effective reflection requires some structure and organization, tools for reflection should support comparison, exploration, and problem solving.

Jef Raskin’s book starts by defining ‘The Human Interface’, which has the following characteristics:

• It is responsive to human needs and considerate of human frailties.
• It should not waste your time or require you to do more work than is strictly necessary.
• Users should set the pace of an interaction. (e.g. Users should not be kept waiting unnecessarily)

It is interesting to note that Jef Raskin’s book introduces similar concept of cognitive consciousness and cognitive unconsciousness, which roughly correspond to the idea of Reflective mode and Experiential mode. Any sequence of actions that a user perform repeatedly will become automatic eventually, moving the user from the realm of cognitive consciousness to cognitive unconsciousness.

Given this, he says, one mandate as designers is to create interfaces that do not allow habits to cause problems for the user. For instance, any confirmation step that elicits a fixed response soon becomes useless because the user will develop an automatic response to that.

Jef’s books include many other useful pieces of advice for user interface designers. While Wikipedia article of the book has a brief summary, just to quote a few here:

• We must take into account common factors first we can deal with the differences among individual humans. (don’t try personalization before getting the basic interface right
• Once the product’s task is known, design the interface first; then implement to the interface design
• Attention to detail is crucial for keep user engaged.
• Users should be focusing on the task, not the system

I strongly recommend reading these books for anyone designing an interface that should be used by humans.

Any other recommendations for IR students who’s getting into the field of HCI?

So far, I’ve mostly worked on the area of structured document retrieval and the retrieval of personal documents. Currently I’m preparing my thesis proposal whose main topic is combining different methods (keyword search, associative browsing and metadata-based filtering) for personal documents retrieval.

Last year, I had summer internship at MSR / Bing Search, working with Vitor Carvalho as mentor. My intern project was about analyzing and controlling the time-instability in web search results.  The first part of this work is published at ECIR’11 and the second part is currently under submission to the World Wide Web conference (WWW’11).

For this year’s internship, while continuing my efforts in information retrieval research, I aim to focus my attention to areas which involves a more close interaction with the user. This include personalized search, exploratory search, interactive IR and so on, which are typically referred to as Human-Computer Information Retrieval (HCIR). Depending on the project, I am also open to other problems regarding information retrieval and human-computer interaction.

You can visit my webpage to see my publications, CV and research statement. Please let me know if you have a relevant position or know someone who does. You can email me at jykim dot cs dot umass dot edu.