Introduction to Topic Models

Vivi Nastase

Summer semester 2012

ICL, University of Heidelberg

1
 Course plan

Scheduling:
• Lecture: Thursdays, 14-16, here
• Office hours: Thursdays, 11-12 (Room 121)
• e-mail: nastase@[Link]

Work:
• attend the lectures, and interact – bring pens and papers! I
will rarely have slides
• a semester long project
• present and discuss an assigned paper
• oral exam

2
 Goals

• understand the mathematical formalism behind topic models

• figure out the strengths and weaknesses of this type of
approaches (the hunting joke is true!)
• look at some of the more interesting extensions of the vanilla
LDA
• give you hands on experience in developing a topic model

3
 Project: LDA with your favourite extension

Homework 1, due date May 17th :

• pick your favourite text collection from the ICL’s resources
• implement a system that splits the input data into fragments
(sentences / paragraphs/ documents) – this should be a
parameter
• represent the data in a structure that matches the split
• send me an archive with your code and documentation by
May 17th

4
Why topic models?

5
 Topic models

from David Blei, KDD-11 tutorial

• Observation: a collection of texts

• Assumption: the texts have been generated according to some
model
• Output: the model that has generated the texts

6
 Topic models

• Discover hidden topical patterns that pervade the collection

through statistical regularities
• Annotate documents with these topics
• Use the topic annotations to organize, summarize, search
texts ...
7
Topic examples

Steyvers & Griffiths, 2006

8
LSA and topic models

Steyvers & Griffiths, 2006

9
 Topic models – intuition

• Find the latent structure of “topics” or “concepts” in a text

corpus, which is obscured by “word choice” noise
• Deerwester et al (1990) – LSA – co-occurrence of terms in
text documents can be used to recover this latent structure,
without additional knowledge.
• Latent topic representations representations of text allow
modelling linguistic phenomena, like synonymy and
polysemy.
10
 Topic models

Each document is a mixture of topics:

X X
p(zm = k) = θm,k = 1
k k
Each word is drawn from one of its document’s topics:

X X
p(wm,n ) = p(wm,n |zm,n = k)p(zm,n = k) = ϕk (wm,n )θm,k
k k
11
 Topic models

The observations are the documents: wm , m ∈ 1, M

We need to infer the model, i.e the underlying topic structure,
i.e. the topic assignments zm,n , the topic θm , m ∈ 1, M and
word distributions ϕk , k ∈ 1, K
Priors:
θ ∼ distribution with hyperparameter α
ϕ ∼ distribution with hyperparameter β
12
 Topic models – Latent Dirichlet Allocation

1 Y α −1
p(θ|α) = θk k
B(α)
k
X
θm,k = 1
k

α controls the mean shape and sparsity of θ

The topic proportions (θm ) are a K-dimensional Dirichlet
zm,n are multinomial distributions from θm
K
N! Y nk
p(zm,n |θm ) = QK θm,k
k=1 nk ! k=1

13
 Topic models – Latent Dirichlet Allocation

1 Y
p(ϕ|β) = ϕβv −1
B(β) v v
X
ϕk,v = 1
v

β controls the mean shape and sparsity of ϕ

The topics (ϕk ) are a V-dimensional Dirichlet
wm,n are multinomial distributions from ϕzm,n
V
V! Y
nv
p(wm,n |ϕk ) = QV ϕk,v
v =1 nv ! v =1

14
Topic models – inference via Gibbs sampling

15
Topic models – inference via Gibbs sampling

p(x = 1, O|αh , αt ) nh + αh
p(x = 1|O, αh , αt ) = =
p(O|αh , αt ) N + αh + αt
16
Topic examples

17
 Topic examples

Object ≡ bag of words with labels

18
 Topic examples

Basic components:
• A set of entities (e.g. documents, images, individuals, genes)
• A set of relations (e.g. citation, coauthor, co-tag, friends,
pathways)
19
 Topic models in machine learning

• generative – assume an underlying model (probability

distribution, parameters) generated the observed data
• the class is a hidden variable
• can handle a large number of classes
• difference relative to discriminative models?

20
 Topic models in machine learning

• generative – assume an underlying model (probability

distribution, parameters) generated the observed data
• the class is a hidden variable
• can handle a large number of classes
• difference relative to discriminative models?
discriminative: P(Y |X )
generative: P(Y , X )

21
 References

• Probabilistic topic models, Mark Steyvers, Tom Griffiths

• Parameter estimation for text analysis, Gregor Heinrich
• Topic Models, David Blei (tutorial, [Link])
• Any of the many tutorials you can find on-line

22
Probabilities refresher

23
probability/probable
late 14c., from [Link]. probable (14c.), from L. probabilis
”provable,” from probare ”to try, to test”
Wahrsheinlichkeit/wahrsheinlich
seems to be true
 Probabilities refresher

An experiment whose outcome depends on chance

random variable X captures the outcome of the experiment
sample space S the set of all possible outcomes
event E ⊆ S
X can be
discrete if S is finite or countably infinite
continuous
Examples?
 Distributions and probabilities
The distribution function:

p : S → [0, 1]

p(x) ≥ 0, ∀x ∈ S
X
p(x) = 1
x∈S

26
 Distributions and probabilities
The distribution function:

p : S → [0, 1]

p(x) ≥ 0, ∀x ∈ S
X
p(x) = 1
x∈S

Probability of an event:
X
P(E ) = p(x)
x∈E

P({x}) = p(x)

27
 A bit of practice

1. dice rolling
2. tossing two coins

28
Properties of probabilities

P(E ) ≥ 0, ∀E ⊆ S

29
Properties of probabilities

P(E ) ≥ 0, ∀E ⊆ S
P(S) = 1
Properties of probabilities

P(E ) ≥ 0, ∀E ⊆ S
P(S) = 1
E ⊂ F ⊂ S → P(E ) ≤ P(F )
 Properties of probabilities

P(E ) ≥ 0, ∀E ⊆ S
P(S) = 1
E ⊂ F ⊂ S → P(E ) ≤ P(F )
E ∩ F = ∅ → P(E ∪ F ) = P(E ) + P(F )
 Properties of probabilities

P(E ) ≥ 0, ∀E ⊆ S
P(S) = 1
E ⊂ F ⊂ S → P(E ) ≤ P(F )
E ∩ F = ∅ → P(E ∪ F ) = P(E ) + P(F )
P(Ē) = 1 − P(E )
 Properties of probabilities

P(E ) ≥ 0, ∀E ⊆ S
P(S) = 1
E ⊂ F ⊂ S → P(E ) ≤ P(F )
E ∩ F = ∅ → P(E ∪ F ) = P(E ) + P(F )
P(Ē) = 1 − P(E )
Proofs?
 Examples of probabilities in language models

• the sample space

• the events
• distributions

35
 Expected value

Discrete: X
E (X ) = xP(x)
x∈S

Continuous: Z b
E (X ) = xp(x)dx
a

36
 Common discrete distributions
Uniform(n) : |S| = n, n is finite
1
P(X = x) =
n

37
 Common discrete distributions
Uniform(n) : |S| = n, n is finite
1
P(X = x) =
n
Bernoulli(p) : p ∈ [0, 1]; X ∈ 0, 1:

P(X = 1) = p; P(X = 0) = 1 − p

38
 Common discrete distributions
Uniform(n) : |S| = n, n is finite
1
P(X = x) =
n
Bernoulli(p) : p ∈ [0, 1]; X ∈ 0, 1:

P(X = 1) = p; P(X = 0) = 1 − p
Binomial(p,n) : p ∈ [0, 1]; X ∈ 0, 1, ..., n; n ∈ N
 
n x
P(X = x) = p (1 − p)(n−x)
x

39
 Common discrete distributions
Uniform(n) : |S| = n, n is finite
1
P(X = x) =
n
Bernoulli(p) : p ∈ [0, 1]; X ∈ 0, 1:

P(X = 1) = p; P(X = 0) = 1 − p
Binomial(p,n) : p ∈ [0, 1]; X ∈ 0, 1, ..., n; n ∈ N
 
n x
P(X = x) = p (1 − p)(n−x)
x
P
Multinomial(p1 , ..., pk ; x1 , ..., xk ; n) : i xi = n

n!
P(X1 = x1 , ..., Xk = xk ) = p x1 ...pkxk
x1 !...xk ! 1
...
40
Common continuous distributions
Z x
P(X ≤ x) = p(y )dy
−∞

41
 Common continuous distributions
Z x
P(X ≤ x) = p(y )dy
−∞

Uniform(a,b) : a, b ∈ R, a < b, X ∈ [a, b]

1
p(x) =
b−a

42
 Common continuous distributions
Z x
P(X ≤ x) = p(y )dy
−∞

Uniform(a,b) : a, b ∈ R, a < b, X ∈ [a, b]

1
p(x) =
b−a
Beta(α, β) : α, β ∈ R++ , X ∈ [0, 1]

Γ(α + β) α−1
p(x; α, β) = x (1 − x)β−1
Γ(α)Γ(β)

43
 Common continuous distributions
Z x
P(X ≤ x) = p(y )dy
−∞

Uniform(a,b) : a, b ∈ R, a < b, X ∈ [a, b]

1
p(x) =
b−a
Beta(α, β) : α, β ∈ R++ , X ∈ [0, 1]

Γ(α + β) α−1
p(x; α, β) = x (1 − x)β−1
Γ(α)Γ(β)
Dirichlet(α) : generalization of Beta(α, β)

44
 Common continuous distributions
Z x
P(X ≤ x) = p(y )dy
−∞

Uniform(a,b) : a, b ∈ R, a < b, X ∈ [a, b]

1
p(x) =
b−a
Beta(α, β) : α, β ∈ R++ , X ∈ [0, 1]

Γ(α + β) α−1
p(x; α, β) = x (1 − x)β−1
Γ(α)Γ(β)
Dirichlet(α) : generalization of Beta(α, β)
Normal(µ, σ 2 ) : µ ∈ R, σ ∈ R++ , X ∈ R

1 (x−µ)2
p(x) = √ e − 2σ2
σ 2π
45
Test

46
 Test

Two random variables

thought they were discrete
but I heard them continuously.

47
Next week sneak preview

48
 Next week sneak preview

Bayes’ law and conjugate distributions

49