TA3 - Learning to rank in vector spaces and social networks

Time: Monday, April 21 (half-day, morning, 8:30am to 12:00noon)
Location: Room 201C (tentative)

Abstract:

Scoring and ranking pages and ads are central to Web search and advertising. We will study machine learning and associated numerical techniques to automatically learn ranking functions for entities represented as feature vectors as well as nodes in a social network. In the feature-vector scenario, an entity, e.g., a document x, is mapped to a feature vector phi(x) in a d-dimensional space, and we have to search for a scoring weight vector beta whose dot-product with phi(x) determines its score, and therefore, rank. This case corresponds to Information Retrieval in the "vector space" model. Training data consists of a partial order of preference among entities. We will study recent Bayesian and maximum-margin approaches to solving this problem, including recent efficient linear-time approximate algorithms. We will consider various ranking performance measures and how some of them create complications for learning algorithms. In the graph node-ranking scenario, we will briefly review PageRank, generalize it to arbitrary Markov conductance matrices, and consider the problem of learning conductance parameters from partial orders between nodes. In another class of formulation, the graph does not establish PageRank or prestige-flow relationships between nodes, but encourages a certain smoothness between the scores of neighboring nodes. Some of these techniques have been used by Web search companies with very large query logs. We will review some of the issues and experience with applying the theory to practical systems, including ranking and selection for sponsored and content-driven ad placement. If time permits, we will look at general connections between score stability and rank stability, and the connection between the stability of a score/rank-learning algorithm and its power to generalize to unforeseen test data.

Presenters:

Soumen Chakrabarti, Indian Institute of Technology, Bombay (India)

Inquiries can be sent to: