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.

Max-Margin Markov Networks

by Ben Taskar, Carlos Guestrin and Daphne Koller

As we might see in CME, CRF, features are just as features in SVM, the parameters we are learning from data are learnt via those in logistic model. We know MLE is just one way of training discriminative models. Another widely-used rule is max margin. How can we model a structured output as in CRF (namely it is an MRF) with margins?

The idea comes from multi-class SVM: the predicted label defines a feature vector which should be separated from other vectors of different configurations for at least γ. But now we have a variable length of each sequence. Therefore it is reasonable to constrain the margin inquality to a certain scale of γ. The scale is simply the number of classification error. Like SVM, introducing slack variable for the unseparable case will get us the margin + loss expression. This optimization is still convex, but the constraints are too many since in multi-class discrimination, the configurations are comparatively fewer (c classes, then c-1 constraints for each sample). Now for a sequence of l labels and the number of values of y is c, we have c^l constraints.

The tackle this problem, they convert it into the dual problem. The dual variables can be regarded as a density (to a given scale). Though they are many, not every single variable must be computed. The structure of the MRF determines the necessary combinations of them: grouping them into edge dual variables and vertex dual variables gives us a polynomial-number of optimization variables. But now we have to satisfy the consistency the vectex variable now is the margin of related edge variables. Then we can convert the dual problem back into the prime one. The optimization is done in SVM's flavor, e.g. SMO.

Learning Globally-Consistent Local Distance Functions for Shape-Based Image Retrieval and Classification

by Andrea Frome, Yoram Singer, Fei Sha and Jitendra Malik

It looks like a similar problem to CBIR (content-based information retrieval). This application might be solved with MIL (multiple-instance learning). Here the basic idea is distance learning. First several patches are extraced from the images (with SIFT or geometric blur). The distance of each pair of images is a weighted sum of ditances of patches. Here the distance of each pair of images is actually not a distance (no symmetry is assured). We only compute the distance of image i and j to the image k and compare the two to decide which is more likely a match. Then we only need to decide the weights.

Here it exploits the maximum margin concept by a similar strategy as in SVM, that is to constrain the training set by an inequality . - .. >= 1 and minimize the norm of weights. The thing about this strategy is whether this is a margin -,-b I am always confused by it. Maybe it is reasonable but not geometrically interpretable?

Large Margin Hidden Markov Models for Automatic Speech Recognition

by Fei Sha and Lawrence K. Saul

This work is the topic of Dr. Fei Sha's Ph.D. assertion. Two parts of it look familiar but I still have something not clearly comprehended.

The first part is about large margin GMM for multiway classification. First the separable cases (each class with one Gaussian) are considered: The highest probability of a certain class wins, which could be formulated with a quadratic form; the separable samples could be scaled such that a similar constraint as in SVM must be met; the maximal margin is equivalent to the minimal trace of the precision matrix of the Gaussian. If we allow samples that comes into the margin, slack variables could be introduced similarly. At last, if we add more Gaussians for each class, our constraints will increase much. They proposed to use a stronger inequality instead: taking the softmax (softmin indeed) of several terms instead of using the minimum results in a inequality with log-sum term. I don't know why the trace relates to the margin -,- From his Ph.D. thesis, it seems that the trace could be regarded as a norm for positive semi-definite matrices but it is used here simply because it will be a convex optimization problem (specifically a SDP problem). Please note that GMM is a generative model. But it is trained with maximum margin instead of maximum likelihood.

The second part is about the HMM. The GMM is used as the emission probability. Then we can write down the joint PDF easily. Now the HMM model does not need EM for training since in the given task the labels are known. The good thing in training is that the formulation has the same form as the previous one and hence still a convex optimization problem which could be solved with SDP.

I guess I will spend some time for his Ph.D, thesis later.