Uniform Convergence, Stability and Learnability for Ranking Problems
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 1337-1342.
Abstract
Most studies were devoted to the design of efficient algorithms and the evaluation and application on diverse ranking problems, whereas few work has been paid to the theoretical studies on ranking learnability. In this paper, we study the relation between uniform convergence, stability and learnability of ranking. In contrast to supervised learning where the learnability is equivalent to uniform convergence, we show that the ranking uniform convergence is sufficient but not necessary for ranking learnability with AERM, and we further present a sufficient condition for ranking uniform convergence with respect to bipartite ranking loss. Considering the ranking uniform convergence being unnecessary for ranking learnability, we prove that the ranking average stability is a necessary and sufficient condition for ranking learnability.
@inproceedings{ijcai2013p201,
title = {Uniform Convergence, Stability and Learnability for Ranking Problems},
author = {Gao, Wei and Zhou, Zhi-Hua},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {1337--1342},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/201},
}
TY - CPAPER TI - Uniform Convergence, Stability and Learnability for Ranking Problems AU - Gao, Wei AU - Zhou, Zhi-Hua T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 1337 EP - 1342 UR - https://ijcai.org/proceedings/2013/201 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
