Overview

Existing popular algorithms for user preference retrieval, such as Rocchio s similarity-based relevance feedback algorithm and its variants [Rocchio (1971); Ide (1971a)], the Perceptron algorithm [Rosenblatt (1958)] and the Gradient Descent Procedure [Wong et. al. (1988)], are based on linear additions of documents judged by the user. In contrast to the adoption of linear additive query updating techniques in those algorithms, in this chapter two new algorithms, which use multiplicative query expansion strategies to adaptively improve the query vector, are designed. It is shown that one algorithm has a substantially better mistake bound than the Rocchio and the Perceptron algorithms in learning a user preference relation determined by a linear classifier with a small number of non-zero coefficients over the realvalued vector space [0, 1] ⁿ. It is also shown that the other algorithm boosts the usefulness of an index term exponentially, while the gradient descent procedure does so linearly. Applications of those two algorithms to Web search are also presented.

15.1 Introduction

Consider a collection of documents D. For any given user, her preference about documents in D is a relation defined over documents in D with respect to her information needs or search queries. For any two documents in the collection, she may prefer one to the other or considers them as being equivalent. In other words, she may...