Combining Supervised and Unsupervised Models via Unconstrained Probabilistic Embedding

1 Introduction

Recently, an interesting problem that combines multiple supervised and unsupervised models at output level has been proposed [Gao et al., 2009]. It is an extension of previous studies on classification ensembles (combining only supervised models) and clustering ensembles (combining only unsupervised models). Here, it combines the output from both supervised models and unsupervised models, and aims to fully utilize the constraints provided by unsupervised clusterings to improve prediction accuracy for classification. The solution to this problem is in great need, where the raw data cannot be accessed due to privacy or other issues and the output from multiple supervised and unsupervised models is provided.

This problem can be formulated as follows. Suppose we have a set of data objects O = {o1, o2, · · · , oN} from c classes. There are M models that provide the classification information of O, where the first r of them are supervised classifiers, and the left are unsupervised clustering algorithms. Here, we only consider "hard" classification and clustering algorithms, i.e., the object o is predicted to be in exactly one class or cluster. Consider an example where O = {o1, · · · , o6}, c = 2 and M = 4. The output of the four models are: M1 = {1, 2, 1, 1, 2, 2}, M2 = {1, 1, 2, 1, 2, 2}, M3 = {2, 2, 1, 1, 3, 3}, M4 = {2, 2, 2, 2, 1, 1}, where M1 and M2 assign each object a class label, whereas M3 and M4 partition the objects into multiple clusters and assign each object a cluster ID.

The objective is to predict the class label of oi ∈ O based on the ensemble of base classification and clustering results. The prediction of this proposed ensemble satisfies as much as possible that 1) it agrees with the base classifiers' prediction, and 2) the objects in the same cluster have the same prediction.

Object-Group Co-occurrence Matrix

Before briefly introducing our general solution to this problem, we give the concept of groups, referring to the classes and clusters from the models, and object-group co-occurrence matrix. Note that the taxonomy of data is predefined for classification, and the same class ID assigned by different classification algorithms have the same meaning. However, the clusters from different clustering algorithms have different meaning, and cluster IDs are not related to class labels. Therefore, we can assign a group ID to each class label and each cluster. Assume that clustering algorithm i partitions the data O into li clusters, then the total number of groups is G = c + ∑Mi=r+1 li.

Consider our example again. M3 partitions the objects into 3 clusters, while M4 partitions them into 2 clusters. Thus, G = 7 in this example. Figure 1 shows the grouping results in the example. As you can see, the groups from the classification algorithms M1 and M2 share the same group IDs, namely g1 and g2. However, the different clusters from the clustering algorithms M3 and M4 use the different group IDs.

Based on the assignment of group IDs, we can generate an object-group co-occurrence matrix MN×G, where Mn,g is equal to the number of times that object n belongs to group g. Table 1 shows this co-occurrence matrix for our example. Obviously, when group g is for a class label (say g1 and g2 in the example), Mn,g may be bigger than 1. For example, M1,1 = 2 in Table 1 since object 1 belongs to group 1 twice. However, when group g is for a cluster (say g3, g4, g5, g6, g7 in the example), Mn,g can only be 0 or 1.

Constrained vs. Unconstrained Embedding

Gao et al. [Gao et al., 2009] proposed a constrained embedding solution to this ensemble task. In their method, each object and class/cluster are embedded into a c-dimensional cube. Additionally, it is a constrained embedding in the sense that the sum of all the entries in each c-dimensional coordinate must be equal to 1. It means that the embedded space is limited as a c-dimensional simplex, and the i-th entry in the coordinate of an object can be viewed as the probability that this object belongs to the i-th class. See our example of binary classification again. The obtained coordinate for each object is a 2-entry probability vector (v1, v2), where v1+v2 = 1 and v1 (or v2) is the probability that this object belongs to class 1 (or 2).

In this study we solve this ensemble problem by Unconstrained Probabilistic Embedding (UPE for short). We assume that each object and group correspond to a latent coordinate without any constraint in a D-dimension Euclidean space. With these coordinates the generation of the objectgroup co-occurrence matrix can be viewed as a probabilistic generative process. Then, by maximizing the posterior of parameters all these coordinates can be obtained, and the prediction of an object is determined by the distances between the object and the groups for the c classes in the embedded space. Different from the constrained embedding method in [Gao et al., 2009], no constraints are imposed into the latent coordinates in our solution. Additionally, the dimension of the embedded space D can be any positive integer while that in the constrained embedding must be c, the number of class labels. We argue that with more freedom in fitting the data into any coordinates in any dimension space our solution might achieve better predictions.

The remainder of this paper is organized as follows. Section 2 details our solution of UPE, including the generative process from the coordinates for objects and groups to the object-group co-occurrence matrix, and the derivation of the model parameters by the quasi-Newton method. In Section 3, we demonstrate the effectiveness of UPE by three real applications and compare it with existing alternatives. Section 4 concludes this study.

2 Unconstrained Probabilistic Embedding

For clarity and convenience, the notation and denotation used in this study are summarized in Table 2.

2.1 FromLatent Space to Object-Group Co-occurrence Matrix

Now we embed the objects and groups to a new space. We assume the objects have latent coordinates X = {xn}Nn=1 , where xn = (xn1, · · · , xnD) is a coordinate of the n-th object in the embedded space, and D is its dimensionality. Similarly, we assume each group g also has its associated latent coordinate φg = {φg1, · · · , φgD} in the embedded space. The probability of an object belonging to a certain group is determined by its Euclidean distances from each group in the embedded space as follows:

where ∑Gg=1 P (g|xn, Φ) = 1, and ‖ · ‖ represents the Euclidean norm in the latent space. Obviously, if the Euclidean distance between xn and φg is small, the probability P (g|xn, Φ) is high.

φg

Our model assumes the probabilistic generative process of the object-group co-occurrence matrix M as shown in Algorithm 1. First, the coordinates xn and φg are assumed to be generated by the zero-mean spherical Gaussian distributions. Then, for an object n we draw the group ID M times using the multinomial distribution Mult({P (g|xn, Φ)}Gg=1 ). Each entry in the parameters of this multinomial distribution is calculated by xn and Φ via Equation (1). If g′ is drawn for n, we add 1 to Mn,g′ . This process ends after we sample the groups for all the N objects. Figure 2 shows the graphical model representation of UPE, where the observed and latent variables are indicated by shaded and unshaded nodes, respectively.

Algorithm 1 Generative Process for the Object-Group Cooccurrence Matrix

1. Initialize the object-group co-occurrencematrix :

1. For each group g = 1, · · · , G:

Draw group coordinate

∼

Normal(0, β-1 I).

1. For each object n = 1, · · · , N:

Our model is motivated by PLSV (Probabilistic Latent Semantic Visualization) [Iwata et al., 2008], which is a topic modeling based visualization method for documents. In that model the document-word occurrence matrix is taken as input, and the documents and latent topics are embedded into a 2 or 3 dimension space for visualization. To compare PLSV with our model of UPE, we may view objects in our problem as documents, and groups as words. Then, the difference between UPE and PLSV is as follows. First, there are not latent topics in UPE. Second, in UPE not only documents but also words are embedded into a D dimension space. Third, since PLSV is used for visualization, the dimension of the embedded space must be 2 or 3, while that for UPE can be any positive integer.

2.2 Parameter Estimation

The unknown parameters are a set of object coordinates X and a set of group coordinates Φ. We estimate these parameters based on Maximum A Posteriori (MAP) estimation. The posterior of the parameters is given as follows,

where

In the generative process described in the previous subsection, we use a Gaussian prior with a zero mean and a spherical covariance for distribution of the coordinates of xn and φg. Then, we have

where β and γ are hyper-parameters. We choose β = λN, γ = λG, and λ (0 ≤ λ ≤ 1) is a coefficient. In the experiment section we will discuss the influence of different values of λ.

Next, we estimate parameters X, Φ by maximizing the posterior p(X, Φ|M) in Equation (2). By applying the log function, it is equivalent to the following optimization problem,

where

We use the quasi-Newton method [Liu and Nocedal, 1989] to maximize Q(X, Φ). The partial differentials of Q(X, Φ) w.r.t. xn and φg are as follows respectively,

(11)

By applying the quasi-Newton method until convergence, we obtain a local optimum solution for {X, Φ}, including the coordinates of objects and groups in the embedded space. Then we can predict the label of object n as follows,

Remember that our task is for classification. Thus, in the prediction process we only consider the first c groups, corresponding to the c class labels, for comparison. This prediction process is equivalent to

where ‖ · ‖ represents the Euclidean norm in the latent space.

3 Experiments

3.1 Data Set

We apply the proposed method on the data set from [Gao et al., 2009], including 11 classification tasks from three real world applications. In each task, the data set is separated into training and test sets. Clustering algorithms are performed on the test set to obtain the grouping results. On the other hand, we learn classification model from training set and apply it to the test set. The proposed algorithm generates a consolidated classification solution for the test set based on both classification and clustering results. The details of each application is elaborated in the following.

20 Newsgroups categorization. The 20 newsgroups data set 1 contains approximately 20,000 newsgroup documents, partitioned across 20 different newsgroups nearly evenly. From the data sets, six learning problems are constructed, each of which has documents from four different topics to distinguish. The logistic regression [Genkin et al., 2005] and SVM models [Chang and Lin, 2001] are learned from the training sets, and apply, as well as K-means and min-cut clustering algorithms [Karypis, 2006] on the test sets.

Cora research paper classification. The Cora data set [McCallum et al., 2000] contains around 37,000 research papers that are classified into a topic hierarchy with 73 leaves. The citations among papers are around 75,000 entries. Four test sets are extracted, each of which includes papers from around four areas. The training sets contain research papers that are different from those in the test sets. Both training and test sets have two views, the paper abstracts, and the paper citations.

1 http://people.csail.mit.edu/jrennie/20Newsgroups/

The logistic regression classifiers and K-means clustering algorithms are applied on the two views of the target sets.

DBLP network. Around 4,000 authors are retrieved from DBLP network [Ley, 2001]. We try to predict their research areas in four candidate fields. There are also two views for both training and test sets, namely the publication network and the textual content of the publications. The amount of papers an author published in the conference can be regarded as link feature, whereas the pool of titles that an author published is the text feature. Logistic regression and K-means clustering algorithms are used to derive the predictions on the test set. The test set is labeled manually for evaluation.

3.2 Baseline Methods

On each test set, two classification models and two clustering models (denoted as M1 to M4) are obtained by applying four different algorithms. Then we applied the ensemble methods on the four models. In [Gao et al., 2009] the constrained embedding solution, namely Bipartite Graph-based Consensus Maximization (BGCM for short) is compared with the two clustering ensemble approaches, MCLA [Strehl and Ghosh, 2003] and HBGF [Fern and Brodley, 2004], which regard all the base models as unsupervised clustering, and integrate all their output. They show that BGCM improves the accuracy of the best single model by 2% to 10%.

Here, we focus on the comparison between UPE and BGCM, and also give the results of the baselines in [Gao et al., 2009]. To evaluate classification accuracy, The output of all the clustering algorithms (the base models, and the ensembles) are mapped to the best possible class predictions with the help of hungarian method 2 [Kuhn, 1955], where cluster IDs are matched with class labels. In addition, the results of Majority Voting on only the classification models (denoted as MV) are presented. We denote the proposed methods as UPE-D, where D refer to the number of dimension used for the embedded space. D is set from 1 to 4 in the experiments. Note that UPE has some random property since the initial parameters are drawn from a spherical Gaussian distribution. Thus, we run our solution 20 times with different initialization for each task, and calculate the average value as the result.

3.3 Experimental Results

In Table 3, we present the classification accuracy of UPED and the other baselines on eleven tasks, and the highest accuracy of each task is bolded. The graphical comparison of UPE and BGCM is also shown as Figure 3. We can see that UPE-2 is already better than BGCM, which indicates that our unconstrained embedding method in 2-dimensional space is already better than the constrained embedding method in a c-dimensional space (c = 4 in these tasks). Additionally, UPE-3 further improves the accuracy. Among the 11 tasks UPE-3 achieves 7 best results, and it increases the accuracy by 1.3% to 4.4% in 10 cases compared with BGCM. Also UPE-4 achieves similar performance with UPE-3.

As described before, two hyper-parameters β and γ are used in the prior distribution of the coordinates. They are set as β = λN and γ = λG. In the previous experiments, we fix λ = 0.1 for UPE. Here, on the date set of Cora we check the sensitivity of this parameter by changing it from 0.01 to 0.20 with 0.01 as interval. As shown in Figure 4, when 0.05 ≤ λ ≤ 0.19, the performance is not sensitive.

2 N. Borlin, http://www.cs.umu.se/ niclas/matlab/assignprob/

We also check whether the random initialization of the coordinates affects the performance of UPE. Since we run 20 times with different initialized values for each task, we can calculate the standard deviation of the 20 values. The results show that when λ ≤ 0.2 the standard deviation is less than 0.01. However, when λ > 0.2 the standard deviation increases, and exceeds 0.15 when λ > 0.4. Therefore, λ > 0.2 UPE is not stable in terms of the random initialization. Fortunately, it is very stable when λ ≤ 0.2.

4 Conclusions

In this paper we propose an unconstrained probabilistic embedding solution to combine output from multiple supervised and unsupervised models. In our solution each object and group are embedded into a D dimensional space without any constraints. We argue that the more freedom in the embedding process of our solution will result in performance improvement. By considering the mapping from the coordinates in the embedded space into the object-group co-occurrence matrix as a generative process, we can obtain these coordinates by the MAP estimation. This optimization problem is then solved by the quasi-Newton method. With the 11 tasks from three real applications we show the superiority of our solution over the constrained embedding method.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 60933004, 60975039, 61035003, 60903141, 61072085), and National Basic Research Priorities Programme (No.2007CB311004). Thanks to the internship program of Hewlett Packard Labs China.