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.
展开▼
