Learning Non-Isomorphic Tree Mappings for Machine Translation

What it is about

Eisner proposes learning a mapping between two trees that need not have the same shape. The model is a synchronous tree substitution grammar (STSG): a set of pairs of elementary trees, each pair with a state for every open position, which combine into a pair of derived trees. He gives a probabilistic form, a tree parsing algorithm that finds all ways to cut a tree into elementary trees with bounded size (for dependency trees, at most three internal nodes), and EM training with an inside-outside pass over all derivations, so unaligned tree pairs can be used. Empty elementary trees handle free-translation mismatches, such as a deleted quantifier or an inserted adverb, and a matching between frontier nodes allows a chunk to be aligned to a non-isomorphic chunk. The paper is a short sketch. It reports the algorithms and an implementation status, but no experiments and no numbers.

Ideas

• I1. Empty meta tokens for deletions and insertions. A verse pair often adds or drops a word (and, the, a pronoun). Give the reader a null-concept meta token for each side, so a dropped word is recorded as a deletion, not lost. Count these per author (open problem 4).
• I2. Chunk-to-chunk pairs learned from unaligned verse pairs. Enumerate the decompositions of the two trees into bounded chunks, weight them by the current counts, and keep a chunk pair (give a kiss to to kiss) only when it lowers the residual. This is the count-based version of the residual-driven lexicon (open problem 2).
• I3. Put number and person into the states of the chunk table. The paper uses states such as (plural, third person) for a subject slot, which is the UD FEATS idea of open problem 5 for meta tokens.
• I4. Prune matchings whose inside score is low, and compare the pruned and full search on a dev set of verses. The control is the exact encoder output: pruning must leave it unchanged on dev.

For Mova

The relevant code is tools/translate (meta.rs for the chunk pairs and the null tokens, profile.rs for the encoder). The paper's EM is not needed as such: the counted decompositions of verse pairs can be kept as integer counts in ordered maps. Since the paper has no results, the first step is a measurement, not a claim: count how many verse pairs need a null token on each side.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1075178.1075217

@inproceedings{eisner2003learning,
  title = {{Learning Non-Isomorphic Tree Mappings for Machine Translation}},
  author = {Eisner, Jason},
  booktitle = {The Companion Volume to the Proceedings of 41st Annual Meeting of the Association for Computational Linguistics},
  year = {2003},
  doi = {10.3115/1075178.1075217},
  url = {https://doi.org/10.3115/1075178.1075217}
}

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/eisner-2003-learning-non-isomorphic-tree-mappings/