Generalized Dictionary for Multitask Learning with Boosting

1 Introduction

Multitask learning [Caruana, 1997] is a learning paradigm that aims to improve learning performance across many tasks by leveraging information and knowledge that is shared across tasks. It has been demonstrated both theoretically [Ben-David and Schuller, 2003; Ando and Zhang, 2005; Maurer et al., 2013] and empirically [Argyriou et al., 2007; Liu et al., 2009; Kumar and Daum´e III, 2012; Hern´andezLobato et al., 2015] that generalization performance can be improved by learning multiple tasks jointly, in contrast to learning each task individually, especially when training samples for each task are limited and the number of tasks is large.

One key assumption of multitask learning is that the tasks are related to each other and therefore there is some underlying relatedness structure that can be exploited and shared across tasks. Examples of such structure include the model parameters lying close to each other [Evgeniou and Pontil, 2004] in a low dimensional subspace [Ando and Zhang, 2005], manifold [Agarwal et al., 2010], or sharing similar sparsity patterns [Liu et al., 2009; Obozinski et al., 2010].

One drawback of most multitask approaches is that they assume that all the tasks are related to each other. This is restrictive in real world applications where the tasks may share knowledge in a more complicated way. To address this issue, algorithms have been proposed to model more sophisticated task relatedness structures. For example, some methods assume that the tasks can be clustered into groups, and that tasks within each group are similar to each other [Xue et al., 2007; Jacob et al., 2008; Kang et al., 2011]. Other models consider the existence of outlier tasks [Chen et al., 2011; Gong et al., 2012] or hierarchical structure of model parameters [Zweig and Weinshall, 2013]. Task relatedness has also been modeled by correlations [Zhang and Yeung, 2010; Zhang and Schneider, 2010] or tree structures [Kim and Xing, 2010]. Finally, the dictionary learning approach [Kumar and Daum´e III, 2012; Maurer et al., 2013] offers another method for multitask learning and can model various relatedness structures such as disjoint grouping, partial overlap, and outlier tasks. Its generalization performance has been analyzed in [Maurer et al., 2013; 2014].

However, most existing methods are limited to learning a linear model of tasks, which restricts their potential for addressing more complex nonlinear problems. Although some kernel methods have been proposed for this issue [Yu et al., 2005; Evgeniou et al., 2005], they usually require welldefined kernel functions which can be difficult to specify. In addition, the computational complexity of kernel algorithms grows cubically with the number of training samples, which limits their applications on large datasets. There have also been boosting-based multitask learning algorithms proposed in [Chapelle et al., 2010; Becker et al., 2013], but both of these approaches implicitly assume that all the tasks are related to each other, and fail to capture more sophisticated task relatedness such as grouped and/or outlier tasks.

In this paper, we propose a generalized dictionary learning algorithm for multitask learning. The starting point of our method is similar to the dictionary multitask learning (DMTL) approach [Kumar and Daum´e III, 2012], assuming that the model parameters of the tasks lie in a low dimensional subspace spanned by a linear dictionary. We extend this by constructing a nonlinear mapping defined by a generalized dictionary, which allows us to handle datasets that are difficult to model by linear algorithms. More specifically, instead of learning a dictionary of basis vectors as in DMTL, we learn a more generalized dictionary that contains a set of basis functions in function space. We optimize the set of basis functions using gradient boosting, and call the approach generalized dictionary multitask learning with boosting (GDMTLB). There are several advantages to the GDMTLB: 1. Compared with DMTL, GDMTLB produces more expressive nonlinear models to tackle complex problems arising from real world applications. 2. As a meta-learning algorithm, GDMTLB offers out-of-the-box usability and allows arbitrary learning algorithm to be used for multitask learning. 3. Compared with other nonlinear multitask learning approaches (e.g., [Chapelle et al., 2010]), GDMTLB can capture sophisticated task relatedness structures by using dictionary learning and sparse coding. 4. It offers theoretical guarantee of generalization bound, which gives the insight into the nature of the algorithm.

2 Method

We being this section by formulating the problem and describing the generalized dictionary learning framework for multitask learning. We then derive learning algorithms for specific loss functions and problems, based on the idea of functional gradient descent [Friedman, 2001; Mason et al., 2000], leading to our boosted dictionary learning algorithm.

2.1 ProblemFormulation

Let ¶S1↪ ▷ ▷ ▷ ↪ ST♦ be T related tasks, where St = ¶(xt1 ↪ yt1 )↪ ▷ ▷ ▷ (xtNt ↪ ytNt )♦ are the d-dimensional training samples for the t-th task. In the DMTL approach [Kumar and Daum´e III, 2012; Maurer et al., 2013], the objective is to learn a linear model parameter wt 2 Rd for each task, which is sparse coded by wt = Dγt, where D 2 Rd⇥M is the dictionary shared across the tasks, γt 2 RM is the sparse coefficient vector for the t-th task, M is the size of dictionary. Formally, the goal is to minimize the following objective function:

where h·↪ ·i is an inner product, `(·↪ ·) is a loss function, ♣♣ · ♣♣1 is the `1 norm used to encourage sparsity of the coefficients ¶γt♦, R(·) is the regularization term imposed on dictionary D to avoid overfitting, and θ and λ are the regularization parameters. It has been proven that given M ⌧ d and M < T , the DMTL algorithm can have a lower generalization error bound than learning T tasks separately [Maurer et al., 2013].

The main drawback of this approach (as well as others in the literature) is that it only considers linear hypotheses, which cannot properly deal with nonlinear problems. The principal contribution in our paper is to propose a more flexible learning framework that can accommodate any existing algorithm to model nonlinearity in multitask learning scenarios. Specifically, instead of learning a d ⇥M matrix D, we consider a generalized dictionary F(·) = [f1(·)↪ ▷ ▷ ▷ ↪ fM(·)], where fm(·)↪ m = 1↪ ▷ ▷ ▷ ↪ M can be any hypothesis:

Note that we have omitted the regularization term R(F), since we later will use the trick of gradient approximation to avoid overfitting, as detailed in [Friedman, 2001].

The dictionary D in Eq. 1 can be regarded as a linear mapping from x 2 Rd to z = D>x 2 RM . The DMTL algorithm can be retrieved as a special case of GDMTLB by setting F(x) = D>x. In this paper, we focus on the more general case where the atoms of dictionary F are the set of nonlinear mappings.

Eq. 2 can be optimized by the alternating optimization approach [Bezdek and Hathaway, 2003], as detailed in Algorithm 1. More precisely, we alternate between the following two optimization steps:

Sparse Coding (Line 4 of Algorithm 1)

Given a fixed hypothesis set, Eq. 2 can be decomposed into T individual `1-regularized optimization problems:

for t = 1↪ ▷ ▷ ▷ ↪ T, which can be solved efficiently by many algorithms (e.g., two-metric projection, coordinate descent, accelerated gradient method).

Generalized Dictionary Learning (Line 6 of Algorithm 1) The second objective is to learn a dictionary over any hypothesis class, rather than a matrix of linear mapping or some specific model, which motivates us to perform gradient descent of F in function space. In particular, we treat F as a set of parameters, and solve Eq. 2 as a sum of component dictionaries:

where K is the number of weak learners/dictionaries. We select Hk such that the Frobenius distance between Hk and the negative gradient of L at F = Fk-1 is minimized:

Let ↵t(x) , hF(x)↪ γti and using chain rule, the gradient of the loss function ` with respect to F(x) is given by

Algorithm 1 Generalized Dictionary for Multitask Learning

Input: ¶S1↪ ▷ ▷ ▷ ↪ ST♦, maxIter, the number of iterations K,

the number of basis hypotheses M, regularization parameter θ1: Initialize F 2: while n < maxIter do 3: for t = 1↪ ▷ ▷ ▷ ↪ T do 4: Solve Eq. 3. 5: end for 6: Learn a generalized dictionary given ¶γt♦. (Detailed in Algorithm 2 and Algorithm 3.) 7: n = n+1 8: if converge then 9: break 10: end if 11: end while

By choosing different loss functions ` we can obtain different learning algorithms, suitable for different types of problems. More important, by using a gradient boosting approach, the basis functions ¶fm♦ of F are decoupled and therefore can be learned individually and efficiently, as detailed below.

2.2 Exponential Loss for Classification

We first consider an AdaBoost-type [Freund and Schapire, 1997] algorithm, which minimizes the exponential loss `(hF (x)↪ γi↪ y) = exp(-yhF (x)↪ γi), where y 2 ¶-1↪ +1♦. Given fixed ¶γt♦, the gradient for exponential loss over ¶xti ↪ yt i ♦ at F = Fk-1 is given by

Plugging Eq. 7 into Eq. 4 gives

for m = 1↪ ▷ ▷ ▷ ↪M, where wt i , exp (-yt i hFk-1(xti )↪ γti), hk↪m is the m-th basis function of Hk, γt↪m is the m-th entry of γt. As we focus on classification problems, we have h(x) 2 ¶1↪+1♦. Therefore, Eq. 8 is equivalent to

Eq. 9 reveals that the solution of Eq. 4 can be decomposed into M individual learning problems, and for each we learn a hypothesis that minimizes the weighted error rate in predicting the label y. In addition, at the k-th iteration, for the m-th basis function, the weight for a sample ¶xti ↪ yt i ♦ is determined by vt i↪k↪m , γt↪mwt i . As ¶γt♦ are sparse vectors, each basis hypothesis is only trained on the tasks with non-zero coefficients ¶γt↪m♦. This is reasonable, since γt↪m = 0 means that the m-th basis function is not involved in predicting the t-th task, and therefore samples from the t-th task should not contribute to the training of the m-th base learner. This is

Algorithm 2 AdaBoosted Dictionary Learning

Input: ¶S1↪ ▷ ▷ ▷ ↪ ST ♦, ¶γt♦, the number of iterations K, number of

13: end for

basis hypothesises M, 1: Initialize wt i = 1N for t 2 ¶1↪ ▷ ▷ ▷ ↪ T♦, i 2 ¶1↪ ▷ ▷ ▷ ↪Nt♦, where N = PTt=1 Nt. 2: for k = 1↪ ▷ ▷ ▷ ↪K do 3: for m = 1↪ ▷ ▷ ▷ ↪M do 4: for t = 1↪ ▷ ▷ ▷ ↪ T do 5: vt i↪k↪m = γt↪mwt i for i 2 ¶1 ▷ ▷ ▷Nt♦ 6: end for 7: Normalize vt i↪k↪m 8: hk↪m = arg minh PTt=1 PNt i=1 vtk↪m (yt i 6= h(xti)) 9: end for 10: Compute error: ✏k = PTt=1 Pyt i 6=signhHk(xti )↪γti wt i 11: Compute ⇢k = 12 ln 1-✏k ✏k 12: Set wt i wt i · exp(βk (yt i 6= signhHk(xti)↪ γti)), followed by a normalization step.

not only computationally efficient but also introduces grouping and/or partial overlap effects that enable the algorithm to selectively share information across tasks, as in [Kumar and Daum´e III, 2012].

To obtain the step size ⇢k, we differentiate Eq. 5 with respect to ⇢k and set it equal to zero. Using some simple calculation, we determine ⇢k analytically:

where ✏k = PTt=1 Pyt i 6=signhHk↪γti wt i . The pseudo-code for dictionary learning for classification is shown in Algorithm 2.

2.3 Squared Loss for Regression

Alternately, we consider a regression problem, applying the proposed framework with squared loss `(hF(x)↪ γi↪ y) = 12 (hF (x)↪ γi - y)2 , where y 2 R. This yields an L2boostingtype [B¨uhlmann and Yu, 2003] dictionary learning algorithm. Given training sample ¶xti ↪ yt i ♦, the loss function with re-

spect to the m-th basis function fm can be reformulated as

where zt i = yt i -hF (xti )↪γti γt↪m + fm(xti ). Therefore, the original least square fitting problem can be reformulated as a weighted least square fitting problem for fm, where the weight is given by γ 2 t↪m. Differentiating Eq. 10 with respect to fm(xti ) gives

Plugging Eq. 11 into Eq. 4 gives

Algorithm 3 L2Boosted Dictionary Learning

Input: ¶S1↪ ▷ ▷ ▷ ↪ ST ♦, ¶γt♦, the number of iterations K, number of

where

for m = 1↪ ▷ ▷ ▷ ↪M. Again, each basis function of F can be learned separately by repeated weighted least square fitting of current residuals, where the weights of samples of the t-th task for the m-th basis function are given by γ 2 t↪m. For L2Boosting, the step size of Hk is not strictly necessary [B¨uhlmann and Hothorn, 2007], but it can be beneficial if we assign different step sizes to each basis function hk↪m (i.e., ⇢k is a vector of step sizes). Differentiating L with respect to ⇢k and setting equal to zero, we have

which gives

where diag(γt) is a diagonal matrix with the elements of vector γt on the main diagonal. The boosted dictionary learning algorithm with squared loss is summarized in Algorithm 3.

2.4 Dictionary Initialization

The dictionary F can be initialized in several ways. For example, we can first learn a linear dictionary by DMTL and use it as a warm start, or randomly select T 0 tasks to train each basis function. In this work, we consider both approaches and the better empirical results between the two are reported in the experimental section.

2.5 Computational Complexity

The computational complexity of GDMTLB depends on the choice of base learner, as well as the optimization algorithms used for sparse coding. We assume that the complexity of training a baser learner is O(⇠(N m tr ↪ d)), where N m tr is the number of training samples for the m-th atom of dictionary. In general N m tr  N, since the coefficients ¶γt♦ are sparse. Then, the overall complexity of each dictionary learning step will be O(KM⇠(N↪ d)). Note that we have omitted the complexity of testing and weight update step of boosting since it is usually much smaller than that of training cost. The sparse coding step requires solving a `1 regularized minimization problem (i.e., Eq. 3). If we use accelerated gradient descent [Nesterov, 2004], for each sparse coefficient γt, it takes O(dNt) to evaluate the function value and its gradient, and O(d) to project the point back onto `1 ball. As the convergence rate of this method is quadratic, the computational complexity of sparse coding step is O( 1 p" dN), where " is the error tolerance. Therefore, the overall complexity of each alternating optimization iteration is O(KM⇠(N↪ d) + 1 p" dN ), which scales linearly with K and M. Empirically, the entire GDMTLB algorithm usually stops within ten iterations.

2.6 Theoretical Analysis

The following theorem provides a generalization error bound for GDMTLB with exponential loss (Algorithm 2) and using linear functions as base learners. 1

Theorem 1. Let G = (G1 ↪ ▷ ▷ ▷ ↪GT ) : Rd ! RT , with Gt (x) = hF(x)↪ γti, be the multitask classifier returned by GDMTLB with exponential loss, and G be the function class of G. Let ¶S1↪ ▷ ▷ ▷ ↪ ST♦ be T related tasks, where St = ¶(xt1 ↪ yt1 )↪ ▷ ▷ ▷ (xtNt ↪ ytNt )♦ are the d-dimensional training samples for the t-th task. For simplicity we assume that Nt = N↪ 8t 2 ¶1↪ ▷ ▷ ▷ ↪ T♦. Given G and a sample ¶xt ↪ yt ♦ of the t-th task, define loss function ` : RT ⇥R ! ¶0↪ 1♦ as `(G(xt )↪ yt ) = ytGt (x)0, where ! is the indicator function of event !. If the base learners of GDMTLB are linear functions, and ✏k < 1 2 ↪ 8k 2 ¶1↪ ▷ ▷ ▷ ↪K♦, then for any δ > 0 and fixed ⌧ > 0, with probability at least 1-δ, for all G 2 G, its generalization error E[`(G)] is bounded by

where λmax ⇣ ˆ⌃(Xt)⌘ = sup♣♣d♣♣1 PNi=1 hd↪ xti i. We have several remarks concerning Theorem 1.

1. From the learning bound, it can be observed that GDMTLB inherits the benefits from both AdaBoost and linear dictionary for multitask learning. A is the upper bound of the margin loss for AdaBoost [Mohri et al., 2012], while B and C are the upper bound of

1 The detailed proof can be found in our online supplementary materials https://sites.google.com/site/borriewang/.

• the Rademacher complexity of a linear dictionary-based multitask learning algorithm [Maurer et al., 2014].
• If the margin loss is small for a relative large ⌧, small generalization error is guaranteed. In addition, it can be proved that, under certain conditions, the upper bound A is reduced exponentially as a function of number of iterations K [Mohri et al., 2012], which justifies the advantage of our boosting approach for multitask learning. Finally, given a fixed function class, GDMTLB will succeed if we can design an effective algorithm that performs with error across all tasks through all iterations (i.e., ✏k are small), since it leads to lowmargin loss.
• B and C indicate the benefits of performing multitask learning using a dictionary learning approach. Note that C can be dominated by B for N ⌧ d, and compared with the individual task learning approach, B is lower by a factor of pM◁T , which demonstrates the advantage of multitask dictionary learning in high dimensional spaces by choosing M < T [Maurer et al., 2014].

3 Experiments

We now evaluate GDMTLB algorithm against several stateof-the-art algorithms on both synthetic and real-world datasets. Competitive methods include `2↪1-regularized multitask feature learning (MTFL) [Liu et al., 2009], tracenorm regularized multitask learning (Trace) [Argyriou et al., 2007], dictionary multitask learning (DMTL) [Kumar and Daum´e III, 2012], as well as a nonlinear boosted multitask learning algorithm (MultiBoost) [Chapelle et al., 2010]. In addition, single task learning (STL) is also used as the baseline algorithm, where the tasks are learned individually.

In all experiments, the hyper-parameters (e.g., M↪ θ, different dictionary initializations) are selected by cross-validation. Regression tree is used as the weak learner of GDMTLB for regression, and logistic regression is used as the weak learner for classification. Each dataset is evaluated by using 10 randomly generated 50/50 splits of the data between training and test set, and the average results are reported.

3.1 Synthetic Data

The synthetic dataset consists of 2-dimensional vectors, two groups of tasks, and 20 tasks per group. For the j-th task of the i-th group, the samples are generated by yij ⇠ cj · (xi> j wi + xi> j Pixij ) + ✏, where x ⇠ N(0↪ I), cj ⇠ U(0↪ 2), wi ⇠ N(0↪ 3I), ✏ ⇠ N(0↪ 1), Pi = Q>i Qi (each entry of Qi is sampled from a normal distribution), where N denotes the Gaussian distribution, U denotes the uniform distribution. Therefore, the parameters of the tasks within each group are identical up to a scaling factor. For each task, there are 30 training samples and 30 test samples.

Figures 2(a)-2(c) show the samples in the original feature space, where we observe that the data cannot be properly fitted by linear regression due to the nonlinearity of the data. Figures 2(d)-2(f) demonstrate the samples projected into a new feature space by nonlinear dictionary F, from which it can be observed that the samples of the first group (blue samples) exhibit linearity in the first dimension (Figure 2(e))

GDMTLB 3▷31◦0▷42 10▷11◦0▷07 0▷7936◦0▷008

while the samples of the second group (red samples) exhibit linearity in the second dimension (Figure 2(f)), which means the data can be well fitted by sparse linear regression in the new feature space. In other words, the nonlinear structure of tasks can be well captured by the dictionary F, where each basis function of F corresponds to one group of tasks. Each task within the group can be fitted by the corresponding basis function up to a scaling factor, which is the slope of linear fitting in the new feature space. This can be further illustrated by Figure 1, where it can be observed that after projection the outputs of each group of tasks are highly correlated with only one dimension (basis function) of the new feature space. The results of different algorithms, measured by root mean squared error (RMSE), are shown in the first column of Table 1, where we see that GDMTLB outperforms other multitask learning algorithms in this simple case. This is not surprising, since the linear multitask learning algorithms cannot fit nonlinear functions, while MultiBoost cannot capture the group structure of the tasks.

3.2 Real Data

Next, we evaluate multi-task methods on three real-world datasets, one for regression: London school data [Argyriou et al., 2007]; and two for classification: landmine data [Xue et al., 2007], and BCI Competition data 2 . We omit the description of the first two datasets as they are frequently used benchmarks for multitask learning. The BCI dataset consists of EEG signals from 9 subjects who are instructed with visual cues to perform left hand or right hand motor imagery. Each subject corresponds to a distinct task. For each subject, the EEG signals consist of a training set and a test set, each containing 72 trials. The main challenge of this problem is that the underlying task (i.e. patient) relatedness is unknown and the EEG data structure can be complex [M¨uller et al., 2003].

2 http://www.bbci.de/competition/iv/.

For the London school regression problem, RMSE is used for performance evaluation. Performance on the classification problems is measured using area under ROC curve (AUC) for the landmine data since the dataset is imbalanced, and classification accuracy for the EEG dataset. The results on the London school and landmine datasets are summarized in the second and third columns of Table 1, which again shows that GDMTLB improves the predictive performances over single task learning as well as other multitask learning algorithms. Table 2 presents the results on the EEG dataset. GDMTLB achieves the highest classification accuracy on four subjects, yielding an average improvement of 2.24% over all subjects, which is significant compared with other multitask learning approaches. Across all the experiments, the improvements of GDMTLB over STL is at least twice as much as other algorithms, which validates the effectiveness of our algorithm.

4 Conclusion

This paper presents a novel GDMTLB algorithm for multitask learning with nonlinear structure. The core idea is to apply gradient boosting to learn the dictionary in function space, which substantially enriches the expressiveness of the model. The proposed model can be applied to a variety of loss functions and can readily accommodate many choices of nonlinear base algorithms for multitask learning. We validate the effectiveness of allowing nonlinear model and dictionary learning through theoretical and empirical analysis. Perhaps one of the most promising future directions is to investigate use of deep neural network for the base learners [Bengio, 2012]; our approach could provide an appealing framework for learning multitask constraints over several such learners.

Acknowledgments

This work was supported by the Natural Sciences and Engineering Research Council (NSERC) through the Discovery Grants Program and the NSERC Canadian Field Robotics Network (NCFRN), as well as by the Fonds de Recherche du Quebec Nature et Technologies (FQRNT).