MINING FEEDBACK IN RANKING AND RECOMMENDATION SYSTEMS

Abstract

The amount of online information has grown exponentially over the past few decades, and users become more and more dependent on ranking and recommendation systems to address their information seeking needs. The advance in information technologies has enabled users to provide feedback on the utilities of the underlying ranking and recommendation systems, and in return the systems to utilize such feedback for enhanced service. It is increasingly important to be able to tailor relevant information for different users and applications given various feedback. In this dissertation, we study how feedback can be utilized to improve the service quality of ranking and recommendation systems, in the application context of Web search engines and large scale digital libraries.

We first introduce a flow-based collaborative ranking model of users’ collective feedback in an online information seeking process. The model constructs a flowbased network to describe the relationship among collaborating users, queries, and documents. This generic model allows us to quantitatively investigate the properties of a collaborative ranking process. We also present a collaborative ranking algorithm derived from this model.

We then study the implicit user feedback in query reformulations in the context of general purpose Web search ranking. Specifically, we apply the knowledge of user feedback to address the problems introduced by the under-specified queries. We propose an algorithm to leverage the query context to refine the relevance ranking of the search results. We describe empirical evaluations which demonstrate the benefits of our proposal.

We then study the utility of feedback in two vertical ranking and recommendation systems. The first is a geographic information retrieval system. We analyze users’ historical clicks as their implicit feedback to the system, and study two click-based models to infer geographical preference based on mining the user click stream data. We are able to identify search queries and documents with spatial specificity, and generate effective relevance features for search ranking.

The second vertical is a venue recommendation system for digital libraries. We study the feedback loop of publication quality and venue organization, and propose a set of heuristics to automatically discover prestigious (as well as low-quality) publication venues by exploring the characteristics of the venue organizers.

 

Chapter 1

Introduction

In the past few decades we have witnessed the exponential growth of information available online. The growth rate is getting faster on the Web [2, 52, 79] , owing to enabling technologies for self-publishing and the recent flourish of user generated content such as blogs. Studies in 2007 estimated the number of Web pages to be close to 30 billion [2] , and the number of URLs found by a major commercial major search engine is even higher at one trillion^[1] [3] . To make the situation worse, although there are a number of standardization bodies such as the W3C^[2] and IETF^[3] , there is no “quality control” per se for the online content. Thus, information-seeking users have to face a prohibitive situation similar to “finding needles in a haystack”.

There are a number of directions along which solutions to this problem have been proposed. For example, the Semantic Web is proposed as an extension of the raw Web: by adding an additional layer on which the semantics of information and services on the Web is annotated, it enables computers to accurately understand and utilize these information and services to serve the users. However, until the Semantic Web becomes ubiquitous, the most widely adopted solutions are ranking and recommendation systems operating directly on the raw Web.

What are ranking and recommendation systems? Before we give them formal definitions in Chapter 2, here we describe them intuitively as follows. In an information-seeking scenario where the amount of available information is so huge that a user cannot practically evaluate, comprehend, and consume all of them, a ranking and recommendation system filters irrelevant information, ranks the different pieces of information based on a number of user-defined metrics, recommends and presents a much smaller subset of information to the user. Applications of these systems, such as a Web search engine, have become the indispensable information gateway for users nowadays [1] .

In this dissertation, we study how feedback can be utilized to improve the service quality of ranking and recommendation systems. Feedback is a process in which some proportion of the output signal is passed back as input, in order to dynamically adjusts the system’s behavior. In the context of ranking and recommendation systems for online information, we are interested in two types of feedback (formal definitions to follow in Chapter 2):

• Internal feedback. feedback that propagate among the distinct entities internal to the system, such as two different but somewhat correlated
• External feedback. feedback that propagate between the system and the external entities, such as a search engine and its users.

As in other systems and services that involve user interactions, external feedback provide a valuable source of user preference for ranking and recommendation systems. A typical scenario where user feedback help improve system performance is collaborative search ranking, in which the collective usage patterns of collaborating users are analyzed and utilized as implicit feedback to enhance the relevance ranking quality. Thus, our first research question is to investigate and model such a collaborative ranking process, more specifically,

How do we model the collaborative search process, formulate a quantitative representation of the implicit feedback from the collaborating users, and derive a feedback-based collaborative ranking framework?

In the first part of this dissertation, we systematically investigate the properties of various feedback among users, documents, and queries in a collaborative ranking process. We propose a flow-based collaborative ranking model, which casts the collaborative ranking problem into a network flow problem. The relations among the heterogeneous entities – queries, documents, and collaborating users are drawn into a concise and cohesive framework. Based on this model, we describe FlowRank, a collaborative ranking algorithm, and demonstrate its utility in improving relevance ranking.

The next research question is, from a practitioner’s standpoint, to study how feedback can be used in real-world ranking and recommendation systems, more

specifically,

How do we utilize feedback in the application context of general purpose Web search ranking systems, as well as vertical (i.e., special purpose) search ranking and recommendation systems?

In the second part of this dissertation, we first study an aspect in the flowbased collaborative ranking model: the utility of users’ feedback on search queries in a general purpose Web search ranking system. We describe a method Q-Rank to mine the collective feedback embedded in query logs, and to use the distributional information of what we defined as query contexts, to effectively improve the relevance ranking for search queries that are not very well articulated.

We then present two case studies on the utility of feedback in special purpose ranking and recommendation systems. First, we investigate users’ clicks as their implicit feedback on locality preference in geographic search ranking. By mining historical user click stream data, we present two models of users’ geographical interests, and address three important issues in spatial Web search. First, search queries and documents can be classified by the model according to their spatial specificity. Second, the geographical centers of interests for queries and documents can be inferred. Finally, the model is adapted to generate meaningful relevance features for search ranking. Second, we study feedback in the context of a venue recommendation system in digital libraries. Specifically, we investigate the correlation between the publishing and collaboration patterns of the program committee members, and the quality of the publication venues. Based on these feedback, we propose a number of heuristics to automatically discover prestigious as well as low-quality academic conferences. See Figure 1.1 for an overview of the structure of this dissertation.

Figure 1.1. Overall structure of the dissertation and the relationship among different chapters.

Key Contributions

1. We introduce a flow-based model of collaborative ranking [140] , which quantitatively describes the various feedback relationship among users, queries, and documents. This model translates the collaborative ranking problem into a network flow calculation problem. We also present a systematic case study on a number of ranking scenarios using the model.
2. We study the utility of feedback in general purpose Web search ranking systems. We propose a method Q-Rank to leverage the implicit feedback on search queries and to apply such feedback to effectively refine the ranking of Web search results, especially for naive or ambiguous queries [138, 139] .
3. We demonstrate the utility of user clicks as implicit feedback in a geographic search ranking system. We describe a method to use the geographic distribution of user clicks to model the collective locality preference [137, 136] .
4. We investigate the feedback relationship between the academic venues, the organizers, and their publishing and collaboration patterns. We propose a set of heuristics to rank and recommend academic conferences, and to discover emergent venues of good quality [141] .

Organization

The rest of this dissertation is organized as follows. In Chapter 2, we present a detailed review of relevant literature and provide definitions for common terminologies and annotations used throughout the dissertation. In Chapter 3, we introduce the flow-based collaborative ranking model, FlowRank, systematically study the feedback relationship among collaborating users, search queries, and relevant documents. We also empirically demonstrate the effectiveness of our model. In Chapter 4, we continue to explore one specific type of feedback, study the utility of users’ implicit feedback on search queries, and describe a method Q-Rank to improve relevance ranking based on such feedback. We further evaluate our Q-Rank proposal, comparing it against the query-log based authority analysis algorithm [84] , and describe our evaluation in Chapter 5. While Chapters 3, 4, and 5 are for general purpose search ranking, Chapters 6 and 7 present two case studies on the utility of feedback in vertical ranking and recommendation systems. In Chapter 6, we investigate two models of users’ geographic interests, based on historical click patterns as the implicit feedback. The models we proposed prove effective in identifying search queries with spatial specificity, and in improving relevance ranking for geographic search queries. In Chapter 7, we study the problem of venue ranking and recommendation, by investigating the feedback relationship of a venue and its organizers. We describe a method to measure the quality of academic conferences.

In Chapter 8, we conclude the dissertation.

[1] According to Google, not all lead to unique Web pages.

[2] The W3C Consortium http://www.w3c.org/

[3] The Internet Engineering Task Force, http://www.ietf.org/

MINING FEEDBACK IN RANKING AND RECOMMENDATION SYSTEMS

Sharing is caring!