面向大数据流的多任务加速在线学习算法

云计算、物联网、社交网络等新兴信息技术和应用模式的快速发展，越来越多的软件系统部署在以互联网为代表的开放、动态、难控和不确定的变化环境，产生了急剧增加的大数据流。大数据流以其实时性、无序性、无限性、易失性、突发性等显着特征,使得其与传统批量大数据在数据计算的要求、方式等方面有着明显的不同。大数据的批量计算首先进行数据的存储，然后再对存储的静态数据进行集中计算。Hadoop是典型的大数据批量计算框架，由HDFS分布式文件系统负责静态数据的存储，并通过MapReduce将计算逻辑分配到各数据节点进行数据计算和价值发现。而在流式计算中，无法确定数据的到来时刻和到来顺序，也无法将全部数据存储起来。此，不再进行流式数据的存储，而是当流动的数据到来后在内存中直接进行数据的实时计算。如Twitter的Stor、Yahoo的S4就是典型的流式数据计算框架。因此，如何通过创新性的数据分析方法实现对大数据流的快速、高效、及时的分析与计算,是大数据分析技术领域面临的新挑战。在围绕实时大数据流处理这一需求展开的研究中，在线机器学习算法采用数据流直接处理的模式，每次迭代处理一个随机流数据，学习变量的迭代更新只经过简单的计算，从而在实时性和准确率之间取得一个平衡，是解决该难题很有前途的方案，特别适合于训练流式大数据。

研究表明，许多大数据实际应用领域，如金融时间序列预测，自然语言处理，生物信息学多任务数据集分析等，同时学习多个相关的任务获取共享信息模式要优于单个任务分别学习的方式。还有一些应用，如协同过滤的用户特征矩阵优化与物品特征矩阵优化，矩阵分类等，优化对象本身是矩阵变量，直接类同于多任务学习算法的权重矩阵变量的求解。因此，近年来许多相关研究侧重于多任务学习框架，如文献不过这些工作大多是批训练模式，在线多任务学习框架的研究工作很少。

提出的正则化对偶平均方法(DA-STL, regularized dual averaging method for single task learning)，以凸函数优化为基础，通过迭代计算过去所有损失函数梯度值的平均值，降低优化目标表达式的求解复杂度，达到高效更新权重向量的目的。正则化对偶平均方法是单任务在线学习领域的标志性研究工作。基于正则化对偶平均思想，Yang提出了一多任务的在线学习框架并应用于多任务特征选择(DA-MTFS, dual averaging based multi-task feature selection)。DA-MTFS算法收敛率为()TO1，每次迭代时间与空间复杂度均为O(dQ)。其中，T为算法迭代次数，d为数据特征维度，Q是任务个数。显然，该算法依然存在在线算法面临的普遍问题：低计算复杂性常常与算法的低收敛率联系在一起。加速在线学习方面，提出了正则化对偶平均在线学习框架并讨论了加速分支的情况。提出了随机优化与在线学习的加速梯度方法。不过，这些算法的加速效果取决于参数的满足条件，极端情况下才能获得最优收敛率()21TO，并且讨论的都是单任务在线算法的加速效果。

提出了一种迹范数最小化加速梯度方法，在理论上证明了多任务学习算法的最优收敛率可以达到()21TO。不过，该算法是基于批处理模式。并且，由于应用了矩阵的奇异值分解SVD，每次迭代的昂贵计算代价使得该方法并不适用于大规模数据场景。本文结合使用加速技术和正则化对偶平均方法，首次提出一种新颖的多任务加速在线学习算法，算法计算高效且加速收敛。迭代更新权重学习矩阵的邻近解计算表达式，以及算法的收敛率分析，均有完整的数学推导过程。多任务加速在线算法可以很方便地应用于金融时间序列预测、在线推荐系统协同过滤等动态多变的大数据流场景中，实验结果表明它能显着提升大规模数据流处理的实时性和可伸缩性，是有效学习大数据流的一种很有前途的工具。1多任务在线学习框架1.1问题构建定义1.多任务学习(MTL, multitask learning).