Random Walks for Image Segmentation

by Leo Grady

This paper proposed a random walk based algorithm for image segmentation. The idea is quite straightforward: some part of the images are labeled by the user and other areas are segmented using the random walk probability that stops at these landmarks.

The interesting part of the paper is that it proposed a (several) linear system to solve the probability, instead of solving an eigenvalue problem.

L_U X = -B

where L_U is the graph Laplacian of the unlabelled samples and the B is the cross block in the Laplacian of the whole graph.

The idea was used in t-SNE to build p-table for landmarks.

Annotating Photo Collections by Label Propagation According to Multiple Similarity Cues

by Liangliang Cao, Jiebo Luo and Thomas Huang

The image annotation problems is actually a multi-label propagation, unlike three previous papers. We are only interested in the label propagation part. Actually it is only a weighted counting for independent labels. Nothing new :-(

Semi-supervised Classification Using Linear Neighborhood Propagation

by Fei Wang, Jingdong Wang, Changshui Zhang and Helen C. Shen

The so-called linear neighborhood propagation relies on the idea from LLE. Instead of using the graph weights directly, as in former methods (c.f. Zhou and Zhu's papers, two previous paper), the weights are computed using the idea from LLE. Therefore, in a way Zhou's version is something like diffusion map, Zhu's Laplacian eigenmap while this one LLE. We may find those counterparts in manifold learning.

The procedure to calculate the weights are identical to that of LLE (by minimizing the affine reconstruction error). Then the weights are used to propagate the labels with the same objective function as in semi-supervised LLE (or landmark LLE). In this way, it eliminates the selection for a width for Gaussian kernels.

Well, why not make a LTSA version? Haha...

Semi-supervised Learning Using Gaussian Fields and Harmonic Functions

by Xiaojin Zhu, Zoubin Ghahramani and John Lafferty

This is also a piece of even earlier work on label propagation in semi-supervised setting. There are many fancy nouns, Gaussian random fields, energy minimization and harmonics... But it ends like something resembling the previous paper.

They explain the label propagation as the minimization of the so-called energy function of a Gaussian field, which is actually the quadratic form of the Laplacian and therefore corresponds to the so-call elliptic PDE (and hence many more nouns: Green function, harmonics). The little difference might be they are using D^{-1} W (one-step transition matrix) instead of the symmetrized and normalized version D^{-1/2} W D^{-1/2} in the previously scanned paper. The closed form solution is obtained via Schur complement instead of the iterative procedure in Zhou's paper.

The paper also discusses connections with random walks and electric networks, graph kernels, spectral clustering and N-cut. I believe due to the connection, this propagation idea must have been discussed with all kinds of variants (normalized? symmetrized?)

Learning with Local and Glabal Consistency

by Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston and Bernhard Scholkopf

This paper is about label propagation in semi-supervised learning setting. The basic idea about label propagation is to use a graph as a random walk structure. The label is propagated with the following equation

Y(t + 1) = \alpha L Y(t) + (1 - \alpha) Y(t)

where Y(t) is the label matrix (in multi-class classification, it is a unit vector for labeled sample) and S is the normalized weight matrix. The iterative procedure will result in a limit of

Y^\star = (I - \alpha S)^{-1} Y

This reveals some connection with the graph Laplacian.
Th interesting part is how we may develop a parallel version of this idea.

Non-metric Label Propagation

by Yin Zhang and Zhi-hua Zhou

This paper follows the idea of the non-metric similarity matrix analysis. By decomposing the Gram matrix into two separate graphs (one for positive eigenvalues and the other for the negative), they build two separate Markov chains, which compromise a mixture of Markov model for label propagation (just an explicit solution of linear equations). Their paper contains many experiments as usual, which I think might be the deficit of my own research work.

The idea is not that fancy but the application in label propagation might be novel, the research style of Zhou's :-p That requires keen olfaction.

Two-view Feature Generation Model for Semi-supervised Learning

by Rie Kubota Ando and Tong Zhang

We first take a look at their logic: for semi-supervised learning, a generative model is usually preferred since unlabeled data help estimate the margin distribution \Pr(x). In a Bayesian MAP formulation, we are actually

\min_\alpha - \sum_i \log \Pr(y_i \mid \alpha, x_i) - \log \Pr(x_u \mid \alpha)\Pr(\alpha)

which is a little different from a direct generative model. Here the first term is actually a discriminative term and the second term is a penalty from unlabeled part (therefore it is more similar to a ``supervised loss + penalty'' model). This paper does talk about models of the latter, using auxiliary problems.

The two-view model means, analogous to co-training, we have two view of feature vector x, namely z_1(x), z_2(x), which are inpdependent conditioned on the label. The different thing about this model is in order to solve \Pr(y \mid z_1, z_2), we need \Pr(y \mid z_1), \Pr(y \mid z_2). Now we only consider \Pr(y \mid z_1). One possibility is to make a low-rank decomposition of \Pr(z_2 \mid z_1) = \sum_y \Pr(z_2 \mid y) \Pr(y \mid z_1) but the LHS is sometimes impossible to compute. An approximation is to encode z_2 with a set of binary labels t_1^k(z_2). Then \Pr( t_1^k \mid z_1) = \sum_y \Pr(t_1^k \mid y) \Pr(y \mid z_1) can be computed. By increasing the number of related binary labels t_1^k we may have a good estimation of \Pr(y \mid z_1).

They proposed two models (one linear and the other log-linear, which resembles linear regression and logistic regression in a way). The linear version coincides with the SVD-ASO model in their JMLR paper. The log-linear model is solved via EM-like algorithm.

The thing is what kind of binary auxilliary function would be essential to our semi-supervised problems? This might be a key to understanding their JMLR paper for multi-task learning.

A Framework for Learning Predicative Structures from Multiple Tasks and Unlabeled Data

by Rie Kubota Ando and Tong Zhang

This paper addresses a framework for multi-task learning. Their idea is quite simple. There is a common factor \Theta which is shared in different but related problems. Therefore in each problem P_k, our parameters include w_i, which is problem-specific and v_i which is dependent on the common feature controled by \Theta. To solve the model it usually desirable to alternatively optimize over w_i, v_i and \Theta. Usually a regularizer is also included for better generalization capacity.

using this idea, the authors proposed a linear model which is solved by the ASO using SVD in each iteration to find \Theta (SVD-ASO in their term). With this idea, they analyzed the semi-supervised learning with auxiliary functions, which are essentially those multi-tasks.

Their extention for this piece of work is scanned here.

Discriminative Semi-supervised Feature Selection via Manifold Regularization

by Zenglin Xu, Rong Jin, Michael R. Lyu and Irwin King

This paper talks about feature selection via SVM. The semi-supervised part is enabled by adding a manifold regularizer. The method is to multiply the feature with a diagonal 0-1 matrix (selecting features). With these variables in the optimization as well, we get the optimization for this problem. The key idea to solve this problem is to reformulate it with the dual of SVM but leaving the feature selecting variables alone. Then the optima is the saddle point of the optimization problem. This kind of problem can be found in multiple-kernel learning, which has a standard algorithm (alternating optimization w.r.t. difference variables).

The idea of using SVM for feature selection is not new. The contribution might be the semi-supervised setting. In my own research it seems that we still do not have a clear goal of achieving this with other methods. hmm...

Graph Construction and b-Matching for Semi-supervised Learning

by Tony Jebara, Jun Wang and Shi-fuh Chang

This is an ``advertisement'' paper for their 2007 paper on b-matching. In general b-matching is a graph construction algorithm as k-NN. This paper enumerate all kinds of combinations of label diffusion (propagation?):

• graph construction, kNN and b-matching
• weight, Gaussian kernel, LLR (like LLE).
• diffusion algorithms, GRF, LGC and GTAM.

I don't buy their conclusion. Yes graph construction might be important to later algorithms, but the b-matching result doesn't seem so different from k-NN. Maybe we have to try for ourselves.

Localized Sliced Inverse Regression

by Qiang Wu, Sanyan Mukherjee and Feng Liang

Sliced inverse regression (SIR) for classification is equivalent to FDC. That is to solve a generalized eigenvalue problem Γβ=λΣβ, where Γ is the between-class covariance matrix and Σ is the total covariance matrix. The largest eigenvalues of this problem correspond to the disired directions. Well, in some cases we use the in-class covariance matrix B for Σ.

This has been discussed in Jieping Ye's paper extensively. In a way Σ is more likely to be non-singular than B. Due to the fact Σ = Γ + B, there exists a non-singular matrix A such that they can be diagonalized simultaneously with a transform Az = x. If they are non-singular, it matters not whether we use B or Σ. When B or Σ is singular, we might use its principal subspace or its null space for approximation (well it's not approximation I guess). I wonder what we shall do for SIR. Maybe we do the same rubbish too.

Now we come to the LSIR. The authors proposes a localized Γ by choosing the kNN samples of the same class. The only difference between LSIR and LFDC, I think, is the denominator part (i.e. a global covariance class v.s. a localized in-class covariance). Maybe I have to explore the corresponding graph to see their difference more clearly.

Their extension for SSL is to put all unlabelled samples into to all slices. That might be natural in the graph embedding framework. Why should I read this paper then?

Semi-supervised Learning via Gaussian Processes

by Neil D. Lawrence and Miachael I. Jordan

The authors present a way of modifying the discriminative model in order to use the unlabelled data. As we know the parameters are conditionally independent with the unlabelled data. They propose to add a null-category variable to the model which ensures there might exist a certain dependency between the parameters and the unlabelled data.

The main idea is the unlabelled data will get a 0 label and the parametric model is thrown away by a Gaussian latent variable. Thus, the dependecy x -> y -> z will be x -> f -> y -> z. Nonparametric model needs tuning hyperparameters (EM to maximize Pr( y | x, z)) and the inference is done with EP as in a GPC. The conditional probability of Pr( y=0 | f ) suggests a low probability around the sample, if it is unlabelled and the value of f is large. And Pr( z | y = 0 ) is simply 0-1 (indicator of labels) and Pr( z | y = 1 or -1) is defined as a binomial variable. Then our model is done.

Why does it work anyway? One thing about the labelled data is for positive ones f should be positive and have a large absolute value and negative ones negative and a large absolute values. For unlabelled data, we don't have y and we use the conditional posterior probability Pr(y | x, z, D ) which involves setting z = 1 (instead of 0 as unlabelled samples) and Pr( z = 1 | y=0 )=0. Then the posterior could be computed.

I have to do some experiments on non-parametric Bayesian methods to gain more intuitive insight.

Classification using Discriminative Restricted Boltzmann Machines

by Hugo Larochelle and Yoshua Bengio

This paper formulates a ``discriminative'' RBM. The visible layer contains the features and the labels (in a softmax way). It can be trained in a generative way and a discriminative one. The generative one maximizes Pr( x, y ) while the latter maximizes Pr( y | x ). As we can see, Pr( x, y ) could be maximized with contrastive divergence as the normal RBM. And I remember Hinton's course last year includes an example of classification using free energy directly with this model. Now for the discriminative case, when the number of classes is small, a exhaustive sum over y is feasible. The good news is that the partial differentials can be obtained with explicit expressions.

Regarding last scanned paper, they propose a hybrid model that relies on two loss functions (negated log-likelihoods, introducing a coefficient for the generative part). Then the discriminative part has a non-stochastic gradient and the generative part has a stochastic one (due to CD).

As for semi-supervised learning, we just marginalize out the label y from the RBM. Then the gradient becomes the CD averaged over y. This negated likelihood of Pr(x) will function as a regularizer.

It's amazing the DRBM alone could achieve 1.81% error rate on MNIST with only 500 samples. The HDRBM could achieve even lower. They mention a sparse version which I will scan soon.

Exploiting Generative Model in Discriminative Classifier

by Tommi S. Jaakkola and David Haussler

This is a classic semi-supervised style of learning. First a generative model is trained with all samples without labels. The generative model has parameters and the Fisher information matrix I could be calculated (Hessian of the Likelihood function). With this a kernel could be introduced as the quadratic form of the score:

k( x, z ) = U_x^T I^-1 U_z

The kernel could be exploited by later discriminative models, such as GLIMs and SVMs.

It can be easily proved the proposed kernel has several nice properties:

• It is a qualified kernel.
• As Jeffreys's rule, it is invariant under continuously differentiable transform of parameters.
• A kernel classifier employing this kernel derived from a model whose latent variable is the label is asymptotically as good as a MAP labelling.

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.

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.

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.

Semi-supervised Nonlinear Dimensionality Reduction

by Xin Yang, Haoying Fu, Hongyuan Zha, Jesse Barlow

I guess those guys working on semi-supervised manifold learning are far away from practical applications. In this paper, the so-called SS-LLE and SS-LTSA are so obvious that they are not mentioning. Just consider the original algorithm, since the optimization will result the required coordinates while now some of them are known, the blockwise formulation will immediately show us the semi-supervised problem is an even easier one to solve.

Something a little more difficult is how to make the traditional ISOMAP semi-supervised. Since in LLE and LTSA, the to-be-minimized term has the meaning that the reconstruction error in the corresponding settings should be minimized. However, as a spectral embedding, the optimization in ISOMAP doesn't share a similar meaning. They use an ugly way to incorporate their idea in the case of ISOMAP:

As you can see, A is the Gram matrix obtained after the double-centering step in ISOMAP. With the shifting of the eigen values, now the desired coordinates can be obtained in the terms of M, which is similar to the one in LLE and LTSA. But somehow you can sense their non-sense. Their paper states a similar result, complaining SS-ISOMAP is not as good as the other two.

Maybe their latter part is more interesting, analysing the numerical stability of their algorithms. But somehow it is not a mathematical paper and I don't like their style in machine learning.

Some thinking on Parzen window and Semi-supervised learning

Here is an idea originates from the following refereces:
Pattern Classification, by O. Duda: It presents me a basic form of Parzen window. And I think it is quite natural to use other distributons instead of a uniform distribution in a super cube. So I wondered where I can find more information on this topic. PageRank then suggested severl useful links and mnauce gave several more and comments.

• Emaneul Parzen, On estimation of a probability density function and mode. Annals of Mathematical Statistics, 33(3):1065-1076, 1962.<available from JSTOR>
• B. Silverman, Density estimation for statistics and data analysis, Chapman and Hall, London, 1986<books.google>
• Asymptotic Statistics, by Vann Der vaart<in library>
• A framework for probability density estimation, by John Shawe-Taylor<PASCAL>

Learning with Kernels, by Bernhard Schölkopf and Alex Smola: There is a simple mean classifier in it which indicates that kernel framework will convert many algorithms to superior ones. And then it tells us this classifier can be taken as a difference of Parzen windows. And then I think about SVM. The solution of a SVM tells us which samples are necessary to establish a discriminant classifier and what's their weight.

Manifold Parzen Window, by Vincent, Bengio(in NIPS 2003): They suggested a method to incorporate manifold learning ideas with density estimation. The final version is not far from what I have thought about the problem, local PCA just as MFA does. But I suddenly realize that the neighborhood sellection method used by Zhenyue Zhang is also feasible here. However they indeed extended this version in their later work.

Non-local Manifold Parzen Window, by by Vincent, Bengio(in NIPS 2005). However, then they still stayed at manifold learning. They haven't progressed as fast as I imagined. Though I am still confused about the value of this work now(am silly), I guess there can be something if we try to put the problem in the field of semi-supervised learning paradigm.

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