Professor Hsuan-Tien Lin　Department of Computer Science and Information Engineering National Taiwan Universit

From Ordinal Ranking to Binary Classification

Ordinal ranking is an important concept in modeling our preferences. We rank hotels by stars to represent their quality; we give feed-backs to products on Amazon using a scale from one to five; we say that the weather is hot, warm, cool, or cold without referring to the actual temperature. The wide applications of ranking range from social science to behavioral science to information retrieval. For yet another example, in 2006, Netflix (an on-line DVD rental company) announced a million-dollar-prize challenge for building a better automatic personalized movie ranking system that just ended in 2009. The prize really heated up the competition in machine learning and related areas. Many machine learning algorithms are designed in recent years to understand ordinal ranking better, but the design process can be time-consuming. Our work presents a novel alternative---a reduction framework that systematically transforms ordinal ranking to simpler yes/no questions, i.e., binary classification. Then, well-studied binary classification algorithms can be effortlessly casted as new ordinal ranking ones. Furthermore, the reduction framework reveals a strong theoretical connection between ordinal ranking and binary classification, and allows us to easily extend well-known theoretical results for binary classification to new ones for ordinal ranking. In this talk, I will discuss the key ideas of the reduction framework, as well as its theoretical and algorithmic merits, using the Netflix challenge as an example.