Semi-Supervised Learning for Multi-Component Data Classification

1 Introduction

Data samples such as web pages and multimodal data usually contain main and additional information. For example, web pages consist of main text and additional components such as hyperlinks and anchor text. Although the main content plays an important role when designing a classifier, additional content may contain substantial information for classification. Recently, classifiers have been developed that deal with multicomponent data such as web pages [Chakrabarti et al., 1998; Cohn and Hofmann, 2001; Sun et al., 2002; Lu and Getoor, 2003], technical papers containing text and citations [Cohn and Hofmann, 2001; Lu and Getoor, 2003], and music data with text titles [Brochu and Freitas, 2003].

In supervised learning cases, existing probabilistic approaches to classifier design for arbitrary multi-component data are generative, discriminative, and a hybrid of the two. Generative classifiers learn the joint probability model, p(x, y), of feature vector x and class label y, compute P(y|x) by using the Bayes rule, and then take the most probable class label y. To deal with multiple heterogeneous components, under the assumption of the class conditional independence of all components, the class conditional probability density p(xj |y) for the jth component xj is individually modeled [Brochu and Freitas, 2003]. By contrast, discriminative classifiers directly model class posterior probability P(y|x) and learn mapping from x to y. Multinomial logistic regression [Hastie et al., 2001] can be used for this purpose.

It has been shown that discriminative classifiers often achieve better performance than generative classifiers, but that the latter often provide better generalization performance than the former when trained by few labeled samples [Ng and Jordan, 2002]. Therefore, hybrid classifiers have been proposed to take advantage of the generative and discriminative approaches [Raina et al., 2004]. To construct hybrid classifiers, the generative model p(xj |y) of the jth component is first designed individually, and all the component models are combined with weight determined on the basis of a discriminative approach. It has been shown experimentally that the hybrid classifier performed better than pure generative and discriminative classifiers [Raina et al., 2004].

On the other hand, a large number of labeled samples are often required if we wish to obtain better classifiers with generalization ability. However, in practice it is often fairly expensive to collect many labeled samples, because class labels are manually assigned by experienced analysts. In contrast, unlabeled samples can be easily collected. Therefore, effectively utilizing unlabeled samples to improve the generalization performance of classifiers is a major research issue in the field of machine learning, and semi-supervised learning algorithms that use both labeled and unlabeled samples for training classifiers have been developed (cf. [Joachims, 1999; Nigam et al., 2000; Grandvalet and Bengio, 2005; Fujino et al., 2005b], see [Seeger, 2001] for a comprehensive survey).

In this paper, we focus on Semi-Supervised Learning for Multi-Component data classification (SSL-MC) based on probabilistic approach and present a hybrid classifier for SSLMC problems. The hybrid classifier is constructed by extending our previous work for semi-supervised learning [Fujino et al., 2005b] to deal with multiple components. In our formulation, an individual generative model for each component is designed and trained on labeled samples. When there are few labeled samples, the class boundary provided by the trained generative models is often far from being the most appropriate one. Namely, the trained generative models often have a high bias as a result of there being few labeled samples. To mitigate the effect of the bias on classification performance, for each component, we introduce a bias correction model. Then, by discriminatively combining these models based on the maximum entropy principle [Berger et al., 1996], we obtain our hybrid classifier. The bias correction models are trained by using many unlabeled samples to incorporate global data distribution into the classifier design.

We can consider some straightforward applications of the conventional generative and discriminative semi-supervised learning algorithms [Nigam et al., 2000; Grandvalet and Bengio, 2005] to train the above-mentioned classifiers for multicomponent data. Using three test collections such as web pages and technical papers, we show experimentally that our proposed method is effective in improving the generalization performance of multi-component data classification especially when the generative and discriminative classifiers provide similar performance.

2 Straightforward Approaches to Semi-supervised Learning

2.1 Multi-component Data Classification

In multi-class (K classes) and single-labeled classification problems, one of the K classes y ∈ {1, . . . , k, . . . ,K} is assigned to a feature vector x by a classifier. Here, each feature vector consists of J separate components as x = {x1 , . . . , xj , . . . , xJ }. In semi-supervised learning settings, the classifier is trained on both labeled sample set Dl = {xn, yn}Nn=1 and unlabeled sample set Du = {xm}Mm=1. Usually, M is much greater than N. We require a framework that will allow us to incorporate unlabeled samples without class labels y into classifiers. First, we consider straightforward applications of conventional semi-supervised learning algorithms [Nigam et al., 2000; Grandvalet and Bengio, 2005] with a view to incorporating labeled and unlabeled samples into generative, discriminative, and hybrid classifiers proposed for multi-component data.

2.2 Generative Classifiers

Generative classifiers model a joint probability density p(x, y). However, such direct modeling is hard for arbitrary components that consist of completely different types of media. To deal with multi-component data in the generative approach, under the assumption that all components have class conditional independence, the joint probability model can be expressed as p(x, k;Θ) = P(k) ∏Jj=1 p(xj |k; θjk ) (cf. [Brochu and Freitas, 2003]), where θjk is the jth component model parameter for the kth class and Θ = {θjk }j,k is a set of model parameters. Note that the class conditional probability model p(xj |k; θjk ) should be selected according to the features of the jth component. The class posteriors for all classes are computed according to the Bayes rule, such as

where ˆΘ = {ˆθjk }j,k is a parameter estimate set. The class label y of x is determined as the k that maximizes P (k|x; ˆΘ).

For the semi-supervised learning of the generative classifiers, unlabeled samples are dealt with as a missing class label problem, and are incorporated in a mixture of joint probability models [Nigam et al., 2000]. That is, xm ∈ Du is drawn from the marginal generative distribution p(x;Θ) = ∑Kk=1 p(x, k;Θ). Model parameter set Θ is computed by maximizing the posterior p(Θ|D) (MAP estimation). According to the Bayes rule, p(Θ|D) ∝ p(D|Θ)p(Θ), we can provide the objective function of model parameter estimation such as

Here, p(Θ) is a prior over Θ. We can obtain the Θ value that maximizes F(Θ) using the Expectation-Maximization (EM) algorithm [Dempster et al., 1977].

The estimation of Θ is affected by the number of unlabeled samples used with labeled samples. In other words, when N ≪ M, model parameter Θ is estimated as almost unsupervised clustering. Then, training the model by using unlabeled samples might not be useful in terms of classification accuracy if the mixture model assumptions are not true for actual classification tasks. To mitigate the problem, a weighting parameter λ ∈ [0, 1] that reduces the contribution of the unlabeled samples to the parameter estimation was introduced (EM-λ [Nigam et al., 2000]). The value of λ is determined by cross-validation so that the leave-one-out labeled samples are, as far as possible, correctly classified.

2.3 Discriminative Classifiers

Discriminative classifiers directly model class posterior probabilities P(y|x) for all classes. We can design a discriminative model P(y|x) without the separation of components. In Multinomial Logistic Regression (MLR) [Hastie et al., 2001], the class posterior probabilities are modeled as

where W = {w1, . . . ,wk, . . . ,wK} is a set of unknown model parameters. wk · x represents the inner product of wk and x.

Certain assumptions are required if we are to incorporate unlabeled samples into discriminative classifiers, because p(x) is not modeled in the classifiers. A Minimum Entropy Regularizer (MER) was introduced as one approach to the semi-supervised learning of discriminative classifiers [Grandvalet and Bengio, 2005]. This approach is based on the empirical knowledge that classes should be well separated to take advantage of unlabeled samples because the asymptotic information content of unlabeled samples decreases as classes overlap. The conditional entropy is used as a measure of class overlap. By minimizing the conditional entropy, the classifier is trained to separate unlabeled samples as well as possible.

Applying MER to MLR, we estimate W to maximize the following conditional log-likelihood with the regularizer:

Here, λ is a weighting parameter, and p(W) is a prior over W. A Gaussian prior [Chen and Rosenfeld, 1999] is often employed as p(W).

2.4 Hybrid Classifiers

Hybrid classifiers learn an individual class conditional probability model p(xj |y; θjy ) for the jth component and directly model the class posterior probability by using the trained component models [Raina et al., 2004; Fujino et al., 2005a]. Namely, each component model is estimated on the basis of a generative approach, while the classifier is constructed on the basis of a discriminative approach. For the hybrid classifiers, the class posteriors are provided as

where ˆΘ = {ˆθj,k}j,k is a parameter estimate set of component generative models {p(xj |k; θjk )}j,k, and Γ = {{γj}Jj=1 , {μk}Kk=1} is a parameter set that provides the combination weights of components and class biases. In supervised learning cases, Γ is estimated to maximize the crossvalidation conditional log-likelihood of labeled samples.

To incorporate unlabeled samples in the hybrid classifiers, we can consider a simple approach in which we train the component generative models using EM-λ as mentioned in Section 2.2. With this approach, we incorporate unlabeled samples into the component generative models and then discriminatively combine these models. For convenience, we call this approach Cascade Hybrid (CH).

3 ProposedMethod

As mentioned in the introduction, we propose a semisupervised hybrid classifier for multi-component data, where bias correction models are introduced to use unlabeled samples effectively. For convenience, we call this classifier Hybrid classifier with Bias Correction Models (H-BCM classifier). In this section, we present the formulation of the HBCM classifier and its parameter estimation method.

3.1 Component Generative Models and Bias Correction

We first design an individual class conditional probability model (component generative model) p(xj |k; θjk ) for the jth component xj of data samples that belong to the kth class, where Θ = {θjk }j,k denotes a set of model parameters over all components and classes. In our formulation, the component generative models are trained by using a set of labeled samples, Dl. Θ is computed using MAP estimation: ˆΘ = maxΘ{logp(Dl|Θ) + logp(Θ)}. Assuming Θ is independent of class probability P(y = k), we can derive the objective function for Θ estimation as

Here, p(θjk ) is a prior over θjk .

When there are few labeled samples, the classifier obtained by using the trained component generative models often provides a class boundary that is far from the most appropriate one. Namely, the trained component generative models often have a high bias. To obtain a classifier with a smaller bias, we newly introduce another class conditional generative model per component, called bias correction model. The generative and bias correction models for each component belong to the same model family, but the set of parameters Ψ = {ψjk }j,k of the bias correction models is different from Θ. We construct our hybrid classifier by combining the trained component generative models with the bias correction models to mitigate the effect of the bias.

3.2 Discriminative Class Posterior Design

We define our hybrid classifier by using the class posterior probability distribution derived from a discriminative combination of the component generative and bias correction models. The combination is provided based on the Maximum Entropy (ME) principle [Berger et al., 1996].

The ME principle is a framework for obtaining a probability distribution, which prefers the most uniform models that satisfy any given constraints. Let R(k|x) be a target distribution that we wish to specify using the ME principle. A constraint is that the expectation of log-likelihood, log p(xj |k; ˆθjk ), with respect to the target distribution R(k|x) is equal to the expectation of the log-likelihood with respect to the empirical distribution ˜ p(x, k) = ∑Nn=1 δ(x - xn, k - yn)/N of the training samples as

where ˜ p(x) = ∑Nn=1 δ(x -xn)/N is the empirical distribution of x. The equation of the constraint for logp(xj |k;ψjk ) can be represented in the same form as Eq. (7). We also restrict R(k|x) so that it has the same class probability as seen in the labeled samples, such that

By maximizing the conditional entropy H(R) = - ∑x,k ˜ p(x)R(k|x) logR(k|x) under these constraints, we can obtain the target distribution:

where Γ = {{γ1j, γ2j}Jj=1 , {μk}Kk=1} is a set of Lagrange multipliers. γ1j and γ2j represent the combination weights of the generative and bias correction models for the jth component, and μk is the bias parameter for the kth class. The distribution R(k|x, ˆΘ,Ψ, Γ) gives us the formulation of the discriminative classifier, which consists of the trained component generative models and the bias correction models.

According to the ME principle, the solution of Γ in Eq. (9) is the same as the Γ that maximizes the log-likelihood for R(k|x; ˆΘ,Ψ, Γ) of labeled samples (xn, yn) ∈ Dl [Berger et al., 1996; Nigam et al., 1999]. However, Dl is also used to estimate Θ. Using the same labeled samples for both Γ and Θ may lead to a bias estimation of Γ. Thus, a leave-oneout cross-validation of the labeled samples is used to estimate Γ [Raina et al., 2004]. Let ˆΘ(-n) be a generative model parameter set estimated by using all the labeled samples except (xn, yn). The objective function of Γ then becomes

where p(Γ) is a prior over Γ. We used the Gaussian prior [Chen and Rosenfeld, 1999] as p(Γ) ∝ ∏k exp(-μ2k /2ρ2) ∏l,j exp{-(γlj-1)2/2σ2}. Global convergence is guaranteed when Γ is estimated with fixed ˆΘ(-n) and Ψ, since F2(Γ|Ψ) is an upper convex function of Γ.

3.3 Training Bias Correction Models

In our formulation, the parameter set Ψ of the bias correction models is trained with unlabeled samples to reduce the bias that results when there are few labeled samples. According to R(k|x; ˆΘ,Ψ, Γ) as shown in Eq. (9), the class label y of a feature vector x is determined as the k that maximizes the discriminative function:

Here, when the values of gk(x;Ψ) for all classes are small, the classification result for x is not reliable, because gk(x; Ψ) is almost the same for all classes. Thus, we expect our classifier to provide a large gk(x;Ψ) difference between classes for unseen samples, by estimating Ψ that maximizes the sum of the discriminative function of unlabeled samples:

where p(Ψ) is a prior over Ψ. We incorporate unlabeled samples into our hybrid classifier directly by maximizing F3(Ψ|Γ) in the same way as for a mixture model in generative approaches, where joint probability models are regarded as discriminative functions.

If Γ is known, we can estimate the Ψ that provides the local maximum of F3(Ψ|Γ) around the initialized value of Ψ, with the help of the EM algorithm [Dempster et al., 1977]. However, Γ is not a known value but an unknown parameter that should be estimated using Eq. (10) with Θ and Ψ fixed. Therefore, we estimate Ψ and Γ iteratively and alternatively. Ψ and Γ are updated until some convergence criterion is met.

4 Experiments

4.1 Test Collections

Empirical evaluations were performed on three test collections: WebKB 1 , Cora 2 , and 20newsgroups (20news) 3 datasets, which have often been used as benchmark tests for classifiers in text classification tasks [Nigam et al., 1999].

WebKB contains web pages from universities. This dataset consists of seven categories, and each page belongs to one of them. Following the setup in [Nigam et al., 1999], we used only four categories: course, faculty, project, and student. The categories contained 4199 pages. We extracted four components, Main Text (MT), Out-Links (OL), In-Links (IL), and Anchor-Text (AT), from each page. Here, MT is the text description except for tags and links. The OL for a page consists of web page URLs linked by the page. The IL for a page is the set of web page URLs linking the page. AT is the anchor text set for each page, which consists of text descriptions expressing the link to the page found on other web pages. We collected IL and AT from the links within the dataset. For the MT and AT components, we removed stop words and vocabulary words included in only one web page. We also removed URLs included in only one page for the OL and IL components. There were 18525 and 496 vocabulary words in the MT and AT of the dataset, respectively. OL and IL contained 4131 and 500 different URLs, respectively.

Cora contains more than 30000 summaries of technical papers, and each paper belongs to one of 70 groups. For our evaluation, we used 4240 papers included in 7 groups: /Artificial Intelligence/Machine Learning/*. We extracted three components, Main Text (MT), authors (AU), and citations (CI) from each paper. Here, MT consists of the text distribution included in the papers, and AU is the set of authors. CI consists of citations to other papers. We removed vocabulary words, authors, and cited papers for each component in the same way as for WebKB. There were 9190 vocabulary words, 1495 authors, and 13282 cited papers in the dataset.

20news consists of 20 different UseNet discussion groups. Each article belongs to one of the 20 groups. The test collection has been used to evaluate a supervised hybrid classifier for multi-component data [Raina et al., 2004]. Following the setup in [Nigam et al., 1999], we used only five groups: comp.*. There were 4881 articles in the groups. We extracted two components, Main (M) and Title (T), from each article, where T is the text description following "Subject:" and M is the main content of each article except for the title. We removed stop words and vocabulary words included in only one article. There were 19273 and 1775 vocabulary words in components M and T of the dataset, respectively.

4.2 Experimental Settings

We used a naive Bayes (NB) model [Nigam et al., 2000] as a generative model and a bias correction model for each component, assuming that different features (works, links, citations, or authors) included in the component are independent. xj was provided as the feature-frequency vector of the jth component. For the MAP estimation in Eqs (2), (6), and (12), we used Dirichlet priors as the priors over NB model parameters.

1 http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo20/www/data/webkb-data.gtar.gz

2 http://www.cs.umass.edu/˜mccallum/data/cora-classify.tar.gz

3 http://people.csail.mit.edu/jrennie/20Newsgroups/20news18828.tar.gz

For our experiments, we randomly selected labeled, unlabeled, and test samples from each dataset. We made ten different evaluation sets for each dataset by this random selection. 1000 data samples from each dataset were used as the test samples in each experiment. 2500, 2000, and 2500 unlabeled samples were used with labeled samples for training these classifiers in WebKB, Cora, and 20news, respectively. The average classification accuracy over the ten evaluation sets was used to evaluate the methods.

We compared our H-BCM classifier with three semisupervised classifiers for multi-component data as mentioned in Section 2: an NB based classifier with EM-λ [Nigam et al., 2000], an NLR classifier with MER (MLR/MER) [Grandvalet and Bengio, 2005], and a CH classifier. We also examined three supervised classifiers: NB, MLR, and hybrid (HY) classifiers. NB, MLR, and HY classifiers were trained only on labeled samples.

In our experiments, for EM-λ, the value of weighting parameter λ was set in the manner mentioned in Section 2.2 Note that in our experiments we selected the value from fourteen candidate values of {0.01, 0.05, 0.1, 0.2, 0.25, 0.3, 0.4, 0.5, 0.6, 0.7, 0.75, 0.8, 0.9, 1} to save computational time, but we carefully selected these candidate values via preliminary experiments.

For MLR/MER, the value of weighting parameter λ in Eq. (4) was selected from sixteen candidate values of {{0.1 × 10-n, 0.2 × 10-n, 0.5 × 10-n}4n=0 , 1} that were carefully selected via the preliminary experiments. For a fair comparison of the methods, the value of λ should be determined using training samples, for example, using a cross-validation of labeled samples [Grandvalet and Bengio, 2005]. We determined the value of λ that gave the best classification performance for test samples to examine the potential ability of MLR/MER because the computation cost of tuning λ was very high.

4.3 Results and Discussion

Table 1 shows the average classification accuracies over the ten different evaluation sets for WebKB, Cora, and 20news for different numbers of labeled samples. Each number in parentheses in the table denotes the standard deviation of the ten evaluation sets. |Dl| (|Du|) represents the number of labeled (unlabeled) samples.

As reported in [Raina et al., 2004; Fujino et al., 2005a], in supervised cases, the hybrid classifier was useful for achieving better generalization performance for multi-component data classification. In our experiments, the average classification accuracy of HY was similar to or better than that of NB and MLR.

We examined EM-λ, MLR/MER, CH, and H-BCM classifiers for semi-supervised cases. The H-BCM classifier outperformed the other semi-supervised classifiers except when the generative classifier performed very differently from the discriminative classifier for WebKB. We confirmed experimentally that the H-BCM classifier was useful for improving the generalization performance of multi-component data classification with both labeled and unlabeled samples.

More specifically, the H-BCM classifier outperformed the MLR/MER classifier except when there were many labeled samples for WebKB. This result is because MLR/MER tends to be overfitted to few labeled samples. In contrast, H-BCM inherently has the characteristic of the generative models, whereby such an overfitting problem is mitigated. When many labeled samples are available such that the overfitting problem can be solved, it would be natural for the discriminative classifier to be better than the H-BCM classifier.

The classification performance with H-BCM was better that with EM-λ except when there were few labeled samples for WebKB. It is known that discriminative approaches often provide better classification performance than generative approaches when there are many labeled samples [Ng and Jordan, 2002]. Our experimental result indicates that there might be an intrinsic limitation preventing EM-λ from achieving a high level of performance because only weighting parameter λ is trained discriminatively.

H-BCM provided better classification performance than CH except when there were few labeled samples for WebKB. The H-BCM and CH classifiers are constructed based on a hybrid of generative and discriminative approaches, but CH differs fromH-BCM, in that the former does not contain bias correctionmodels. This experimental result indicates that introducing bias correction models was effective in incorporating unlabeled samples into the hybrid classifier and thus improves its generalization ability.

5 Conclusion

We proposed a semi-supervised classifier design method for multi-component data, based on a hybrid generative and discriminative approach, called Hybrid classifier with Bias Correction Models (H-BCM classifier). The main idea is to design an individual generative model for each component and to introduce models to reduce the bias that results when there are few labeled samples. For evaluation, we also considered straightforward applications of conventional generative and discriminative semi-supervised learning algorithms to the classifiers proposed for multi-component data. We confirmed experimentally that H-BCM was more effective in improving the generalization performance of multi-component data classification than the straightforward approaches. Our experimental results using three test collections suggest that the HBCM classifier is useful especially when the generative and discriminative classifiers provide similar performance. Future work will involve applying H-BCM to multimodal data in which different generative models are employed.