papers: Estimation of Dirichlet Distribution Parameters

Recently, I am interested in apply Pachinko Allocation topic models to the object recognition problems. Mixtures of Hierarchical Topics with Pachinko Allocation, ICML 2007 mentioned several methods in training the hPAM model, and here are the related papers: 

• Gibbs EM: 
• An introduction to MCMC for machine learning, Machine Learning 2003
• implementations of the Monte Carlo EM Algorithm, 2001
  
• fixed point iteration method for estimating the Dirichlet parameters: 
• Estimating a Dirichlet distribution, Minka 2000, and code
• Maximum Likelihood Estimation of Dirichlet Distribution Parameters by Jonathan Huang

papers: syntax and topic model

Syntactic constraint is an important ingredient in NLP. At the beginning, topic models, such as LDA, assume bag-of-word model and thus ignore the syntax. Later on, this constraint is added to the topic model to improve the modeling power. Here are a few papers regarding this issue:

• Integrating topics and syntax, NIPS 2005
• Style and Topic Language Model Adaptation Using HMM-LDA, EMNLP 2006
• Hidden Topic Markov Models, AISTATS 2007, presentation video
  
• Topic Modeling: Beyond Bag-of-Words, ICML 2006, slides
• Syntactic Topic Models, NIPS 2008, supplement materials
• Bayesian Modeling of Dependency Trees Using Hierarchical Pitman-Yor Priors, In Proceedings of the Workshop on Prior Knowledge for Text and language (held in conjunction with ICML/UAI/COLT), 2008
• Topical N-grams: Phrase and Topic Discovery, with an Application to Information Retrieval, ICML 2007, technical report

paper: Rethinking LDA: Why Priors Matter

Rethinking LDA: Why Priors Matter, Hanna M. Wallach David Mimno Andrew McCallum, NIPS 2009

Abstract:


Implementations of topic models typically use symmetric Dirichlet priors with fixed concentration parameters, with the implicit assumption that such “smoothing parameters” have little practical effect. In this paper, we explore several classes of structured priors for topic models. We find that an asymmetric Dirichlet prior over the document–topic distributions has substantial advantages over a symmetric prior, while an asymmetric prior over the topic–word distributions provides no real benefit. Approximation of this prior structure through simple, efficient hyperparameter optimization steps is sufficient to achieve these performance gains. The prior structure we advocate substantially increases the robustness of topic models to variations in the number of topics and to the highly skewed word frequency distributions common in natural language. Since this prior structure can be implemented using efficient algorithms that add negligible cost beyond standard inference techniques, we recommend it as a new standard for topic modeling.

paper: On Smoothing and Inference for Topic Models

On Smoothing and Inference for Topic Models, UAI 2009
abstract:

Latent Dirichlet analysis, or topic modeling, is a flexible latent variable framework for modeling high-dimensional sparse count data. Various learning algorithms have been developed in recent years, including collapsed Gibbs sampling, variational inference, and maximum a posteriori estimation, and this variety motivates the need for careful empirical comparisons. In this paper, we highlight the close connections between these approaches. We find that the main differences are attributable to the amount of smoothing applied to the counts. When the hyperparameters are optimized, the differences in performance among the algorithms diminish significantly. The ability of these algorithms to achieve solutions of comparable accuracy gives us the freedom to select computationally efficient approaches. Using the insights gained from this comparative study, we show how accurate topic models can be learned in several seconds on text corpora with thousands of documents.

fast and parallel Gibbs sampling for LDA

Gibbs sampling for LDA is very simple to understand and implement, especially the collapsed Gibbs sampling. But one drawbacks of GS is its complexity is linear to the number of word tokens. This problem is even more serious when we apply LDA-based approaches to computer vision problems where we use visual words in images to replace words in documents. To maximize our chance to detect the object in an image, we need large number of visual word tokens. It is more and more popular to extract features at dense regular grids over images, and to one extreme, someone extract features at every pixel with several scales. Also we often need to extract several types of features and hope them to be complementary to each other since we usually do not which type of feature is more useful for a particular object category. Combine these factors together, there are often more than 10k ~ 50k word tokens per image extracted. For Gibbs sampling, this is a nightmare!

So a fast Gibbs sampling or parallel Gibbs sampling are absolutely rescues. There are two such papers recently, with published codes (that is great!):

PLDA: Parallel Latent Dirichlet Allocation for Large-scale Applications by Wang Yi et al at Google, code

Fast Collapsed Gibbs Sampling For Latent Dirichlet Allocation at UCI, code

here is a comment from LingPipe's blog:

Porteous et al. (2008) Fast Collapsed Gibbs Sampling for Latent Dirichlet Allocation

Another paper related to topic model inference in large scale corpus is

Efficient Methods for Topic Model Inference on Streaming Document Collections

A clever way to derive the collapsed Gibbs sampling for LDA

Inspired by Tom Griffiths technical report, Gibbs Sampling in the Generative Model of Latent Dirichlet Allocation, I derive the collapsed Gibbs sampling for LDA by myself using the tricks in Tom's report. These tricks are universally applicable to other topic models:

• simplify the conditional property by employing Bayes theorem and
  d-separation property
• derive the results of conditional probability directly from the result of
  the predictive likelihood of Dirichlet/multinomial distribution
  

There is no lengthy and complex computation like those in Wang Yi's note or Gregor Heinrich's note. It is easy to understand and has intuitive explanation for the formulas involved. I wrote up a report for my derivation, as a complementary to Tom's note:
Derivation of Collapsed Gibbs Sampling for LDA

paper: DeltaLDA

DeltaLDA is a modification of the Latent Dirichlet Allocation (LDA) model which uses two different topic mixing weight priors to jointly model two corpora with a shared set of topics, where one topic mixing weight prior to model the normal pattern and the other for the abnormal pattern.
The graphical model:

An illustration of topic mixture weights in two scenarios:

This looks like quite similar to the Adapted Vocabularies for Generic Visual Categorization, ECCV 2006 in the way they split the topic/vocabulary into two sets, though there are fundamental difference in their underneath mechanism.

Author-topic model and transformed LDA

Latent Dirichlet Allocation (LDA) is essentially a generative model for document analysis rather than classification, and it is an unsupervised rather than supervised learning algorithm. Given a new document, the output of LDA is the topic proportion instead of document category. So LDA can not be directly used for classification.

Author-topic model (ATM), on the other hand, can be used in classification, as long as we view the author as the category label.

Comparison between the above two models can be summarized as follows, where the figures are from the UAI paper by M. Rosen-Zvi, T. Griffiths, M. Steyvers, P. Smyth, 2004:

LDA	ATM
generative process: choose for each of the  words in document d choose choose	generative process: for each of the  words in document d choose an author x from  , the author set of document d following a uniform distribution choose choose

Notice the most significant difference in ATM compared to LDA is that the topic mixture weight is not generated for each document; rather, there are finite number of possible topics mixture weights, which is specified by the author information in each document.

For document classification, if we view the author as the class label, and let is a scalar, the ATM model can be directly applied.

My interest on the ATM model is due to Sudderth's transformed LDA model, which reduces to an ATM when ignore the spatial transformation (see the part inside the big red square).

a good review article for LDA

I happened to find a review article for LDA and its application for text, vision and music.
The link is Latent Dirichlet Allocation for Text, Images, and Music
and the slides is here

They are worth to read carefully.

papers: extend topic model to deal with temporal dependency

Using topic models to analyze the tread and change of topics along the time line in a document corpus is definitely a cool idea. It has plenty of potentials in video analysis, human action understanding, etc. The following are a few papers related to this idea:

• Dynamic Topic Models, ICML 2006
• Continuous Time Dynamic Topic Models, UAI 2008
• Hidden Topic Markov Models, AISTATS 2007

non-parametric models:

• an HDP-HMM model is described in Yee Whye Teh's HDP paper
• An HDP-HMM for Systems with State Persistence, ICML 2008
• Infinite Hierarchical Hidden Markov Models. K. Heller, Y.W. Teh and D. Gorur. AISTATS 2009

Here is a good discussion on several infinite HMM:
a blog by Jurgen Van Gael, discussing several infinite HMM

A Matlab demo of collapsed Gibbs sampling for learning LDA

The equations of the conditional posterior is based on the technical note by Yi Wang,
"Gibbs Sampling and Latent Diriclet Allocation: The Gritty Details"

I have summarized a step-by-step illustration of the derivation of this method in a previous post:
A step-by-step deriviation of collapsed Gibbs sampling of LDA

The codes can be downloaded from my SkyDrive

A step-by-step deriviation of collapsed Gibbs sampling of LDA

How we can derive the collapsed Gibbs sampling procedure for LDA from scratch: a step by step illustration. This is based on Wang Yi's tech report. 

1. To fully describe a LDA, we need to solve the following three problems:

1. latent variables  for each word , where  indexes a word from the whole training set, i.e., 
2. parameters , where specifies the topic distribution for document d=m
3. parameter and , where  specifies the word distribution for topic z = k

2. Given the training data set, we only need to know the latent variables , because the two parameters can be considered as statistics of the association between the observed w and the corresponding z.
3. Problem I can not be solved deterministically due to the noise in the data. So a practical solution is to estimate .
4. Directly estimate is difficult due to the complex form of distribution in LDA. Gibbs sampling solve this problem by approximating with samples from after the burn-in period, i.e., when the Markov chain is stationary.
5. To draw samples from , we need not know the exact form of this distribution. All we need is a function . The rest thing we need to do is to derive such a function.
6. The conditional distribution be derived from the joint distribution . The second equality comes from the fact that only depends on .
7. The denominator has the similar form of the numerator. So we need to derive the form of
8. can derived by using the conditional independent property of LDA:
9. The two distributions in step 8 are both multinomial distributions with Dirichlet conjugate prior. So their derivations are also similar. I summarize the key steps in their derivations and compare them side by side to emphasize these similarities.
   

Dirichlet prior	Dirichlet prior

10. Substitute the results in step 9 to step 8 and then to step 6, we can express the conditional distribution as functions of the co-occurrence of word and topic , and the co-occurrence of topic and document, , and the hyperparameter, and thus we draw samples from therefrom.
    
11. The procedure of the Gibbs sampling for LDA learning can be then summarized in a figure from Wang Yi's tech report:
    

This sampling scheme integrates out the model parameters , and this strategy is called "collapsed" Gibbs sampling.