|
Thorsten Joachims
Cornell University Learning Rankings for Information Retrieval [Slides] Abstract: Ranked retrieval has become the dominant search engine interface. The key component of a ranked-retrieval system is the function that generates the ranking. Determining the optimal ranking function can be cast as a machine learning problem: given a query, predict an ordering over the document collection that best covers the user's information need. This talk discusses the properties and challenges of this prediction task. In addition, it proposes a method for addressing one of the challenges, namely that of optimizing the ranking function to performance measures like Average Precision or ROC Area. The talk explores a Support Vector Method that directly optimizes these measures. Bio: Thorsten Joachims is an Assistant Professor in the Department of Computer Science at Cornell University. In 2001, he finished his dissertation with the title "The Maximum-Margin Approach to Learning Text Classifiers: Methods, Theory, and Algorithms", advised by Prof. Katharina Morik at the University of Dortmund. From there he also received his Diplom in Computer Science in 1997 with a thesis on WebWatcher, a browsing assistant for the Web. His research interests center on a synthesis of theory and system building in the field of machine learning, with a focus on Support Vector Machines and machine learning with text. He authored the SVM-Light algorithm and software for support vector learning. From 1994 to 1996 he was a visiting scientist at Carnegie Mellon University with Prof. Tom Mitchell. Yoram Singer The Hebrew University Beyond Pair-wise Classification and Regression: Efficient Learning of Preferences by Soft Projections onto Polyhedra Abstract: We discuss the problem of learning to predict the order of nodes in a graph from a real valued feedback associated with each node. This setting includes as special cases binary classification, multiclass categorization, and multilabel ordering. In the preference graph problem the nodes are labels and edges express preferences over labels. In contrast to many ranking algorithms which decompose a ranking problem into preferences over pairs, we approach the problem employing a loss which assesses the quality of a predicted graph with respect to a feedback graph. This loss is defined by decomposing the feedback graph into bipartite sub-graphs. We then adopt the maximum-margin framework which leads to a quadratic optimization problem with linear constraints. While the size of the problem grows quadratically with the number of the nodes in the feedback graph, we derive a problem of a much smaller size and prove that it attains the same minimum. We then describe a new algorithm for solving the reduced problem. The algorithm employs "soft" projections onto a polyhedron defined by a reduced set of constraints. We also describe and analyze a wrapper procedure for batch preference graph learning when multiple graphs are provided for training. We conclude with the description of a set of experiments which underscore the merits of the algorithm over interior-point methods. Bio: Yoram Singer is an associate professor of computer science at the Hebrew University, Jerusalem, Israel. He is currently on leave of absence, coding at Google Inc. He obtained his Ph.D. in 1995 in computer science. From 1995 through 1999 he was a member of the technical staff at AT&T Research. His work focuses on the design, analysis, and implementation of machine learning algorithms. |