The Infinite Markov Model

Daichi Mochihashi
NTT Communication Science Laboratories, Japandaichi@cslab.kecl.ntt.co.jp

NIPS 2007

The Infinite Markov Model (NIPS 2007) – p.1/20

Overviewislanguageofstates
iswillhe sheoforderlanguagewillstatesFixed n-th order Markov model• Fixed-order Markov dependency···

unitedinfinite⇓
Infinitely variable Markov orders

the• Simple prior for stochastic trees

Infinitely Variable-order(other than Coalescents)
Markov model◦ How to draw an inference based on only the output
sequences?
The Infinite Markov Model (NIPS 2007) – p.2/20

Markov Models

1st orderp(”mama I want to sing”)= p(mama) × p(I|mama)× p(want|mama I)× p(to|I want)× p(sing|want to)

2nd ordern-gram (3-gram)• “n-gram” (n-1’th order Markov) model is prevalent inspeech recognition and natural language processing• Music processing, Bioinformatics, compression, · · ·• Notice: HMM is a first order Markov model over hidden states◦ Emission is a unigram on the hidden state

The Infinite Markov Model (NIPS 2007) – p.3/20

Estimating a Markov Model
Predictive
Distributions"will""of""and"butter"she will" "he will" "states of" "bread and"• Each Markov state is a node in a Suffix Tree(Ron+ (1994), Pereira+ (1995), Buhlmann (1999))◦ Depth = Markov order◦ Each node has a predictive distribution over the next word
• Problem: # of states will explode as the order n gets larger◦ Restrict to a small Markov order (n = 3 ∼ 5 in speech and NLP)
◦ Distributions get sparser and sparser ⇒ using hierarchical

Bayes?
The Infinite Markov Model (NIPS 2007) – p.4/20

Hierarchical (Poisson-) Dirichlet Process• Teh (2006), Goldwater+ (2006) mapped a hierarchical Dirichlet

process to Markov Models
"will"

Text"of""and"······
a bread and butter
is usually a · · ·america butter"she will" "he will" "states of" " bread and "◦ n’th order predictive distribution is a Dirichlet process draw

from the (n−1)’th distribution◦ Chinese restaurant process representation:a customer = a count (in the training data)◦ Hierarchical Pitman-Yor Language Model (HPYLM)

The Infinite Markov Model (NIPS 2007) – p.5/20

Hierarchical (Poisson-) Dirichlet Process• Teh (2006), Goldwater+ (2006) mapped a hierarchical Dirichlet

process to Markov Models
"will"

Text"of""and"······
a bread and butter
is usually a · · ·america butter"she will" "he will" "states of" " bread and "◦ n’th order predictive distribution is a Dirichlet process draw

from the (n−1)’th distribution◦ Chinese restaurant process representation:a customer = a count (in the training data)◦ Hierarchical Pitman-Yor Language Model (HPYLM)

The Infinite Markov Model (NIPS 2007) – p.5/20

Hierarchical (Poisson-) Dirichlet Process• Teh (2006), Goldwater+ (2006) mapped a hierarchical Dirichlet

process to Markov Models
"will"

Text"of""and"······
a bread and butter
is usually a · · ·america butter"she will" "he will" "states of" " bread and "◦ n’th order predictive distribution is a Dirichlet process draw

from the (n−1)’th distribution◦ Chinese restaurant process representation:a customer = a count (in the training data)◦ Hierarchical Pitman-Yor Language Model (HPYLM)

The Infinite Markov Model (NIPS 2007) – p.5/20

Hierarchical (Poisson-) Dirichlet Process• Teh (2006), Goldwater+ (2006) mapped a hierarchical Dirichlet

process to Markov Models
"will""of"Proxy (imaginary) customer(Not relevant)Text"and"······
a bread and butter
is usually a · · ·america butter"she will" "he will" "states of" " bread and "◦ n’th order predictive distribution is a Dirichlet process draw

from the (n−1)’th distribution◦ Chinese restaurant process representation:a customer = a count (in the training data)◦ Hierarchical Pitman-Yor Language Model (HPYLM)

The Infinite Markov Model (NIPS 2007) – p.5/20

Problem with HPYLM
"will"Text"of""and"······
a bread and butter
is usually a · · ·america butter"she will" "he will" "states of" " bread and "• All the real customers reside in depth (n−1) (say, 2)

in the suffix tree
◦ Corresponds to a fixed Markov order◦ “less than”; “the united states of america”◦ Character model for “supercalifragilisticexpialidocious”!
• How can we deploy customers at suitably different depths?
The Infinite Markov Model (NIPS 2007) – p.6/20

Infinite-depth Hierarchical CRP
1 − qi1 − qj1 − qkijk• Add a customer by stochastically decending a suffix tree

from its root
• Each node i has a probability to stop at that node
(1−qi equals the “penetration” probability)qi ∼ Be(α, β) i.i.d.

(1)• Therefore, a customer will stop at depth n by the probabilityp(n|h) = qnn−1(1 − qi ) .

(2)

i=0
The Infinite Markov Model (NIPS 2007) – p.7/20

Variable-order Pitman-Yor language model(VPYLM)• For the training data w = w1 w2 · · · wT , latent Markov ordersn = n1 n2 · · · nT exist:

p(w) =

np(w, n, s)(3)s◦ s = s1 s2 · · · sT : seatings of proxy customers in parent nodes• Gibbs sample n for inference:p(nt |w, n−t , s−t )∝ p(wt |nt , w, n−t , s−t ) · p(nt |w−t , n−t , s−t ) 

nt -gram prediction prob to reach depth nt(4)◦ Trade-off between two terms (penalty for deep nt )◦ How to compute the second term p(nt |w−t , n−t , s−t )?

The Infinite Markov Model (NIPS 2007) – p.8/20

Inference of VPYLM (2)w(a, b) = (100, 900)
900+β1000+α+β· · · wt−2 wt−1 wt wt+1 · · ·n···

wt−1

←→
2

324···

70+β80+α+β20+β50+α+β• We can estimate qi of node ithrough the depths of theother customers

β5+α+β(a, b) = (10, 70)
wt−2(a, b) = (30, 20)

wt−3(a, b) = (5, 0)• Let ai = # of times the node i was· · ·stopped at,bi = # of times the node i was passed by:p(nt = n|w−t , n−t , s−t ) = qn
=n−1
(1 − qi )

(5)

i=0
an +α

n−1


an +bn +α+β

i=0bi +β.
ai +bi +α+β(6)

The Infinite Markov Model (NIPS 2007) – p.9/20

whilekey
european
consuming
nationsappearunfazedabout
theprospectsofaproducer
cartelthatwillattempt
tofix
prices|thepact
islikelytomeetstrongopposition
from
u.s.
delegates
thisweek
EOS

n0 1 2 3 4 5 6 7 8 9Estimated Markov Orders• Hinton diagram of p(nt |w) used in Gibbs sampling for thetraining data
• Estimated Markov orders from which each word has been

generated.
• NAB Wall Street Journal corpus of 10,007,108 words

The Infinite Markov Model (NIPS 2007) – p.10/20

Prediction• We don’t know the Markov order n beforehand ⇒ sum it outp(w|h) =∞

p(w, n|h) =n=0∞
p(w|n, h) p(n|h).

(7)

n=0

• We can rewrite the above expression recursively:p(w|h) = p(0|h)·p(w|h, 0) + p(1|h)·p(w|h, 1) + p(2|h)·p(w|h, 2) + · · ·= q0 ·p(w|h, 0)+(1−q0 )q1 ·p(w|h, 1)+(1−q0 )(1−q1 )q2 ·p(w|h, 2) · · ·= q0 ·p(w|h, 0)+(1−q0 ) q1 ·p(w|h, 1)+(1−q1 )q2 ·p(w|h, 2)+· · ·(8)• Therefore,p(w|h, n+ ) ≡ qn · p(w|h, n) + (1 − qn ) · p(w|h, (n+1)+ ) ,p(w|h) = p(w|h, 0+ ) .

(9)
(10)

The Infinite Markov Model (NIPS 2007) – p.11/20

Prediction (2)p(w|h, n+ ) ≡ qn · p(w|h, n)+(1−qn ) · p(w|h, (n+1)+ )  

Prediction at Depth n Prediction at Depths > np(w|h) = p(w|h, 0+ ) ,qn ∼ Be(α, β) .
• Stick-breaking process on an infinite tree, wherebreaking proportions will differ from branch to branch.
• Bayesian sophistication of CTW (context tree weighting)algorithm (Willems+ 1995) in information theory(⇒ Poster)

The Infinite Markov Model (NIPS 2007) – p.12/20

Perplexity and Number of Nodes in the Treen3578∞

HPYLM
113.60101.08
N/A
N/A—VPYLM Nodes(H) Nodes(V)113.74
1,417K
1,344K
101.69 12,699K
7,466K
100.68 27,193K 10,182K
100.58 34,459K 10,434K
100.36—
10,629K• Perplexity = 1/average predictive probabilities (lower is better)• VPYLM causes no memory overflow even for large n◦ Italic : expected number of nodes• Identical performance as HPYLM, but with much lessnumber of nodes◦ ∞-gram performed the best ( = 1e−8)

The Infinite Markov Model (NIPS 2007) – p.13/20

“Stochastic phrases” from VPYLM (1/2)• p(w, n|h) = p(w|h, n)p(n|h)· · · Probability to generate w using the last n words of has the context◦ For example, generate “Gaussians” after “mixture of”↓“mixture of Gaussians”: a phrase• p(w, n|h) = cohesion strength of the stochastic phrase◦ Will not necessarily decay with length(like an empirical probability)◦ Enumerated by traversing the suffix tree in depth-first order

The Infinite Markov Model (NIPS 2007) – p.14/20

“Stochastic phrases” from VPYLM (2/2)
p0.9784
0.9726
0.9556
0.95120.93940.8896
0.88310.86960.7566
0.7134
0.6617:

Stochastic phrase in the suffix tree
primary new issues
ˆ at the same timeamerican telephone &is a unit of
to # % from # %in a number ofin new york stock exchange composite tradinga merrill lynch & co.
mechanism of the european monetary
increase as a result oftiffany & co.
:• “ˆ” = beginning-of-sentence, “#” = numbers
The Infinite Markov Model (NIPS 2007) – p.15/20

Random Walk generation from the language model
it was a singular man , fierce and quick-tempered , veryfoul-mouthed when he was angry , and of her muff andbegan to sob in a high treble key .
“ it seems to have made you , ” said he . ’what have i to his
invariable success that the very possibility of something
happening on the very morning of the wedding . ”...
• Random walk generation from the 5-gram VPYLM

trained on “The Adventures of Sherlock Holmes.”◦ We begin with an infinite number of“beginning-of-sentence” special symbols as the context.
• If we use vanilla 5-grams, overfitting will lead toa mere reproduction of the training data.

The Infinite Markov Model (NIPS 2007) – p.16/20

Infinite Character Markov Model‘how queershaped little children drawling-desks, which would
get through that dormouse!’ said alice; ‘let us all for anything
the secondly, but it to have and another question, but i shalledout, ‘you are old,’ said the you’re trying to far out to sea.
(a) Random walk generation from a character model.

Charactersa i d a l i ce ;‘ l e t us a l l

f o r an y t h i ng···

Markov order 5654 7 10 65437 1 4824 4 65 5 445 5 645 6 77753345 9 · · ·(b) Markov orders used to generate each character above.

• Character-based Markov model trained on “Alice in Wonderland”.
◦ Lowercased alphabets + space◦ OCR, compression, Morphology, . . .

The Infinite Markov Model (NIPS 2007) – p.17/20

Final Remarks• Hyperparameter sensitivity and empirical Bayes optimization⇒ Paper• LDA extension ⇒ Paper (but partially succeeded)• Comparison with Entropy Pruning (Stolcke 1998) ⇒ Poster• Poster: W24 (near the escalator).

The Infinite Markov Model (NIPS 2007) – p.18/20

Summary2.52←

1.5

1

0.5

000.2

0.4

0.6

0.8

1

• We introduced the Infinite Markov model where the orders areunspecified and unbounded but can be learned from data.
• We defined a simple prior for stochastic infinite trees.
• We expect to use it for latent trees:◦ Variable resolution hierarchical clustering (cf. hLDA)◦ Deep semantic categories just when needed.
• Also for variable order HMM (pruning approach: Wang+, ICDM

2006)
The Infinite Markov Model (NIPS 2007) – p.19/20

Future Work• Fast variational inference◦ Obviates Gibbs for inference and prediction◦ CVB for HDP: Teh et al. (this NIPS)• More elaborate tree prior than a single Beta
• Relationship to Tailfree processes (Fabius 1964; Ferguson

1974)

The Infinite Markov Model (NIPS 2007) – p.20/20