A Submodular Feature-Aware Framework for Label Subset Selection in Extreme Classification Problems

Elham J. Barezi, Ian D. Wood, Pascale Fung, Hamid R. Rabiee


Abstract
Extreme classification is a classification task on an extremely large number of labels (tags). User generated labels for any type of online data can be sparing per individual user but intractably large among all users. It would be useful to automatically select a smaller, standard set of labels to represent the whole label set. We can then solve efficiently the problem of multi-label learning with an intractably large number of interdependent labels, such as automatic tagging of Wikipedia pages. We propose a submodular maximization framework with linear cost to find informative labels which are most relevant to other labels yet least redundant with each other. A simple prediction model can then be trained on this label subset. Our framework includes both label-label and label-feature dependencies, which aims to find the labels with the most representation and prediction ability. In addition, to avoid information loss, we extract and predict outlier labels with weak dependency on other labels. We apply our model to four standard natural language data sets including Bibsonomy entries with users assigned tags, web pages with user assigned tags, legal texts with EUROVOC descriptors(A topic hierarchy with almost 4000 categories regarding different aspects of European law) and Wikipedia pages with tags from social bookmarking as well as news videos for automated label detection from a lexicon of semantic concepts. Experimental results show that our proposed approach improves label prediction quality, in terms of precision and nDCG, by 3% to 5% in three of the 5 tasks and is competitive in the others, even with a simple linear prediction model. An ablation study shows how different data sets benefit from different aspects of our model, with all aspects contributing substantially to at least one data set.
Anthology ID:
N19-1106
Volume:
Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)
Month:
June
Year:
2019
Address:
Minneapolis, Minnesota
Editors:
Jill Burstein, Christy Doran, Thamar Solorio
Venue:
NAACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
1009–1018
Language:
URL:
https://aclanthology.org/N19-1106
DOI:
10.18653/v1/N19-1106
Bibkey:
Cite (ACL):
Elham J. Barezi, Ian D. Wood, Pascale Fung, and Hamid R. Rabiee. 2019. A Submodular Feature-Aware Framework for Label Subset Selection in Extreme Classification Problems. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 1009–1018, Minneapolis, Minnesota. Association for Computational Linguistics.
Cite (Informal):
A Submodular Feature-Aware Framework for Label Subset Selection in Extreme Classification Problems (Barezi et al., NAACL 2019)
Copy Citation:
PDF:
https://aclanthology.org/N19-1106.pdf
Supplementary:
 N19-1106.Supplementary.pdf
Video:
 https://vimeo.com/360593989