Solving label ranking problems via error-correcting output codes (Ba/Ma)
Topic for a bachelor/master's thesis
Short Description:
Label ranking is a specific problem in the realm of preference learning [1]. It can be seen as a generalization of multi-class classification, in which the problem is to learn a mapping from instances to rankings (permutations) over a finite number of alternatives (class labels). Ranking by pairwise comparison (RPC) is a state-of-the-art approach to label ranking [2]. RPC constructs one binary classifier for each pair of labels, and trains it to decide which of the two is preferred to the other one; thus, RPC effectively reduces a label ranking problem to a set of binary classification problems. At prediction time, a ranking is assembled from the predictions of the binary classifiers.
RPC can be seen as a special case of learning with error-correcting output codes (ECOC) [3]. Al- though the number of binary models is relatively small in comparison to the size of the output space, i.e., the set of permutations of the class labels, the predictions in principle suffice to recon- struct the correct ranking thanks to the special structure of that space. Yet, reconstruction gets difficult as soon as one of the classifiers makes a mistake. In particular, due to a lack of redundancy, mistakes of that kind cannot be compensated.
The goal of the thesis, therefore, is to develop an ECOC-approach for label ranking. Important questions to be addressed in this regard include the design of the coding matrix (e.g., the binary problems should be balanced), the question of how to handle incomplete observations (partial rankings) in the training data, and how to realize the decoding step efficiently.
Requirements
Requirements: Development of a label ranking method based on ECOC; empirical evaluation of the method and systematic comparison with existing approaches, especially RPC.
Prerequisites
Basic knowledge in machine learning; programming skills.
Contact
References
- [1] J. Fürnkranz and E. Hüllermeier, editors. Preference Learning. Springer-Verlag, 2011.
- [2] E. Hüllermeier, J. Fürnkranz, W. Cheng, and K. Brinker. Label ranking by learning pairwise preferences. Artificial Intelligence, 172:1897–1917, 2008.
- [3] TG. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1995