emnlp emnlp2010 emnlp2010-69 knowledge-graph by maker-knowledge-mining

69 emnlp-2010-Joint Training and Decoding Using Virtual Nodes for Cascaded Segmentation and Tagging Tasks

Source: pdf

Author: Xian Qian ; Qi Zhang ; Yaqian Zhou ; Xuanjing Huang ; Lide Wu

Abstract: Many sequence labeling tasks in NLP require solving a cascade of segmentation and tagging subtasks, such as Chinese POS tagging, named entity recognition, and so on. Traditional pipeline approaches usually suffer from error propagation. Joint training/decoding in the cross-product state space could cause too many parameters and high inference complexity. In this paper, we present a novel method which integrates graph structures of two subtasks into one using virtual nodes, and performs joint training and decoding in the factorized state space. Experimental evaluations on CoNLL 2000 shallow parsing data set and Fourth SIGHAN Bakeoff CTB POS tagging data set demonstrate the superiority of our method over cross-product, pipeline and candidate reranking approaches.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 cn Abstract Many sequence labeling tasks in NLP require solving a cascade of segmentation and tagging subtasks, such as Chinese POS tagging, named entity recognition, and so on. [sent-5, score-0.768]

2 In this paper, we present a novel method which integrates graph structures of two subtasks into one using virtual nodes, and performs joint training and decoding in the factorized state space. [sent-8, score-0.571]

3 Experimental evaluations on CoNLL 2000 shallow parsing data set and Fourth SIGHAN Bakeoff CTB POS tagging data set demonstrate the superiority of our method over cross-product, pipeline and candidate reranking approaches. [sent-9, score-0.786]

4 1 Introduction There is a typical class of sequence labeling tasks in many natural language processing (NLP) applications, which require solving a cascade of segmentation and tagging subtasks. [sent-10, score-0.733]

5 For example, many Asian languages such as Japanese and Chinese which do not contain explicitly marked word boundaries, word segmentation is the preliminary step for solving part-of-speech (POS) tagging problem. [sent-11, score-0.588]

6 The most commonly approach solves cascaded subtasks in a pipeline, which is very simple to implement and allows for a modular approach. [sent-14, score-0.227]

7 To cope with this problem, Shi and Wang (2007) proposed a reranking framework in which N-best segment candidates generated in the first stage are passed to the tag- ging model, and the final output is the one with the highest overall segmentation and tagging probability score. [sent-16, score-0.756]

8 The main drawback of this method is that the interaction between tagging and segmentation is restricted by the number of candidate segmentation outputs. [sent-17, score-0.971]

9 Bunescu (2008) presented an improved pipeline model in which upstream subtask outputs are regarded as hidden variables, together with their probabilities are used as probabilistic features in the downstream subtasks. [sent-19, score-0.21]

10 Another disadvantage of these two methods is that they employ separate training and the segmentation model could not take advantages of tagging information in the training procedure. [sent-21, score-0.588]

11 On the other hand, joint learning and decoding using cross-product of segmentation states and tagging states does not suffer from error propagation problem and achieves higher accuracy on both subtasks (Ng and Low, 2004). [sent-22, score-0.962]

12 Sutton (2004) proposed Dynamic Conditional Random Fields (DCRFs) to perform joint training/decoding of subtasks using much fewer parameters than the cross-product approach. [sent-24, score-0.165]

13 tc ho2d0s10 in A Nsastoucira tlio Lnan fogru Cagoem Ppruotcaetisosninagl, L pinag eusis 1t8ic7s–195, ever, DCRFs do not guarantee non-violation ofhardconstraints that nodes within the same segment get a single consistent tagging label. [sent-27, score-0.412]

14 Recently, perceptron based learning framework has been well studied for incorporating node level and segment level features together (Kazama and Torisawa, 2007; Zhang and Clark, 2008). [sent-29, score-0.133]

15 The main shortcoming is that exact inference is intractable for those dynamically generated segment level features, so candidate based searching algorithm is used for approximation. [sent-30, score-0.147]

16 On the other hand, Jiang (2008) proposed a cascaded linear model which has a two layer structure, the inside-layer model uses node level features to generate candidates with their weights as inputs of the outside layer model which captures non-local features. [sent-31, score-0.162]

17 As pipeline models, error propagation problem exists for such method. [sent-32, score-0.251]

18 In this paper, we present a novel graph structure that exploits joint training and decoding in the factorized state space. [sent-33, score-0.347]

19 Our method does not suffer from error propagation, and guards against violations of those hard-constraints imposed by segmentation subtask. [sent-34, score-0.436]

20 The motivation is to integrate two Markov chains for segmentation and tagging subtasks into a single chain, which contains two types of nodes, then standard dynamic programming based exact inference is employed on the hybrid structure. [sent-35, score-0.957]

21 Experiments are conducted on two different tasks, CoNLL 2000 shallow parsing and SIGHAN 2008 Chinese word segmentation and POS tagging. [sent-36, score-0.445]

22 Evaluation results of shallow parsing task show the superiority of our proposed method over traditional joint training/decoding approach using crossproduct state space, and achieves the best reported results when no additional resources at hand. [sent-37, score-0.399]

23 For Chinese word segmentation and POS tagging task, a strong baseline pipeline model is built, experimental results show that the proposed method yields a more substantial improvement over the baseline than candidate reranking approach. [sent-38, score-0.962]

24 xl denote the observed sequence, where xi is the ith node in the sequence, lis sequence length, y = y1y2 . [sent-48, score-0.163]

25 yl is a label sequence over x that we wish to predict. [sent-51, score-0.168]

26 For sequence labeling task, linear chain CRFs are very popular, in which a first order Markov assumption is made on the labels: p(y|x) =Z(1x)Yiφ(x,y,i) ,where ‡wTf(x, Z(x) = XyYiφ(x,y,i) φ(x, y, i) = exp yi−1, yi, i)· f(x, yi−1 , yi , i) = [f1(x, yi−1, yi, i), . [sent-54, score-0.353]

27 ,fm(x, yi−1, yi, i)]T, each element fj (x, yi−1 , yi, i) is a real valued feature function, here we simplify the notation of state feature by writing fj (x, yi, i) = fj (x, yi−1 , yi, i), m is the cardinality of feature set {fj}. [sent-57, score-0.449]

28 In the traditional joint training/decoding approach for cascaded segmentation and tagging task, each label yi has the form si-ti, which consists of segmentation label si and tagging label ti. [sent-64, score-2.13]

29 To facilitate our discussion, in later sections we will use BIES label set, where B,I,E represents Beginning, Inside and End of a multi-node segment respectively, S denotes a single node segment. [sent-70, score-0.267]

30 Graphical representation of linear chain CRFs is shown in Figure 1, where tagging label “P” is the simplification of “PER”. [sent-76, score-0.448]

31 For nodes that are labeled as other, we define si =S, ti =O. [sent-77, score-0.57]

32 2 Hybrid structure for cascaded labeling tasks Different from traditional joint approach, our method integrates two linear markov chains for segmentation and tagging subtasks into one that contains two types of nodes. [sent-79, score-1.06]

33 Specifically, we first regard segmentation and tagging as two independent sequence labeling tasks, corresponding chain structures are built, as shown in the top and middle sub-figures of Figure 2. [sent-80, score-0.778]

34 Then a chain of twice length of the observed sequence is built, where nodes x1, . [sent-81, score-0.219]

35 , xl on the even positions are original observed nodes, while nodes v1, . [sent-84, score-0.12]

36 , vl on the odd positions are virtual nodes that have no content information. [sent-87, score-0.18]

37 For original nodes xi, the state space is the tagging label set, while for virtual nodes, their states are segmentation labels. [sent-88, score-1.015]

38 The label sequence of the hybrid chain is y = y1 . [sent-89, score-0.478]

39 sltl, where combination of consecutive labels siti represents the full label for node xi. [sent-95, score-0.151]

40 Then we let si be connected with si−1 and si+1 , so that first order Markov assumption is made on segmentation states. [sent-96, score-0.539]

41 Then neighboring tagging and segmentation states are connected as shown in the bottom sub-figure of Figure 2. [sent-98, score-0.624]

42 Non-violation of hard-constraints that nodes within the same segment get a single consistent tagging label is guaranteed by introducing second order transition features f(ti−1 , si, ti, i) that are true if ti−1 ti and si ∈ {I,E}. [sent-99, score-1.005]

43 For example, fj (ti−1 , si, ti, i) tis de- = 189 fined as true if ti−1 =PER, si =I and ti =LOC. [sent-100, score-0.582]

44 In other words, it is true, if a segment is partially tagging as PER, and partially tagged as LOC. [sent-101, score-0.323]

45 Since such features are always false in the training corpus, their corresponding weights will be very low so that inconsistent label assignments impossibly appear in decoding procedure. [sent-102, score-0.172]

46 The hybrid graph structure can be regarded as a special case of second order Markov chain. [sent-103, score-0.267]

47 3 Factorized features Compared with traditional joint model that exploits cross-product state space, our hybrid structure uses factorized states, hence could handle more flexible features. [sent-105, score-0.55]

48 Any state feature g(x, yi, i) defined in the cross-product state space can be replaced by a first order transition feature in the factorized space: f(x, si, ti, i). [sent-106, score-0.348]

49 Features in cross-product state space require that segmentation label and tagging label take on particular values simultaneously, however, sometimes we want to specify requirement on only segmentation or tagging label. [sent-108, score-1.499]

50 In such case, our observation is that “Smith” is likely a (part of) person name, we do not care about its segmentation label. [sent-113, score-0.354]

51 So we could define state feature f(x, ti, i) = true, if xi is “Smith” with tagging label ti=PER. [sent-114, score-0.466]

52 Further more, we could define features like f(x, ti−1 , ti, i), f(x, si−1 , si, i), f(x, ti−1 , si , i), etc. [sent-115, score-0.213]

53 The hybrid structure facilitates us to use varieties of features. [sent-116, score-0.236]

54 In decoding stage, we use second order Viterbi algorithm to find the best label sequence. [sent-124, score-0.172]

55 The Viterbi decoding can be 190 Table 1: Time Complexity CrRoMPseHirpay-bPenthlkriond eguct(|S 2(T+|cSsraT|+in)|TiSn2|cg LTct|)L(S|D(2+|Se c+|To )dT|Si2nU|)gNTU used to label a new sequence, and marginal computation is used for parameter estimation. [sent-125, score-0.201]

56 3 Complexity Analysis The time complexity of the hybrid CRFs training and decoding procedures is higher than that of pipeline methods, but lower than traditional crossproduct methods. [sent-126, score-0.629]

57 Let • |S| = size of the segmentation label set. [sent-127, score-0.438]

58 N = number of candidates in candidate reranking approach. [sent-134, score-0.164]

59 Time requirements for pipeline, cross-product, candidate reranking and hybrid CRFs are summarized in Table 1. [sent-135, score-0.4]

60 ld be very large, we assume tSh|at i |T| >> |S|, so f boer evaerchy iteration, hybrid mCeRF thsa aist |aTbo|ut > |S| ti |mSe|s, s sloow feorr tehaacnh pipeline ,a hndyb |S| CtimRFess fiassatebro tuhta|nS cross-product + Table 2: Feature templates for shallow parsing task method. [sent-138, score-0.992]

61 When decoding, candidate reranking approach requires more time if candidate number N > |S|. [sent-139, score-0.221]

62 Though the space complexity could not be compared directly among some of these methods, hybrid CRFs require less parameters than cross-product CRFs due to the factorized state space. [sent-140, score-0.465]

63 This is similar with factorized CRFs (FCRFs) (Sutton et al. [sent-141, score-0.13]

64 1 Shallow Parsing Our first experiment is the shallow parsing task. [sent-144, score-0.119]

65 and other (O), the segmentation state space we used is BIES label set, since we find that it yields a little improvement over BIO set. [sent-149, score-0.537]

66 191 We compare our approach with traditional crossproduct method. [sent-151, score-0.123]

67 After selecting feature templates by cross validation, we extract features and learn their weights on the whole training data set. [sent-154, score-0.186]

68 Feature templates are summarized in Table 2, where wi denotes the ith word, pi denotes the ith POS tag. [sent-155, score-0.586]

69 Notice that in the second row, feature templates of the hybrid CRFs does not contain wi−2si, wi+2si, since we find that these two templates degrade performance in cross validation. [sent-156, score-0.581]

70 However, wi−2ti, wi+2ti are useful, which implies that the proper context window size for segmentation is smaller than tagging. [sent-157, score-0.326]

71 Similarly, for hybrid CRFs, the window size of POS bigram features for segmentation is 5 (from pi−2 to pi+2, see the eighth row in the second column); while for tagging, the size is 7 (from pi−3 to pi+3, see the ninth row in the second column). [sent-158, score-0.562]

72 For traditional cross-product CRFs and our hybrid CRFs, we use fixed gaussian prior σ = 1. [sent-160, score-0.294]

73 0 for both methods, we find that this parameter does not signifiTable 3: Results for shallow parsing task, Hybrid CRFs significantly outperform Cross-Product CRFs (McNemar’s test; p < 0. [sent-161, score-0.119]

74 2 Chinese word segmentation and POS tagging Our second experiment is the Chinese word segmentation and POS tagging task. [sent-175, score-1.176]

75 We compare our hybrid CRFs with pipeline and candidate reranking methods (Shi and Wang, 2007) 192 Table 4: Comparison with other systems on shallow parsing task using the same evaluation metrics as shallow parsing. [sent-181, score-0.814]

76 For pipeline method, we built our word segmenter based on the work of Huang and Zhao (2007), which uses 6 label representation, 7 feature templates (listed in Table 5, where ci denotes the ith Chinese character in the sentence) and CRFs for parameter learning. [sent-183, score-0.83]

77 Our POS tagging system is based on linear chain CRFs. [sent-188, score-0.336]

78 Since SIGHAN dose not provide development data, we use the 10 fold cross validation described in the previous experiment to turning feature templates and Gaussian prior. [sent-189, score-0.213]

79 Feature templates are listed in Table 5, where wi denotes the ith word in Table 5: Feature templates for Chinese word segmentation and POS tagging task Segmentation feature templates (1. [sent-190, score-1.419]

80 6) ti−1ti i−1 Joint segmentation and POS tagging feature templates (3. [sent-199, score-0.774]

81 7) si−1ti−1si, ti−1siti i−1i−1i−1 Table 6: Word segmentation results on Fourth SIGHAN Bakeoff CTB corpus 2143R/a2n6k9F15. [sent-206, score-0.326]

82 20u4189racyto PDefOmfisc Sia rtilapgtsbheigocesrnotdinpelinsy- 193 the sentence, cj (wi) ,j > 0 denotes the jth Chinese character of word wi, cj (wi) ,j < 0 denotes the jth last Chinese character, l(wi) denotes the word length of wi. [sent-208, score-0.195]

83 For reranking method, we varied candidate numbers n among n ∈ {10, 20, 50, 100}. [sent-212, score-0.164]

84 For hybrid CRFs, we use nthe ∈ same segmentation la Fboerl syebt as the segmentor in pipeline. [sent-213, score-0.599]

85 The gain of hybrid CRFs over the baseline pipeline model is 0. [sent-216, score-0.446]

86 Notice that, such comparison is indirect due to different data sets and re- candidate number Figure 3: Results for Chinese word segmentation and POS tagging task, Hybrid CRFs significantly outperform 100-Best Reranking (McNemar’s test; p < 0. [sent-221, score-0.645]

87 01) Table 8: Comparison of word segmentation and POS tagging, such comparison is indirect due to different data sets and resources. [sent-222, score-0.326]

88 One common conclusion is that joint models generally outperform pipeline models. [sent-235, score-0.271]

89 5 Conclusion We introduced a framework to integrate graph structures for segmentation and tagging subtasks into one using virtual nodes, and performs joint training and decoding in the factorized state space. [sent-236, score-1.13]

90 Our approach does not suffer from error propagation, and guards against violations of those hard-constraints imposed by segmentation subtask. [sent-237, score-0.436]

91 Experiments on shallow parsing and Chinese word segmentation tasks demonstrate our technique. [sent-238, score-0.445]

92 A cascaded linear model for joint chinese word segmentation and part-of-speech tagging. [sent-262, score-0.642]

93 The fourth international chinese language processing bakeoff: Chinese word segmentation, named entity recognition and chinese pos tagging. [sent-266, score-0.443]

94 A new perceptron algorithm for sequence labeling with nonlocal features. [sent-270, score-0.149]

95 Conditional random fields: Probabilistic models for segmenting and labeling sequence data. [sent-281, score-0.116]

96 A dual-layer crfs based joint decoding method for cascaded segmentation and labeling tasks. [sent-303, score-0.947]

97 Semi-supervised sequential labeling and segmentation using giga-word scale unlabeled data. [sent-314, score-0.386]

98 Semi-supervised structured output learning based on a hybrid generative and discriminative approach. [sent-318, score-0.236]

99 Joint word segmentation and pos tagging using a single perceptron. [sent-326, score-0.691]

100 Unsupervised segmentation helps supervised learning of character tagging forword segmentation and named entity recognition. [sent-338, score-0.979]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('segmentation', 0.326), ('crfs', 0.317), ('ti', 0.268), ('tagging', 0.262), ('hybrid', 0.236), ('si', 0.213), ('pipeline', 0.21), ('wi', 0.202), ('ci', 0.2), ('yi', 0.163), ('templates', 0.159), ('chinese', 0.132), ('factorized', 0.13), ('cascaded', 0.123), ('sighan', 0.123), ('label', 0.112), ('reranking', 0.107), ('subtasks', 0.104), ('pos', 0.103), ('fj', 0.101), ('ctb', 0.101), ('bakeoff', 0.101), ('virtual', 0.091), ('nodes', 0.089), ('cici', 0.087), ('dcrfs', 0.087), ('shallow', 0.085), ('chain', 0.074), ('crossproduct', 0.065), ('state', 0.065), ('shi', 0.065), ('joint', 0.061), ('segment', 0.061), ('decoding', 0.06), ('labeling', 0.06), ('traditional', 0.058), ('candidate', 0.057), ('sequence', 0.056), ('denotes', 0.055), ('name', 0.051), ('sutton', 0.05), ('shanghai', 0.046), ('chunking', 0.045), ('cisi', 0.043), ('citi', 0.043), ('etchingham', 0.043), ('funds', 0.043), ('girlfriend', 0.043), ('guards', 0.043), ('hendrix', 0.043), ('bies', 0.043), ('fourth', 0.041), ('pi', 0.041), ('propagation', 0.041), ('node', 0.039), ('huang', 0.038), ('kazama', 0.037), ('segmentor', 0.037), ('bio', 0.037), ('accessing', 0.037), ('jin', 0.037), ('ith', 0.037), ('fields', 0.037), ('markov', 0.037), ('states', 0.036), ('suffer', 0.036), ('zhang', 0.036), ('entity', 0.035), ('space', 0.034), ('parsing', 0.034), ('kathy', 0.034), ('subsequences', 0.034), ('jiang', 0.033), ('perceptron', 0.033), ('listed', 0.033), ('violations', 0.031), ('suzuki', 0.031), ('superiority', 0.031), ('xl', 0.031), ('mcnemar', 0.031), ('graph', 0.031), ('china', 0.031), ('smith', 0.03), ('character', 0.03), ('marginal', 0.029), ('dynamic', 0.029), ('cascade', 0.029), ('shortcoming', 0.029), ('hai', 0.029), ('hideki', 0.029), ('integrates', 0.029), ('nocedal', 0.029), ('person', 0.028), ('feature', 0.027), ('approximations', 0.027), ('fold', 0.027), ('folds', 0.027), ('clark', 0.027), ('zhao', 0.027), ('wang', 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999964 69 emnlp-2010-Joint Training and Decoding Using Virtual Nodes for Cascaded Segmentation and Tagging Tasks

Author: Xian Qian ; Qi Zhang ; Yaqian Zhou ; Xuanjing Huang ; Lide Wu

2 0.24406253 43 emnlp-2010-Enhancing Domain Portability of Chinese Segmentation Model Using Chi-Square Statistics and Bootstrapping

Author: Baobao Chang ; Dongxu Han

Abstract: Almost all Chinese language processing tasks involve word segmentation of the language input as their first steps, thus robust and reliable segmentation techniques are always required to make sure those tasks wellperformed. In recent years, machine learning and sequence labeling models such as Conditional Random Fields (CRFs) are often used in segmenting Chinese texts. Compared with traditional lexicon-driven models, machine learned models achieve higher F-measure scores. But machine learned models heavily depend on training materials. Although they can effectively process texts from the same domain as the training texts, they perform relatively poorly when texts from new domains are to be processed. In this paper, we propose to use χ2 statistics when training an SVM-HMM based segmentation model to im- prove its ability to recall OOV words and then use bootstrapping strategies to maintain its ability to recall IV words. Experiments show the approach proposed in this paper enhances the domain portability of the Chinese word segmentation model and prevents drastic decline in performance when processing texts across domains.

3 0.1938419 2 emnlp-2010-A Fast Decoder for Joint Word Segmentation and POS-Tagging Using a Single Discriminative Model

Author: Yue Zhang ; Stephen Clark

Abstract: We show that the standard beam-search algorithm can be used as an efficient decoder for the global linear model of Zhang and Clark (2008) for joint word segmentation and POS-tagging, achieving a significant speed improvement. Such decoding is enabled by: (1) separating full word features from partial word features so that feature templates can be instantiated incrementally, according to whether the current character is separated or appended; (2) deciding the POS-tag of a potential word when its first character is processed. Early-update is used with perceptron training so that the linear model gives a high score to a correct partial candidate as well as a full output. Effective scoring of partial structures allows the decoder to give high accuracy with a small beam-size of 16. In our 10-fold crossvalidation experiments with the Chinese Tree- . bank, our system performed over 10 times as fast as Zhang and Clark (2008) with little accuracy loss. The accuracy of our system on the standard CTB 5 test was competitive with the best in the literature. 1 Introduction and Motivation Several approaches have been proposed to solve word segmentation and POS-tagging jointly, including the reranking approach (Shi and Wang, 2007; Jiang et al., 2008b), the hybrid approach (Nakagawa and Uchimoto, 2007; Jiang et al., 2008a), and the single-model approach (Ng and Low, 2004; Zhang and Clark, 2008; Kruengkrai et al., 2009). These methods led to accuracy improvements over the traditional, pipelined segmentation and POS-tagging . . . 843 clark} @ cl cam ac uk baseline by avoiding segmentation error propagation and making use of part-of-speech information to improve segmentation. The single-model approach to joint segmentation and POS-tagging offers consistent training of all in- formation, concerning words, characters and partsof-speech. However, exact inference with dynamic programming can be infeasible if features are defined over a large enough range of the output, such as over a two-word history. In our previous work (Zhang and Clark, 2008), which we refer to as Z&C08; from now on, we used an approximate decoding algorithm that keeps track of a set of partially built structures for each character, which can be seen as a dynamic programming chart which is greatly reduced by pruning. In this paper we follow the line of single-model research, in particular the global linear model of Z&C08.; We show that effective decoding can be achieved with standard beam-search, which gives significant speed improvements compared to the decoding algorithm of Z&C08;, and achieves accuracies that are competitive with the state-of-the-art. Our research is also in line with recent research on improving the speed of NLP systems with little or no accuracy loss (Charniak et al., 2006; Roark and Hollingshead, 2008). Our speed improvement is achieved by the use of a single-beam decoder. Given an input sentence, candidate outputs are built incrementally, one character at a time. When each character is processed, it is combined with existing candidates in all possible ways to generate new candidates, and an agenda is used to keep the N-best candidate outputs from ProceMedITin,g Ms oasfs thaceh 2u0se1t0ts C,o UnSfAer,e n9c-e1 on O Ectmobpeir ic 2a0l1 M0.e ?tc ho2d0s10 in A Nsastoucira tlio Lnan fogru Cagoem Ppruotcaetisosninagl, L pinag eusis 8t4ic3s–852, the begining of the sentence to the current character. Compared to the multiple-beam search algorithm of Z&C08;, the use of a single beam can lead to an order of magnitude faster decoding speed. 1.1 The processing of partial words An important problem that we solve in this paper is the handling of partial words with a single beam decoder for the global model. As we pointed out in Z&C08;, it is very difficult to score partial words properly when they are compared with full words, although such comparison is necessary for incremental decoding with a single-beam. To allow comparisons with full words, partial words can either be treated as full words, or handled differently. We showed in Z&C08; that a naive single-beam decoder which treats partial words in the same way as full words failed to give a competitive accu- racy. An important reason for the low accuracy is over-segmentation during beam-search. Consider the three characters “ 自来水 (tap water)”. The first two characters do not make sense when put together as a single word. Rather, when treated as two singlecharacter words, they can make sense in a sentence such as “请 (please) 自 (self) 来 (come) 取 (take)”. Therefore, when using single-beam search to process “ 自来水 (tap water)”, the two-character word candidate “ 自来” is likely to have been thrown off the agenda before the third character “水” is considered, leading to an unrecoverable segmentation error. This problem is even more severe for a joint segmentor and POS-tagger than for a pure word segmentor, since the POS-tags and POS-tag bigram of “ 自 and “来” further supports them being separated when ”来” is considered. The multiple-beam search decoder we proposed in Z&C08; can be seen as a means to ensure that the three characters “ 自来水” always have a chance to be considered as a single word. It explores candidate segmentations from the beginning of the sentence until each character, and avoids the problem of processing partial words by considering only full words. However, since it ex- ” plores a larger part of the search space than a singlebeam decoder, its time complexity is correspondingly higher. In this paper, we treat partial words differently from full words, so that in the previous example, 844 the decoder can take the first two characters in “ 自来水 (tap water)” as a partial word, and keep it in the beam before the third character is processed. One challenge is the representation of POS-tags for partial words. The POS of a partial word is undefined without the corresponding full word information. Though a partial word can make sense with a particular POS-tag when it is treated as a complete word, this POS-tag is not necessarily the POS of the full word which contains the partial word. Take the three-character sequence “下雨天” as an example. The first character “下” represents a singlecharacter word “below”, for which the POS can be LC or VV. The first two characters “下雨” represent a two-character word “rain”, for which the POS can be VV. Moreover, all three characters when put together make the word “rainy day”, for which the POS is NN. As discussed above, assigning POS tags to partial words as if they were full words leads to low accuracy. An obvious solution to the above problem is not to assign a POS to a partial word until it becomes a full word. However, lack of POS information for partial words makes them less competitive compared to full words in the beam, since the scores of full words are futher supported by POS and POS ngram information. Therefore, not assigning POS to partial words potentially leads to over segmentation. In our experiments, this method did not give comparable accuracies to our Z&C08; system. In this paper, we take a different approach, and assign a POS-tag to a partial word when its first character is separated from the final character of the previous word. When more characters are appended to a partial word, the POS is not changed. The idea is to use the POS of a partial word as the predicted POS of the full word it will become. Possible predictions are made with the first character of the word, and the likely ones will be kept in the beam for the next processing steps. For example, with the three characters “下雨天”, we try to keep two partial words (besides full words) in the beam when the first word “下” is processed, with the POS being VV and NN, respectively. The first POS predicts the two-character word “下雨” ， and the second the three-character word “下雨天”. Now when the second character is processed, we still need to maintain the possible POS NN in the agenda, which predicts the three-character word “下雨天”. As a main contribution of this paper, we show that the mechanism ofpredicting the POS at the first character gives competitive accuracy. This mechanism can be justified theoretically. Unlike alphabetical languages, each Chinese character represents some specific meanings. Given a character, it is natural for a human speaker to know immediately what types of words it can start. The allows the knowledge of possible POS-tags of words that a character can start, using information about the character from the training data. Moreover, the POS of the previous words to the current word are also useful in deciding possible POS for the word.1 The mechanism of first-character decision of POS also boosts the efficiency, since the enumeration of POS is unecessary when a character is appended to the end of an existing word. As a result, the complexity of each processing step is reduce by half compared to a method without POS prediction. Finally, an intuitive way to represent the status of a partial word is using a flag explicitly, which means an early decision of the segmentation of the next incoming character. We take a simpler alternative approach, and treat every word as a partial word until the next incoming character is separated from the last character of this word. Before a word is confirmed as a full word, we only apply to it features that represent its current partial status, such as character bigrams, its starting character and its part-ofspeech, etc. Full word features, including the first and last characters of a word, are applied immediately after a word is confirmed as complete. An important component for our proposed system is the training process, which needs to ensure that the model scores a partial word with predicted POS properly. We use the averaged perceptron (Collins, 2002) for training, together with the “early update” mechanism of Collins and Roark (2004). Rather than updating the parameters after decoding is com- plete, the modified algorithm updates parameters at any processing step if the correct partial candidate falls out of the beam. In our experiments using the Chinese Treebank 1The next incoming characters are also a useful source of information for predicting the POS. However, our system achieved competitive accuracy with Z&C08; without such character lookahead features. 845 data, our system ran an order of magnitude faster than our Z&C08; system with little loss of accuracy. The accuracy of our system was competitive with other recent models. 2 Model and Feature Templates We use a linear model to score both partial and full candidate outputs. Given an input x, the score of a candidate output y is computed as: Score(y) = Φ(y) · where Φ(y) is the global feature vector extracted from y, and is the parameter vector of the model. Figure 1 shows the feature templates for the model, where templates 1 14 contain only segmentation information and templates 15 29 contain w~ , w~ – – both segmentation and POS information. Each template is instantiated according to the current character in the decoding process. Row “For” shows the conditions for template instantiation, where “s” indicates that the corresponding template is instantiated when the current character starts a new word, and “a” indicates that the corresponding template is instantiated when the current character does not start a new word. In the row for feature templates, w, t and c are used to represent a word, a POS-tag and a character, respectively. The subscripts are based on the current character, where w−1 represents the first word to the left of the current character, and p−2 represents the POS-tag on the second word to the left of the current character, and so on. As an example, feature template 1is instantiated when the current character starts a new word, and the resulting feature value is the word to the left of this character. start(w), end(w) and len(w) represent the first character, the last character and the length of word w, respectively. The length of a word is normalized to 16 if it is larger than 16. cat(c) represents the POS category of character c, which is the set of POS-tags seen on character c, as we used in Z&C08.; Given a partial or complete candidate y, its global feature vector Φ(y) is computed by instantiating all applicable feature templates from Table 1 for each character in y, according to whether or not the character is separated from the previous character. The feature templates are mostly taken from, or inspired by, the feature templates of Z&C08.; Templates 1, 2, 3, 4, 5, 8, 10, 12, 13, 14, 15, 19, 20, Feature templateFor 24, 27 and 29 concern complete word information, and they are used in the model to differentiate correct and incorrect output structures in the same way as our Z&C08; model. Templates 6, 7, 9, 16, 17, 18, 21, 22, 23, 25, 26 and 28 concern partial word information, whose role in the model is to indicate the likelihood that the partial word including the current character will become a correct full word. They act as guidance for the action to take for the cur846 function DECODE(sent, agenda): CLEAR(agenda) ADDITEM(agenda, “”) for index in [0..LEN(sent)]: for cand in agenda: new ← APPEND(cand, sent[index]) ADDITEM(agenda, new) for pos in TAGSET(): new ← SEP(cand, sent[index], pos) ADDITEM(agenda, new) agenda ← N-BEST(agenda) retaugrenn BEST(agenda) Figure 1: The incremental beam-search decoder. rent character according to the context, and are the crucial reason for the effectiveness of the algorithm with a small beam-size. 2.1 Decoding The decoding algorithm builds an output candidate incrementally, one character at a time. Each character can either be attached to the current word or separated as the start a new word. When the current character starts a new word, a POS-tag is assigned to the new word. An agenda is used by the decoder to keep the N-best candidates during the incremental process. Before decoding starts, the agenda is initialized with an empty sentence. When a character is processed, existing candidates are removed from the agenda and extended with the current character in all possible ways, and the N-best newly generated candidates are put back onto the agenda. After all input characters have been processed, the highest-scored candidate from the agenda is taken as the output. Pseudo code for the decoder is shown in Figure 1. CLEAR removes all items from the agenda, ADDITEM adds a new item onto the agenda, N-BEST returns the N highest-scored items from the agenda, and BEST returns the highest-scored item from the agenda. LEN returns the number of characters in a sentence, and sent[i] returns the ith character from the sentence. APPEND appends a character to the last word in a candidate, and SEP joins a character as the start of a new word in a candidate, assigning a POS-tag to the new word. Both our decoding algorithm and the decoding algorithm of Z&C08; run in linear time. However, in order to generate possible candidates for each character, Z&C08; uses an extra loop to search for possible words that end with the current character. A restriction to the maximum word length is applied to limit the number of iterations in this loop, without which the algorithm would have quadratic time complexity. In contrast, our decoder does not search backword for the possible starting character of any word. Segmentation ambiguities are resolved by binary choices between the actions append or separate for each character, and no POS enumeration is required when the character is appended. This improves the speed by a significant factor. 2.2 Training The learning algorithm is based on the generalized perceptron (Collins, 2002), but parameter adjustments can be performed at any character during the decoding process, using the “early update” mechanism of Collins and Roark (2004). The parameter vector of the model is initialized as all zeros before training, and used to decode training examples. Each training example is turned into the raw input format, and processed in the same way as decoding. After each character is processed, partial candidates in the agenda are compared to the corresponding gold-standard output for the same characters. If none of the candidates in the agenda are correct, the decoding is stopped and the parameter vector is updated by adding the global feature vector of the gold-standard partial output and subtracting the global feature vector of the highest-scored partial candidate in the agenda. The training process then moves on to the next example. However, if any item in the agenda is the same as the corresponding gold-standard, the decoding process moves to the next character, without any change to the parameter values. After all characters are processed, the decoder prediction is compared with the training example. If the prediction is correct, the parameter vector is not changed; otherwise it is updated by adding the global feature vector of the training example and subtracting the global feature vector of the decoder prediction, just as the perceptron algorithm does. The same training examples can be used to train the model for multiple iterations. We use 847 the averaged parameter vector (Collins, 2002) as the final model. Pseudocode for the training algorithm is shown in Figure 2. It is based on the decoding algorithm in Figure 1, and the main differences are: (1) the training algorithm takes the gold-standard output and the parameter vector as two additional arguments; (2) the training algorithm does not return a prediction, but modifies the parameter vector when necessary; (3) lines 11to 20 are additional lines of code for parameter updates. Without lines 11 to 16, the training algorithm is exactly the same as the generalized perceptron algorithm. These lines are added to ensure that the agenda contains highly probable candidates during the whole beam-search process, and they are crucial to the high accuracy of the system. As stated earlier, the decoder relies on proper scoring of partial words to maintain a set of high quality candidates in the agenda. Updating the value of the parameter vector for partial outputs can be seen as a means to ensure correct scoring of partial candidates at any character. 2.3 Pruning We follow Z&C08; and use several pruning methods, most of which serve to to improve the accuracy by removing irrelevant candidates from the beam. First, the system records the maximum number of characters that a word with a particular POS-tag can have. For example, from the Chinese Treebank that we used for our experiments, most POS are associated with only with one- or two-character words. The only POS-tags that are seen with words over ten characters long are NN (noun), NR (proper noun) and CD (numbers). The maximum word length information is initialized as all ones, and updated according to each training example before it is processed. Second, a tag dictionary is used to record POStags associated with each word. During decoding, frequent words and words with “closed set” tags2 are only allowed POS-tags according to the tag dictionary, while other words are allowed every POS-tag to make candidate outputs. Whether a word is a frequent word is decided by the number of times it has been seen in the training process. Denoting the num2“Closed set” tags are the set of POS-tags which are only associated with a fixed set of words, according to the Penn Chinese Treebank specifications (Xia, 2000). function TRAIN(sent, agenda, gold-standard, w~ ): 01: CLEAR(agenda) 02: ADDITEM(agenda, “”) 03: for index in [0..LEN(sent)]: 04: 05: 06: 07: 08: 09: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: for cand in agenda: new ← APPEND(cand, sent[index]) ADDITEM(agenda, new) for pos in TAGSET(): new ← SEP(cand, sent[index], pos) ADDITEM(agenda, new) agenda ← N-BEST(agenda) faogre cnadnad ← ←in agenda: if cand = gold-standard[0:index] : CONTINUE w~ ← w~ + Φ(gold-standard[0:index]) ww~~ ← ww~ ~ - Φ(BEST(agenda)) wr~et ←urn w~ if BEST(agenda) gold-standard: w~ ← a ~wg + Φ(gold-standard) ww~~ ← ww~ ~ - Φ(BEST(agenda)) wr~et ←urn w~ return = Figure 2: The incremental learning function. ber of times the most frequent word has been seen with M, a word is a frequent word if it has been seen more than M/5000 5 times. The threshold value is taken from Z&C08;, and we did not adjust it during development. Word frequencies are initialized as zeros and updated according to each training example before it is processed; the tag dictionary is initialized as empty and updated according to each training example before it is processed. Third, we make an additional record of the initial characters for words with “closed set” tags. During decoding, when the current character is added as the start of a new word, “closed set” tags are only assigned to the word if it is consistent with the record. This type of pruning is used in addition to the tag + dictionary to prune invalid partial words, while the tag dictionary is used to prune complete words. The record for initial character and POS is initially empty, and udpated according to each training example before it is processed. Finally, at any decoding step, we group partial 848 candidates that are generated by separating the current character as the start of a new word by the signature p0p−1w−1, and keep only the best among those having the same p0p−1w−1. The signature p0p−1w−1 is decided by the feature templates we use: it can be shown that if two candidates cand1 and cand2 generated at the same step have the same signature, and the score of cand1 is higher than the score of cand2, then at any future step, the highest scored candidate generated from cand1 will always have a higher score than the highest scored candidate generated from cand2. From the above pruning methods, only the third was not used by Z&C08.; It can be seen as an extra mechanism to help keep likely partial words in the agenda and improve the accuracy, but which does not give our system a speed advantage over Z&C08.; 3 Experiments We used the Chinese Treebank (CTB) data to perform one set of development tests and two sets of fi- Training iteration Figure 3: The influence of beam-sizes, and the convergence of the perceptron. nal tests. The CTB 4 was split into two parts, with the CTB 3 being used for a 10-fold cross validation test to compare speed and accuracies with Z&C08;, and the rest being used for development. The CTB 5 was used to perform the additional set of experiments to compare accuracies with other recent work. We use the standard F-measure to evaluate output accuracies. For word segmentation, precision is defined as the number of correctly segmented words divided by the total number of words in the output, and recall is defined as the number of correctly segmented words divided by the total number of words in the gold-standard output. For joint segmentation and POS-tagging, precision is defined as the number of correctly segmented and POS-tagged words divided by the total number of words from the output, and recall is defined as the correctly segmented and POS-tagged words divided by the total number of words in the gold-standard output. All our experiments were performed on a Linux platform, and a single 2.66GHz Intel Core 2 CPU. 3.1 Development tests Our development data consists of 150K words in 4798 sentences. 80% of the data were randomly chosen as the development training data, while the rest were used as the development test data. Our development tests were mainly used to decide the size ofthe beam, the number oftraining iterations, the ef- fect of partial features in beam-search decoding, and the effect of incremental learning (i.e. early update). 849 Figure 3 shows the accuracy curves for joint segmentation and POS-tagging by the number of training iterations, using different beam sizes. With the size of the beam increasing from 1to 32, the accuracies generally increase, while the amount of increase becomes small when the size of the beam becomes 16. After the 10th iteration, a beam size of 32 does not always give better accuracies than a beam size of 16. We therefore chose 16 as the size of the beam for our system. The testing times for each beam size between 1 and 32 are 7.16s, 11.90s, 18.42s, 27.82s, 46.77s and 89.21s, respectively. The corresponding speeds in the number of sentences per second are 111.45, 67.06, 43.32, 28.68, 17.06 and 8.95, respectively. Figure 3 also shows that the accuracy increases with an increased number of training iterations, but the amount of increase becomes small after the 25th iteration. We chose 29 as the number of iterations to train our system. The effect of incremental training: We compare the accuracies by incremental training using early update and normal perceptron training. In the normal perceptron training case, lines 11to 16 are taken out of the training algorithm in Figure 2. The algorithm reached the best performance at the 22nd iteration, with the segmentation F-score being 90.58% and joint F-score being 83.38%. In the incremental training case, the algorithm reached the best accuracy at the 30th training iteration, obtaining a segmentation F-score of 91.14% and a joint F-score of 84.06%. 3.2 Final tests using CTB 3 CTB 3 consists of 150K words in 10364 sentences. We follow Z&C08; and split it into 10 equal-sized parts. In each test, one part is taken as the test data and the other nine are combined together as the training data. We compare the speed and accuracy with the joint segmentor and tagger of Z&C08;, which is publicly available as the ZPar system, version 0.23. The results are shown in Table 2, where each row shows one cross validation test. The column head- ings “sf”, “jf”, “time” and “speed” refer to segmentation F-measure, joint F-measure, testing time (in 3http://www.sourceforge.net/projects/zpar #sZf&C08jftimespeed; tshfis papjefrtimespeed seconds) and testing speed (in the number of sentences per second), respectively. Our system gave a joint segmentation and POStagging F-score of 91.37%, which is only 0.04% lower than that of ZPar 0.2. The speed of our system was over 10 times as fast as ZPar 0.2. 3.3 Final tests using CTB 5 We follow Kruengkrai et al. (2009) and split the CTB 5 into training, development testing and testing sets, as shown in Table 3. We ignored the development test data since our system had been developed in previous experiments. Kruengkrai et al. (2009) made use of character type knowledge for spaces, numerals, symbols, alphabets, Chinese and other characters. In the previous experiments, our system did not use any knowledge beyond the training data. To make the comparison fairer, we included knowledge of English letters and Arabic numbers in this experiment. During both training and decoding, English letters and Arabic numbers are segmented using simple rules, treating consecutive English letters or Arabic numbers as a single word. The results are shown in Table 4, where row “N07” refers to the model of Nakagawa and Uchimoto (2007), rows “J08a” and “b” refer to the models of Jiang et al. (2008a) and Jiang et al. (2008b), and row “K09” refers to the models of Kruengkrai et al. (2009). Columns “sf” and “jf” refer to segmentation and joint accuracies, respectively. Our system 850 SectionsSentencesWords T Daerbsvltien3:gTrain14230i–7n021 g–71,3d90–21e035v 1elopm1e385n40t,8and5tes a648t,903o2n,18C92TB5. TJoKNab0ul8re79abs4(y:rtAesomcl-indurea)vycom9 pa7 r.i87s34o59n w3 i.t64h2710recntsudio sfjf CTB 5. gave comparable accuracies to these recent works, obtaining the best (same as the error-driven version of K09) joint F-score. 4 Related Work The effectiveness of our beam-search decoder showed that the joint segmentation and tagging problem may be less complex than previously perceived (Zhang and Clark, 2008; Jiang et al., 2008a). At the very least, the single model approach with a simple decoder achieved competitive accuracies to what has been achieved so far by the reranking (Shi and Wang, 2007; Jiang et al., 2008b) models and an ensemble model using machine-translation techniques (Jiang et al., 2008a). This may shed new light on joint segmentation and POS-tagging methods. Kruengkrai et al. (2009) and Zhang and Clark (2008) are the most similar to our system among related work. Both systems use a discriminatively trained linear model to score candidate outputs. The work of Kruengkrai et al. (2009) is based on Nakagawa and Uchimoto (2007), which separates the processing of known words and unknown words, and uses a set of segmentation tags to represent the segmentation of characters. In contrast, our model is conceptually simpler, and does not differentiate known words and unknown words. Moreover, our model is based on our previous work, in line with Zhang and Clark (2007), which does not treat word segmentation as character sequence labeling. Our learning and decoding algorithms are also different from Kruengkrai et al. (2009). While Kruengkrai et al. (2009) perform dynamic programming and MIRA learning, we use beam-search to perform incremental decoding, and the early-update version of the perceptron algorithm to train the model. Dynamic programming is exact inference, for which the time complexity is decided by the locality of feature templates. In contrast, beam-search is approximate and can run in linear time. The parameter updating for our algorithm is conceptually and computationally simpler than MIRA, though its performance can be slightly lower. However, the earlyupdate mechanism we use is consistent with our incremental approach, and improves the learning of the beam-search process. 5 Conclusion We showed that a simple beam-search decoding algorithm can be effectively applied to the decoding problem for a global linear model for joint word segmentation and POS-tagging. By guiding search with partial word information and performing learning for partial candidates, our system achieved sig- nificantly faster speed with little accuracy loss compared to the system of Z&C08.; The source code of our joint segmentor and POStagger can be found at: www.sourceforge.net/projects/zpar, version 0.4. 851 Acknowledgements We thank Canasai Kruengkrai for discussion on efficiency issues, and the anonymous reviewers for their suggestions. Yue Zhang and Stephen Clark are supported by the European Union Seventh Framework Programme (FP7-ICT-2009-4) under grant agreement no. 247762. References Eugene Charniak, Mark Johnson, Micha Elsner, Joseph Austerweil, David Ellis, Isaac Haxton, Catherine Hill, R. Shrivaths, Jeremy Moore, Michael Pozar, and Theresa Vu. 2006. Multilevel coarse-to-fine PCFG parsing. In Proceedings of HLT/NAACL, pages 168– 175, New York City, USA, June. Association for Computational Linguistics. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111–1 18, Barcelona, Spain, July. Michael Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP, pages 1–8, Philadelphia, USA, July. Wenbin Jiang, Liang Huang, Qun Liu, and Yajuan L u¨. 2008a. A cascaded linear model for joint Chinese word segmentation and part-of-speech tagging. In Proceedings of ACL/HLT, pages 897–904, Columbus, Ohio, June. Wenbin Jiang, Haitao Mi, and Qun Liu. 2008b. Word lattice reranking for Chinese word segmentation and part-of-speech tagging. In Proceedings of COLING, pages 385–392, Manchester, UK, August. Canasai Kruengkrai, Kiyotaka Uchimoto, Jun’ichi Kazama, Yiou Wang, Kentaro Torisawa, and Hitoshi Isahara. 2009. An error-driven word-character hybrid model for joint Chinese word segmentation and POS tagging. In Proceedings of ACL/AFNLP, pages 5 13– 521, Suntec, Singapore, August. Tetsuji Nakagawa and Kiyotaka Uchimoto. 2007. A hybrid approach to word segmentation and POS tagging. In Proceedings of ACL Demo and Poster Session, Prague, Czech Republic, June. Hwee Tou Ng and Jin Kiat Low. 2004. Chinese part-ofspeech tagging: One-at-a-time or all-at-once? word- based or character-based? In Proceedings of EMNLP, Barcelona, Spain. Brian Roark and Kristy Hollingshead. 2008. Classifying chart cells for quadratic complexity context-free inference. In Proceedings of COLING, pages 745– 752, Manchester, UK, August. Coling 2008 Organizing Committee. Yanxin Shi and Mengqiu Wang. 2007. A dual-layer CRF based joint decoding method for cascade segmentation and labelling tasks. In Proceedings of IJCAI, Hyderabad, India. Fei Xia, 2000. The part-of-speech tagging guidelines for the Chinese Treebank (3.0). Yue Zhang and Stephen Clark. 2007. Chinese segmentation with a word-based perceptron algorithm. In Proceedings of ACL, pages 840–847, Prague, Czech Republic, June. Yue Zhang and Stephen Clark. 2008. Joint word segmentation and POS tagging using a single perceptron. In Proceedings of ACL/HLT, pages 888–896, Columbus, Ohio, June. 852

4 0.1373284 34 emnlp-2010-Crouching Dirichlet, Hidden Markov Model: Unsupervised POS Tagging with Context Local Tag Generation

Author: Taesun Moon ; Katrin Erk ; Jason Baldridge

Abstract: We define the crouching Dirichlet, hidden Markov model (CDHMM), an HMM for partof-speech tagging which draws state prior distributions for each local document context. This simple modification of the HMM takes advantage of the dichotomy in natural language between content and function words. In contrast, a standard HMM draws all prior distributions once over all states and it is known to perform poorly in unsupervised and semisupervised POS tagging. This modification significantly improves unsupervised POS tagging performance across several measures on five data sets for four languages. We also show that simply using different hyperparameter values for content and function word states in a standard HMM (which we call HMM+) is surprisingly effective.

5 0.12973368 97 emnlp-2010-Simple Type-Level Unsupervised POS Tagging

Author: Yoong Keok Lee ; Aria Haghighi ; Regina Barzilay

Abstract: Part-of-speech (POS) tag distributions are known to exhibit sparsity a word is likely to take a single predominant tag in a corpus. Recent research has demonstrated that incorporating this sparsity constraint improves tagging accuracy. However, in existing systems, this expansion come with a steep increase in model complexity. This paper proposes a simple and effective tagging method that directly models tag sparsity and other distributional properties of valid POS tag assignments. In addition, this formulation results in a dramatic reduction in the number of model parameters thereby, enabling unusually rapid training. Our experiments consistently demonstrate that this model architecture yields substantial performance gains over more complex tagging — counterparts. On several languages, we report performance exceeding that of more complex state-of-the art systems.1

6 0.12399708 99 emnlp-2010-Statistical Machine Translation with a Factorized Grammar

7 0.12124556 75 emnlp-2010-Lessons Learned in Part-of-Speech Tagging of Conversational Speech

8 0.11946061 10 emnlp-2010-A Probabilistic Morphological Analyzer for Syriac

9 0.11597866 64 emnlp-2010-Incorporating Content Structure into Text Analysis Applications

10 0.11160584 17 emnlp-2010-An Efficient Algorithm for Unsupervised Word Segmentation with Branching Entropy and MDL

11 0.10960101 41 emnlp-2010-Efficient Graph-Based Semi-Supervised Learning of Structured Tagging Models

12 0.098877415 71 emnlp-2010-Latent-Descriptor Clustering for Unsupervised POS Induction

13 0.093955293 25 emnlp-2010-Better Punctuation Prediction with Dynamic Conditional Random Fields

14 0.089682207 33 emnlp-2010-Cross Language Text Classification by Model Translation and Semi-Supervised Learning

15 0.089325614 9 emnlp-2010-A New Approach to Lexical Disambiguation of Arabic Text

16 0.080729604 86 emnlp-2010-Non-Isomorphic Forest Pair Translation

17 0.076419219 88 emnlp-2010-On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing

18 0.074058235 77 emnlp-2010-Measuring Distributional Similarity in Context

19 0.073237784 61 emnlp-2010-Improving Gender Classification of Blog Authors

20 0.073010519 110 emnlp-2010-Turbo Parsers: Dependency Parsing by Approximate Variational Inference

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.252), (1, 0.129), (2, 0.078), (3, -0.151), (4, -0.393), (5, 0.042), (6, -0.004), (7, -0.102), (8, -0.199), (9, -0.016), (10, -0.075), (11, -0.053), (12, -0.021), (13, -0.202), (14, -0.116), (15, 0.133), (16, 0.158), (17, 0.022), (18, 0.14), (19, -0.021), (20, 0.117), (21, -0.082), (22, -0.028), (23, -0.041), (24, -0.015), (25, -0.006), (26, -0.008), (27, -0.006), (28, -0.002), (29, 0.143), (30, -0.018), (31, 0.034), (32, -0.019), (33, -0.044), (34, -0.012), (35, -0.011), (36, 0.022), (37, -0.026), (38, -0.02), (39, 0.068), (40, 0.072), (41, -0.026), (42, 0.059), (43, -0.039), (44, 0.023), (45, -0.061), (46, -0.11), (47, 0.048), (48, -0.015), (49, -0.002)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.98433548 69 emnlp-2010-Joint Training and Decoding Using Virtual Nodes for Cascaded Segmentation and Tagging Tasks

Author: Xian Qian ; Qi Zhang ; Yaqian Zhou ; Xuanjing Huang ; Lide Wu

2 0.78640378 43 emnlp-2010-Enhancing Domain Portability of Chinese Segmentation Model Using Chi-Square Statistics and Bootstrapping

Author: Baobao Chang ; Dongxu Han

3 0.73442483 2 emnlp-2010-A Fast Decoder for Joint Word Segmentation and POS-Tagging Using a Single Discriminative Model

Author: Yue Zhang ; Stephen Clark

4 0.45584556 17 emnlp-2010-An Efficient Algorithm for Unsupervised Word Segmentation with Branching Entropy and MDL

Author: Valentin Zhikov ; Hiroya Takamura ; Manabu Okumura

Abstract: This paper proposes a fast and simple unsupervised word segmentation algorithm that utilizes the local predictability of adjacent character sequences, while searching for a leasteffort representation of the data. The model uses branching entropy as a means of constraining the hypothesis space, in order to efficiently obtain a solution that minimizes the length of a two-part MDL code. An evaluation with corpora in Japanese, Thai, English, and the ”CHILDES” corpus for research in language development reveals that the algorithm achieves an accuracy, comparable to that of the state-of-the-art methods in unsupervised word segmentation, in a significantly reduced . computational time.

5 0.44346723 10 emnlp-2010-A Probabilistic Morphological Analyzer for Syriac

Author: Peter McClanahan ; George Busby ; Robbie Haertel ; Kristian Heal ; Deryle Lonsdale ; Kevin Seppi ; Eric Ringger

Abstract: We define a probabilistic morphological analyzer using a data-driven approach for Syriac in order to facilitate the creation of an annotated corpus. Syriac is an under-resourced Semitic language for which there are no available language tools such as morphological analyzers. We introduce novel probabilistic models for segmentation, dictionary linkage, and morphological tagging and connect them in a pipeline to create a probabilistic morphological analyzer requiring only labeled data. We explore the performance of models with varying amounts of training data and find that with about 34,500 labeled tokens, we can outperform a reasonable baseline trained on over 99,000 tokens and achieve an accuracy of just over 80%. When trained on all available training data, our joint model achieves 86.47% accuracy, a 29.7% reduction in error rate over the baseline.

6 0.42503461 34 emnlp-2010-Crouching Dirichlet, Hidden Markov Model: Unsupervised POS Tagging with Context Local Tag Generation

7 0.4134644 41 emnlp-2010-Efficient Graph-Based Semi-Supervised Learning of Structured Tagging Models

8 0.39285213 97 emnlp-2010-Simple Type-Level Unsupervised POS Tagging

9 0.38824838 71 emnlp-2010-Latent-Descriptor Clustering for Unsupervised POS Induction

10 0.37816879 75 emnlp-2010-Lessons Learned in Part-of-Speech Tagging of Conversational Speech

11 0.36645737 9 emnlp-2010-A New Approach to Lexical Disambiguation of Arabic Text

12 0.35196936 79 emnlp-2010-Mining Name Translations from Entity Graph Mapping

13 0.33701703 13 emnlp-2010-A Simple Domain-Independent Probabilistic Approach to Generation

14 0.31440294 61 emnlp-2010-Improving Gender Classification of Blog Authors

15 0.30757791 99 emnlp-2010-Statistical Machine Translation with a Factorized Grammar

16 0.30651367 64 emnlp-2010-Incorporating Content Structure into Text Analysis Applications

17 0.29631686 25 emnlp-2010-Better Punctuation Prediction with Dynamic Conditional Random Fields

18 0.28669596 77 emnlp-2010-Measuring Distributional Similarity in Context

19 0.28574196 110 emnlp-2010-Turbo Parsers: Dependency Parsing by Approximate Variational Inference

20 0.28493413 48 emnlp-2010-Exploiting Conversation Structure in Unsupervised Topic Segmentation for Emails

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(3, 0.025), (5, 0.013), (10, 0.019), (12, 0.042), (29, 0.129), (32, 0.015), (52, 0.046), (56, 0.103), (62, 0.022), (64, 0.192), (66, 0.167), (72, 0.072), (76, 0.014), (79, 0.022), (87, 0.025), (89, 0.018)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.90604836 65 emnlp-2010-Inducing Probabilistic CCG Grammars from Logical Form with Higher-Order Unification

Author: Tom Kwiatkowksi ; Luke Zettlemoyer ; Sharon Goldwater ; Mark Steedman

Abstract: This paper addresses the problem of learning to map sentences to logical form, given training data consisting of natural language sentences paired with logical representations of their meaning. Previous approaches have been designed for particular natural languages or specific meaning representations; here we present a more general method. The approach induces a probabilistic CCG grammar that represents the meaning of individual words and defines how these meanings can be combined to analyze complete sentences. We use higher-order unification to define a hypothesis space containing all grammars consistent with the training data, and develop an online learning algorithm that efficiently searches this space while simultaneously estimating the parameters of a log-linear parsing model. Experiments demonstrate high accuracy on benchmark data sets in four languages with two different meaning representations.

same-paper 2 0.87194544 69 emnlp-2010-Joint Training and Decoding Using Virtual Nodes for Cascaded Segmentation and Tagging Tasks

Author: Xian Qian ; Qi Zhang ; Yaqian Zhou ; Xuanjing Huang ; Lide Wu

3 0.76847458 82 emnlp-2010-Multi-Document Summarization Using A* Search and Discriminative Learning

Author: Ahmet Aker ; Trevor Cohn ; Robert Gaizauskas

Abstract: In this paper we address two key challenges for extractive multi-document summarization: the search problem of finding the best scoring summary and the training problem of learning the best model parameters. We propose an A* search algorithm to find the best extractive summary up to a given length, which is both optimal and efficient to run. Further, we propose a discriminative training algorithm which directly maximises the quality ofthe best summary, rather than assuming a sentence-level decomposition as in earlier work. Our approach leads to significantly better results than earlier techniques across a number of evaluation metrics.

4 0.7614218 86 emnlp-2010-Non-Isomorphic Forest Pair Translation

Author: Hui Zhang ; Min Zhang ; Haizhou Li ; Eng Siong Chng

Abstract: This paper studies two issues, non-isomorphic structure translation and target syntactic structure usage, for statistical machine translation in the context of forest-based tree to tree sequence translation. For the first issue, we propose a novel non-isomorphic translation framework to capture more non-isomorphic structure mappings than traditional tree-based and tree-sequence-based translation methods. For the second issue, we propose a parallel space searching method to generate hypothesis using tree-to-string model and evaluate its syntactic goodness using tree-to-tree/tree sequence model. This not only reduces the search complexity by merging spurious-ambiguity translation paths and solves the data sparseness issue in training, but also serves as a syntax-based target language model for better grammatical generation. Experiment results on the benchmark data show our proposed two solutions are very effective, achieving significant performance improvement over baselines when applying to different translation models.

5 0.76076329 35 emnlp-2010-Discriminative Sample Selection for Statistical Machine Translation

Author: Sankaranarayanan Ananthakrishnan ; Rohit Prasad ; David Stallard ; Prem Natarajan

Abstract: Production of parallel training corpora for the development of statistical machine translation (SMT) systems for resource-poor languages usually requires extensive manual effort. Active sample selection aims to reduce the labor, time, and expense incurred in producing such resources, attaining a given performance benchmark with the smallest possible training corpus by choosing informative, nonredundant source sentences from an available candidate pool for manual translation. We present a novel, discriminative sample selection strategy that preferentially selects batches of candidate sentences with constructs that lead to erroneous translations on a held-out development set. The proposed strategy supports a built-in diversity mechanism that reduces redundancy in the selected batches. Simulation experiments on English-to-Pashto and Spanish-to-English translation tasks demon- strate the superiority of the proposed approach to a number of competing techniques, such as random selection, dissimilarity-based selection, as well as a recently proposed semisupervised active learning strategy.

6 0.75961143 49 emnlp-2010-Extracting Opinion Targets in a Single and Cross-Domain Setting with Conditional Random Fields

7 0.7545715 2 emnlp-2010-A Fast Decoder for Joint Word Segmentation and POS-Tagging Using a Single Discriminative Model

8 0.75453234 78 emnlp-2010-Minimum Error Rate Training by Sampling the Translation Lattice

9 0.75433934 67 emnlp-2010-It Depends on the Translation: Unsupervised Dependency Parsing via Word Alignment

10 0.75205338 18 emnlp-2010-Assessing Phrase-Based Translation Models with Oracle Decoding

11 0.75126708 105 emnlp-2010-Title Generation with Quasi-Synchronous Grammar

12 0.74961567 25 emnlp-2010-Better Punctuation Prediction with Dynamic Conditional Random Fields

13 0.74895036 103 emnlp-2010-Tense Sense Disambiguation: A New Syntactic Polysemy Task

14 0.74844819 84 emnlp-2010-NLP on Spoken Documents Without ASR

15 0.74739665 58 emnlp-2010-Holistic Sentiment Analysis Across Languages: Multilingual Supervised Latent Dirichlet Allocation

16 0.74574596 104 emnlp-2010-The Necessity of Combining Adaptation Methods

17 0.74567389 45 emnlp-2010-Evaluating Models of Latent Document Semantics in the Presence of OCR Errors

18 0.74548703 109 emnlp-2010-Translingual Document Representations from Discriminative Projections

19 0.74511123 43 emnlp-2010-Enhancing Domain Portability of Chinese Segmentation Model Using Chi-Square Statistics and Bootstrapping

20 0.74427623 120 emnlp-2010-What's with the Attitude? Identifying Sentences with Attitude in Online Discussions