Generalization performance of bipartite ranking algorithms with convex losses
2013
Abstract Previous works describing the generalization performance of bipartite ranking algorithms are usually based on the assumption of (0–1) loss or the area under the receiver operating characteristic (ROC) curve. In this paper we go far beyond this classical framework by investigating the generalization performance of bipartite ranking algorithms with convex losses over reproducing kernel Hilbert spaces. Based on the McDiarmid inequality and Rademacher complexity, we establish the upper bound on the generalization error for a bipartite ranking algorithm. The theoretical analysis is different from the previous results on error analysis and shows the attractive uniform convergence property of regularized bipartite ranking algorithms.
Keywords:
- Hilbert space
- Uniform convergence
- Combinatorics
- Learning to rank
- Receiver operating characteristic
- Mathematical analysis
- Reproducing kernel Hilbert space
- Bipartite graph
- Ranking
- Mathematical optimization
- Rademacher complexity
- Mathematics
- Regular polygon
- Kernel (linear algebra)
- Algorithm
- bipartite ranking
- Discrete mathematics
- Upper and lower bounds
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
29
References
4
Citations
NaN
KQI