CS630 Representing and Accessing Digital Information Lecture 11: March 2, 2006 1 Scribes: Gilly Leshed, N. Sadat Shami Outline 1. Review: Relevance Feedback 2. Interactive Query Expansion (IQE) 3. AQE vs. IQE 4. Active Relevance Feedback 5. Evaluation of Relevance Feedback 6. Motivation for Implicit Relevance Feedback 1 Review: Relevance Feedback Explicit Relevance Feedback (RF) is the process in which the user marks documents initially retrieved by an IR system as relevant or not. The system then uses this information to retrieve a better set of results for the user’s query. In the previous lecture we discussed the following ways to use RF information: • Term Re-weighting: Weights of terms that appear in the query are adjusted as a result of the RF information, and the document scores are re-calculated. For instance, a query term that appears in a judged relevant document will most likely receive increased weight. • Query Expansion (QE): A process in which terms are added to the query as a result of the examination of judged relevant documents. We examined how, methodologically, QE can be applied to the VSM, probabilistic model, and language model. These methods assume that the system automatically expands the query given the RF information. We can therefore refer to these techniques as Automatic Query Expansion (AQE). However, AQE can be confusing to users, as they do not necessarily understand how the system works: the underlying mechanism of RF and AQE is not transparent to users [1]. 2 Interactive Query Expansion (IQE) To clarify the concept of query expansion, instead of applying it “behind the back” of users1, we can ask the user’s permission to add terms to the query, basing the suggested terms on the RF information. This is the idea of Interactive Query Expansion (IQE), of which the process is: - Given RF, re-rank terms and list them in descending order - Ask user which terms from the list to add to the query 2.1 IQE Advantages • User more in control of the process • It makes more use of the user’s knowledge • Additional feedback, beyond document relevance feedback, is provided about terms 2.2 IQE Disadvantages 1 The following exercise could be applied to check if a certain IR system is applying AQE: (1) type a query; (2) given the results, guess which terms could have been added to the query; (3) type the query with the conjectured terms. If the results of (1) and (3) match, it is possible that the system is applying AQE.CS630 Representing and Accessing Digital Information Lecture 11: March 2, 2006 2 • Extra work for the user • Poor user choice of which terms to add could produce inferior results. From a user-centered perspective we need to consider what it means for a user to make a “poor choice”. The user could (1) misunderstand the meaning of terms, or (2) misjudge which terms would be useful for the system to enhance the number of relevant documents retrieved. Additionally, as mentioned in a prior lecture, perhaps the interface used for searching/formulating a query does not follow the mental model of certain users. For example, a user can easily judge whether a document is relevant or not, but most users have problems formulating effective query terms. 3 AQE vs. IQE Two complementary ways can be considered to examine which approach is superior, AQE or IQE: user preference and system performance. 3.1 User Preference: Fowkes and Beaulieu, 2000 The degree to which users prefer AQE or IQE depends on how well they perceive the system is performing in either approach. Fowkes and Beaulieu [3] found that AQE seemed more effective to users for simpler search tasks whereas IQE appeared more productive for more complex search tasks. The concept of delegating the control back to the user in IQE can also play a role in user preference. Users might evaluate the results of IQE as more valuable than AQE because it keeps them in the loop. 3.2 System Performance: Ruthven, 2003 In a paper that won the Best Paper Award in SIGIR 2003, Ruthven described a way to compare the performance of AQE with that of IQE [4]. He looked at three AQE concepts, namely, collection independent, collection dependent, and query dependent. 3.2.1 Simulating IQE First, Ruthven describes a method in which IQE was simulated, over a total of 99 queries in three separate collections: For each query, 1. The documents were initially ranked using VSM. 2. A list of 15 possible expansion terms was obtained from user-judged relevant documents. 3. All 32678 combinations of expansion terms were created, simulating all possible IQE decisions that a user could make. 4. Each combination of expansion terms was separately added to the original query and the documents were re-ranked using VSM. 5. For each of the 32678 versions of query expansion results, recall-precision performance measures were calculated. These 32678 possible IQE versions were then sorted by performance, providing the best performing IQE decision at the top and the worst performing IQE decision at the bottom. 3.2.2 Query Expansion vs. No Query Expansion One way to compare AQE with IQE is to show which of them improves more over the “no query expansion” results, in terms of the percentage of queries that were improved by these strategies. On average, AQE was more likely to improve the results of a query than to harm it, with the query dependent approach performing better and the collection independent approach performing worst. However, the best performing IQE decision for each query improved the queries in a much higher percentage than all AQECS630 Representing and Accessing Digital Information Lecture 11: March 2, 2006 3 approaches. Ruthven suggests that this only represents a potential benefit, as there is no guarantee that the user can easily select the best performing set of terms to add to the query. 3.2.3 AQE vs. IQE To address the question of the potential of IQE decisions to perform better than AQE, Ruthven compared how many IQE decisions actually performed better than AQE. In all, depending on the corpus, only 9-12% of possible IQE decisions performed significantly better than the corpus independent approach, which can be considered as the most realistic approach. This implies that it may be hard for users to select the set of terms that would expand the query to produce superior results. In a pilot study using three human participants, users were presented with 15