Semi-Supervised Learning from a Translation Model between Data Distributions

1 Introduction

In the last years, the task of semi-supervised classification has attracted a considerable amount of research in machine learning and pattern recognition [Singh et al., 2008]. Broadly, this task consists of learning a classifier from a training set composed of both labeled and unlabeled data. The motivation of semi-supervised classification stems from the use of unlabeled data to help build a better classifier from the labeled data. This is of great interest in many real-world applications [Cherniavsky et al., 2010; Bandos et al., 2006], mainly in those in which the acquisition of labeled data is quite expensive and time consuming, whereas a large amount of unlabeled data is far easier to obtain.

There are actually two different semi-supervised learning settings, namely transductive and inductive semi-supervised learning [Zhu and Goldberg, 2009]. In the transdutive setting, the goal is to predict only the labels of the unlabeled data in the training set. In addition, the inductive semi-supervised learning is aimed at devising a good classifier on future data, beyond the training set.

We focus our research on the inductive setting. That is, given a training set T ⊆ X that includes a set of labeled instances L (L ⊆ T ), the goal is to train a classifier in order to predict the labels for the instances in X. Specifically, in this paper we address the task in which the labels are binary by introducing a new probabilistic classification model.

The novelty of our proposal consists of measuring distributional relationships between the labeled data and the instances in X. To this end, the approach relies on a stochastic translation model between distributions from a mixture, which is also introduced in this paper. The proposed method combines the stochastic translation model with a kernel logistic regression on labeled data to define the probabilistic classifier.

The proposal can be contextualized into the class of those stochastic (generative) semi-supervised methods that estimate conditional prediction models. Traditionally, these methods have been focused on estimating structured models such as conditional random fields [Mann and Mccallum, 2008; Dillon et al., 2010], and they have been mainly applied to discrete data such as texts.

On the other hand, this work can be seen as an extension to the inductive setting of the classifier derived from the semisupervised multi-task learning framework presented in [Liu et al., 2009]. In that work, authors rely on t-step Markov transition probabilities between the training points to learn their conditional predictive model. In our case, we consider arbitrary Markov chains on mixture distributions to setup the stochastic translation model. This allows us both to directly apply our approach to the inductive setting, and to base the method on local and global knowledge from the data.

The rest of this paper is organized as follows. In Section 2, we present the proposed probabilistic model for semisupervised classification. Section 3 describes some experiments for validating the performance on both synthetic and real-world data sets. Finally, in Section 4 we provide some conclusions and future work.

2 The Probabilistic ClassificationModel

In order to address our semi-supervised classification task, we rely on the latent structure of data X given by a mixture model:

where x ∈ X, ∀i ∈ {1, . . . ,m} gi represents a probability distribution, p(gi) is the prior for gi, and p(x|gi) represents the probability of generating data point x from gi. Such a mixture can be obtained from the training set T by typically applying an Expectation-Maximization algorithm, Latent Dirichlet Allocation in the case of discrete data [Blei et al., 2003], or a Dirichlet Process Mixture Model [Rasmussen,

2000]. In our experiments, we consider both Dirichlet processes and data spectroscopy [Shi et al., 2008] to learn this mixture.

Let G denotes the set of probability distributions {g1, . . . , gm} from the mixture shown in Equation 1. In this work, the distributions in G are aimed at measuring distributional relationships between the labeled data in L and the data points in X. In this way, for all x′ ∈ L and all x ∈ X we can define a posterior probability for x′ given x as:

where p(gi|x) = p(x|gi)p(gi)/p(x) (from Bayes' theorem), and t(gi|gj ) represents some posterior probability for gi given gj . 1

In this paper, we define t(gi|gj) as the probability of transforming or translating gj into gi by regarding the overall structure of distributions from the mixture shown in Equation 1. We refer to {t(gi|gj)}gi,gj∈G as the (stochastic) translation model between mixture distributions.

Accordingly, p(x′ |x) can be thought of as a measure of how likely x can be transformed into x′ . Hence, a straightforward definition for the posterior probability of class y ∈ Y given x ∈ X can be determined by:

where p∗ (y|x′ ) is an estimation of the probability of including the labeled point x′ in class y.

Thus, in our proposal each data point x ∈ X can be classified as belonging to class y∗ (x) according to the rule:

where p(y|x) is defined as in Equation 3.

The next subsections are devoted to describe the estimation of both (i) the stochastic translation model between mixture distributions (i.e., {t(gi|gj)}gi,gj∈G), and (ii) the class posteriors conditioned on the labeled points (i.e., {p∗ (y|x′ )}y∈Y,x′∈L).

2.1 Translation BetweenMixture Distributions

For estimating the translation model {t(gi|gj)}gi,gj∈G, we consider Markov chains between the mixture distributions.

In a generative model of Markov chains between distributions, the generation of a chain 〈gi1 gi2 . . . gik 〉 starting with distribution gi1 stems from the model:

where α is the probability of adding a new distribution to the chain being generated, and p(gb|ga) typically represents the probability of generating the distribution gb immediately after ga in a chain.

1 The values p(x|gi), p(gi) and p(x) are defined from Equation 1. Both x ∈ X and x′ ∈ L, in p(x|g) and p(x′ |g) respectively, are drawn according to the same distribution.

Currently, we propose two approaches for estimating the conditional probability p(gb|ga) from the training set T . The first one simply relies on the chain rule to define the conditional densities as follows:

On the other hand, the second approach estimates p(gb|ga) from a given metric h between distributions in the following manner:

where h0 is a given distribution width. Notice that different from the first approach, in this case we compare two probability distribution without considering their context in the modeling of data X (i.e., their priors are disregarded).

The rationale here is to rely on the method based on the chain rule when both (a) the underlying distribution of the training set T approaches the true underlying distribution of actual data X, and (b) the distributions reveal some chaining effect to conform the class structures. Otherwise, we consider the distance-based method to estimate the conditional probabilities p(ga|gb).

Overall, {p(gb|ga)}ga,gb∈G can be seen as a translation model [Berger and Lafferty, 1999] that expresses the likelihood of translating distribution ga into gb in one translation step. In this way, a distribution chain of length k starting at distribution ga and ending at gb can be seen as a translation sequence that translates ga into gb in k steps.

Consequently, the overall probability of translating a distribution gj into gi can be defined as the probability of generating an arbitrary chain starting at gj and ending at gi, and hence:

This definition can be summarized in the following closed form [Lafferty and Zhai, 2001]:

where I is the m × m identity matrix, and P is a m × m matrix whose element Pi,j is defined as p(gi|gj).

2.2 Class Posteriors Conditioned on Labeled Points

In this work, the estimation of the conditional probabilities {p∗ (y|x′ )}y∈Y,x′∈L is based on Kernel Logistic Regression [Roth, 2001].

Typically, given a set of kernel functions {K1, . . . ,Km} with domain X and a discrete random variable Y (taking values in {-1, 1}), a kernel-based logistic regression model computes the posterior probability of a value y ∈ Y conditioned on x ∈ X as follows:

where ∀i ∈ {0, . . . ,m} βi is a scalar coefficient.

For estimating the probability of including the labeled point x′ ∈ L in the class y ∈ Y, we follow Equation 10. However, we properly rely on the mixture distributions g1, . . . , gm instead of using traditional kernel functions in our estimation. Note that this is feasible since each distribution corresponds to a probability density function.

Therefore, we define p∗ (y|x′ ) as the parameterized regression:

Several optimization methods can be applied to estimate vector β. In [Roth, 2001], it has been shown that kernel logistic regression can be learned in the primal using Newton's method. Thus, in this work we estimate β by considering a Newton-like method for maximizing the log-posterior:

where y(x′ ) is the class label associated to the labeled point x′ ∈ L.

Starting from an initial value of β, namely β(0), the Newton-like method iteratively approaches the value of vector β until convergence by using the following updating equation in the kth iteration:

where the scalar value γ is the learning step (γ > 0), and H and g represent the Hessian matrix and the gradient vector respectively of the regularized ℓ(β) at β = β(k - 1).

Notice that the overall formulation of our methodology can be seen as a combination of two models: (i) the model of labeled data conditioned on the domain data {p(x′ |x)}x∈X ,x′∈L, and (ii) the model of class posteriors conditioned on the labeled data {p∗ (y|x′ )}y∈Y,x′∈L. Actually, in the learning mechanism parameterization only affects the second model (i.e. only a component of the overall model) since the estimation of the probabilities p(x′ |x) is performed in an unsupervised manner. Thus, the overall model can be considered as a partially parameterized one.

3 Experiments

In order to validate the proposal here presented, we consider both synthetic and real-world evaluation data sets. The performance of the classification is evaluated in terms of the Accuracy measure, defined as the ratio of the number of correctly classified data over the total number of data being tested.

For each data set X , the experimentation is carried out considering different training and test sets, and also different labeled sets from each training set. Specifically, for each data set X, and given a size l for the labeled data set, we consider 25 different triplets of training, labeled and test sets, which are generated as follows.

Firstly, we randomly sample a uniform partition X = X1 ∪ . . . ∪ X5. Then, for each i ∈ {1, . . . , 5}, we define both a training and a test set fromX as X \Xi and Xi respectively. Finally, from each training set X \ Xi, we randomly sample 5 labeled data sets Li1 , . . . ,Li5 , each one of size l. We report the results for different values of l in each data set X by averaging the accuracy on their corresponding 25 test sets.

Our experimentation is mainly focused on the following issues:

1. Measure the impact of combining the kernel logistic regression with the proposed translation model between distributions. With this aim, we compare our model with a Kernel Logistic Classifier (KLC) [Roth, 2001].
2. Compare our approach with existing most related work. That is, a version of the Semi-Supervised Single Task Learning (SS-STL) classifier derived from [Liu et al., 2009]. This is also useful for measuring the impact of using the translation model between distributions, instead of t-step Markov transition probabilities between training points.

To ensure a fair comparison, the underlying kernels for both KLC and SS-STL were given by the mixture distributions learned from the training sets.

3.1 Synthetic Data Sets

As for synthetic data, we consider the two toy data sets represented in left column of Figure 1. These data sets are uniformly divided into 2 classes. The first data set (moons) consists of 600 points in the real plane, whereas the second one (p-moons) comprises 1000 data points.

In this case, for generating the mixture models we regard the unsupervised mixture generation given by Dirichlet processes as defined in [Rasmussen, 2000]. Thus, for each training set we regard a gaussian mixture to carry out the semi-supervised classification. The second column of Figure 1 shows one of the training samples generated from the databases together with the respective gaussian mixture distributions learned from the sample. It is worth mentioning that the mixture generation process produced some spatial confusion according to the actual class distributions in some training sets.

In tables 1 and 2, we show the results obtained over moons and p-moons data sets respectively. We consider two versions of our proposal, namely T-Chain and T-Distance, obtained from the use of the chain rule and the distance-based approaches respectively for estimating the translation model between distributions (see equations 6 and 7).

For the version T-Distance, we rely on the well-known Hellinger distance as the metric between distributions. The distribution width h0 was conveniently defined as the third part of the average distance between each gaussian and its nearest (gaussian) neighbor in the mixture model. The parameter α in the translation model can be seen as a confidence on the chaining effect of the mixture distributions. Thus, we consider a large α for version T-Chain (α = 0.99), and a small α for T-Distance (α = 0.10). Since SS-STL is a transductive method, the results reported for this method on the test data correspond to the base kernel classifier embedded in its own methodology.

As it can be seen, our two versions consistently outperforms both KLC and SS-STL. Particularly, version T-Chain performs largely better than T-Distance. This was expected on these data sets since we perceived from Figure 1 that the mixture model learned from T accurately approaches the actual underlying distribution of data X, and there is a certain overlapping degree between gaussians that generates subsets of the same class with a high likelihood. It can be noticed that a distance-based criterion can produce some uncertainty on the conditional probability between gaussians in the extremes of the moons.

Currently, learning from very few labeled samples is a challenging issue in semi-supervised classification. In these data sets, it can be appreciated that T-Chain obtains a small number of misclassified data despite of the size of the labeled data set. Notice also that in the case of p-moons this version correctly classifies the entire dataset from l0 labeled instances. We estimate that when the number of labeled samples is large enough so that the randomly selected labeled points tend to spatially cover the class distributions, the performance of all of these methods will be similar.

3.2 Real-World Data Sets

For the case of real-world data sets, we test our approach using two binary databases from the UCI repository, namely Ionosphere and Wisconsin Breast Cancer (WBC). The Ionosphere database is a collection of radar data obtained by a system in Goose Bay, Labrador. This database comprises 351 instances described by 34 continuous attributes. On the other hand, WBC database includes 683 samples, each one consisting of 9 features taken from fine needle aspirates from a patient's breast. All 9 features were graded on an integer scale from 1 to 10.

Since these databases consists of a small number of samples according to their dimensionality, we avoid the use of Dirichlet processes to generate the mixture models (currently, they need a very large number of iterations to converge). Instead, we consider data spectroscopy [Shi et al., 2008] to efficiently produce a mixture of gaussian distributions from the training sets.

Our aim was to generate a number of gaussians from each mixture so that the entropy value of the classes conditioned on each gaussian distribution was small. This caused a relative large separation between the gaussian distributions within each mixture learned, which in turn impacts negatively on the chaining effect between the distributions. In this way, the results obtained by T-Chain do not significantly improve those obtained by KLC and SS-STL. Note that this problem is overcome by T-Distance.

Figures 2 and 3 show the results obtained over Ionosphere and WBC respectively. In these figures we show in the left and right columns the average accuracy values obtained over the unlabeled samples in the training sets and the test samples respectively.

Several observations can be made by analyzing these figures. Firstly, it can be seen that T-Distance has a good performance on unseen data (i.e., on the test data sets). This corroborates the usefulness of our proposal for the inductive semi-supervised task, which is the main purpose of this work. Indeed, T-Distance significantly outperforms both KLC and SS-STL on test data.

Secondly, it can be appreciated that despite SS-STL performs the best on the unlabeled data fromWBC, this method is not appropriate for inductive learning. It suffer from some overfitting, which can be explained from both (i) the unstable behavior of it accuracy curve on unseen data and (ii) the similarity of this curve with that of KLC (i.e., SS-STL performs similar to a pure supervised classifier). On the other hand, it can be clearly observed that our approach obtains stable and similar results on both transductive and inductive semi-supervised learning.

The performance improvement over KLC validates the combination of logistic regression with the proposed translation model, whereas the improvement over SS-STL measures the positive impact of translating from Markov chains on mixture distributions instead of using t-step Markov transition probabilities between the training points for inductive learning.

4 Conclusions

In this paper, a new semi-supervised probabilistic classification model has been introduced. The proposal exploits the local and global context of the data by measuring distributional relationships between the labeled and unlabeled data. This is carried out from a stochastic translation model between data distributions, which allows our method to be directly applied to unseen data within the semi-supervised learning task.

The proposed learning mechanism combines both the stochastic translation model and a kernel logistic regression on labeled data. Experimentally, we tested two approaches derived from the methodology on synthetic and real-world data sets. The obtained results corroborates the usefulness of our proposal for the semi-supervised classification task.

Future works include extending this methodology to the multiclass setting. This can be easily achieved since the learning mechanism relies on logistic regression, which is suitable for the multiclass learning problem.

Acknowledgments

This work has been supported by the Spanish Ministry of Science and Innovation under projects Consolider Ingenio 2010 CSD2007-00018 and TIN2008-01825/TIN, and by the project P1-1B2009-45 of Fundaci ´o Caixa-Castell ´o.