Elamur Research⌕
☰
home / papers / 2006 / Minimum Risk Annealing for Training Log-Linear Models

Minimum Risk Annealing for Training Log-Linear Models

Paper · 2006 · David A. Smith and Jason Eisner

Summary

The paper tackles the mismatch between how NLP systems are evaluated (task metrics such as BLEU or labeled attachment accuracy) and how they are usually trained (maximum likelihood). Directly minimizing 1-best error is difficult because the error surface is piecewise flat and full of local optima. The authors instead minimize risk, the expected loss under the model's distribution over a fixed list of candidate analyses. They wrap this in deterministic annealing: a scale or temperature parameter starts the model at a smooth, high-entropy distribution and gradually sharpens it toward the single best hypothesis. They also show how to approximate the expectation of corpus-level nonlinear metrics such as BLEU or precision using a Taylor expansion. The approach is used to tune weights of log-linear combinations of submodels for machine translation (German-English, Finnish-English) and labeled dependency parsing (Bulgarian, Dutch, Slovenian). On MT, annealed minimum risk significantly beats Och-style minimum error training in BLEU. On parsing, the gains are mixed. Across experiments, it was never significantly worse than either baseline.

Key points

  • The models are log-linear rescorers over K-best lists, where each feature can be the log probability of an entire submodel ("products of experts"). A scale parameter γ moves the model from uniform (γ=0), through the ordinary model (γ=1), to Viterbi-like behavior (γ→∞).

  • Annealing optimizes expected loss minus T times entropy and cools T over time. Once T is low, γ is raised quickly ("quenching").

  • Corpus-level BLEU is handled by minimizing the expectation of −log of the metric. This decomposes into expectations of log counts, which are approximated with a second-order Taylor expansion around their means.

  • Parsing setup:

    • Data and parsers: CoNLL-X data, with parsers built from 10 globally normalized log-linear experts.
    • Tuning: weights were tuned on 200-best lists for a 200-sentence dev set.
    • Testing: each language was evaluated on 200 test sentences.

  • Labeled accuracy, reported as max-likelihood / min-error / annealed min-risk:

    LanguageMax-likelihoodMin-errorAnnealed min-risk
    Slovenian27.7822.5231.16
    Bulgarian47.2354.7254.66
    Dutch36.7836.7836.71

    Only the Slovenian gain for annealing is significant (paired permutation test, 1000 replications).

Interesting ideas

  • I1. Optimize the expected metric under the model's own distribution. This gives a smooth, differentiable surrogate for any evaluation measure, including non-decomposable ones. It applies to any reranking or system-combination task where the true metric is piecewise constant.
  • I2. Anneal from high entropy to a peaked distribution. This continuation strategy helps the optimizer step past local optima that only appear once the objective becomes sharp. It is a cheap alternative to many random restarts in other non-convex tuning problems.
  • I3. Control entropy rather than the scale parameter alone. In an unregularized log-linear model, the optimizer can cancel γ by shrinking the weights, so annealing must target entropy directly. This pitfall is worth remembering whenever temperature is used as a training knob.
  • I4. Taylor-approximate expectations of ratio metrics. Turning a corpus-level score into expectations of log counts makes metrics like BLEU, precision, or F-scores trainable as risks.
  • I5. Explain gains through generalization, not better minimization. The authors note the method sometimes lost on training data yet won on held-out data. They attribute this to several low-loss hypotheses per sentence jointly steering the weights, which is a useful diagnostic for judging a new training objective.

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

🎓Johns Hopkins UniversityBaltimore · United States187 works · 92,194 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as David A. Smith and Jason Eisner. 2006. Minimum Risk Annealing for Training Log-Linear Models. Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions.

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

@inproceedings{smith2006minimum,
  title = {{Minimum Risk Annealing for Training Log-Linear Models}},
  author = {David A. Smith and Jason Eisner},
  booktitle = {Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions},
  year = {2006},
  doi = {10.3115/1273073.1273174},
  url = {https://doi.org/10.3115/1273073.1273174}
}

References

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

  1. L. R. Bahl, P. F. Brown, P. V. de Souza, and R. L. Mercer. 1988. A new algorithm for the estimation of hidden Markov model parameters. In ICASSP, pages 493–496. find
  2. E. Charniak and M. Johnson. 2005. Coarse-to-fine n-best parsing and maxent discriminative reranking. In ACL, pages 173–180.
  3. S. F. Chen and R. Rosenfeld. 1999. A gaussian prior for smoothing maximum entropy models. Technical report, CS Dept., Carnegie Mellon University. find
  4. K. Crammer, R. McDonald, and F. Pereira. 2004. New large margin algorithms for structured prediction. In Learning with Structured Outputs (NIPS). find
  5. M. Dreyer, D. A. Smith, and N. A. Smith. 2006. Vine parsing and minimum risk reranking for speed and precision. In CoNLL. find
  6. G. Elidan and N. Friedman. 2005. Learning hidden variable networks: The information bottleneck approach. JMLR, 6:81–127. find
  7. V. Goel and W. J. Byrne. 2000. Minimum Bayes-Risk automatic speech recognition. Computer Speech and Language, 14(2):115–135. find
  8. J. T. Goodman. 1996. Parsing algorithms and metrics. In ACL, pages 177–183. find
  9. G. Hinton. 1999. Products of experts. In Proc. of ICANN, volume 1, pages 1–6. find
  10. K.-U. Hoffgen, H.-U. Simon, and K. S. Van Horn. 1995. Robust trainability of single neurons. J. of Computer and System Sciences, 50(1):114–125. find
  11. D. S. Johnson and F. P. Preparata. 1978. The densest hemisphere problem. Theoretical Comp. Sci., 6(93–107). find
  12. S. Katagiri, B.-H. Juang, and C.-H. Lee. 1998. Pattern recognition using a family of design algorithms based upon the generalized probabilistic descent method. Proc. IEEE, 86(11):2345–2373, November. find
  13. P. Koehn, F. J. Och, and D. Marcu. 2003. Statistical phrase-based translation. In HLT-NAACL, pages 48–54. find
  14. S. Kumar and W. Byrne. 2004. Minimum bayes-risk decoding for statistical machine translation. In HLT-NAACL.
  15. J. Lafferty, A. McCallum, and F. C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML. find
  16. F. J. Och. 2003. Minimum error rate training in statistical machine translation. In ACL, pages 160–167. find
  17. K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. 2002. B LEU : A method for automatic evaluation of machine translation. In ACL, pages 311–318. find
  18. K. A. Papineni. 1999. Discriminative training via linear programming. In ICASSP. find
  19. A. Rao and K. Rose. 2001. Deterministically annealed design of Hidden Markov Model speech recognizers. IEEE Trans. on Speech and Audio Processing, 9(2):111–126. find
  20. K. Rose. 1998. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proc. IEEE, 86(11):2210–2239. find
  21. N. A. Smith and J. Eisner. 2004. Annealing techniques for unsupervised statistical language learning. In ACL, pages 486–493. find
  22. A. Smith, T. Cohn, and M. Osborne. 2005. Logarithmic opinion pools for conditional random fields. In ACL, pages 18–25. find
  23. B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In EMNLP, pages 1–8. find
  24. N. Ueda and R. Nakano. 1998. Deterministic annealing EM algorithm. Neural Networks, 11(2):271–282. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/smith-2006-minimum-risk-annealing-training-log/