Chunking with Max-Margin Markov Networks

Chunking with Max-Margin Markov Networks* Tang Buzhou, Wang Xuan , and Wang Xiaolong Department of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, Shenzhen, 518055,China {tangbuzhou5125@gmail.com, wangxuan@insun.hit.edu.cn, xiaolongwang@insun.hit.edu.cn} Abstract. In this paper, we apply Max-Margin Markov Networks (M3Ns) to English base phrases chunking, which is a large margin approach combining both the advantages of graphical models(such as Conditional Random Fields, CRFs) and kernel-based approaches (such as Support Vector Machines, SVMs) to solve the problems of multi-label multi-class supervised classification. To show the efficiency of M3Ns, we compare it with CRFs and other relative systems on the data set of CoNLL-2000 comprehensively. The experiment results show that M3Ns achieves state-of-the-art performance with strong generalization ability, which is better than CRFs. Keywords: max-margin markov networks; graphical models; conditional random fields; support vector machines; generalization ability 1. Introduction Text chunking is an intermediate step towards full parsing, which consists of dividing a text in syntactically correlated parts of words. Tasks of chunking are extracting the non-overlapping segments from a stream of data and identifying them with non-recursive cores of various types of phrases. It can be solved as sequential labeling. Many probabilistic graphical models such as Hidden Markov Models (HMMs) (Zhou et al.,2000; Sang and Buchholz, 2000), Maximum Entropy Models (MEs) (Koeling, 2000), Conditional Random Fields (CRFs) (Lafferty et al., 2001), Semi-Markov Random Fields (Collins, 2002a) have been applied to chunking for their abilities to deal with structured data by taking advantages of the potential of interactions in a factored way (Jordan al., 1998). However, the condition of the probabilistic infinite samples assumption cannot be satisfied in practice and over fitting problem cannot be avoided. On the other hand, the tasks of chunking can be recognized as a classifying problem, statistic machine learning techniques are also often applied to chunking and various machine learning approaches have been proposed for chunking such as SVMs (Cortes and Vapnik, 1995; Vapnik, 1999) and Boosting (Freund and Schapire, 1996). Compared with probabilistic graphical models, statistic machine learning approaches have no flaw of infinite samples assumption and have strong generalization guarantees theoretically, but they assume that the classification of each object (word or phrase) is independent and ignore some precious correlation information in structured data. * This research has been partially supported by the National Natural Science Foundation of China (No.60435020 and No.90612005) and the Goal-oriented Lessons from the National 863 Program of China (No.2006AA01Z197). Copyright 2008 by Tang Buzhou, Wang Xuan, and Wang Xiaolong 474 22nd Pacific Asia Conference on Language, Information and Computation, pages 474–480 M3Ns is a new framework combining SVMs with graphical models. It is a SVM-like approach that could also deal with structured data efficiently like graphical models do (Taskar, 2003). In practice, M3Ns can not only make use of correlations in structured data, including sequential data, like CRFs, but also efficiently deal with high-dimensional features with high generalization performance like SVMs. In this paper, we apply M3Ns to the CoNLL-2000 text chunking shared task using distinct chunk representations. In …

Content truncated to 500 words