Learning-Related Complexity of Linear Ranking Functions Author: Atsuyoshi Nakamura Source: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, October 2006, Proceedings, (José L. Balcázar, Phil Long and Frank Stephan, Eds.), Lecture Notes in Artificial Intelligence 4264, pp. 378 - 392, Springer 2006. 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. ©Copyright 2006, Springer