Fast and Robust Multi-View Multi-Task Learning via Group Sparsity

1 Introduction

In recent years, many real-world applications, such as web page classification, bioinformatics analysis, semantic image annotation and product recommendation, usually exhibit dual-heterogeneity [He and Lawrence, 2011], i.e., each task has heterogeneous features from multiple views (feature heterogeneity), and multiple tasks are probably correlated via one or more common views (task heterogeneity). For example, in web page classification, each web page has at least two views: text and image, and multiple labels, such as politics, science and sports. In image annotation, each image has features extracted from multiple sources, such as color histogram, edge direction and wavelet texture, and is probably annotated with multiple objects, like cat, dog, lion, etc.

In order to handle these heterogeneous datasets, MultiView Learning (MVL) and Multi-Task Learning (MTL) were proposed for feature heterogeneity and task heterogeneity, respectively. In order to improve the performance of a baseline learner, MVL aims to combine the information from multiple feature views, while MTL is proposed to learn multiple correlated tasks together. Experimental results in a variety of applications have shown the superiority of their performance against baseline learners. However no MVL method has considered heterogeneity of MTL and vice versa, limiting their application on the datasets with dual-heterogeneity.

To overcome the limitation of MVL and MTL, recently Multi-View Multi-Task Learning (MVMTL) has been proposed by considering both view consistency and task relationship [He and Lawrence, 2011]. Compared with MVL and MTL methods, it achieved much success on various realworld problems with dual-heterogeneity [Zhang and Huan, 2012; Jin et al., 2013; Lu et al., 2017]. However, there are still three challenges in MVMTL. 1) Feature learning should be applied in the learning phase. Multi-view multi-task datasets usually emerge in high-dimensionality, where only a subset of features, i.e, discriminative features, are useful, and the noisy features might reduce the prediction performance. 2) Modeling flexible view consistency is recently demanded, as it is possible that different views provide complementary information, rather than strictly consistent with each other. One simple example is web page classification, where the visual content is complementary to the text content. 3) The existence of task outliers and inconsistent views should be considered. For example, each of texts and images has unique information in web page classification.

To cope with the aforementioned challenges, we propose a fAst and robust method with Group sparsIty for multiview multi-task LEarning (AGILE), to capture a more flexible relationship among both tasks and views, and meanwhile discard useless features and views. To handle the dualheterogeneity in a robust manner, the weight matrix Θ of AGILE is decomposed into a sum of two group-sparse components: W and H. Specifically, for Challenges 1 and 2, W saves task relationship with selected task-common features by ℓ2,1-norm-based regularization, and models flexible view consistency by regularizing a new norm we call group trace lasso. For Challenge 3, H simultaneously captures task outliers and inconsistent views by penalizing a group lasso regularization. We illustrate the framework of AGILE in Fig. 1. To optimize the convex objective function of AGILE, we propose a fast optimization algorithm with global convergence, which has a linear time complexity w.r.t. the number of features and labeled samples. Empirical results on synthetic and real-world datasets demonstrate the superior performance of AGILE, compared with cutting-edge methods. The contributions of this work can be summarized into three-folds.

• We propose a robust MVMTL method, enabling to cope with dual-heterogeneity, select relevant common features, and capture task outliers and inconsistent views.
• To promote flexible view consistency, we propose the group trace lasso norm, which is regarded as a generalization of trace lasso [Grave et al., 2011].
• We develop a fast optimization algorithm to solve the convex objective function, and show that it has a linear time complexity in problem size.

2 RelatedWorks

To address the problems with dual-heterogeneity, IteM2 [He and Lawrence, 2011] was first proposed for MVMTL. IteM2 constructs a bi-partite graph for each view, and projects any two tasks to a new reproducing kernel Hilbert space based on their common views. However, it is a transductive method, which is designed only for problems with nonnegative features, and unable to generate predictive models for future testing samples. To overcome these limitations, inductive learning methods [Zhang and Huan, 2012; Jin et al., 2013] were later developed based on linear models and co-regularization [Sindhwani et al., 2005]. In [Zhang and Huan, 2012], regMVMT was proposed by minimizing the difference of predictive models for distinct tasks on the same view. A more general method, CSL-MVMT [Jin et al., 2013] was developed by assuming that a low-dimensional subspace is shared among related tasks with common views. But the two methods hold a strong assumption on view consistency, i.e., predictive models from different views should be consistent with each other on the unlabeled data, which probably violates the problem setting of various real-world problems. Inspired by linear discriminant analysis, MAMUDA [Jin et al., 2014] was proposed as a supervised feature extraction method to handle dual-heterogeneity via shared latent space among multiple views. Based on multilinear factorization machines, MFMwas recently proposed in [Lu et al., 2017] by learning both task-specific feature map and task-view shared multilinear structures. However, MFM is unable to directly capture inconsistent views and utilize a possible large amount of unlabeled data. In [Zhou et al., 2018], MVMTL is treated as a multi-objective optimization problem by integrating relationships among tasks, views and samples.

Existing MVMTL methods typically build the models on original features, however, irrelevant features would negatively influence the prediction performance. Besides, they usually assume that predictive models from multiple views are consistent, and multiple tasks are correlated, which is probably contradictory to real-world applications.

3 The AGILEMethod

3.1 Preliminary

In MVMTL, suppose that we have T tasks, and each task has V views. For the t-th task, let Xt = [X1t , ...,XVt ] ∈ Rnt×d and Ut ∈ Rmt×d be the labeled and unlabeled data matrices, respectively, where Xvt ∈ Rnt×dv is the v-th view data in the t-th task, ∀t, v. Each data matrix Xt is associated with a target vector yt ∈ Rnt , ∀t. Without loss of generality, for an arbitrary matrix A, ‖A‖F and ‖A‖∗ denote its Frobenius norm and trace norm, respectively. Additionally, we define ℓ2,1-norm by ‖A‖2,1 = ∑pi=1 ‖ai·‖2 , where ‖ai·‖2 is the ℓ2-norm of the i-th row ai· of A.

For the t-th task of a MVMTL problem, we consider a linear predictive function defined by

where θt = [θ1 t ; ...; θV t ] ∈ Rd with θv t ∈ Rdv denoting the weight vector for the v-th view of the t-th task, ∀t, v. Eq. (1) actually averages the prediction results from all the V views in the t-th task, ∀t. For simplicity, we omit the intercept in the linear model by assuming that samples and targets have been centered in column-wise.

3.2 Formulation

For robust MVMTL, we decompose the weight matrix Θ = [θ1, ..., θT ] ∈ Rd×T into two components W and H. It allows to model correlations among tasks and views by W, and capture tasks/views that are specific to some views/tasks by H, which cannot be fit into W. Thus, based on (1) and empirical risk minimization with squared ℓ2-norm loss, the optimization problem of AGILE is

where R(W) and R(H) denote the regularization terms on W = [w1, ...,wT ] and H = [h1, ..., hT ], respectively. R(W) aims to cope with dual-heterogeneity, while R(H) is designed to detect task outliers and inconsistent views.

To capture both task relationship and view consistency, R(W) is further decomposed into a sum of two parts. In terms of task relationship, we consider that multiple tasks are correlated based on an identical feature subset, i.e., taskcommon features. In this respect, the ℓ2,1-norm [Liu et al., 2009] is imposed onW to promote its row-sparsity (featurewise group sparsity). Since the ℓ2,1-norm regularizer ‖W‖2,1 encourages sparsity among features and non-sparsity among tasks, discriminative task-common features will be assigned larger values. In this way, irrelevant features are removed by relying on the complementary information from multiple views, and task relationship is modeled via the non-zero rows (common features) of W.

In terms of view consistency, the independence assumption [Belkin et al., 2006] of multiple views has been widely adopted by MVL methods [Blum and Mitchell, 1998; Sindhwani et al., 2005], indicating that predictive models from multiple views can achieve mutual agreement on the unlabeled data. On some practical applications, however, it is possible that a few views become useless for certain tasks due to noise pollution, thus the assumption is violated. To address this challenge, for the t-th task, we impose a novel group trace lasso norm ‖UtWt‖∗ , in which Wt is a special diagonal matrix whose diagonal elements are vectors {wv t }v,

with wv t ∈ Rdv denoting the v-th view weight vector of wt. In group trace lasso, UtWt is a matrix containing the predictions from multiple views (each in a column) on the unlabeled data Ut. Hence, its low-rankness imposes the relationships among views in the multi-view setting. If predictive models are restrictively consistent among multiple views, the rank of UtWt equals to 1. In addition, as shown in Sec. 3.3, the regularizer promotes group-sparsity among views, so that consistent views will get larger values while useless views are discarded by W. Therefore, we formulate R(W) by

where α and β are positive hyperparameters. In this way, W models task relationship by selecting common features, and promotes flexible view consistency by group trace lasso.

For robustness, we expect to capture both task outliers, that have specific supporting features, and inconsistent views, that are inconsistent to other views but provide complementary information. Thus, a group-sparsity inducing regularizer R(H) is imposed on H by treating each task-view pair as a group. Specifically, for the v-th view, view-specific task outliers are captured by regularizing ∑Tt=1 ‖hvt ‖2 , where hvt ∈ Rdv denotes the weight vector of the v-th view of ht. Similarly, for the t-th task, task-specific inconsistent views are detected by regularizing ∑Vv=1 ‖hvt ‖2 . By summing over V views and T tasks on these two terms, we have

where ‖·‖G1 denotes the Group ℓ1-norm of groups {hvt }t,v, and γ is a positive hyperparameter. Once the t-th task is a outlier in the v-th view, or the v-th view is inconsistent in the t-th task, corresponding hvt would take arbitrary values, otherwise zero.

Based on (2), (4) and (5), we now have the optimization problem for the proposed AGILE method:

(6) where X ∈ R∑t nt×dT , U ∈ R∑t mt×dT and W ∈ RdT×V T are block diagonal matrices with the t-th blocks being 1 V Xt, Ut and Wt, respectively, and y = [y1; ...; yT ] ∈ R∑t nt . In (6), θ ∈ RdT denotes a vectorization of the weight matrix Θ. Note that, the equation ∑Tt=1 ‖UtWt‖∗ = ‖UW‖∗ holds based on Lemma 2.3 in [Recht et al., 2010].

3.3 Remarks on Group Trace Lasso

To model view consistency, some MVMTL methods [Zhang and Huan, 2012; Jin et al., 2013] adopt co-regularization [Sindhwani et al., 2005]. In contrast, AGILE applies a novel regularizer ‖UW‖∗ in (6) for saving flexible consistency. Following lemmas 1 present its important properties.

Lemma 1. For the t-th task, if predictions from multiple views are consistent, the following inequality holds,

where ‖·‖op denotes operator norm. If prediction from multiple views are orthogonal, the following inequality holds,

where ‖Utwt‖G1 = ∑Vv=1 ‖Uvt wv t ‖2 is Group ℓ1-norm. Lemma 2. For the t-th task, the following inequality holds,

Lemmas 1 and 2 tell us if predictions from two views are strongly consistent, the proposed norm behaves like ℓ2-norm on these two predictive models; if predictions from two views are orthogonal, the norm equals to the group ℓ1 norm, imposing group sparsity on {wv t }Vv=1 . Thus, it enables to equally penalize the two consistent views, and discard the useless inconsistent views. In this sense, this method lies in between the usual strict assumption of "all views contain 'exactly' the same information" and feature concatenation, which imposes no relationship among the weights.

Note that the proposed norm is similar with the trace lasso [Grave et al., 2011], since both impose a trace norm regularizer on the product of a data matrix and a diagonal matrix of model parameters. The difference exists in the diagonal matrix, where each diagonal element is a parameter in trace lasso, but a group (view) of parameters in the proposed norm. In other words, the proposed norm can be regarded as group trace lasso, as trace lasso is its special case, in which the number of parameters in each group is restricted to one.

1 The proofs are provided in supplementary materials: https: //www.dropbox.com/s/5koj44hmx4qb504/AGILE sup.pdf?dl=0.

4 Optimization Algorithm

Since the objective function (6) is jointly convex w.r.t. W and H, the global optimum is obtained by alternatively updating W and H. The trace norm in (6) is non-smooth and involves the product of U and W, thus it is impossible to directly employ the proximal gradient method. To circumvent this difficulty, we apply ADMM [Boyd et al., 2011] to optimize (6) by introducing an auxiliary variable P = UW, leading to the augmented Lagrangian defined as follows,

where Q is the scaled dual variable. The algorithm on solving (10) repeats the following three steps until convergence:

For Problem (a), we propose to solve it by proximal method [Nesterov, 2013], which decomposes its objective into two components, smooth f(Θ) and non-smooth g(Θ):

In the k-th iteration, the optimal solution can be calculated by the follow two proximal operators:

where ∇wf and ∇hf denote the derivatives of f(Θ) w.r.t W and H, respectively, and η is a step size, which satisfies

The optimization problems (12) and (13) can be analytically solved by applying soft thresholding operations as summarized in [Liu et al., 2009] and Lemma 3, respectively.

Lemma 3. If H∗ is the optimal solution of the optimization problem (12), its t-th column h∗t is given by the proximal operator, Sηγ(rt) = [Sηγ(r1t ); ...; Sηγ(rVt )], where

and rt denotes the t-th column of Hk - η∇hf(Θk ).

For Problem (b), it admits a closed-form solution by applying a matrix soft thresholding operation [Cai et al., 2010]. It is worth noting that, based on Lemma 2.3 in [Recht et al., 2010] and the fact that UW is a diagonal block matrix, Problem (b) can be decoupled for T tasks and solved efficiently.

4.1 Analysis on Time Complexity

In practice, we apply fast-ADMM [Goldstein et al., 2014] and accelerated proximal method [Nesterov, 2013] to accelerate the optimization algorithm 2 , leading to an optimal convergence rate of O( 1 k2 ) with k being the number of iterations.

In time complexity, for updating Θ, gradient calculation (∇wf and ∇hf) and soft thresholding have time complexities of O(d ∑t (nt + Vmt)) and O(dT), respectively. On updating P, matrix soft thresholding needs to conduct SVD on UW, resulting in a time complexity of O(V ∑t m2t ). Therefore, the total time complexity of each iteration is O(d(∑t nt +V mt +T )+V ∑t m2t ), in a linear complexity w.r.t. the number of features and labeled samples.

5 Experiments

5.1 Experimental Setting

Synthetic Data

For the generation of synthetic datasets, the number of tasks and views are set as T = 12 and V = 6, respectively, and each task has n = 150 labeled and m = 150 unlabeled data. The dimensionality dv of each view is selected from 30 to 60 by step 6, with d = ∑v dv = 300. The data matrix X1 ∈ Rn×d1 and the weight matrix W1 ∈ Rd1×T from the 1-st view are randomly sampled from normal distributions N(0, 25) and N(0, 16), respectively. In W1 , top 30% of the features are treated as useful features by setting 70% of rows to 0. To keep view consistency, Xv ∈ Rn×dv and Wv ∈ Rdv×T (v > 1) are generated by Xv = X1Pv⊤ and Wv = PvW1 , respectively, with constraints Pv⊤Pv = Id1 . Columns of Pv ∈ Rdv×d1 are left-singular vectors of a matrix randomly sampled from uniform distribution U(0, 1). Another weight matrix H ∈ Rd×T is randomly sampled from N(0, 16), where a certain set of {hvt }t,v is treated as outliers by assigning 0 to the rest. Finally, the target yt is calculated by yt = 1 V Xt(wt + ht) + δt, with δt ∼ N(0, 1) being stochastic noise.

Real-World Data

We conduct experiments on four real-world heterogeneous datasets: FOX, Mirflickr, NUS-Scene and NUS-Object. The FOX dataset is extracted from FOX web news [Qian and Zhai, 2014], while Mirflickr, NUS-Scene and NUS-Object refer to image annotation problem [Huiskes and Lew, 2008; Chua et al., 2009]. The statistics are summarized in Table 1, and more details are presented in supplementary materials.

2 The procedure of the algorithm is provided in the supplement.

Comparing Methods

We compare AGILE 3 with six cutting-edge methods: ElasticNet [Zou and Hastie, 2005], rMTFL [Gong et al., 2012], coMVL [Sindhwani et al., 2005], IteM2 [He and Lawrence, 2011], CSL-MVMT [Jin et al., 2013] and MFM [Lu et al., 2017]. As a generalization of ridge regression [Hoerl and Kennard, 1970] and lasso [Tibshirani, 1996], Elastic-Net is selected as a baseline method, while rMTFL and coMVL are selected as representative MTL and MVL methods, respectively. As state-of-the-art MVMTL methods, IteM2 , CSLMVMT and MFM 4 are introduced in comparison, and the codes are provided by corresponding authors.

Configuration

For evaluation, in each task, we randomly select a%, a%, 20% and 20% of total samples as labeled training set, unlabeled training set, validation set and testing set, respectively, and a is selected from {10, 20, 30}. We repeat this process five times, and report average results with standard deviation. In parameter setting, the weight balancing ℓ1 and ℓ2 regularizers in Elastic-Net is selected from {0.2, 0.4, 0.6, 0.8, 1}. As recommended in original papers, the dimensionality of latent space in CSL-MVMT and MFM is set as 20. Values for other parameters are selected from {10a ∣∣ |a| ∈ [3]}. For each iterative algorithm, we terminate it once the relative change of its objective is below 10-5 , and set the maximum number of iterations as 500. The performances of comparing methods are evaluated by Area Under ROC-Curve (AUC) and Accuracy.

5.2 Experiments on Synthetic Data

Illustration of Weight Matrix Decomposition

Weight matrix decomposition of AGILE on one designed synthetic dataset is illustrated in Fig 2, where Θ∗ = W∗+H∗ denotes the design truth model, and Θ = W+H is learned by AGILE with the setting α = 10, β = 1 and γ = 36. As shown in Fig. 2, AGILE successfully recovers the groupsparse pattern in Θ∗ by assigning group-sparsity to W and H. To validate group trace lasso, for each task we select one view as the useless view by assigning strong noise and 0 to corresponding Xvt and wv t , respectively, producing a featurewise and view-wise group-sparseW∗ in Fig. 2(a). As shown in Fig. 2(b), W detects not only noise features (row-sparsity) but also useless views (group-sparsity).

Comparison of MVMTL Methods

Next, we analyze the robustness of AGILE. In this experiment, we generate nine synthetic datasets by changing the percentage of task-view outliers in H from 10% to 90% by step 10%. Fig. 3 shows the comparison results of AGILE and three MVMTL methods in AUC and Accuracy, where AGILE consistently achieves superior performance.

To evaluate MVMTL methods in running time, we generate two sets of synthetic datasets by varying the number of training samples and features from 100 to 1000 by step 100, respectively. Fig. 4 reports the running time of AGILE and three MVMTL methods on these two sets of datasets. AGILE and IteM2 consume the least running time as increasing the data size. In contrast, the running time of MFM and CSLMVMT significantly increase as the number of training samples and features increases, respectively.

3 We provide the MATLAB code of AGILE at: https://github. com/futuresun912/AGILE.

4 MFM-F-S in [Lu et al., 2017] is used here for its best performance among the variants of MFM.

5.3 Experiments on Real-World Data

Evaluation of Comparing Methods

To evaluate the performances of comparing methods, an experiment on four real-world heterogeneous datasets is conducted. The ratio n/N of labeled training samples is selected from the set {10%, 20%, 30%}. Experimental results are reported in Table 2, where the best performance is highlighted in boldface. In Table 2, as n/N increases, the performances of comparing methods increase. AGILE obtains the best performance in 75% of total cases. This performance superiority probably comes from AGILE's ability on capturing task-view outliers and removing useless features. Another MVMTL method, CSL-MVMT, performs the second best among MVMTL methods, and competes with comparing methods except AGILE and rMTFL, indicating the importance on modeling dual-heterogeneity in real-world datasets. By handling task-heterogeneity, rMTFL performs better or comparable compared with Elastic-Net, and has a significant advantage on FOX, probably implying that task correlation is relatively strong in the FOX dataset. IteM2 performs worst on the used datasets, and one possible explanation is that it is originally designed for problems with non-negative features.

AUC

Accuracy

Analysis on the Effect of Regularizers

To evaluate the effect of regularizations used in AGILE, an experiment is performed by assigning 0 to α, β and γ in (6), respectively, and evaluation results on NUS-Object are shown in Fig. 5. As shown in Fig. 5, setting γ = 0 results in the largest performance loss in four out of six cases, demonstrating the importance of capturing task-view outliers on improving performance. Although setting β = 0 gives the least performance loss in half of cases, there is still a significant loss compared with the original AGILE.

Hyperparameter Sensitivity Analysis

The sensitivity of AGILE in three regularization parameters α, β and γ is investigated on NUS-Object. Specifically, α controls the row-sparsity of W, β measures the degree of view consistency and γ controls the group-sparsity of H. Values of the parameters are selected from the set

{10a ∣∣ |a| ∈ [4]}. Fig. 6 shows the experimental results in AUC with n/N = 30%. The subfigure on α and β is shown by fixing γ = 1, and the similar setting is used for the other two subfigures. As shown in Fig. 6, AGILE achieves its best performance on NUS-Object with α ≤ 101 , β = 100 and 101 ≤ γ ≤ 102 . Generally, it is recommended to assign smaller values to α and β, and a relatively larger value to γ.

6 Conclusion

In this paper, we propose a fast and robust MVMTL method, AGILE, by decomposing the weight matrix into two components, and adopting a joint regularization to promote groupsparsity. To select relevant features and model flexible view consistency, joint group-sparsity is imposed on the first component by ℓ2,1-norm and group trace lasso. To detect task outliers and inconsistent views, the second component is regularized by group ℓ1-norm to encourage its group sparsity. Thanks to the convexity of the objective function, a fast iterative algorithm is developed to solve it with global convergence. Experiments on both synthetic and real-world datasets demonstrate its effectiveness. It shows that in real MVMTL setting, data exhibit all the problems, like existence of noisy features, useless views and task-view outliers, and our method is flexible enough to handle it.

Acknowledgements

L. S. has been supported in part by JST ACCEL (grant number JPMJAC1503). C. H. N. has been supported in part by MEXT Kakenhi 18K11434. H. M. has been supported in part by JST ACCEL (grant number JPMJAC1503), MEXT Kakenhi (grant numbers 16H02868 and 19H04169), FiDiPro by Tekes (currently Business Finland) and AIPSE program by Academy of Finland.