We improve parse error detection, weighting dependency information on the basis of simulated parses. Such simulations extend the training grammar, and, although the simulations are not wholly correct or incorrect-as observed from the results with different weightings for small treebanks-they help to determine whether a new parse fits the training grammar.
Obtaining high-quality annotation is a bottleneck for corpus and parser development, leading to methods of leveraging existing resources to improve the parameters of a lesser-resourced language—through the use of annotated corpora of higher-resourced languages, parallel language data, universal treebanks, and so on [5, 7, 11, 13, 18, 19, 22]. Building on work that envisions bootstrapping corpora via parse error detection and human correction [3, 24]—from a larger paradigm of exploiting a small amount of annotated data in a language [6, 8, 14]—we focus on extracting more resources from just the treebank itself. Specifically, we explore the use of parse simulations within a (small) treebank to supplement the parameters learned from the treebank itself, in order to improve parse error detection.
This bears much in common with contrastive estimation [e.g., 25, 26] and negative sampling [e.g., 9, 20], where learning is the process of distinguishing a positive example from similar negative examples in the data. With small data and the task of error detection, however, it is not clear whether the simulated information is truly incorrect or not: for small data sets, one may uncover structures which, although incorrect in a particular sentence, can be correct. Thus, instead of maximizing the differences between actually-occurring and simulated data, we employ “negative” information heuristically, to modify the scores of syntactic dependency structures.
Employing simulations has the effect of generalizing the grammar implicit in a treebank. This allows one to explore a large amount of information in the annotation space (e.g., 100x more structures). Our specific contributions are to: Posit annotation simulations during training; Replace ad hoc weighting by a weighting scheme using the simulations, leading to improved error detection precision; and Experiment with different weighting schemes, testing the relationship between simulations and (un)seen structures. 2
We start with the DAPS (Detecting Anomalous Parse Structures) method [3, 4],1 effective across a variety of settings. N -gram sequences of dependency structures are used to identify anomalous (likely erroneous) dependencies. Referring to the suggested simulation (dotted line) in Figure 1 as an example, the process is: 1. Extract rules from dependency trees (rule = a head (H) + its dependents). e.g., one rule (headed by board) is S T A R T det:DT NN-H prep:IN E N D. 2. Extract rule n-grams, e.g., det:DT NN-H prep:IN or prep:IN E N D. 3. Score an element by adding up relevant training n-gram counts. e.g., to score prep:IN here, one adds up training counts of the n-grams with prep:IN.2 Using information from complete trees, the DAPS method serves as a sanity check on more complicated parse models. While such checks may be possible inside a parser, this method optimizes for unlikelihood, whereas parsers more directly maximize likelihood. In the context of low-resource languages, DAPS has the benefit of using very general representations—as opposed to integrating information from, e.g., word clusters—that do not require a lot of (un)annotated data. Insights Our previous DAPS work [3, 24] has noted that not all n-grams are equal: a parsed rule lacking any training bigrams indicates an error, and yet, without more context, bigrams often upweight erroneous rules because they generally occur in training. Previous variations ignored bigrams (high method: n 3) or downweighted them (weighted all-grams [wall]: n 2, bigram counts multiplied by 0:01). Problematic is setting the weight arbitrarily and equally across bigrams.
A second insight comes from a stage of revision checking [3], where revisions (alternative attachments and labelings) are posited for a parse. Errors are flagged when the parser did not choose better-scoring possible revisions. The crucial insight is that dependency trees provide information not only about what they are, but what they could have been, an insight we will apply during training 1http://cl.indiana.edu/~md7/papers/dickinson-smith11.html 2See [3] for more details. nsubj aux
prep dobj det pobj
det prep amod Pierre Vinken ...
NNP NNP ...
will join the board as MD VB DT NN IN a DT nonexecutive director ...
JJ NN ...
We focus on alternate plausible structures within the training data and use these syntactic parse simulations to gauge the utility of each n-gram. Consider, for example, the attachment of the preposition (IN) as in Figure 1. It may help here to see that in the gold tree as doesn’t attach to the immediately preceding noun (NN) board—a potential attachment, as indicated by the gray dotted line.
We view the process of generating alternative structures, i.e., simulations, as involving the reattachment of each node (i.e., word/POS) in the dependency tree. This means that: a) a full set of alternatives is generated for every node in the tree (e.g., for the attachment of Pierre, of Vinken, etc.), and b) no more than one node is reattached for a given simulation (e.g., if as is re-attached, then no other word is). Each simulation is thus only “one off” from the original tree, preventing highly implausible generalizations from the source trees. While each simulation results in a specific incorrect tree (token), to be useful for error detection simulations should ideally correspond to valid structures (types) used elsewhere in the corpus, i.e., plausible structures a parser would likely consider for the sentence at hand.
We use the reattachment procedure as implemented for revision checking (section 2).3 From this, we keep a frequency database of n-grams that actually occurred (A) and a separate one for simulated n-grams (S); we call each database a grammar. The n-grams are a sequence of pairs of POS and dependency labels.
To build plausible simulations, we currently stipulate [cf., e.g., 1, 10] that: a) a posited reattachment must maintain projectivity; and b) its posited dependency label must have been seen with its POS in training.4 We only consider reattachments, and not simple relabelings, because: a) we already posit multiple labels for each reattached dependency, and b) the grammar size is more manageable. One could explore creating new POS, label pairs or filtering implausible simulations; we leave these for future work, but will see the effects of not filtering in section 4.
3The interpretation is different for revision checking, as one hopes to go from an incorrect parse to a correct one, and here the situation is reversed, but the process is the same.
4We do not enforce acyclicity, as in [3], as this unduly restricts the search space for revisions [12]. 3.2
With a definition of simulations, the next step is to integrate such information with actually-occurring rules. As mentioned, we do not simply view every simulation as incorrect, so our methods reflect a gradable nature of the simulations.
During training, we use the actual count of an n-gram (a) and its simulated count (s) to calculate an adjusted score (a ). Previous (0) weighting used an ad hoc weight (wall) on bigrams or no weight (all/high: a = a).
The formulas in Figure 2 attempt to downweight n-grams which are too confusable with other structures to be good indicators of quality (i.e., occur a great deal in simulated fashion [s > a]) and to upweight helpful n-grams (i.e., ones where actual occurrences outweigh simulated ones [a > s]), as can be seen in the ratio as++11 . Starting with formula B, the training grammar is expanded by giving non-zero scores to what we term SimOnly n-grams, where a = 0 and s > 0.
Formulas B–E differ in how they handle the interplay between these SimOnly n-grams, the actually-occurring n-grams (a > 0, Actual), and the never-occurring n-grams (a = 0, s = 0), i.e., the ones Novel to both grammars. The general principles are characterized at the bottom of each section of Figure 2: less important than the specifics is what these indicate about how to use simulations for new data. 3.3
As an additional evaluation, we run revision checking during the error detection stage, in order to see the effect of combining parse simulations with parse revisions. Note what this means: parse simulations posit additional structures to expand grammars during training, while revisions are additional structures posited after parsing. (For revision checking we try both reattachments and relabelings as revisions.) These posited revisions are scored with the same training grammar as the original parse is scored with—i.e., the grammar including simulations—and thus no scoring proceeds in the same way for the parse and any suggested revision. 4 4.1
We use the Wall Street Journal (WSJ) corpus from the Penn Treebank [15], converted to Stanford dependencies [2], to be comparable to previous work [24]. Based on the recommendations we outline in [24], we consider two complementary parsers (graph-based MSTParser [17]; transition-based MaltParser [21]) for the various methods, as well as a more recent one (TurboParser [16]). We use a small training corpus (section 02 [48k tokens]) [see 24], as this matches our focus, and test on a slightly larger corpus (sections 00+01+22 [134k tokens]).
C =1:2 C =2 -2 -2 A B
-2 a =
-2 a = D
-2 E
Novel < SimOnly < Actual Grammar sizes Before evaluating the effectiveness on error detection, we can see the impact of parse simulations by examining training grammar sizes, as in Table 1. In moving from Actual (A) to Simulated (S) grammars, we see a 88x increase in type grammar size (94k to 8.3m) and a 104x increase in token size.5 We also see a gain in type coverage and a drop in token coverage, indicating simulations of infrequent n-grams; given the difficulty of predicting rare events, positing such rules may benefit many applications.6
Grammar (All) 02A 02S 02A[S 00+01+22A
When the entire Actual and Simulated grammars are combined (A [ S), the overlap with the testing data increases by an absolute 13% (types) or 6% (tokens). Creating simulations thus shows promise for expanding the grammar in ways that extend to new data—with a caveat of a huge leap in grammar size for a smaller gain in grammar coverage, thus indicating a need for some grammar filtering. Evaluation metric For evaluating error detection, we report precision (P) of detected errors.7 We rely on equivalently-sized segments across different error detection methods, accounting for recall. Using segment size—e.g., 5% of corpus tokens—approximates the idea of annotators having a set amount of time to correct parser errors [see 24, for discussion]. When it comes to segment size, we assume that correction works from the lowest scores up to the highest.
For methods employing revision checking (sections 2 and 3.3), the methodology is slightly different: first, all flagged positions are examined, from lowest to highest scores, and then all unflagged positions. We focus on flagged positions. 4.2
We report results for MST and Malt in Table 2 and for Turbo in Table 3, with the best formula results in bold, and the best overall results underlined. To summarize: 1) Weighting seems to work, as formula 0 is generally among the worst 5There are 32,199 types (188,698 Actual tokens) in common between the A and S grammars. 6We omit numbers broken down by n-gram size: there are many more types for higher n values. 7In [24], we also recommend reporting a revised labeled attachement score (LASr), to see the impact of correcting errors on resulting corpus quality. As we are more interested in method development and as the LASr trends precisely mirror the precision ones, we do not report LASr here. formulas; 2) The best overall settings seem to be a mixture of hand- (wall) and auto-weighting (A, B, E); and 3) A better parser (Turbo) mitigates the improvements to some extent, but basically follows the same trends.
While the wall method is generally best, for MST and Malt the all method curiously outperforms it for formulas B–E at the 5% size, i.e., bigram weighting seems unhelpful. For Turbo, the all method is almost always lowest, with high and wall being fairly comparable across the different segments; unweighted bigrams (all) are apparently more misleading with a better parser. Additionally, formula E (Novel < SimOnly < Actual) is most often the best setting, but A (ignoring the Novel/SimOnly distinction) can be better. Formulas employing a Novel/SimOnly distinction are perhaps more unstable than formula A.
If forced to pick a best setting, wall.E is consistently strong, aside from its dip at 5% for MST and Malt. Simulations seem to be both positive and negative: formula E equals or outperforms B (SimOnly Actual), while also outperforming D (SimOnly < Novel) and often A (SimOnly Novel). This pattern, along with the 5% dip, may in part be due to not having sorted the simulations: some SimOnly cases behave like Novel and some like Actual n-grams. Model Positions score 0 Employing revision checking presents a slightly different—and more consistent— picture, shown in Tables 4 and 5, where we focus on evaluation cutoffs that highlight the effect of revisions.8 Most noticeably, formula E almost always has the highest precision for both all the flagged positions (AF) and the flagged positions with the lowest scores (0F), and the wall.E method is clearly best. Although some of the differences are small (especially for the MST results), we see 4–10% increases in precision for Malt for the 5% segment, comparing E to formulas 0/A.
We suspect that this improvement comes because simulations and revisions rely upon the same procedure of positing alternate structures, and formula E provides better scoring for the unseen structures involved in the revisions. Because it assigns positive scores to simulated training n-grams (SimOnly), formula E more often positively scores revisions. Thus, it is easier to find a revision that scores better than the original parse (compare, e.g., 86% [= 11;;740600 ] of zero-scoring dependencies being flagged [0F] for Malt.all with formula E vs. 59% [= 23;;162094 ] with formula A). The extended grammar thus helps identify when there is a potentially better 8We also ignore the C and D models here, as they continue to be the worst-performing ones. Model 0F
Model
0F
all.0 86.2% (
But the picture is more complicated: we also need to note that E almost always has higher precision than formula D, the formula that cleanly ranks SimOnly lower than Novel cases. Additionally, formula E generally—though, not always— 9B and E are equivalent when treating zero cases the same, i.e., as Novels only; see Figure 2. outperforms formula A, the formula where Novel and SimOnly are grouped together as equally bad. Taken together, the performances indicate that simulations as a whole are better than cases which have never been seen.
We conjecture that this behavior is due, at least in part, to not having sorted out the simulations: some of the SimOnly cases seem to behave like Novel cases and some more like Actual n-grams. As mentioned, a crucial next step is thus to sort the SimOnly cases, so that only the valid cases receive higher scores. 5
We have improved a method for parse error detection, weighting dependency ngrams on the basis of parse simulations in training. As important as the improvements in error detection is the idea of extending the training grammar for small treebanks by such simulations. As we observed from the results with different formulas, the simulations cannot be treated as wholly correct or incorrect—especially given the small size of the training data—but are nonetheless useful for helping determine whether a new parse fits into the (extended) grammar.
There are several next steps for this work. There is a need to try different (sub)sets of simulations, to see which constraints or filters can be best employed, in particular to sort out the good and bad SimOnly cases. Adding filters will increase the amount of time spent in building a grammar during training, but result in smaller—as well as more accurate—grammars, thus improving the speed for post-parsing analysis. We have experimented only with a small training corpus, resulting in a huge extension of n-grams; one could investigate larger and more diverse training corpora, to observe both the effectiveness of the techniques and the efficiency with such large grammars.
One could also test the methods on out-of-domain data, to see how well the grammar extensions cover different kinds of data, as well as comparing to alternative methods of tree exploration, such as parse reranking models employing ngrams or subtree features over a set of k-best parses [e.g., 23]. In that light, one also needs to explore more extrinsic evaluation, to see whether the methods are actually identifying errors that truly impact parsing models (i.e., have a real-world impact) vs. ones which are more ad hoc.
We wish to thank the three anonymous reviewers for very helpful feedback, as well as the CL discussion group at Indiana University.