Search Logs as Information Footprints: Supporting Guided Navigation for Exploratory Search

by Xuanhui Wang, Bin Tan, Azadeh Shakery, ChengXiang Zhai

This is a paper on building a exploration interface based on a clustering algorithm (star clustering), that can arrange search queries according to the similarities of the search queries into tree structure. Then the material is shown to the users in a tree structured interface, incorporating search utility.

It's quite similar to what we are doing and may be I will develop another parallel clustering algorithm based on affinity propagation. But let's first scan the result of star clustering.

Maximum Margin Clustering

by Linli Xu, James Neufeld, Bryce Larson and Dale Schuurmas

This paper is interesting in formulating a clustering problem as a convex optimization problem. Its framework is not brand new but the idea is very enlightening for a current project. referring to maximum margin method, everyone knows how SVM is modelled with a quadratic programming problem with linear constraints. In clustering, we are not interested in the parametrized separation boundary but in the partition of samples that maximizes the boundary. Then the problem turns out to be an integer optimization problem, which is often NP-hard.

The key idea is to use the out product, e.g. the kernel matrix of the assignment matrixM = y y^\top in the dual formulation of soft-margin SVM. And another interesting finding is that instead of using non-convex constraint \mathrm{rank}(M) = 1, they use three linear constraints:

• M encodes equivalent class information, i.e. transitive M_{i, k} \geq M_{i, j} + M_{j, k} - 1, reflexive M_{i,i} = 1 and symmetric M_{i, j} = M_{j, i};
• M has at most 2 equivalent classes, i.e. M_{j, k} \geq - M_{i, j} - M_{i, k} - 1;
• M has at least 2 equivalent classes, \sum_i M_{i, j} \leq N - 2.

Then the problem becomes a SDP. It might not be easy to extend the idea to multi-clustering.

Discriminative k-Metrics

by Arthur Szlam and Guillermo Sapiro

This paper tells us about an old clustering technique called k q-flats. It can be regarded as a generalization of k-means algorithm but we find a q-dimensional space to project onto instead of a centroid for each cluster,

\sum_{j = 1}^K \sum_{x \in K_j} \| x - P_{F_j} x \|^2

This can be solved with k-means-like (EM-like) algorithms. Basically if we want to apply it to classification problems, we may train a k q-flats for each class but this model lacks discriminative power.

But this can be solved in a natural way

\sum_{i = 1}^c\sum_{j = 1}^K \left( \sum_{x \in K_{i, j}}g_1(\| F_{i, j}^\top x \|^2) + \sum_{x \not \in C_i} g_2(\| F_{i, j}^\top x\|^2)\right)

A little difference is the optimization has to be done with gradient. The selected g_i are Hinge-like loss funtions and the derivatives are simple piecewise constant functions.

Information Theoretic Measures for Clustering Comparisons: Is a Correction for Chance Nessary?

by Nguyen Xuan Vinh, Julien Epps and James Bailey

One problem in clustering is how to measure two clustering result. E.g. given two clustering results, which one is more closed to the true clustering?

There are many analytical methods, including Rand Index (RI) and Adjusted Rand Index (ARI). They are based on contingency table. Although RI could be useful since it is 1 iff the two clustering are identical and 0 when no pair are in the same cluster, it can not extinguish a random partition with a ``good clustering''.

To correct this (why it is called correction for chance), ARI is proposed. Another class comes from information theory. They use the mutual information of proportion of two clustering (each clustering's proportion is a density, therefore the mutual information is the common information in the two clustering). As we know we can create a distance based on entropy D(p, q) = H(p, q) - I(p, q) = H(p) + H(q) - 2 I(p, q) or its normalized version \mathrm{NMI}(p, q) = \frac{I(p, q)}{\sqrt{H(p) H(q)}}.

The authors proposed a corrected-for-chance version based on information method and from their experiments, we may find it works pretty well. Their criterion is

\mathrm{AMI}(U, V) = \frac{I(U, V) - \mathbb{E}( I(M) \mid a, b)}{\sqrt{H(U) H(V)} - \mathbb{E}(I(M) \mid a, b)}

or

\mathrm{AVI} = \frac{2 I(U, V) - 2 \mathbb{E}(I(M) \mid a, b)}{H(U) + H(V) - 2 \mathbb{E}(I(M) \mid a, b)}

where \mathbb{E}(I(M) \mid a, b) is computed from the contingency table.

The author provided examples where the correction is necessary. Esp. when samples in each cluster is few.

K-means Clustering via Principal Component Analysis

by Cris Ding and Xiaofeng He

Th most important result of this paper is that principal components are the continuous solutions to the discrete cluster membership indicators for K-means clustering and the subspace spanned by the cluster centroids are given by the spectral expansion of the data covariance matrix truncated at K-1 terms.

I'd like to say their discovery is very similar to that of normalized cut and the spectral expansion of Laplacian matrix. Let

J_K = \sum_{k = 1}^K \sum_{i \in C_k} \|x_i - m_k \|^2

be the objective of K-means clustering,

d(C_k, C_l) = \sum_{i \in C_k} \sum_{j \in C_l} \| x_i - x_j \|^2

be the distance between two clusters. It can be shown that

J_K = N \bar{y}^2 - \frac{1}{2} J_D,

where in 2-way clustering case

J_D = \frac{N_1 N_2}{N} \left( 2 \frac{d(C_1, C_2)}{N_1 N_2} - \frac{d(C_1, C_1)}{N_1^2} - \frac{d(C_2, C_2)}{N_2^2}\right).

Further we have

\frac{d(C_1, C_2)}{N_1 N_2} = \frac{d(C_1, C_1)}{N_1^2} + \frac{d(C_2, C_2)}{N_2^2} + (m_1 - m_2)^2.

The important theorem they proved says in 2-way clustering, the continuous solution is given by the leading principal components, those positive in one cluster and negative in the other. The optimal K-means solution in this case can be bounded with the leading spectrum,

n \bar{y}^2 - \lamnda_1 \leq J_{2} \leq n \bar{y}^2.

If we create a fully connected graph with each weight \frac{1}{N}, the linearization of the N-cut algorithm is PCA and the N-cut is simply K-means, is it right? The difference is PCA is done in the feature space and spectral clustering employs the embedding space Laplacian eigenmaps learns.

For K-way clustering, we have similar results. But unlike 2-way clustering, we can not interpret the PC in a similar way. Maybe the matting paper has better interpretation. Their second result is about the centroids.

This result has several implications. Spectral clustering is done in the embedding space learned by Laplacian eigenmap; PCA/K-means is done in the feature space; KPCA/Kernel K-means is done in the kernel-induced space. So if we considering the unsupervised KDR idea, can we find a similar interpretation such as clustering?

A Dependence Maximaization View of Clustering

by Le Song, Alex Smola, Arthur Gretton and Karsten M. Borgwardt

HSIC is an upper bound of the COCO which in theory has been proved to be equivalent to independence. Therefore HSIC can be used as an independence test. However, as an upper bound, it might not be suitable if we want to maximize the dependence of r.v.s IMHO. So the motivation of using HSIC for this purpose (clustering) is still vague.

For clustering, we maximize

\tr HK_xH K_y

for making features and labels dependent. So we have to find a kernel for the discrete variable y: delta kernel; or the kernel in the paper,

\Pi A \Pi^\top

where A is the Gram matrix for different clusters and \Pi is the assignment matrix. The paper also consider other kernels, relating this algorithm with kernel PCA (maybe kernel k-means also?).

The optimization is quite difficult as other clustering algorithms. It initialize an assignment matrix randomly and repeat updating the assignment matrix until it converges. We loop by the samples, finding the best assignment that maximizes the HSIC. Please notice the matrix A will be updated when the assignment matrix is updated. Like k-means, each sample has the same weight and A is simply a diagonal matrix with the inverse of number of samples in this cluster. Another choice generalizes the weights. This leads to a family of clustering algorithms by choosing A.

Maybe it's worth considering about the designing idea more carefully.

Hierarchical Dirichlet Processes

by Yee Whye Teh, Michael I. Jordan, Matthew J. Beal and David Blei

This paper is relevant to hierarchical modeling of MoE (hence related to HMoE). The DP extension for mixture model has been studied in this paper (with variational approximation methods) too. This paper only use Monte Carlo methods for inference (instead of approximation algorithms). They simply introduce one DP prior for parameters of the model that generates the data and another DP prior for the generation of groups. In one word,

G_0 \mid \gamma, H \sim \mathrm{DP}( \gamma, H ), G_j \mid \alpha_0, G_0 \sim \mathrm{DP}( \alpha_0, G_0), \theta_{ji} \sim G_j, x_{ji} \sim F(\theta_{ji}).

Their idea of DP is implemented with SBP (as in this paper). However, we can only observe x_i. For a learning problem we must find a proper settings for \gamma and \alpha_0. For inference, we must get the posterior distribution of two DPs. Please notice for a DP MoE, the base distribution of the DP is on the parameter space; now in HDP, the base distribution of the intermediate DP is a random measure, which is the top DP. Therefore the base distribution of the top DP is on the parameter space: the sampling from the top DP results in \sum_{k = 1}^K \frac{m_k}{m + \gamma}\delta_{\phi_k} + \frac{\gamma}{m + \gamma} H where m_k is the number of samples with \phi_k values and \phi_k are drawn from H, m=\sum_{k=1}^K m_k; the intermediate DP put these samples \theta_i in groups according to \sum_{t = 1}^T \frac{n_t}{i-1 + \alpha_0} \delta_{\psi_t} + \frac{\alpha_0}{i-1 + \alpha_0} G_0, where n_t is the number of samples in this group and T is the number of groups.

Now we come to the details:

• The SBP generates a set of v_i, \pi_i and \theta_i in the following way,

  v_i \sim \mathrm{Beta}(1, \alpha), \quad \pi_i = v_i \prod_{k = 1}^{i - 1}(1 - v_i), \quad \theta_i \sim G, \quad \Pr(\theta = \theta_i) = \pi_i

  This is equivalent to a DP whose parameter is \alpha and G. Then we may generate the data according to this.
• The HDP can be formulated as a variant of CRP, Chinese restaurant franchise: a customer chooses a dish (being served or not) and sits at a table (serving the dish or a new one). We can dormulate the generation as follows: a customer \theta_i comes into the restaurant and will sit at a table according to the intermediate DP and asks for a dish (if it is a new table) according to the top DP.
• For inference, we use SBP formulation and calculate the posterior of the hidden r.v.s. Ad we may see in the SBP formulation, we need an indicator (multinomial distribution) for one DP. The sampling is done with Gibbs sampler.
• It can be used for enhancing LDA (latent Dirichlet allocation) and HMM.
  

Implicit Mixtures of Restricted Boltzmann Machines

by Vinod Nair and Geoffrey Hinton

This is quite simple extension. It employs a three-order RBM instead of a mixture of RBM (mainly due to the complexity of training RBM). Usually we use v for input, h for hidden neurons. Now add another z for clustering. And v and h are binomial while z is actually a multinomial r.v. (so that it corresponds to the clustering index). This model can be trained with CD. We know given z and h the sampling of v is simple. The only thing we need to consider is how to sample h and z given v. This is still easy. One way is to find z first (well it has a number of configurations linear with the number of clusters, instead of exponential). By marginalize h, we get the free energy for each z. Then a softmax function (or just a normalization of the probability) will tell us the distribution of z. Then we can sample h.

Therefore, the three-order RBM is trained with CD. They address a problem of the training. One RBM might be too strong and others won't be chosen forever. They use a technique from annealing. By dividing the free energy with a temperature T (first high later getting smaller), we might avoid this problem.

Clustering by Passing Messages Between Data Points

by Brendan J. Fray and Delbert Dueck

It's an interesting paper about clustering. The technique they employed is affinity propagation, believed to be an example of belief propagation. It has several important features: it identifies exemplars in the samples instead of find a mean/center directly; when the similarity matrix is sparse, the algorithm works fast since it is a linear algorithm w.r.t. the number of similarity values s(i, k); instead of choosing the number of exemplars, the user is only required to set a value for s(k, k) which may influence the number of exemplars (the larger the value is the more exmplars are).

The iterative algorithm is very simple. Two matrices are introduced to show how well the sample k is as the exemplar of sample i in the opinion of sample i or k, i.e. responsibility r(i, k) and availability a(i, k). The updating rule for responsibility is

r( i, k ) <- s( i, k ) - max { a( i, j ) + s( i, j) | j <> k}.

The initial value of availability is 0 (later it is nonpositive). The maximal sum similarity and availability indicates the sample which is similar while thinking itself works best as the exemplar of sample i. Therefore the difference of s( i, k) and the sum shows the evidence sample i thinks sample k is his exemplar---evidence based on the observation of availability and similarity. The updating rule for availability is

a( i, k ) <- min { 0, r( k, k ) + sum { max{ 0, r( j, k) | j <> i, k } } }

As you might see here, the availability is nonpositive (due to the min function). The sum only includes those samples with positive responsibility (namely those samples still regard sample k as a possible exemplar). Therefore the sum with r( k, k) shows the availability of sample k for sample i, since it is a negative value when r( k, k) is negative and few samples take sample k as the exemplar---namely the evidence sample k holds based on its observation of other samples.

After the affinity propagation converges, there are two ways of determining whether a sample is the exemplar: one chooses those samples with r( k, k ) + a( k, k ) > 0; the other chooses those with r( k, k ) + a( k, k ) > r( k, j ) + a( k, j ) satisfied for all j <> k.

One important thing about the algorithm is damping. I haven't explored this part carefully but I do encounter this technique quite frequently. Actually in the training of SRBM and BP with momentum, similar techniques exist. The convex combination of the proposed updating values and the old ones from last update ensures the convergence (why?).

The science paper includes 3 experiments, on facial images, bioinformatic data and a text data of air lines, demonstrating the effectiveness of the algorithm. It's really amazing how well it works. How did they discover this simple but useful technique? This algorithm is designed from (loopy) belief propagation on an elaborate factor graph. I am not familiar with this and have to explore this ASAP.

Here is the important reference site from PSI group.

Spectral Clustering with Inconsistent Advice

by Tom Coleman, James Saunderson and Anthony Wirth

This paper is about semi-supervised clustering. The two main algorithms are spectral clustering and 2-correlation clustering problem (2CC). The main technique used here is SDP relaxation, which is very interesting.

The basic idea of SDP relaxation: Usually a combinatoric optimization problem results in a minimization of a quadratic form, where the variables are 0-1. The relaxation allows the variables to take real values. Then the optimization could be turned into a SDP problem by exploiting the trace equation: tr X^T S X = tr S G, where G = X X^T. With this formulation of the original problem G would substitute X. We could derive new optimization in SDP form and later transform it back to the original problem which can be efficiently solved by eigen decomposition.

It is famous that spectral clustering does the relaxation part and simplifies the NP-hard problem into an eigenvalue problem. Somehow, given consistent advice, we could solve the semi-supervised learning problem in a subspace that accords with the advice. But for inconsistent advice, it would be infeasible to apply the technique.

Several solutions are proposed in this paper. One is simple enough. 2CC could resolve the inconsistancies, which reenables the usage of subspace method with spectral clustering.

The other two ideas exploit SDP relaxation. The 2CC optimization could be relaxed in the same way as spectral clustering, resulting in a SDP problem. Combining the two SDP, optimizing over the clustering and putting 2CC in the constraints by limiting the upper bound, we get the SDP formulation of the problem. The imposed constraint in the spectral form turns out to be the subspace constraint of a block of advice graph. Compared with the original subspace method, it's similar (but it's blockwise and the eigen vectors of another matrix.) However this method doesn't yield a flexible model that could vary the importance of the advice. By multiplying a scalar (>1), and searching in a larger space (spanned by eigen vectors of the smallest eigen value multiplied by the scalar), the relaxation is done.

I think SDP might be really something useful in the spectrum related algorithms. Graph-related algorithms and similar ideas might all benefit from the idea.

An Investigation of Computational and Informational Limits in Gaussian Mixture Clustering

by Nathan Srebro, Gregory Shakhnarovich and Sam Roweis

I thought it was about the GMM ability in density estimation. Somehow it wasn't. I am not familiar with the literature on GMM clustering ability though I know it is trained with EM algorithms which is usu. the typical example for general EM algorithm.

They put the whole in under very restricted conditions where theoretical analysis is feasible. They assume each Gaussian has equal probability and the Gaussians have a unified scalar diagonal co-variance matrix. They list several important results on the necessary sample size when the training of GMM will lead to correct clustering results. There are several factors, the sample size N, the separation s, the number of clusters k and the dimension d. Here they further assume the covirance matrix is the identity matrix and hence only s is to be considered instead of s/σ.

They mention several tips for training with EM:

• PCA will help cluster with GMM. The algorithm is to project data into a (k-1)-D subspace where EM is applied to train a model that tells for each sample its probability of each cluster, which is to substitute the corresponding values in the EM training in the original space. This kind of cascaded EM will improve clustering results.
• They use a prune strategy, which sets a possible larger k', which is O(k log k). Then by merging near clusters, we get the final clustering result.

Their main result is they set up a procedure that illustrates three phases of the training of the GMM w.r.t. sample size N:

• Given too limited data, the MLE won't yield a good clustering (a wrong one). The EM will not find the MLE and results in a model that is unstable. This is Random Phase.
• Given more data, although EM still gives no MLE, MLE does correspond to a good clustering and hence is what we desire. This phase is Gap Phase.
• Given enough data, EM will get MLE which is the one we desire. This is Success Phase.

They develop an approximation of the sample size where the phase transitions take place. With these they could suggest when the gap exists.

The difficulty is how we can judge the gap phase for a real data set. And we have to extend their results to more general cases. I doubt most of the time, we are dealing with random phase and gap phase :-(

A New Approach to Data Driven Clustering

by Arik Azran, Zoubin Ghahramani

Well, on seeing Ghahramani, I guess it's no easy job @@ At first I was curious why their starting point resembles a lot from the paper on diffusion map. But soon I knew I was wrong. The first author is a Ph.D. student whose advisor is the second author. I wonder when I can publish a paper like he did in the top conferences. Sigh~ Maybe never.

Like diffusion map, they show us a Markov random walk model on a graph of samples. Then they notice the similarity of distributions starting at each sample can help clustering. They propose a clustering algorithm analogous to K-means(the proposed version minimizes KL divergence instead of L² norm). The optimization problem can be solved as K-means, yielding an local minima. I thought they might stop here, but they didn't.

Careful readers notice that the number of clusters, K and the time t for random walk are not determined yet. So the following part deals with these two parameters. Given K, learn t. It's an easy problem. If the distribution matrix should be maximally preserved, low rank approximation will take the leading eigen values and we abandon the rest when the gap between them is maximized.

Then how can we obtain the desired parameters from data? Well, it's not that difficult. With the similar idea, when some gap is maximized while we don't know which K.

But then, is it possible to formulate a hierarchical clustering algorithm with this random walk? Well, use the gap size as the plausibility for the partition. Choose the smallest number of plausible clusters(big gap and few clusters). And do partition and recursively carry out the algorithm.

A piece of fresh work needs few references.