NLP Programming Tutorial 7 – Topic Models

NLP Programming Tutorial 7 Topic Models

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 7 – Topic Models

Topics in Documents●In general, documents can be grouped into topics

Cuomo to Push for Broader
Ban on Assault Weapons

2012 Was Hottest
Year in U.S. History

…
…
…
…

…
…
…
…

2

NLP Programming Tutorial 7 – Topic Models

Topics in Documents●In general, documents can be grouped into topics

Cuomo to Push for Broader
Ban on Assault Weapons

2012 Was Hottest
Year in U.S. History

…
…
…
…

…
…
…
…

New York
Politics
Weapons
Crime

Weather
ClimateStatistics
U.S.
3

NLP Programming Tutorial 7 – Topic Models

Topic Modeling●Topic modeling finds topics Y given documents X

Cuomo to Push for Broader
Ban on Assault Weapons

2012 Was Hottest
Year in U.S. History

…
…
…
…

…
…
…
…

New York
Politics
Weapons
Crime

Weather
ClimateStatistics
U.S.

XY

●TopicModeling

A type of “structured” prediction
4

NLP Programming Tutorial 7 – Topic Models

Probabilistic Generative Model●We assume some probabilistic model generated thetopics Y and documents X jointlyP(Y , X )●The topics Y with highest joint probability given X also
has the highest conditional probability

argmax P (Y∣X )=argmax P(Y , X)
YY5

NLP Programming Tutorial 7 – Topic Models

Generative Topic Model●Assume we have words X and topics Y:
X = Cuomo to Push for Broader Ban on Assault Weapons
Y = NY Func Pol Func Pol

Pol Func Crime

Crime

NY=New York, Func=Function Word, Pol=Politics, Crime=Crime●First decide topics (independently)
IP(Y )=∏i=1 P ( y i )●Then decide words given topics (independently)
IP( X∣Y )=∏ i=1 P(x i∣y i )6NLP Programming Tutorial 7 – Topic Models

Unsupervised Topic Modeling●Given only the documents X, find topic-like clusters Y

Cuomo to Push for Broader
Ban on Assault Weapons

2012 Was Hottest
Year in U.S. History

…
…
…
…

…
…
…
…

X

32241019Y●●5184937

UnsupervisedTopicModeling

A type of “structured” prediction
But unlike before, we have no labeled training data!

7

NLP Programming Tutorial 7 – Topic Models

Latent Dirichlet Allocation●

Most popular generative model for topic modeling●First generate model parameters θ: P(θ )●For every document in X:●

Generate document topic distribution Ti:●

For each word xi,j in Xi:

P(T i∣θ)P( y i , j∣T i )– Generate the word x :P( x i , j∣y i , j , θ)–Generate word topic yi,j:i,jP( X ,Y )=∫θ P (θ) ∏i P( T i∣θ) ∏ j P ( y i , j∣T i , θ) P( x i , j∣y i , j , θ)
8NLP Programming Tutorial 7 – Topic Models

Maximum Likelihood Estimation●

Assume we have words X and topics Y:
X1 = Cuomo to Push for Broader Ban on Assault Weapons
Y1 = 32●

724724 71010Can decide the topic distribution for each document:P( y∣Y i)=c ( y , Y i )/∣Y i∣●

24e.g.:P( y =24∣Y 1)=3 / 9

Can decide word distribution for each topic:P( x∣y )=c ( x , y )/c ( y)e.g.:P( x =assault∣y =10)=1/2
9

NLP Programming Tutorial 7 – Topic Models

Problem: Unobserved Variables●

Problem: We do not know the values of yi,j●Solution: Use a method for unsupervised learning
EM Algorithm● Variational Bayes● Sampling●10NLP Programming Tutorial 7 – Topic Models

Sampling Basics●Generate a sample from probability distribution:

Distribution: P(Noun)=0.5 P(Verb)=0.3 P(Preposition)=0.2
Sample: Verb Verb Prep. Noun Noun Prep. Noun Verb Verb Noun …
●Count the samples and calculate probabilities

P(Noun)= 4/10 = 0.4, P(Verb)= 4/10 = 0.4, P(Preposition) = 2/10 = 0.2

More samples = better approximation
1Probability●0.8NounVerbPrep.

0.6
0.4
0.2
0
1E+00 1E+01 1E+02 1E+03 1E+04 1E+05 1E+06
Samples11

NLP Programming Tutorial 7 – Topic Models

Actual Algorithm
SampleOne(probs[])z = Sum(probs)

Calculate sum of probs

remaining = Rand(z)Generate number from
uniform distribution over [0,z)for each i in 0 .. probs.size-1

Iterate over all probabilities

remaining -= probs[i]Subtract current prob. value

if remaining <= 0

If smaller than zero, returncurrent index as answer

return i
Bug check, beware of overflow!

12

NLP Programming Tutorial 7 – Topic Models

Gibbs Sampling●

Want to sample a 2-variable distribution P(A,B)… but cannot sample directly from P(A,B)● … but can sample from P(A|B) and P(B|A)●●●

Gibbs sampling samples variables one-by-one torecover true distribution
Each iteration:
Leave A fixed, sample B from P(B|A)
Leave B fixed, sample A from P(A|B)

13

NLP Programming Tutorial 7 – Topic Models

Example of Gibbs Sampling●●

Parent A and child B are shopping, what sex?
P(Mother|Daughter) = 5/6 = 0.833
P(Mother|Son) = 5/8 = 0.625
P(Daughter|Mother) = 2/3 = 0.667
P(Daughter|Father) = 2/5 = 0.4
Original state: Mother/Daughter
Sample P(Mother|Daughter)=0.833, chose Mother
Sample P(Daughter|Mother)=0.667, chose Sonc(Mother, Son)++Sample P(Mother|Son)=0.625, chose Mother
Sample P(Daughter|Mother)=0.667, chose Daughterc(Mother, Daughter)++
14…

NLP Programming Tutorial 7 – Topic Models

Try it Out:
Probability

1
0.8
0.6

Moth/DaughMoth/Son
Fath/DaughFath/Son

0.40.201E+00

1E+02

1E+04

1E+06

Number of Samples●

In this case, we can confirm this result by hand
15

NLP Programming Tutorial 7 – Topic Models

Sampling in Topic Models (1)●Sample one yi,j at a time:

X1 = Cuomo to Push for Broader Ban on Assault Weapons
Y1 =57 4 734 766●

Subtract of yi,j and re-calculate topics and parameters{0, 0, 1/9, 2/9, 1/9, 2/9, 3/9, 0}{0, 0, 1/8, 2/8, 1/8, 2/8, 2/8, 0}

16

NLP Programming Tutorial 7 – Topic Models

Sampling in Topic Models (2)●Sample one yi,j at a time:

X1 = Cuomo to Push for Broader Ban on Assault Weapons
Y1 =57 4 ???
34 766●

Multiply topic prob., by word given topic prob.:Calculated from whole corpus

P(yi,j | Ti)={

0,0, 0.125, 0.25, 0.125, 0.25, 0.25, 0}*=P(xi,j | yi,j, θ) ={0.01, 0.02, 0.01, 0.10, 0.08, 0.07, 0.70, 0.01}
P(xi,j yi,j| Ti, θ)={0, 0,0.00125,0.01,0.01,0.00875,0.175, 0}/Z
Normalization constant

17

NLP Programming Tutorial 7 – Topic Models

Sampling in Topic Models (3)●Sample one value from this distribution:P(xi,j, yi,j | Ti, θ)={●0, 0,0.00125,0.01,0.01,0.00875,0.175, 0}/Z

Add the word with the new topic:

X1 = Cuomo to Push for Broader Ban on Assault Weapons
Y1 =57 4 634 766●

Update the counts and the probabilities:{0, 0, 1/8, 2/8, 1/8, 2/8, 2/8, 0}{0, 0, 1/9, 2/9, 1/9, 3/9, 2/9, 0} 18

NLP Programming Tutorial 7 – Topic Models

Dirichlet Smoothing●●

Problem: Many probabilities are zero!
→ Cannot escape from local minima
Solution: Smooth the probabilities
Unsmoothed

Smoothedc ( xi , j , yi , j )P( x i , j∣x i , j )=c ( y i , j)c ( x i , j , y i , j)+ αP( x i , j∣y i , j )=c ( y i , j)+ α∗N xc( y i , j ,Y i)
P( y i , j∣Y i)=c (Y i)c( y i , j∣Y i)+ βP( y i , j∣Y i)=c( Y i)+ β∗N y●●

Nx and Ny are number of unique words and topics
Equal to using a Dirichlet prior over the probabilities(More details in my Bayes tutorial)

19

NLP Programming Tutorial 7 – Topic Models

Implementation: Initialization
make vectors xcorpus, ycorpus # to store each value of x, ymake map xcounts, ycounts# to store counts for probs
for line in filedocid = size of xcorpus# get a numerical ID for this doc
split line into words
make vector topics# create random topic ids
for word in words
topic = Rand(NUM_TOPICS) # random in [0,NUM_TOP)
append topic to topics
AddCounts(word, topic, docid, 1) # add counts
append words (vector) to xcorpus
append topics (vector) to ycorpus

20

NLP Programming Tutorial 7 – Topic Models

Implementation: Adding Counts
AddCounts(word, topic, docid, amount)
xcounts[topic] += amountxcounts[word,topic] += amountforc ( x i , j , y i , j)+ αP( x i , j∣y i , j )=c ( y i , j)+ α∗N x
forycounts[docid] += amount
ycounts[topic,docid] += amountc ( y i , j , Y i)+ βP( y i , j∣Y i)=c( Y i)+ β∗N ybug check!
if any of these values < 0, throw error

21

NLP Programming Tutorial 7 – Topic Models

Implementation: Sampling
for many iterations:ll = 0for i in 0:Size(xcorpus):
for j in 0:Size(xcorpus[i]):x = xcorpus[i][j]y = ycorpus[i][j]AddCounts(x, y, i, -1) # subtract the counts (hence -1)
make vector probs
for k in 0 .. NUM_TOPICS-1:
append P(x|k) * P(k|Y) to probs # prob of topic k
new_y = SampleOne(probs)
ll += log(probs[new_y])# Calculate the log likelihood
AddCounts(x, new_y, i, 1) # add the counts
ycorpus[i][j] = new_y
print ll22
print out wcounts and tcounts

NLP Programming Tutorial 7 – Topic Models

Exercise23

NLP Programming Tutorial 7 – Topic Models

Exercise●

Write learn-lda●

Test the program, setting NUM_TOPICS to 2●

●

●

●

Input: test/07­train.txt●

Answer:–No correct answer! (Because sampling is random)–However, “a b c d” and “e f g h” should probably be different topics

Train a topic model on data/wiki­en­documents.word
with 20 topics

Find some topics that match with your intuition
Challenge: Change the model so you don't have to choose
the number of topics in advance24(Read about non-parametric Bayesian techniques)

NLP Programming Tutorial 7 – Topic Models

Thank You!

25