Multiplicative Updates for Nonnegative Quadratic Programming

by Fei Sha, Yuanqing Lin, Lawrence K. Saul and Daniel D. Lee

This paper addresses a method for quadratic programming with non-negative constraints. We know there are serveral basic techniques dealing with non-negative constraints: one is use the logarithm and the gradient method would becoeme a multiplicative update step, which is usually referred to as EG.

In this paper, the following optimization problem,

minimize F(x) = x^TA x /2 + b^T x subject to x >= 0

is explored. The proposed updating rule is simple: let A = A⁺ - A^-, where A⁺ and A^- are the positive elements and negative elements of A and let a_i = (A⁺ x)_i, c_i = (A^-x)_i. The updating scale factor resembles a root of a quadratic algebraic equation:

x_i <- x_i (-b_i + sqrt(b_i² + 4 a_i c_i)) / (2a_i)

The rest is the proof.

Here I want to mention several easy parts about the algorithm: the gradient of the objective function is a_i + b_i - c_i and when it's positive the update rule will decrease the objective function and when it's negative the update rule will increase the objective function; the fixed point analysis shows that the condition coincides with KKT condition.

There are several application of this optimization technique, e.g. in the dual problem of SVM. But it seems that specific algorithms, such as SMO will do better than this multiplicative update rule. So maybe we have to check the convergence rate and do some experiments for comparison.

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.

DiscLDA: Discriminative Learning for Dimensionality Reduction and Classification

by Simon Lacoste-Julien, Fei Sha and Michael I. Jordan

I decided to read this paper since LDA has been encountered several times recently. This LDA does not stand for Linear Discriminant Analysis, which refers to a linear classifier or sometimes the famous Fisher discriminant criterion. This term might originates from the paper published in JMLR 2003 (see below, I haven't verified this) and refers to Latent Dirichlet Allocation, which is designed for NLP modeling. It's a Bayesian generative model.

As we can see in the figure, the word w depends on the topic z, which is a r.v. of multinomial distribution. The prior for z is naturally a r.v. theta of Dirichlet distribution, whose hyperparameter is alpha. The parameter beta is simply a table of parameters for each topic. After we integrate out the latent r.v.s, z and theta, by maximizing the likelihood of the marginal distribution, i.e. empirical Bayesian method, the parameters alpha and beta could be estimated (with standard EM algorithm). To get the posterior distribution of z, we have to use variational approximation.

The LDA model could be used in unsupervised learning where the topic provides a dimensionality reduction/semantic hashing function. It could also be used in classification, where z is the corresponding label.

This paper provides additional information for the topics. These labels are side supervised information.

As you might see in thr figure, the label y comes into the model and the model becomes tougher. So the resulting inference is solved with MCMC methods. The improvement of the model demonstrates how the side information could help build a better model. Not sure about the core part. But it looks worth trying...

Several References
David M. Blei, Andrew Y. Ng and Michael I. Jordan: Latent Dirichlet Allocation, JMLR 2003

Graph Laplacian Regularization for Large-Scale Semidefinite Programming

by Kilian Q. Weinberger, Fei Sha, Qihui Zhu and Lawrence K. Saul

The first time I read of Weinberger is when I was working on manifold learning. At that time, his idea of maximum variance unfolding was quite enlightening. The manifold learning task, in his interpretation, should preserve local distances while maximizing the embedding variance. The formulation of the problem in optimization term is an SDP problem.

This paper further studies the MVU idea, since the SDP can't scale well when the number of samples grows. The so-called Laplacian regularization technique has been quite popular since its proposal in manifold regularization (maybe, I am not sure about the first appearance of it). The idea is that the bottom eigen vectors of the Laplacian matrix correspond to smooth eigen functions over the graph. Therefore it is reasonable to find an approximation in this subspace for the original problem. By re-formulating the original problem we could find one with reduced complexity.

The other fine-tuning techniques is the approximation offers us a good initial value if we try to solve the non-linear optimization problem without SDP. Using CG algorithm, the result could be further improved.

I think I'd better get familiar with SDP ASAP. I am really in urgent need of comprehension of these optimization tools.

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.

Using the Nyström Method to Speed Up Kernel Machines

by Christopher K. I. Willians and Matthias Seeger

This is an old paper, which I must scan for recent research. The Nyström method originates from the numerical solution of integral equations. Since in kernel methods, we have to eigen decompose a large Gram matrix (of size N, the number of samples), which requires O( N3 ).

The eigen decomposition yields the basis functions evaluating at the sample points and the eigenvalues, which could be used to approximate the basis functions evaluating at an arbitrary position. This is the so-called Nyström method. What this paper says is to select randomly a subset of the samples, for which the required elements in Nyström method are derived. As is written in the paper, only comparatively small amount of calculation needs to be done.

This technique is verified on Gaussian Process in the experiment, yielding a good approximation.

Understanding camera trade-offs through a Bayesian analysis of light field projections

by Anat Levin William T. Freeman and Fredo Durand

In the recent a few years the direction of computational photography has become hot, with unconventional cameras capturing not only a traditional image but also structure of the scene. Yet this might be the first paper to state a unified framework for such cameras.

The atomic element that interact camera sensors are light rays, which could be encoded by the notion of light field. With this notion, an image captured by a computational camera could be formulated as a linear projection of the light field. Considering the noises on the sensor, reconstruction of the light field could be addressed as solving a linear problem in the Bayesian manner.

A number of recent optical designs were examined in this framework for a empirical comparison, including pinhole, lens, wavefront coding, coded aperture, stereo and plenoptic cameras. It was found that a good depth prior, e.g. a mixture of oriented Gaussians, is critical for computational imaging tasks. It was also found that the optical design of wavefront coding is optimal to capture single-view scenes while a stereo configuration is best for capturing the full light field. Well, it's ironic to note that both configurations are quite "ancient": even earlier than the notion of light field was invented...

This paper might be helpful for vision people to design new cameras, and for setting up a more analytical study of existing designs. I personally think this could be a cornerstone of the field.

This is a eccv2008 paper and could be downloaded from:
http://people.csail.mit.edu/alevin/