ICML-98 Submission #155

       An Efficient Boosting Algorithm for Combining Preferences

	Yoav Freund
	AT&T Labs
	180 Park Avenue, Room A205
	Florham Park, NJ  07932-0971  USA

	Raj D. Iyer
	MIT Laboratory for Computer Science
	545 Technology Square, NE43-313
	Cambridge, MA  02139  USA

	Robert E. Schapire
	AT&T Labs
	180 Park Avenue, Room A279
	Florham Park, NJ  07932-0971  USA

	Yoram Singer
	AT&T Labs
	180 Park Avenue, Room A277
	Florham Park, NJ  07932-0971  USA

Abstract

The problem of combining preferences arises in several applications,
such as combining the results of different search engines. This work
describes an efficient algorithm for combining multiple preferences.
We first give a formal framework for the problem. We then describe and
analyze a new boosting algorithm for combining preferences called
RankBoost. We also describe an efficient implementation of the
algorithm for a restricted case. We discuss two experiments we carried
out to assess the performance of RankBoost. In the first experiment,
we used the algorithm to combine different search strategies, each of
which is a query expension for a given domain. For this task, we
compare the performance of RankBoost to the individual search
strategies. The second experiment is a collaborative-filtering task,
specifically, for making movie recommendations. Here, we present
results comparing RankBoost to nearest-neighbor and regression
algorithms.

Keywords:
      ranking, boosting, meta-search, collaborative filtering,
      information retrieval

Email address of contact author:  schapire@research.att.com

Phone number of contact author:   973-360-8329