|| Efficient Top-K Ranking
|| Communications & Networks
||Dr Changho Suh, Department of Electrical Engineering,Korea Advanced Institute of Science and Technology (KAIST)
||29 April 2015, Wednesday
||2:00 pm to 3:00 pm
||Seminar Room E5-02-32, Engineering Blk E5, Faculty of Engineering,
| Rank aggregation has been investigated in a wide spectrum of contexts like social choice, web search, graduate admission, crowdsourcing, recommendation system and sports competitions. In the big data era, however, a new challenge arises: due to the huge number of items/candidates to be ranked, observation of the complete data sets is often infeasible. This challenge brings about a series of significant questions. How can we identify a ranking of the items, given highly incomplete measurements of data sets? Is there a low-complexity algorithm that promises the optimal ranking accuracy, usually quantified as minimal sample complexity? Can we exploit realistic scenarios in which only a few significant items, say top-K items, are emphasized among the huge number of the entire items?
In this talk, I will present some of our recent progress towards addressing the questions: (1) characterizing the minimal sample complexity required for recovering the top-K ranked items; (2) developing a computationally efficient algorithm that can achieve the limit. Specifically we consider a prominent pairwise measurement model, called the Bradley-Terry-Luce model, in which measurements are of the pairwise information type: movie A is preferred over movie B; player A defeats player B.
Our main innovation lies in the development of a near linear-time two-stage ranking algorithm that exploits advantageous features of two popular paradigms: spectral methods such as Google’s PageRank, and maximum likelihood estimation, both having the low-complexity nature. This innovation enables tractability of a non-convex ranking problem with little loss of optimality, possibly giving significant ramifications into a wide range of other applications which face challenges due to the non-convex nature of their relevant problems. This is joint work with Dr. Yuxin Chen (postdoc in Prof. Emmanuel Candes’s group).
|ABOUT THE SPEAKER|
| Changho Suh is an Assistant Professor in the Department of Electrical Engineering at Korea Advanced Institute of Science and Technology (KAIST) since 2012. He received the B.S. and M.S. degrees in Electrical Engineering from KAIST in 2000 and 2002 respectively, and the Ph.D. degree in Electrical Engineering and Computer Sciences from UC-Berkeley in 2011, under the supervision of Prof. David Tse. From 2011 to 2012, he was a postdoctoral associate at the Research Laboratory of Electronics in MIT. From 2002 to 2006, he had been with the Telecommunication R&D Center, Samsung Electronics.
Dr. Suh received the 2013 Stephen O. Rice Prize from the IEEE Communications Society, the David J. Sakrison Memorial Prize (top research award in the Department) from the UC-Berkeley EECS Department in 2011, and the Best Student Paper Award of the IEEE International Symposium on Information Theory in 2009. He was also awarded the Vodafone U.S. Foundation Fellowship in 2006 and 2007, and the Kwanjeong Educational Foundation Fellowship in 2009.
| Back to seminar list |
All are welcome to attend these Seminars. Should
you have any enquiries, please contact Ms. Lily Png at 6516 6509
or you can e-mail to Ms Lily Png