Context as Filtering
Keywords: Language Modeling, Particle Filters, Change Point Analysis,LDA, Dirichlet Mixtures
Abstract: For a prediction problem for high-dimensional
discrete sequences, we propose a solution using onlinechange point analysis by Particle Filters combined withprobabilistic text models LDA and DM.

Daichi Mochihashi

Yuji Matsumoto

ATR, Spoken Language Communication
Research Laboratories, Japandaichi.mochihashi@atr.jp

Computational Linguistics
Laboratory, NAIST, Japanmatsu@is.naist.jp

Multinomial Particle Filter

Dirichlet
Dirichlet Mixtures:Mixtures: Mixture
Mixture ofof Polya
Polya distributions
distributions Simultaneous Bernoulli trials Æ Multinomial Particle Filter
6474
8 Update prior Weights (UpdatedPseudo “documents”

adaptively)

Particle #1

Language Modeling

Particle #2

Prediction from history on High-dimensional discrete data
w1 w2 w3 LL wt Æ wt +1 (Speech Recognition,Machine Translation)
LL Æ(Hyperlink Navigation)
URL t

URL1 URL 2LL

ÆSong tSong 1Song 2

URL t +1

(Collaborative Filtering):Song t +1
This problem is ubiquitous.

Problem: How long context should we use?
– Hidden state of multinomial distributions may differ– Beyond “Bag of Words” assumption
Aim of this research: Estimate next word from a long history
by introducing a state space model in Multinomial space.
Mean Shift Modely3Dirichlet(α )θ'××θθ t ~ Dir(α ) with probability ρwith probability (1 − ρ ) = θ t −1
 yt ~ Mult(θ t , l ) l=1 for simplicity• Multinomials occasionallychange• If change points are known,
use data from last change pointÆ Change point problem

y2y164474 48 64748
y1 y2 ‥‥ yc −1 yc yc +1 ‥ yt

 Online estimate of ρ : Expectation of Beta posterior
α + (# of change points thus far) α , β : hyperparametersρt =α + β + t −1
 Problem: Extremely high dimensionality of language(Semantic correlations between words)
LDA, Dirichlet Mixtures (DM) Æ MSM-LDA, MSM-DM

MSM-LDA
Topic
Subsimplex
Topic
distributiont2

MSM in Topic space– Some loss of information– Extend to other mixture models
M– p (v | h) = ∑i =1 p (v | θ i ) θ i q (θ|h )Prediction

yt +1

MSM-DM

Change Point Probabilities
By Bayes’ Theorem,p(change|observed) ∝ p(observed|change)p(change)p(observed|change=1)p(change=1)=p(observed|change=0)p(change=0)
Prior prediction p ( yt | α ) × ρ=Posterior prediction p ( yt | α, yc K yt −1 ) × (1 − ρ ) ρ × α y / ∑ α y{{=y(1 − ρ ) × (α yt + n( y t )) / ∑ y (α y + n( y )) n( y ) : # of y in yc K yt −1Topics

w N• w: Word• z : Latent variable foreach document• p : Unigram distribution(integrated out)
• α1 L α M : Dirichlet
hyperparameters for pDMp ( D | λ , α1 Lα M ) = ∏∑ λmi =1 m =1

Γ(∑v α mv )∏Γ(∑v α mv + niv ) v

Γ(α mv + niv )Γ(α mv )niv : occurrences of word v in
As opposed to LDA:
document i
9 Unitopic
9 Can model whole word simplex
9 Lower document perplexity than LDA- “Cache” property of Polya distributions (Minka 2000)
9 Number of parameters equal to LDA ( λ , α1 K α M )9 Dirichlet Process Extension is now under developmentExperiments• British National Corpus (wide coverage of topics)• 11,032,233 words, Lexicon = 52,846 words• Evaluation texts: 100 documents x 100 sentences– Raw: Extract contiguous 100 sentences– Slow~VeryFast: Randomly skip to sample 100 sentences(Slow: a little skip, Fast: large, VeryFast: very large)
Experimental Results
 Example of actual text
 Perplexity= 1/Average Predictive Probability Change pointprobability

1100
1050

To cover whole word simplex,
use a mixture of Dirichlets (DM)MSM-DM

1000

DM950

MSM-LDA900

LDA850Unigramdistribution××( q(θ | h) : VB-EM on h)Change point (Unknown)wNpz

High-dimensional word simplex
to topic subsimplex (LDA)wNt K ××t1

WordSimplex

αDt −1t

w2
w1
Word Simplex
64474
4864748
w1 w2 ‥‥ wi wi +1wi + 2 ‥‥Change point (Unknown)

t

wt +1

Particle #3:
Particle #N(Sjolander et al. 1996; Yamamoto et al. 2005)

800

×MSM directly on word simplex– No loss of information
α + n (v )M– p(v | h) = ∑m=1 p(m |h) mv∑ α + n( v )vmv

(n(v): # of v in h)

w6w62 7
1 47 4868474
8
w1 w2wi wi +1 ‥ w j w j +1 ‥Change points (Unknown)

RawSlow

Fast

VeryFastTimeParticle

Summary and Future Directions
9 Introduced a MSM of natural language with LDA/DM– Online inference with a Particle Filter
9 Multiple observations, Gibbs for a whole document (OK)
9 How to estimate segmentation and LDA/DM parameterssimultaneously (without using a slow Gibbs)?