A Boosting-based Algorithm for Classification of Semi-Structured Text using the Frequency of Substructures

Proceedings of Recent Advances in Natural Language Processing, pages 319–326, Hissar, Bulgaria, 7-13 September 2013. A Boosting-based Algorithm for Classification of Semi-Structured Text using Frequency of Substructures Tomoya Iwakura Fujitsu Laboratories Ltd iwakura.tomoya@jp.fujitsu.com Abstract Research in text classification currently fo- cuses on challenging tasks such as sen- timent classification, modality identifica- tion, and so on. In these tasks, approaches that use a structural representation, like a tree, have shown better performance rather than a bag-of-words representation. In this paper, we propose a boosting algorithm for classifying a text that is a set of sentences represented by tree. The algorithm learns rules represented by subtrees with their frequency information. Existing boosting- based algorithms use subtrees as features without considering their frequency be- cause the existing algorithms targeted a sentence rather than a text. In contrast, our algorithm learns how the occurrence frequency of each subtree is important for classification. Experiments on topic iden- tification of Japanese news articles and En- glish sentiment classification shows the ef- fectiveness of subtree features with their frequency. 1 Introduction Text classification is used to classify texts such as news articles, E-mails, social media posts, and so on. A number of machine learning algorithms have been applied to text classification success- fully. Text classification handles not only tasks to identify topics, such as politics, finance, sports or entertainment, but also challenging tasks such as categorization of customer E-mails and reviews by types of claims, subjectivity or sentiment (Wiebe, 2000; Banea et al., 2010; Bandyopadhyay and Okumura, 2011). To identify difficult categories on challenging tasks, a traditional bag-of-words representation may not be sufficient. Therefore, a richer, structural representation is used rather than the traditional bag-of-words. A straightfor- ward way to extend the traditional bag-of-words representation is to heuristically add new types of features such as fixed-length n-grams such as word bi-gram or tri-gram, or fixed-length syntac- tic relations. Instead of such approaches, learn- ing algorithms that handle semi-structured data have become increasingly popular (Kudo and Mat- sumoto, 2004; Kudo et al., 2005; Ifrim et al., 2008; Okanohara and Tsujii, 2009). This is due to the fact that these algorithms can learn better substructures for each task from semi-structured texts annotated with parts-of-speech, base-phrase information or syntactic relations. Among such learning algorithms, boosting- based algorithms have the following advantages: Boosting-based learning algorithms have been ap- plied to Natural Language Processing problems successfully, including text classification (Kudo and Matsumoto, 2004), English syntactic chunk- ing (Kudo et al., 2005), zero-anaphora resolution (Iida et al., 2006), and so on. Furthermore, clas- sifiers trained with boosting-based learners have shown faster classification speed (Kudo and Mat- sumoto, 2004) than Support Vector Machines with a tree kernel (Collins and Duffy, 2002). However, existing boosting-based algorithms for semi-structured data, boosting algorithms for classification (Kudo and Matsumoto, 2004) and for ranking (Kudo et al., 2005), have the follow- ing point that can be improved. The weak learn- ers used in these algorithms learn classifiers which do not consider frequency of substructures. This is because these algorithms …

Content truncated to 500 words