Comparator selection for RPC with many labels

[en] The Ranking by Pairwise Comparison algorithm (RPC) is a well established label ranking method. However, its complexity is of O(N²) in the number N of labels. We present algorithms for selection, before model construction, a subset of comparators of size O(N), to reduce the computational complexity without loss in accuracy.

Research center :

Systmod

Disciplines :

Computer science

Author, co-author :

Hiard, Samuel ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Geurts, Pierre ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Wehenkel, Louis ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Language :

English

Title :

Comparator selection for RPC with many labels

Publication date :

August 2012

Event name :

20th European Conference on Artificial Intelligence (ECAI)

Event organizer :

European Coordinating Committee for Artificial Intelligence (ECCAI)
Association Française pour l'Intelligence Artificielle (AFIA)

Event place :

Montpellier, France

Event date :

du 27 août 2012 au 31 août 2012

Audience :

International

Main work title :

ECAI 2012 : 20th European Conference on Artificial Intelligence : 27-31 August 2012, Montpellier, France

Publisher :

IOS Press, Amsterdam, Netherlands

ISBN/EAN :

978-1-61499-097-0

Pages :

408-413

Peer reviewed :

Peer reviewed

Funders :

ULiège - Université de Liège [BE]
ARC Biomod
IAP Biomagnet (P6/25)

Available on ORBi :

since 03 September 2012

Statistics

Number of views

184 (24 by ULiège)

Number of downloads

4 (4 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms, chapter 16: "Greedy algorithms,", The MIT Press, Cambridge, MA, 1990.
E. Hüllermeier, J. Fürnkranz, W. Cheng and K. Brinker, 'Label ranking by learning pairwise preference', Artificial Intelligence, 172, 1897-1916, (2008).
University of Minnesota GroupLens Research Project. Movielens data set, http://www.grouplens.org/node/73.
S. Hiard and L. Wehenkel, 'Using class-probability models instead of hard classifiers as base learners in the ranking by pairwise comparison algorithm', in ICMLC 2011 3rd International Conference on Machine Learning and Computing, ed., Steve Thatcher, Volume 1, pp. 218-222. IEEE Press, (2011).
T. Kamishima and J. Fujiki, 'Clustering orders.', in Discovery Science, eds., Gunter Grieser, Yuzuru Tanaka, and Akihiro Yamamoto, Volume 2843 of Lecture Notes in Computer Science, pp. 194-207. Springer, (2003).
T. Kamishima, H. Kazawa, and S. Akaho, 'Supervised ordering an empirical survey', in In Proc. of The 5th IEEE Intl Conf. on Data Mining, pp. 673-676, (2005).
P. Larranage and J.A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Dordrecht, Netherland, 2001.
D. Ernst P. Geurts and L. Wehenkel, 'Extremely randomized trees', Machine Learning, 36(1), 3-42, (2006).
C. Spearman, 'The proof and measurement of association between two things. By C. Spearman, 1904.', The American journal of psychology, 100(3-4), 441-471, (1987).
L. Wehenkel, Automatic Learning Techniques in Power Systems, Kluwer Academic Publishers, Norwell, MA, USA, 1998.