Elamur Research⌕
☰
home / papers / 2008 / Generalizing Word Lattice Translation

Generalizing Word Lattice Translation

Summary

Text-based statistical MT systems usually commit to a single source-side analysis, such as one Chinese word segmentation or one Arabic morphological split, before decoding. Errors made at that stage cannot be undone later. Dyer, Muresan and Resnik take lattice decoding, a technique already common in speech translation, and apply it to text. Competing analyses are packed into a word lattice, and the decoder picks the path and the translation together. The authors adapt two decoder families to lattice input. For hierarchical phrase-based (SCFG) models they use a lattice-aware CKY-style parser. For phrase-based models they extend Moses so that it tracks covered lattice nodes rather than covered words. They also address a problem specific to non-linear lattices: distance-based distortion is ill-defined there because paths differ in length, and they handle it with a simple heuristic. On Chinese-English (several segmentations combined) and Arabic-English (surface and morphologically segmented forms combined), lattice input beats every single-analysis baseline in BLEU on NIST MT05 and MT06. This shows that keeping preprocessing ambiguity until decoding pays off well beyond speech input.

Key points

  • The model is framed as a "noisier channel": an observation yields a set of possible source strings, and the decoder maximizes over both the translation and the source string. Lattices are treated as weighted FSAs, encoded as a topologically ordered chart ⟨F, p, R⟩.
  • Two decoders were adapted:
    • a Chiang-style hierarchical decoder, using a lattice parser written as a deductive system with ε-edge handling, plus cube pruning for LM intersection;
    • Moses, with node-based coverage vectors and a reachability check so that later spans stay coverable.
  • Chinese-English results: the lattices combine the segmentations labeled cs, hs and ss. The Stanford and Harbin segmenters are credited in the acknowledgments.
    • Phrase-based: MT05 BLEU rose from 0.2833 (cs) to 0.2993 (hs+ss+cs), and to 0.3072 with the lexRo variant.
    • Hierarchical: MT05 BLEU rose from 0.2904 to 0.3176, and MT06 from 0.2821 to 0.3043.
  • Arabic-English setup: lattices merge surface tokens with segmented clitics and definiteness/future markers. The segmentations are produced by the Buckwalter analyzer, with ambiguity resolved by a unigram model estimated from Penn Arabic Treebank data.
    • Training used NIST MT08 data with Papineni's n-gram-based subsampling.
    • The language model was a 5-gram LM trained on 250M English words.
    • Weights were tuned with MER on MT03.
  • Arabic-English results (MT05/MT06 BLEU):
Modelsurfacemorphmorph+surface
Phrase-based0.4682 / 0.35120.5087 / 0.38410.5225 / 0.4008
Hierarchical0.5253 / 0.39910.5377 / 0.41800.5453 / 0.4287

Interesting ideas

  • I1. Delay preprocessing decisions. Rather than choosing one tokenization or segmentation up front, pass all plausible analyses to the downstream model as a lattice. This fits any morphologically rich language, such as Ukrainian with ambiguous lemma or segment splits, where a pipeline would otherwise propagate early mistakes.
  • I2. Combine heterogeneous analyzers. Merging outputs from several segmenters, or surface plus segmented forms, into one lattice outperformed each source alone. Ensembling at the input-representation level is cheap and can be tried in other pipelines.
  • I3. Count coverage over graph nodes, not words. Measuring progress by covered lattice nodes, together with a check that the remaining gaps are still reachable, turns a sequence decoder into a graph decoder with minimal changes. The same trick applies to other left-to-right search procedures over DAG inputs.
  • I4. Use one parser for strings and lattices. Writing the parser as a deductive system whose rules move across lattice edges, including ε-edges, means a plain sentence is just the degenerate case. That keeps a single code path for both kinds of input.
  • I5. Keep reordering in the design. The paper points out that earlier lattice-translation work often decoded monotonically or required confusion networks. Checking that distance-based features stay well-defined on non-linear inputs is a useful sanity check whenever sequence features are moved onto graphs.

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

Fields: Natural language processing

Topics: Machine translation

Cited by

98 papers of our library cite it (of the 140884 whose bibliographies we read); 4 of them have a page here, 94 not yet.

Cite

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

@inproceedings{dyer2008generalizing,
  title = {{Generalizing Word Lattice Translation}},
  author = {Dyer, Christopher and Muresan, Smaranda and Resnik, Philip},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  doi = {10.21236/ada482158},
  url = {https://doi.org/10.21236/ada482158}
}

References

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

  1. S. Bangalore and G. Riccardi. 2000. Finite state models for lexical reordering in spoken language translation. In Proc. Int. Conf. on Spoken Language Processing, pages 422–425, Beijing, China. find
  2. A.L. Berger, V.J. Della Pietra, and S.A. Della Pietra. 1996. A maximum entropy approach to natural language processing. Comput. Linguist., 22(1):39–71. find our card
  3. N. Bertoldi and M. Federico. 2005. A new decoder for spoken language translation based on confusion networks. In Proceedings of the IEEE Automatic Speech Recognition and Understanding Workshop. find
  4. N. Bertoldi, R. Zens, and M. Federico. 2007. Speech translation by confusion network decoding. In Proceeding of ICASSP 2007, Honolulu, Hawaii, April. find
  5. P.F. Brown, J. Cocke, S. Della-Pietra, V.J. Della-Pietra, F. Jelinek, J.D. Lafferty, R.L. Mercer, and P.S. Roossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16:79–85. find
  6. F. Casacuberta, H. Ney, F. J. Och, E. Vidal, J. M. Vilar, S. Barrachina, I. Garcia-Varea, D. Llorens, C. Martinez, S. Molau, F. Nevado, M. Pastor, D. Pico, A. Sanchis, and C. Tillmann. 2004. Some approaches to statistical and finite-state speech-to-speech translation. Computer Speech & Language, 18(… find
  7. J. Cheppalier and M. Rajman. 1998. A generalized CYK algorithm for parsing stochastic CFG. In Proceedings of the Workshop on Tabulation in Parsing and Deduction (TAPD98), pages 133–137, Paris, France. find
  8. J. Cheppalier, M. Rajman, R. Aragues, and A. Rozenknop. 1999. Lattice parsing for speech recognition. In Sixth Conference sur le Traitement Automatique du Langage Naturel (TANL’99), pages 95–104. find
  9. D. Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 263–270. find our card
  10. D. Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228. find
  11. T.H. Cormen, C. E. Leiserson, and R. L. Rivest, 1989. Introduction to Algorithms, pages 558–565. The MIT Press and McGraw-Hill Book Company. find
  12. M. Costa-jussà and J.A.R. Fonollosa. 2007. Analysis of statistical and morphological classes to generate weighted reordering hypotheses on a statistical machine translation system. In Proc. of the Second Workshop on SMT, pages 171–176, Prague. find
  13. C. Dyer. 2007. Noisier channel translation: translation from morphologically complex languages. In Proceedings of the Second Workshop on Statistical Machine Translation, Prague, June. find
  14. R. Florian, H. Hassan, A. Ittycheriah, H. Jing, N. Kambhatla, X. Luo, N Nicolov, and S Roukos. 2004. A statistical model for multilingual entity detection and tracking. In Proc. of HLT-NAACL 2004, pages 1–8. find
  15. J. Goodman. 1999. Semiring parsing. Computational Linguistics, 25:573–605. find
  16. D. Grune and C.J. H. Jacobs. 2008. Parsing as intersection. Parsing Techniques, pages 425–442. find
  17. N. Habash and F. Sadat. 2006. Arabic preprocessing schemes for statistical machine translation. In Proc. of NAACL, New York. find our card
  18. D. Klein and C. D. Manning. 2001. Parsing with hypergraphs. In Proceedings of IWPT 2001. find
  19. R. Kneser and H. Ney. 1995. Improved backing-off for m-gram language modeling. In Proceedings of IEEE Internation Conference on Acoustics, Speech, and Signal Processing, pages 181–184. find
  20. P. Koehn, F.J. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proceedings of NAACL 2003, pages 48–54. find
  21. P. Koehn, A. Axelrod, A. Birch Mayne, C. Callison-Burch, M. Osborne, and D. Talbot. 2005. Edinburgh system description for the 2005 IWSLT speech translation evaluation. In Proc. of IWSLT 2005, Pittsburgh. find our card
  22. P. Koehn, H. Hoang, A. Birch Mayne, C. Callison-Burch, M. Federico, N. Bertoldi, B. Cowan, W. Shen, C. Moran, R. Zens, C. Dyer, O. Bojar, A. Constantin, and E. Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Annual Meeting of the Association for Computation Linguisti… find
  23. P. Koehn. 2004. Statistical significance tests for machine translation evluation. In Proc. of the 2004 Conf. on EMNLP, pages 388–395. find
  24. A. Lopez. to appear 2008. Statistical machine translation. ACM Computing Surveys. find
  25. L. Mathias and W. Byrne. 2006. Statistical phrase-based speech translation. In IEEE Conf. on Acoustics, Speech and Signal Processing. find
  26. L. Mathias. 2007. Statistical Machine Translation and Automatic Speech Recognition under Uncertainty. Ph.D. thesis, The Johns Hopkins University. find
  27. E. Matusov, S. Kanthak, and H. Ney. 2005. On the integration of speech recognition and statistical machine translation. In Proceedings of Interspeech 2005. find
  28. H. Ney. 1991. Dynamic programming parsing for context-free grammars in continuous speech recognition. IEEE Transactions on Signal Processing, 39(2). find
  29. H. Ney. 1999. Speech translation: Coupling of recognition and translation. In Proc. of ICASSP, pages 517– 520, Phoenix. find
  30. F. Och and H. Ney. 2002. Discriminitive training and maximum entropy models for statistical machine translation. In Proceedings of the 40th Annual Meeting of the ACL, pages 295–302. find
  31. S. Saleem, S.-C. Jou, S. Vogel, and T. Schulz. 2005. Using word lattice information for a tighter coupling in speech translation systems. In Proc. of ICSLP, Jeju Island, Korea. find
  32. H. Tseng, P. Chang, G. Andrew, D. Jurafsky, and C. Manning. 2005. A conditional random field word segmenter. In Fourth SIGHAN Workshop on Chinese Language Processing. find
  33. J. Xu, E. Matusov, R. Zens, and H. Ney. 2005. Integrated Chinese word segmentation in statistical machine translation. In Proc. of IWSLT 2005, Pittsburgh. find
  34. M. Yang and K. Kirchhoff. 2006. Phrase-based backoff models for machine translation of highly inflected languages. In Proceedings of the EACL 2006, pages 41–48. find
  35. R. Zhang, G. Kikui, H. Yamamoto, and W. Lo. 2005. A decoding algorithm for word lattice translation in speech translation. In Proceedings of the 2005 International Workshop on Spoken Language Translation. find
  36. T. Zhao, L. Yajuan, Y. Muyun, and Y. Hao. 2001. Increasing accuracy of chinese segmentation with strategy of multi-step processing. In J Chinese Information Processing (Chinese Version), volume 1, pages 13–18. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/dyer-2008-generalizing-word-lattice-translation/