Soft Margin Consistency Based Scalable Multi-View Maximum Entropy Discrimination

1 Introduction

Heterogeneous data analysis is a timely and important task for the artificial intelligence community. For many real-world datasets, features can be naturally partitioned into distinct sets, each of which is regarded as a view. Then each datum can be described by multiple views. For instance, a web page can be described by the text on it and words appearing in the hyperlinks to it, each of which forms a single view. As another example, in multimedia content understanding, multimedia segments can be described by both their audio and video signals.

Multi-view learning is the learning scheme that utilizes the heterogeneous property of datasets. Compared with single view learning, multi-view learning learns a function on each view and train them jointly to improve performance. Xu, Tao and Xu [2013] and Sun [2013] have surveyed the development and applications of multi-view learning.

Maximum entropy discrimination (MED) [Jaakkola et al., 2000] is an effective approach to learn a discriminative classifier as well as consider uncertainties over model parameters, which combines generative and discriminative learning.

Rather than find a single classifier parameter ⇥ of the discriminant function L(⇥) (e.g., L(Xt♣⇥) = ✓TXt + b↪ ⇥ = ¶✓↪ b♦), MED considers to learn a distribution p(⇥) over classifier parameter ⇥. After obtaining a joint distribution p(⇥↪ γ) over ⇥ and margin parameters γ by minimizing its relative entropy (also known as Kullback-Leiber divergence, or KL divergence) with respect to some prior target distribution p0(⇥↪ γ) under certain large margin constraints, MED marginalizes out γ to obtain p(⇥) [Jebara, 2004]. MED can be extended to a wide variety of learning scenarios, such as feature selection [Jebara and Jaakkola, 2000], multitask learning [Jebara, 2011] and structure learning [Zhu and Xing, 2009; Zhu et al., 2008a; 2008b].

Recently, multi-view maximum entropy discrimination (MVMED) [Sun and Chao, 2013] was proposed as an extension of MED to the multi-view learning setting. It considers a joint distribution p(⇥1↪⇥2) over the view 1 classifier parameter ⇥1 and view 2 classifier parameter ⇥2. Using the augmented joint distribution p(⇥1↪ ⇥2↪ γ), MVMED was formulated as follows

(1)

where L1(X1 t ♣⇥1) and L2(X2 t ♣⇥2) are discriminant functions from two views, respectively. Chao and Sun [2015] also proposed a similar MVMED framework called alternative MVMED (AMVMED), which considers two separate distributions p1(⇥1) over ⇥1 and p2(⇥2) over ⇥2 and balances KL divergences of their augmented distributions with respect to the corresponding prior distributions. AMVMED was formulated as

Unlike conventional multi-view learning methods, MVMED and AMVMED exploit the multiple views in a different style called margin consistency, that is, to enforce the margins from two views to be identical. Although they have provided state-of-the-art multi-view learning performance, this margin consistency requirement may be too strong to fulfill in many cases. For example, all positive margins can lead to the same label prediction in binary classifications. It is thus interesting to explore the possibility of relaxing the requirement. Moreover, as far as we know, the current training algorithms for MVMED and AMVMED are inefficient and not scalable, which prevent people from using them to large datasets.

In this paper, we propose a new multi-view MED framework named soft margin consistency based multi-view MED (SMVMED) which is based on the different principle of soft margin consistency. We give an iterative method to approximate the solution. Compared with MVMED and AMVMED with 'hard' margin consistency that enforces the margins from two views to be identical, SMVMED achieves 'soft' margin consistency by utilizing the sum of two KL divergences KL(p(γ) ♣♣ q(γ)) and KL(q(γ) ♣♣ p(γ)) in the objective function, where p(γ) and q(γ) are the posteriors of two view margins, respectively. By balancing all the involved terms in the objective function, SMVMED is more flexible. Moreover, we propose a sequential minimal optimization (SMO) algorithm [Platt, 1999] to effectively train SMVMED for large datasets under some configurations on priors of model and margin parameters.

The rest of the paper is organized as follows. We first introduce our SMVMED and derive its solution. Then a practical realization of SMVMED will be given. Next we describe the SMO algorithm for fast training and scalability. After that, we report experiments on multiple real-world datasets. Finally, conclusions are given.

2 Soft Margin Consistency BasedMulti-view MED

In this section, we give the formal framework of our soft margin consistency based multi-view MED. It achieves margin consistency by minimizing the KL-divergence between the posteriors of margin parameters from two views. We also introduce a trade-off parameter balancing large margin and margin consistency to make the model more flexible.

Suppose we are given a multi-view dataset ¶X1 t ↪X2 t ↪ yt♦↪ t = 1↪ ▷ ▷ ▷ ↪N↪ where X1 t and X2 t indicate the tth input from view 1 and view 2, respectively, and yt 2 ¶◦1♦ is the label. SMVMED aims to learn two discriminant functions L1(X1 t ♣⇥1) and L2(X2 t ♣⇥2) for two views, respectively, where ⇥1 and ⇥2 are parameters of these two functions. First, we assume that there are two independent distributions p(⇥1) and p(γ), with their joint distribution p(⇥1↪ γ) = p(⇥1)p(γ), where γ = ¶γt♦↪ t = 1↪ ▷ ▷ ▷ ↪N↪ is the margin parameter. Here p(⇥1) is the posterior of ⇥1 and p(γ) is the posterior of margins from view 1. Then the same settings are applied to view 2, that is, q(⇥2↪ γ) = q(⇥2)q(γ), where q(γ) is the posterior of margins from view 2. Formally, SMVMED can be formulated as follows:

Since we will choose the margin priors that favor large margins, the parameter ↵ above plays the trade-off role of balancing large margin and soft margin consistency.

Since it is tricky to find the solutions making the partial derivatives of the Lagrangian of (3) with respect to p(⇥1↪ γ) and p(⇥1↪ γ) be zero, we propose an iterative scheme for finding a solution to (3). In the mth iteration, we successively update p(m) (⇥1↪ γ) and q(m) (⇥2↪ γ) by solving the following two problems:

and

Notice that we omit ↵KL(q(m-1) (γ) ♣♣ p(m) (γ)) in (4) for the purpose of simplifying the subsequent calculation of derivatives. We think ↵KL(p(m) (γ) ♣♣ q(m-1) (γ)) is a good approximation to ↵KL(p(m) (γ) ♣♣ q(m-1) (γ)) + ↵KL(q(m-1) (γ) ♣♣ p(m) (γ)) since the latter is just the symmetrization version of the former. We omit ↵KL(p(m) (γ) ♣♣ q(m) (γ)) in (5) for the same reason.

Before employing this iterative scheme, we first choose some initial value for q(0) (⇥2↪ γ). It is a proper choice to initialize q(0) (⇥2↪ γ) with q0(⇥2↪ γ), which makes (4) a standard MED problem. We will use this scheme in this paper.

The Lagrangian of (4) can be written as

where λ(m) 1 = ¶λ(m) 1↪t ♦ is a set of nonnegative Lagrange multipliers, one for each classification constraint. After taking the partial derivative of (6) with respect to p(m) (⇥1↪ γ) and setting it to zero, we will obtain the solution to (4) which has the following form

where Z (m) 1 (λ(m) ) is the normalization constant. λ(m) 1 is set by finding the unique maximum of the following concave objective function:

Apply the same analysis to (5) and we will obtain the its solution, which has the following form

where λ(m) 2 = ¶λ(m) 2↪t ♦ is another set of Lagrange multipliers. λ(m) 2 is set by finding themaximumof the following objective function:

After each iteration, we calculate the relative error between values of (8) from two successively iterations and that of (10), respectively, and utilize them for determining convergence. When the relative errors

and

are both less than some tolerance ✏, the iteration ends. Then we obtain p(⇥1) and q(⇥2) and use the following formulas as decision rules for a new example (X1 ↪X2 ) from view 1 and view 2, respectively

or use two views together

3 Practical Realization

In this section, we discuss the practical realization of SMVMED. Since the priors p0(⇥1↪ γ) and q0(⇥2↪ γ) play an important role in the solution, we shall give their concrete formulations. Also, we use the linear classifier assumptions, that is,

We will show that the particular configuration leads to the implementation of an SMO algorithm for fast training.

Suppose

where p0(✓1) and q0(✓2) are Gaussian distributions with mean 0 and standard deviation I, p0(b1) and q0(b2) are set to non-informative Gaussian distributions, and p0(γ) and q0(γ) are assumed to be fully factorized, namely,

with p0(γt) = q0(γt) = c p2⇡ e- c2 2 (1-γt)2 , a Gaussian prior with mean 1 that encourages large margins.

Under the above configuration, we can derivate a concrete form of (8) and (10). Before doing that, we first introduce some notations to simplify the derivation. We use k to indicate the times of optimization problems that we have solved and set l = (kmod2) + 1. Let Z (k) (λ(k) ) represent Z (m) 1 (λ(m) 1 ) when k = 2m- 1, and represent Z (m) 2 (λ(m) 2 ) when k = 2m. J (k) (λ(k) ) is used in the same manner. After

Substituting it into (8) and (10), we will get

According to the non-informative prior assumption on b1 and b2, we will have σ2 l ! 1, which requires that NP t=1 λ(k) t yt = 0. Thus we have the following dual optimization problem

The Lagrange multipliers λ(k) are set by solving the convex optimization problem (24). After each iteration, we obtain two sets of Lagrange multipliers and substitute them into (8) and (10). Then we can use (11) and (12) to judge convergence. After the iteration converges, we compute (22) using λ(m) 1 from the last iteration and substitute (16), (18), (20) and (22) into (4) to obtain the solution p(⇥1↪ γ). Similarly, using λ(m) 2 from the last iteration to compute (22) and substituting (17), (19), (21) and (22) into (5) will give q(⇥2↪ γ). The decision rule using view 1 can be given as

where ˆ ✓1 and ˆb1 are the expected values of discriminant function parameters. ˆ ✓1 is obtained as follows

With (26) substituted into (25), the prediction rule becomes

Similarly, the prediction rules using view 2 and using two views together are given as

We will give the solution to ˆb1 and ˆb2 in the next section.

3.1 Remarks onMargin Priors

Jaakkola et al. [3] discussed different margin priors and their corresponding potential terms in the objective function of the dual optimization problem. Both MVMED and AMVMED choose the exponential distribution p0(γt) = ce-c(1-γt) as the margin prior which leads to a logarithmic potential term. In this paper, we use the Gaussian distribution p0(γt) = q0(γt) = c p2⇡ e- c2 2 (1-γt)2 as margin priors since the corresponding potential term makes the key optimization problem of SMVMED a quadratic programming problem, which can be solved efficiently.

4 Sequential Minimal Optimization

In this section, we propose an SMO algorithm to solve the convex optimization problem (24) which plays a central role in SMVMED. We will also give the solution to ˆb1 and ˆb2 in (27), (28) and (29). SMO solves (24) by successively performing direction search on a small subset of dataset called working set [Bottou and Lin, 2007]. With respect to the working set selection scheme, we use the second order working set selection scheme [Fan et al., 2005].

First, we rewrite the objective function in (24) as

where we omit the term irrelevant to λ(k) and replace Xl t TXl⌧ with Kl t⌧ so that nonlinear classifiers can be taken into account. Then we write the constraints on λ(k) t as constraints on ytλ(k) t , that is,

We give the optimality criterion next. Let λ⇤ = ¶λ⇤t ♦↪ t = 1↪ ▷ ▷ ▷ ↪N↪ be the solution to (31). λ⇤ should satisfy the optimization constraints. Let g⇤ = ¶g⇤ t ♦↪ t = 1↪ ▷ ▷ ▷ ↪N↪ be the derivatives of (30) with respect to λ⇤ .

where

where (t↪ ⌧) is a pair of subscripts such that ytλ⇤t < Bt and y⌧λ⇤⌧ > A⌧ , and ✏ is a small positive quantity. Since λ⇤ is the solution to (31), the first order expansion

D(λ✏ ) - D(λ⇤ ) = ✏ (ytg⇤ t - y⌧g⇤ ⌧ ) + o(✏)  0 (35) suggests that ytg⇤ t - y⌧g⇤ ⌧ is necessarily negative. This hold for all pairs (t↪ ⌧) such that ytλ⇤t < Bt and y⌧λ⇤⌧ > A⌧ . Therefore we can write the following optimality criterion

To start with, we initialize λt = 0 and gt = 1 - k-1 P i=1 ↵k-i λ(i) t c2 ↪ t = 1↪ ▷ ▷ ▷ ↪N. Then we successively choose a pair of subscripts (t↪ ⌧) as the working set and perform direction search on it until the optimality criterion (36) is satisfied. The second order working set selection scheme can be formulated as

For each working set, we maximize (30) by performing direction search along a direction v containing only two non-zero coefficients: vt = yt↪ v⌧ = y⌧ . This direction search is expressed by the following optimization problem

where λ is the starting point. The solution to (38) is

Gradients and coefficients are updated as follows

Repeat the above procedure until optimality criterion (36) is satisfied, and we will obtain solution to (24). With respect to ˆbl in the prediction rules, we set ˆbl = ⇢.

5 Experiment

In this section, we evaluate SMVMED on real-world datasets: Course, Ads and Indoor. We compare soft margin consistency and hard margin consistency by performing SMVMED, MVMED and AMVMED on Course and Ads. Since Indoor is a large dataset that can not be handled by MVMED and AMVMED, we compare SMVMED with SVM-2K [Farquhar et al., 2005] on it to show the scalability. For prediction functions, besides using two views sign(f1) and sign(f2) separately, the hybrid prediction function is also taken into consideration. That is, we also consider sign( 12 (f1 + f2)) for SMVMED, MVMED and SVM-2K and sign(⇢f1 + (1 - ⇢)f2)) for AMVMED, where ⇢ is chosen from ¶0↪ 0▷1↪ ▷ ▷ ▷ ↪ 1▷0♦. Among all the three prediction functions , the one having the highest validation accuracy will be selected. The linear kernel is used in all the experiments. All of the experiments are executed on an Intel(R) Core(TM) i7-3667U 2.00GHz CPU with 8GB of RAM using Matlab R2014a.

5.1 Soft Margin Consistency vs. HardMargin Consistency

We evaluate the performance of our soft margin based multiview MED by comparing it with MVMED and AMVMED on Course and Ads. Note that the original implementations of MVMED and AMVMED use the exponential prior. Here we also adapt them with the Gaussian prior to facilitate comparisons with SMVMED. We give a description of each used dataset below.

• ÷ Course: The dataset is the web-page dataset used in the co-training experiment [Blum and Mitchell, 1998]. It is a subset of the WebKB dataset which contains web pages collected by World Wide Knowledge Base (Web -> Kb) project of the CMU text learning group from computer science departments of four universities. It contains 230

94▷73 ◦ 1▷94

95▷07 ◦ 1▷67

95▷33 ◦ 1▷75

95▷27 ◦ 1▷92

96▷40 ◦ 1▷55

Table 2: Average training times for Course and Ads

course pages and 821 non-course pages, with view 1 being words in a web page and view 2 being words in the hyperlinks to the page. The dimensions of the two views are 500 and 82, respectively.

• ÷ Ads: The dataset consists of 459 ads images and 2820 non-ads images [Kushmerick, 1999]. We randomly select 600 examples as the used dataset. View 1 contains 587 features describing the image itself. The other 967 features form view 2.

We randomly select half of the dataset as the training set, and the rest is divided into the validation set and the test set equally. Parameter c in SMVMED, MVMED and AMVMED is independently chosen from ¶21 ↪ 22 ↪ ▷ ▷ ▷ ↪ 25 ♦ for Course, and from ¶21 ↪ 22 ↪ ▷ ▷ ▷ ↪ 215 ♦ for Ads. Parameter ↵ in SMVMED is chosen from ¶0↪ 0▷1↪ ▷ ▷ ▷ ↪ 1▷0♦. All the experiments are performed ten times.

The average accuracies and standard deviations in percentage for Course and Ads are shown in Table 1, and the corresponding average training times with validated parameters are shown in Table 2. From Table 1, we can see that SMVMED performs better than MVMED and AMVMED. Table 2 shows that SMVMED and the Gaussian prior MVMED and AMVMED train much faster than the exponential prior MVMED and AMVMED, and that SMVMED is the fastest.

5.2 Scalability

We examine the scalability of SMVMED on a large dataset Indoor and compare it with SVM-2K. The dataset is the UJIIndoorLoc indoor localization database [Joaquın et al., 2014]. The training set consists of 19936 examples including 5249 Wifi fingerprints collected from building 0, 5195 from building 1 and 10444 form building 2. The test set consists of 536 Wifi fingerprints collected from building 0, 306 from building 1 and 268 from building 2. We perform experiments on both the whole dataset and a subset containing only examples from building 0 and 1. For the whole dataset experiment, we use examples from building 0 and 1 as the positive class and the others as the negative class. Each Wifi fingerprint is characterized by the detected wireless access points and the corresponding received signal strength intensity. We divide 520 intensity values into two views, the dimensions of which are 300 and 220, respectively. Each intensity value is randomly assigned to one of the two views. Since the performance of SMVMED is not sensitive to parameter c on the dataset, we fix it to 1. Parameter ↵ is chosen from ¶0↪ 0▷1↪ ▷ ▷ ▷ ↪ 1▷0♦.

Table 3 shows the accuracies for Indoor and its subset, and the corresponding training times. From Table 3, we can find that SMVMED performs better than SVM-2K and is much faster. Also, with the increase of the dataset size, the trainng time of SMVMED grows more slowly than that of SVM-2K.

The dataset used here includes 19936 training examples. However, SMVMED is scalable for larger datasets. From (37), (39) and (40), we can see that only the diagonal and two rows of Gl are required at the same time in SMO. Therefore, once these elements of Gl of a dataset can be cached, it can be handled by SMVMED.

5.3 Summary

The above experimental results show that SMVMED performs better than MVMED and AMVMED, and is much faster. The choice of the Gaussian margin prior greatly improves the training speed. On the large dataset Indoor, SMVMED performs better than SVM-2K and trains much faster.

6 Conclusion

We have presented soft margin consistency based scalable MED, with an SMO algorithm for efficient training. Different from the hard margin consistency used in MVMED and AMVMED, a different principle of less strict soft margin consistency is employed. By balancing large margin and margin consistency, SMVMED is more flexible. Furthermore, the use of the Gaussian prior and SMO makes SMVMED very efficient. Experimental results on multiple real-world datasets have shown its good performance and scalability.

Acknowledgments

The corresponding author Shiliang Sun would like to thank supports from the National Natural Science Foundation of China under Project 61370175.