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/Unit :

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
ARC Biomod
IAP Biomagnet (P6/25)

Available on ORBi :

since 03 September 2012

Statistics

Number of views

205 (24 by ULiège)

Number of downloads

4 (4 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

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.

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website