Alto: Rapid Prototyping for Parsing and Translation

What it is about

Alto is an open-source toolkit for grammar formalisms. It is built on Interpreted Regular Tree Grammars (IRTGs). A regular tree grammar produces derivation trees, and each interpretation maps a derivation tree through a homomorphism into a term over an algebra, such as strings or graphs. The same derivation can therefore give a string, a graph, or both, and a synchronous grammar is one IRTG with two interpretations. The toolkit implements generic algorithms: binarisation, parse charts, best and k-best derivations, EM and log-linear training, and decoding from one interpretation into another. A new formalism needs only a new algebra with its decomposition operation, and the generic algorithms apply to it. The implementations are lazy, so rules are computed only when needed. The paper is a tool description, with an example of a string-to-graph grammar; it reports no accuracy numbers.

Ideas

• I1. One derivation, several readings: keep the reader's derivation (the parse with its frames) as the single object, and give it separate interpretations: the meta-world, the English string, and the Hebrew-side gloss. The interpretations are separate tables over one tree, so a change in one does not touch the others. This follows the split in tools/roundtrip between tree and world.
• I2. Lazy evaluation of rule tables: compute the encoder's chunk table for a meta token only when the token is seen, not for the whole table, and count how many entries are touched per verse. This keeps the run cheap and shows which entries matter.
• I3. Best and k-best derivations as a measurement: report the k-best encoder outputs for k = 1 and k = 5 on the dev verses, with their scores, so the residual of the best and the second-best output can be compared. This makes the choice of the encoder visible.
• I4. Do not adopt the toolkit: the paper's algorithms are for weighted regular tree grammars, which Mova does not use. The ideas to take are the separation of derivation and interpretation, and the counting of how many rules a parse touches.

For Mova

The code is tools/translate (encoder and meta-world) and tools/roundtrip (tree and world). Alto is a tool for grammars, not for Mova's counts, so it is a design reference only. The separation of derivation from interpretation answers the frame-versus-tree question in open problem 1, with no new library.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/e17-3008

@inproceedings{gontrum2017alto,
  title = {{Alto: Rapid Prototyping for Parsing and Translation}},
  author = {Gontrum, Johannes and Groschwitz, Jonas and Koller, Alexander and Teichmann, Christoph},
  booktitle = {Proceedings of the Software Demonstrations of the 15th Conference of the European Chapter of the Association for Computational Linguistics},
  year = {2017},
  doi = {10.18653/v1/e17-3008},
  url = {https://doi.org/10.18653/v1/e17-3008}
}

References

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

1. A. K. Joshi, L. S. Levy, and M. Takahashi. 1975. Tree adjunct grammars. Journal of Computer and System Sciences, 10(1):136–163. find
2. L. Banarescu, C. Bonial, S. Cai, M. Georgescu, K. Griffitt, U. Hermjakob, K. Knight, P. Koehn, M. Palmer, and N. Schneider. 2013. Abstract meaning representation for sembanking. In Proceedings of the 7th Linguistic Annotation Workshop. find our card
3. A. Koller and M. Kuhlmann. 2011. A generalized view on parsing and translation. In Proceedings of the 12th International Conference on Parsing Technologies. find
4. A. Koller and M. Kuhlmann. 2012. Decomposing tag algorithms using simple algebraizations. In Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+11). find
5. M. Büchse, A. Koller, and H. Vogler. 2013. Generic binarization for parsing and translation. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics. find
6. E. Charniak, M. Johnson, M. Elsner, J. Austerweil, D. Ellis, I. Haxton, C. Hill, R. Shrivaths, J. Moore, M. Pozar, and T. Vu. 2006. Multilevel coarse-to-fine pcfg parsing. In Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL. find
7. M. Lewis, K. Lee, and L. Zettlemoyer. 2016. LSTM CCG parsing. In Proceedings of NAACL-HLT. find our card
8. K. Sima’an, R. Bod, S. Krauwer, and R. Scha. 1994. Efficient disambiguation by means of stochastic tree substitution grammars. In Proceedings of International Conference on New Methods in Language Processing. find
9. D. Chiang, J. Andreas, D. Bauer, K. M. Hermann, B. Jones, and K. Knight. 2013. Parsing graphs with find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/gontrum-2017-alto-rapid-prototyping-parsing-translation/