Topical N-grams: Phrase and Topic Discovery,

with an Application to Information Retrieval

Xuerui Wang, Andrew McCallum, Xing Wei

University of Massachusetts
140 Governors Dr, Amherst, MA 01003
{xuerui, mccallum, xwei}@cs.umass.edu

Abstract cluding parsing, machine translation and information re-

trieval. In general, phrases as the whole carry more in-
Most topic models, such as latent Dirichlet allocation, formation than the sum of its individual components, thus
rely on the bag-of-words assumption. However, word order they are much more crucial in determining the topics of col-
and phrases are often critical to capturing the meaning of lections than individual words. Most topic models such as
text in many text mining tasks. This paper presents topical latent Dirichlet allocation (LDA) [2], however, assume that
n-grams, a topic model that discovers topics as well as top- words are generated independently from each other, i.e., un-
ical phrases. The probabilistic model generates words in der the bag-of-words assumption. Adding phrases increases
their textual order by, for each word, first sampling a topic, the model’s complexity, but it could be useful in certain con-
then sampling its status as a unigram or bigram, and then texts. The possible over complicacy caused by introducing
sampling the word from a topic-specific unigram or bigram phrases makes these topic models completely ignore them.
distribution. Thus our model can model “white house” as It is true that these models with the bag-of-words assump-
a special meaning phrase in the ‘politics’ topic, but not tion have enjoyed a big success, and attracted a lot of inter-
in the ‘real estate’ topic. Successive bigrams form longer ests from researchers with different backgrounds. We be-
phrases. We present experimental results showing mean- lieve that a topic model considering phrases would be defi-
ingful phrases and more interpretable topics from the NIPS nitely more useful in certain applications.
data and improved information retrieval performance on a Assume that we conduct topic analysis on a large collec-
TREC collection. tion of research papers. The acknowledgment sections of
research papers have a distinctive vocabulary. Not surpris-
ingly, we would end up with a particular topic on acknowl-
edgment (or funding agencies) since many papers have an
1 Introduction acknowledgment section that is not tightly coupled with the
content of papers. One might therefore expect to find words
Although the bag-of-words assumption is prevalent in such as “thank”, “support” and “grant” in a single topic.
document classification and topic models, the great major- One might be very confused, however, to find words like
ity of natural language processing methods represent word “health” and “science” in the same topic, unless they are
order, including n-gram language models for speech recog- presented in context: “National Institutes of Health” and
nition, finite-state models for information extraction and “National Science Foundation”.
context-free grammars for parsing. Word order is not only Phrases often have specialized meaning, but not always.
important for syntax, but also important for lexical mean- For instance, “neural networks” is considered a phrase be-
ing. A collocation is a phrase with meaning beyond the cause of its frequent use as a fixed expression. However, it
individual words. For example, the phrase “white house” specifies two distinct concepts: biological neural networks
carries a special meaning beyond the appearance of its in- in neuroscience and artificial neural networks in modern us-
dividual words, whereas “yellow house” does not. Note, age. Without consulting the context in which the term is lo-
however, that whether or not a phrase is a collocation may cated, it is hard to determine its actual meaning. In many sit-
depend on the topic context. In the context of a document uations, topic is very useful to accurately capture the mean-
about real estate, “white house” may not be a collocation. ing. Furthermore, topic can play a role in phrase discovery.
N -gram phrases are fundamentally important in many Considering learning English, a beginner usually has diffi-
areas of natural language processing and text mining, in- culty in telling “strong tea” from “powerful tea” [15], which
are both grammatically correct. The topic associated with SYMBOL DESCRIPTION
“tea” might help to discover the misuse of “powerful”. T number of topics
In this paper, we propose a new topical n-gram (TNG) D number of documents
model that automatically determines unigram words and W number of unique words
phrases based on context and assign mixture of topics to Nd number of word tokens in document d
(d)
both individual words and n-gram phrases. The ability to zi the topic associated with the ith token in the
form phrases only where appropriate is unique to our model, document d
(d)
distinguishing it from the traditional collocation discovery xi the bigram status between the (i − 1)th token
methods discussed in Section 3, where a discovered phrase and ith token in the document d
is always treated as a collocation regardless of the context wi
(d)
the ith token in document d
(which would possibly make us incorrectly conclude that
θ(d) the multinomial (Discrete) distribution of topics
“white house” remains a phrase in a document about real
w.r.t. the document d
estate). Thus, TNG is not only a topic model that uses
φz the multinomial (Discrete) unigram distribution
phrases, but also help linguists discover meaningful phrases
of words w.r.t. topic z
in right context, in a completely probabilistic manner. We
ψv in Figure 1(b), the binomial (Bernoulli) distribution
show examples of extracted phrases and more interpretable
of status variables w.r.t. previous word v
topics on the NIPS data, and in a text mining application,
ψzv in Figure 1(c), the binomial (Bernoulli) distribution
we present better information retrieval performance on an
of status variables w.r.t. previous topic z/word v
ad-hoc retrieval task over a TREC collection.
σzv in Figure 1(a) and (c), the multinomial (Discrete)
bigram distribution of words w.r.t. topic z/word v
2 N -gram based Topic Models σv in Figure 1(b), the multinomial (Discrete) bigram
distribution of words w.r.t. previous word v
α Dirichlet prior of θ
Before presenting our topical n-gram model, we first de-
β Dirichlet prior of φ
scribe two related n-gram models. Notation used in this pa-
γ Dirichlet prior of ψ
per is listed in Table 1, and the graphical models are showed
δ Dirichlet prior of σ
in Figure 1. For simplicity, all the models discussed in this
section make the 1st order Markov assumption, that is, they
are actually bigram models. However, all the models have Table 1. Notation used in this paper
the ability to “model” higher order n-grams (n > 2) by
concatenating consecutive bigrams.
2.2 LDA Collocation Model (LDACOL)
2.1 Bigram Topic Model (BTM)
Starting from the LDA topic model, the LDA colloca-
Recently, Wallach develops a bigram topic model [22] on tion model [20] (not yet published) introduces a new set
the basis of the hierarchical Dirichlet language model [14], of random variables (for bigram status) x (xi = 1: wi−1
by incorporating the concept of topic into bigram models. and wi form a bigram; xi = 0: they do not) that denote if
This model is one solution for the “neural network” exam- a bigram can be formed with the previous token, in addi-
ple in Section 1. We assume a dummy word w0 existing at tion to the two sets of random variables z and w in LDA.
the beginning of each document. The graphical model pre- Thus, it has the power to decide if to generate a bigram or
sentation of this model is shown in Figure 1(a). The gener- a unigram. At this aspect, it is more realistic than the bi-
ative process of this model can be described as follows: gram topic model which always generates bigrams. After
all, unigrams are the major components in a document. We
1. draw Discrete distributions σzw from a Dirichlet prior assume the status variable x1 is observed, and only a uni-
δ for each topic z and each word w; gram is allowed at the beginning of a document. If we want
to put more constraints into the model (e.g., no bigram is
2. for each document d, draw a Discrete distribution θ(d) allowed for sentence/paragraph boundary; only a unigram
(d)
from a Dirichlet prior α; then for each word wi in can be considered for the next word after a stop word is
document d: removed; etc.), we can assume that the corresponding sta-
(d)
tus variables are observed as well. This model’s graphical
(a) draw zi from Discrete θ(d) ; and model presentation is shown in Figure 1(b).
(b) draw wi
(d)
from Discrete σz(d) w(d) . The generative process of the LDA collocation model is
i i−1 described as follows:
 α 1. draw Discrete distributions φz from a Dirichlet prior β
for each topic z;
θ
2. draw Bernoulli distributions ψw from a Beta prior γ
... zi−1 zi zi+1 zi+2 ... for each word w;

3. draw Discrete distributions σw from a Dirichlet prior δ

for each word w;

... wi−1 wi wi+1 wi+2 ... 4. for each document d, draw a Discrete distribution θ(d)
(d)
D from a Dirichlet prior α; then for each word wi in
document d:
(d)
(a) draw xi from Bernoulli ψw(d) ;
σ δ i−1

TW (b) draw
(d)
zi from Discrete θ (d)
; and
(a) Bigram topic model (d) (d)
(c) draw wi from Discrete σw(d) if xi = 1; else
α i−1
(d)
draw wi from Discrete φz(d) .
i
θ
Note that in the LDA Collocation model, bigrams do not
... zi−1 zi zi+1 zi+2 ... have topics as the second term of a bigram is generated from
a distribution σv conditioned on the previous word v only.
... xi xi+1 xi+2 ...
2.3 Topical N -gram Model (TNG)
... wi−1 wi wi+1 wi+2 ...
D The topical n-gram model (TNG) is not a pure addition
of the bigram topic model and LDA collocation model. It
can solve the problem associated with the “neural network”
φ γ ψ σ example as the bigram topic model, and automatically de-
β δ
termine whether a composition of two terms is indeed a bi-
T W
gram as in the LDA collocation model. However, like other
(b) LDA-Collocation model collocation discovery methods discussed in Section 3, a dis-
α covered bigram is always a bigram in the LDA Collocation
model no matter what the context is.
θ One of the key contributions of our model is to make it
possible to decide whether to form a bigram for the same
... zi−1 zi zi+1 zi+2 ... two consecutive word tokens depending on their nearby
context (i.e., co-occurrences). Thus, additionally, our model
... xi xi+1 xi+2 ... is a perfect solution for the “white house” example in Sec-
tion 1. As in the LDA collocation model, we may assume
... wi−1 wi wi+1 wi+2 ... some x’s are observed for the same reason as we discussed
in Section 2.2. The graphical model presentation of this
D
model is shown in Figure 1(c). Its generative process can
be described as follows:

β φ γ ψ σ δ 1. draw Discrete distributions φz from a Dirichlet prior β

T TW for each topic z;
(c) Topical n-gram model
2. draw Bernoulli distributions ψzw from a Beta prior γ
Figure 1. Three n-gram based topic models for each topic z and each word w;

3. draw Discrete distributions σzw from a Dirichlet prior

δ for each topic z and each word w;
 (d)
4. for each document d, draw a Discrete distribution θ(d) conveniently1 using Bayes rule, where z−i denotes the
(d)
from a Dirichlet prior α; then for each word wi in topic assignments for all word tokens except word wi ,
(d)
document d: (d)
and x−i represents the bigram status for all tokens except
(d) (d)
(a) draw xi from Bernoulli ψz(d) w(d) ; word wi . During Gibbs sampling, we draw the topic as-
i−1 i−1 (d) (d)
signment zi and the bigram status xi iteratively2 for
(d)
(b) draw zi from Discrete θ(d) ; and (d)
each word token wi according to the following condi-
(c) draw wi
(d)
from Discrete σz(d) w(d) if xi
(d)
= 1; tional probability distribution:
i i−1
(d) (d) (d) (d)
else draw wi
(d)
from Discrete φz(d) . P (zi , xi |z−i , x−i , w, α, β, γ, δ)
i
∝ (γx(d) + pz(d) w(d) xi − 1)(αz(d) + qdz(d) − 1)
Note that our model is a more powerful generalization of i i−1 i−1 i i

β (d) +n (d) (d) −1

BTM and of LDACOL. Both BTM (by setting all x’s to 1) 
 PWi
 w z
i
w
i (d)
if xi = 0
and LDACOL (by making σ conditioned on previous word (βv +n (d) )−1

 v=1 z v
only) are the special cases of our TNG models. × i
δ (d) +m (d) (d) (d) −1
w z w w (d)
i i i−1 i
if xi = 1

Before discussing the inference problem of our model,

 PW

 (δv +m (d) (d) )−1
v=1 z w v
let us pause for a brief interlude on topic consistency of i i−1

terms in a bigram. As shown in the above, the topic as- where nzw represents how many times word w is assigned
signments for the two terms in a bigram are not required into topic z as a unigram, mzwv represents how many times
to be identical. We can take the topic of the first/last word word v is assigned to topic z as the 2nd term of a bigram
token or the most common topic in the phrase, as the topic given the previous word w, pzwk denotes how many times
of the phrase. In this paper, we will use the topic of the the status variable x = k (0 or 1) given the previous word
last term as the topic of the phrase for simplicity, since long w and the previous word’s topic z, and qdz represents how
noun phrases do truly sometimes have components indica- many times a word is assigned to topic z in document d.
tive of different topics, and its last noun is usually the “head Note all counts here do include the assignment of the token
noun”. Alternatively, we could enforce consistency in the being visited. Details of the Gibbs sampling derivation are
model with ease, by simply adding two more sets of arrows provided in Appendix A.
(zi−1 → zi and xi → zi ). Accordingly, we could substitute Simple manipulations give us the posterior estimates of
(d)
Step 4(b) in the above generative process with “draw zi θ, φ, ψ, and σ as follows:
(d) (d) (d)
from Discrete θ(d) if xi = 1; else let zi = zi−1 ;” In (d)
this way, a word has the option to inherit a topic assignment θ̂z = PTαz +qdz φ̂zw = PWβw +nzw
(αt +qdt ) (βv +nzv )
from its previous word if they form a bigram phrase. How-
t=1
γk +pzwk
v=1 (1)
ψ̂zwk =P 1 σ̂zwv = PWδv +mzwv
ever, from our experimental results, the first choice yields (γk +pzwk ) (δv +mzwv )
k=0 v=1

better performance. From now on, we will focus on the As discussed in the bigram topic model [22], one could
model shown in Figure 1(c). certainly infer the values of the hyperparameters in TNG
Finally we want to point out that the topical n-gram using a Gibbs EM algorithm [1]. For many applications,
model is not only a new framework for distilling n-gram topic models are sensitive to hyperparameters, and it is im-
phrases depending on nearby context, but also a more sen- portant to get the right values for the hyperparameters. In
sible topic model than the ones using word co-occurrences the particular experiments discussed in this paper, however,
alone. we find that sensitivity to hyperparameters is not a big con-
In state-of-the-art hierarchical Bayesian models such as cern. For simplicity and feasibility in our Gigabyte TREC
latent Dirichlet allocation, exact inference over hidden topic retrieval tasks, we skip the inference of hyperparameters,
variables is typically intractable due to the large number and use some reported empirical values for them instead to
of latent variables and parameters in the models. Approxi- show salient results.
mate inference techniques such as variational methods [12],
Gibbs sampling [1] and expectation propagation [17] have
3 Related Work
been developed to address this issue. We use Gibbs sam-
pling to conduct approximate inference in this paper. To
Collocation has long been studied by lexicographers and
reduce the uncertainty introduced by θ, φ, ψ, and σ, we
linguists in various ways. Traditional collocation discov-
could integrate them out with no trouble because of the con-
jugate prior setting in our model. Starting from the joint 1 As (d)
shown in Appendix A, one could further calculate P (zi | · · ·)
distribution P (w, z, x|α, β, γ, δ), we can work out the con- (d)
and P (xi | · · ·) as in a traditional Gibbs sampling procedure.
(d) (d) (d) (d)
ditional probabilities P (zi , xi |z−i , x−i , w, α, β, γ, δ) 2 For some observed x(d) , only z (d) needs to be drawn.
i i
ery methods range from frequency to variance, to hypothe- with comparison to the corresponding closest (by KL diver-
sis testing, to mutual information. The simplest method is gence) topics found by LDA.
counting. A small amount of linguistic knowledge (a part- The “Reinforcement Learning” topic provides an ex-
of-speech filter) has been combined with frequency [13] to tremely salient summary of the corresponding research
discover surprisingly meaningful phrases. Variance based area. The LDA topic assembles many common words used
collocation discovery [19] considers collocations in a more in reinforcement learning, but in its word list, there are quite
flexible way than fixed phrases. However, high frequency a few generic words (such as “function”, “dynamic”, “deci-
and low variance can be accidental. Hypothesis testing can sion”) that are common and highly probable in many other
be used to assess whether or not two words occur together topics as well. In TNG, we can find that these generic words
more often than chance. Many statistical tests have been are associated with other words to form n-gram phrases
explored, for example, t-test [5], χ2 test [4], and likelihood (such as “markov decision process”, etc.) that are only
ratio test [7]. More recently, an information-theoretically highly probable in reinforcement learning. More impor-
motivated method for collocation discovery is utilizing mu- tantly, by forming n-gram phrases, the unigram word list
tual information [6, 11]. produced by TNG is also cleaner. For example, because
The hierarchical Dirichlet language model [14] is closely of the prevalence of generic words in LDA, highly related
related to the bigram topic model [22]. The probabilistic words (such as “q-learning” and “goal”) are not ranked high
view of smoothing in language models shows how to take enough to be shown in the top 20 word list. On the contrary,
advantage of a bigram model in a Bayesian way. they are ranked very high in the TNG’s unigram word list.
The main stream of topic modeling has gradually gained In the other three topics (Table 2), we can find similar
a probabilistic flavor as well in the past decade. One of phenomena as well. For example, in “Human Receptive
the most popular topic model, latent Dirichlet allocation System”, some generic words (such as “field”, “receptive”)
(LDA), which makes the bag-of-words assumption, has are actually the components of the popular phrases in this
made a big impact in the fields of natural language pro- area as shown in the TNG model. “system” is ranked high in
cessing, statistical machine learning and text mining. Three LDA, but almost meaningless, and on the other hand, it does
models we discussed in Section 2 all contain an LDA com- not appear in the top word lists of TNG. Some extremely
ponent that is responsible for the topic part. related words (such as “spatial”), ranked very high in TNG,
In our point of view, the HMMLDA model [10] is the are absent in LDA’s top word list. In “Speech Recognition”,
first attack to word dependency in the topic modeling frame- the dominating generic words (such as “context”, “based”,
work. The authors present HMMLDA as a generative com- “set”, “probabilities”, “database”) make the LDA topic less
posite model that takes care of both short-range syntac- understandable than even just TNG’s unigram word list.
tic dependencies and long-range semantic dependencies be- In many situations, a crucially related word might be not
tween words; its syntactic part is a hidden Markov model mentioned enough to be clearly captured in LDA, on the
and the semantic component is a topic model (LDA). Inter- other hand, it would become very salient as a phrase due to
esting results based on this model are shown on tasks such the relatively stronger co-occurrence pattern in an extremely
as part-of-speech tagging and document classification. sparse setting for phrases. The “Support Vector Machines”
topic provides such an example. We can imagine that “kkt”
4 Experimental Results will be mentioned no more than a few times in a typical
NIPS paper, and it probably appears only as a part of the
We apply the topical n-gram model to the NIPS pro- phrase “kkt conditions”. TNG satisfyingly captures it suc-
ceedings dataset that consists of the full text of the 13 cessfully as a highly probable phrase in the SVM topic.
years of proceedings from 1987 to 1999 Neural Informa- As we discussed before, higher-order n-grams (n > 2)
tion Processing Systems (NIPS) Conferences. In addition can be approximately modeled by concatenating consecu-
to downcasing and removing stopwords and numbers, we tive bigrams in the TNG model, as shown in Table 2 (such
also removed the words appearing less than five times in as “markov decision process”, “hidden markov model” and
the corpus—many of them produced by OCR errors. Two- “support vector machines”, etc.).
letter words (primarily coming from equations), were re- To numerically evaluate the topical n-gram model, we
moved, except for “ML”, “AI”, “KL”, “BP”, “EM” and could have used some standard measures such as perplexity
“IR.” The dataset contains 1,740 research papers, 13,649 and document classfication accuracy. However, to convinc-
unique words, and 2,301,375 word tokens in total. Top- ingly illustrate the power of the TNG model on larger, more
ics found from a 50-topic run on the NIPS dataset (10,000 real scale, here we apply the TNG model to a much larger
Gibbs sampling iterations, with symmetric priors α = 1, standard text mining task—we employ the TNG model
β = 0.01, γ = 0.1, and δ = 0.01) of the topical n- within the language modeling framework to conduct ad-hoc
gram model are shown in Table 2 as anecdotal evidence, retrieval on Gigabyte TREC collections.
 Reinforcement Learning Human Receptive System
LDA n-gram (2+) n-gram (1) LDA n-gram (2+) n-gram (1)
state reinforcement learning action motion receptive field motion
learning optimal policy policy visual spatial frequency spatial
policy dynamic programming reinforcement field temporal frequency visual
action optimal control states position visual motion receptive
reinforcement function approximator actions figure motion energy response
states prioritized sweeping function direction tuning curves direction
time finite-state controller optimal fields horizontal cells cells
optimal learning system learning eye motion detection figure
actions reinforcement learning rl reward location preferred direction stimulus
function function approximators control retina visual processing velocity
algorithm markov decision problems agent receptive area mt contrast
reward markov decision processes q-learning velocity visual cortex tuning
step local search goal vision light intensity moving
dynamic state-action pair space moving directional selectivity model
control markov decision process step system high contrast temporal
sutton belief states environment flow motion detectors responses
rl stochastic policy system edge spatial phase orientation
decision action selection problem center moving stimuli light
algorithms upright position steps light decision strategy stimuli
agent reinforcement learning methods transition local visual stimuli cell
Speech Recognition Support Vector Machines
LDA n-gram (2+) n-gram (1) LDA n-gram (2+) n-gram (1)
recognition speech recognition speech kernel support vectors kernel
system training data word linear test error training
word neural network training vector support vector machines support
face error rates system support training error margin
context neural net recognition set feature space svm
character hidden markov model hmm nonlinear training examples solution
hmm feature vectors speaker data decision function kernels
based continuous speech performance algorithm cost functions regularization
frame training procedure phoneme space test inputs adaboost
segmentation continuous speech recognition acoustic pca kkt conditions test
training gamma filter words function leave-one-out procedure data
characters hidden control context problem soft margin generalization
set speech production systems margin bayesian transduction examples
probabilities neural nets frame vectors training patterns cost
features input representation trained solution training points convex
faces output layers sequence training maximum margin algorithm
words training algorithm phonetic svm strictly convex working
frames test set speakers kernels regularization operators feature
database speech frames mlp matrix base classifiers sv
mlp speaker dependent hybrid machines convex optimization functions

Table 2. The four topics from a 50-topic run of TNG on 13 years of NIPS research papers with their
closest counterparts from LDA. The Title above the word lists of each topic is our own summary of
the topic. To better illustrate the difference between TNG and LDA, we list the n-grams (n > 1) and
unigrams separately for TNG. Each topic is shown with the 20 sorted highest-probability words. The
TNG model produces clearer word list for each topic by associating many generic words (such as
“set”, “field”, “function”, etc.) with other words to form n-gram phrases.
4.1 Ad-hoc Retrieval γ = 0.1, and δ = 0.01) for the NIPS dataset are used. Here,
we aim to beat the state-of-the-art model [23] instead of the
Traditional information retrieval (IR) models usually state-of-the-art results in TREC retrieval that need signifi-
represent text with bags-of-words assuming that words oc- cant, non-modeling effort to achieve (such as stemming).
cur independently, which is not exactly appropriate to nat-
ural language. To address this problem, researchers have 4.2 Difference between Topical N-grams
been working on capturing word dependencies. There are and LDA in IR Applications
mainly two types of dependencies being studied and shown
From both of LDA and TNG, a word distribution for
to be effective: 1) topical (semantic) dependency, which is
each document can be calculated, which thus can be viewed
also called long-distance dependency. Two words are con-
as a document model. With these distributions, the likeli-
sidered dependent when their meanings are related and they
hood of generating a query can be computed to rank docu-
co-occur often, such as “fruit” and “apple”. Among mod-
ments, which is the basic idea in the query likelihood (QL)
els capturing semantic dependency, the LDA-based docu-
model in IR. When the two models are directly applied to do
ment models [23] are state-of-the-art. For IR applications,
ad-hoc retrieval, the TNG model performs significant better
a major advantage of topic models (document expansion),
than the LDA model under the Wilcoxon test at 95% level.
compared to online query expansion in pseudo relevance
Among of 4881 relevant documents for all queries, LDA
feedback, is that they can be trained offline, thus more effi-
retrieves 2257 of them but TNG gets 2450, 8.55% more.
cient in handling a new query; 2) phrase dependency, also
The average precision for TNG is 0.0709, 61.96% higher
called short-distance dependency. As reported in literature,
than its LDA counterpart (0.0438). Although these results
retrieval performance can be boosted if the similarity be-
are not the state-of-the-art IR performance, we claim that,
tween a user query and a document is calculated by com-
if used alone, TNG represent a document better than LDA.
mon phrases instead of common words [9, 8, 21, 18]. Most
The average precisions for both models are very low, be-
research on phrases in information retrieval has employed
cause corpus-level topics may be too coarse to be used as
an independent collocation discovery module, e.g., using
the only representation in IR [3, 23]. Significant improve-
the methods described in Section 3. In this way, a phrase
ments in IR can be achieved through a combination with the
can be indexed exactly as an ordinary word.
basic query likelihood model.
The topical n-gram model automatically and simulta- In the query likelihood model, each document is scored
neously takes cares of both semantic co-occurrences and by the likelihood of its model generating a query Q,
phrases. Also, it does not need a separate module for phrase PLM (Q|d). Let the query Q = (q1 , q2 , ..., qLQ ). Under
discovery, and everything can be seamlessly integrated into QLQ
the bag-of-words assumption, PLM (Q|d) = i=1 P (qi |d),
the language modeling framework, which is one of the most which is often specified by the document model with
popular statistically principled approaches to IR. In this sec- Dirichlet smoothing [24],
tion, we illustrate the difference in IR experiments of the
Nd Nd
TNG and LDA models, and compare the IR performance PLM (q|d) = PM L (q|d) + (1 − )PM L (q|coll),
Nd + µ Nd + µ
of all three models in Figure 1 on a TREC collection intro-
duced below. where Nd is the length of document d, PM L (q|d) and
The SJMN dataset, taken from TREC with standard PM L (q|coll) are the maximum likelihood (ML) estimates
queries 51-150 that are taken from the title field of TREC of a query term q generated in document d and in the en-
topics, covers materials from San Jose Mercury News in tire collection, respectively, and µ is the Dirichlet smooth-
1991. All text is downcased and only alphabetic characters ing prior (in our reported experiments we used a fixed value
are kept. Stop words in both the queries and documents with µ = 1000 as in [23]).
are removed, according to a common stop word list in the To calculate the query likelihood from the TNG model
Bow toolkit [16]. If any two consecutive tokens were orig- within the language modeling framework, we need to sum
inally separated by a stopword, no bigram is allowed to be over the topic variable and bigram status variable for each
formed. In total, the SJMN dataset we use contains 90,257 token in the query token sequence. Given the posterior es-
documents, 150,714 unique words, and 21,156,378 tokens, timates θ̂, φ̂, ψ̂, and σ̂ (Equation 1), the query likelihood of
which is order of magnitude larger than the NIPS dataset. query Q given document d, PT N G (Q|d) can be calculated3
Relevance judgments are taken from the the judged pool as
of the top retrieved documents by various participating re- LQ
Y
trieval systems from previous TREC conferences. PT N G (Q|d) = PT N G (qi |qi−1 , d),
The number of topics are set to be 100 for all models i=1
with 10,000 Gibbs sampling iterations, and the same hyper- 3 A dummy q is assumed at the beginning of every query, for the con-
0
parameter setting (with symmetric priors α = 1, β = 0.01, venience of mathematical presentation.
 No. Query LDA TNG Change
053 Leveraged Buyouts 0.2141 0.3665 71.20%
097 Fiber Optics Applications 0.1376 0.2321 68.64%
108 Japanese Protectionist Measures 0.1163 0.1686 44.94%
111 Nuclear Proliferation 0.2353 0.4952 110.48%
064 Hostage-Taking 0.4265 0.4458 4.52%
125 Anti-smoking Actions by Government 0.3118 0.4535 45.47%
145 Influence of the “Pro-Israel Lobby” 0.2900 0.2753 -5.07%
148 Conflict in the Horn of Africa 0.1990 0.2788 40.12%

Table 3. Comparison of LDA and TNG on TREC retrieval performance (average precision) of eight
queries. The top four queries obviously contain phrase(s), and thus TNG achieves much better per-
formance. On the other hand, the bottom four queries do not contain common phrase(s) after pre-
processing (stopping and punctuation removal). Surprisingly, TNG still outperforms LDA on some
of these queries.

where 4.3 Comparison of BTM, LDACOL and

T
X TNG on TREC Ad-hoc Retrieval
PT N G (qi |qi−1 , d) = (P (xi = 0|ψ̂qi−1 )P (qi |φ̂zi )
zi =1 In this section, we compare the IR performance of the
+P (xi = 1|ψ̂qi−1 )P (qi |σ̂zi qi−1 ))P (zi |θ̂(d) ), three n-gram based topic models on the SJMN dataset5 , as
shown in Table 4. For a fair comparison, the weighting fac-
and, tor λ (reported in Table 4) are independently chosen to get
T
X the best performance from each model. Under the Wilcoxon
P (xi |ψ̂qi−1 ) = P (xi |ψ̂zi−1 qi−1 )P (zi−1 |θ̂(d) ). test with 95% confidence, TNG significantly outperforms
zi−1 =1 BTM and LDACOL on this standard retrieval task.
Due to stopping and punctuation removal, we may simply Space limitations prevent us from presenting the results
set P (xi = 0|ψ̂qi−1 ) = 1 and P (xi = 1|ψ̂qi−1 ) = 0 at for all queries, but it is interesting to see that different mod-
corresponding positions in a query. Note here in the above els are good at quite different queries. For some queries
calculation, the bag-of-words assumption is not made any (such as No. 117 and No. 138), TNG and BTM perform
more. similarly, and better than LDACOL, and for some other
Similar to the method in [23], we can combine the query queries (such as No. 110 and No. 150), TNG and LDA-
likelihood from the basic language model and the likelihood COL perform similarly, and better than BTM. There are also
from the TNG model in various ways. One can combine queries (such as No. 061 and No. 130) for which TNG per-
them at query level, i.e., forms better than both BTM and LDACOL. We believe that
they are clear empirical evidence that our TNG model are
P (Q|d) = λPLM (Q|d) + (1 − λ)PT N G (Q|d), more generic and powerful than BTM and LDACOL.
where λ is a weighting factor between the two likelihoods. We analyze the performance of the TNG model for
Alternatively, under first order Markov assumption, query No. 061, as an example. As we inspect the phrase
QLQ
P (Q|d) = P (q1 |d) i=2 P (qi |qi−1 , d), and one can com- “Iran-Contra” contained in the query, we find that it has
bine the query likelihood at query term level (used in this been primarily assigned to two topics (politics and econ-
paper), that is, omy) in TNG. This has increased the bigram likelihood
of some documents emphasizing the relevant topic (such
P (qi |qi−1 , d) = λPLM (qi |d) + (1 − λ)PT N G (qi |qi−1 , d). as “SJMN91-06263203”), thus helps promote these docu-
To illustrate the difference of TNG and LDA in IR appli- ments to higher ranks. As a special case of TNG, LDACOL
cations, we select a few of the 100 queries that clearly con- is unable to capture this and leads to inferior performance.
tain phrase(s), and another few of them that do not contain It is true that for certain queries (such as No. 069 and
phrase due to stopping and puntuation removal, on which No. 146), TNG performs worse than BTM and LDACOL,
we compare the IR performance (average precision)4 as but we notice that all models perform badly on these queries
shown in Table 3. 5 The running times of our C implementation on a dual-processor
4 The results reported in [23] is a little better since they did stemming. Opteron for the three models are 11.5, 17, 22.5 hours, respectively.
 No. Query TNG BTM Change LDACOL Change
061 Israeli Role in Iran-Contra Affair 0.1635 0.1104 -32.47% 0.1316 -19.49%
069 Attempts to Revive the SALT II Treaty 0.0026 0.0071 172.34% 0.0058 124.56%
110 Black Resistance Against the South African Government 0.4940 0.3948 -20.08% 0.4883 -1.16%
117 Capacity of the U.S. Cellular Telephone Network 0.2801 0.3059 9.21% 0.1999 -28.65%
130 Jewish Emigration and U.S.-USSR Relations 0.2087 0.1746 -16.33% 0.1765 -15.45%
138 Iranian Support for Lebanese Hostage-takers 0.4398 0.4429 0.69% 0.3528 -19.80%
146 Negotiating an End to the Nicaraguan Civil War 0.0346 0.0682 97.41% 0.0866 150.43%
150 U.S. Political Campaign Financing 0.2672 0.2323 -13.08% 0.2688 0.59%
All Queries 0.2122 0.1996 -5.94%* 0.2107 -0.73%*

Table 4. Comparison of the bigram topic model (λ = 0.7), LDA collocation model (λ = 0.9) and the
topical n-gram Model (λ = 0.8) on TREC retrieval performance (average precision). * indicates sta-
tistically significant differences in performance with 95% confidence according to the Wilcoxon test.
TNG performs significantly better than other two models overall.

and the behaviors are more possibly due to randomness. jugate priors to simplify the integrals. All symbols are
defined in Section 2.
5 Conclusions
P (w, z, x|α, β, γ, δ)
In this paper, we have presented the topical n-gram ZZZ Y D Y Nd
model. The TNG model automatically determines to form =
(d) (d)
(P (wi |xi , φz(d) , σz(d) w(d) )
an n-gram (and further assign a topic) or not, based on its d=1 i=1
i i i−1

surrounding context. Examples of topics found by TNG T Y

W
are more interpretable than its LDA counterpart. We also (d)
Y
P (xi |ψz(d) w(d) )) p(σzv |δ)p(ψzv |γ)dΣdΨ
demonstrate how TNG can help improve retrieval perfor- i−1 i−1
z=1 v=1
mance in standard ad-hoc retrieval tasks on TREC collec- T D
Z Y Nd
!
tions over its two special-case n-gram based topic models. (d)
Y Y
p(φz |β)dΦ P (zi |θd )p(θd |α) dΘ
Unlike some traditional phrase discovery methods, the z=1 d=1 i=1
TNG model provides a systematic way to model (topical) T
Z Y W PW W
!
phrases and can be seamlessly integrated with many proba-
Y Γ( v=1 βv ) Y βv −1
= QWφnzvzv φzv dΦ
bilistic frameworks for various tasks such as phrase discov- z=1 v=1 v=1 Γ(βv ) v=1
ery, ad-hoc retrieval, machine translation, speech recogni- Z YT Y W W PW W
!
Y Γ( δ v ) Y
tion and statistical parsing. × mzwv
σzwv QW
v=1 δv −1
σzwv dΣ
Evaluating n-gram based topic models is a big challenge. z=1 w=1 v=1 v=1 Γ(δv ) v=1
As reported in [22], the bigram topic models have only been Z YT Y W 1 P1 1
!
pzwk Γ( k=0 γv ) γk −1
Y Y
shown to be effective on hundreds of documents, and also × ψzwk Q1 ψzwk dΨ
we have not seen a formal evaluation of the unpublished z=1 w=1 k=0 k=0 Γ(γk ) k=0
LDA collocation models. To the best of our knowledge, our Z YD T PT T
!
qdz Γ( z=1 αz )
Y Y
αz −1
paper presents the very first application of all three n-gram × θdz QT θdz dΘ
based topic models on Gigabyte collections, and a novel d=1 z=1 z=1 Γ(αz ) z=1
way to integrate n-gram based topic models into the lan- T QW T Y W QW
v=1 Γ(nzv + βv ) v=1 Γ(mzwv + δv )
Y Y
guage modeling framework for information retrieval tasks. ∝ PW PW
z=1 Γ( v=1 (nzv + βv )) z=1 w=1 Γ( v=1 (mzwv + δv ))
T W 1 D T
Appendix
Q Q
k=0 Γ(pzwk + γk ) z=1 Γ(qdz + αz )
Y Y Y
P 1 PT
A Gibbs Sampling Derivation for the Topical z=1 w=1 Γ( k=0 (pzwk + γk )) d=1 Γ( z=1 (qdz + αz ))

N -grams Model Using the chain rule and Γ(α) = (α − 1)Γ(α − 1), we can
obtain the conditional probability conveniently,
We begin with the joint distribution
(d) (d) (d) (d)
P (w, x, z|α, β, γ, δ). We can take advantage of con- P (zi , xi |w, z−i , x−i , α, β, γ, δ)
 (d) (d) (d) (d) (d) (d)
P (wi , zi , xi |w−i , z−i , x−i , α, β, γ, δ) [7] T. E. Dunning. Accurate methods for the statistics of
= (d) (d) (d) (d) surprise and coincidence. Computational Linguistics,
P (wi |w−i , z−i , x−i , α, β, γ, δ) 19(1):61–74, 1993.
∝ (γx(d) + pz(d) w(d) xi − 1)(αz(d) + qdz(d) − 1) [8] D. A. Evans, K. Ginther-Webster, M. Hart, R. G. Lefferts,
i i−1 i−1 i i
and I. A. Monarch. Automatic indexing using selective
β (d) +n (d) (d) −1
 w z w (d) NLP and first-order thesauri. In Proceedings of Intelligent
 PWi
 i i
if xi = 0 Multimedia Information Retrieval Systems and Management
(βv +n (d) )−1

 v=1 z v
× i
δ (d) +m (d) (d) (d) −1 (RIAO’91), pages 624–643, 1991.
w z w w


 PW i i i−1 i (d)
if xi = 1 [9] J. Fagan. The effectiveness of a nonsyntactic approach to

 v=1
(δv +m (d) (d) )−1
z w v
automatic phrase indexing for document retrieval. Journal
i i−1
of the American Society for Information Science, 40(2):115–
Or equivalently, 139, 1989.
[10] T. Griffiths, M. Steyvers, D. Blei, and J. Tenenbaum. Inte-
(d) (d) grating topics and syntax. In Advances in Neural Informa-
P (zi |w, z−i , x, α, β, γ, δ)
tion Processing Systems 17, 2005.
∝ (αz(d) + qdz(d) − 1) [11] J. Hodges, S. Yie, R. Reighart, and L. Boggess. An auto-
i i
mated system that assists in the generation of document in-
β (d) +n (d) (d) −1
 w z w (d) dexes. Natural Language Engineering, 2(2):137–160, 1996.

 PWi i i
if xi =0 [12] M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul.
(βv +n (d) )−1

 v=1 z v
× i
δ (d) +m (d) (d) (d) −1 An introduction to variational methods for graphical mod-
w z w w (d)
 PWi

 i i−1 i
if xi =1 els. In Proceedings of the NATO Advanced Study Institute

 (δv +m (d) (d) )−1 on Learning in graphical models, pages 105–161, 1998.
v=1 z w v
i i−1
[13] J. S. Justeson and S. M. Katz. Technical terminology: some
And, linguistic properties and an algorithm for identification in
text. Natural Language Engineering, 1:9–27, 1995.
(d) (d)
P (xi |w, z, x−i , α, β, γ, δ) [14] D. J. C. MacKay and L. Peto. A hierarchical Dirichlet lan-
guage model. Natural Language Engineering, 1(3):1–19,
∝ (γx(d) + pz(d) w(d) xi − 1) 1994.
i i−1 i−1
[15] C. Manning and H. Schutze. Foundations of Statistical Nat-
β (d) +n (d) (d) −1
 w z w (d) ural Language Processing. MIT Press, Cambridge, MA,

 PWi i i
if xi =0
(βv +n (d) )−1 1999.

 v=1 z v
× i
δ (d) +m (d) (d) (d) −1 [16] A. K. McCallum. Bow: A toolkit for statistical lan-
w z w w (d)
 PWi i i−1 i
if xi =1 guage modeling, text retrieval, classification and clustering.



 (δv +m (d) (d) )−1 http://www.cs.cmu.edu/ mccallum/bow, 1996.
v=1 z w v
i i−1
[17] T. Minka and J. Lafferty. Expectation-propagation for the
generative aspect model. In Proceedings of the 18th Confer-
References ence on Uncertainty in Artificial Intelligence, 2002.
[18] M. Mitra, C. Buckley, A. Singhal, and C. Cardie. An anal-
[1] C. Andrieu, N. de Freitas, A. Doucet, and M. Jordan. An ysis of statistical and syntactic phrases. In Proceedings
introduction to mcmc for machine learning. Machine Learn- of RIAO-97, 5th International Conference, pages 200–214,
ing, 50:5–43, 2003. Montreal, CA, 1997.
[2] D. M. Blei, A. Y. Ng, and M. J. Jordan. Latent Dirichlet [19] F. Smadja. Retrieving collocations from text: Xtract. Com-
allocation. Journal of Machine Learning Research, 3:993– putational Linguistics, 19:143–177, 1993.
1022, 2003. [20] M. Steyvers and T. Griffiths. Mat-
[3] C. Chemudugunta, P. Smyth, and M. Steyvers. Modeling lab topic modeling toolbox 1.3.
general and specific aspects of documents with a probabilis- http://psiexp.ss.uci.edu/research/programs data/toolbox.htm,
tic topic model. In Advances in Neural Information Process- 2005.
ing Systems 19, pages 241–248, 2007. [21] T. Strzalkowski. Natural language information retrieval.
[4] K. Church and W. Gale. Concordances for parallel text. In Information Processing and Management, 31(3):397–417,
Proceedings of the Seventh Annual Conference of the UW 1995.
[22] H. Wallach. Topic modeling: beyond bag-of-words. In Pro-
Centre for the New OED and Text Research, pages 40–62,
ceedings of the 23rd International Conference on Machine
1991.
Learning, 2006.
[5] K. Church and P. Hanks. Word association norms, mutual
[23] X. Wei and W. B. Croft. LDA-based document models for
information and lexicography. In Proceedings of the 27th
ad-hoc retrieval. In Proceedings of the 29th Annual Interna-
Annual Meeting of the Association for Computational Lin-
tional ACM SIGIR Conference on Research & Development
guistics (ACL), pages 76–83, 1989.
on Information Retrieval, 2006.
[6] K. W. Church, W. Gale, P. Hanks, and D. Hindle. Using [24] C. Zhai and J. Lafferty. A study of smoothing methods
statistics in lexical analysis. In Lexical Acquisition: Us- for language models applied to information retrieval. ACM
ing On-line Resources to Build a Lexicon, pages 115–164. Transactions on Information System, 22(2):179–214, 2004.
Lawrence Erlbaum, 1991.