Random forests with random projections of the output space for high dimensional multi-label classification

Joly, Arnaud; Geurts, Pierre; Wehenkel, Louis

doi:10.1007/978-3-662-44848-9_39

Download

Paper published in a book (Scientific congresses and symposiums)

Random forests with random projections of the output space for high dimensional multi-label classification

Joly, Arnaud; Geurts, Pierre; Wehenkel, Louis

2014 • In Machine Learning and Knowledge Discovery in Databases

Peer reviewed

Permalink
https://hdl.handle.net/2268/172146

DOI
10.1007/978-3-662-44848-9_39

Files (3)Send to Details Statistics Bibliography Similar publications

Files

Full Text

ajoly2014.pdf

Author postprint (682.99 kB)

Download

Annexes

poster.pdf

Publisher postprint (626.49 kB)

Poster

Download

slides.pdf

Publisher postprint (675.09 kB)

Slides from the ECML presentation

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Machine learning; Multilabel; Random forest; Random projections

Abstract :

[en] We adapt the idea of random projections applied to the out- put space, so as to enhance tree-based ensemble methods in the context of multi-label classification. We show how learning time complexity can be reduced without affecting computational complexity and accuracy of predictions. We also show that random output space projections may be used in order to reach different bias-variance tradeoffs, over a broad panel of benchmark problems, and that this may lead to improved accuracy while reducing significantly the computational burden of the learning stage.

Research center :

Systems and Modeling Research Unit

Disciplines :

Computer science

Author, co-author :

Joly, Arnaud ; 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) > Algorith. des syst. en interaction avec le monde physique

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 :

Random forests with random projections of the output space for high dimensional multi-label classification

Publication date :

15 September 2014

Event name :

7th European machine learning and data mining conference (ECML-PKDD 2014)

Event place :

Nancy, France

Event date :

From 15 September au 19 September 2014

Audience :

International

Main work title :

Machine Learning and Knowledge Discovery in Databases

Peer reviewed :

Peer reviewed

Tags :

CÉCI : Consortium des Équipements de Calcul Intensif

Additional URL :

http://arxiv.org/abs/1404.3581
http://github.com/arjoly/random-output-trees

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
PASCAL2
IUAP DYSCO
CÉCI - Consortium des Équipements de Calcul Intensif [BE]

Commentary :

Source code is available at https://github.com/arjoly/random-output-trees in bsd license

Available on ORBi :

since 21 September 2014

Statistics

Number of views

543 (84 by ULiège)

Number of downloads

804 (48 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671-687 (2003)
Agrawal, R., Gupta, A., Prabhu, Y., Varma, M.: Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 13-24. International World Wide Web Conferences Steering Committee (2013)
Blockeel, H., De Raedt, L., Ramon, J.: Top-down induction of clustering trees. In: Proceedings of ICML 1998, pp. 55-63 (1998)
Breiman, L.: Random forests. Machine Learning 45(1), 5-32 (2001)
Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Wadsworth (1984)
Candes, E.J., Plan, Y.: A probabilistic and ripless theory of compressed sensing. IEEE Transactions on Information Theory 57(11), 7235-7254 (2011)
Cheng, W., Hüllermeier, E., Dembczynski, K.J.: Bayes optimal multilabel classification via probabilistic classifier chains. In: Proceedings of the 27th International Conference on Machine Learning (ICML 2010), pp. 279-286 (2010)
Cisse, M.M., Usunier, N., Artières, T., Gallinari, P.: Robust bloom filters for large multilabel classification tasks. In: Burges, C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K. (eds.) Advances in Neural Information Processing Systems 26, pp. 1851-1859 (2013)
Dekel, O., Shamir, O.: Multiclass-multilabel classification with more classes than examples. In: International Conference on Artificial Intelligence and Statistics, pp. 137-144 (2010)
Faulon, J.L., Misra, M., Martin, S., Sale, K., Sapra, R.: Genome scale enzyme- metabolite and drug-target interaction predictions using the signature molecular descriptor. Bioinformatics 24(2), 225-233 (2008)
Geurts, P., Ernst, D., Wehenkel, L.: Extremely randomized trees. Machine Learning 63(1), 3-42 (2006)
Geurts, P., Wehenkel, L., d'Alché Buc, F.: Kernelizing the output of tree-based methods. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 345-352. ACM (2006)
Hsu, D., Kakade, S., Langford, J., Zhang, T.: Multi-label prediction via compressed sensing. In: Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C.K.I., Culotta, A. (eds.) Advances in Neural Information Processing Systems 22, pp. 772-780 (2009)
Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics 26(189-206), 1 (1984)
Kocev, D., Vens, C., Struyf, J., Dzeroski, S.: Tree ensembles for predicting structured outputs. Pattern Recognition 46(3), 817-833 (2013)
Li, P., Hastie, T.J., Church, K.W.: Very sparse random projections. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 287-296. ACM (2006)
Madjarov, G., Kocev, D., Gjorgjevikj, D., Dzeroski, S.: An extensive experimental comparison of methods for multi-label learning. Pattern Recognition 45(9), 3084-3104 (2012)
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al.: Scikit-learn: Machine learning in python. The Journal of Machine Learning Research 12, 2825-2830 (2011)
Read, J., Pfahringer, B., Holmes, G., Frank, E.: Classifier chains for multi-label classification. In: Buntine, W., Grobelnik, M., Mladenić, D., Shawe-Taylor, J. (eds.) ECML PKDD 2009, Part II. LNCS (LNAI), vol. 5782, pp. 254-269. Springer, Heidelberg (2009)
Tsoumakas, G., Katakis, I., Vlahavas, I.: Effective and efficient multilabel classification in domains with large number of labels. In: Proc. ECML/PKDD 2008 Workshop on Mining Multidimensional Data (MMD 2008), pp. 30-44 (2008)
Tsoumakas, G., Katakis, I., Vlahavas, I.P.: Random k-labelsets for multilabel classification. IEEE Trans. Knowl. Data Eng. 23(7), 1079-1089 (2011)
Tsoumakas, G., Vlahavas, I.P.: Random k-labelsets: An ensemble method for multilabel classification. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladenič, D., Skowron, A. (eds.) ECML 2007. LNCS (LNAI), vol. 4701, pp. 406-417. Springer, Heidelberg (2007)
Zhou, T., Tao, D.: Multi-label subspace ensemble. In: International Conference on Artificial Intelligence and Statistics, pp. 1444-1452 (2012)