Regression on Manifold Using Kernel Dimension Reduction

by Jens Nilsson, Fei Sha and Michael I. Jordan

This paper describes a regression problem: the samples come from a manifold embedded in a high dimensional space and the response is function defined on the manifold. There are 3 techniques applied in this problem: sufficient dimension reduction (SDR), kernel dimension reduction (KDR) and manifold learning.

The basic idea is from KDR, in which we seek a subspace (to be the central subspace) B such that the projection onto the subspace are sufficient to regress the responses. This idea (in linear case, namely SDR) requires solving the following optimization problem,

where K_Z^c is projected Gram matrix. Here with manifold learning, the projected sample Bx_i in the RKHS is approximated with the affine transformation of the coordinates obtained by the manifold learning algorithm (e.g. Laplacian Eigenmap). Therefore the optimization problem could be formulated as

After solving the problem, the regression could be done in the corresponding subspace. The difficult part is how to solve this nonlinear and nonconvex problem. It is solved with projected gradient descent method.

But it seems hard to extend to new data. It is argued that by computing the latent B, it is possible to extend the regressor on new data. But it doesn't say how. I guess it must be much tougher :-(

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.

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.

Efficient Co-Regularized Least Squares Regression

by Ulf Brefeld, Thomas Gärtner, Tobias Scheffer and Stefan Wrobel

In semisupervised learning, there is an important technique called co-learning. The basic idea is to train two independent classifier. Let them mutually interact with training errors in order to agree on unlabelled examples at last. Two phrase: independent classifiers, agree on unlabelled data.

Now let's focus on what the authors show us. As is know, the framework of SVM give a regularization technique for supervised learning already. So in order to incorporate unsupervised data, add a "agreement regularizer".

Then by representer theorem, the optimization result requires O(M³(m+n)³) where M is the number of different views, m is the number of unlabelled data and n the number of labelled data.

However, usually m will be huge due to the accessibility of unlabelled data and we will suffer with a cubic algorithm. An alternative simply uses a subspace of the original RKHS, namely the one expanded with labelled data only. Then the optimization becomes the following equation:

and this can be solved in O(M³n³+M²m).

Another result given in this paper is a distributed algorithm for the optimization problems mentioned above. The algorithm called block coordinate descent is analogous to steepest gradient descent while the former one only scrambles along several coordinates associated with the message sent by another classifier in a different site.

The paper also lists several literatures on co-learning for my future study:

• Combining labled and unlabeled data, by Blum and et al.(the one who proposed co-training)
• Learning classification with unlabeled data, by de Sa, in NIPS(the first who noticed the consensus of multiple hypothesis)
• Unsupervised models for named entity classification, by Collins and et al.(a variant of adaboost)
• PAC generalization bounds for co-training, by Dasgupta and et al., in NIPS
• The value of agreement, a new boosting algorithm, by Leskes, in COLT
• Two view learning: SVM-2K, theory and practice, by Hardoon and et al., in NIPS

Here is another survey:

• Semi-supervised learning in literature survey, by Zhu