ML Anthology

Learning-Related Complexity of Linear Ranking Functions

Atsuyoshi Nakamura
ALT 2006 pp. 378-392
doi:10.1007/11894841_30 /alt/2006/nakamura2006alt-learningrelated/

Abstract

In this paper, we study learning-related complexity of linear ranking functions from n -dimensional Euclidean space to 1,2,..., k . We show that their graph dimension , a kind of measure for PAC learning complexity in the multiclass classification setting, is Θ( n + k ). This graph dimension is significantly smaller than the graph dimension Ω( nk ) of the class of 1,2,..., k -valued decision-list functions naturally defined using k –1 linear discrimination functions. We also show a risk bound of learning linear ranking functions in the ordinal regression setting by a technique similar to that used in the proof of an upper bound of their graph dimension.

PDF ALT Semantic Scholar

Cite

Text

Nakamura. "Learning-Related Complexity of Linear Ranking Functions." International Conference on Algorithmic Learning Theory, 2006. doi:10.1007/11894841_30

Markdown

[Nakamura. "Learning-Related Complexity of Linear Ranking Functions." International Conference on Algorithmic Learning Theory, 2006.](https://mlanthology.org/alt/2006/nakamura2006alt-learningrelated/) doi:10.1007/11894841_30

BibTeX

@inproceedings{nakamura2006alt-learningrelated,
  title     = {{Learning-Related Complexity of Linear Ranking Functions}},
  author    = {Nakamura, Atsuyoshi},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2006},
  pages     = {378-392},
  doi       = {10.1007/11894841_30},
  url       = {https://mlanthology.org/alt/2006/nakamura2006alt-learningrelated/}
}