Error Mining on Dependency Trees
Gardent, Claire and Narayan, Shashi

Article Structure

Abstract

In recent years, error mining approaches were developed to help identify the most likely sources of parsing failures in parsing systems using handcrafted grammars and lexicons.

Introduction

In recent years, error mining techniques have been developed to help identify the most likely sources of parsing failure (van Noord, 2004; Sagot and de la Clergerie, 2006; de Kok et al., 2009).

Mining Trees

Mining for frequent subtrees is an important problem that has many applications such as XML data mining, web usage analysis and RNA classification.

Mining Dependency Trees

We develop an algorithm (called ErrorTreeMiner, ETM) which adapts the HybridTreeMiner algorithm to mine sources of generation errors in the Generation Challenge SR shallow input data.

Experiment and Results

Using the input data provided by the Generation Challenge SR Task, we applied the error mining algorithm described in the preceding Section to debug and extend a symbolic surface realiser developed for this task.

Related Work

We now relate our proposal (i) to previous proposals on error mining and (ii) to the use of error mining in natural language generation.

Conclusion

Previous work on error mining has focused on applications (parsing) where the input data is sequential working mainly on words and part of speech tags.

Topics

POS tag

Appears in 18 sentences as: POS tag (15) POS tags (7)
In Error Mining on Dependency Trees
  1. One feature of our approach is that it permits mining the data for tree patterns of arbitrary size using different types of labelling information ( POS tags , dependencies, word forms and any combination thereof).
    Page 5, “Experiment and Results”
  2. 4.3.1 Mining on single labels (word form, POS tag or dependency)
    Page 5, “Experiment and Results”
  3. Mining on a single label permits (i) assessing the relative impact of each category in a given label category and (ii) identifying different sources of errors depending on the type of label considered ( POS tag , dependency or word form).
    Page 5, “Experiment and Results”
  4. Mining on POS tags Table 1 illustrates how mining on a single label (in this case, POS tags) gives a good overview of how the different categories in that label type impact generation: two POS tags (POS and CC) have a suspicion rate of 0.99 indicating that these categories always lead generation to fail.
    Page 5, “Experiment and Results”
  5. Other POS tag with much lower suspicion rate indicate that there are unresolved issues with, in decreasing order of suspicion rate, cardinal numbers (CD), proper names (N N P), nouns (N N ), prepositions (IN) and determiners (DT).
    Page 5, “Experiment and Results”
  6. 5 In the Penn Treebank, the POS tag is the category assigned to possessive ’s.
    Page 5, “Experiment and Results”
  7. Table 1: Error Mining on POS tags with frequency cutoff 0.1 and displaying only trees of size 1 sorted by decreasing suspicion rate (Sus)
    Page 6, “Experiment and Results”
  8. We will see below how the richer information provided by mining for larger tree patterns with mixed labelling information permits identifying the contexts in which these POS tags lead to generation failure.
    Page 6, “Experiment and Results”
  9. Mining on Word Forms Because we remove from the failure set all cases of errors due to a missing word form in the lexicon, a high suspicion rate for a word form usually indicates a missing or incorrect lexical entry: the word is present in the lexicon but associated with either the wrong POS tag and/or the wrong TAG tree/family.
    Page 6, “Experiment and Results”
  10. To capture such cases, we therefore mine not on word forms alone but on pairs of word forms and POS tag .
    Page 6, “Experiment and Results”
  11. (Sus=1) was assigned the POS tag $ in the input data, a POS tag which is unknown to our system and not documented in the SR Task guidelines.
    Page 6, “Experiment and Results”

See all papers in Proc. ACL 2012 that mention POS tag.

See all papers in Proc. ACL that mention POS tag.

Back to top.

subtrees

Appears in 15 sentences as: subtrees (17)
In Error Mining on Dependency Trees
  1. by (Chi et al., 2004) for discovering frequently occurring subtrees in a database of labelled unordered trees.
    Page 2, “Introduction”
  2. Section 3 shows how to adapt this algorithm to mine the SR dependency trees for subtrees with high suspicion rate.
    Page 2, “Introduction”
  3. Mining for frequent subtrees is an important problem that has many applications such as XML data mining, web usage analysis and RNA classification.
    Page 2, “Mining Trees”
  4. The HybridTreeMiner (HTM) algorithm presented in (Chi et al., 2004) provides a complete and com—putationally efficient method for discovering frequently occurring subtrees in a database of labelled unordered trees and counting them.
    Page 2, “Mining Trees”
  5. Second, the subtrees of the BFCF trees are enumerated in increasing size order using two tree operations called join and extension and their support (the number of trees in the database that contains each subtree) is recorded.
    Page 2, “Mining Trees”
  6. In effect, the algorithm builds an enumeration tree whose nodes are the possible subtrees of T and such that, at depth d of this enumeration tree, all possible frequent subtrees consisting of d nodes are listed.
    Page 2, “Mining Trees”
  7. The join and extension operations used to iteratively enumerate subtrees are depicted in Figure 2 and can be defined as follows.
    Page 2, “Mining Trees”
  8. For the join operation, the subtrees being combined must occur in the same tree at the same position (the intersection of their occurrence lists must be non empty and the tree nodes must match except the last node).
    Page 3, “Mining Trees”
  9. Since we work with subtrees of arbitrary length, we also need to check whether constructing a longer subtree is useful that is, whether its suspicion rate is equal or higher than the suspicion rate of any of the subtrees it contains.
    Page 3, “Mining Dependency Trees”
  10. In that way, we avoid computing all subtrees (thus saving time and space).
    Page 3, “Mining Dependency Trees”
  11. Because we use a milder condition however (we accept bigger trees whose suspicion rate is equal to the suspicion rate of any of their subtrees ), some amount of
    Page 3, “Mining Dependency Trees”

See all papers in Proc. ACL 2012 that mention subtrees.

See all papers in Proc. ACL that mention subtrees.

Back to top.

dependency trees

Appears in 14 sentences as: dependency tree (3) Dependency Trees (1) dependency trees (12)
In Error Mining on Dependency Trees
  1. Dependency Trees
    Page 1, “Introduction”
  2. For instance, when generating sentences from dependency trees , as was proposed recently in the Generation Challenge Surface Realisation Task (SR Task, (Belz et al., 2011)), it would be useful to be able to apply error mining on the input trees to find the most likely causes of generation failure.
    Page 1, “Introduction”
  3. We adapt an existing algorithm for tree mining which we then use to mine the Generation Challenge dependency trees and identify the most likely causes of generation failure.
    Page 1, “Introduction”
  4. Section 3 shows how to adapt this algorithm to mine the SR dependency trees for subtrees with high suspicion rate.
    Page 2, “Introduction”
  5. Section 4 presents an experiment we made using the resulting tree mining algorithm on SR dependency trees and summarises the results.
    Page 2, “Introduction”
  6. In the next section, we will show how to modify this algorithm to mine for errors in dependency trees .
    Page 2, “Mining Trees”
  7. First, dependency trees are converted to Breadth—First Canonical Form whereby lexicographic order can apply to the word forms labelling tree nodes, to their part of speech, to their dependency relation or to any combination thereof3.
    Page 4, “Mining Dependency Trees”
  8. 3For convenience, the dependency relation labelling the edges of dependency trees is brought down to the daughter node of the edge.
    Page 4, “Mining Dependency Trees”
  9. It consists of a set of unordered labelled syntactic dependency trees whose nodes are labelled with word forms, part of speech categories, partial morphosyntactic information such as tense and number and, in some cases, a sense tag identifier.
    Page 4, “Experiment and Results”
  10. The chunking was performed by retrieving from the Penn Treebank (PTB), for each phrase type, the yields of the constituents of that type and by using the alignment between words and dependency tree nodes provided by the organisers of the SR Task.
    Page 5, “Experiment and Results”
  11. Using this chunked data, we then ran the generator on the corresponding SR Task dependency trees and stored separately, the input dependency trees for which generation succeeded and the input dependency trees for which generation failed.
    Page 5, “Experiment and Results”

See all papers in Proc. ACL 2012 that mention dependency trees.

See all papers in Proc. ACL that mention dependency trees.

Back to top.

Penn Treebank

Appears in 8 sentences as: Penn Treebank (6) Penn treebank (2)
In Error Mining on Dependency Trees
  1. The shallow input data provided by the SR Task was obtained from the Penn Treebank using the LTH Constituent—to—Dependency Conversion Tool for Penn—style Treebanks (Pennconverter, (J ohans—son and Nugues, 2007)).
    Page 4, “Experiment and Results”
  2. The chunking was performed by retrieving from the Penn Treebank (PTB), for each phrase type, the yields of the constituents of that type and by using the alignment between words and dependency tree nodes provided by the organisers of the SR Task.
    Page 5, “Experiment and Results”
  3. 5 In the Penn Treebank , the POS tag is the category assigned to possessive ’s.
    Page 5, “Experiment and Results”
  4. The SR guidelines specify that the Penn Treebank tagset is used modulo the modifications which are explicitly listed.
    Page 6, “Experiment and Results”
  5. However for the $ symbol, the Penn treebank used SYM as a POS tag and the SR Task $, but the modification is not listed.
    Page 6, “Experiment and Results”
  6. Similarly, while in the Penn treebank , punctuations are assigned the SYM POS tag, in the SR data “,” is used for the comma, “(“ for an opening bracket and so on.
    Page 6, “Experiment and Results”
  7. (Callaway, 2003) avoids this shortcoming by converting the Penn Treebank to the format expected by his realiser.
    Page 8, “Related Work”
  8. Using the Penn Treebank sentences associated with each SR Task dependency tree, we will create the two tree sets necessary to support error mining by dividing the set of trees output by the surface realiser into a set of trees (FAIL) associated with overgeneration (the generated sentences do not match the original sentences) and a set of trees (SUCCESS) associated with success (the generated sentence matches the original sentences).
    Page 8, “Conclusion”

See all papers in Proc. ACL 2012 that mention Penn Treebank.

See all papers in Proc. ACL that mention Penn Treebank.

Back to top.

Treebank

Appears in 8 sentences as: Treebank (6) treebank (2) Treebanks (1)
In Error Mining on Dependency Trees
  1. The shallow input data provided by the SR Task was obtained from the Penn Treebank using the LTH Constituent—to—Dependency Conversion Tool for Penn—style Treebanks (Pennconverter, (J ohans—son and Nugues, 2007)).
    Page 4, “Experiment and Results”
  2. The chunking was performed by retrieving from the Penn Treebank (PTB), for each phrase type, the yields of the constituents of that type and by using the alignment between words and dependency tree nodes provided by the organisers of the SR Task.
    Page 5, “Experiment and Results”
  3. 5 In the Penn Treebank , the POS tag is the category assigned to possessive ’s.
    Page 5, “Experiment and Results”
  4. The SR guidelines specify that the Penn Treebank tagset is used modulo the modifications which are explicitly listed.
    Page 6, “Experiment and Results”
  5. However for the $ symbol, the Penn treebank used SYM as a POS tag and the SR Task $, but the modification is not listed.
    Page 6, “Experiment and Results”
  6. Similarly, while in the Penn treebank , punctuations are assigned the SYM POS tag, in the SR data “,” is used for the comma, “(“ for an opening bracket and so on.
    Page 6, “Experiment and Results”
  7. (Callaway, 2003) avoids this shortcoming by converting the Penn Treebank to the format expected by his realiser.
    Page 8, “Related Work”
  8. Using the Penn Treebank sentences associated with each SR Task dependency tree, we will create the two tree sets necessary to support error mining by dividing the set of trees output by the surface realiser into a set of trees (FAIL) associated with overgeneration (the generated sentences do not match the original sentences) and a set of trees (SUCCESS) associated with success (the generated sentence matches the original sentences).
    Page 8, “Conclusion”

See all papers in Proc. ACL 2012 that mention Treebank.

See all papers in Proc. ACL that mention Treebank.

Back to top.

dependency relation

Appears in 3 sentences as: dependency relation (3)
In Error Mining on Dependency Trees
  1. First, dependency trees are converted to Breadth—First Canonical Form whereby lexicographic order can apply to the word forms labelling tree nodes, to their part of speech, to their dependency relation or to any combination thereof3.
    Page 4, “Mining Dependency Trees”
  2. 3For convenience, the dependency relation labelling the edges of dependency trees is brought down to the daughter node of the edge.
    Page 4, “Mining Dependency Trees”
  3. Interestingly, the underspecified dependency relation DEP which is typically used in cases for which no obvious syntactic dependency comes to mind shows a suspicion rate of 0.61 (595F/371P).
    Page 6, “Experiment and Results”

See all papers in Proc. ACL 2012 that mention dependency relation.

See all papers in Proc. ACL that mention dependency relation.

Back to top.

iteratively

Appears in 3 sentences as: iteratively (3)
In Error Mining on Dependency Trees
  1. The join and extension operations used to iteratively enumerate subtrees are depicted in Figure 2 and can be defined as follows.
    Page 2, “Mining Trees”
  2. Next, the algorithm iteratively enumerates the subtrees occurring in the input data in increasing size order and associating each subtree t with two occurrence lists namely, the list of input trees in which t occurs and for which generation was successful (PASS (1%)); and the list of input trees in which t occurs and for which generation failed (FAIL(t)).
    Page 4, “Mining Dependency Trees”
  3. The approach was later extended and refined in (Sagot and de la Clergerie, 2006) and (de Kok et al., 2009) whereby (Sagot and de la Clergerie, 2006) defines a suspicion rate for n—grams which takes into account the number of occurrences of a given word form and iteratively defines the suspicion rate of each word form in a sentence based on the suspicion rate of this word form in the corpus; (de Kok et al., 2009) combined the iterative error mining proposed by (Sagot and de la Clergerie, 2006) with expansion of forms to n—grams of words and POS tags of arbitrary length.
    Page 7, “Related Work”

See all papers in Proc. ACL 2012 that mention iteratively.

See all papers in Proc. ACL that mention iteratively.

Back to top.

semantic representations

Appears in 3 sentences as: semantic representation (1) semantic representations (2)
In Error Mining on Dependency Trees
  1. The surface realisation algorithm extends the algorithm proposed in (Gardent and Perez—Beltrachini, 2010) and adapts it to work on the SR dependency input rather than on flat semantic representations .
    Page 5, “Experiment and Results”
  2. Typically, the input to surface realisation is a structured representation (i.e., a flat semantic representation , a first order logic formula or a dependency tree) rather than a string.
    Page 8, “Related Work”
  3. Approaches based on reversible grammars (Carroll et al., 1999) have used the semantic formulae output by parsing to evaluate the coverage and performance of their realiser; similarly, (Gardent et al., 2010) developed a tool called GenSem which traverses the grammar to produce flat semantic representations and thereby provide a benchmark for performance and coverage evaluation.
    Page 8, “Related Work”

See all papers in Proc. ACL 2012 that mention semantic representations.

See all papers in Proc. ACL that mention semantic representations.

Back to top.

PDF available from www.aclweb.org.
Send us an email