Multiplicative Sparse Feature Decomposition for Efficient Multi-View Multi-Task Learning

1 Introduction

Multi-View Multi-Task Learning (MVMTL) is an important learning problem with a variety of interesting real-world applications, such as text categorization [He and Lawrence, 2011], bioinformatics analysis [Zhang and Huan, 2012], semantic image annotation [Jin et al., 2013] and web page classification [Lu et al., 2017]. The objective of MVMTL is to improve the prediction of targets by relying on dualheterogeneity [He and Lawrence, 2011]. Dual-heterogeneity comprises task-heterogeneity and feature-heterogeneity, indicating that multiple tasks possibly related with each other by the common views of samples, and each sample can have various representations from different views. A representative example is classification of protein functions, in which each protein is possibly associated with multiple functional classes, including metabolism, transcription and cellular organization, and has distinct features from multiple views, such as protein sequences and 3D structures.

The problems with single-heterogeneity have been extensively studied in Multi-Task Learning (MTL) and Multi-View Learning (MVL). The intuitive idea behind MTL/MVL is that, learning performance for one single task/view can be improved by leveraging samples from other related tasks/views. MVL captures feature-heterogeneity by saving view consistency in the way that predictive models from multiple views achieve mutual agreement on the unlabeled data [Blum and Mitchell, 1998; Hardoon et al., 2004]. In contrast, MTL saves task-heterogeneity by modeling task correlation and learning multiple correlated tasks together, based on joint regularization [Liu et al., 2009b; Gong et al., 2012a] or feature decomposition [Jalali et al., 2010; Han and Zhang, 2015].

Recent research has gradually shifted its emphasis from the problems with single-heterogeneity to the ones with dualheterogeneity. Several MVMTL methods have recently been proposed, based on joint regularization [Zhang and Huan, 2012], factorization machines [Lu et al., 2017], and multiobjective optimization [Zhou et al., 2018]. Current MVMTL methods usually suffer from three problems: (a) saving task correlation in the way that models of each task-pair are similar, which is too strong on many real problems, and results in a relatively large number of model parameters to learn; (b) building a learning model on original features, however, irrelevant features would harm the generalization ability, and it is probable that a group of correlated tasks shares group-specific features; (c) modeling strict view consistency, and assigning a same weight to different views. But it can be expected that multiple views provide supplementary information, and different views contribute distinct importance to the model.

To address all the three problems, in this paper, we propose a novel method via multiplicative Sparse feature decomPosition for muLti-vIew multi-Task learning (SPLIT), which decomposes the weight matrix Θ into three multiplicative components A, B and H. Under an assumption that tasks can be reconstructed by a small number of latent topics, Θ is first decomposed as Θ = WH by low-rank constraint matrix factorization, leading to a reduced number of effective parameters of Θ. To learn a topic-specific sparse model and a viewweighting scheme, W is further decomposed as W = A ◦ B by Hadamard (element-wise) product, where A and B select topic-specific relevant features and assign different weights to distinct topic-view pairs, respectively. Fig. 1 illustrates the multiplicative sparse feature decomposition. Our theoretical analysis shows two things: 1) the family of methods is equivalent to a joint regularization with a more general form of regularizers, and 2) feature-sparse component A is directly related to view-weighting component B, motivating us to derive a fast optimization algorithm in a linear complexity w.r.t. the data size. Promising empirical results on various datasets demonstrate the efficiency of SPLIT for MVMTL. We highlight the contributions of this paper as follows:

• We focus on the key missing points of current MVMTL methods, i.e. feature selectivity and viewweighting, and develop a new method that allows us to efficiently select relevant features and assign view-wise importance. This was not realized by any method so far.
• Theoretical analysis reveals that the equivalence between a general family of the proposed framework and the jointly regularized approach, leading to two novel MVMTL formulations.
• An efficient optimization algorithm is developed to solve the optimization problem in a linear time w.r.t. the data size, which has not been realized by any method so far.

We begin by discussing related works in Section 2. Next, we introduce the proposed SPLIT in Section 3. We provide theoretical analysis of a family of SPLIT in Section 4, and develop an efficient algorithm in Section 5. In Section 6, we present experimental results on evaluation. Finally, we conclude this paper in Section 7.

2 RelatedWorks

For Multi-task learning, based on the assumption that task relationship is shared through task-common features, regularization with ℓp,q-norm (p > 1, q ≥ 1) is imposed on the weight matrix to encourage group sparsity [Liu et al., 2009a; Gong et al., 2012a]. To capture both task commonality and specificity, feature decomposition approaches are proposed via decomposing the weight matrix into multiple components by summation [Chen et al., 2011; Gong et al., 2012b] or multiplication [Lozano and Swirszcz, 2012; Wang et al., 2016].

Multi-view learning aims to utilize features from different views to improve the performance of a baseline learner. Two types of methods, co-training [Blum and Mitchell, 1998; Muslea et al., 2006; Sun and Jin, 2011] and co-regularization [Sindhwani et al., 2005; Xie and Sun, 2015; Kan et al., 2016], are proposed to make predictive models from multiple views consistent on the unlabeled data.

For multi-view multi-task learning, IteM2 [He and Lawrence, 2011] 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. As an inductive learning method, CSL-MTMV [Jin et al., 2013] aims to mine a low-dimensional subspace shared among related tasks with common views. Based on multilinear factorization machines, MFM was recently proposed in [Lu et al., 2017] by learning both task-specific feature map and task-view shared multilinear structures. In [Li and Huan, 2018], asymmetric bilinear factor analyzers with rank constraints are applied to capture the interactions among tasks and views.

3 The ProposedMethod

3.1 Preliminary

For a MVMTL problem with V views and T tasks, given the data Xt = [X1t , ...,XVt ] ∈ Rnt×d of t-th task, where Xvt ∈ Rnt×dv denotes the v-th data with d = ∑v dv, we introduce a linear model to approximate the t-th target yt ∈ Rnt :

In (1), θt = [θ1 t ; ...; θV t ] ∈ Rd is the parameter model of the t-th task, with θv t ∈ Rdv being its sub-vector of the v-th view. For T tasks, we have Θ = [θ1, ..., θT ] ∈ Rd×T . For convenience, we omit the intercept in (1) by assuming that the input data and target have been centered in column-wise.

3.2 Methodology

In order to model task correlation efficiently, we assume that multiple tasks are correlated through a subspace constructed by a limited number of latent topics. For instance, in image annotation, the tags (tasks) "ocean" and "sky" can be treated as a single latent topic, since they typically emerge together and share similar color features. Thus, instead of directly learning Θ ∈ Rd×T , we impose a low-rank constraint on it, and restrict Θ to learn only a reduced number of effective parameters, which is much less than d × T . To this end, matrix factorization is applied to decompose Θ by Θ = WH, where W ∈ Rd×K and H ∈ RK×T with K denoting the number of latent topics, K ≤ T. Each column of W corresponds to one latent topic, and H is usually considered as a factor loading matrix, whose t-th column ht stores the coefficients of K latent topics for the t-th task. In this sense, the model parameter θt belonging to the t-th task enables to be reconstructed by θt = Wht. This low-rank constraint matrix decomposition not only captures task correlations, but also controls overfitting by reducing the model size.

In terms of multi-view sparse learning, it is possible that a small feature subset from one view is crucial to detect a certain topic, even though that view is not discriminative for the topic. In other words, we expect that each topic is supported by a specific subset of features, while different views contribute distinct importance. A real example is image annotation, where features from edge view are critical to detect a latent topic comprising tags (tasks) "car", "bus" and "truck", and almost irrelevant for the topic consisting of tags (tasks) "ocean" and "sky". Thus, to learn a topic-specific sparse model and a view-weighting scheme, for the v-th view of the k-th column (topic) of W, we decompose it by

where αvk ∈ Rdv aims at selecting topic-specific features for the v-th view, βv k ≥ 0 denotes the topic-specific weight of the v-th view, and 1dv is a all-one vector in size of dv. Therefore, the topic model W can be reformulated by

where B ∈ RV×K with βv k being the element in the v-th row of the k-th column, ∀t, v. In (3), A ∈ Rd×K and B ∈ Rd×K store the topic-specific sparse model and the view-weighting scheme, respectively, with the k-th column being αk = [α1k ; ...;αVk ] and βk = [β1 k ; ...; βV k ], respectively. We then use ℓ1-norm and Frobenius norm to regularize A and B, respectively, with ‖A‖1,1 = ∑ij |αij | and ‖B‖2F = ∑ij |βi j |2 . In this way, topic-specific irrelevant features will be discarded by A, while non-discriminative views will be assigned with small weights by B.

Inspired by above motivations, we decompose the model parameter Θ into a product of three component, i.e., Θ = WH = (A◦B)H, and propose the multiplicative multi-task multi-view sparse feature learning model as follows:

For the v-th view of the t-th task (∀t, v), we have

where hkt is the coefficient of the k-th topic for the t-th task.

4 Theoretical Analysis

In this section, we present theoretical analysis of a general form of (4), which helps us to develop an efficient algorithm for a family of SPLIT. This general form is formualted by

Table 1: A summary of conclusions of Theorem 1 with p, q ∈ {1, 2}. R(wvk) = 2s√‖wvk ‖pp is the regularizer w.r.t. wvk in (7).

where ‖·‖p denotes ℓp-norm with ‖α‖p = p√∑j |αj|p . Obviously, (6) becomes (4) with p = 1 and q = 2. The following theorem 1 shows that, under some conditions, (6) is equivalent to a jointly regularized model.

Theorem 1. Let ( ˆW, ˆH) be the optimal solution of the following optimization problem,

where wvk is the v-th view sub-vector of the k-th column of W. If { ˆA, ˆB, ˆH} is the optimal solution of (6), we have ˆW= ˆA ◦ ˆB, given γ = 2√λ2- p qs 1 λ p qs 2 and s = p+q 2q . In addition, the view-weighting component ˆB is related with the topicspecific sparse component ˆA by the following formula

Theorem 1 reveals the family in (6) is equivalent to a jointly regularized problem in (7) with a more general form of regulariers, while Eq. (8) implies the sparsity of the topic-specific component A is relative to the sparsity of the view-weighting component B. A direct instantiation of Theorem 1 with p = 1 and q = 2 is exactly related with (4). Table 1 summarizes the conclusions derived from Theorem 1 with p, q ∈ {1, 2}.

5 Optimization Algorithm

Despite of the equivalence of (4) and (7), here we aim to solve (4). It is because optimizing A and B separately is much easier than optimizing W directly, and B gives some insight into the relationship between views and topics. The objective function of (4) is convex w.r.t. A, B and H, respectively, which motivates us to develop an alternating algorithm. For simplicity, least squared loss is considered here. The algorithm repeats following three steps until convergence.

• (i) Update Awith fixed B and H:

It is a lasso-like problem, which can be solved by many efficient gradient descent optimization approaches. Let

1 Proofs are provided in the supplement: https://www.dropbox. com/s/vwl1jtt0qiso8j8/SPLIT sup.pdf?dl=0.

∇f(A) denote the derivative of the loss function in (9) w.r.t A, whose k-th column equals to

Then, proximal gradient descent method can be applied to update A according to

where soft(a, b) = sign(a)max(|a| - b, 0) is the soft thresholding operator, and µ is the learning rate determined by line search.

• (ii) Update B with fixed A and H: According to Theorem 1 and Table 1, B is solved with a closed-form solution.
• (iii) Update Hwith fixedW=A◦B:

Let ˜Xt = XtW, above problem has a closed-form solution, whose t-th column is calculated by

Since it typically follows K ≤ T ≪ d, the closed-form solution (13) can be efficiently computed.

Proposition 1. The proposed iterative optimization algorithm does not increase the objective function of (4) at each iteration, indicating that

in the (i + 1)-th iteration, with J(A, B, H) denoting the objective function of (4) w.r.t. A, B and H.

Proposition 1 guarantees that the optimization algorithm does not increase the objective value of (4) in each iteration. In practice, accelerated proximal method [Nesterov, 2013] is applied to accelerate the algorithm. In terms of time complexity analysis, updating A comprises two major steps, gradient computation and soft thresholding, resulting in time complexities of O(d(N + TK)) and O(dK), respectively, with N = ∑t nt being the total number of samples frommultiple tasks. Computation of B needs a time complexity of O(dK), and updating H with the closed-form solution has a time cost of O(K2 (N+TK)). Therefore, the total time complexity of each iteration is O((d +K2 )(N + TK)), which is linear in number of samples, features and tasks.

6 Experiments

6.1 Datasets and ComparingMethods

Four real-world datasets are used for performance evaluation, and their statistics are summarized in Table 2. We compare SPLIT with five methods for performance evaluation. Ridge regression [Hoerl and Kennard, 1970] and Lasso [Tibshirani, 1996] are selected as baseline methods. As representative MTL methods with multiplicative feature learning, MLL

Table 2: The statistics of used real-world datasets, where V and T denote the number of views and tasks, respectively, dv is the number of features in the v-th view (d = ∑v dv), and ntp/ntn is the number of positive/negative samples in the t-th task (nt = ntp + ntn).

[Lozano and Swirszcz, 2012] and MMTFL [Wang et al., 2016] enable to model various patterns of task-specific/taskcommon features, and outperform several MTL methods on real-world applications. As a state-of-the-art MVMTL method, MFM [Lu et al., 2017] is selected due to its superior performance compared with existing MVMTL methods. The proposed SPLIT 2 is implemented in two variants: SPLIT1 and SPLIT2, corresponding to p = 1 and p = 2, respectively, both with q = 2 in (6). The difference between them is that, for an irrelevant feature, SPLIT1 might shrink corresponding element in A to zero, and SPLIT2 might shrink it to a small non-zero value, instead.

6.2 Configuration

In evaluation, for each task we randomly select a%, 20% and 20% of its total samples as training set, validation set and testing set, respectively, with a ∈ {10, 20, 30}. We repeat this procedure five times, and report the mean value and standard deviation of two metrics, Area Under ROC-Curve (AUC) and Accuracy. Grid search is conducted on the evaluation set, and the best parameter setting is used for prediction on the testing set. For grid search, values of regularization coefficients of comparing methods are selected from {10a ∣∣ |a| ∈ {0, 1, 2, 3, 4}}. The dimensionality of latent space in MFM is set as 20, as recommended in [Lu et al., 2017]. The number K of latent topics of SPLIT is set according to KT ∈ {0.3, 0.5, 0.7, 0.9}. 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 1000.

6.3 Experiments on Simulated Datasets

Simulated Datasets

For simulated datasets, we set the number of tasks and views are set as T = 8 and V = 4, respectively, and select the dimensionality dv of the v-th view from {25, 42, 58, 75} with d = ∑v dv = 200. Each task has the same number (n = 200) of labeled samples. The weight matrix Θ is decomposed into three parts in a multiplicative way, i.e., Θ = (A◦B)H, with the latent dimensionality being K = 4. Elements of A ∈ Rd×K are randomly sampled according to normal distribution N(0, 16), while elements of B ∈ RV ×T and H ∈ RK×T are randomly sampled based on uniform distributions U(0, 1) and U(-1, 1), respectively. To make A and B sparse, a% and b% of total elements are assigned with value 0, respectively. Finally, for the t-th task, its target vector yt is calculated by yt = 1 V Xtθt +δt, where Xt is randomly sampled from normal distribution N(0, 25), and δt ∼ N(0, 1) denotes the stochastic noise.

2 We provide the MATLAB code of SPLIT at: https://github.com/ futuresun912/SPLIT.git.

Analysis on Feature Decomposition and Sparse Learning

We illustrate multiplicative feature decomposition of SPLIT on one designed synthetic dataset in Fig 2 3 , where ̂Θ = ( ̂A◦ ̂B) ̂H is learned by SPLIT with the setting λ1 = 101 , λ2 = 103 and η = 104 . The designed model Θ = (A ◦ B)H is shown in Fig. 1. As shown in Fig. 1 and Fig. 2, SPLIT1 successfully detects the underlying models by selecting topicspecific features in A, learning view-wise weights in B, and saving task correlation in W = A ◦ B and H.

Next, to evaluate the performance of SPLIT on handling the datasets with sparse underlying models, we conduct an experiment on ten synthetic datasets by varying the percentage of zero-elements (irrelevant features) in A from 0% to 90% by step 10%. Fig. 3 shows the comparison result of SPLIT1, SPLIT2 and two baseline methods, Lasso and Ridge, in AUC and Accuracy. As the sparsity of A increases, SPLIT1 and SPLIT2 consistently outperform two baselines with a significant advantage. The sparse ratio 0.7 in A seems to be a turning point for sparse methods (SPLIT1 and Lasso) and dense methods (SPLIT2 and Ridge). Sparse methods perform worse than their dense counterparts when the ratio is below 0.7, but outperform them once the ratio exceeds 0.7. It shows that sparse learning is necessary for MVMTL, when the underlying model is indeed sparse.

3 A quantitative comparison is presented in the supplement.

Analysis on Task Correlation Modeling

To model task correlation, SPLIT constructs multiple tasks based on a limited number of latent topics. We expect that it would avoid overfitting, and give computational efficiency. To evaluate this effect, we generate three simulated datasets by changing the number K∗ of latent topics with K∗ ∈ {1, 2, 4}, and apply SPLIT1 on each dataset by varying its number K of latent topics from 1 to 8 by step 1. As shown in Fig. 4, as the value of K increases, SPLIT consumes more running time, because it needs to learn a larger number of effective parameters. In terms of AUC, as the value of K∗ increases, SPLIT always achieves the best performance when K = K∗ . Therefore, once tasks are modeled by a small number of latent topics in one dataset, SPLIT has a chance to improve the performance in less running time.

6.4 Experiments on Real-World Datasets

Evaluation of Comparing Methods

For evaluation of comparing methods, we conduct an experiment on four real-world heterogeneous datasets, and report empirical results in AUC and Accuracy by Table 3 4 . In the experiment, we change the ratio n/N of training samples from 10% to 30% by step 10%. In Table 3, the best performance is highlighted in boldface. For all methods, we can see that as the ratio n/N increases, the performance in both AUC and Accuracy increases as well. Specifically, the two variants of SPLIT, SPLIT1 and SPLIT2, together perform the best in 20 cases out of total 24 cases. Such observation validates the effectiveness of SPLIT on handling MVMTL problems via multiplicative sparse feature decomposition. Its ability on selecting relevant features, weighting different views and saving task correlation, leads to a more powerful MVMTL learner. As multiplicative multitask learning methods, MLL and MMTFL perform the second best, and compete with SPLIT1 and SPLIT2 on the Caltech101 and NUS-Object datasets. It is probably because AUC

4 Statistical test on the results is provided in the supplement.

Accuracy

both of the methods enable to select task-specific features and encourage task correlations via common features. In terms of two baseline methods, Lasso outperforms Ridge regression in almost all the cases, indicating the importance on learning a sparse model for improving MVMTL.

Analysis on the Effect of View-Weighting

To demonstrate the effectiveness of view-weighting component B used in SPLIT, an experiment is performed by comparing SPLIT1 and SPLIT2 with a special variant SPLITλ2=0, which removes the view-weighting component B and decomposes Θ by Θ = AH. The training ratio is selected from {10%, 20%, 30%}, and comparison results are shown in Fig. 5. From Fig. 5, we can see that both SPLIT1 and SPLIT2 significantly outperform SPLITλ2=0. It shows that it is important to learn view-wise weights for performance improvement on the NUS-Scene dataset.

Sensitivity Analysis on Hyperparameters

To understand the behavior of SPLIT, sensitivity analysis on hyperparameters is conducted on NUS-Object with the training ratio being 30%. SPLIT has three regularization parameters λ1, λ2 and η, controlling topic-specific sparsity, viewwise importance and regression weight, respectively, and one parameter K on the latent dimensionality, controlling the strongness of task correlation. Values of λ1, λ2 and η are selected from {10a ∣∣ |a| ∈ {0, 2, 4, 6, 8}}, while the value of K is varied from 1 to 10 by step 1. Three experiments are conducted to evaluate the pairwise correlation between the parameters. The first experiment on λ1 and K is conducted by fixing λ2 = η = 1, and similar setting is applied for other two experiments. Fig. 6 leads to three conclusions: (1) as the value of K increases, the performance first increases, and then becomes stable once K ≥ 5; (2) compared to λ2 and η, the performance is more sensitive to the value change of λ1; (3) the best performance on NUS-Object is achieved by setting λ1 ≤ 102 , and λ2, η ≤ 104 .

7 Conclusion

In this paper, we propose a novel method, SPLIT, via multiplicative sparse feature decomposition, so as to address three challenges in MVMTL: saving task correlations efficiently, selecting relevant features and assigning view-wise weights. Our theoretical analysis provides an equivalence guarantee of SPLIT with a general form of joint regularization, according to which two formulations with specific settings are proposed and solved by an efficient optimization algorithm in a linear complexity w.r.t. the data size. Extensive experiments on a variety of datasets show that it is necessary for a successful MVMTL method to model task correlation, select relevant features and learn view-wise weights, and demonstrate that the proposed SPLIT enables to address the challenges in both simulated and real-world MVMTL applications.

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.