Multi-View Maximum Entropy Discrimination

1 Introduction

Maximum entropy discrimination (MED) is an effective approach to discriminative training of model parameters, and relies on the maximum entropy or minimum relative entropy principle and the maximum margin principle. It can make full use of the merits of generative and discriminative modeling, and has been successfully applied to a large number of machine learning problems.

MED was first presented by Jaakkola et al. [1999], and was applied to anomaly detection and classification involving partially labeled examples. Jebara and Jaakkola [2000] employed MED for feature selection by introducing a selector variable into the discrimination function. Jebara [2004; 2011] extended MED to the problem of multi-task feature and kernel selection. On the theoretical side, Long and Wu [2004] established a mistake bound for an ensemble method for MED and proved a more refined bound that leads to a nearly optimal algorithm for learning disjunctions based on the maximum entropy principle.

Recently, Zhu and Xing [2009] applied MED to structure learning which posses the advantages of probabilistic models and the maximum margin approach. By adopting a Laplace prior, Zhu et al. [2008a] obtained a Laplace maximum margin Markov network which is a sparse model suitable for learning complex structures. Zhu et al. [2008b] also presented a partially observed MED Markov network to deal with the situation where latent variables exist.

Multi-view learning (MVL) is an emerging direction which considers learning with multiple feature sets. Its popularity is mainly motivated by the fact that many real-world data have multiple representations. For example, a web page can be described by words appearing on the web page itself and words underlying all links pointing to the web page from other pages. In multimedia content understanding, multimedia segments can be simultaneously described by their video signals and audio signals. But it should be noted that when there are no natural multiple views, manually generated multiple views can also be helpful [Nigam and Ghani, 2000]. Among the current MVL methods, we can identify two main categories: co-training style algorithms and co-regularization style algorithms.

Co-training style algorithms are inspired by the co-training algorithm [Blum and Mitchell, 1998], which iteratively runs the following procedure untill a termination condition is satisfied: Two learners are separately obtained from two views initially, and then the most confident examples identified by one learner are fed to the other to improve their learning performance. Recently, Yu et al. [2011] proposed a Bayesian undirected graphical model for co-training. Sun and Jin [2011] proposed a robust co-training algorithm, which integrates canonical correlation analysis to examine the predictions of co-training on unlabeled data. In addition to classification, the idea of co-training was later used for clustering [Bickel and Scheffer, 2004; Kumar and Daum´e III, 2011]. Theoretical work also attracted many researchers. For example, Dasgupta et al. [2001] gave a PAC-style bound on the generalization error, Balcan et al. [2005] presented a weaker assumption called ϵ-expansion to guarantee the success of cotraining, and Wang and Zhou [2010] provided a sufficient and necessary condition for co-training to succeed.

The core idea of co-regularization style algorithms is that minimizing the distinction between the functions of two views acts as one part of the objective function. Representative methods include [Sindhwani et al., 2005; Kumar et al., 2011; Sun, 2011; White et al., 2012]. There are also some theoretical research on co-regularization style algorithms. Rosenberg and Bartlett [2007] provided a tight bound on the Rademacher complexity of the co-regularized hypothesis class in terms of the kernel matrices from each reproducing kernel Hilbert space (RKHS). Sindhwani and Rosenberg [2008] constructed a single, new RKHS which can transform standard supervised algorithms to multi-view semisupervised algorithms. Sun and Shawe-Taylor [2010] characterized the generalization error of a multi-view SVM in terms of the margin bound and derived the empirical Rademacher complexity of the considered function class.

Inspired by the recent success of MVL, in this paper we extend MED to the MVL setting. But different from the previous two kinds of methods combining multiple views, we propose a new approach to exploiting multiple views. We enforce the margins from two views to be identical to yield a new MVL mechanism, which extends MED to our new framework multi-view maximum entropy discrimination (MVMED). Then we derive the solution to the optimization problem of MVMED, and give one instantiation by using a specific prior formulation.

The rest of the paper is organized as follows. Section 2 briefly reviews MED. Section 3 describes our proposed MVMED. Section 4 reports the experiments on three realworld data sets and makes comparisons. Finally, we give conclusions and point out possible future work in Section 5.

2 MaximumEntropy Discrimination

MED is similar to Bayesian learning in the sense that the posterior of model parameters requires to be inferred. But it integrates the large margin principle and may not need the formulation of generative distributions for data.

Now, we introduce the general learning setup of MED. Suppose we have a data set {Xt, yt} with N examples where Xt indicates the tth input, yt indicates the corresponding output, and yt ∈ {±1}. If we have two class-conditional probability distributions over the examples, i.e., p(Xt|θyt ) with parameters θyt , the decision rule follows the sign of the discriminant function

where Θ = {θ1, θ-1, b} includes the model parameters and b is a bias term that can be expressed as a log-ratio of class priors b = log (p+/(1 - p+)) with p+ being the prior of the positive class. Alternatively, the discriminant function can be directly described by a parameter formulation without any reference to probability models. MED applies well to any of the above two cases.

The general MED is formulated as follows:

where γ = {γ1, . . . , γN} specifies the desired classification margins which reflect the large margin principle as in SVMs. Here, instead of seeking a single parameter estimation, MED considers a more general problem of finding a distribution p(Θ, γ) over the parameters and margins, from which we can get the parameter distribution p(Θ) by marginalization. Correspondingly, it uses a convex combination of discriminant functions, i.e., ∫ p(Θ)L(Xt|Θ)dΘ rather than one single discriminant function to make model averaging for decisions. As Domingos [2000] proved, model averaging can improve the classification performance by means of alleviating the overfitting problem. In addition, the solution of MED is unique as long as it exists since the optimization problem in (2) is convex with respect to p(Θ, γ) [Jaakkola et al., 1999].

After adding a set of dual variables, one for each constraint, the Lagrangian of the optimization problem can be written as

In order to find the solution to (2), we require

which results in the following theorem [Jaakkola et al., 1999]. Theorem 2.1 The solution to the MED problem has the following general form

where Z(λ) is the normalization constant (partition function) and λ = {λ1, ..., λN} defines a set of non-negative Lagrange multipliers, one for each classification constraint. λ is set by finding the unique maximum of the following jointly concave objective function

Whether the solution to MED can be found depends entirely on whether the partition function Z(λ) can be evaluated in a closed form, which is given as

After λ is obtained, the following formula is used to predict the label of a new example X

3 Multi-viewMaximumEntropy Discrimination

As we have mentioned above, MED incorporates the principles of maximum entropy and maximum margin, which can provide a good justification for its successful applications. In addition, the recent MVL shows that simultaneously using multiple feature sets can further improve the performance over using a single feature set. But as far as we know, there is no research on MVMED yet. Our work in this paper aims to fill the gap and investigate the feasibility of MVMED. We also propose a novel approach to exploiting multiple views which is completely different from existing approaches.

We enforce the margins from two views to be identical, which is a new attempt to combine multiple views. This means that the classification confidences from different views are deemed to match each other exactly. Another benefit of this kind of "margin consistency" is that the solution to MVMED will be convenient to be computed.

Suppose the data set is {X1 t ,X2 t , yt} with N examples where X1 t and X2 t indicate the tth input from view 1 and view 2, respectively, and yt ∈ {±1} is the label. Our MVMED considers a joint distribution of Θ1, Θ2 and γ where Θ1 = {θ1, b1}, Θ2 = {θ2, b2}, and the common margin vector γ = {γ1, . . . , γN}. Formally, the MVMED framework is formulated as follows:

where L1(X1 t |Θ1) and L2(X2 t |Θ2) are discriminant functions from view 1 and view 2, respectively. The Lagrangian of the optimization problem is

where λ1 = {λ1,1, . . . , λ1,N} and λ2 = {λ2,1, . . . , λ2,N} are Lagrange multipliers for view 1 and view 2, respectively. In order to find the solution to (9), we require

which results in the following theorem.

Theorem 3.1 The solution to the MVMED problem has the following general form

where Z(λ1, λ2) is the normalization constant and λ1 = {λ1,1, ..., λ1,N}, λ2 = {λ2,1, ..., λ2,N} define two sets of non-negative Lagrange multipliers, one for each classification constraint. λ1 and λ2 are set by finding the unique maximum of the following jointly concave objective function

After λ1 and λ2 are obtained, the following two formulae are used to predict the label of a new example (X1 , X2 ) from view 1 and view 2, respectively

We can also make predictions by using the two views together

3.1 Instantiation of MVMED

The prior p0(Θ1,Θ2, γ) plays an important role in our MVMED framework as shown in (12). Now we instantiate our MVMED with a concrete prior formulation. Suppose

where p0(b1), p0(b2) approach a non-informative Gaussian prior, p0(θ1), p0(θ2) are both Gaussian distributed with mean 0 and identity covariance I, and the prior over the margin constraints γ is assumed to be fully factored

with p0(γt) = ce-c(1-γt) and γt ≤ 1. A penalty is incurred for margins smaller than 1-1/c (the prior mean of γt) while vanishes otherwise. In fact, this choice of the margin prior corresponds closely to the use of slack variables and additive penalties in SVMs.

Then the normalization constant in (12) can be obtained as

where we have used the fact that L1(X1 t |Θ1) = θ1X1 t + b1 and L2(X2 t |Θ2) = θ2X2 t + b2. We substitute (19) into (13) and get

Here, λ1 ≥ 0, λ2 ≥ 0. Since σ1 2 → ∞ and σ2 2 → ∞ correspond to using non-informative priors on the bias terms b1,t and b2,t, the above dual objective function requires the constraints ∑Nt=1 λ1,tyt = 0 and ∑Nt=1 λ2,tyt = 0. Thus we have the following dual optimization problem

The Lagrange multipliers λ1 and λ2 are recovered by solving the convex optimization problem (21), whose non-zero values indicate support vectors. Then the prediction rules for view 1 and view 2 on a new example (X1 ,X2 ) are respectively

where ˆb1 and ˆb2 are given by the Karush-Kuhn-Tucker (KKT) conditions using support vectors. If classifiers from two views are combined together to make predictions, the prediction rule can be given analogously from (16).

3.2 Relationship to SVM-2K

This section will discuss the relationship between our instantiation of MVMED and an MVL algorithm SVM-2K [Farquhar et al., 2005]. In order to facilitate the comparison and analysis, we rewrite (21) as (24) by replacing X1 t X1 τ , X2 t X2 τ with Mercer kernel functions κ(X1 t ,X1 τ ), κ(X2 t ,X2 τ ) and setting g1,t = λ1,tyt , g2,t = λ2,tyt, and the dual form of SVM2K is given in (25).

By inspection, we find that compared to each other, (24) has an additional term log(1 - λ1,t+λ2,t c ) in the objective function, while (25) has additional β+ t - βt in g1,t and g2,t. In fact, they both play the role of combining two views, though in different fashions. If we set c →∞ in (24) and set β+ t = βt = 0,C 1 →∞,C2 →∞ in (25) , the two formulae will be exactly identical. However, it should be noted that our MVMED framework is much more flexible than SVM2K, since we can reach different instantiations in terms of different prior specifications.

4 Experiments

In this section, we evaluate our proposed MVMED on three real-world data sets: web-page classification, ionosphere classification and advertisement classification.

For all the experiments, given a division of the training and test set, we use one half of the test set as a validation set for parameter selection and the other half for test. The average accuracies obtained by ten random divisions of the training and test sets are reported. The parameter c in MVMED is chosen from {2-5 , 2-4 , ..., 25}. Two single-view methods MED1 and MED2 are employed to compare with our MVMED. In addition, the MVL method SVM-2K is also used for comparison. For MVMED and SVM-2K, besides the prediction functions sign(f1) and sign(f2) from the separate views, we also consider the hybrid prediction function sign((f1 +f2)/2) and the one with the highest validation accuracy will be selected.

We first report the average accuracies and standard deviations of the four methods on data sets with only one tenth of the data as the training set in Table 1. Then we increase the training set sizes gradually, and show their performances in Figure 1.

4.1 Web-Page Classification

The data set for this experiment consists of 1051 two-view web pages collected from computer science department web sites at four universities: Cornell University, University of Washington, University of Wisconsin, and University of Texas. There are 230 course pages and 821 non-course pages. The two natural views are words occurring in a web page and words appearing in the links pointing to that page [Blum and Mitchell, 1998; Sindhwani et al., 2005]. The dimensions of the two views are 2333 and 87, respectively. For convenience, we reduce the dimension of view 1 from 2333 to 500 via principal component analysis (PCA).

Clearly, Table 1 indicates that MVMED is superior to single-view MED1, single-view MED2 and SVM-2K. We can also find that SVM-2K performs better than single-view MED1 but worse than single-view MED2. Figure 1(a) with varying training sizes also shows that our MVMED consistently outperforms the other three methods.

4.2 Ionosphere Classification

The ionosphere data set origins from UCI, 1 and includes 351 instances in total which are divided into 225 "good" (positive) instances and 126 "bad" (negative) instances. This data set has only one view, but we generate the other view through PCA. Now, the two views have 35 and 24 dimensions, respectively.

The experimental results are shown in Table 1 and Figure 1(b), from which we can see that MVMED performs the best among all the methods. SVM-2K performs better than single-viewMED1 but worse than single-viewMED2. From Figure 1(b), we can also find that although MVMED and single-view MED2 need fewer training data to reach a high accuracy, MVMED is more stable than single-view MED2.

4.3 Advertisement Classification

The data set consists of 3279 examples including 459 ads images (positive examples) and 2820 non-ads images (negative examples) [Kushmerick, 1999]. The first view describes the image itself (words in the image's URL, alt text and caption), while the other view contains all other features (words from the URLs of the pages that contain the image and the image points to). Here, we randomly select 600 examples therein to form the used data set.

From Table 1 and Figure 1(c), we can find that our method MVMED performs better than all the other methods. SVM2K performs the worst in the beginning, but then performs nearly as well as single-view MED1, though still behaves worse than single-view MED2 and MVMED.

4.4 Summary

From the above experiments, we can find that our MVMED performs the best. Another MVL method SVM-2K performs not as good as the MVMED, and sometimes is even worse than single-view MEDs. In a nutshell, the new MVMED framework is effective.

5 Conclusion and FutureWork

We have proposed an MVMED framework which is an extension of MED to the scenario of learning with multiple views and therefore integrates the merits of MVL and MED. Different from existing approaches to exploiting multiple views, we propose to use "margin consistency" to perform MVL, and apply it to MVMED. We also give an instantiation of the MVMED framework with a factorized prior, which is further shown to be related to the multi-view method SVM-2K. Experimental results on real-world applications web-page classification, ionosphere classification and advertisement classification validate the effectiveness of the proposed MVMED.

1 Data available at http://archive.ics.uci.edu/ml/.

Interesting future work directions include extending our MVMED framework to more than two views, and applying it to other learning scenarios such as semi-supervised learning and structure learning.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Project 61075005, and Shanghai Knowledge Service Platform Project (No. ZF1213).