并行多任务学习论文阅读（一）（多任务学习速览）并行多任务学习论文阅读（一

最近导师让我做并行多任务学习方面的工作，我开始着手阅读这方面的论文并归纳一个大致的速览。首先，我们看看什么是多任务学习，然后我们主要聚焦于基于正则化的多任务学习方法（这也是目前学术界主要的并行对象），并在此基础上讨论如何分布式并行。
1、多任务学习介绍类似于迁移学习，多任务学习也运用了知识迁移的思想，即在不同任务间泛化知识。但二者的区别在于：

迁移学习可能有多个源域；而多任务学习没有源域而只有多个目标域。
迁移学习注重提升目标任务性能，并不关心源任务的性能（知识由源任务\(\rightarrow\)目标任务；而多任务学习旨在提高所有任务的性能(知识在所有任务间相互传递)。

下图从知识迁移流的角度来说明迁移学习和多任务学习之间的区别所示：

文章图片
不严格地说，多任务学习的目标为利用多个彼此相关的学习任务中的有用信息来共同对这些任务进行学习（一般会将各任务的损失函数加起来一起优化）。
形式化地，多任务学习的定义如下：给定\(T\)个学习任务\(\{\mathcal{T}_t\}_{t=1}^{m}\)，其中所有任务或者其中某些任务是相关的但不相同。多任务学习旨在利用这\(T\)个任务中的知识来提高所有\(\mathcal{T}_t\)的学习性能。
多任务学习按照学习任务性质不同可分为多任务监督学习、多任务无监督学习、多任务主动学习、多任务强化学习、多任务在线学习等。下面我们仅介绍最常见的多任务监督学习。
多任务监督学习每个任务都是监督学习，目的是学习样本到标签的的映射。形式化地说，给定\(t\)个监督学习的任务\(\{\mathcal{T}_t\}_{t=1}^T\)，每个任务各有一个训练集\(\mathcal{D}_t = {\{(\bm{x}_{ti}, y_{ti})}_{i=1}^{m_t}\}\)，其中\(\bm{x_{ti}} \in \mathbb{R}^{d}\)，\(y_{ti} \in \mathbb{R}\)。多任务学习的目标是根据\(T\)个任务的训练集学习\(T\)个函数\(\{f_t(\bm{x})\}_{t=1}^{T}\)，使得\(f_t(\bm{x}_{ti})\)可以很好的近似\(y_{ti}\)。学习完成后，\(f_t(\cdot)\)将用于对第\(t\)个任务中的新数据样本的标签进行预测。
接下来我们描述多任务学习的目标函数，若第\(t\)个任务的经验风险形式为\(\mathbb{E}_{(\bm{x_{ti}, y_{ti})\sim \mathcal{D}_t}}[L(y_{ti}, f(\bm{x}_{ti}; \bm{w}_t))]\)(设\(\bm{w}_t\)为第\(t\)个模型的参数)，则一般多任务学习的目标函数形式为

\[\begin{aligned} \underset{\textbf{W}}{\min} & \sum_{t=1}^{T}\mathbb{E}_{(\bm{x_{ti}, y_{ti})\sim \mathcal{D}_t}}[L(y_{ti}, f(\bm{x}_{ti}; \bm{w}_t))]\\ & = \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, f(\bm{x}_{ti}; \bm{w}_t))] \end{aligned} \]
（此处\(\textbf{W}=(\bm{w}_1,\bm{w}_2,...,\bm{w}_T)\)为所有任务参数构成的矩阵）
不过，如果我们直接对各任务的损失函数和\(\sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, f(\bm{x}_{ti}))]\)进行优化，我们发现不同任务的损失函数是解耦（decoupled）的，无法完成我们的多任务学习任务。在多任务学习中一种典型的方法为增加一个正则项[1][2][3]：

\[\begin{aligned} \underset{\textbf{W}}{\min} & \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, f(\bm{x}_{ti}; \bm{w}_t))]+\lambda g(\textbf{W})\\ & = f(\textbf{W}) + \lambda g(\textbf{W}) \end{aligned} \]
这里\(g(\textbf{W})\)编码了任务的相关性（多任务学习的假定）并结合了\(T\)个任务；\(\lambda\)是一个正则化参数，用于控制有多少知识在任务间共享。在许多论文中，都假设了损失函数\(f(\textbf{W})\)是凸的，且是\(L\text{-Lipschitz}\)可导的（对\(L>0\)），然而正则项\(g(\textbf{W})\)虽然常常不满足凸性（比如采用矩阵的核范数），但是我们认为其实接近凸的，可以采用近端梯度算法（proximal gradient methods）[4]来求解。
2、多任务监督学习多任务监督学习的关键是找到任务之间的相关性。根据找到的任务相关性不同，可分为基于特征的多任务监督学习、基于模型的多任务监督学习和基于样本的多任务监督学习。下面我们主要介绍基于特征和基于模型的这两种。
（1）基于特征的多任务监督学习的分类
特征变换: 即通过线性/非线性变换由原始特征构建共享特征表示。这种方法最招可追溯到使用多层前馈网络（Caruana, 1997）[5]，如下图所示：

文章图片
该示例中，假设所有任务的输入相同，将多层前馈网络的隐藏层输出视为所有任务共享的特征表示，将输出层的输出视为对\(T\)个任务的预测结果。
如果采用我们之前所提到的正则化框架，多任务特征学习（Multi-Task Feature Learning, MTFL）方法[6][7]（Argyrious等人，2006、2008）和多任务稀疏编码（Multi-Task Sparse Coding, MTSC）[8]方法（Maurer等， 2013）都通过酉变换\(\hat{\bm{x}}_{ti}= \textbf{U}^T\bm{x}_{ti}\)来为每个任务先构造共享特征表示, 再在此基础上为每个任务学习线性函数\(f_t(\bm{x}_{ti})=\langle \bm{a}_t, \hat{\bm{x}}_{ti} \rangle\)。设每个\(f_t(\bm{x}_{ti})\)的参数为\(\bm{a}_{t}\)，设线性函数的参数矩阵为\(\textbf{A}=(\bm{a}_1,...,\bm{a}_T)\)。该方法定义的优化问题表示如下：

\[\begin{aligned} & \underset{\textbf{A},\mathbf{U},\bm{b}}{\min} \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, \langle \bm{a}_t, \mathbf{U}^T\bm{x}_{ti} \rangle+b_t)]+\lambda ||\textbf{A}||_{2,1}^2 \\ & \text{s. t. } \quad \mathbf{U}\mathbf{U}^T = \mathbf{I} \end{aligned} \]
这里\(\mathbf{U} \in \mathbb{R}^{d \times d}\)是酉（正交）矩阵。
与MTFL不同, MTSC方法的目标函数定义为

\[\begin{aligned} & \underset{\textbf{A},\mathbf{U},\bm{b}}{\min} \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, \langle \bm{a}_t, \mathbf{U}^T\bm{x}_{ti} \rangle+b_t)] \\ & \text{s. t. } \quad ||\bm{a}_i||_{1} \leqslant \lambda , \quad i=1,2,..,m\\ &\quad\quad\quad||\bm{u}_j||_{2}\leqslant 1, \quad j=1,2,.., d^{'}，表示第j列 \end{aligned} \]
此时\(\mathbf{U}^T \in \mathbb{R}^{d^{'}\times d}(d^{'} 联合特征学习（joint feature learning）：通过特征选择得到原始特征的共享子集（shared feature subset），以做为共享的特征表示。我们常采用的方法是将参数矩阵\(\textbf{W}=(\bm{w}_1,...,\bm{w}_T)\)正则化使其称为行稀疏矩阵，从而去除特定特征对于线性模型预测的影响，只有对所有任务都有用的特征被保留。
所有正则化方法中，最广泛使用的是\(l_{p, q}\)正则化（即采用\(l_{p, q}\)范数做为正则项)，其目标函数为:

\[ \underset{\textbf{W}, \bm{b}}{\min} \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, \langle \bm{w}_t, \bm{x}_{ti} \rangle + b_{t})]+\lambda ||\textbf{W}||_{p, q} \]
\(l_{p, q}\)正则化的特例是\(l_{2, 1}\)[9][10](Obozinski等人，2006、2010)和\(l_{\infin}\)无穷正则化[11]（Liu等人，2009b）。\(l_{2, 1}\)正则化中采用\(l_{2, 1}\)范数\(||\textbf{W}||_{2, 1} = \sum_{i=1}^{d}||\bm{w}^{i}||_2\)（此处\(d\)为特征维度，\(\bm{w}^i\)为\(\textbf{W}\)第\(i\)行），\(l_{\infin}\)正则化采用\(l_{\infin}\)范数\(||\mathbf{W}||_{\infin}=\underset{1\leqslant i\leqslant d}{\max}\sum_{j=1}^{T}|w_{ij}|\)，即对所有行沿着行求和，然后求最大。为了获得对所有特征都有用的更紧凑的子集，Gong等人[12](2013)提出了上限\(l_{p, 1}\)惩罚项\(\sum_{i=1}^{d}\min(||\bm{w}^i||_p, \theta)\)，当\(\theta\)足够大时它将退化为\(l_{p, 1}\)正则化。
（2）基于模型的多任务监督学习
共享子空间学习(shared subspace learning)：该方法的假设参数矩阵\(\textbf{W}\)为低秩矩阵，以使相似的任务拥有相似的参数向量（即\(\textbf{W}\)的\(T\)个列向量尽量线性相关），以使\(T\)个任务的模型参数\(\bm{w_t}\)都来自一个共享低秩子空间。Ando和Zhang(2005)[13]提出了一个对\(\bm{w}_t\)的参数化方式，即\(\bm{w}_t = \bm{p}_t + \mathbf{\Theta}^T \bm{q}_t\)，其中线性变换\(\mathbf{\Theta}^T\in \mathbb{R}^{d^{'} \times d}(d^{'}
\[\begin{aligned} & \underset{\textbf{P},\mathbf{Q},\mathbf{\Theta},\bm{b}}{\min} \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, \langle \bm{p}_t + \mathbf{\Theta}^T \bm{q}_t, \bm{x}_{ti} \rangle + b_{t}]+\lambda ||\textbf{P}||_{F}^2 \\ & \text{s. t. } \quad \mathbf{\Theta}\mathbf{\Theta}^T = \mathbf{I} \end{aligned} \]
Chen等人(2009)[14]通过为\(\mathbf{W}\)增加平方Frobenius正则化推广了这一模型，并采用松弛技术将问题转换为了凸优化问题。
除此之外，根据优化理论，使用矩阵的核范数(nuclear norm, 有时也称迹范数(trace norm))\(||\mathbf{W}||_{*}=\sum_{i=1}^{\min(d, T)}\sigma_i(\mathbf{W})\)来进行正则化会产生地址矩阵，所以核范数正则化（pong等人）也在多任务学习中应用广泛，此时目标函数通常为：

\[ \underset{\textbf{W}, \bm{b}}{\min} \sum_{t=1}^{T} [\frac{1}{m_t}\sum_{i=1}^{m_t}L(y_{ti}, \langle \bm{w}_t, \bm{x}_{ti} \rangle + b_{t}]+\lambda ||\textbf{W}||_{*} \]
【并行多任务学习论文阅读（一）（多任务学习速览）】核范数是一rank function[15]（Fazel等人, 2001）的紧的凸松弛，可以用近端梯度下降法求解。
聚类方法：该方法受聚类方法的启发，基本思想为：将任务分为若个个簇，每个簇内部的任务在模型参数上更相似。
参考文献

[1] Evgeniou T, Pontil M. Regularized multi--task learning[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. 2004: 109-117.
[2] Zhou J, Chen J, Ye J. Malsar: Multi-task learning via structural regularization[J]. Arizona State University, 2011, 21.
[3] Zhou J, Chen J, Ye J. Clustered multi-task learning via alternating structure optimization[J]. Advances in neural information processing systems, 2011, 2011: 702.
[4] Ji S, Ye J. An accelerated gradient method for trace norm minimization[C]//Proceedings of the 26th annual international conference on machine learning. 2009: 457-464.
[5] Caruana R. Multitask learning[J]. Machine learning, 1997, 28(1): 41-75
[6] Evgeniou A, Pontil M. Multi-task feature learning[J]. Advances in neural information processing systems, 2007, 19: 41.
[7] Argyriou A, Evgeniou T, Pontil M. Convex multi-task feature learning[J]. Machine learning, 2008, 73(3): 243-272.
[8] Maurer A, Pontil M, Romera-Paredes B. Sparse coding for multitask and transfer learning[C]//International conference on machine learning. PMLR, 2013: 343-351.
[9] Obozinski G, Taskar B, Jordan M. Multi-task feature selection[J]. Statistics Department, UC Berkeley, Tech. Rep, 2006, 2(2.2): 2.
[10] Obozinski G, Taskar B, Jordan M I. Joint covariate selection and joint subspace selection for multiple classification problems[J]. Statistics and Computing, 2010, 20(2): 231-252.
[11] Liu H, Palatucci M, Zhang J. Blockwise coordinate descent procedures for the multi-task lasso, with applications to neural semantic basis discovery[C]//Proceedings of the 26th Annual International Conference on Machine Learning. 2009: 649-656.
[12] Gong P, Ye J, Zhang C. Multi-stage multi-task feature learning[J]. arXiv preprint arXiv:1210.5806, 2012.
[13] Ando R K, Zhang T, Bartlett P. A framework for learning predictive structures from multiple tasks and unlabeled data[J]. Journal of Machine Learning Research, 2005, 6(11).
[14] Chen J, Tang L, Liu J, et al. A convex formulation for learning shared structures from multiple tasks[C]//Proceedings of the 26th Annual International Conference on Machine Learning. 2009: 137-144.
[15] Fazel M, Hindi H, Boyd S P. A rank minimization heuristic with application to minimum order system approximation[C]//Proceedings of the 2001 American Control Conference.(Cat. No. 01CH37148). IEEE, 2001, 6: 4734-4739.
[16] 杨强等. 迁移学习[M].机械工业出版社, 2020.