Elamur Research⌕
☰
home / papers / 2012 / Mining Rules for Rewriting States in a Transition-based Dependency Parser for English

Mining Rules for Rewriting States in a Transition-based Dependency Parser for English

Paper · 2012 · Akihiro Inokuchi and Ayumu Yamaoka

Summary

Transition-based dependency parsers make local decisions. Once a wrong arc is added, the correct tree can no longer be reached, and even beam search sometimes ends in a wrong final state. It is also hard to tell why this happens. The authors connect parsing to graph sequence mining. Each state of an arc-eager parser becomes a graph whose vertices are words and whose edges are dependencies, so a whole parse becomes a graph sequence. Their earlier miner, GTRACE, describes the step between consecutive graphs as a short list of edit operations. Running it over parser transition sequences yields frequent, human-readable rewriting rules, each of which redirects a state heading to a wrong tree toward one that reaches the correct tree. The authors study three of these rules and use what they learn to design new feature templates for a beam-search arc-eager parser in the style of Zhang and Clark (2008), evaluated on the WSJ treebank. Attachment scores go up, most clearly at narrow beams. The broader contribution is a systematic way to diagnose parser errors and turn the diagnosis into better features.

Key points

  • Each arc-eager parser state is redefined as a forest of ordered trees, with a marked subset of unreduced vertices on the rightmost paths. A transition changes at most two elements of this graph, which satisfies GTRACE's assumption that "change is gradual".
  • The mined rules act as bypasses in the search space, a DAG rooted at the initial state with final states as leaves. They show how a state on a path to a wrong final state could be rewritten into one on a path to the correct final state.
  • Three rules led to three groups of new templates:
    • a flag that fires when "said/say/says" occurs later in the sentence;
    • features using the word of the stack top's parent, which helps with constructions like "because of NN";
    • word trigrams around the buffer top, which help with proper compound nouns.
  • The data split was WSJ sections 02–21 for training, 22 for development and 23 for testing. With beam 64 and the added features, the parser reaches 92.67% attachment score. This is comparable to other parsers of the time, such as Zhang and Nivre (2011) at 93.07% and Koo and Collins (2010) at 93.04%.
  • Also applying the mined rules directly could not be run at beam 64 because memory overflowed. The authors argue their method extends to any transition system with graph-shaped states, including phrase-structure parsing. Revision rules that only edit output edges cannot do this.

Interesting ideas

  • I1. Treat each parser run as a sequence of graph states and mine frequent edit patterns on the runs that went wrong, so that error analysis targets the internal decision process rather than only the final tree.
  • I2. Express repairs as rewrites of an intermediate parser state, not as post-hoc relabeling of output arcs. A rule at the state level can explain where the parse went off track and also covers systems that add nodes.
  • I3. Use mined rules as human-readable hints for designing features instead of applying them blindly. In the paper this produced cheap features that generalized well, and it avoided the memory cost of applying the rules at runtime.
  • I4. Report gains across a range of beam widths. The improvement from better features was largest at small beams, which shows where extra knowledge substitutes for extra search.
  • I5. Encode change between successive structures as a minimal ordered list of vertex and edge insertions, deletions and relabelings, which makes long evolving structures compact and minable.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (learn): Logging the perceptron parser's state trajectories and mining recurring divergences from silver/gold paths could become a source of self-induced repair rules, each one readable and attributable.
  • I2 (tree): Repair rules for the parser could be stated as "in state X, prefer transition Y", which keeps every correction tied to an explainable decision point.
  • I3 (tree): Mined error patterns could suggest new perceptron feature templates, such as a sentence-level flag for a reporting verb appearing later, computed in linear time during preprocessing.
  • I4 (learn): Evaluating parser changes at several beam sizes would show whether a fix adds real knowledge or only compensates for weak search.
  • I5 (world): The same edit-operation encoding could represent how entities, holdings and states change between events in a story, allowing frequent change patterns to be mined.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓The University of OsakaOsaka · Japan17 works · 517 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksInformation Systems · 1,730 works

🧭 Topics 2Research subjects and languages the work is about.English · 2,379 worksDependency parsing · 132 works

Cite

Cite as Akihiro Inokuchi and Ayumu Yamaoka. 2012. Mining Rules for Rewriting States in a Transition-based Dependency Parser for English. Proceedings of COLING 2012.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{inokuchi2012mining,
  title = {{Mining Rules for Rewriting States in a Transition-based Dependency Parser for English}},
  author = {Akihiro Inokuchi and Ayumu Yamaoka},
  booktitle = {Proceedings of COLING 2012},
  year = {2012},
  url = {https://aclanthology.org/C12-1078/}
}

References

29 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Agrawal, R., and Srikant, R. 1994. Fast Algorithms for Mining Association Rules in Large Databases. Proc. of Int’l Conf. on Very Large Data Bases (VLDB), 487–499. find
  2. Ahmed, R., and Karypis, G. 2011. Algorithms for Mining the Evolution of Conserved Relational States in Dynamic Networks. Proc. of IEEE Int’l Conf. on Data Mining (ICDM), 1–10. find
  3. Attardi, G. and Ciaramita, M. 2008. Tree Revision Learning for Dependency Parsing. Proc. of Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, (HLT-NAACL), 388–395. find
  4. Berlingerio, M., et al., 2009. Mining Graph Evolution Rules. Proc. of Euro. Conf. on Principles and Practice of Knowledge Discovery in Databases (PKDD), 115–130. find
  5. Borgwardt, K. M., et al., 2006. Pattern Mining in Frequent Dynamic Subgraphs. Proc. of IEEE Int’l Conf. on Data Mining (ICDM), 818–822. find
  6. Collins, M., and Roark, B. 2004. Incremental parsing with the perceptron algorithm. Proc. of the 42nd Annual Meeting of the Association for Computational Linguistics(ACL), pp. 111-118.
  7. Culotta, A., and Sorensen, J. 2004. Dependency Tree Kernels for Relation Extraction. Proc. of Annual Meeting of Association for Comp. Linguistics (ACL), 423–429.
  8. Ding, Y., and Palmer, M. 2004. Automatic Learning of Parallel Dependency Treelet Pairs. Proc. of Int’l Joint Conf. on Natural Language Processing, 233–243. find
  9. Garey, M., and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York. find
  10. Goldberg, Y. and Elhadad, M. 2010. An efficient algorithm for easy-first non-directional dependency parsing. Proc of Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL), pp. 742–750. find
  11. Hayashi, K. et al., 2011. The third-order variational reranking on packed-shared dependency forests. Proc. of Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1479–1488. find
  12. Hayashi, K., et al., 2012. Head-driven Transition-based Parsing with Top-down Prediction. Proc. of the Annual Meeting of the Association for Computational Linguistics(ACL). find
  13. Huang, L., and Sagae, K. 2010. Dynamic Programming for Linear-Time Incremental Parsing. Proc. of Annual Meeting of the Association for Computational Linguistics (ACL), 1077-1086. find
  14. Inokuchi A., and Washio, T. 2008. A Fast Method to Mine Frequent Subsequences from Graph Sequence Data. Proc. of IEEE Int’l Conf. on Data Mining (ICDM), 303–312. find
  15. Inokuchi, A., et al., 2012. Efficient Graph Sequence Mining Using Reverse Search. IEICE Transactions 95-D(7), 1947–1958 find
  16. Inokuchi, A., et al., 2012. Mining Rules for Rewriting States in a Transition-Based Dependency Parser. Proc of Pacific Rim International Conference on Artificial Intelligence (PRICAI), 133–145. find
  17. Iwatate, M., et al., 2008. Japanese Dependency Parsing Using a Tournament Model. Proc. of Int’l Conf. on Comp. Linguistics (COLING), 361–368. find
  18. Kitagawa, K. and Tanaka-Ishii, K. 2010. Tree-based deterministic dependency parsing - an application to Nivre’s method. Proc. of Annual Meeting of the Association for Computational Linguistics (ACL), Short Papers, pp. 189–193. find
  19. Koo, T. and Collins, M. 2010. Efficient third-order dependency parsers. Proc. of Annual Meeting of the Association for Computational Linguistics (ACL), pp. 1–11. find
  20. Kubler, S., et al., 2009. Dependency Parsing. Morgan and Claypool Publishers. find
  21. Kudo, T., and Matsumoto, Y. 2002. Japanese Dependency Analysis using Cascaded Chunking. Proc. of Conf. on Comp. Natural Language Learning (CoNLL), 63–69. find
  22. Kudo, T. et al. 2005. Boosting-based Parse Reranking with Subtree Features. Proc. of Annual Meeting of the Association for Computational Linguistics (ACL). find
  23. Makinen, E. 1989. On the Subtree Isomorphism Problem for Ordered Trees. Information Processing Letters 32(5), 271–273. find
  24. McDonald, R. and Pereira, F. 2006. Online learning of approximate dependency parsing algorithms. Proc. of Conference of European Chapter of the Association for Computational Linguistics (EACL), pp. 81–88.
  25. Nivre, J. 2008. Algorithms for Deterministic Incremental Dependency Parsing. Comp. Linguistics 34(4), 513–553.
  26. Pei, J., et al., 2001. PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Proc. of Int’l Conf. on Data Engineering (ICDE), 2–6. find
  27. Yamada, H., and Matsumoto, M. 2003. Statistical dependency analysis with support vector machines. Proc. of the International Workshop on Parsing Technologies (IWPT), pp 195–206.
  28. Zhang, Y., and Clark, S. 2008. A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing. Proc. of Conf. on Empirical Methods in Natural Language Processing (EMNLP), 562-571.
  29. Zhang, Y. and Nivre, J. 2011. Transition-based dependency parsing with rich non-local features. Proc. of Annual Meeting of the Association for Computational Linguistics (ACL), pp. 188– 193. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/inokuchi-2012-mining-rules-rewriting-states-transition/