Review of Available Implementations of the Latent Dirichlet Allocation

A part of my dissertation is based on the Latent Dirichlet Allocation Model and I have extensively searched for played with various LDA implementations.

Gibbs Sampling implementation of LDA in C++
The input format is basically a single text file that contains one line for each document. Each line contains the actual terms. I found this input format to be bulky. The code itself is very clean and easy to understand. Gibbs Sampling by itself is a little slow and nothing can be done about it.

Gibbs Sampling Implementation of LDA in Java
Written by the same folks who wrote the c++ implementation. Leaving the programming language aside everything else is kept same.

Variational Inference of LDA in Matlab and C
This is easy to use code that uses the input format as that of  SVMLight software, which is basically a text file with each line containing a sequence of tuples of the format : where the feature_id is the word_id based on a dictionary and count is the number of times it appears in the corpus. Implementation wise, I have one comment though. I was hoping that the algorithm would include estimation of the \eta parameter, the smoothing parameter on \beta.

MALLET toolbox
This is written in Java and uses plain text or SVM light format as input. It implements the Gibbs Sampling for LDA and allows for optimization of the hyper parameters \alpha and \eta after burn-in iterations. This allows us to exercise greater control over the impact of topics on the entire collection. Given that LDA itself is slow and that for estimation of hyper parameters we need to wait for burn-in number of iterations, I feel discouraged to use this tool.

Hybrid approach to LDA inference
This approach apparently uses both Variational and Gibbs Sampling based approach to learn the parameters. The author also presents a vanilla LDA implementation.

I will keep updating this post as and when I find more useful stuff.

Trying to revive the C3M algorithm

C3M is so much unlike other hierarchical  or k-means category of algorithms for clustering. The C3M (Cover-Coefficient Clustering Method) is a single-pass clustering algorithm built by researchers in IR (Information Retrieval). Hence, it is primarily meant for documents. Because IR researchers built this algorithm, they take advantage of the fact that term-document matrices are usually sparse and can be represented well by an inverted index. The main advantage of the algorithm is that it provides a way to estimate/compute the number of clusters given a document-term matrix.

 Here are some of the claims made by their paper " Concept and Effectiveness of the Cover Coefficient Based Clustering Methodology for Text Databases by Fazli Can and Esen OZkarahan".
a) Clusters are stable
b) Algorithm is independent of order of documents, hence, we will always a unique clusters
c) The memory overhead is really low
d) The algorithm distributes the documents evenly among cluster. In other words, it does not create fat clusters or singletons.

The algorithm starts of by examining the document-term matrix D of a collection of size m by n. From this it computes C ( m by m) and C' (n by n), where C[i,j] indicates the extent to which i covers j. The higher c[i,j] the higher the similarity between the two documents. Similarly, C' records how much one terms covers the other. From C and C' matrices it is possible to compute a document's seed power. The higher the seed power of a document, the higher the chance that it being selected to be a seed of a cluster.Once the cluster seeds are selected. For each document (not assigned yet) we find the closest cluster by simply examining c[i,j], where i corresponds to the unassigned document and j corresponds to each of the cluster seeds.

If m denotes the total number of documents, xd denotes the average number of words in each document and, tg denotes the average of documents in which a term appears, then the complexity of this clustering approch is O(xd X m X tg)


Creating the C matrix

initialize C[m,m] <- 0="0" p="p">for each document i
      for each term t_i in that document
                 Compute P(t_i) = D(i,t)/ sum_t {D(i,t)}
                 Get the inverted index for term t_i .. Lets call it inv(t_i)
                  compute p(d_j|inv(t_i)) for each document in the inverted list
                  for each document j in inv(t_i)
                               c[i,j] = c[i,j] + p(t_i)*p(d_j|inv(t_i))

Similarly one can compute c'

Compute number of clusters n_c = \sum_i c[i,i]

Computing Cluster seed power
for each document i
     P(i) = c[i,i]*(1-c[i,i])* sum_j  { d[i,j] c'[j,j] (1-c'[j,j])}

Pick the top n_c documents that have highest P(i) and set them as cluster seeds  {D_cluster_Seeds}

Assigning documents to cluster seeds
for each of the document i (that is not a cluster seed)
   assigned = argmax(j) {c[i,j] where j < {D_cluster_Seeds}}

Cluster Validity

This paper presents a unique way of gauging the cluster structure as it measures this in terms of the query. Given two cluster structures -one random assignment and second the cluster structure under test, a set of queries with the corresponding set of relevant documents, the cluster validity is computed as follows. Suppose a query has k relevant documents, then we compute the value $n_t$ and $n_tr$ corresponding to the test cluster structure and random clustering. The authors use $n_t$ or $n_tr$ to denote the number of target clusters. The target cluster is a cluster that contains at least 1 relevant document to the query. If the clustering is any good, then $n_t$ should be less than $n_tr$. The average of $n_t$ is computed with $n_tr$ over all the queries and may be additionally subject to significance testing.

Now let me explain how $n_t$ is computed. For a given query, the authors first find the size of the relevant set (from ground truth). Lets denote this by k. Given $n_c$ number of clusters, for each cluster, $P_i$ is computed. $P_i$ computes the probability that a cluster $C_i$ will be selected given that randomly k documents from the set of m documents were picked. There is a direct formula in the paper that computes this. Computing $P_1+P_2+...P_n_c$ yields $n_t$ for the test cluster. The procedure is repeated for the cluster structure obtained by random clustering.

Although it makes mathematical sense, I wonder what would be the actual number of target clusters for the queries based on the actual location of the relevant documents. I personally feel that this is a far better and more accurate representation of the reality. Of course, we can compare the number of target clusters with a random cluster structure or with another clustering algorithm.

Querying

Querying with different term weighting has been extensively covered in this paper and I will not be able to cover all of it here.

I am going to implement this algorithm and update this post with some results.

TREC tracks and their meanings: A high level overview

Confusion Track:

Study Impact of corruption on retrieval of known items. The corpus contains 55,600 documents in 3 different versions. First version is the true text and these second and third version caused by 5% and 20% degradation of the original documents. There are 49 queries for which retrievals are measured. The task to perform data cleaning in order to get MAP as close to that obtain with first version of the corpus.

Blog Track:

There are multiple tasks and sub-tasks in this track of TREC. These include blog distillation and then opinion polarity. There are about 100,000 blogs in this dataset and 50 queries for which opinion polarity was provided as ground truth. These opinions are categorized into (relevant, not relevant, negative, positive, mixed)

Enterprise Track:

The goal of this track is to study interactions within an organization mainly through email discussions, intranet pages and document repositories. W3C mailing lists were mined to study two main tasks: Email discussion search and Expert Search. In the email discussion search task, the email discussions are mined for opinion. The focus was topics for which different people had conflicting opinions. The second task (expert search) returns a ranking of users as candidates for experts on a topic. There were 198K emails discussions mined and 50 queries were used to evaluate the expert-search task. 

Entity Track:

The task here is to extract not just documents but documents related to the query. The target entity is specified by the user as a part of the query. The dataset used is a subset of the ClueWeb09 dataset containing 50 million pages. The very first year of this track, 20 queries were accessed. In subsequent years 50 more queries were added.

Genomics Track:

DNA and RNA sequences (genomes and proteomes) are indexed by the NCBI (National Center for BioTechnology Information) and each of these gene functions are linked to other publicly available medical datasets (as mentioned below) by means of locuslink database:

• Medline (Documenting the first discovery of that gene function)
• GenBank (containing nucleotide sequence)
• Online Mednelian Impact on Man (OMIM) (diseases these gene functions may cause). 

Locuslink also contains GeneRIF (Gene Reference Into Function). This links the gene function with an article in Medline along with a short textual description. These serve as psuedo relevance judgements for ad-hoc IR task

• The query is the short textual description for that gene function
• The medline documents linked is the pseudo- relevant set for that gene function

The dataset consists of 525K docs, 50 of these queries were used for training and 50 for testing.

Legal Track

This track was first started in 2006 by researchers at the Complex Document Information Processing at IIT Chicago and they called the track the IIT CDP version 1.0. The mining was carried out on the only publicly available legal documents released as a part of the Master Settlement Agreement. These legal documents contained lawsuits filed against tobacco companies and other health-related issues. These legal track documents were scanned and then OCRed (Optical Character Recognition) by team of researchers at Univ of Southern California creating a large (1.5TB) dataset . The IIT Chicago team of researchers extracted documents from this set amount to 7 million documents. A team of lawyers working for Sedona Conference created hypothetical complaints falling in the following 5 categories 1) investigation into a campaign 2) Consumer protection lawsuit 3) Product liability 4) insider trading 5) anti trust lawsuits. There are in all 43 queries created, for which the relevance judgments were populated by pooling initial results from 6 research teams.

More to come..

Randomized algorithm for Verification of Matrix Multiplication

Suppose you want to verify if AB = C and A is m by n and B is n by k then, the time taken for this is O(mnk + nk) = O(mnk)

What if you had a vector x, then ABx = Cx...  here x is a random vector.
x  is of dimensionality k by 1  and created by randomly sampling from a gaussian distribution.

Now the time taken to compute Bx is O(nk)  and is of dimentionaity n by 1 and time taken to compute ABx is O(mn). Similarly, time taken to compute Cx is O(mk)...

So the total time taken to verify is O(mn+nk+mk) and not O(mnk)

The hashing trick for a dynamically changing vocabulary

I recently learned about the "hashing" trick in Machine Learning. It is typically used to handle dynamically changing vocabulary in large-scale machine learning algorithms. With the hashing trick, we always have a "fixed" vocabulary. Only thing is what this vocabulary is, we dont know. The words are hashed into a M- length hash table, and no matter how many new words come in the hash contains all of these tables. Its amazing that Yahoo research is the company that came up with the idea and implemented a widely used open source software called the vowpal wabbit. Researchers who propose new online algorithms with a dynamically changing feature set implement their algorithm in vowpal Wabbit. I think there is also an effort to implement vowpal wabbit on top of hadoop.

It is indeed sad that a company like Yahoo which has been an innovator of so many cool ideas is under the weather. Hopefully Marissa Mayer will turn things around.

For more information on Vowpal Wabbit visit https://github.com/JohnLangford/vowpal_wabbit/wiki/Examples

Measuring Query Difficulty

The trail of this reading began with Sonia Haiduc's paper "On the Effect of the Query in IR-based Concept Location". A lot of the paper is a review of the recent research focus in IR "predicting query difficulty". I was surprised to see that this paper was accepted. There were no results, not even an explanation of how evaluating query difficulty is different for concept location compared to traditional IR. Nevertheless, there was a good amount of literature review that guided me to several other interesting papers. There are "predictors" as well as "estimators" of query quality. Predictors usually examine the content of the query alone and generate a score that represents the query difficulty. The estimators use the ranked list to generate a score. The evaluation technique for all the algorithms in the umbrella of query difficulty prediction goes as follows:
The predictor or the estimator gives out score for each query that is expected to have correlation with the Average Precision for that query. The query quality score is correlated with the AP over all the queries in the entire test collection and in order to be doubly sure, a statistical significance test is conducted to illustrate that the two distributions originated from the same original system (demonstrate high p-value).

In order to get a better idea of how the specificities of the predictor or estimator algorithm goes I referred to the highly cited paper " Predicting Query Performance, SIGIR 2002". This paper is output of the Bruce Croft group and lives up to its reputation. The paper discuses an clarity based score, which measures the separateness of the query from the collection model. The following formula measures the divergence  = \sum_w p(w|q) log_2(p(w|q)/p(w|coll)). The numerator measures the entropy of the query while the denominator the divergence from the collection model. the p(w|q) is the query model. The experimentation is extensive spanning multiple test collections and setting up quantitative proof for all the thresholds they use in their experiments.
  
"Query Difficulty, Robustness, and Selective Application of Query Expansion" published in Advances in Information Retrieval in 2004, was one of the first to come up with a "use" of measuring query difficulty. They employed a number of retrieval models and test collections for their study. Not only did they correlate query difficulty with the P@10, AP and so on, they used the "relevance judgements"  also to understand its correlation with query difficulty.

There has been some work in the area of "traceability link recovery" for dealing with difficult queries. The method employed is simple. For queries that show poor performance, one uses an web based search to mine documents that could be used for query reformulation. I wonder if this comes under the umbrella of multi-modal retrieval.

I think it is worthwhile to spend some using these metrics on my own datasets and isolating "difficult" queries ahead of time to aid analysis.

Handling duplicates in ranking documents for Retrieval Algorithms

I never paid attention to the ranking step of a retrieval algorithm. All I had to do was sort the scores. These scores are computed by using a similarity (or divergence) function to compare a query with all the documents in the collection. What I had overlooked was the possibility of scores being equal. How do you rank documents with similar scores? Does it have a great impact on retrieval performance? Turns out, the answer to the second question is YES. To give a simple example, consider 6 documents with the following scores,

doc no   1      2      3       4    5        6
scores 0.87 0.97 0.97 0.85 0.49 0.87

Simple ranking would give out the following output

doc no   1      2      3    4    5   6
rank       3     1      2    5    6   4

If doc 3 is the relevant document,  it is still considered to be at rank 2 as opposed to rank 1(where it actually should be since it scores as much as doc2). The Precision goes from 1.00 to 0.5 just because of this sort of ranking.

This wikipedia article summarizes on ways to handle this. It seems like a trivial concept but it has tremendously improved bug localization results on my iBUGS dataset.

For 291 bugs, I compute the retrieval performance by using the "standard competition" ranking (1 2 2 4) and the retrieval performance shot up from 0.14 to 0.21 with a p-value of 0. Thus the improvement is statistically significant.

Experience with Matlab's TMG

I have been playing with Matlab's TMG and here are my 2 cents from experience with the software

Pros: Easy to install, Easy to index a corpus and queries.
Cons: Proprietary code. Impossible to contribute modify or fix bugs in the code. Is not maintained well. Does not have any discussion forum where users and developers can communicate. Last citation was 2009

I was unable to even run some basic retrieval tasks due to bug in the code. norm2 does not work for sparse arrays and one needs to replace norm2 with normset, and I was unable to make the change because the code is protected and proprietary.

Vocabulary handling for software reuse

Vocabulary mismatch is even more of a pronounced problem when dealing with corpus made of source code. There are several tools used in the past and here are some of them that I will need to research and learn about

1) Soundex: Phonetic variations of the words are captured
2) Lexical affinity: A sliding window (grep-like) tool that calculates how close are two identifier names
3) Separate words using "_": counter_activity -> counter activity
4) Separate words using case sensitivity: LoadBuffer -> Load buffer

One could additionally use WORDNET and spelling correction or missing character handling to improve upon the existing techniques

Combining discriminative and Generative training

This blog is a continuation of the previous post Targeting discrimination as opposed to similarity. In model learning, given labeled data there is always a choice to make, discriminative or generative. There are pros and cons of either methods and usually a two-stage approach is used to combine the power of the two. I found a very recent paper, Multi-Conditional Learning published in AAAI 2006, on combining the power of the two at the time of learning. The likelihood function is now composed of the generative likelihood and the discriminative likelihood. This is possible only because we have labeled data. The discriminative-generative pair used for illustration is primarily the CRF-MRF. The MRF is used to capture topic co-occurrences. The word co-occurrences are captured by the latent topic model. However, by using a MCL regularizer (discriminative component) in the learning algorithm, the model being learnt is actually a combination of MRF and CRF, thereby combining the power of the two.The authors claim huge performance gains in document retrieval on the 20newsgroups dataset.

Review: IR application into software libraries: Concept graphs

I bumped upon this paper recently Source Code Retrieval using Conceptual Similarity published in 2004, RAIO. The main idea of the paper is to introduce concept graphs to be able to represent software code at two levels of granularity, structured and unstructured. Concept graphs enforce relationships between the variable names (unstructured information) based on the constructs of the programming language. Once the concept graphs are created, graph matching algorithms are used to find similar code segments. The baseline used is the Okapi IRS on the unstructured information in the code. They also present a combined approach where the scores obtained from Okapi and the Concept graphs are used to rank documents and queries (both are software segments). A corpus of size 2392 was used with a subset of 25 documents separated out as queries. In order to prove that the structure of the code plays an important role in matching (of code segments) these 25 documents were modified by performing transformation on the variable names etc. The results were reported using two measures: MMR and P@n n being the order of 5 (for this corpus)

Targetting discrimination as opposed to similarity

Clustering mechanism with data that is expected to follow continuous distributions use an objective function to measure the optimum clustering of the documents. Such an objective function is usually a ratio of two quantities : inter-cluster distance to intra-cluster distance. Such a ratio measures the power of the clustering algorithm to bring together similar data samples and separate apart the dissimilar data samples. Fortunately for Gaussian models, this works out into a nice clean equation. No wonder people LOVE the Gaussian model.

When we are dealing with discrete data, the most likely distribution is the multinomial distribution. To add more control over the behavior of the model one could use dirichlet priors. The document clustering approaches in the discrete domain merely use the EM or the gibbs sampling approach to fit data optimally to the discrete model (especially latent mixture model). There is no underlying objective function that says, this discrete (latent) model should also be able to optimally sepearte out one topic from the other. Thus one could end up with 2 topics generating the exact same set of words.

This is definitely something that is lacking in the EM algorithms for fitting discrete data....
Maybe there has been work done on this already. But I am yet to discover it

Multiplication of matrices in log domain

Given two matrices A and B, whose entries are specified in log. i.e. the ith row and jth column has log(aij). If you take the exponent of these values the numbers may just disappear (exp(-200) is approximately 0) or explode (exp(200) is approximately infinity).

So multiplying them by first taking the exponent of their entries is out of question. How to efficiently perform matrix multiplication in such cases. There are two pieces to the jigsaw puzzle.

log(a*b) = log(a)+ log(b)
log(a+b) ~ max(log(a),log(b)) + k* exp(-abs(log(a)-log(b)))
k = 0.77

the second formula is called the "Chad's approximation formula"

How to use these? Crank at your computer a little

Bayesian Unlearning

An interesting problem in Dynamic mixture model is to be able to see how we can accommodate unlearning and if it can be done by a 'particle-filtering' like on-line approach