Label Filters for Large Scale Multilabel Classification

Alexandru Niculescu-Mizil, Ehsan Abbasnejad
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1448-1457, 2017.

Abstract

When assigning labels to a test instance, most multilabel and multiclass classifiers systematically evaluate every single label to decide whether it is relevant or not. This linear scan over labels becomes prohibitive when the number of labels is very large. To alleviate this problem we propose a two step approach where computationally efficient label filters pre-select a small set of candidate labels before the base multiclass or multilabel classifier is applied. The label filters select candidate labels by projecting a test instance on a filtering line, and retaining only the labels that have training instances in the vicinity of this projection. The filter parameters are learned directly from data by solving a constraint optimization problem, and are independent of the base multilabel classifier. The proposed label filters can be used in conjunction with any multiclass or multilabel classifier that requires a linear scan over the labels, and speed up prediction by orders of magnitude without significant impact on performance.

Cite this Paper


BibTeX
@InProceedings{pmlr-v54-niculescu-mizil17a, title = {{Label Filters for Large Scale Multilabel Classification}}, author = {Niculescu-Mizil, Alexandru and Abbasnejad, Ehsan}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1448--1457}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/niculescu-mizil17a/niculescu-mizil17a.pdf}, url = {https://proceedings.mlr.press/v54/niculescu-mizil17a.html}, abstract = {When assigning labels to a test instance, most multilabel and multiclass classifiers systematically evaluate every single label to decide whether it is relevant or not. This linear scan over labels becomes prohibitive when the number of labels is very large. To alleviate this problem we propose a two step approach where computationally efficient label filters pre-select a small set of candidate labels before the base multiclass or multilabel classifier is applied. The label filters select candidate labels by projecting a test instance on a filtering line, and retaining only the labels that have training instances in the vicinity of this projection. The filter parameters are learned directly from data by solving a constraint optimization problem, and are independent of the base multilabel classifier. The proposed label filters can be used in conjunction with any multiclass or multilabel classifier that requires a linear scan over the labels, and speed up prediction by orders of magnitude without significant impact on performance.} }
Endnote
%0 Conference Paper %T Label Filters for Large Scale Multilabel Classification %A Alexandru Niculescu-Mizil %A Ehsan Abbasnejad %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-niculescu-mizil17a %I PMLR %P 1448--1457 %U https://proceedings.mlr.press/v54/niculescu-mizil17a.html %V 54 %X When assigning labels to a test instance, most multilabel and multiclass classifiers systematically evaluate every single label to decide whether it is relevant or not. This linear scan over labels becomes prohibitive when the number of labels is very large. To alleviate this problem we propose a two step approach where computationally efficient label filters pre-select a small set of candidate labels before the base multiclass or multilabel classifier is applied. The label filters select candidate labels by projecting a test instance on a filtering line, and retaining only the labels that have training instances in the vicinity of this projection. The filter parameters are learned directly from data by solving a constraint optimization problem, and are independent of the base multilabel classifier. The proposed label filters can be used in conjunction with any multiclass or multilabel classifier that requires a linear scan over the labels, and speed up prediction by orders of magnitude without significant impact on performance.
APA
Niculescu-Mizil, A. & Abbasnejad, E.. (2017). Label Filters for Large Scale Multilabel Classification. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1448-1457 Available from https://proceedings.mlr.press/v54/niculescu-mizil17a.html.

Related Material