Pre-meeting comment - Daniel

Focus Paper: Reading tea leaves: How humans interpret topic models. Chang et al. NIPS 2009
Related Paper: Evaluation Methods for Topic Models. Wallach et al. ICML 2009

This paper explores various intrinsic methods of evaluation for topic models, focusing on LDA. All of the methods are various ways of estimating the probability of held-out test documents given the model. The held-out documents are either entirely held out, or used in a document completion setting, where only the latter half of each test document is held out. For the completely held-out setting, they compare two commonly used methods, harmonic mean sampling and annealed importance sampling, to methods that had not previously been used for topic model evaluation, Chib-style estimation and left-to-right evaluation. For the document completion setting, they compare older methods, annealed importance sampling and estimated theta, to left-to-right evaluation. The methods are compared by seeing which assigns higher probabilities to the held-out data, as well as by looking at the variance and computational complexity of each method. The Chib-style estimation and left-to-right evaluation are determined to be the best. This method for comparing evaluation methods does not seem well-justified, and the authors do not go into any detail about why they used the procedures that they did.

Pre-meeting Dong

Pre-meeting (Dong Nguyen).
Related paper Automatic Evaluation of Topic Coherence, Newman et al.
Focus paper: Reading tea leaves: How humans interpret topic models, Chang et al.

I think the focus paper addressed an important topic. Topic models seem to be used a lot for visualization etc., thus it is important to be able to measure
how interpretable a topic is. I liked the way they evaluated,
although I'm wondering how sensitive their results are too the used inference methods/parameters.

My related paper essentially builds on the work by Chang et al. by proposing
automatic methods to measure topic coherence/interpretability.
They tried a bunch of external methods, using Wordnet, Wikipedia and Google
(a total of 15 different measures).
I like the range of methods they tried, but it would have been nice if they
had said some more regarding error analysis etc. Now I felt most of the paper
was about explaining all the different measures. They found that Wikipedia based method achieved very good results.
They used annotators to rate the topics on a 3-point scale. They view their upper bound as the inter-annotator agreement. It seems a bit strange that some of the methods, have an even higher score than that , and a lot of the methods are very close to the upperbound score. So I'm wondering if their comparison with the upper bound (which they use to conclude that their methods perform really well) makes sense.
In addition I wonder how well their methods work when the domains are very specific and not well covered by the Web/Wordnet/Wikipedia. It also wasn't clear to me also how they mapped terms to Wikipedia pages, which is not a trivial thing to do.

Post meeting comment - Dhananjay Kulkarni

Based on the concept of creating a metric space of clusterings, I wondered if there might be a way to use the motivation for adaboost - an ensemble of multiple weak learners can be used to create a strong learner.

What if the dimensions of this metric space is a set of weak learners, and the human observation is used to generate weights that create a decent clustering application? I don't have a particular example or application to illustrate this point, but perhaps somebody might want to help me out over here?

Pre-meeting post from Weisi Duan

I have read “A Topic Model for Word Sense Disambiguation” by Jordan Boyd-Graber, David Blei, and Xiaojin Zhu, appeared in EMNLP 2007. For the focus paper, one thing I feel that is missing is the inter-rater agreement, especially in such as situation where there are a group of not highly reliable raters. The agreement might be calculated using measures such as Fleiss’ Kappa. Another issue I feel is that they could also address the problem of semantic similar topics (topics that have similar distributions), this problem results as that the users can not disambiguate the intruder from the intended topic words (as the authors suggested). In real semantic applications, people could wish to get rid of such semantic duplicated topics, and could do so if the similarity between two topics are known.

As the author suggested that the task specific evaluation measures should be preferred over perplexity, I decided to read the paper above. The Boy-Graber 2007 paper proposes a hierarchical bayesian model that integrates two bayesian models: LDA and WordNet-Walk. In a graphical model view, the model basically inserts into the LDA model a path node between the topic node and the word node. The state space of the node spans all the paths from the root synset to the a specific synset that could generate the observed word in the WordNet. The training is done through Gibbs Sampling and during inference, the lowest synset node of the path with max probability coming out from the assigned topic is assigned as the sense to the target word. The evaluation is done on different topic numbers and the results turn out to be inferior to the state-of-art. Besides the issues raised in the error analysis, I feel the model also does not address the path length issue--even if the parameters estimated for each edge on path is big, if the path is much longer than the competing paths, the model would not be able to pick the correct sense confidently. Being bayesian, the model can be integrated into a bigger model, as the authors claimed, however, as with the Haghighi paper, the model itself is complex for inference, when combined into a more complex model, the inference is going to much complex and how good the approximation could be is unknown. In general, this paper provides an elegant generative model and shows that more knowledge and sense specific features are needed in order to do better in WSD.

Reading for 3/24/11: Chang et al., NIPS 2009

Reading tea leaves:  How humans interpret topic models

Author:  Jonathan Chang, Jordan Boyd-Graber, Sean Gerrish, Chong Wang, and David Blei

Venue:  NIPS 2009

Leader:  Weisi Duan

Request:  When you post to the blog, please include:

1. Your name 
2. Which focus paper this post relates to
3. Whether this is the pre-meeting review or the post-meeting summary

Reminders:

• Leave a comment on this post (non-anonymously) giving the details of the related paper you will read (include a URL), by Monday, March 21.
• Post your commentary (a paragraph) as a new blog post, by Wednesday, March 23.

I read

Comparing clusterings: An information based distance. Meila, M. 2007. Journal of Multivariate Analysis

www.stat.washington.edu/mmp/Papers/compare-jmva-revised.ps

This paper provides a different approach to deriving the distance metric used to compare clusterings in the focus paper. The goal of this metric, called variation of information (VI), is to be intuitive as well as to possess desirable mathematical characteristics. From a variety of axioms, the following definition is derived VI(C,C')=H(C|C')+H(C'|C), where H denotes the conditional entropy. This function is a true metric, which makes possible more types of reasoning about the space of clusterings. VI is not directly dependent on dataset size, so distances are comparable between different datasets. The author proves that VI is the only function that satisfies all the desired properties, although some of these properties are somewhat nonintuitive, relating to the way the metric interacts with combinations of clusters. The principal advantage of this metric over others is the fact that it is comparable across datasets and experimental conditions without rescaling, which is generally not mathematically justified.

Pre-Meeting Review - Alan

This week I read "Combining Multiple Weak Clusters" by Topchy, Jain, and Punch from Proceedings IEEE Intl. Conf. on Data Mining 2003. http://www.cse.msu.edu/prip/Files/topchy_combination.pdf

This paper presented several interesting points on the topic. First it sets up a formal definition of the combination clustering problem, which basically says given some set of clusterings for a set of data, find a cluster which is some combination of one or more of those sets that yields a "better" cluster. The paper formalizes this combination problem basically into a clustering problem of itself, where the critical aspect of the combination problem is the consensus function that defines how different clusters are combined. Then there follows a proof of relating this to a median partitioning problem and intra-class variance criterion. Seven different consensus functions are studied, where evaluation is done by measuring the mis-assignment rate of the consensus partition (the true known number of clusters is made available). A second point of the paper focuses on combining weak clustering algorithms, specifically clustering (via k-means) the data after projection into a lower dimension, or splitting the data randomly via hyperplanes. Experiments are combined with the consensus functions and applied in different dimensions for different values of k.

The idea in this paper seems pretty intuitive which probably explains why it was published some time ago. Theoretically it makes sense that you should be able form a more optimal cluster by combining multiple clusterings of a set of data, but because you could also telescope the argument, the practicality and marginal benefits seem limited in significance.

-Alan