emnlp emnlp2013 emnlp2013-14 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Steven Bethard
Abstract: We present an approach to time normalization (e.g. the day before yesterday⇒20 13-04- 12) based on a synchronous contex⇒t free grammar. Synchronous rules map the source language to formally defined operators for manipulating times (FINDENCLOSED, STARTATENDOF, etc.). Time expressions are then parsed using an extended CYK+ algorithm, and converted to a normalized form by applying the operators recursively. For evaluation, a small set of synchronous rules for English time expressions were developed. Our model outperforms HeidelTime, the best time normalization system in TempEval 2013, on four different time normalization corpora.
Reference: text
sentIndex sentText sentNum sentScore
1 A synchronous context free grammar for time normalization Steven Bethard University of Alabama at Birmingham Birmingham, Alabama, USA bethard@ cis . [sent-1, score-0.463]
2 edu Abstract We present an approach to time normalization (e. [sent-3, score-0.149]
3 the day before yesterday⇒20 13-04- 12) based on a synchronous contex⇒t free grammar. [sent-5, score-0.295]
4 Synchronous rules map the source language to formally defined operators for manipulating times (FINDENCLOSED, STARTATENDOF, etc. [sent-6, score-0.128]
5 Time expressions are then parsed using an extended CYK+ algorithm, and converted to a normalized form by applying the operators recursively. [sent-8, score-0.084]
6 For evaluation, a small set of synchronous rules for English time expressions were developed. [sent-9, score-0.295]
7 Our model outperforms HeidelTime, the best time normalization system in TempEval 2013, on four different time normalization corpora. [sent-10, score-0.298]
8 1 Introduction Time normalization is the task of converting a natural language expression of time into a formal representation of a time on a timeline. [sent-11, score-0.275]
9 For example, the expres- sion the day before yesterday would be normalized to the formal representation 2013-04- 12 (assuming that today is 20 13-04- 14) in the ISO-TimeML representation language (Pustejovsky et al. [sent-12, score-0.301]
10 Time normalization is a crucial part of almost any information extraction task that needs to place entities or events along a timeline. [sent-14, score-0.112]
11 And research into methods for time normalization has been growing since the ACE1 and TempEval (Verhagen et al. [sent-15, score-0.149]
12 , 2013) challenges began to include time normalization as a shared task. [sent-17, score-0.149]
13 gov/ i ad/mig/t e st s / ace / 821 Most prior work on time normalization has taken a rule-based, string-to-string translation approach. [sent-21, score-0.149]
14 That is, each word in a time expression is looked up in a normalization lexicon, and then rules map this sequence of lexical entries directly to the normalized form. [sent-22, score-0.29]
15 A drawback of this approach though is that there is no nesting of rules: for example, in HeidelTime the rules for yesterday and the day before yesterday are completely separate, despite the compositional nature of the latter. [sent-25, score-0.382]
16 They define a target grammar of typed pre-terminals, such as YESTERDAY (a SEQUENCE) or DAY (a DURATION), and compositional operations, such as SHIFTLEFT (a (RANGE, DURATION) → RANGE). [sent-28, score-0.16]
17 They apply an expectation-maximization approach to learn how words align to elements of the target grammar, and achieve performance close to that of the rule-based systems. [sent-29, score-0.035]
18 However, their grammar does not allow for non-binary or partially lexicalized rules (e. [sent-30, score-0.213]
19 SEQUENCE → DURATION before SEQUENCE would be impossible), and some of their primitive elements could naturally be expressed using other primitives (e. [sent-32, score-0.048]
20 We present a synchronous grammar for time normalization that addresses these shortcomings. [sent-35, score-0.434]
21 We first define a grammar of formal operations over temporal elements. [sent-36, score-0.202]
22 We then develop synchronous rules that map time expression words to temporal opera- ProceSeedatintlges, o Wfa tshhein 2g01to3n, C UoSnfAe,re 1n8c-e2 o1n O Ecmtopbier ic 2a0l1 M3. [sent-37, score-0.363]
23 tors, and perform normalization by parsing with an extended CYK+ parsing algorithm. [sent-41, score-0.202]
24 We evaluate this approach to time normalization on the TimeBank, AQUAINT, Timen and TempEval 2013 corpora. [sent-42, score-0.149]
25 2 Synchronous grammars Our time grammar is based on the synchronous context free grammar formalism. [sent-43, score-0.476]
26 Synchronous grammars allow two trees, one in the source language and one in the target language, to be constructed simultaneously. [sent-44, score-0.093]
27 For time normalization, the source side is the natural language text, and the target side is a formal grammar of temporal operators. [sent-46, score-0.394]
28 Figure 1 shows a synchronous parse of the week of March 6 2. [sent-47, score-0.315]
29 The left side is the source side (an English expression), the right side is the target side (a temporal operator expression), and the alignment is shown via subscripts. [sent-48, score-0.286]
30 2Figure 1corresponds to an interpretation along the lines of the week of the last March 6. [sent-49, score-0.078]
31 The full grammar developed in this article would also produce an interpretation corresponding to the week of the next March 6, since the phrase is ambiguous. [sent-50, score-0.203]
32 822 3 Target time grammar The right side of Figure 1 shows an example of our target formal representation: FINDENCLOSING( FINDEARLIER(PRESENT, MONTHOFYEAR→3, DAYOFMONTH→6), WEEKS). [sent-51, score-0.272]
33 Each termina→l in the parse is eith→er a numeric value or an operator like FINDENCLOSING, WEEKS or MONTHOFYEAR. [sent-52, score-0.105]
34 Each non-terminal combines terminals or non-terminals to create a [TIMESPAN] , [PERIOD], [FIELD], [UNIT] or [INT]. [sent-53, score-0.117]
35 The list of rules allowed by our target grammar (the right-hand side of our synchronous grammar) is given in Table 1. [sent-54, score-0.427]
36 Each of the target operators defines a procedure for creating a temporal object from others. [sent-55, score-0.11]
37 For example, FINDENCLOSING takes a [TIMESPAN] and a [UNIT] and expands the start and end of the time span to fill a period of one unit. [sent-56, score-0.151]
38 This could be used, for example, to define today as FINDENCLOSING(PRESENT, DAYS), where the PRESENT, which is instantaneous, is expanded out to the enclosing day. [sent-57, score-0.037]
39 Note that we define things like today and yesterday in terms of primitive operations, rather than making them primitives themselves as in (Angeli et al. [sent-58, score-0.191]
40 The left side of Figure 1 shows the synchronous parse of the source language. [sent-60, score-0.314]
41 Each non-terminal thus corresponds to a synchronous grammar rule that describes how a source expression should be translated into the target time grammar. [sent-77, score-0.448]
42 Only a small amount of bookkeeping is necessary to allow the generation of the target parse once the source parse is complete. [sent-79, score-0.247]
43 We can therefore apply standard parsing algorithms to this task. [sent-80, score-0.045]
44 This means that we can’t directly use CYK parsing or even CYK+ parsing (Chappelier and Rajman, 1998), which allows rules that expand into more than two terminals or non-terminals, but does not meet our other requirements. [sent-83, score-0.271]
45 As with standard CYK+ parsing, two charts are filled, one for rules that have been completed (C) and one for rules that have been only partially advanced (P). [sent-85, score-0.158]
46 All parses covering 1terminal are completed first, then these are used to complete parses covering 2 terminals, etc. [sent-86, score-0.266]
47 Our extensions to the standard CYK+ parsing are as follows. [sent-88, score-0.045]
48 To handle integers, we modify the initialization to generate new rules on the fly for any numeric terminals that fit the range of an [INT:X-Y] non-terminal in the grammar (starts at line 5). [sent-89, score-0.354]
49 To allow mixing of terminals and non-terminals, we extend the initialization step to also produce partial parses (line 17), and extend the parse advancement step to allow advancing rules with terminals (starting at line 23). [sent-90, score-0.603]
50 Finally, to handle [NIL] rules, which consume tokens but are not included in the final parse, we add a step where rules are allowed to advance, unchanged, past a [NIL] rule (starting at line 35). [sent-91, score-0.084]
51 (E|wR(|w −i) 1th) edno 7: for all [INT:x-y] ∈ non-terminals of G do 8: if x ≤ TO:xN-UyM] ∈BE nRo(nw-tei)r m≤i y ltsh eofn 9: C(1,i) [INT:x-y] →) ≤ wi 10: // Start any rules that begin with terminals 11: for i ← 0 . [sent-99, score-0.214]
52 ( αwβ| − −∈ 1G) ddoo 13: rif a ∃llj X X| α →= α wi:j ∧G ¬ doISTERMINAL(β0) then 14: ∃ifj β | =α ? [sent-104, score-0.048]
53 t when 15: C(|wi:j |,i) X → wi:jα 16: else 17: P(|wi:j |,i) (|wi:j |, X → wi:jα) 18: for n ← 1. [sent-105, score-0.032]
54 n→ d αo) ∈ P(m,i) do 22: r// a aAlld (vpa,nXce → partial parses using terminals 23: if wi+m:i+n = αp:p+n−m then 24: if αp+n−m: |α | = ? [sent-121, score-0.277]
55 →th Xenα C(n,i) ∪= Y → Xα else P(n,i) ∪= (1, Y → Xα) return C(|w|,0) = (|w|,0) 824 (The • is the visual equivalent of the first element in the pa•rtial parse tuples of Algorithm 1, which marks parsing progress. [sent-123, score-0.154]
56 ) And given the [INT: 1-3 1] at C(1,4) the algorithm can make a complete size 1parse: C(1,4) ∪= [DAY] → [INT: 1-3 1] The algorithm then moves on to create parses that span 2 tokens. [sent-124, score-0.142]
57 Both of these yield: C(5,0) ∪= [TIMESPAN] → [UNIT] of [TIMESPAN] The complete parses in C(5,0) are then deterministically translated into target side parses using the alignments in the rules of the synchronous grammar. [sent-127, score-0.524]
58 6 Evaluation Using our synchronous grammar formalism for time normalization, we manually developed a grammar for English time expressions. [sent-128, score-0.484]
59 Following the lead of TIMEN and HeidelTime, we developed our grammar by inspecting examples from the AQUAINT4 and 4http : / /www . [sent-129, score-0.125]
60 cat alogI d=LDC2 0 0 2 T3 1 N TIMEN HeidelTime SCFG AQUAINT65269. [sent-134, score-0.021]
61 6 Table 2: Performance of TIMEN, HeidelTime and our synchronous context free grammar (SCFG) on each evaluation corpus. [sent-146, score-0.314]
62 The resulting grammar has 354 rules, 192 of which are only lexical, e. [sent-150, score-0.125]
63 Our grammar produces multiple parses when the input is ambiguous. [sent-153, score-0.236]
64 For example, the expression Monday could mean either the previous Monday or the following Monday, and the expression the day could refer either to a period of one day, or to a specific day in time, e. [sent-154, score-0.414]
65 To choose between the two, we employ a very simple set of heuristics: (1) prefer [TIMESPAN] to [PERIOD], (2) prefer an earlier [TIMESPAN] to a later one and (3) prefer a [TIMESPAN] with QUARTERS granularity if the anchor time is also in QUARTERS (this is a common rule in TimeBank annotations). [sent-158, score-0.091]
66 Our synchronous grammar approach outperformed HeidelTime on all corpora, both on the training corpora (AQUAINT and TimeBank) and on the test corpora (Timen and TempEval 2013). [sent-164, score-0.285]
67 The remaining 21 errors were from two new normalization forms not present at all in the training data: 19 instances of THH:MM: SS (times were always YYYY-MM-DDTHH:MM:SS in the training data) and 2 instances of BCYYYY (years were always YYYY in the training data). [sent-179, score-0.112]
68 Our time normalization code and models are freely available. [sent-181, score-0.149]
69 The source code and English grammar are hosted at https : / /github . [sent-182, score-0.159]
70 In future work, we plan to replace the heuristic for selecting between ambiguous parses with a more principled approach. [sent-185, score-0.111]
71 But given an expression like Monday, it would still be impossible to decide whether it refers to the future or the past, since the surrounding context, e. [sent-188, score-0.057]
72 A more promising approach would be to train a classifier that selects between the ambiguous parses based on features of the surrounding context. [sent-191, score-0.111]
73 Semeval-2013 task 1: Tempeval-3: Evaluating time expressions, events, and temporal relations. [sent-229, score-0.082]
wordName wordTfidf (topN-words)
[('timespan', 0.758), ('timen', 0.227), ('synchronous', 0.16), ('heideltime', 0.152), ('nil', 0.144), ('unit', 0.132), ('grammar', 0.125), ('int', 0.119), ('terminals', 0.117), ('normalization', 0.112), ('parses', 0.111), ('findenclosing', 0.106), ('yesterday', 0.106), ('day', 0.106), ('cyk', 0.096), ('timebank', 0.092), ('period', 0.088), ('tempeval', 0.084), ('angeli', 0.079), ('week', 0.078), ('field', 0.078), ('parse', 0.077), ('llorens', 0.066), ('rules', 0.064), ('pustejovsky', 0.063), ('dayofmonth', 0.061), ('expression', 0.057), ('month', 0.056), ('march', 0.055), ('weeks', 0.053), ('uzzaman', 0.053), ('partial', 0.049), ('rif', 0.048), ('chappelier', 0.045), ('findearlier', 0.045), ('monthofyear', 0.045), ('tgen', 0.045), ('xll', 0.045), ('temporal', 0.045), ('parsing', 0.045), ('monday', 0.045), ('verhagen', 0.045), ('side', 0.043), ('rfo', 0.042), ('time', 0.037), ('today', 0.037), ('aquaint', 0.036), ('target', 0.035), ('source', 0.034), ('expressions', 0.034), ('wi', 0.033), ('token', 0.032), ('else', 0.032), ('formal', 0.032), ('moves', 0.031), ('imenorm', 0.03), ('karch', 0.03), ('quarters', 0.03), ('shiftleft', 0.03), ('stro', 0.03), ('weeek', 0.03), ('duration', 0.03), ('integers', 0.03), ('advanced', 0.03), ('operators', 0.03), ('free', 0.029), ('completing', 0.029), ('numeric', 0.028), ('alabama', 0.026), ('birmingham', 0.026), ('derczynski', 0.026), ('ime', 0.026), ('expands', 0.026), ('handles', 0.026), ('modifier', 0.024), ('allow', 0.024), ('ava', 0.024), ('bethard', 0.024), ('hector', 0.024), ('primitive', 0.024), ('primitives', 0.024), ('roser', 0.024), ('sauri', 0.024), ('advance', 0.023), ('arl', 0.022), ('gaizauskas', 0.022), ('seconds', 0.022), ('covering', 0.022), ('elra', 0.021), ('completes', 0.021), ('nonterminals', 0.021), ('scfg', 0.021), ('cat', 0.021), ('normalized', 0.02), ('consume', 0.02), ('fly', 0.02), ('mixing', 0.02), ('handling', 0.019), ('james', 0.019), ('prefer', 0.018)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 14 emnlp-2013-A Synchronous Context Free Grammar for Time Normalization
Author: Steven Bethard
Abstract: We present an approach to time normalization (e.g. the day before yesterday⇒20 13-04- 12) based on a synchronous contex⇒t free grammar. Synchronous rules map the source language to formally defined operators for manipulating times (FINDENCLOSED, STARTATENDOF, etc.). Time expressions are then parsed using an extended CYK+ algorithm, and converted to a normalized form by applying the operators recursively. For evaluation, a small set of synchronous rules for English time expressions were developed. Our model outperforms HeidelTime, the best time normalization system in TempEval 2013, on four different time normalization corpora.
2 0.13334125 127 emnlp-2013-Max-Margin Synchronous Grammar Induction for Machine Translation
Author: Xinyan Xiao ; Deyi Xiong
Abstract: Traditional synchronous grammar induction estimates parameters by maximizing likelihood, which only has a loose relation to translation quality. Alternatively, we propose a max-margin estimation approach to discriminatively inducing synchronous grammars for machine translation, which directly optimizes translation quality measured by BLEU. In the max-margin estimation of parameters, we only need to calculate Viterbi translations. This further facilitates the incorporation of various non-local features that are defined on the target side. We test the effectiveness of our max-margin estimation framework on a competitive hierarchical phrase-based system. Experiments show that our max-margin method significantly outperforms the traditional twostep pipeline for synchronous rule extraction by 1.3 BLEU points and is also better than previous max-likelihood estimation method.
3 0.056969281 151 emnlp-2013-Paraphrasing 4 Microblog Normalization
Author: Wang Ling ; Chris Dyer ; Alan W Black ; Isabel Trancoso
Abstract: Compared to the edited genres that have played a central role in NLP research, microblog texts use a more informal register with nonstandard lexical items, abbreviations, and free orthographic variation. When confronted with such input, conventional text analysis tools often perform poorly. Normalization replacing orthographically or lexically idiosyncratic forms with more standard variants can improve performance. We propose a method for learning normalization rules from machine translations of a parallel corpus of microblog messages. To validate the utility of our approach, we evaluate extrinsically, showing that normalizing English tweets and then translating improves translation quality (compared to translating unnormalized text) using three standard web translation services as well as a phrase-based translation system trained — — on parallel microblog data.
4 0.055565547 9 emnlp-2013-A Log-Linear Model for Unsupervised Text Normalization
Author: Yi Yang ; Jacob Eisenstein
Abstract: We present a unified unsupervised statistical model for text normalization. The relationship between standard and non-standard tokens is characterized by a log-linear model, permitting arbitrary features. The weights of these features are trained in a maximumlikelihood framework, employing a novel sequential Monte Carlo training algorithm to overcome the large label space, which would be impractical for traditional dynamic programming solutions. This model is implemented in a normalization system called UNLOL, which achieves the best known results on two normalization datasets, outperforming more complex systems. We use the output of UNLOL to automatically normalize a large corpus of social media text, revealing a set of coherent orthographic styles that underlie online language variation.
5 0.052434329 106 emnlp-2013-Inducing Document Plans for Concept-to-Text Generation
Author: Ioannis Konstas ; Mirella Lapata
Abstract: In a language generation system, a content planner selects which elements must be included in the output text and the ordering between them. Recent empirical approaches perform content selection without any ordering and have thus no means to ensure that the output is coherent. In this paper we focus on the problem of generating text from a database and present a trainable end-to-end generation system that includes both content selection and ordering. Content plans are represented intuitively by a set of grammar rules that operate on the document level and are acquired automatically from training data. We develop two approaches: the first one is inspired from Rhetorical Structure Theory and represents the document as a tree of discourse relations between database records; the second one requires little linguistic sophistication and uses tree structures to represent global patterns of database record sequences within a document. Experimental evaluation on two domains yields considerable improvements over the state of the art for both approaches.
6 0.050568692 76 emnlp-2013-Exploiting Discourse Analysis for Article-Wide Temporal Classification
7 0.049279384 41 emnlp-2013-Building Event Threads out of Multiple News Articles
8 0.049156711 40 emnlp-2013-Breaking Out of Local Optima with Count Transforms and Model Recombination: A Study in Grammar Induction
9 0.043613981 19 emnlp-2013-Adaptor Grammars for Learning Non-Concatenative Morphology
10 0.043245379 71 emnlp-2013-Efficient Left-to-Right Hierarchical Phrase-Based Translation with Improved Reordering
11 0.04130682 84 emnlp-2013-Factored Soft Source Syntactic Constraints for Hierarchical Machine Translation
12 0.036426563 10 emnlp-2013-A Multi-Teraflop Constituency Parser using GPUs
13 0.035369765 201 emnlp-2013-What is Hidden among Translation Rules
14 0.033966068 187 emnlp-2013-Translation with Source Constituency and Dependency Trees
15 0.033918768 119 emnlp-2013-Learning Distributions over Logical Forms for Referring Expression Generation
16 0.033871993 49 emnlp-2013-Combining Generative and Discriminative Model Scores for Distant Supervision
17 0.033728328 160 emnlp-2013-Relational Inference for Wikification
18 0.033107873 18 emnlp-2013-A temporal model of text periodicities using Gaussian Processes
19 0.030782929 50 emnlp-2013-Combining PCFG-LA Models with Dual Decomposition: A Case Study with Function Labels and Binarization
20 0.030671427 167 emnlp-2013-Semi-Markov Phrase-Based Monolingual Alignment
topicId topicWeight
[(0, -0.099), (1, -0.04), (2, 0.012), (3, 0.054), (4, -0.011), (5, -0.014), (6, -0.04), (7, -0.011), (8, 0.013), (9, 0.048), (10, -0.004), (11, 0.009), (12, -0.006), (13, 0.13), (14, -0.003), (15, 0.026), (16, -0.009), (17, 0.009), (18, 0.021), (19, 0.009), (20, -0.023), (21, -0.094), (22, 0.03), (23, -0.08), (24, -0.076), (25, -0.013), (26, -0.004), (27, -0.101), (28, 0.149), (29, -0.029), (30, -0.115), (31, -0.019), (32, 0.045), (33, 0.029), (34, 0.04), (35, 0.121), (36, -0.046), (37, -0.027), (38, 0.135), (39, -0.051), (40, -0.024), (41, -0.037), (42, -0.045), (43, -0.093), (44, -0.147), (45, 0.111), (46, 0.098), (47, 0.152), (48, -0.071), (49, -0.211)]
simIndex simValue paperId paperTitle
same-paper 1 0.95229304 14 emnlp-2013-A Synchronous Context Free Grammar for Time Normalization
Author: Steven Bethard
Abstract: We present an approach to time normalization (e.g. the day before yesterday⇒20 13-04- 12) based on a synchronous contex⇒t free grammar. Synchronous rules map the source language to formally defined operators for manipulating times (FINDENCLOSED, STARTATENDOF, etc.). Time expressions are then parsed using an extended CYK+ algorithm, and converted to a normalized form by applying the operators recursively. For evaluation, a small set of synchronous rules for English time expressions were developed. Our model outperforms HeidelTime, the best time normalization system in TempEval 2013, on four different time normalization corpora.
2 0.49117202 9 emnlp-2013-A Log-Linear Model for Unsupervised Text Normalization
Author: Yi Yang ; Jacob Eisenstein
Abstract: We present a unified unsupervised statistical model for text normalization. The relationship between standard and non-standard tokens is characterized by a log-linear model, permitting arbitrary features. The weights of these features are trained in a maximumlikelihood framework, employing a novel sequential Monte Carlo training algorithm to overcome the large label space, which would be impractical for traditional dynamic programming solutions. This model is implemented in a normalization system called UNLOL, which achieves the best known results on two normalization datasets, outperforming more complex systems. We use the output of UNLOL to automatically normalize a large corpus of social media text, revealing a set of coherent orthographic styles that underlie online language variation.
3 0.47689965 10 emnlp-2013-A Multi-Teraflop Constituency Parser using GPUs
Author: John Canny ; David Hall ; Dan Klein
Abstract: Constituency parsing with rich grammars remains a computational challenge. Graphics Processing Units (GPUs) have previously been used to accelerate CKY chart evaluation, but gains over CPU parsers were modest. In this paper, we describe a collection of new techniques that enable chart evaluation at close to the GPU’s practical maximum speed (a Teraflop), or around a half-trillion rule evaluations per second. Net parser performance on a 4-GPU system is over 1 thousand length30 sentences/second (1 trillion rules/sec), and 400 general sentences/second for the Berkeley Parser Grammar. The techniques we introduce include grammar compilation, recursive symbol blocking, and cache-sharing.
4 0.47312218 106 emnlp-2013-Inducing Document Plans for Concept-to-Text Generation
Author: Ioannis Konstas ; Mirella Lapata
Abstract: In a language generation system, a content planner selects which elements must be included in the output text and the ordering between them. Recent empirical approaches perform content selection without any ordering and have thus no means to ensure that the output is coherent. In this paper we focus on the problem of generating text from a database and present a trainable end-to-end generation system that includes both content selection and ordering. Content plans are represented intuitively by a set of grammar rules that operate on the document level and are acquired automatically from training data. We develop two approaches: the first one is inspired from Rhetorical Structure Theory and represents the document as a tree of discourse relations between database records; the second one requires little linguistic sophistication and uses tree structures to represent global patterns of database record sequences within a document. Experimental evaluation on two domains yields considerable improvements over the state of the art for both approaches.
5 0.46793097 151 emnlp-2013-Paraphrasing 4 Microblog Normalization
Author: Wang Ling ; Chris Dyer ; Alan W Black ; Isabel Trancoso
Abstract: Compared to the edited genres that have played a central role in NLP research, microblog texts use a more informal register with nonstandard lexical items, abbreviations, and free orthographic variation. When confronted with such input, conventional text analysis tools often perform poorly. Normalization replacing orthographically or lexically idiosyncratic forms with more standard variants can improve performance. We propose a method for learning normalization rules from machine translations of a parallel corpus of microblog messages. To validate the utility of our approach, we evaluate extrinsically, showing that normalizing English tweets and then translating improves translation quality (compared to translating unnormalized text) using three standard web translation services as well as a phrase-based translation system trained — — on parallel microblog data.
6 0.40661457 127 emnlp-2013-Max-Margin Synchronous Grammar Induction for Machine Translation
8 0.33963284 188 emnlp-2013-Tree Kernel-based Negation and Speculation Scope Detection with Structured Syntactic Parse Features
9 0.33407485 122 emnlp-2013-Learning to Freestyle: Hip Hop Challenge-Response Induction via Transduction Rule Segmentation
10 0.31230003 35 emnlp-2013-Automatically Detecting and Attributing Indirect Quotations
11 0.28411034 19 emnlp-2013-Adaptor Grammars for Learning Non-Concatenative Morphology
12 0.27628332 71 emnlp-2013-Efficient Left-to-Right Hierarchical Phrase-Based Translation with Improved Reordering
13 0.24728003 190 emnlp-2013-Ubertagging: Joint Segmentation and Supertagging for English
14 0.24667493 50 emnlp-2013-Combining PCFG-LA Models with Dual Decomposition: A Case Study with Function Labels and Binarization
15 0.23738316 161 emnlp-2013-Rule-Based Information Extraction is Dead! Long Live Rule-Based Information Extraction Systems!
16 0.23611304 18 emnlp-2013-A temporal model of text periodicities using Gaussian Processes
17 0.23150712 152 emnlp-2013-Predicting the Presence of Discourse Connectives
18 0.22057894 76 emnlp-2013-Exploiting Discourse Analysis for Article-Wide Temporal Classification
19 0.21777779 195 emnlp-2013-Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion
20 0.19797264 194 emnlp-2013-Unsupervised Relation Extraction with General Domain Knowledge
topicId topicWeight
[(3, 0.024), (15, 0.364), (18, 0.065), (22, 0.037), (30, 0.118), (45, 0.025), (50, 0.01), (51, 0.133), (66, 0.036), (71, 0.025), (75, 0.027), (77, 0.012), (96, 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 0.74609506 14 emnlp-2013-A Synchronous Context Free Grammar for Time Normalization
Author: Steven Bethard
Abstract: We present an approach to time normalization (e.g. the day before yesterday⇒20 13-04- 12) based on a synchronous contex⇒t free grammar. Synchronous rules map the source language to formally defined operators for manipulating times (FINDENCLOSED, STARTATENDOF, etc.). Time expressions are then parsed using an extended CYK+ algorithm, and converted to a normalized form by applying the operators recursively. For evaluation, a small set of synchronous rules for English time expressions were developed. Our model outperforms HeidelTime, the best time normalization system in TempEval 2013, on four different time normalization corpora.
2 0.60542417 126 emnlp-2013-MCTest: A Challenge Dataset for the Open-Domain Machine Comprehension of Text
Author: Matthew Richardson ; Christopher J.C. Burges ; Erin Renshaw
Abstract: Christopher J.C. Burges Microsoft Research One Microsoft Way Redmond, WA 98052 cburge s @micro so ft . com Erin Renshaw Microsoft Research One Microsoft Way Redmond, WA 98052 erinren@mi cros o ft . com disciplines are focused on this problem: for example, information extraction, relation extraction, We present MCTest, a freely available set of stories and associated questions intended for research on the machine comprehension of text. Previous work on machine comprehension (e.g., semantic modeling) has made great strides, but primarily focuses either on limited-domain datasets, or on solving a more restricted goal (e.g., open-domain relation extraction). In contrast, MCTest requires machines to answer multiple-choice reading comprehension questions about fictional stories, directly tackling the high-level goal of open-domain machine comprehension. Reading comprehension can test advanced abilities such as causal reasoning and understanding the world, yet, by being multiple-choice, still provide a clear metric. By being fictional, the answer typically can be found only in the story itself. The stories and questions are also carefully limited to those a young child would understand, reducing the world knowledge that is required for the task. We present the scalable crowd-sourcing methods that allow us to cheaply construct a dataset of 500 stories and 2000 questions. By screening workers (with grammar tests) and stories (with grading), we have ensured that the data is the same quality as another set that we manually edited, but at one tenth the editing cost. By being open-domain, yet carefully restricted, we hope MCTest will serve to encourage research and provide a clear metric for advancement on the machine comprehension of text. 1 Reading Comprehension A major goal for NLP is for machines to be able to understand text as well as people. Several research 193 semantic role labeling, and recognizing textual entailment. Yet these techniques are necessarily evaluated individually, rather than by how much they advance us towards the end goal. On the other hand, the goal of semantic parsing is the machine comprehension of text (MCT), yet its evaluation requires adherence to a specific knowledge representation, and it is currently unclear what the best representation is, for open-domain text. We believe that it is useful to directly tackle the top-level task of MCT. For this, we need a way to measure progress. One common method for evaluating someone’s understanding of text is by giving them a multiple-choice reading comprehension test. This has the advantage that it is objectively gradable (vs. essays) yet may test a range of abilities such as causal or counterfactual reasoning, inference among relations, or just basic understanding of the world in which the passage is set. Therefore, we propose a multiple-choice reading comprehension task as a way to evaluate progress on MCT. We have built a reading comprehension dataset containing 500 fictional stories, with 4 multiple choice questions per story. It was built using methods which can easily scale to at least 5000 stories, since the stories were created, and the curation was done, using crowd sourcing almost entirely, at a total of $4.00 per story. We plan to periodically update the dataset to ensure that methods are not overfitting to the existing data. The dataset is open-domain, yet restricted to concepts and words that a 7 year old is expected to understand. This task is still beyond the capability of today’s computers and algorithms. ProceSe datintlges, o Wfa tsh ein 2g01to3n, C UoSnfAe,re 1n8c-e2 o1n O Ecmtopbier ic 2a0l1 M3.et ?hc o2d0s1 i3n A Nsastoucria lti Loan fgoura Cgoem Ppruotcaetsiosin agl, L piang eusis 1t9ic3s–203, By restricting the concept space, we gain the difficulty of being an open-domain problem, without the full complexity of the real world (for example, there will be no need for the machine to understand politics, technology, or to have any domain specific expertise). The multiple choice task avoids ambiguities (such as when the task is to find a sentence that best matches a question, as in some early reading comprehension tasks: see Section 2), and also avoids the need for additional grading, such as is needed in some TREC tasks. The stories were chosen to be fictional to focus work on finding the answer in the story itself, rather than in knowledge repositories such as Wikipedia; the goal is to build technology that actually understands stories and paragraphs on a deep level (as opposed to using information retrieval methods and the redundancy of the web to find the answers). We chose to use crowd sourcing, as opposed to, for example, contracting teachers or paying for existing standardized tests, for three reasons, namely: (1) scalability, both for the sizes of datasets we can provide, and also for the ease of regularly refreshing the data; (2) for the variety in story-telling that having many different authors brings; and (3) for the free availability that can only result from providing non-copyrighted data. The content is freely available at http://research.microsoft.com/mct, and we plan to use that site to track published results and provide other resources, such as labels of various kinds. 2 Previous Work The research goal of mapping text to meaning representations in order to solve particular tasks has a long history. DARPA introduced the Airline Travel Information System (ATIS) in the early 90’s: there the task was to slot-fill flight-related information by modeling the intent of spoken language (see Tur et al., 2010, for a review). This data continues to be a used in the semantic modeling community (see, for example, Zettlemoyer and Collins, 2009). The Geoquery database contains 880 geographical facts about the US and has played a similar role for written (as opposed to spoken) natural language queries against a database (Zelle and Mooney, 1996) and it also continues to spur research (see for example Goldwasser et al., 2011), as does the similar Jobs database, which provides mappings of 640 sentences to a listing of jobs 194 (Tang and Mooney, 2001). More recently, Zweig and Burges (2012) provided a set of 1040 sentences that comprise an SAT-style multiple choice sentence completion task. The idea of using story-based reading comprehension questions to evaluate methods for machine reading itself goes back over a decade, when Hirschmann et al. (1999) showed that a bag of words approach, together with some heuristic linguistic modeling, could achieve 40% accuracy for the task of picking the sentence that best matches the query for “who / what / when / where / why” questions, on a small reading comprehension dataset from Remedia. This dataset spurred several research efforts, for example using reinforcement learning (Grois and Wilkins, 2005), named entity resolution (Harabagiu et al., 2003) and mapping questions and answers to logical form (Wellner et al., 2006). Work on story understanding itself goes back much further, to 1972, when Charniak proposed using a background model to answer questions about children’s stories. Similarly, the TREC (and TAC) Question Answering tracks (e.g., Voorhees and Tice, 1999) aim to evaluate systems on their ability to answer factual questions such as “Where is the Taj Mahal”. The QA4MRE task also aims to evaluate machine reading systems through question answering (e.g., Clark et al., 2012). Earlier work has also aimed at controlling the scope by limiting the text to children’s stories: Breck et al. (2001) collected 75 stories from the Canadian Broadcasting Corporation’s web site for children, and generated 650 questions for them manually, where each question was answered by a sentence in the text. Leidner et al. (2003) both enriched the CBC4kids data by adding several layers of annotation (such as semantic and POS tags), and measured QA performance as a function of question difficulty. For a further compendium of resources related to the story comprehension task, see Mueller (2010). The task proposed here differs from the above work in several ways. Most importantly, the data collection is scalable: if the dataset proves sufficiently useful to others, it would be straightforward to gather an order of magnitude more. Even the dataset size presented here is an order of magnitude larger than the Remedia or the CBC4kids data and many times larger than QA4MRE. Second, the multiple choice task presents less ambiguity (and is consequently easier to collect data for) than the ly from MC500 train set). task of finding the most appropriate sentence, and may be automatically evaluated. Further, our stories are fictional, which means that the information to answer the question is contained only in the story itself (as opposed to being able to directly leverage knowledge repositories such as Wikipedia). 195 This design was chosen to focus the task on the machine understanding of short passages, rather than the ability to match against an existing knowledge base. In addition, while in the CBC4kids data each answer was a sentence from the story, here we required that approximately half of the questions require at least two sentences from the text to answer; being able to control complexity in this way is a further benefit of using multiple choice answers. Finally, as explained in Section 1, the use of free-form input makes the problem open domain (as opposed to the ATIS, Geoquery and Jobs data), leading to the hope that solutions to the task presented here will be easier to apply to novel, unrelated tasks. 3 Generating the Stories and Questions Our aim was to generate a corpus of fictional story that could be scaled with as little expert input as possible. Thus, we designed the process to be gated by cost, and keeping the costs low was a high priority. Crowd-sourcing seemed particularly appropriate, given the nature of the task, so we opted to use Amazon Mechanical Turk2 (AMT). With over 500,000 workers3, it provides the work sets1 force required to both achieve scalability and, equally importantly, to provide diversity in the stories and types of questions. We restricted our task to AMT workers (workers) residing in the United States. The average worker is 36 years old, more educated than the United States population in general (Paolacci et al., 2010), and the majority of workers are female. 3.1 The Story and Questions Workers were instructed to write a short (150-300 words) fictional story, and to write as if for a child in grade school. The choice of 150-300 was made to keep the task an appropriate size for workers while still allowing for complex stories and questions. The workers were free to write about any topic they desired (as long as it was appropriate for a young child), and so there is a wide range, including vacations, animals, school, cars, eating, gardening, fairy tales, spaceships, and cowboys. 1 We use the term “story set” to denote the fictional story together with its multiple choice questions, hypothetical answers, and correct answer labels. 2 http://www.mturk.com 3 https://requester.mturk.com/tour Workers were also asked to provide four reading comprehension questions pertaining to their story and, for each, four multiple-choice answers. Coming up with incorrect alternatives (distractors) is a difficult task (see, e.g., Agarwal, 2011) but workers were requested to provide “reasonable” incorrect answers that at least include words from the story so that their solution is not trivial. For example, for the question “What is the name of the dog?”, if only one of the four answers occurs in the story, then that answer must be the correct one. Finally, workers were asked to design their questions and answers such that at least two of the four questions required multiple sentences from the story to answer them. That is, for those questions it should not be possible to find the answer in any individual sentence. The motivation for this was to ensure that the task could not be fully solved using lexical techniques, such as word matching, alone. Whilst it is still possible that a sophisticated lexical analysis could completely solve the task, requiring that answers be constructed from at least two different sentences in the story makes this much less likely; our hope is that the solution will instead require some inference and some form of limited reasoning. This hope rests in part upon the observation that standardized reading comprehension tests, whose goal after all is to test comprehension, generally avoid questions that can be answered by reading a single sentence. 3.2 Automatic Validation Besides verifying that the story and all of the questions and answers were provided, we performed the following automatic validation before allowing the worker to complete the task: Limited vocabulary: The lowercase words in the story, questions, and answers were stemmed and checked against a vocabulary list of approximately 8000 words that a 7-year old is likely to know (Kuperman et al., 2012). Any words not on the list were highlighted in red as the worker typed, and the task could not be submitted unless all of the words satisfied this vocabulary criterion. To allow the use of arbitrary proper nouns, capitalized words were not checked against the vocabulary list. Multiple-sentence questions: As described earlier, we required that at least two of the questions need multiple sentences to answer. Workers were simply asked to mark whether a question needs one 196 or multiple sentences and we required that at least two are marked as multiple. 3.3 The Workers Workers were required to reside in the United States and to have completed 100 HITs with an over 95% approval The median worker took 22 minutes to complete the task. We paid workers $2.50 per story set and allowed each to do a maximum of 8 tasks (5 in MC500). We did not experiment with paying less, but this rate amounts to $6.82/hour, which is approximately the rate paid by other writing tasks on AMT at the time, though is also significantly higher than the median wage of $1.38 found in 2010 (Horton and Chilton, 2010). Workers could optionally leave feedback on the task, which was overwhelmingly positive – the most frequent non-stopword in the comments was “fun” and the most frequent phrase was “thank you”. The only negative comments (in <1% of submissions) were when the worker felt that a particular word should have been on the allowed vocabulary list. Given the positive feedback, it may be possible to pay less if we collect more data in the future. We did not enforce story length constraints, but some workers interpreted our suggestion that the story be 150-300 words as a hard rate4. constraint, and some asked to be able to write a longer story. The MCTest corpus contains two sets of stories, named MC160 and MC500, and containing 160 and 500 stories respectively. MC160 was gathered first, then some improvements were made before gathering MC500. We give details on the differences between these two sets below. 3.4 MC160: Manually Curated for Quality In addition to the details described above, MC160 workers were given a target elementary grade school level (1-4) and a sample story matching that grade level5. The intent was to produce a set of stories and questions that varied in difficulty so that research work can progress grade-by-grade if needed. However, we found little difference between grades in the corpus.. After gathering the stories, we manually curated the MC160 corpus by reading each story set and 4 The latter two are the default AMT requirements. 5 From http://www.englishforeveryone.org/. correcting errors. The most common mistakes were grammatical, though occasionally questions and/or answers needed to be fixed. 66% of the stories have at least one correction. We provide both the curated and original corpuses in order to allow research on reading comprehension in the presence of grammar, spelling, and other mistakes. 3.5 MC500: Adding a Grammar Test Though the construction of MC160 was successful, it requires a costly curation process which will not scale to larger data sets (although the curation was useful, both for improving the design of MC500, and for assessing the effectiveness of automated curation techniques). To more fully automate the process, we added two more stages: (1) A grammar test that automatically pre-screens workers for writing ability, and (2) a second Mechanical Turk task whereby new workers take the reading comprehension tests and rate their quality. We will discuss stage (2) in the next section. The grammar test consisted of 20 sentences, half of which had one grammatical error (see Figure 2). The incorrect sentences were written using common errors such as you ’re vs. your, using ‘s to indicate plurality, incorrect use of tense, it’ ’s vs. its, 197 NGoGramram mar TreTsets Q(u134a-.52l3i) tyaAn73ib m0o% aults Table 1. Pre-screening workers using a grammar test improves both quality and diversity of stories. Both differences are significant using the two-tailed t-test (p<0.05 for quality and p<0.01 for animals). less vs. fewer, I me, etc. Workers were required vs. to indicate for each sentence whether it was grammatically correct or not, and had to pass with at least 80% accuracy in order to qualify for the task. The 80% threshold was chosen to trade off worker quality with the rate at which the tasks would be completed; initial experiments using a threshold of 90% indicated that collecting 500 stories would take many weeks instead of days. Note that each worker is allowed to write at most 5 stores, so we required at least 100 workers to pass the qualification test. To validate the use of the qualification test, we gathered 30 stories requiring the test (qual) and 30 stories without. We selected a random set of 20 stories (10 from each), hid their origin, and then graded the overall quality of the story and questions from 1-5, meaning do not attempt to fix, bad but rescuable, has non-minor problems, has only minor problems, and has no problems, respectively. Results are shown in Table 1. The difference is statistically significant (p<0.05, using the twotailed t-test). The qual stories were also more diverse, with fewer of them about animals (the most common topic). Additional Modifications: Based on our experience curating MC160, we also made the following modifications to the task. In order to eliminate trivially-answerable questions, we required that each answer be unique, and that either the correct answer did not appear in the story or, if it did appear, that at least two of the incorrect answers also appeared in the story. This is to prevent questions that are trivially answered by checking which answer appears in the story. The condition on whether the correct answer appears is to allow questions such as “How many candies did Susan eat?”, where the total may never appear in the story, even though the information needed to derive it does. An answer is considered to appear in the story if at least half (rounded down) of its non-stopword terms appear in the story (ignoring word endings). This check is done automatically and must be satisfied before the worker is able to complete the task. Workers could also bypass the check if they felt it was incorrect, by adding a special term to their answer. We were also concerned that the sample story might bias the workers when writing the story set, particularly when designing questions that require multiple sentences to answer. So, we removed the sample story and grade level from the task. Finally, in order to encourage more diversity of stories, we added creativity terms, a set of 15 nouns chosen at random from the allowed vocabulary set. Workers were asked to “please consider” using one or more of the terms in their story, but use of the words was strictly optional. On average, workers used 3.9 of the creativity terms in their stories. 4 Rating the Stories and Questions In this section we discuss the crowd-sourced rating of story sets. We wished to ensure story set quality despite the fact that MC500 was only minimally manually curated (see below). Pre-qualifying workers with a grammar test was one step of this process. The second step was to have additional workers on Mechanical Turk both evaluate each story and take its corresponding test. Each story was evaluated in this way by 10 workers, each of whom provided scores for each of ageappropriateness (yes/maybe/no), grammaticality (few/some/many errors), and story clarity (excellent/reasonable/poor). When answering the four reading comprehension questions, workers could also mark a question as “unclear”. Each story set was rated by 10 workers who were each paid $0. 15 per set. Since we know the purportedly correct answer, we can estimate worker quality by measuring what fraction of questions that worker got right. Workers with less than 80% accuracy (ignoring those questions marked as unclear) were removed from the set. This constituted just 4.1% of the raters and 4.2% of the judgments (see Figure 3). Only one rater appeared to be an intentional spammer, answering 1056 questions with only 29% accuracy. The others primarily judged only one story. Only one worker fell between, answering 336 questions with just 75% accuracy. 198 Figure 3. Just 4.1% of raters had an accuracy below 80% (constituting 4.2% of the judgments). For the remaining workers (those who achieved at least 80% accuracy), we measured median story appropriateness, grammar, and clarity. For each category, stories for which less than half of the ratings were the best possible (e.g., excellent story clarity) were inspected and optionally removed from the data set. This required inspecting 40 (<10%) of the stories, only 2 of which were deemed poor enough to be removed (both of which had over half of the ratings all the way at the bot- tom end of the scale, indicating we could potentially have inspected many fewer stories with the same results). We also inspected questions for which at least 5 workers answered incorrectly, or answered “unclear”. In total, 29 questions (<2%) were inspected. 5 were fixed by changing the question, 8 by changing the answers, 2 by changing both, 6 by changing the story, and 8 were left unmodified. Note that while not fully automated, this process of inspecting stories and repairing questions took one person one day, so is still scalable to at least an order of magnitude more stories. 5 Dataset Analysis In Table 2, we present results demonstrating the value of the grammar test and curation process. As expected, manually curating MC160 resulted in increased grammar quality and percent of questions answered correctly by raters. The goal of MC500 was to find a more scalable method to achieve the same quality as the curated MC160. As Table 2 shows, the grammar test improved story grammar quality from 1.70 to 1.77 (both uncurated). The rating and one-day curation process in- TS51a06bet0l cu2r.ateAdvra1 Ag.9e8241aAgpe1 Cp.67la13r57oiptyrae1 Gn.7er8a90s74mǂ, satroy9C 567oc.lr397a eritcy, grammar quality (0-2, with 2 being best), and percent of questions answered correctly by raters, for the original and curated versions of the data. Bold indicates statistical significance vs. the original version of the same set, using the two-sample t-test with unequal variance. The indicates the only statistical difference between 500 curated and 160 curated. ǂ TMCaob lre5p10u63s. CoSr51tp06uise tawM2it06sreimt dcinsea gfnorS2Mt1o0C2r4Ay1v6eQ0raug7e8n.ds0W7tMionCrd5s0APne3.sr:4w er creases this to 1.79, whereas a fully manual curation results in a score of 1.84. Curation also improved the percent of questions answered correctly for both MC160 and MC500, but, unlike with grammar, there is no significant difference between the two curated sets. Indeed, the only statis- tically significant difference between the two is in grammar. So, the MC500 grammar test and curation process is a very scalable method for collecting stories of nearly the quality of the costly manual curation of MC160. We also computed correlations between these measures of quality and various factors such as story length and time spent writing the story. On MC500, there is a mild correlation between a worker’s grammar test score and the judged grammar quality of that worker’s story (correlation of 0.24). Interestingly, this relation disappeared once MC500 was curated, likely due to repairing the stories with the worst grammar. On MC160, there is a mild correlation between the clarity and the number of words in the question and answer (0.20 and 0.18). All other correlations were below 0. 15. These factors could be integrated into an estimate for age-appropriateness, clarity, and grammar, potentially reducing the need for raters. Table 3 provides statistics on each corpus. MC160 and MC500 are similar in average number of words per story, question, and answer, as well as the median writing time. The most commonly used 199 Baseline Algorithms Require: Passage P, set of passage words PW, ith word in passage Pi, set of words in question Q, set of words in hypothesized answers A1..4, and set of stop words U, Define: ( ) ∑( ) Define: ( ) ( ( )). Algorithm 1 Sliding Window Algorithm 1 Sliding Window for i= 1to 4 do | | ∑ | |{ ( ) end for return Algorithm 2 Distance Based for i= 1to 4 do ( ) (( ) ) if | | else or | | | |( ), where ()is the minimum number of words between an occurrence of q and an occurrence of a in P, plus one. end if end for return Algorithm Return SW Algorithm SW+D Return Figure 4. The two lexical-based algorithms used for the baselines. nouns in MC500 are: day, friend, time, home, house, mother, dog, mom, school, dad, cat, tree, and boy. The stories vary widely in theme. The first 10 stories of the randomly-ordered MC500 set are about: travelling to Miami to visit friends, waking up and saying hello to pets, a bully on a schoolyard, visiting a farm, collecting insects at Grandpa’s house, planning a friend’s birthday party, selecting clothes for a school dance, keeping animals from eating your ice cream, animals ordering food, and adventures of a boy and his dog. TSMaAiblCnuge1tli460.Per5TcS9reW.an54it360 caonrQdS6e’W7c8Dst.4+1e7vfD5o:rthem465S8u.W4l28t93ip Tl4e0cQsht:o’S5i76Wc e.8+2q1D95ues- tions for MC160. SW: sliding window algorithm. SW+D: combined results with sliding window and distance based algorithms. Single/Multi: questions marked by worker as requiring a single/multiple sentence(s) to answer. All differences between SW and SW+D are significant (p<0.01 using the two-tailed paired t-test). TASMabiluCnge5tli0.Pe5T4rSc92a.We18ni304t ac0noSQrd56W’8e1D.sc2+7et8Dv1fo:rt5hS1eW.85m603uTletQsiSp5W:l’76es.31+c570hDoiceS65Wq0A7u.4l5+e 3Ds- tions for MC500, notation as above. All differences between SW and SW+D are significant (p<0.01, tested as above). We randomly divided MC160 and MC500 into train, development, and test sets of 70, 30, and 60 stories and 300, 50, and 150 stories, respectively. 6 Baseline System and Results We wrote two baseline systems, both using only simple lexical features. The first system used a sliding window, matching a bag of words constructed from the question and hypothesized answer to the text. Since this ignored long range dependencies, we added a second, word-distance based algorithm. The distance-based score was simply subtracted from the window-based score to arrive at the final score (we tried scaling the distance score before subtraction but this did not improve results on the MC160 train set). The algorithms are summarized in Figure 4. A coin flip is used to break ties. The use of inverse word counts was inspired by TF-IDF. Results for MC160 and MC500 are shown in Table 4 and Table 5. The MC160 train and development sets were used for tuning. The baseline algorithm was authored without seeing any portion of MC500, so both the MC160 test set and all of 200 BRCoaTsmEelbin e d(SW+D)65 M967C. 76219506ǂ 0Test5 6M603C. 685 7320ǂ 0Test Table 6. Percent correct for MC160 and MC500 test sets. The ǂ indicates statistical significance vs. baseline (p<0.01 using the two-tailed paired t-test). MC160 combined vs. baseline has p-value 0.063. MC500 were used for testing (although we nevertheless report results on the train/test split). Note that adding the distance based algorithm improved accuracy by approximately 10% absolute on MC160 and approximately 6% on MC500. Overall, error rates on MC500 are higher than on MC160, which agrees with human performance (see Table 2), suggesting that MC500’s questions are more difficult. 7 Recognizing Textual Entailment Results We also tried using a “recognizing textual entailment” (RTE) system to answer MCTest questions. The goal of RTE (Dagan et al., 2005) is to determine whether a given statement can be inferred from a particular text. We can cast MCTest as an RTE task by converting each question-answer pair into a statement, and then selecting the answer whose statement has the highest likelihood of being entailed by the story. For example, in the sample story given in Figure 1, the second question can be converted into four statements (one for each answer), and the RTE system should select the statement “James pulled pudding off of the shelves in the grocery store” as the most likely one. For converting question-answer pairs to statements, we used the rules employed in a web-based question answering system (Cucerzan and Agichtein, 2005). For RTE, we used BIUTEE (Stern and Dagan, 2011), which performs better than the median system in the past four RTE competitions. We ran BIUTEE both in its default configuration, as well as with its optional additional data sources (FrameNet, ReVerb, DIRT, and others as found on the BIUTEE home page). The default configuration performed better so we present its results here. The results in Table 6 show that the RTE method performed worse than the baseline. We also combined the baseline and RTE system by training BIUTEE on the train set and using the development set to optimize a linear combination of BIUTEE with the baseline; the combined system outperforms either component system on MC500. It is possible that with some tuning, an RTE system will outperform our baseline system. Nevertheless, these RTE results, and the performance of the baseline system, both suggest that the reading comprehension task described here will not be trivially solved by off-the-shelf techniques. 8 Making Data and Results an Ongoing Resource Our goal in constructing this data is to encourage research and innovation in the machine comprehension of text. Thus, we have made both MC160 and MC500 freely available for download at http://research.microsoft.com/mct. To our knowledge, these are the largest copyright-free reading comprehension data sets publicly available. To further encourage research on these data, we will be continually updating the webpage with the bestknown published results to date, along with pointers to those publications. One of the difficulties in making progress on a particular task is implementing previous work in order to apply improvements to it. To mitigate this difficulty, we are encouraging researchers who use the data to (optionally) provide per-answer scores from their system. Doing so has three benefits: (a) a new system can be measured in the context of the errors made by the previous systems, allowing each research effort to incrementally add useful functionality without needing to also re-implement the current state-of-the-art; (b) it allows system performance to be measured using paired statistical testing, which will substantially increase the ability to determine whether small improvements are significant; and (c) it enables researchers to perform error analysis on any of the existing systems, simplifying the process of identifying and tackling common sources of error. We will also periodically ensemble the known systems using standard machine learning techniques and make those results available as well (unless the existing state-of-theart already does such ensembling). The released data contains the stories and questions, as well as the results from workers who rated 201 the stories and took the tests. The latter may be used, for example, to measure machine performance vs. human performance on a per-question basis (i.e., does your algorithm make similar mistakes to humans?), or vs. the judged clarity of each story. The ratings, as well as whether a question needs multiple sentences to answer, should typically only be used in evaluation, since such information is not generally available for most text. We will also provide an anonymized author id for each story, which could allow additional research such as using other works by the same author when understanding a story, or research on authorship attribution (e.g., Stamatatos, 2009). 9 Future Work We plan to use this dataset to evaluate approaches for machine comprehension, but are making it available now so that others may do the same. If MCTest is used we will collect more story sets and will continue to refine the collection process. One interesting research direction is ensuring that the questions are difficult enough to challenge state-ofthe-art techniques as they develop. One idea for this is to apply existing techniques automatically during story set creation to see whether a question is too easily answered by a machine. By requiring authors to create difficult questions, each data set will be made more and more difficult (but still answerable by humans) as the state-of-the-art methods advance. We will also experiment with timing the raters as they answer questions to see if we can find those that are too easy for people to answer. Removing such questions may increase the difficulty for machines as well. Additionally, any divergence between how easily a person answers a question vs. how easily a machine does may point toward new techniques for improving machine comprehension; we plan to conduct research in this direction as well as make any such data available for others. 10 Conclusion We present the MCTest dataset in the hope that it will help spur research into the machine comprehension of text. The metric (the accuracy on the question sets) is clearly defined, and on that metric, lexical baseline algorithms only attain approximately 58% correct on test data (the MC500 set) as opposed to the 100% correct that the majority of crowd-sourced judges attain. A key component of MCTest is the scalable design: we have shown that data whose quality approaches that of expertly cu- rated data can be generated using crowd sourcing coupled with expert correction of worker-identified errors. Should MCTest prove useful to the community, we will continue to gather data, both to increase the corpus size, and to keep the test sets fresh. The data is available at http://research.microsoft.com/mct and any submitted results will be posted there too. Because submissions will be requested to include the score for each test item, researchers will easily be able to compare their systems with those of others, and investigation of ensembles comprised of components from several different teams will be straightforward. MCTest also contains supplementary material that researchers may find useful, such as worker accuracies on a grammar test and crowd-sourced measures of the quality of their stories. Acknowledgments We would like to thank Silviu Cucerzan and Lucy Vanderwende for their help with converting questions to statements and other useful discussions. References M. Agarwal and P. Mannem. 2011. Automatic Gap-fill Question Generation from Text Books. In Proceed- ings of the Sixth Workshop on Innovative Use of NLP for Building Educational Applications, 56–64. E. Breck, M. Light, G.S.Mann, E. Riloff, B. Brown, P. Anand, M. Rooth M. Thelen. 2001. Looking under the hood: Tools for diagnosing your question answering engine. In Proceedings of the workshop on Opendomain question answering, 12, 1-8. E. Charniak. 1972. Toward a Model of Children’s Story Comprehension. Technical Report, 266, MIT Artificial Intelligence Laboratory, Cambridge, MA. P. Clark, P. Harrison, and X. Yao. An Entailment-Based Approach to the QA4MRE Challenge. 2012. In Proceedings of the Conference and Labs of the Evaluation Forum (CLEF) 2012. S. Cucerzan and E. Agichtein. 2005. Factoid Question Answering over Unstructured and Structured Content on the Web. In Proceedings of the Fourteenth Text Retrieval Conference (TREC). I. Dagan, O. Glickman, and B. Magnini. 2006. The PASCAL Recognising Textual Entailment Challenge. In J. Quiñonero-Candela, I. Dagan, B. Magnini, F. d'Alché-Buc (Eds.), Machine Learning 202 Challenges. Lecture Notes in Computer Science, Vol. 3944, pp. 177-190, Springer. D. Goldwasser, R. Reichart, J. Clarke, D. Roth. 2011. Confidence Driven Unsupervised Semantic Parsing. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, 1486-1495. E. Grois and D.C. Wilkins. 2005. Learning Strategies for Story Comprehension: A Reinforcement Learning Approach. In Proceedings of the Twenty Second International Conference on Machine Learning, 257264. S.M. Harabagiu, S.J. Maiorano, and M.A. Pasca. 2003. Open-Domain Textual Question Answering Techniques. Natural Language Engineering, 9(3): 1-38. Cambridge University Press, Cambridge, UK. L. Hirschman, M. Light, E. Breck, and J.D. Burger. 1999. Deep Read: A Reading Comprehension System. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL), 325-332. J. Horton and L. Chilton. 2010. The labor economics of paid crowdsourcing. In Proceedings of the 11th ACM Conference on Electronic Commerce, 209-218. V. Kuperman, H. Stadthagen-Gonzalez, M. Brysbaert. 2012. Age-of-acquisition ratings for 30,000 English words. Behavior Research Methods, 44(4):978-990. J.L. Leidner, T. Dalmas, B. Webber, J. Bos, C. Grover. 2003. Automatic Multi-Layer Corpus Annotation for Evaluating Question Answering Methods: CBC4Kids. In Proceedings of the 3rd International Workshop on Linguistically Interpreted Corpora. E.T. Mueller. 2010. Story Understanding Resources. http://xenia.media.mit.edu/~mueller/storyund/storyre s.html. G. Paolacci, J. Chandler, and P. Iperirotis. 2010. Running experiments on Amazon Mechanical Turk. Judgment and Decision Making. 5(5):41 1-419. E. Stamatatos. 2009. A survey of modern authorship attribution methods. J. Am. Soc. Inf. Sci., 60:538– 556. A. Stern and I. Dagan. 2011. A Confidence Model for Syntactically-Motivated Entailment Proofs. In Proceedings of Recent Advances in Natural Language Processing (RANLP). L.R. Tang and R.J. Mooney. 2001. Using Multiple Clause Constructors in Inductive Logic Programming for Semantic Parsing. In Proceedings of the European Conference on Machine Learning (ECML), 466-477. G. Tur, D. Hakkani-Tur, and L.Heck. 2010. What is left to be understood in ATIS? Spoken Language Technology Workshop, 19-24. E.M. Voorhees and D.M. Tice. 1999. The TREC-8 Question Answering Track Evaluation. In Proceedings of the Eighth Text Retrieval Conference (TREC8). 12th Wellner, L. Ferro, W. Greiff, and L. Hirschman. 2005. Reading comprehension tests for computerbased understand evaluation. Natural Language Engineering, 12(4):305-334. Cambridge University Press, Cambridge, UK. J.M. Zelle and R.J. Mooney. 1996. Learning to Parse Database Queries using Inductive Logic Programming. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI), 10501055. B. Zettlemoyer and M. Collins. 2009. Learning Context-Dependent Mappings from Sentences to Logical Form. In Proceedings of the 47th Annual Meeting of the Association for Computation Linguistics (ACL), 976-984. G. Zweig and C.J.C. Burges. 2012. A Challenge Set for Advancing Language Modeling. In Proceedings of the Workshop on the Future of Language Modeling for HLT, NAACL-HLT. L.S. 203
Author: Russell Beckley ; Brian Roark
Abstract: Pronunciation dictionaries provide a readily available parallel corpus for learning to transduce between character strings and phoneme strings or vice versa. Translation models can be used to derive character-level paraphrases on either side of this transduction, allowing for the automatic derivation of alternative pronunciations or spellings. We examine finitestate and SMT-based methods for these related tasks, and demonstrate that the tasks have different characteristics finding alternative spellings is harder than alternative pronunciations and benefits from round-trip algorithms when the other does not. We also show that we can increase accuracy by modeling syllable stress. –
4 0.46164447 56 emnlp-2013-Deep Learning for Chinese Word Segmentation and POS Tagging
Author: Xiaoqing Zheng ; Hanyang Chen ; Tianyu Xu
Abstract: This study explores the feasibility of performing Chinese word segmentation (CWS) and POS tagging by deep learning. We try to avoid task-specific feature engineering, and use deep layers of neural networks to discover relevant features to the tasks. We leverage large-scale unlabeled data to improve internal representation of Chinese characters, and use these improved representations to enhance supervised word segmentation and POS tagging models. Our networks achieved close to state-of-theart performance with minimal computational cost. We also describe a perceptron-style algorithm for training the neural networks, as an alternative to maximum-likelihood method, to speed up the training process and make the learning algorithm easier to be implemented.
5 0.45709503 172 emnlp-2013-Simple Customization of Recursive Neural Networks for Semantic Relation Classification
Author: Kazuma Hashimoto ; Makoto Miwa ; Yoshimasa Tsuruoka ; Takashi Chikayama
Abstract: In this paper, we present a recursive neural network (RNN) model that works on a syntactic tree. Our model differs from previous RNN models in that the model allows for an explicit weighting of important phrases for the target task. We also propose to average parameters in training. Our experimental results on semantic relation classification show that both phrase categories and task-specific weighting significantly improve the prediction accuracy of the model. We also show that averaging the model parameters is effective in stabilizing the learning and improves generalization capacity. The proposed model marks scores competitive with state-of-the-art RNN-based models.
6 0.45643055 4 emnlp-2013-A Dataset for Research on Short-Text Conversations
7 0.45602539 157 emnlp-2013-Recursive Autoencoders for ITG-Based Translation
8 0.4553149 13 emnlp-2013-A Study on Bootstrapping Bilingual Vector Spaces from Non-Parallel Data (and Nothing Else)
9 0.45524409 47 emnlp-2013-Collective Opinion Target Extraction in Chinese Microblogs
10 0.45459118 81 emnlp-2013-Exploring Demographic Language Variations to Improve Multilingual Sentiment Analysis in Social Media
11 0.4536227 143 emnlp-2013-Open Domain Targeted Sentiment
12 0.45341358 38 emnlp-2013-Bilingual Word Embeddings for Phrase-Based Machine Translation
13 0.45335442 15 emnlp-2013-A Systematic Exploration of Diversity in Machine Translation
14 0.45310658 52 emnlp-2013-Converting Continuous-Space Language Models into N-Gram Language Models for Statistical Machine Translation
15 0.45282608 107 emnlp-2013-Interactive Machine Translation using Hierarchical Translation Models
16 0.45261022 66 emnlp-2013-Dynamic Feature Selection for Dependency Parsing
17 0.45212546 163 emnlp-2013-Sarcasm as Contrast between a Positive Sentiment and Negative Situation
18 0.45172188 175 emnlp-2013-Source-Side Classifier Preordering for Machine Translation
19 0.45067799 187 emnlp-2013-Translation with Source Constituency and Dependency Trees
20 0.44999051 164 emnlp-2013-Scaling Semantic Parsers with On-the-Fly Ontology Matching