Nonlinear Maximum Margin Multi-View Learning with Adaptive Kernel

1 Introduction

Nowadays data typically can be collected from various information channels, e.g., a piece of news is consisted of text, audio, video clip and hyperlink. How to effectively and efficiently fuse the information from different channels for specific learning tasks is a problem (known as multiview learning) attracting more and more attention. For supervised learning, e.g., news classification, we have not only these multi-channel features but also the corresponding category labels. Making full use of the label information usually is critical for the construction of predictive multi-view models since it can help to learn more discriminative features for classification. A popular choice is to exploit the maximum margin principle to guarantee the learned model to have a good generalization ability [Xu et al., 2014; He et al., 2016]. Though improved performance is reported on many problems, these methods have made linearity assumption on the data, which may be inappropriate for multiview data revealing nonlinearities.

Kernel method [Hofmann et al., 2007] is a principled way for introducing nonlinearity into linear models, and a kernel machine can approximate any function or decision boundary arbitrarily well by tuning its kernel parameter. Along this line, many single kernel multi-view learning methods have been proposed [Farquhar et al., 2005; Szedmak and ShaweTaylor, 2007; Fang and Zhang, 2012; Sun and Chao, 2013; Quang et al., 2013; Xu et al., 2014], which typically require the user to select and tune a predefined kernel for every view. Choosing an appropriate kernel for real-world situations is usually not easy for users without enough domain knowledge. The performance of these models may be greatly affected by the choice of kernel. An alternative solution to resolve this problem is provided by multiple kernel learning (MKL), which can predefine different kernels for each data view and then integrate the kernels by algorithms such as semi-definite programming (SDP) [Lanckriet et al., 2004], semi-infinite linear programming (SILP) [Sonnenburg et al., 2006], and simple MKL [Rakotomamonjy et al., 2008]. However, MKL models inherently have to compute and store many Gram matrices to get good performance while computing a Gram matrix for a data set with N instances and D features needs O(N 2D) operations and storing too many Gram matrices often leads to out of memory on commonly used computers. Besides, all the aforementioned kernelized models seek single point estimation of their parameters, thus are prone to overfitting to small training data. Under the Bayesian framework, BEMKL [Gonen, 2012] is a state-of-the-art variational method that estimates the entire posterior distribution of model weights. Unfortunately, BEMKL has to perform timeconsuming matrix inversions to compute the posterior covariances of sample and kernel weights. Moreover, BEMKL's performance may be limited by its mean-field assumption on the approximate posterior and the absence of max-margin principle.

To address the aforementioned problems, we propose an adaptive kernel maximum margin multi-view learning (M3L) model with low computational complexity. Specifically, we firstly propose an efficient multi-view latent variable model (LVM) based on the traditional Bayesian Canonical Correlation Analysis (BCCA) [Wang, 2007], which learns the shared latent representations for all views. To adaptively learn the kernel, we introduce the random Fourier features which constructs an approximate primal space to estimate kernel evaluations K(x, x′ ) as the dot product of finite vectors ϕ(x)T ϕ(x′ ) [Rahimi and Recht, 2007]. Assuming these random features are drawn from Dirichlet process (DP) Gaussian mixtures, we can adaptively learn shift-invariant kernels from data according to Bochners theorem. With such a stochastic random frequency distribution, it is more general than the traditional kernel method approach with a fixed kernel. Secondly, to make full use of the label information, we impose max-margin classification constraints on the explicit expressions ϕ(x) in random Fourier feature space. Next, we regularize the posterior of the efficient multi-view LVM by explicitly mapping the latent representations to a random Fourier feature space where max-margin classification constraints are imposed. Our model is based on the data augmentation idea for max-margin learning in the Bayesian framework, which allows us automatically infer parameters of adaptive kernel and the penalty parameter of max-margin learning model. For inference, we devise a hybrid Markov chain Monte Carlo (MCMC) sampler. To infer random frequencies, we use an effective distributed DP mixture models (DPMM) [Ge et al., 2015]. Moreover, some key parameters don't have corresponding conjugate priors. So we adopt the gradient-based MCMC sampler Hamiltonian Monte Carlo (HMC) [Neal, 2011] for faster convergence. The computational complexity of our algorithm is linear w.r.t. the number of instances N. Extensive experiments on real-world datasets demonstrate our method has a superior performance, compared with a number of competitors.

2 Model

BCCA [Wang, 2007] assumes the following generative process to learn the shared latent representations from multiple views {xi}Nv i=1 , where Nv is the number of views:

where N(·) denotes the normal distribution, h ∈ Rm is the shared latent variable, Wi ∈ RDi×m is the linear transformation and Ψi ∈ RDi×Di denotes covariance matrix. A commonly used prior is the Wishart distribution for Ψ-1 i .

2.1 An Efficient Multi-view LVM

However, BCCA has to perform time-consuming inversions of the high-dimension covariance matrix Ψi which could result in a severe computational problem. To solve the problem, we propose an efficient model by introducing additional latent variables. We assume the following generative process:

where ui ∈ RKi is the additional latent variable. Gamma prior can be used for τi and popular automatic relevance determination (ARD) prior can be imposed on projection matrices Wi, Vi ∈ RDi×Ki , i.e.,

where i = 1, · · · ,Nv, Γ(·) denotes Gamma distribution, wi,·j represents the j-th column of the transformation matrix Wi and vi,·j represents the j-th column of Vi. This model can be shown to be equivalent to imposing a low-rank assumption Ψi = ViVT i + τ -1 i I for the covariances, which allows decreasing the computational complexity.

We define that the data matrix of the i-th view is Xi ∈ RDi×N consisting of N observations {xni }Nn=1 , ˜X = {Xi}Nv i=1 , H = {hn }Nn=1 and Ui = {uni }Nn=1 . For simplicity, let Ω = (ri,Vi,Wi, η, τi,H,Ui) be the parameters of the multi-view LVM and p0(Ω) be the prior of Ω. We can verify that the Bayesian posterior distribution p(Ω| ˜X) = p0(Ω)p( ˜X|Ω)/p( ˜X) can be equivalently obtained by solving the following optimization problem:

where KL(q‖p) is the Kullback-Leibler divergence, and P is the space of probability distributions. When the observations are given, p( ˜X) is a constant.

2.2 Adaptive Kernel M3L

From the description above, we can see that the multi-view LVM is an unsupervised model which learns the shared latent variables from the observations without using any label information. In general, we prefer that the shared latent representation can not only explain the observed data well but also help to learn a predictive model, which predicts the responses of new observations as accurate as possible.

Moreover, this multi-view LVM is a linear multi-view representation learning algorithm, but multi-view data usually reveal nonlinearities in many scenarios of real-world. As is well known, kernel methods are attractive because they can approximate any function or decision boundary arbitrarily well. So in this section we propose an adaptive kernel max-margin multi-view learning (M3L) model. With the method named random features for the approximation of kernels [Rahimi and Recht, 2007], we can get explicit expression of the latent variable h in random feature space. Then we can classify these explicit expression linearly by introducing the max-margin principle which has good generalization performance. To incorporate the nonlinear max-margin method to the unsupervised multi-view LVM, we adopt the posterior regularization strategy [Jaakkola et al., 1999; Zhu et al., 2012]. Suppose we have a 1 × N label vector y with its element yn ∈ {+1,-1}, n = 1, · · · ,N. Then we define the following pseudo-likelihood function of latent representation hn for the n-th observation {xni }Nv i=1 :

where C is the regularization parameter, ˜ ϕ(hn ) is the explicit expression of the latent variable hn in random Fourier feature space and ˜ ϕ(hn ) = (ϕ(hn )T, 1)T. ωi ∈ Rm denotes random frequency vector and βT ˜ ϕ(hn ) is a discrimination function parameterized by β ∈ R2M+1 .

Bochners theorem states that a continuous shift-invariant kernel K(h, ¯h) = k(h - ¯h) is a positive definite function if and only if k(t) is the Fourier transform of a non-negative measure ρ(ω) [Rudin, 2011]. Further, we note that if k(0) = 1, ρ(ω) will be a normalized density. So we can get

If the kernel k is real-valued, we can discard the imaginary part:

A robust and flexible choice of ρ(ω) is a Gaussian mixture model. Mixture models based on DPs treat the number of represented mixture components as a latent variable, and infer it automatically from observed data. DP Gaussian mixture prior is widely used for density estimation [Oliva et al., 2016]. Assuming these random features are drawn from DP Gaussian mixtures, we can adaptively learn shift-invariant kernels from data according to Bochners theorem. We impose DP Gaussian mixture prior for the variables ωj, j = 1, · · · ,M. Suppose the DP has base distribution G0 and concentration parameter α, then we have

where k = 1, · · · ,∞ and ζk = (µk,Σk) contains the mean and covariance parameters of the k-th Gaussian component. Popular choice would be Normal-Inverse-Wishart prior G0 for the mixture components:

where W-1 (·) denotes Inverse-Wishart distribution. Next, we impose prior on β as the following form

where av and bv are hyper-parameters and v plays a similar role as the penalty parameter in SVM.

For simplicity, let Θ = (β, v, νk,ϖk, ζk, zi,ωi,µk,Σk) be the variables of the nonlinear max-margin prediction model. Now, we can formulate our final modal as

where p0(Ω,Θ) is the prior, p0(Ω,Θ) = p0(Ω)p0(Θ) and p0(Θ) is the prior of Θ. By solving the optimization above, we get the desired post-data posterior distribution [Ghosh and Ramamoorthi, 2003]

where Ξ( ˜X, y) is the normalization constant.

3 Post-Data Posterior Sampling with HMC

As we can see, the post-data posterior above is intractable to compute. Firstly, the pseudo-likelihood function ℓ(·) involves a max operater which mixes the posterior inference difficult and inefficient. We introduce the data augmentation idea [Polson and Scott, 2011] to solve this problem. Secondly, the form of ˜ ϕ(hn ) mixes local conjugacy. So we adopt the gradient-based MCMC sampler for faster convergence. Thirdly, we introduce the ditributed DPMM to improve the efficiency. In the following, we devise a hybrid MCMC sampling algorithm that generates a sample from the post-data posterior distribution of each variable in turn, conditional on the current values of the other variables. It can be shown that the sequence of samples constitutes a Markov chain and the stationary distribution of that Markov chain is just the joint posterior.

3.1 Updating variables β, λn, ωj and hn

In this part, we develop a MCMC sampler for β, λn , ωj and hn by introducing augmented variables.

Data augmentation

The pseudo-likelihood function ℓ(·) involves a max operater which mixes the posterior inference difficult and inefficient. So we re-express the pseudo-likelihood function into the integration of a function with augmented variable based on the data augmentation idea:

Then we can get the non-normalized joint distribution of y and λ conditional on H and Θ:

Sampling β :

The conditional distribution of β is

where Λ = C(1 - ynβT ˜ ϕ(hn )). This conditional distribution is a Gaussian distribution with covariance Σβ = {vI2M+1 + ∑Nn=1 C2 ˜ ϕ(hn ) ˜ ϕ(hn )T λn }-1 and mean µβ = Σβ ∑Nn=1 ( Cλn+C2 λn )yn ˜ ϕ(hn )).

Sampling λn :

The conditional distribution over the augmented variable λn is a generalized inverse Gaussian distribution:

Sampling ωj, hn :

Unfortunately, we find the conditional distribution over ωj

where ˜ ϕ(hn ) = (ϕ(hn )T, 1)T = { 1 √M [cos(ωT 1 hn ), · · · , cos(ωTM hn ), sin(ωT 1 hn ), · · · , sin(ωTM hn )], 1}T is too complex and the prior is non-conjugated. So it is hard to get the analytical form of the above distribution. To generate a sample from q(ωj |H, λ, β, y) with its non-normalized density, we appeal to the HMC method [Neal, 2011]. Sampling from a distribution with HMC requires translating the density function for this distribution to a potential energy function and introducing 'momentum' variables to go with the original variables of interest ('position' variables). We need to constitute a Markov chain. Each iteration has two steps. In the first step, we sample the momentum which needs the gradient of the potential energy function. In the second step, we do a Metropolis update with a proposal found by using Hamiltonian dynamics.

Similar to ωj , we also find the conditional posterior distribution over hn

doesn't have the analytical form. So we can sample hn with the HMC sampler.

3.2 Updating the variables in distributed DPMM

Unlike a Gibbs sampler using the marginal representation of the DP mixtures, slice sampling methods [Walker, 2007;

Kalli et al., 2011; Ge et al., 2015] employ the random measure G directly. It consists of the imputation of G and subsequent Gibbs sampling of the component assignments from their posteriors. To be able to represent the infinite number of components in G0, we have to introduce some auxiliary (slice) variables tj, j = 1, · · · ,M. Through introducing an auxiliary variable tj, the joint density of ωj and the latent variable tj becomes

where 1(·) is the indicator function. We can easily verify that when tj is integrated over, the joint density is equivalent to p(ωj|ϖ, ζ). Thus the interesting fact is that given the latent variable tj, the number of mixtures needed to be represented is finite.

Through introducing the slice variable, the conditional posterior distribution of ωj becomes independent so it is possible to derive a parallel sampler for the DP mixture model under the Map-Reduce framework. Our parallel sampler in distributed DPMM is similar as that in [Ge et al., 2015], thus is omitted here.

3.3 Updating the other variables

In this part, the other variables all have the conjugate prior. So we get the analytic conditional posterior distributions of them.

Sampling uni :

The conditional posterior of uni is

a Gaussian distribution with covariance Σuni = (I + τiViTVi)-1 and mean µuni =Σuni [ViT(xni -Wihn )τi].

SamplingWi, Vi :

The conditional posterior distribution of Wi is proportional to the prior times the likelihood:

where j = 1, · · · ,m. This is a Gaussian distribution with covariance Σwi,·j = (rij +τi||hj·||2 )-1 I and mean µwi,·j =

Similar to Wi, conditional posterior of Vi is a Gaussian distribution with covariance Σvi,·j = (η + τi||ui,·j||2 )-1 I

Sampling ri, τi :

For each rij, j = 1, · · · ,m, its conditional distribution is

a Gamma distribution with the shape and rate parameter

Similar to sampling ri, the conditional distribution of τi is a Gamma distribution with the shape and rate parameter

Computational Complexity

In our post-data posterior sampling, the dominant computation is spent on sampling latent shared variables H. In each round of parameter sampling, our algorithm consumes

of steps for the leapfrog method in HMC. So the computational complexity of our algorithmM3LAK is linear w.r.t. the number of instances N.

4 Experiments

In this section, we evaluate our proposed model (M3LAK) on various classification tasks.

4.1 Data Description

The Flickr dataset contains 3,411 images of 13 animals [Chen et al., 2012]. For each image, two types of features are extracted, including 634-dim real-valued features and 500-dim bag of word SIFT features. Trecvid contains 1,078 manually labeled video shots that belongs to five categories [Chen et al., 2012]. And each shot is represented by a 1,894-dim binary vector of text features and a 165-dim vector of HSV color histogram. The web-page data set has two views, including the content features of the web pages and the link features exploited from the link structures. This data set consists of web pages from computer science department in three universities, i.e., Cornell, Washington, Wisconsin.

We transform these multi-class data sets into binary ones by following the way in [Zhuang et al., 2012]. For example, the web-page classification with five categories ('course', 'faculty', 'student', 'project', 'staff'), we select category 'student' as a group and the other four categories as another group, since the number of examples in category 'student' is similar with the one belonging to the other four categories. The other data sets are similarly constructed. The details of these data sets are shown in Table 1.

4.2 Baselines

We compare our model with five competitors:

• BM2SMVL [He et al., 2016]: a linear Bayesian maxmargin subspace multi-view learning method.
• MVMED [Sun and Chao, 2013]: a multi-view maximum entropy discrimination model.
• VMRML [Quang et al., 2013]: a vector-valued manifold regularization multi-view learning method.
• MMH [Chen et al., 2012]: a predictive latent subspace Markov network multi-view learning model.
• BEMKL [Gonen, 2012]: a state-of-the-art Bayesian multiple kernel learning method which we use for multiview learning. For each view, we construct Gaussian kernels with 21 different widths {2-10 , 2-9 , ..., 210 } on all features using its public implementation 1 .

4.3 Experimental Setting

In M3LAK, we perform 5-fold cross-validation on training set to decide the regularization parameter C from the integer set {5, 6, 7, 8, 9} for each data set. The rest parameters are fixed as follows for all data sets, i.e., m = 20, M = 100, η = 1e+3, α = 1, ar = 1e-1, aτ = v = 1e-2, bτ = br = 1e-5. For fair comparison, the subspace dimension m in BM2SMVL and MMH is also fixed to 20 for all data sets. For BM2SMVL, the regularization parameter 'C' is chosen from the integer set {1, 2, 3} by 5-fold cross-validation on training set according to its original paper. For MVMED, we choose 'c' from 2[-5:5] for each data set as suggested in its original paper. For VMRML, the parameters are set as the default values in its paper. For RBF kernel's parameter of MVMED and VMRML, we carefully tune them on each data set separately. For MMH, we tune its parameters as suggested in its original papers. On each data set, we conduct 10-fold cross validation for all the algorithms, where nine folds of the data are used for training while the rest for testing. The averaged accuracies over these 10 runs are reported in Table 2.

4.4 Experimental Results

We have the following insightful observations:

• M3LAK consistently outperforms BM2SMVL. The reason may be that BM2SMVL is a linear multi-view method with limited modeling capabilities.
• On most data sets, M3LAK performs better than MMH. This may be because that unlike MMH which are under the maximum entropy discrimination framework, and can not infer the penalty parameter of max-margin models in a Bayesian style, our method is based on the data augmentation idea for max-margin learning, which allows us to automatically infer the weight parameters and the penalty parameter.
• M3LAK has better performance than the single kernel multi-view learning methods VMRML and MVMED on

1 http://users.ics.aalto.fi/gonen/bemkl/

all data sets. The reason may be that M3LAK infers a posterior under the Bayesian framework instead of a point estimate as in VMRML. With Baysian model averaging over the posterior, we can make more robust predictions than VMRML. And MVMED is also under the maximum entropy discrimination framework, and can not infer the penalty parameter of max-margin models in a Bayesian style.

• M3LAK performs better than BEMKL on most data sets. BEMKL's performance may be limited by its meanfield assumption on the approximate posterior and the absence of max-margin principle while M3LAK introduces the popular max-margin principle which has a great generalization ability. Although BEMKL performs better than M3LAK on some data sets, BEMKL has to perform matrix inversion to compute the posterior covariance of kernel weights in each round of iteration which requires O(N 3 ) operations. Besides, BEMKL needs to store many Gram matrix to get good performances. However, storing too many Gram matrix leads to out of memory on commonly used computers.

4.5 Parameter Study and Convergence

We study the performance change of the three subspace learning methods (BM2SMVL, MMH and M3LAK). Performances change when the subspace dimension m varies on two datasets (Cornell and Wisconsin). The averaged results are shown in Figure 1. As we can see, different methods prefer different values of m. On some datasets, when m becomes too large, the performances of these three methods become poor. When m ranges from 5 to 30, M3LAK performs better than other subspace learning methods in general.

Also, we set m as 20 and study the influence of regularization parameter C. From the results in Figure 2 (a) , we can find that different data sets may prefer different values of C. C balances the nonlinear classifier with adaptive kernel and the multi-view latent variable model, so M3LAK cannot get the best performance when C is too large or small.

Figure 2 (b) shows the convergency of M3LAK on two data sets. We find that M3LAK has a fast convergence rate, which we contribute to the efficient gradient-based HMC sampler [Neal, 2011].

5 Conclusion

In this paper, we present an adaptive kernel nonlinear maxmargin multi-view learning framework. It regularizes the posterior of an efficient multi-view LVM by explicitly mapping the latent representations extracted from multiple data views to a random fourier feature space where max-margin classification constraints are imposed. Having no need to compute the Gram matrix, the computational complexity of our algorithm is linear w.r.t. N. Extensive experiments on real-world datasets demonstrate our method has a superior performance, compared with a number of competitors.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 61473273, 61602449, 91546122, 61573335, 61602438, 61473274), National High-tech R&D Program of China (863 Program) (No.2014AA015105), Guangdong provincial science and technology plan projects (No. 2015 B010109005), the Youth Innovation Promotion Association CAS 2017146.