emnlp emnlp2010 emnlp2010-54 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alla Rozovskaya ; Dan Roth
Abstract: In this paper, we consider the problem of generating candidate corrections for the task of correcting errors in text. We focus on the task of correcting errors in preposition usage made by non-native English speakers, using discriminative classifiers. The standard approach to the problem assumes that the set of candidate corrections for a preposition consists of all preposition choices participating in the task. We determine likely preposition confusions using an annotated corpus of nonnative text and use this knowledge to produce smaller sets of candidates. We propose several methods of restricting candidate sets. These methods exclude candidate prepositions that are not observed as valid corrections in the annotated corpus and take into account the likelihood of each preposition confusion in the non-native text. We find that restricting candidates to those that are ob- served in the non-native data improves both the precision and the recall compared to the approach that views all prepositions as possible candidates. Furthermore, the approach that takes into account the likelihood of each preposition confusion is shown to be the most effective.
Reference: text
sentIndex sentText sentNum sentScore
1 edu l ino s Abstract In this paper, we consider the problem of generating candidate corrections for the task of correcting errors in text. [sent-2, score-0.518]
2 We focus on the task of correcting errors in preposition usage made by non-native English speakers, using discriminative classifiers. [sent-3, score-0.844]
3 The standard approach to the problem assumes that the set of candidate corrections for a preposition consists of all preposition choices participating in the task. [sent-4, score-1.571]
4 We determine likely preposition confusions using an annotated corpus of nonnative text and use this knowledge to produce smaller sets of candidates. [sent-5, score-0.931]
5 These methods exclude candidate prepositions that are not observed as valid corrections in the annotated corpus and take into account the likelihood of each preposition confusion in the non-native text. [sent-7, score-1.514]
6 We find that restricting candidates to those that are ob- served in the non-native data improves both the precision and the recall compared to the approach that views all prepositions as possible candidates. [sent-8, score-0.439]
7 Furthermore, the approach that takes into account the likelihood of each preposition confusion is shown to be the most effective. [sent-9, score-0.851]
8 1 Introduction We address the problem of generating candidate corrections for the task of correcting context-dependent mistakes in text, mistakes that involve confusing valid words in a language. [sent-10, score-0.593]
9 The context-sensitive spelling correction task addresses the problem of correcting spelling mistakes that result in legitimate words, such as confusing their and there or your and you ’re. [sent-13, score-0.585]
10 In this task, a candidate set or a confusion set is defined that spec- ifies a list of confusable words, e. [sent-14, score-0.41]
11 Given a text to correct, for each word in text that belongs to the confusion set the classifier predicts the most likely candidate in the confusion set. [sent-21, score-0.67]
12 More recently, work in error correction has taken an interesting turn and focused on correcting errors made by English as a Second Language (ESL) learners, with a special interest given to errors in article and preposition usage. [sent-22, score-1.327]
13 Approaches to correcting these mistakes have adopted the methods of the context-sensitive spelling correction task. [sent-26, score-0.516]
14 While in the article correction task the candidate set is small (a, the, no article), systems for correcting preposition errors, even when they consider the most common prepositions, may include between 9 to 34 preposition classes. [sent-38, score-1.797]
15 For each preposition in the non-native text, every other candidate in the confusion set is viewed as a potential correction. [sent-39, score-0.962]
16 This approach, however, does not take into account that writers do not make mistakes randomly: Not all candidates are equally likely given the preposition chosen by the author and errors may depend on the first language (L1) of the writer. [sent-40, score-0.884]
17 In this paper, we de- fine L1-dependent candidate sets for the preposition correction task (Section 4. [sent-41, score-1.066]
18 L1-dependent candidate sets reflect preposition confusions observed with the speakers of the first language L1. [sent-43, score-1.041]
19 In this approach, a separate binary classifier for each preposition pi, 1 ≤ i ≤ 10, is trained, s. [sent-47, score-0.704]
20 Thus, for each preposition pi in non-native text there are ten1 possible prepositions that the classifier can propose as corrections for pi. [sent-52, score-1.337]
21 First, we train a separate classifier for each preposition pi on the prepositions that belong to L1dependent candidate set of pi. [sent-54, score-1.333]
22 In this setting, the negative examples for pi are those that belong to L1dependent candidate set of pi. [sent-55, score-0.377]
23 The second method of enforcing L1-dependent 1This includes the preposition pi itself. [sent-56, score-0.842]
24 962 candidate sets in training is to train on native data with artificial preposition errors in the spirit of Rozovskaya and Roth (2010b), where the errors mimic the error rates and error patterns of the non-native text. [sent-58, score-1.367]
25 We consider two ways of applying a threshold: (1) the standard way, when a correction is proposed only if the classifier’s confidence is sufficiently high and (2) L1-dependent threshold, when a correction is proposed only if it belongs to L1-dependent candidate set. [sent-61, score-0.708]
26 We show that the methods of restricting candidate sets to L1-dependent confusions improve the preposition correction system. [sent-62, score-1.316]
27 We demonstrate that restricting candidate sets to those prepositions that are confusable in the data by L1 writers is beneficial, when compared to a system that assumes an unrestricted candidate set by considering as valid corrections all prepositions participating in the task. [sent-63, score-1.358]
28 Furthermore, we find that the most effective method is the one that uses knowledge about the likelihoods of preposition confusions in the non-native text introduced through artificial errors in training. [sent-64, score-0.938]
29 Section 3 presents the ESL data and statistics on preposition errors. [sent-67, score-0.609]
30 2 Related Work Work in text correction has focused primarily on correcting context-sensitive spelling errors (Golding and Roth, 1999; Banko and Brill, 2001 ; Carlson et al. [sent-74, score-0.553]
31 , 2001 ; Carlson and Fette, 2007) and mistakes made by ESL learners, especially errors in article and preposition usage. [sent-75, score-0.857]
32 Given a candidate set or a confusion set of confusable words, the task is to select the most likely candidate in context. [sent-77, score-0.541]
33 Examples of confusion sets are {sight, site, cite} for contextsoefn csoitnifveus spelling correction, {among, between} fxotrsweonrsdit selection, or a srerte of prepositions f boert twheee preposition correction problem. [sent-78, score-1.5]
34 Given text to correct, for each word in text that belongs to the confusion set the classifier is used to predict the most likely candidate in the confusion set given the word’s context. [sent-81, score-0.67]
35 al (2007), Tetreault and Chodorow (2008), and De Felice and Pulman (2008) train a maximum entropy model and De Felice and Pulman (2007) train a voted perceptron algorithm to correct preposition errors. [sent-86, score-0.707]
36 (2008) train a decision tree model and a language model to correct errors in article and preposition usage. [sent-88, score-0.834]
37 (2009) propose a Na¨ ıve Bayes algorithm with web-scale N-grams as features, for preposition selection and context-sensitive spelling correction. [sent-90, score-0.678]
38 The set of valid candidate corrections for a target word includes all words in the confusion set. [sent-91, score-0.577]
39 For the preposition correction task, the entire set of prepositions considered for the task is viewed as the set of possible corrections for each preposition in nonnative text. [sent-92, score-2.024]
40 Given a preposition with its surrounding context, the model selects the most likely preposition from the set of all candidates, where the set of candidates consists of nine (Felice and Pulman, 2008), 12 (Gamon, 2010), or 34 (Tetreault et al. [sent-93, score-1.306]
41 One way to incorporate knowledge about which 963 confusions are likely with ESL learners into the error correction system is to train a model on error-tagged data. [sent-97, score-0.656]
42 Preposition confusions observed in the nonnative text can then be included in training, by using the preposition chosen by the author (the source preposition) as a feature. [sent-98, score-0.892]
43 This is not possible with a system trained on native data, because each source preposition is always the correct preposition. [sent-99, score-0.824]
44 Gamon (2010) proposes a hybrid system for preposition and article correction, by incorporating the scores of a language model and class probabilities of a maximum entropy model, both trained on native data, into a meta-classifier that is trained on a smaller amount of annotated ESL data. [sent-105, score-0.896]
45 The metaclassifier outperforms by a large margin both of the native models, but it requires large amounts of expensive annotated data, especially in order to correct preposition errors, where the problem complexity is much larger. [sent-106, score-0.762]
46 Rozovskaya and Roth (2010b) show that by introducing into native training data artificial article errors it is possible to improve the performance of the article correction system, when compared to a classifier trained on native data. [sent-107, score-0.879]
47 (2010) that use annotated data for training, the system is trained on native data, but the native data are transformed to be more like L1 data through artificial article errors that mimic the error rates and error patterns of non-native writers. [sent-109, score-0.68]
48 Unlike article errors, preposition errors lend themselves very well to a study of confusion sets because the set of prepositions participating in the task is a lot bigger than the set of article choices. [sent-113, score-1.441]
49 In the Cambridge Learner Corpus2 (CLC), which contains data by learners of different first language backgrounds and different proficiency levels, preposition errors account for about 13. [sent-116, score-0.954]
50 Learning correct preposition usage in English is challenging for learners of all first language backgrounds (Dalgish, 1985; Bitchener et al. [sent-124, score-0.809]
51 For each preposition used incorrectly by the author, the annotator also indicated the correct preposition choice. [sent-130, score-1.241]
52 Table 1 shows preposition statistics based on the annotated data. [sent-136, score-0.643]
53 Column Incorrect denotes the number of prepositions judged to be incorrect by the native annotators. [sent-147, score-0.394]
54 3 Preposition Errors and L1 We focus on preposition confusion errors, mistakes that involve an incorrectly selected preposition4. [sent-155, score-0.901]
55 We mentioned in Section 2 that not all preposition confusions are equally likely to occur and preposition errors may depend on the first language of the writer. [sent-157, score-1.514]
56 (2010) show that preposition errors in the annotated corpus by Korean learners are not evenly distributed, some confusions occurring more often than others. [sent-159, score-1.025]
57 5It is common to restrict the systems that detect errors in preposition usage to the top prepositions. [sent-166, score-0.774]
58 In the CLC corpus, the usage of the ten most frequent prepositions accounts for 82% of all preposition errors (Leacock et al. [sent-167, score-1.063]
59 For the preposition correction task, the standard approach considers all prepositions participating in the task as valid corrections for every preposition in the non-native data. [sent-170, score-2.035]
60 3, we pointed out that (1) not all preposition confusions are equally likely to occur and (2) preposition errors may depend on the first language of the writer. [sent-172, score-1.514]
61 The methods of restricting confusion sets proposed in this work use knowledge about which prepositions are confusable based on the data by speakers of language L1. [sent-173, score-0.764]
62 We refer to the preposition originally chosen by the author in the non-native text as the source preposition, and label denotes the correct preposition choice, as chosen by the annotator. [sent-174, score-1.283]
63 In example 1, the annotator replaced by with with; by is the source preposition and with is the label. [sent-182, score-0.651]
64 In example 3, the preposition with is judged as correct. [sent-184, score-0.633]
65 1 L1-Dependent Confusion Sets Let source preposition pi denote a preposition that appears in the data by speakers of L1. [sent-187, score-1.521]
66 Let ConfSet denote the set of all prepositions that the system can propose as a correction for source preposition pi. [sent-188, score-1.226]
67 L1-dependent confusion set L1ConfSet(pi) is defined as follows: Definition L1ConfSet(pi) = {pj |∃ a sentence in which an L1 writer replaced preposition pj nwteitnhc pi } For example, in the Spanish speaker data, from is used incorrectly in place of of and for. [sent-191, score-1.069]
68 epi{L 1o wfCn,it foharn,ob fmoSyue,t fi,n(o pr}fi,)to,at in,with,by} Table 2: L1-dependent confusion sets for three prepositions based on data by Chinese speakers. [sent-194, score-0.543]
69 Table 2 shows for Chinese speakers three prepositions and their L1-dependent confusion sets. [sent-195, score-0.58]
70 NegAll Training proceeds in a standard way of training a multi-class classifier (one-vs-all approach) on all ten prepositions using wellformed native English data. [sent-201, score-0.532]
71 For each preposition pi, pi examples are positive and the other nine prepositions are negative examples. [sent-202, score-1.163]
72 For every preposition pi, we train a classifier using only examples that are in L1ConfSet(pi). [sent-205, score-0.748]
73 For source preposition pi in test, we consult the classifier for pi. [sent-208, score-0.923]
74 In this model, the con- fusion set for source pi is restricted through training, since for source pi, the possible candidate replacements are only those that the classifier sees in training, and they are all in L1ConfSet(pi). [sent-209, score-0.487]
75 ErrorL1 This method restricts the candidate set to L1ConfSet(pi) by generating artificial preposition errors in the spirit of Rozovskaya and Roth (2010b). [sent-211, score-0.903]
76 Specifically, each preposition pi in training is replaced with a different preposition pj with probability probConf, s. [sent-213, score-1.433]
77 The classifier uses in training the source preposition as a feature, which cannot be done when training on well-formed text, as discussed in Section 2. [sent-218, score-0.746]
78 By providing the source preposition as a feature, we enforce L1-dependent confusion sets in training, because the system learns which candidate corrections occur with source preposition pi. [sent-220, score-1.906]
79 An important distinction of this approach is that it does not simply provide L1-dependent confusion sets in training: Because errors are generated using L1 writers’ error statistics, the likelihood of each candidate correction is also provided. [sent-221, score-0.842]
80 , 2001), and propose a correction only when the confidence ofthe classifier is above the threshold. [sent-227, score-0.393]
81 ThreshAll A correction for source preposition pi is proposed only when the confidence of the classifier exceeds the threshold. [sent-231, score-1.221]
82 For each preposition in the non-native data, this method considers all candidates as valid corrections. [sent-232, score-0.682]
83 ThreshL1Conf A correction for source preposition pi is proposed only when the confi- dence of the classifier exceeds the empirically found threshold and the preposition proposed as a correction for pi is in the confusion set L1ConfSet(pi). [sent-234, score-2.53]
84 NegAll-Clean-ThreshAll This system assumes both in training and in testing stages that all preposition confusions are possible. [sent-238, score-0.827]
85 The system is trained as a multi-class 10-way classifier, where for each preposition pi, all other nine prepositions are negative examples. [sent-239, score-1.02]
86 NegL1-Clean-ThreshL1 For each preposition pi, a separate classifier is trained on the prepositions that are in L1ConfSet(pi), where pi examples are positive and a set of (fewer than nine) pi-dependent prepositions are negative. [sent-247, score-1.481]
87 Only corrections that belong to L1ConfSet(pi) are considered as valid corrections for Ten pi-dependent classifiers for each L1 are trained. [sent-248, score-0.429]
88 NegAll-ErrorL1-NoThresh A system is trained as a multi-class 10-way classifier with artificial preposition errors that mimic the errors rates and confusion patterns of the non-native text. [sent-251, score-1.304]
89 It assumes both in training and in testing that all preposition confusions are possible. [sent-256, score-0.805]
90 Features are extracted from a window of eight words around the preposition and include words, part-of-speech tags and conjunctions of words and tags of lengths two, three, and four. [sent-258, score-0.609]
91 For each source language, the methods that restrict candidate sets in training or testing outperform the baseline system NegAll-Clean-ThreshAll that does not restrict candidate sets. [sent-270, score-0.455]
92 We hypothesize that the NegAllClean-ThreshAll performance may be affected because the classifiers for different source prepositions contain different number of classes, depending on the size of L1ConfSet confusion sets, which makes it more difficult to find a unified threshold. [sent-287, score-0.538]
93 Moreover, while restricting candidate sets improves the results, providing information to the classifier about the likelihoods of different confusions is more helpful, which is reflected in the precision differences between NegAll-CleanThreshL1 and NegAll-ErrorL1-ThreshL1. [sent-317, score-0.573]
94 969 7 Conclusion and Future Work In this paper, we proposed methods for improving candidate sets for the task of detecting and correcting errors in text. [sent-340, score-0.383]
95 To correct errors in preposition usage made by non-native speakers of English, we proposed L1-dependent confusion sets that determine valid candidate corrections using knowledge about preposition confusions observed in the nonnative text. [sent-341, score-2.327]
96 Gamon (2010) also considers missing and extraneous preposition errors. [sent-343, score-0.651]
97 Furthermore, the approach that takes into account the likelihood of each preposition confusion is shown to be the most effective. [sent-345, score-0.851]
98 A classifier-based approach to preposition and determiner error correction in L2 English. [sent-418, score-0.944]
99 The ups and downs of preposition error detection in ESL writing. [sent-537, score-0.665]
100 Using parse features for preposition selection and error detection. [sent-544, score-0.665]
wordName wordTfidf (topN-words)
[('preposition', 0.609), ('correction', 0.279), ('prepositions', 0.274), ('confusion', 0.222), ('corrections', 0.182), ('pi', 0.177), ('confusions', 0.17), ('esl', 0.164), ('rozovskaya', 0.142), ('tetreault', 0.133), ('candidate', 0.131), ('errors', 0.107), ('learners', 0.105), ('gamon', 0.104), ('correcting', 0.098), ('native', 0.096), ('classifier', 0.095), ('felice', 0.085), ('leacock', 0.085), ('speakers', 0.084), ('restricting', 0.08), ('article', 0.071), ('negall', 0.071), ('nonnative', 0.071), ('proficiency', 0.071), ('chodorow', 0.071), ('mistakes', 0.07), ('han', 0.069), ('spelling', 0.069), ('roth', 0.068), ('carlson', 0.062), ('nine', 0.057), ('confusable', 0.057), ('enforcing', 0.056), ('error', 0.056), ('unrestricted', 0.05), ('pulman', 0.048), ('sets', 0.047), ('rates', 0.045), ('ten', 0.043), ('backgrounds', 0.042), ('bitchener', 0.042), ('extraneous', 0.042), ('izumi', 0.042), ('source', 0.042), ('essays', 0.042), ('valid', 0.042), ('threshold', 0.041), ('learner', 0.041), ('participating', 0.04), ('pj', 0.038), ('rizzolo', 0.036), ('golding', 0.036), ('annotated', 0.034), ('mimic', 0.033), ('freund', 0.033), ('trained', 0.032), ('artificial', 0.032), ('chinese', 0.032), ('candidates', 0.031), ('precision', 0.03), ('korean', 0.03), ('usage', 0.03), ('curves', 0.029), ('clc', 0.028), ('dalgish', 0.028), ('elghaari', 0.028), ('fette', 0.028), ('probconf', 0.028), ('threshall', 0.028), ('russian', 0.028), ('banko', 0.028), ('writers', 0.028), ('restrict', 0.028), ('perceptron', 0.027), ('testing', 0.026), ('negative', 0.026), ('czech', 0.024), ('wellformed', 0.024), ('granger', 0.024), ('gui', 0.024), ('spirit', 0.024), ('judged', 0.024), ('train', 0.024), ('recall', 0.024), ('belong', 0.023), ('correct', 0.023), ('speaker', 0.023), ('clean', 0.022), ('cite', 0.022), ('sight', 0.022), ('system', 0.022), ('english', 0.021), ('account', 0.02), ('likelihoods', 0.02), ('schapire', 0.02), ('mcnemar', 0.02), ('examples', 0.02), ('equally', 0.019), ('confidence', 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 54 emnlp-2010-Generating Confusion Sets for Context-Sensitive Error Correction
Author: Alla Rozovskaya ; Dan Roth
Abstract: In this paper, we consider the problem of generating candidate corrections for the task of correcting errors in text. We focus on the task of correcting errors in preposition usage made by non-native English speakers, using discriminative classifiers. The standard approach to the problem assumes that the set of candidate corrections for a preposition consists of all preposition choices participating in the task. We determine likely preposition confusions using an annotated corpus of nonnative text and use this knowledge to produce smaller sets of candidates. We propose several methods of restricting candidate sets. These methods exclude candidate prepositions that are not observed as valid corrections in the annotated corpus and take into account the likelihood of each preposition confusion in the non-native text. We find that restricting candidates to those that are ob- served in the non-native data improves both the precision and the recall compared to the approach that views all prepositions as possible candidates. Furthermore, the approach that takes into account the likelihood of each preposition confusion is shown to be the most effective.
2 0.20836684 95 emnlp-2010-SRL-Based Verb Selection for ESL
Author: Xiaohua Liu ; Bo Han ; Kuan Li ; Stephan Hyeonjun Stiller ; Ming Zhou
Abstract: In this paper we develop an approach to tackle the problem of verb selection for learners of English as a second language (ESL) by using features from the output of Semantic Role Labeling (SRL). Unlike existing approaches to verb selection that use local features such as n-grams, our approach exploits semantic features which explicitly model the usage context of the verb. The verb choice highly depends on its usage context which is not consistently captured by local features. We then combine these semantic features with other local features under the generalized perceptron learning framework. Experiments on both indomain and out-of-domain corpora show that our approach outperforms the baseline and achieves state-of-the-art performance. 1
3 0.11536229 56 emnlp-2010-Hashing-Based Approaches to Spelling Correction of Personal Names
Author: Raghavendra Udupa ; Shaishav Kumar
Abstract: We propose two hashing-based solutions to the problem of fast and effective personal names spelling correction in People Search applications. The key idea behind our methods is to learn hash functions that map similar names to similar (and compact) binary codewords. The two methods differ in the data they use for learning the hash functions - the first method uses a set of names in a given language/script whereas the second uses a set of bilingual names. We show that both methods give excellent retrieval performance in comparison to several baselines on two lists of misspelled personal names. More over, the method that uses bilingual data for learning hash functions gives the best performance.
4 0.077457517 104 emnlp-2010-The Necessity of Combining Adaptation Methods
Author: Ming-Wei Chang ; Michael Connor ; Dan Roth
Abstract: Problems stemming from domain adaptation continue to plague the statistical natural language processing community. There has been continuing work trying to find general purpose algorithms to alleviate this problem. In this paper we argue that existing general purpose approaches usually only focus on one of two issues related to the difficulties faced by adaptation: 1) difference in base feature statistics or 2) task differences that can be detected with labeled data. We argue that it is necessary to combine these two classes of adaptation algorithms, using evidence collected through theoretical analysis and simulated and real-world data experiments. We find that the combined approach often outperforms the individual adaptation approaches. By combining simple approaches from each class of adaptation algorithm, we achieve state-of-the-art results for both Named Entity Recognition adaptation task and the Preposition Sense Disambiguation adaptation task. Second, we also show that applying an adaptation algorithm that finds shared representation between domains often impacts the choice in adaptation algorithm that makes use of target labeled data.
5 0.046882059 62 emnlp-2010-Improving Mention Detection Robustness to Noisy Input
Author: Radu Florian ; John Pitrelli ; Salim Roukos ; Imed Zitouni
Abstract: Information-extraction (IE) research typically focuses on clean-text inputs. However, an IE engine serving real applications yields many false alarms due to less-well-formed input. For example, IE in a multilingual broadcast processing system has to deal with inaccurate automatic transcription and translation. The resulting presence of non-target-language text in this case, and non-language material interspersed in data from other applications, raise the research problem of making IE robust to such noisy input text. We address one such IE task: entity-mention detection. We describe augmenting a statistical mention-detection system in order to reduce false alarms from spurious passages. The diverse nature of input noise leads us to pursue a multi-faceted approach to robustness. For our English-language system, at various miss rates we eliminate 97% of false alarms on inputs from other Latin-alphabet languages. In another experiment, representing scenarios in which genre-specific training is infeasible, we process real financial-transactions text containing mixed languages and data-set codes. On these data, because we do not train on data like it, we achieve a smaller but significant improvement. These gains come with virtually no loss in accuracy on clean English text.
6 0.046026785 33 emnlp-2010-Cross Language Text Classification by Model Translation and Semi-Supervised Learning
7 0.045309909 35 emnlp-2010-Discriminative Sample Selection for Statistical Machine Translation
8 0.043400604 85 emnlp-2010-Negative Training Data Can be Harmful to Text Classification
9 0.041964568 50 emnlp-2010-Facilitating Translation Using Source Language Paraphrase Lattices
10 0.041798089 4 emnlp-2010-A Game-Theoretic Approach to Generating Spatial Descriptions
11 0.038210791 119 emnlp-2010-We're Not in Kansas Anymore: Detecting Domain Changes in Streams
12 0.037369248 46 emnlp-2010-Evaluating the Impact of Alternative Dependency Graph Encodings on Solving Event Extraction Tasks
13 0.036942378 53 emnlp-2010-Fusing Eye Gaze with Speech Recognition Hypotheses to Resolve Exophoric References in Situated Dialogue
14 0.036272585 21 emnlp-2010-Automatic Discovery of Manner Relations and its Applications
15 0.03530369 63 emnlp-2010-Improving Translation via Targeted Paraphrasing
16 0.034281421 69 emnlp-2010-Joint Training and Decoding Using Virtual Nodes for Cascaded Segmentation and Tagging Tasks
17 0.033337906 114 emnlp-2010-Unsupervised Parse Selection for HPSG
18 0.033281632 39 emnlp-2010-EMNLP 044
19 0.031817306 9 emnlp-2010-A New Approach to Lexical Disambiguation of Arabic Text
20 0.031373836 18 emnlp-2010-Assessing Phrase-Based Translation Models with Oracle Decoding
topicId topicWeight
[(0, 0.129), (1, 0.034), (2, -0.02), (3, 0.145), (4, -0.074), (5, 0.003), (6, 0.034), (7, -0.154), (8, 0.05), (9, 0.092), (10, -0.06), (11, 0.197), (12, -0.086), (13, 0.032), (14, 0.046), (15, 0.005), (16, 0.011), (17, -0.005), (18, -0.007), (19, 0.157), (20, -0.106), (21, -0.217), (22, -0.117), (23, 0.186), (24, -0.011), (25, -0.058), (26, 0.138), (27, 0.12), (28, 0.081), (29, 0.101), (30, -0.255), (31, -0.076), (32, 0.02), (33, -0.038), (34, 0.108), (35, -0.12), (36, 0.052), (37, 0.068), (38, -0.1), (39, 0.101), (40, -0.095), (41, 0.041), (42, 0.047), (43, 0.428), (44, 0.053), (45, 0.07), (46, -0.023), (47, 0.142), (48, -0.04), (49, -0.168)]
simIndex simValue paperId paperTitle
same-paper 1 0.97578633 54 emnlp-2010-Generating Confusion Sets for Context-Sensitive Error Correction
Author: Alla Rozovskaya ; Dan Roth
Abstract: In this paper, we consider the problem of generating candidate corrections for the task of correcting errors in text. We focus on the task of correcting errors in preposition usage made by non-native English speakers, using discriminative classifiers. The standard approach to the problem assumes that the set of candidate corrections for a preposition consists of all preposition choices participating in the task. We determine likely preposition confusions using an annotated corpus of nonnative text and use this knowledge to produce smaller sets of candidates. We propose several methods of restricting candidate sets. These methods exclude candidate prepositions that are not observed as valid corrections in the annotated corpus and take into account the likelihood of each preposition confusion in the non-native text. We find that restricting candidates to those that are ob- served in the non-native data improves both the precision and the recall compared to the approach that views all prepositions as possible candidates. Furthermore, the approach that takes into account the likelihood of each preposition confusion is shown to be the most effective.
2 0.50254124 95 emnlp-2010-SRL-Based Verb Selection for ESL
Author: Xiaohua Liu ; Bo Han ; Kuan Li ; Stephan Hyeonjun Stiller ; Ming Zhou
Abstract: In this paper we develop an approach to tackle the problem of verb selection for learners of English as a second language (ESL) by using features from the output of Semantic Role Labeling (SRL). Unlike existing approaches to verb selection that use local features such as n-grams, our approach exploits semantic features which explicitly model the usage context of the verb. The verb choice highly depends on its usage context which is not consistently captured by local features. We then combine these semantic features with other local features under the generalized perceptron learning framework. Experiments on both indomain and out-of-domain corpora show that our approach outperforms the baseline and achieves state-of-the-art performance. 1
3 0.38151208 56 emnlp-2010-Hashing-Based Approaches to Spelling Correction of Personal Names
Author: Raghavendra Udupa ; Shaishav Kumar
Abstract: We propose two hashing-based solutions to the problem of fast and effective personal names spelling correction in People Search applications. The key idea behind our methods is to learn hash functions that map similar names to similar (and compact) binary codewords. The two methods differ in the data they use for learning the hash functions - the first method uses a set of names in a given language/script whereas the second uses a set of bilingual names. We show that both methods give excellent retrieval performance in comparison to several baselines on two lists of misspelled personal names. More over, the method that uses bilingual data for learning hash functions gives the best performance.
4 0.35690919 4 emnlp-2010-A Game-Theoretic Approach to Generating Spatial Descriptions
Author: Dave Golland ; Percy Liang ; Dan Klein
Abstract: Language is sensitive to both semantic and pragmatic effects. To capture both effects, we model language use as a cooperative game between two players: a speaker, who generates an utterance, and a listener, who responds with an action. Specifically, we consider the task of generating spatial references to objects, wherein the listener must accurately identify an object described by the speaker. We show that a speaker model that acts optimally with respect to an explicit, embedded listener model substantially outperforms one that is trained to directly generate spatial descriptions.
5 0.2779519 45 emnlp-2010-Evaluating Models of Latent Document Semantics in the Presence of OCR Errors
Author: Daniel Walker ; William B. Lund ; Eric K. Ringger
Abstract: Models of latent document semantics such as the mixture of multinomials model and Latent Dirichlet Allocation have received substantial attention for their ability to discover topical semantics in large collections of text. In an effort to apply such models to noisy optical character recognition (OCR) text output, we endeavor to understand the effect that character-level noise can have on unsupervised topic modeling. We show the effects both with document-level topic analysis (document clustering) and with word-level topic analysis (LDA) on both synthetic and real-world OCR data. As expected, experimental results show that performance declines as word error rates increase. Common techniques for alleviating these problems, such as filtering low-frequency words, are successful in enhancing model quality, but exhibit failure trends similar to models trained on unpro- cessed OCR output in the case of LDA. To our knowledge, this study is the first of its kind.
6 0.21688302 35 emnlp-2010-Discriminative Sample Selection for Statistical Machine Translation
7 0.21434639 104 emnlp-2010-The Necessity of Combining Adaptation Methods
8 0.19747975 62 emnlp-2010-Improving Mention Detection Robustness to Noisy Input
9 0.19568361 117 emnlp-2010-Using Unknown Word Techniques to Learn Known Words
10 0.18052451 9 emnlp-2010-A New Approach to Lexical Disambiguation of Arabic Text
11 0.17251885 103 emnlp-2010-Tense Sense Disambiguation: A New Syntactic Polysemy Task
12 0.16427198 71 emnlp-2010-Latent-Descriptor Clustering for Unsupervised POS Induction
13 0.16372727 119 emnlp-2010-We're Not in Kansas Anymore: Detecting Domain Changes in Streams
14 0.15532283 2 emnlp-2010-A Fast Decoder for Joint Word Segmentation and POS-Tagging Using a Single Discriminative Model
15 0.15219007 91 emnlp-2010-Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding
16 0.14991003 85 emnlp-2010-Negative Training Data Can be Harmful to Text Classification
17 0.14318387 114 emnlp-2010-Unsupervised Parse Selection for HPSG
18 0.14013994 53 emnlp-2010-Fusing Eye Gaze with Speech Recognition Hypotheses to Resolve Exophoric References in Situated Dialogue
19 0.13385645 106 emnlp-2010-Top-Down Nearly-Context-Sensitive Parsing
20 0.13012961 72 emnlp-2010-Learning First-Order Horn Clauses from Web Text
topicId topicWeight
[(3, 0.011), (5, 0.399), (10, 0.012), (12, 0.098), (29, 0.073), (30, 0.019), (52, 0.018), (56, 0.062), (66, 0.102), (72, 0.056), (76, 0.025), (87, 0.013), (89, 0.016)]
simIndex simValue paperId paperTitle
same-paper 1 0.71974736 54 emnlp-2010-Generating Confusion Sets for Context-Sensitive Error Correction
Author: Alla Rozovskaya ; Dan Roth
Abstract: In this paper, we consider the problem of generating candidate corrections for the task of correcting errors in text. We focus on the task of correcting errors in preposition usage made by non-native English speakers, using discriminative classifiers. The standard approach to the problem assumes that the set of candidate corrections for a preposition consists of all preposition choices participating in the task. We determine likely preposition confusions using an annotated corpus of nonnative text and use this knowledge to produce smaller sets of candidates. We propose several methods of restricting candidate sets. These methods exclude candidate prepositions that are not observed as valid corrections in the annotated corpus and take into account the likelihood of each preposition confusion in the non-native text. We find that restricting candidates to those that are ob- served in the non-native data improves both the precision and the recall compared to the approach that views all prepositions as possible candidates. Furthermore, the approach that takes into account the likelihood of each preposition confusion is shown to be the most effective.
2 0.58850354 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
3 0.39467293 95 emnlp-2010-SRL-Based Verb Selection for ESL
Author: Xiaohua Liu ; Bo Han ; Kuan Li ; Stephan Hyeonjun Stiller ; Ming Zhou
Abstract: In this paper we develop an approach to tackle the problem of verb selection for learners of English as a second language (ESL) by using features from the output of Semantic Role Labeling (SRL). Unlike existing approaches to verb selection that use local features such as n-grams, our approach exploits semantic features which explicitly model the usage context of the verb. The verb choice highly depends on its usage context which is not consistently captured by local features. We then combine these semantic features with other local features under the generalized perceptron learning framework. Experiments on both indomain and out-of-domain corpora show that our approach outperforms the baseline and achieves state-of-the-art performance. 1
4 0.39192834 101 emnlp-2010-Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval
Author: David Guthrie ; Mark Hepple
Abstract: We present three novel methods of compactly storing very large n-gram language models. These methods use substantially less space than all known approaches and allow n-gram probabilities or counts to be retrieved in constant time, at speeds comparable to modern language modeling toolkits. Our basic approach generates an explicit minimal perfect hash function, that maps all n-grams in a model to distinct integers to enable storage of associated values. Extensions of this approach exploit distributional characteristics of n-gram data to reduce storage costs, including variable length coding of values and the use of tiered structures that partition the data for more efficient storage. We apply our approach to storing the full Google Web1T n-gram set and all 1-to-5 grams of the Gigaword newswire corpus. For the 1.5 billion n-grams of Gigaword, for example, we can store full count information at a cost of 1.66 bytes per n-gram (around 30% of the cost when using the current stateof-the-art approach), or quantized counts for 1.41 bytes per n-gram. For applications that are tolerant of a certain class of relatively innocuous errors (where unseen n-grams may be accepted as rare n-grams), we can reduce the latter cost to below 1byte per n-gram.
5 0.37506482 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.37292549 79 emnlp-2010-Mining Name Translations from Entity Graph Mapping
7 0.36608037 49 emnlp-2010-Extracting Opinion Targets in a Single and Cross-Domain Setting with Conditional Random Fields
8 0.36549118 69 emnlp-2010-Joint Training and Decoding Using Virtual Nodes for Cascaded Segmentation and Tagging Tasks
9 0.36517155 92 emnlp-2010-Predicting the Semantic Compositionality of Prefix Verbs
10 0.36107647 63 emnlp-2010-Improving Translation via Targeted Paraphrasing
11 0.36080244 20 emnlp-2010-Automatic Detection and Classification of Social Events
12 0.36006585 86 emnlp-2010-Non-Isomorphic Forest Pair Translation
13 0.36000159 45 emnlp-2010-Evaluating Models of Latent Document Semantics in the Presence of OCR Errors
14 0.35953251 107 emnlp-2010-Towards Conversation Entailment: An Empirical Investigation
15 0.35941637 105 emnlp-2010-Title Generation with Quasi-Synchronous Grammar
16 0.35932839 84 emnlp-2010-NLP on Spoken Documents Without ASR
17 0.3584938 65 emnlp-2010-Inducing Probabilistic CCG Grammars from Logical Form with Higher-Order Unification
18 0.35751313 82 emnlp-2010-Multi-Document Summarization Using A* Search and Discriminative Learning
19 0.35689628 78 emnlp-2010-Minimum Error Rate Training by Sampling the Translation Lattice
20 0.3565737 120 emnlp-2010-What's with the Attitude? Identifying Sentences with Attitude in Online Discussions