Two-Dimensional Solution Path for Support Vector Regression

by Gang Wang, Dit-Yan Yeung and Frederick H. Lochovsky

In this paper a method for tuning the parameters of SVR is proposed. There are two parameters, ε(the allowable errors) and λ(the regularization parameter). Usu. they are setted up according to experiment results.

In a previous paper in NIPS 2005, the path of λ was studied. The idea is that starting from λ=infinity and by descreasing the value to 0, we might find a path for each Lagrange multiplier and the bias, which are proved to be piece-wise linear function of λ. The paths help us in determination of the regularization parameter, since the number of samples in the elbow implies a ``degree of freedom'', which is employed for selecting the GCV parameter as the SE/(N - DF) instead of MSE. The reason is still not quite clear to me.

The ICML 06 paper aims at ε. Basically they use the same analysis and the result is similar that the Lagrange multipliers and the bias are piecewise function of ε. The paper solves the problem in the NIPS paper that requires ε known and set a priori. Now this paper emphasizes that we could choose a proper ε with the path.

Trace Ratio vc. Ratio Trace for Dimensionality Reduction

by Huan Wang, Shuicheng Yan, Dong Xu, Xiaoou Tang, Thomas Huang

This is a CVPR paper in 2007. I read Yan's CVPR paper in 2005. So I am quite familiar with this direction. Basically I agree with their argument on using trace ratio, esp. for those graph embedding algorithms. It is more sounding by directly maximizing the ratio of between-class scatterness to with-in class compactness. the optimization becomes difficult when trace ratio is the objective instead of the originally used formulations, e.g. iteratively defined optimization, trace formulation and determinant formulation.

The constraints of their proposed optimization ensure orthogonality of the projection. The algorithm, also an approximation in the principal subspace of S_t, iteratively updates the projection V, such that

V^* = arg max tr V^T (S^u_p - λⁿ S^u_t ) V s.t. V^TV = I

The iteration will increase the objective function monotonously and ensures a global optimum (main contribution). For other constraints, such as one in kernelization, an eigen decomposition is first applied.

Hmm... another work as an extension to this (vector -> tensor) says a global optimum might not be obtainable, which I might check later.

Adaptive Online Gradient Descent

by Peter L. Bartlett, Elad Hanzan and Alexander Rakhlin

In this paper, we are looking for a game-like optimization problem. We have to pick up a x_t for an unknown objective f_t(x), which might be a loss the adversary might ompose upon us. To evaluate the final result, the accumulated loss w.r.t time t = 1, ..., T is compared with a fixed action x, that minimize the total lost. The difference of the two is hence called regret (why not wait until the last f_t is given),

There are several results with with problem:

• Zinkevich showed for linear function, the regret will increase as sqrt(T) using his proposed online gradient descent algorithm.
• Hazan et al showed under the assumption of strong convexity, the regret will increase as log(T).

This paper has several results:

• With a regularization technique, they propose an adaptive online gradient descent algorithm, which ensures 1-6 times regret when the coefficients for the regularizer are determined offline for the lowest regret.
  
• It might be proved that for linear functions and strongly convex functions, likewise rates, O(sqrt(T)) and O(log(T)), are to be achieved.
  
• There exists a similar algorithm for general L^p norm, with the help of Bregman divergence generalization, from L² in
  
  
  
  The Bregman divergence is
  
  
  

Bayesian Regression with Input Noise for High Dimensional Data

by Jo-Anne Ting, Aaron D'Souza and Stefan Schaal

Usually in the regression models, no noise is assume at the input side. This paper deals with the case the assumption doesn't hold. The basic observation is that when noise exists, the orignal model tends to underestimate the parameters (para. 3, sec. 2). I am interested in why it is (no reference and proof is given).

To filter the noise, a probabilistic model that resembles JFA is proposed. I can't help recalling those in Jordan's unpublished book. Now I can understand it better. The solution to the model (training part) relies on EM, which is commonly used when hidden variables are at hand. The inference part is done by marginalizing all hidden variables and conditioning the output on the input, as is done in conventional regression. The following figure shows evolution of their model,

I decide to review Jordan's book, really worth reading. Hopefully I'd derive several famous models for later seminars. Now let's get closer to the model. The hidden state t is assumed as a Gaussian. The observed x and y (I don't think z is necessary at all, so just forget about it) are conditioned on t and another parameter, and they are Gaussians too. The only non-Gaussian hidden variable α is a Gamma-distributed R.V.. It's paraphrased as precision of the two parameters, hence the only hyperparameter of the model. Why Gamma?

About the results... The figure shows when the test case is noise-free, the proposed model yields lowest errors. But when the test cases are also contaminated by noise, all methods perform equally worse. It's a little difficult to tell, since after all the test cases are not accurate at all, we know no groundtruth.

Null Space versus Orthogonal Linear Discriminant Analysis

by Jieping Ye and Tao Xiong

In this paper, several LDA algorithms are addressed. The main result says OLDA and NLDA under certain conditions will yield the same result.

I seldom consider the details of the LDA algorithms, but after I read the journal version about the OLDA, I think it's necessary to get a summary for their current work. I am thinking about the possibility of reusing their techniques in the graph-based algorithms. But for the current paper, it's too far.

One deeply-sighted observation is the simultaneous diagonalization of S_w, S_b and S_t. Then the optimization is generalized from ``inverse'' of S_t to its pseudo-inverse. Actually, we have several constraints for different LDA algorithms. The ULDA requires orthogonality w.r.t. S_t while OLDA simply requires orthogonality w.r.t. an identity matrix. The so called NLDA maximizes the projected between class scatterness in the null space of S_w.

The condition they find for the equality is the rank equality. They test their algorithm on several high-dimensional data sets. I guess it's easy to follow their motivation.

Though lots of graph-based dimensionality reduction algorithms extensively use the idea from LDA, the simultaneous diagonalization is seldom feasible. Maybe, it's worth trying to get a more generalized solution for that rank-deficit general eigenvalue problem.

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.