The Infinite Markov Model

Keywords: Nonparametric Bayes, Tree prior,
Pitman-Yor process, Prediction Suffix Trees

Daichi Mochihashi*,† Eiichiro Sumita†* NTT Communication Science Laboratories, JapanATR Spoken Language Communication Research Laboratories, Japan†

Nonparametric Bayes Perspectivez Stochastic infinite trees

Overview

Variable-order HDP• Nonparametric Bayesian variable-orderMarkov Model that estimates latent Markovorders from which each symbol originated.
• Tree prior over stochastic suffix trees ofdiminishing branches.

z Add a customer by stochastically descending the²suffix tree:h1−q(²)

wt−1

1−q(w t−1 )1− q(w t−2 w t−1 )p(n|h) = qn

Previous works: pruning a huge model
Very interesting, but• Often cannot build such huge models in advance(ex. Google >5 grams?)• Difficult to integrate as other model’s component

HDP and Markov Models²‥ bread and butter ‥“butter”
and“america”

she will states of(1 − qi )Posterior qi :E[q i ] =α+#(stop at i)
α+β +#(access of i)

Data• “Deep semantic category” just when needed• Data can reside at the intermediate nodes

so we can Gibbs sample for inference:p(nt |w, z−t , n−t )∝ p(wt |w−t , z−t , n−t , nt )p(nt |w−t , z−t , n−t ).

Natural Language Processingz Bayesian ∞-gram Language Model∞∞XXp(w|h) =p(w, n|h) =p(w|h, n) p(n|h)| {z }
n=1
n=1z Empirical consideration

150z Variable order HMM (Wang+ 2006)• Ordinary HMMs are 1-Markov• Estimate complex dynamics froma pure generative model

Information Theory / Compression
z Context Tree Weighting method (Willems+ 1995)

L High-performancecompression studied in 1990s(Qn-gramNaïve K-N 9-grams,10-grams,… might be possible(esp. with Bloom Filters), but:
• Large n-grams are extremely noisy and bulky• Conveys no linguistic insights• Cannot generate – simply reproduces training data.
z Comparison with Entropy Pruning (Stolcke 1998)
200

How to deploy customers at suitable depths?

hLDA (Blei+ 2003):
Multinomial for depths(maximum known)Dataz This process is still exchangeable over customers,“butter”

z Problem: All real customers reside in depth (n-1)• Top-down (<-> Coalescent tree)• Coalescent points known, but diminishing branches
z Bayesian hierarchical clustering
Dataqi ∼ Be(α, β).

bread andz Markov models can be mapped to hierarchical(Poisson-) Dirichlet process (Teh,Goldwater+ 2006)#(w|h)−d · thw d · th +θp(w|h) =+· p(w|h0 )#(h)+θ
#(h)+θ

wt−2

n−1Y
i=0Perplexity

he will···ph (xT1 ) =pe(xT1 ) =γpe(xT1 ) + (1−γ)
pe(xT1 )Z 1Tw∈L pwh (x1 )Usually 1/2!

1 1p(xT1 |p)Be(p| , )dp
2 20(h: non-leaf)(h: leaf)(KT-Estimator)z γ Æ Bayesian posterior, KTÆPitman-Yor

Our method!

• Infinite Markov Model = “Bayesian CTW algorithm”.
• Difference: not all histories are memoized (like CTW)
- Memoizing only “meaningful” subsequences

PPL% Params

100500• NAB WSJ 1M-words subset• Entropy pruning with thresholds• VPYLM with different priors

SRI
1 . LM00
E
1 . - 1000
E
1 . - 0800
E0HP 5YLM
(4,1)
(7,1)
(10,1)

will ofwt−3 wt−2wt−1 wt

wt−3

Motivation and Background‥‥ and she sings a song ‥‥z Natural language and speech processing
Æ n-gram (n-1 order Markov) model is prevalent• Fixed (n-1) words dependency for next word
• “less than”? “supercalifragilisticexpialidocious”?
• Music processing, Bioinformatics, compression,..

···• Removes independent pruning assumption
through a Gibbs• Not depend on raw context frequency p(h)Future Work
Fast variational inference (extending VB-HDP)
More sensitive and hierarchical prior than a single Betaz de Finetti random measure and relationship toTailfree processes (Fabius 1964;Ferguson 1974)
zz