Elamur Research⌕
☰
home / papers / 2006 / A Hierarchical Bayesian Language Model Based On Pitman-Yor Processes

A Hierarchical Bayesian Language Model Based On Pitman-Yor Processes

Summary

The paper addresses a long-standing gap in n-gram language modelling. The strongest smoothing techniques, such as Kneser-Ney variants, are justified mostly by empirical results. Earlier Bayesian models, which have explicit prior assumptions, performed poorly. Teh proposes the hierarchical Pitman-Yor language model (HPYLM), which extends MacKay and Peto's earlier Dirichlet-based hierarchical model of language. Each context's next-word distribution gets a Pitman-Yor process prior whose mean is the distribution for the context shortened by its earliest word. This yields a suffix-tree hierarchy ending at a uniform base distribution. Unlike the Dirichlet distribution, the Pitman-Yor process generates power-law word statistics, which better match natural language. Inference uses a Gibbs sampler over seating arrangements in a hierarchical Chinese restaurant process. The paper shows that interpolated Kneser-Ney is exactly a particular approximate inference scheme in this model. In perplexity experiments, HPYLM beats interpolated Kneser-Ney and roughly matches modified Kneser-Ney. A cross-validated variant gives the best overall results. The work matters because it shows a principled Bayesian model can reach state-of-the-art smoothing performance.

Key points

  • Prior structure: Each context u has G_u ~ PY(d_|u|, θ_|u|, G_π(u)), where discount and strength depend only on context length.

    • The model has 2n parameters in total.
    • Discounts get uniform priors and strengths get Gamma(1, 1) priors.

  • Link to Kneser-Ney: Interpolated Kneser-Ney is recovered under three conditions:

    • each word type in a context uses at most one "table" (t_uw = min(1, c_uw));
    • all strength parameters are set to zero;
    • in this regime the model reduces to absolute discounting.
    • Modified Kneser-Ney cannot be derived this way, since Pitman-Yor discounts must lie between 0 and 1.

  • Perplexity results: Training sets ranged from 2 to 14 million words, with n = 2, 3 and 4. At 14M words with trigrams:

    ModelPerplexity
    IKN116.7
    MKN113.6
    HPYLM114.3
    HPYCV113.2
    HDLM140.5

    With 4-grams, HPYCV reached 101.9 versus 102.4 for MKN.

  • Dirichlet baseline: The hierarchical Dirichlet model (HDLM) was far worse at every setting. This confirms the value of the power-law prior.

  • Where the gains come from: Differences between methods come almost entirely from rare test words.

Interesting ideas

  • I1. Reinterpret heuristics as inference: Treating a well-tuned heuristic like Kneser-Ney as approximate inference in a generative model explains why it works. It also suggests better variants, and the same move could clarify other ad hoc smoothing or discounting schemes.
  • I2. Fit the prior to the data's statistics: The prior was chosen to reproduce power-law vocabulary growth. Here, θ sets the overall number of unique words and d sets their asymptotic growth. Checking whether a prior reproduces known statistics of the data is a cheap sanity test before building a model.
  • I3. Back off by dropping the earliest word: Encoding back-off as a suffix-tree hierarchy shares statistical strength between related contexts in a principled way. The design could extend to other sparse hierarchical count data, such as morphologically rich vocabularies.
  • I4. Break down error by frequency: Splitting test cross-entropy by how often each word occurs in the test set reveals where models really differ. In this paper, that was mostly rare words. The analysis is useful for evaluating any model on sparse data.
  • I5. Combine cheap tuning with principled inference: Hyperparameters were cross-validated with a fast approximation (IKN), then plugged into the full sampler (HPYCV). This practical compromise applies whenever exact tuning of a Bayesian model is too expensive.

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

Cited by

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

Cite

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

@inproceedings{teh2006hierarchical,
  title = {{A Hierarchical Bayesian Language Model Based On Pitman-Yor Processes}},
  author = {Teh, Yee Whye},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220299},
  url = {https://doi.org/10.3115/1220175.1220299}
}

References

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

  1. Y. Bengio, R. Ducharme, P. Vincent, and C. Jauvin. 2003. A neural probabilistic language model. Journal of Machine Learning Research, 3:1137–1155. find
  2. S.F. Chen and J.T Goodman. 1998. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Computer Science Group, Harvard University. find our card
  3. A. Gelman, J. Carlin, H. Stern, and D. Rubin. 1995. Bayesian data analysis. Chapman & Hall, London. find
  4. Z. Ghahramani. 2005. Nonparametric Bayesian methods. Tutorial presentation at the UAI Conference. find
  5. S. Goldwater, T.L. Griffiths, and M. Johnson. 2006. Interpolating between types and tokens by estimating power-law generators. In Advances in Neural Information Processing Systems, volume 18. find
  6. J.T. Goodman. 2001. A bit of progress in language modeling. Technical Report MSR-TR-2001-72, Microsoft Research. find
  7. J.T. Goodman. 2004. Exponential priors for maximum entropy models. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. find
  8. H. Ishwaran and L.F. James. 2001. Gibbs sampling methods for stick-breaking priors. Journal of the American Statistical Association, 96(453):161–173. find
  9. M.I. Jordan. 2005. Dirichlet processes, Chinese restaurant processes and all that. Tutorial presentation at the NIPS Conference. 0.03 find
  10. IKN MKN HPYLM HPYCV Cross−Entropy Differences from MKN 0.025 0.02 0.015 0.01 0.005 −0.005 −0.01 4 6 8 Count of words in test set R. Kneser and H. Ney. 1995. Improved backing-off for m-gram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processi… find
  11. D.J.C. MacKay and L.C.B. Peto. 1994. A hierarchical Dirichlet language model. Natural Language Engineering. find
  12. A. Nadas. 1984. Estimation of probabilities in the language model of the IBM speach recognition system. IEEE Transaction on Acoustics, Speech and Signal Processing, 32(4):859–861. find
  13. R.M. Neal. 1993. Probabilistic inference using Markov chain Monte Carlo methods. Technical Report CRG-TR-93-1, Department of Computer Science, University of Toronto. find
  14. J. Pitman and M. Yor. 1997. The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator. Annals of Probability, 25:855–900. find
  15. J. Pitman. 2002. Combinatorial stochastic processes. Technical Report 621, Department of Statistics, University of California at Berkeley. Lecture notes for St. Flour Summer School. find
  16. R. Rosenfeld. 2000. Two decades of statistical language modeling: Where do we go from here? Proceedings of the IEEE, 88(8). find
  17. Y.W. Teh, M.I. Jordan, M.J. Beal, and D.M. Blei. 2006. Hierarchical Dirichlet processes. To appear in Journal of the American Statistical Association. find
  18. Y. W. Teh. 2006. A Bayesian interpretation of interpolated Kneser-Ney. Technical Report TRA2/06, School of Computing, National University of Singapore. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/teh-2006-hierarchical-bayesian-language-model-based/