S-MART: Novel Tree-based Structured Learning Algorithms Applied to Tweet Entity Linking

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 504–513, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics S-MART: Novel Tree-based Structured Learning Algorithms Applied to Tweet Entity Linking Yi Yang School of Interactive Computing Georgia Institute of Technology yiyang@gatech.edu Ming-Wei Chang Microsoft Research minchang@microsoft.com Abstract Non-linear models recently receive a lot of attention as people are starting to dis- cover the power of statistical and em- bedding features. However, tree-based models are seldom studied in the con- text of structured learning despite their re- cent success on various classification and ranking tasks. In this paper, we propose S-MART, a tree-based structured learning framework based on multiple additive re- gression trees. S-MART is especially suit- able for handling tasks with dense fea- tures, and can be used to learn many dif- ferent structures under various loss func- tions. We apply S-MART to the task of tweet entity linking — a core component of tweet information extraction, which aims to identify and link name mentions to en- tities in a knowledge base. A novel infer- ence algorithm is proposed to handle the special structure of the task. The exper- imental results show that S-MART signif- icantly outperforms state-of-the-art tweet entity linking systems. 1 Introduction Many natural language processing (NLP) prob- lems can be formalized as structured prediction tasks. Standard algorithms for structured learning include Conditional Random Field (CRF) (Laf- ferty et al., 2001) and Structured Supported Vec- tor Machine (SSVM) (Tsochantaridis et al., 2004). These algorithms, usually equipped with a linear model and sparse lexical features, achieve state- of-the-art performances in many NLP applica- tions such as part-of-speech tagging, named entity recognition and dependency parsing. This classical combination of linear models and sparse features is challenged by the recent emerg- ing usage of dense features such as statistical and embedding features. Tasks with these low dimen- sional dense features require models to be more sophisticated to capture the relationships between features. Therefore, non-linear models start to re- ceive more attention as they are often more expres- sive than linear models. Tree-based models such as boosted trees (Fried- man, 2001) are flexible non-linear models. They can handle categorical features and count data bet- ter than other non-linear models like Neural Net- works. Unfortunately, to the best of our knowl- edge, little work has utilized tree-based methods for structured prediction, with the exception of TreeCRF (Dietterich et al., 2004). In this paper, we propose a novel structured learning framework called S-MART (Structured Multiple Additive Regression Trees). Unlike TreeCRF, S-MART is very versatile, as it can be applied to tasks beyond sequence tagging and can be trained under various objective functions. S- MART is also powerful, as the high order relation- ships between features can be captured by non- linear regression trees. We further demonstrate how S-MART can be applied to tweet entity linking, an important and challenging task underlying many applications in- cluding product feedback (Asur and …

Content truncated to 500 words