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.

Structured Ranking Learning using Cumulative Distribution Networks

by Jim C. Huang and Brendan J. Frey

This NIPS paper further elucidates how to take advantage of CDN's idea to tackle a ranking problem. The author introduce a probability distributon for the preference variable given an ordered relationship. Therefore a natural choice of the ranking scheme is to maximize the likelihood or equivalently to minimize the negative log-likelihood (loss function). Once the ranking function could be parameterized, the optimization problem could be solved. The paper employs a nonparametric model. CDN here plays the role of setting up the CDF for the observed preference variable.

With this formulation, several earlier proposed algorithms could be regarded its special cases, such as RankNet, ListNet and ListMLE. I will take a close look at those ranking algorithms later.

Cumulative Distribution Networks and the Derivative-Sum-Product Algorithm

by Jim C. Huang and Brendan J. Frey

The paper first proposed novel probabilistic graphical model, i.e. CDN. The model differs with MRF and Bayesian belief network in several aspects. The basic idea of the network resembles the factor graph of MRF. The factor graph of an MRF consists a vertex set of two parts: one of the original vertices of the MRF, the other of each cliques. The representer theorem of MRF actually tells us each clique is a nonnegative potential function (unnormalized PDF, hence the vertex is often referred to by function vertex). In CDN, however, each function vertex corresponds to a CDF-like function (i.e. cumulative function as in the paper). As long as these cumulative functions satisfy several simple properties (which might be easily proved as in the paper), their product is a decent CDF.

To do inference in CDF, the authors proposed an algorithm that resembles sum-product algorithm for factor graphs (i.e. belief propagation for polytrees). We know the derivative of the CDF is PDF, therefore it looks natural their inference is called Derivative-Sum-Product (DSP) algorithm. I will read the details about the algorithm later.

This framework is applied to a ranking problem.

Here we can see, we have three teams, (X₁, X₂), (X₃, X₄) and (X₅, X₆, X₇). The function s_i(x_i) is the skill of the player. The performance of each team is the sum of all players, a function of x_i. And we get R₁, R₂ and R₃. We do have the rank of these teams, which comes as an ordered graph whose relationships are represented with h. The prediction is carried out with skill functions learned with previous results. In this model every function vertex is a CDF of a Gaussian and DSP could be computed easily. I think the details are worth trying to see.

In the end, several applications are pointed out, webpage ranking, collaborative filtering and etc. They also intended to focus on the learning part of the model in later research and the DSP algorithm, as the belief propagation, is only applicable to trees.

Several related topic:
convolutional factor graph: Convolutional factor graphs as probabilistic models, UAI 2004.

Clustering by Passing Messages Between Data Points

by Brendan J. Fray and Delbert Dueck

It's an interesting paper about clustering. The technique they employed is affinity propagation, believed to be an example of belief propagation. It has several important features: it identifies exemplars in the samples instead of find a mean/center directly; when the similarity matrix is sparse, the algorithm works fast since it is a linear algorithm w.r.t. the number of similarity values s(i, k); instead of choosing the number of exemplars, the user is only required to set a value for s(k, k) which may influence the number of exemplars (the larger the value is the more exmplars are).

The iterative algorithm is very simple. Two matrices are introduced to show how well the sample k is as the exemplar of sample i in the opinion of sample i or k, i.e. responsibility r(i, k) and availability a(i, k). The updating rule for responsibility is

r( i, k ) <- s( i, k ) - max { a( i, j ) + s( i, j) | j <> k}.

The initial value of availability is 0 (later it is nonpositive). The maximal sum similarity and availability indicates the sample which is similar while thinking itself works best as the exemplar of sample i. Therefore the difference of s( i, k) and the sum shows the evidence sample i thinks sample k is his exemplar---evidence based on the observation of availability and similarity. The updating rule for availability is

a( i, k ) <- min { 0, r( k, k ) + sum { max{ 0, r( j, k) | j <> i, k } } }

As you might see here, the availability is nonpositive (due to the min function). The sum only includes those samples with positive responsibility (namely those samples still regard sample k as a possible exemplar). Therefore the sum with r( k, k) shows the availability of sample k for sample i, since it is a negative value when r( k, k) is negative and few samples take sample k as the exemplar---namely the evidence sample k holds based on its observation of other samples.

After the affinity propagation converges, there are two ways of determining whether a sample is the exemplar: one chooses those samples with r( k, k ) + a( k, k ) > 0; the other chooses those with r( k, k ) + a( k, k ) > r( k, j ) + a( k, j ) satisfied for all j <> k.

One important thing about the algorithm is damping. I haven't explored this part carefully but I do encounter this technique quite frequently. Actually in the training of SRBM and BP with momentum, similar techniques exist. The convex combination of the proposed updating values and the old ones from last update ensures the convergence (why?).

The science paper includes 3 experiments, on facial images, bioinformatic data and a text data of air lines, demonstrating the effectiveness of the algorithm. It's really amazing how well it works. How did they discover this simple but useful technique? This algorithm is designed from (loopy) belief propagation on an elaborate factor graph. I am not familiar with this and have to explore this ASAP.

Here is the important reference site from PSI group.

Multi-Instance Multi-Label Learning with Application to Scene Classification

by Zhi-hua Zhou and Min-Ling Zhang

To solve MIML problems, the authors proposed two solutions: one via MIL and the other via MLL.

The first alternative, via MIL to solve MIML tasks, is quite simple since we are actually working on several independent MIL problems. Therefore any MIL algorithm could be applied here. This paper cited an algorithm called MIBoosting. Though it is written in the paper as a consistent form, I think we are actually training several independent classifier for each label, only the weights are adjusted in the loop of boosting simultaneously. This work comes from others (c.f. [1]) who derived the logistic regression model and boosting model for MIL. [1] is very simple: on logistic regression, they proposed two flavors, one simply predicting with the mean of each sample and the other with mean of log ratio of probability (please notice the training); on the boosting algorithm (bosting a MI learner is trivial), the difference between the original boosting the MIboosting is MIboosting adjusts the weights on bags and the classifier is ok if it yields more correct labels than incorrect ones on a single bag.

The second alternative, via MLL to solve MIML tasks, takes into account of the interactions between labels. Usually, we may notice that certain labels have high-correlations and exploiting this will help build a better classifier. So the problem becomes how to convert a MIL problem into a SIL one. The standard method is something like Lipschitz transform (if the term is correct),, that is to select several medoids from the data and each bag might be formulated as a fixed feature vector whose features come from the medoids and the bag (the distance, here Hausdorff distance). The we can apply MLL algorithm, such as MLSVM [2] to the problem. In fact, MLL is comparatively more difficult to evaluate (there might be missing labels, incorrect labels). [2] compares several strategies in training SVM for MLL problems and several criterion for evaluation. Strategies: MODEL-s labels each data with the label of most significance; MODEL-i doesn't use those samples with multiple labels; MODEL-n add a new class for each multi-labeled sample (that's completely the same labels imply the same class); MODEL-x uses a multi-labeled sample multiple times as positive samples. The criterions for assigning labels: P-criterion assigns a sample with labels when SVM gives a positive value; T-criterion acts differently when all SVM yields negative value (P-criterion puts it unknown) and assigns a label when the corresponding SVM least negative score; C-criterion labels the sample with closed enough outputs of SVMs. [2] finds that MODEL-x with C-criterion works better than other combinations.

References:

• [1] Xin Xu and Eibe Frank: logistic regression and boosting for labeled bag of instances.
• [2] Matthew R. Boutella, Jiebo Luo, Xipeng Shena and Christopher M. Brown: Learning multi-label scene classification.

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?

Modeling Image Patches with a Directed Hierarchy of Markov Random Fields

by Simon Osindero and Geoffrey Hinton

As I have read previously, RBM is the building block of DBM. Here a semi-restricted Boltzmann machine is proposed to model image patches. An SRBM allow lateral connection between visible states.

In this case, the hidden neurons are still conditionally independent given the visible layer. And it's easily seen that it is still a PoE and could be trained with contrastive divergence. The problematic point is that after we sample the hidden states, it's not as easy as in the RBM to sample the visible states. In RBM, a simple mean field approximation will be enough, but SRBM has connections between visible neurons, which means we can't sample each state independent of others. Here a damped mean field approximation is used: each time the mean field approximation and the last time probability (inintial probability is the training sample).

With SRBM, we could model patches from natural images easily, as with RBM. The point of using SRBM instead of RBM is that the correlation between pixels can't be modeled via RBMs. Their experiment shows this point.