Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1345518580.pdf (753.87 KB)

ETD Abstract Container

Abstract Header

Statistical Consistency of Ranking:Bipartite and Multipartite Cases

Uematsu, Kazuki
http://rave.ohiolink.edu/etdc/view?acc_num=osu1345518580

Abstract Details

2012, Doctor of Philosophy, Ohio State University, Statistics.
Ranking methods have important applications in many fields such as information retrieval, web search, and collaborative filtering. Understanding statistical properties of ranking is important. This thesis investigates the theoretical relation between loss criteria and the optimal ranking functions driven by the criteria in ranking. In bipartite ranking, the relation between Area Under the Curve (AUC) maximization and minimization of ranking risk under a convex loss is examined. We show that the best ranking functions under convex loss criteria produce the same ordering as the likelihood ratio of the positive category to the negative category over the instance space. The result illuminates the parallel between ranking and classification in general. For a certain class of loss functions including the exponential loss and the binomial deviance,we specify the optimal ranking function explicitly in relation to the underlying probability distribution. In addition, we point out that the SVM type method for ranking may produce potentially many ties or granularity in ranking scores due to the singularity of the hinge loss, and this could result in ranking inconsistency. Some of the results in bipartite ranking can be extended to multipartite ranking by defining a pairwise ranking loss function. Through minimization of the theoretical risk which combines pairwise ranking errors of ordinal categories with differential ranking costs, we study the consistency of multipartite ranking algorithms. The extension shows that for a certain class of convex loss functions, the optimal ranking function can be represented as a ratio of weighted conditional probability of upper categories to lower categories, where the weights are given by the misranking costs. This result also bridges traditional ranking methods such as proportional odds ratio model in statistics with algorithmic ranking methods in machine learning. Further, the analysis of multipartite ranking with different costs provides a new perspective on nonsmooth ranking measures such as the Discounted Cumulative Gain. We illustrate our findings with simulation studies and real data analysis.
Yoonkyung Lee (Committee Chair)
Haikady Nagaraja (Committee Member)
Tao Shi (Committee Member)
Statistics
Learning to rank

Recommended Citations

Citations

  • Uematsu, K. (2012). Statistical Consistency of Ranking:Bipartite and Multipartite Cases [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1345518580

    APA Style (7th edition)

  • Uematsu, Kazuki. Statistical Consistency of Ranking:Bipartite and Multipartite Cases. 2012. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1345518580.

    MLA Style (8th edition)

  • Uematsu, Kazuki. "Statistical Consistency of Ranking:Bipartite and Multipartite Cases." Doctoral dissertation, Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1345518580

    Chicago Manual of Style (17th edition)

osu1345518580
720
© 2012, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.