Semi-Supervised Learning with Explicit Misclassification Modeling

1 Introduction

In many real-life applications, labeling training data for learn­ ing is costly, sometimes not realistic and often prone to error. For example, for many rapidly evolving data bases available via the web, there is not enough time to label data for differ­ ent information needs. In some cases, like medical diagnosis or biological data analysis, labeling data may require very expensive tests so that only small labeled data sets may be available. In other cases, like object identification in images, noise is inherent in the labeling process.

The statistician and pattern recognition communities were the first to consider the problem of forming discriminant rules us­ ing either partially classified or random misclassified training data in order to cope with this type of situation.

More recently.this idea has motivated the interest of the ma­ chine learning community and many papers now deal with this subject. The use of partially classified data for training, known as semi-supervised learning, has been the subject of intense studies since 1998 and more recently there has been a resurgence of interest for training with misclassified data also called learning in presence of label noise.

We consider here semi-supervised learning for classification. Most approaches to this problem make use of a mixture density model where mixture components are identified as classes. Labeled data are known to belong to exactly one mixture component whereas unlabeled data may belong to any components. Using the Expectation Maximization (EM) algorithm [Dempster et al., 1977], proposed approaches usu­ ally attempt to optimize the likelihood of the whole labeled­ unlabeled data. Starting from an initial labeling, these ap­ proaches proceed by computing at each E-step, tentative labels for unlabeled data using the current parameters of the model and update in the M- step, these parameters us­ ing the estimated labels. Our departure point here is the work of [Amini and Gallinari-a, 2002] who proposed a semi­ supervised discriminant algorithm using a variant form of the CEM algorithm [Celeux and Govaert, 1992]. Discrimina­ tive approaches which attempt to estimate directly posterior class probabilities are often considered superior to generative models which compute these posteriors after learning class conditional densities. Tests on different datasets in [Amini and Gallinari-b, 2002] led to the same conclusion for semi­ supervised learning. Like for other methods, at each step of the algorithm, the model computes tentative labels for unla­ beled data. We extend here the system by incorporating a model which takes into account label errors. This provides an unifying framework for semi-supervised learning and learn­ ing with label noise. To our knowledge, this form of model has not been studied yet. We detail the algorithm for the case of a logistic classifier and give a convergence proof for the general case. We then show experimentally that modeling the stochastic labeling noise, increases notably the perfor­ mance, especially when only small labeled datasets are avail­ able. This paper is organized as follows; we first make a brief review of work on semi-supervised learning and learning in the presence of label noise (section 2). In section 3 we present the formal framework of our model and describe in section 4 the semi-supervised approach we propose. Finally we present a series of experiments on four data sets.

2 Related work

2.1 Learning with both labeled and unlabeled data

The idea of using partially labeled data for learning started in the statistician community at the end of 60's. The seminal paper by [Day, 1969] presents an iterative EM-like approach for learning the parameters of a mixture density under the as­ sumption of multivariate normal components with a common covariance matrix for two group-conditional distributions.

Other iterative algorithms for building maximum likelihood classifiers from labeled and unlabeled data based on the same type of assumption followed [0' Neill, 1978] [McLachlan and Ganesalingam, 1982]. Some other authors have suggested updating procedures for no-normal group conditional densi­ ties using for example kernel methods for modeling mixture components [Murray and Titterington, 1978]. There has been considerably fewer work on discriminative approaches. In his fundamental paper on logistic regression, Anderson sug­ gests modifying a logistic regression classifier to incorporate unlabeled data in order to maximize the likelihood function [Anderson, 1979].

The semi-supervised paradigm has been recently rediscov­ ered by the machine learning community. Most papers pro­ pose mixture density models for combining labeled and unla­ beled data for classification. [Miller and Uyar, 1996] consider a mixture density model where each class is described by sev­ eral component densities. [Roth and Steinhage, 1999] pro­ pose kernel discriminant analysis as an extension to classical linear discriminant analysis. This framework can be used also for semi-supervised learning. [Nigam et al., 2000] propose a semi-supervised EM algorithm which is essentially similar to the_ one in [McLachlan, 1992] but makes use of naive Bayes estimator for modeling the different densities. They present empirical evaluation for text classification tasks. Some au­ thors make use of discriminant classifiers instead of model­ ing conditional densities. For example [Joachims, 1999] pro­ pose a transductive support vector machine which finds pa­ rameters for a linear separator using both the labeled data in the training set and the current test data whose class is un­ known. [Blum and Mitchell, 1998] introduce the co-training paradigm where each sample x is supposed to be described by two modalities. Two classifiers are then used, one for each modality, operating alternatively as teacher and student. This framework can be used for unsupervised and semi-supervised learning. Based on the multi-modal framework introduced by [Blu~ and Mitchell, 1998], [Muslea et al., 2002] propose to combme both active and semi-supervised learning. Since that, different authors have proposed semi-supervised learn­ ing schemes, they usually follow one of the above ideas.

2.2 Learning with imperfectly labeled data

Practical applications of pattern recognition, like eg image classification problems, have motivated in the early 80's some work on the problem of learning in presence of mislabeled data for fully supervised learning. [Chittineni, 1980] ob­ tained error bounds on the performance of the Bayes and nearest neighbor classifiers with imperfect labels. [Krish­ nan, 1988] considered a 2-class classification problem for two group multivariate normal mixture when training samples are subject to random misclassification and derived the likeli­ hood estimation of parameters. [Titterington, 1989] proposed a logistic-normal distribution model and worked out an EM algorithm for the estimation of its parameters. More recently, [Lawrence and Scholkopf, 2001] proposed an algorithm for constructing a kernel Fisher discriminant from training ex­ amples in the presence of label noise.

3 A semi-supervised probabilistic model for mislabeling

We consider here the problem of semi-supervised learn­ ing. We start from the Logistic-CEM algorithm described in [Amini and Gallinari-a, 2002]. It is a generic scheme in the sense that it can be used with any discriminant classifier esti­ mating the posterior class probabilities. The classifier is first trained on labeled data, it then alternates two steps until con­ vergence to a local maximum of the Classification Maximum Likelihood (CML) criterion [Symons, 1981]. Unlabeled data are first labeled using the output of the current classifier. Clas­ sifier parameters are then learned by maximizing the CML function computed using the known labels of labeled data and the current estimated labels for unlabeled data: In this algo­ rithm, at each iteration, labels computed for unlabeled data are considered as desired outputs.

We suppose here that labels from the labeled dataset are cor­ rect and that at each step of this algorithm, labels computed for unlabeled data are subject to error. We propose to model the imperfection of these labels using a probabilistic for­ malism and to Jearn the semi-supervised classifier by taking into account its labeling errors according to this error model. Parameters of the error model and of the classifier will be learned simultaneously in this new algorithm. Compared to the baseline algorithm [Amini and Gallinari-a, 2002], we ex­ plicitly take into account the fact that the current classifier is not optimally trained at each step, since many data labels are missing and are only estimated.

In the following we present the general framework and the learning criterion of our model.

3.1 General framework

We suppose that each example belongs to one and only one class and that there are available a set of n labeled exam­ ples, Dt and a set of m unlabeled examples, Du. A discrim­ inant classifier is to be trained on the basis of these n + m d-dimensional feature vectors 1 x E JRd. For each labeled ex~ ample Xi in Dt, let Ci and ti = { tki }k be respectively the class label and the indicator vector class associated to Xi :

We suppose that for each unlabeled example Xi in Du, there exis~ a perfect and an imperfect label respectively denoted ci and Ci. We propose to model the imperfections in the labels by the following probabilities:

Which are subject to the constraint:

In order to simplify the presentation, we consider in the fol­ lowing a two-class classification problem.

This is not restrictive since we can easily extend the analysis to multi-class cases.

'Components of x could also be discrete

3.2 Classification Maximum Likelihhod estimation in presence of label noise

The baseline semi-supervised discriminant algorithm has been conceived as an extension to classification problems of the CEM algorithm proposed by [Celeux and Govaert, 1992] for clustering. CEM has been first proposed for learning the parameters of gaussian mixtures using as training criterion the classification maximum likelihood criterion initially de­ scribed in [Symons, 1981 ].

McLachlan has extended CML and CEM to the case where both labeled and unlabeled data are used for learning ([McLachlan, 1992], page 39). The CML criterion in this case is the complete-data likelihood and writes:

The algorithm proposed by [McLachlan, 1992] optimizes this criterion for a mixture of normal densities. In their algorithm for training discriminant classifiers on labeled and unlabeled data, [Amini and Gallinari-a, 2002] make use of the following form of the log-classification-likelihood:

This writing makes apparent the posterior probabilities which are directly estimated in their algorithm instead of the condi­ tional densities in [McLachlan, 1992]. As no assumptions are made on the distributional nature of data, maximizing Lc is equivalent to the maximization of L~ ([McLachlan, 1992], page 261).

Let us now introduce our misclassifiction model. For that, we will express the p(c = k I x;) in the second summation in (3) as a function of the mislabeling probabilities and of the posteriorprobabilityofcorrectlabelsp(c = k I x;). Consider

p(x ;, c = k , c = h) can be decomposed with regard to the conditional class probabilities:

Following [Chittineni, 1980] we make the assumption that the density of an example, given its true label, does not depend on its imperfect label:

It then comes:

Using Bayes rule and (1), we get:

p(c = k I x ;) can then be derived fromp( c = k I x;)

From (5), (3) becomes

4 Updating a discriminant function on the basis of labeled and imperfect labeled data

We now present an iterative discriminant CEM algorithm for learning a classifier for semi-supervised learning, which in­ corporates the mislabeling error model. The training criterion is (6). For simplification, we consider a simple logistic classi­ fier [Anderson, 1982], but the algorithm can be easily adapted for training any discriminant classifier. Consider C f3 a logistic classifier with parameters {.Bj}jE{O, ... ,d}· The output of c f3 1 forinputx E JRd isG(x) = 1 ( (.8 ,Bt ))" After .B + exp- o + x have been learned, G(x) and 1- G(x ) are respectively used to estimate p(c = 1 I x) and p(c = 2 I x) . Let, 7r (P) be the current partition for the unlabeled data, a<Pl, ,B(P) the param­ eters for the misclassification model and the logistic classifier at iteration p of the algorithm. The learning criterion (6) is a function of a, .Band 1r . An iterative approach is then adopted for its maximization (algorithm 1). Parameters .B are first ini­ tialized by training the classifier on the labeled dataset D1· Two steps are then iterated until the convergence of criterion L~. In the first step, the classifier is considered as an imper­ fect supervisor for the unlabeled data. Its outputs, G ( x) and 1- G(x), are used to compute the posterior imperfect class probabilities p(c = k I x) for each x in Du and k E { 1, 2}, x is then labeled according to the maximum imperfect output. In the second step, the parameters of the error model and of the classifier are updated using the imperfect labels obtained in the previous step as well as the labeled data. We adopted in this step, a gradient algorithm to maximize (6). An advantage of this method is that it only requires the first order deriva­ tives at each iteration. In the following lemma, we provide a proof of convergence of the algorithm to a local maximum of the likelihood function for semi-supervised training.

Algorithm 1 Semi-supervised learning with imperfect labels

Initialization : Train a discriminant logistic classifier C f3<o> over Dt

For p ~ 0, iterate until the convergence of L~

1. Apply c {3(P) on Du, estimate the imperfect class poste­ rior probabilities using the output Q (P) of the classifier and get an imperfect label for each Xi E Du :

Let 7r(P+l) be the new partition obtained from this clas­ sifier for the unlabeled data.

1. a) Maximize L~ ( 7r(p+l), a(P), ,B(P)) with respect to a (P) subject to constraints 'Vk, 'Vh, a~+l) E (0, 1] and 'Vh "' Q(p+l) - 1

Lemma 1. The modified CML criterion, L~, increases for every sequence ( 1r(p), a(P), ,B(P)) of Algorithm I and the se­ quence L~ ( 1r(p), a(P), ,B(P)) converges to a stationary point.

Proof: we first show that L~ is increasing.

• Since \/xi E Du, ~P+l) = k {::} p(C}.P+l) = k I xi) ~ p(C}.P+l) = k 1 I xi) fork ::j:. k 1 (step 1), we have

Finally as there is a finite number of partitions of the example into 2-classes, the increasing sequence L~ ( 1r(p), a(P), ,B(P)) takes a finite number of values and thus, converges to a sta­ tionary value. ·

In the following section we will present results on four datasets, using a baseline logistic classifier trained with the updating scheme presented above.

5 Experiments

5.1 Data sets

In our experiments we used the Spambase, Credit screening and Mushroom collections from the UCI repository 2 as well as the Computation and Language ( Cmp_lg) collection of TIPSTER SUMMAC 3 for text summarization. Table 1 summarizes the characteris­ tics of these datasets. We removed 37 samples with missing attributes from the Credit data set. For summarization, we adopt the text-span extraction paradigm which amounts at selecting a subset of representative document sentences. This is a classification problem where sentences are to be classi­ fied as relevant or non relevant for the extracted summary. All four problems are two-class classification tasks, Email Spam and Cmp_lg have continuous attributes, Credit vectors are mixed continuous and qualitative, Mushroom attributes are qualitative.

2ftp://ftp.icsS.uci.edu/pub/machine-leaming-databases/

For each dataset, we ran 3 algorithms - the semi-supervised learning algorithm using the label imperfections, the baseline semi-supervised algorithm [Amini and Gallinari-a, 2002] and a fully supervised logistic classifier trained only on the available labeled data. We compared the performance of these algorithms on 20 runs of arbitrary training and test splits, by varying the proportion of labeled-unlabeled data on the training set.

For text summarization, we represent each sentence using a continuous version of features proposed by [Kupiec et a!., 1995]. This characterization has given good re­ sults in previous work [Amini and Gallinari-b, 2002]. Each sentence i, with length l(i) is characterized by Xi = (<Pi, cp~, cp~, cpL cp~ ), where cpi = PbJ is the nor! . d t 1 th i frequency of cue words in i rna 1ze sen ence eng , cp2 = t( i) is the normalized number of cue words in sentence i , i frequency of acronyms in i · th 1 . d cp3 = l(i) IS e norma 1ze number of acronyms in i, cp~ is the position indicator feature (beginning, middle or end of the document) and cp~ is the normalized number of terms within a generic query q and i. q corresponds to the most frequent words in the training set.

5.2 Evaluation measures

For the three UCI datasets there is approximately the same proportion of examples for each class (table 1). We used as performance criterion the percentage of good classification (PGC) defined as:

# of examples in the test set well classified by the syst

PGC = ___ ..::...._----:-:---:---.,---,---,------=---=- # of examples in the test set

For text summarization, we followed the SUMMAC evalua­ tion by using a 10% compression ratio. Hence, for each doc­ ument in the test set we have formed its summary by select­ ing the top 10% sentences having higher score with respect to the output of the classifier. For evaluation we compared these extractive sentences with the desired summary of each document. The desired extractive summaries were generated from the abstract of each article using the text-span alignment method described in [Banko et a!., 1999]. Since the examples, PGC is meaningless, we used the average preci­ sion (AP) measure for the evaluation. Let~, be the number of sentences extracted by the system which are in the target summaries, and a, be the total number of sentences extracted by the system. The precision is defined as the ratio ~/a.

3 http://www.itl.nist.gov/iaui/894.02/related_projects/tipster_summac/ collection is not well balanced between positive and negative

5.3 Results

For each dataset and each cross validation, 25% of examples are held aside as a test set. We vary the percentage of labeled­ unlabeled data in the remaining 75% training set ofthe collec­ tions. Figure 1, shows the performance on the test sets for the four datasets as a function of the proportion of labeled data in the training set. On the x-axis, 5% means that 5% of data in the training set were labeled for training, the 95% remaining being used as unlabeled training data. Each experiment was carried on twenty paired trials of randomly selected training­ test splits. On the y-axis, each point represents the mean per­ formance for the 20 runs and the error bars correspond to the standard deviation for the estimated performance [Tibshirani,

1996].

All figures exhibit the same behavior. In all four datasets, semi-supervised algorithms are over the baseline classifier trained only on the labeled training data. For example, if we consider text summarization, using only 5% of labeled sentences, our algorithm allows to increase performance by 15% compared to a fully supervised algorithm trained on the 5%. 15% labeled data are needed to reach the same performance with the baseline method. Our model is uni­ formly better than the two reference models used in our ex­ periments. It provides an important performance increase es­ pecially when there are only few labeled data available which is the most interesting situation in semi-supervised learning. For the Credit card problem, the dataset is small and semi-supervised learning allows for a smaller increase of per­ formance than for other datasets where there are a lot of un­ labeled data available. Semi-supervised learning allows to reach 'optimal' performance with about 50% of labeled data (only 30% for the Mushroom set).

6 Conclusion

We have described how to incorporate a label error model into an iterative semi-supervised discriminant algorithm. We have detailed a version of this general algorithm in the case of a simple logistic classifier, shown its convergence and proved empirically its efficiency on four datasets with dif­ ferent characteristics. The algorithm allows for an impor­ tant performance increase compared to a reference efficient semi-supervised algorithm without mislabeling model. The main contribution of the paper is to provide a general frame­ work for handling simultaneously semi-supervised learning and learning in the presence of label noise. The noise model we have used is simple and allows for efficient estimations in the semi-supervised setting. More sophisticated models have still to be investigated. However, our experience is that sim­ ple models do often perform better when only few labeled data are available.