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

Proceedings of NAACL-HLT 2019, pages 1009–1018 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 1009 A Submodular Feature-Aware Framework for Label Subset Selection in Extreme Classification Problems Elham J. Barezi1,2,3, Ian D. Wood 1, Pascale Fung 1,2,4, Hamid R. Rabiee 3 1Center for Artificial Intelligence Research (CAiRE) 2Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong 3Department of Computer Engineering, Sharif University of Technology, Tehran, Iran 4EMOS Technologies Inc. HK Limited ejs@cse.ust.hk, pascale@ust.hk, rabiee@sharif.edu 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 in- tractably large among all users. It would be useful to automatically select a smaller, stan- dard set of labels to represent the whole label set. We can then solve efficiently the prob- lem of multi-label learning with an intractably large number of interdependent labels, such as automatic tagging of Wikipedia pages. We propose a submodular maximization frame- work with linear cost to find informative la- bels which are most relevant to other labels yet least redundant with each other. A simple pre- diction 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 repre- sentation and prediction ability. In addition, to avoid information loss, we extract and pre- dict 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 differ- ent aspects of European law) and Wikipedia pages with tags from social bookmarking as well as news videos for automated label de- tection 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 substan- tially to at least one data set. 1 Introduction Multi-label learning has recently attracted atten- tion in the research community due to an increase in applications such as semantic labeling of im- ages and videos, bio-informatics, genetic func- tions, and music categorization. In addition, multi- label learning can address machine learning prob- lems in web data mining, including recommender systems, multimedia sharing websites, and rank- ing (Zhang and Zhang, 2010). An important application of extreme multi-label learning is automatic tagging and social tagging of large information collections such as Wikipedia or the Web. A user can add their own keywords to a text, as if they were the keywords they would use to look for the article in a …

Content truncated to 500 words