TCS-TR-A-06-15

Date: Fri May 26 15:54:34 2006

Title: Learning-Related Complexity of Linear Ranking Functions

Authors: Atsuyoshi Nakamura

Contact:

First name: Atsuyoshi
Last name: Nakamura
Address: Graduate School of Information Science and Technology, Hokkaido University, Kita 14, Nishi 9, Kita-ku, Sapporo, 060-0814 Japan
Email: atsu@main.ist.hokudai.ac.jp

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, which is considered to indicate complexity of PAC learning of the class in the multiclass classification setting, is \Theta(n+k). This graph dimension is significantly smaller than the graph dimension \Omega(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, which is easily shown by the similar technique used in the proof of an upper bound of their graph dimension.