Top Rank Optimization in Linear Time
arXiv:1410.1462
Abstract
Bipartite ranking aims to learn a real-valued ranking function that orders positive instances before negative instances. Recent efforts of bipartite ranking are focused on optimizing ranking accuracy at the top of the ranked list. Most existing approaches are either to optimize task specific metrics or to extend the ranking loss by emphasizing more on the error associated with the top ranked instances, leading to a high computational cost that is super-linear in the number of training instances. We propose a highly efficient approach, titled TopPush, for optimizing accuracy at the top that has computational complexity linear in the number of training instances. We present a novel analysis that bounds the generalization error for the top ranked instances for the proposed approach. Empirical study shows that the proposed approach is highly competitive to the state-of-the-art approaches and is 10-100 times faster.
References in corpus (3)
Cited by in corpus (20)
- Radiological images and machine learning: trends, perspectives, and prospects
- Few-Shot Deep Adversarial Learning for Video-based Person Re-identification
- Quality Aware Network for Set to Set Recognition
- Top Rank Optimization in Linear Time
- Optimizing Top Precision Performance Measure of Content-Based Image Retrieval by Learning Similarity Function
- On the Theories Behind Hard Negative Sampling for Recommendation
- Top-k Multiclass SVM
- Top-push Video-based Person Re-identification
- Optimizing Two-way Partial AUC with an End-to-end Framework
- Drug Selection via Joint Push and Learning to Rank
- Click-aware purchase prediction with push at the top
- Transductive Optimization of Top k Precision
- Surrogate Functions for Maximizing Precision at the Top
- The Limited Multi-Label Projection Layer
- Exploit Bounding Box Annotations for Multi-label Object Recognition
- Perceptron like Algorithms for Online Learning to Rank
- Nonlinear classifiers for ranking problems based on kernelized SVM
- Confidence-Weighted Bipartite Ranking
- Semi-supervised Collaborative Ranking with Push at Top
- Projections onto the canonical simplex with additional linear inequalities