Elamur Research⌕
☰
home / papers / 2010 / cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models

cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models

Summary

The authors address a practical obstacle in statistical machine translation research. Existing open-source decoders such as Moses and Joshua mix translation logic, language-model integration, and pruning in one codebase. They also assume only a handful of dense features. This makes new models hard to prototype and hard to compare fairly. The paper presents cdec, an Apache-licensed C++ framework. In cdec, model-specific code only has to build a translation forest, stored as a hypergraph. Word-based, phrase-based, SCFG, and tagging models all produce this same structure. Generic components then operate on it: rescoring with FST-like models such as n-gram language models, pruning, k-best extraction, alignment against a reference, and training. Training can use MERT (here called VEST) or gradient-based optimization of conditional likelihood, which supports millions of sparse features. On a Chinese-English hierarchical phrase-based task, cdec reaches the same BLEU as Joshua and Hiero. It is faster than single-threaded Joshua and the Python Hiero, and it needs the least memory. The work matters because it provides one reusable infrastructure for decoding, aligning, and learning across model families.

Key points

  • Two-stage pipeline:

    • Stage 1 converts the input into a hypergraph and then rescores it. The input can be a sentence, a lattice, or a source-side CFG forest.
    • Rescoring offers three intersection strategies: full intersection, cube pruning, and cube growing.
    • Stage 2 extracts outputs from the rescored forest: 1-best or k-best derivations, feature expectations, or an alignment forest obtained by parsing the target reference.

  • Semiring framework:

    • Most quantities are computed in time linear in the size of the hypergraph, using a semiring framework.
    • In C++, a semiring is just a type with +=, *=, a default constructor, and T(1), so built-in types like double, int, and bool qualify.
    • The library adds a log-space prob_t type and a first-order expectation semiring.

  • Training:

    • VEST runs MERT over the full hypergraph rather than over k-best lists.
    • Discriminative training maximizes conditional log likelihood. Both the objective and its gradient are a difference between computations on the alignment hypergraph and on the translation hypergraph.
    • The batch pipeline is split into map and reduce steps. Supported optimizers are LBFGS, RPROP, and SGD.

  • Experimental setup: NIST MT03 Chinese-English, with a grammar from a suffix-array rule extractor. All decoders used a span limit of 15, cube pruning with 30 candidates per node, and the SRI LM toolkit. Every system scored between 31.4 and 31.6 BLEU.

  • Speed and memory (per sentence):

    DecoderTimeMemory
    cdec0.37 s1.0 GB
    Joshua, 1 thread0.98 s1.5 GB
    Joshua, 8 threads0.35 s2.5 GB
    Hiero (Python)4.04 s1.1 GB

Interesting ideas

  • I1. Separate search-space construction from scoring. Models only emit an unscored forest, and shared code handles language-model integration and pruning. Any new pruning or inference method then benefits every model at once, and comparisons between models become controlled. This design fits any structured-prediction toolkit, for example taggers or parsers for Ukrainian.
  • I2. Treat alignment as parsing the reference with the translation forest. The decoder's own search space is reused to find how a known output could be derived. This avoids writing a separate aligner and gives a natural sanity check when a model cannot produce a reference.
  • I3. Express training as "clamped minus free". The likelihood and its gradient come from running the same inside or expectation computation on two hypergraphs: one constrained to the reference and one unconstrained. A single inference routine thus serves both decoding and learning. With sequence models, this reduces exactly to CRF training.
  • I4. Define a semiring as a type with overloaded operators. One generic algorithm then yields many quantities, such as derivation counts, expectations, entropy, or Viterbi scores, simply by swapping the value type. A log-space type removes underflow problems. The pattern is cheap to adopt in any dynamic-programming code.
  • I5. Make decoding the map step of training. Running the decoder as the map function and optimization as the reduce step lets expensive gradient-based training scale across a cluster. This suits any objective that decomposes over sentences.

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

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

Cite

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

@inproceedings{dyer2010cdec,
  title = {{cdec: A Decoder, Alignment, and Learning Framework for Finite-State and Context-Free Translation Models}},
  author = {Dyer, Chris and Lopez, Adam and Ganitkevitch, Juri and Weese, Jonathan and Ture, Ferhan and Blunsom, Phil and Setiawan, Hendra and Eidelman, Vladimir and Resnik, Philip},
  booktitle = {Proceedings of the ACL 2010 System Demonstrations},
  year = {2010},
  url = {https://aclanthology.org/P10-4002/}
}

References

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

  1. P. Blunsom and M. Osborne. 2008. Probalistic inference for machine translation. In Proc. of EMNLP. find
  2. P. Blunsom, T. Cohn, and M. Osborne. 2008. A discriminative latent variable model for statistical machine translation. In Proc. of ACL-HLT. find
  3. P. F. Brown, V. J. Della Pietra, S. A. Della Pietra, and R. L. Mercer. 1993. The mathematics of statistical machine translation: parameter estimation. Computational Linguistics, 19(2):263–311. find
  4. D. Chiang, K. Knight, and W. Wang. 2009. 11,001 new features for statistical machine translation. In Proc. of NAACL, pages 218–226. find
  5. D. Chiang. 2007. Hierarchical phrase-based translation. Comp. Ling., 33(2):201–228. find
  6. J. Dean and S. Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In Proc. of the 6th Symposium on Operating System Design and Implementation (OSDI 2004), pages 137–150. find
  7. C. Dyer and P. Resnik. 2010. Context-free reordering, finite-state translation. In Proc. of HLT-NAACL. find
  8. C. Dyer, S. Muresan, and P. Resnik. 2008. Generalizing word lattice translation. In Proc. of HLT-ACL. find our card
  9. C. Dyer. 2010. Two monolingual parses are better than one (synchronous parse). In Proc. of HLT-NAACL. find
  10. L. Huang and D. Chiang. 2005. Better k-best parsing. In In Proc. of IWPT, pages 53–64. find
  11. L. Huang and D. Chiang. 2007. Forest rescoring: Faster decoding with integrated language models. In Proc. ACL. find our card
  12. L. Huang, K. Knight, and A. Joshi. 2006. A syntax-directed translator with extended domain of locality. In Proc. of AMTA. find
  13. P. Koehn, F. J. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proc. of HLT/NAACL, pages 48–54. find
  14. P. Koehn, H. Hoang, A. B. 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 Proc. of ACL, Demonstration Session, pages 177–180, June. find
  15. S. Kumar, W. Macherey, C. Dyer, and F. Och. 2009. Efficient minimum error rate training and minimum B ayes-risk decoding for translation hypergraphs and lattices. In Proc. of ACL, pages 163–171. find
  16. Z. Li and J. Eisner. 2009. First- and second-order expectation semirings with applications to minimum-risk training on translation forests. In Proc. of EMNLP, pages 40–51. find
  17. Z. Li, C. Callison-Burch, C. Dyer, J. Ganitkevitch, S. Khudanpur, L. Schwartz, W. N. G. Thornton, J. Weese, and O. F. Zaidan. 2009. Joshua: an open source toolkit for parsing-based machine translation. In Proc. of the Fourth Workshop on Stat. Machine Translation, pages 135–139. find our card
  18. D. C. Liu, J. Nocedal, D. C. Liu, and J. Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming B, 45(3):503–528. find
  19. A. Lopez. 2007. Hierarchical phrase-based translation with suffix arrays. In Proc. of EMNLP, pages 976–985. find
  20. A. Lopez. 2008. Statistical machine translation. ACM Computing Surveys, 40(3), Aug. find
  21. A. Lopez. 2009. Translation as weighted deduction. In Proc. of EACL, pages 532–540. find
  22. M.-J. Nederhof. 2003. Weighted deductive parsing and Knuth’s algorithm. Comp. Ling., 29(1):135–143, Mar. find
  23. F. Och. 2003. Minimum error rate training in statistical machine translation. In Proc. of ACL, pages 160–167. find
  24. K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proc. of ACL, pages 311–318. find our card
  25. M. Riedmiller and H. Braun. 1993. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In Proc. of the IEEE international conference on neural networks, pages 586–591. find
  26. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of NAACL, pages 134–141. find
  27. M. Snover, B. Dorr, R. Schwartz, L. Micciulla, and J. Makhoul. 2006. A study of translation edit rate with targeted human annotation. In Proc. AMTA. find our card
  28. A. Stolcke. 2002. SRILM – an extensible language modeling toolkit. In Intl. Conf. on Spoken Language Processing. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/dyer-2010-cdec-decoder-alignment-learning-framework/