Permutation Invariant SVMs

by Pannagadatta K. Shivaswamy and Tony Jebara

First I had a wrong image of this paper, mistaking the permutation for robustness. It turned out the permutation means sth other that robustness. One unpolished idea to tackle with problem of permutation of features is to design a suitable kernel that tolerates permutations. This paper depends on a Kuhn-Munkres algorithm which efficiently seeks the optimal permutation that minimizes sth as following:

With this algorithm, the so-called π-SVM is trained as following:

The algorithm trains an SVM with conventional techniques and tries to permute each sample so as to get a larger margin. I don't see a proof of convergence of this algorithm. The testing procedure needs Kuhn-Munkres algorithm that finds largest margin under permutations of both positive and negative classes and chooses the larger one.

To see why such an SVM is designed, we must know the application settings. They select the pixel positions (70, randomly selected) where it is white in each image as features for each image. Hence the feature is a set of positions, where permutation happens. It is interesting though a little experiment-oriented.

Deterministic Annealing for Semi-supervised Kernel Machines

by Vikas Sindhwani, S. Sathiya Keerthi and Olivier Chapelle

I am surprised that another similar paper on S³VM in the same conference (c.f. the continuation method). The homotopy method does the same thing as the continuation. Find a simple, easy-to-optimize function to start with and end up with the original complex, full-of-local-minima target function. In the continuation setting, convolution with a Gaussian whose variance is diminishing is employed to mollify the target function.

Here, the key idea is the following optimization

might be solved by an annealing in MCMC category. Then we reformulate the S³VM target function as this, by introducing a probability for predicting labels for the unlabelled samples.

Then we have to deal with the optimization with a fixed T(temperature in annealing) and p, which is a convex optimization problem.

They also analyze the corresponding loss function for different Ts. As we can see, the initial loss functions are convex and as the temperature goes down, they are deformed into non-convex ones.

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 :-(

Clustering Graphs by Weighted Substructures Mining

by Koji Tsuda and Taku Kudo

The second author Taku Kudo has written several useful packages in NLP. I'd love to do sth such as programming, esp. making useful tools for later research.

In this paper, the data are graphs. The features of these graphs are so-called patterns, which can be observed or not in a certain graph (hence binary features). Then the representation of a sample is a high-dimensional binary vector.

There are two things in this paper, feature selection and clustering.

The feature selection is tackled with a weighted substructure mining strategy with the help of DFS code tree (a data structure I am not familiar with). Their idea is simple, starting from an empty graph, expanding it by adding an edge (hence we get a tree-like structure for searching). Since we know if a patten is contained in another, it appears more frequent than the latter. So in the search structure, the frequency will decrease as the depth goes up. The frequent patterns can be found by pruning the search tree.

The clustering problem is dealt with binomial mixture model. We know GMM which can be applied to clustering and the model is trained with EM. Likewise, BMM is done in the same way. One thing different is a regularization technique they use. I guess it resembles the term in NMF.

The experiment is carried out on biological databases, e.g. RNA. After all, it is a little application-oriented paper.

Local Fisher Discriminant Analysis for Supervised Dimensionality Reduction

by Masashi Sugiyama

I first knew this paper from afliboy, astonished since I was scanning ICML without scanning it first for my current research project. I am experimenting with it. However, up to now I still don't understand why it is not as good as I have expected on my data.

The idea is so simple. Everyone with experience in FDC will know it immediately. In FDC (or shall we say FDA in accordance with the author), we have two ``variance'' matrices, one for between-class (S_b), the other for within-class (S_w). The reduction is projecting samples into the eigen vectors of the generalized eigenvalue problem of (S_b, S_w), which is claimed to minimize the within-class variance and maximize the between-class variance simultaneously, for which I hold the belief that it is only one strategy for selecting a Pareto optimal (of coz, DNE uses another). The proposed idea reformulates the variance as

which allows us to think about the variance as a pairwise relationship, as if a graph, which I did several month ago without furthering the idea. If I had done, I would been more disappointed by now :-( So locality can be introduced by modifying the weights (those As).

Here As are the adjacent matrices. And this algorithm is then easy to kernelize, as FDC.

With several other papers on graph embedding, this area might be quite difficult to get new result. But anyway, let me try first.

Label Propagation Through Linear Neighborhoods

by Fei Wang and Changshui Zhang

This is a semi-supervised learning algorithm based on graphs. First they use the idea from LLE to determine the weights for the graph (they also use the traditional way for selecting the neighborhood), however the weight has one more constraint. (in LLE the weights are those that best reconstruct the samples with the sum of 1, here additionally they have to be non-negative, which then yields a best convex combination approximation) Second they use the transductive learning idea (very similar to the ICML 06 paper on ranking graphs). The iteral procedure is paraphrased as label propagation:

To prove the convergence of the procedure, it is only necessary to analyze the eigen values of W (which they claim Perron-Frobenius theorems applies here for the non-negative matrix).

The analysis leads to another connection of their LNP with Laplacian-regularized Least Square Regression:

I must verify my intuition today.

To tackle those out-of-sample data, which turns transduction into induction, they use the similar idea to extend LLE, of coz with the additional constraint.

I am not familiar with this transductive result. But I don't think their algorithm will work any better than Laplacian-regularized least square regression. OK, let me check it.

Inference with the Universum

by Jason Weston, Ronan Collobert, Fabian Sinz, L\'eon Bottou and Vladimir Vapnik

Universum is a new concept to me. In the settings with universum, we have another data set (universum) besides the training set and testing set. Now let's have a look at the logic of the whole thing.

With the training set, we have finite separation results. With each separation, we have correspondingly an equivalent class of functions from the hypothesis space. In SVM settings, the regularizer for the loss is the margin of the function. Why do we control the margin? Since it is the ``inverse'' of capacity, which controls the generalization capability while the capacity is complexity of the hypothesis space imposed on the whole feature space.

However, real problems are different in that the samples come from only a fraction of the whole feature space. We need to measure the complexity of the function on the problem. Usually in Bayes theory, the prior distribution is considered to encapsulate the information which is priorly holden. However, it is difficult to design priors.

By designing universum samples carefully so as to incorporate the information (hence universum samples are not in any labeled class, but those relevant uninteresting samples), we might figure out a way to measure the complexity. The following optimization is proposed to tackle the issued idea:

The last term is the universum regularizer. The U() function is a epsilon-sensitive loss. The resulted function should have small values on the universum samples and hence is instable (w.r.t. the sign of the values) if there is a small purturbation (the purturbed function is most possibly in the same equivalent class). So the resulted function comes from an equivalent class which has lots of contradictions on the universum samples, which indicates it has high complexity on universum sample and therefore comparably low complexity on those samples we are interested, given the limited total complexity.

Well, this is really interesting. Adding ``useless'' samples and getting a regularizer for them will get better result :-)