Global Model for Hierarchical Multi-Label Text Classification

International Joint Conference on Natural Language Processing, pages 46–54, Nagoya, Japan, 14-18 October 2013. Global Model for Hierarchical Multi-Label Text Classification Yugo Murawaki Graduate School of Informatics Kyoto University murawaki@i.kyoto-u.ac.jp Abstract The main challenge in hierarchical multi- label text classification is how to leverage hierarchically organized labels. In this pa- per, we propose to exploit dependencies among multiple labels to be output, which has been left unused in previous studies. To do this, we first formalize this task as a structured prediction problem and propose (1) a global model that jointly outputs mul- tiple labels and (2) a decoding algorithm for it that finds an exact solution with dy- namic programming. We then introduce features that capture inter-label dependen- cies. Experiments show that these features improve performance while reducing the model size. 1 Introduction Hierarchical organization of a large collection of data has deep roots in human history (Berlin, 1992). The emergence of electronically-available text has enabled us to take computational ap- proaches to real-world hierarchical text classifica- tion tasks. Such text collections include patents,1 medical taxonomies2 and Web directories such as Yahoo! and the Open Directory Project.3 In this paper, we focus on multi-label classification, in which a document may be given more than one label. Hierarchical multi-label text classification is a challenging task because it typically involves thousands of labels and an exponential number of output candidates. For efficiency, divide-and- conquer strategies have often been adopted. Typi- cally, the label hierarchy is mapped to a set of local en/1http://www.wipo.int/classifications/ 2http://www.nlm.nih.gov/mesh/ 3http://www.dmoz.org/ classifiers, which are invoked in a top-down fash- ion (Montejo-R´aez and Ure˜na-L´opez, 2006; Wang et al., 2011; Sasaki and Weissenbacher, 2012). However, local search is difficult to harness be- cause a chain of local decisions often leads to what is usually called error propagation (Bennett and Nguyen, 2009). To alleviate this problem, previ- ous work has resorted to what we collectively call post-training adjustment. One characteristic of the task that has not been explored in previous studies is that multiple labels to be output have dependencies among them. It is difficult even for human annotators to decide how many labels they choose. We conjecture that they consult the label hierarchy when adjusting the number of output labels. For example, if two la- bel candidates are positioned proximally in the hi- erarchy, human annotators may drop one of them because they provide overlapping information. In this paper, we propose to exploit inter-label dependencies. To do this, we first formulate hier- archical multi-label text classification as a struc- tured prediction problem. We propose a global model that jointly predicts a set of labels. Un- der this framework, we replace local search with dynamic programming to find an exact solution. This allows us to extend the model with features for inter-label dependencies. Instead of locally training a set of classifiers, we also propose global training to find globally optimal parameters. Ex- periments show that these features improve perfor- mance while reducing the model size. 2 Task Definition In hierarchical multi-label …

Content truncated to 500 words