第3期 张钢，等：面向大数据流的半监督在线多核学习算法 ·357. 等)回顾了目前的主要多核学习算法，指出大多数算 面向大数据的多核学习算法 法所得到核函数组合对学习器的影响差别不大，但是 在学习算法的时间复杂度及核函数组合的稀疏性方面 首先形式化描述多核学习问题，然后再给出带 却有很大差异，这种差异性在处理大数据的多核学习 有数据依赖的多核学习问题，并给出在线学习版本 问题时必须考虑。他们的工作表明通过非线性和数据 的算法。核学习所解决的问题是直接从训练数据集 依赖的方式进行核函数的组合具有更好的性能，数据 (有标记或无标记)中学习参数化或半参数化的核 依赖的核函数修正方式适合于高速无标记的数据流， 函数，使其能充分反映数据所蕴含的分布规律。给 这是本文在线核学习方法的一个出发点。Orabona 定一系列的训练样本D,={(x,y:)Ii=1,2,…, 等[劉提出了一种多核学习的快速算法，能够通过参数 n},其中x:为属性集，y:∈{-1，+1}为分类标记 控制所生成核的稀疏程度，算法即使在待组合的核数 给定一个包含m个基本核函数的集合K={k(·, 量很大的情况下仍然能够快速收敛，且模型训练的时 ·):X×X→R,j=1,2,…,m,学习一组非负权值 间复杂度仅是训练样本的线性函数。该工作大大减轻 u=山1，山2，…，山，∑4=1，使核学习器在测试 了核学习的算法复杂度，并能控制核的稀疏和与数据 集上的分类错误最小化。由于权值非负，根据核函 拟合的程度，有很重要的理论和应用价值。但该工作 数的性质可知，核函数的凸组合仍为一个有效的核 并不完全适用于大数据，特别是高速数据流，其原因是 函数。该问题可以形式化描述为 它并非一种增量更新算法，而是一种批处理的优化方 min::fIa+C∑fx,)) (1) 法。此外，该方法是一种有监督的核学习方法，并不能 式中：l为Hinge Loss损失函数，定义为l(a,b)= 处理无标记的数据样本，而在大数据流中数据样本的 max(0,1-ab),Hx为核函数K所张成的希尔伯特 标记缺失十分常见，因此核学习器的无监督学习能力 空间，C控制模型复杂度与损失惩罚比重的参数。 非常重要。 求解该优化问题的时间复杂度比较高，这是由于其 针对数据流学习和模型的增量更新问题，研究 中包含2步优化，第1步选择一个“，确定一个核函 者们对在线学习进行了深入研究，其中值得关注的 研究工作是Jim等)提出的在线核学习框架，他们 数K=∑uk,从而确定了H:第2步在H,中寻找 i=1 系统地提出了在线多核学习问题理论及其算法。针 最简单的且在当前训练集中正确率最高（由C控 对核函数和核学习器的增量更新问题，他们提出了 制)的学习器f,这2个目标分别对应式(1)中的2 使用确定和随机2种方法进行更新，其中随机更新 项。若核函数确定，则寻找满足2个条件的f的问 需要结合一定的采样策略进行。他们的工作对于基 题可以直接求解，如SVM模型则属于此种情况。但 本核函数较多的情况下是有效的，但仅在有监督学 若核函数是通过参数“来对若干基核函数进行加权 习中进行研究，即遇到一个新的样本，若当前模型分 组合，要求最优的“和f,则问题变得很有挑战性， 类正确，则不进行更新动作，否则按照一定的策略更 特别是在大数据学习环境中，此类问题基本上不可 新模型。该方法并不直接适用于大数据流环境下的 能在可接受的时间内求得最优解。 多核学习问题，其主要问题是它不能适应数据流产 若通过限制基本核函数的个数或“中各分量的 生规律变化的情况，且当某些数据缺少标签时模型 取值范围，则会牺牲多核学习的优势，且没有从根本 无法有效处理。 上解决多核学习的问题。可以认为，在没有更好的 本文认为要解决此问题需要同时考虑数据标签 求解算法的情况下，在线学习对上述问题是一种较 和数据的空间分布，使用增量学习的方法同步更新 好的求解策略。 模型，这也是在当前很多大数据学习算法中所采用 2.1在线多核学习 的策略。如Qim等[1o]提出了一种适用于云计算增 为了进行在线学习，需要重新考虑式(1)。Jin 量梯度下降算法，解决大数据环境下带线性约束的 等的工作表明，当所学习的核函数为某个基本核 凸优化问题。Yang等)提出了决策树的增量学习 函数集合的线性组合时，式(1)的最优化问题可以 近似算法，可以在没有历史训练数据的情况下通过 转化为如下问题：先求出每个核函数k:在各自张成 在线学习的方式直接更新决策树模型。但这些工作 的希尔伯特空间H,上最优的f,然后寻找一组权 均是直接针对学习器进行增量更新，其方法并不直 值“，使这些f的组合最优，在寻找最优的过程中同 接适用于本文的核函数学习问题。 步更新权值和∫。换句话说，若核函数的组合为线等［７］回顾了目前的主要多核学习算法，指出大多数算 法所得到核函数组合对学习器的影响差别不大，但是 在学习算法的时间复杂度及核函数组合的稀疏性方面 却有很大差异，这种差异性在处理大数据的多核学习 问题时必须考虑。 他们的工作表明通过非线性和数据 依赖的方式进行核函数的组合具有更好的性能，数据 依赖的核函数修正方式适合于高速无标记的数据流， 这是本文在线核学习方法的一个出发点。 Ｏｒａｂｏｎａ 等［８］提出了一种多核学习的快速算法，能够通过参数 控制所生成核的稀疏程度，算法即使在待组合的核数 量很大的情况下仍然能够快速收敛，且模型训练的时 间复杂度仅是训练样本的线性函数。 该工作大大减轻 了核学习的算法复杂度，并能控制核的稀疏和与数据 拟合的程度，有很重要的理论和应用价值。 但该工作 并不完全适用于大数据，特别是高速数据流，其原因是 它并非一种增量更新算法，而是一种批处理的优化方 法。 此外，该方法是一种有监督的核学习方法，并不能 处理无标记的数据样本，而在大数据流中数据样本的 标记缺失十分常见，因此核学习器的无监督学习能力 非常重要。 针对数据流学习和模型的增量更新问题，研究 者们对在线学习进行了深入研究，其中值得关注的 研究工作是 Ｊｉｎ 等［９］ 提出的在线核学习框架，他们 系统地提出了在线多核学习问题理论及其算法。 针 对核函数和核学习器的增量更新问题，他们提出了 使用确定和随机 ２ 种方法进行更新，其中随机更新 需要结合一定的采样策略进行。 他们的工作对于基 本核函数较多的情况下是有效的，但仅在有监督学 习中进行研究，即遇到一个新的样本，若当前模型分 类正确，则不进行更新动作，否则按照一定的策略更 新模型。 该方法并不直接适用于大数据流环境下的 多核学习问题，其主要问题是它不能适应数据流产 生规律变化的情况，且当某些数据缺少标签时模型 无法有效处理。 本文认为要解决此问题需要同时考虑数据标签 和数据的空间分布，使用增量学习的方法同步更新 模型，这也是在当前很多大数据学习算法中所采用 的策略。 如 Ｑｉｎ 等［１０］ 提出了一种适用于云计算增 量梯度下降算法，解决大数据环境下带线性约束的 凸优化问题。 Ｙａｎｇ 等［２］ 提出了决策树的增量学习 近似算法，可以在没有历史训练数据的情况下通过 在线学习的方式直接更新决策树模型。 但这些工作 均是直接针对学习器进行增量更新，其方法并不直 接适用于本文的核函数学习问题。 ２ 面向大数据的多核学习算法 首先形式化描述多核学习问题，然后再给出带 有数据依赖的多核学习问题，并给出在线学习版本 的算法。 核学习所解决的问题是直接从训练数据集 （有标记或无标记）中学习参数化或半参数化的核 函数，使其能充分反映数据所蕴含的分布规律。 给 定一系列的训练样本 ＤＬ ＝ ｛（ｘｉ，ｙｉ） ｜ ｉ ＝ １，２，…， ｎ｝， 其中 ｘｉ 为属性集， ｙｉ ∈｛ － １， ＋ １｝ 为分类标记， 给定一个包含 ｍ 个基本核函数的集合 Ｋｍ ＝ ｛ｋｊ（·， ·）：Ｘ × Ｘ → Ｒ，ｊ ＝ １，２，…，ｍ｝ ，学习一组非负权值 ｕ ＝｛ｕ１ ，ｕ２ ，…，ｕｍ ，∑ｉ ｕｉ ＝ １｝ ，使核学习器在测试 集上的分类错误最小化。 由于权值非负，根据核函 数的性质可知，核函数的凸组合仍为一个有效的核 函数。 该问题可以形式化描述为 ｍｉｎｆ∈ＨＫ ‖ｆ‖２ ＨＫ ＋ Ｃ∑ ｎ ｉ ＝ １ ｌ（ｆ（ｘｉ），ｙｉ） （１） 式中： ｌ 为 Ｈｉｎｇｅ Ｌｏｓｓ 损失函数，定义为 ｌ（ａ，ｂ） ＝ ｍａｘ（０，１ － ａｂ） ， ＨＫ 为核函数 Ｋ 所张成的希尔伯特 空间， Ｃ 控制模型复杂度与损失惩罚比重的参数。 求解该优化问题的时间复杂度比较高，这是由于其 中包含 ２ 步优化，第 １ 步选择一个 ｕ ，确定一个核函 数 Ｋ ＝∑ ｍ ｉ ＝ １ ｕｉ ｋｉ ，从而确定了 ＨＫ ；第 ２ 步在 ＨＫ 中寻找 最简单的且在当前训练集中正确率最高（由 Ｃ 控 制）的学习器 ｆ ，这 ２ 个目标分别对应式（１）中的 ２ 项。 若核函数确定，则寻找满足 ２ 个条件的 ｆ 的问 题可以直接求解，如 ＳＶＭ 模型则属于此种情况。 但 若核函数是通过参数 ｕ 来对若干基核函数进行加权 组合，要求最优的 ｕ 和 ｆ ，则问题变得很有挑战性， 特别是在大数据学习环境中，此类问题基本上不可 能在可接受的时间内求得最优解。 若通过限制基本核函数的个数或 ｕ 中各分量的 取值范围，则会牺牲多核学习的优势，且没有从根本 上解决多核学习的问题。 可以认为，在没有更好的 求解算法的情况下，在线学习对上述问题是一种较 好的求解策略。 ２．１ 在线多核学习 为了进行在线学习，需要重新考虑式（１）。 Ｊｉｎ 等［９］的工作表明，当所学习的核函数为某个基本核 函数集合的线性组合时，式（１）的最优化问题可以 转化为如下问题：先求出每个核函数 ｋｉ 在各自张成 的希尔伯特空间 Ｈｋｉ 上最优的 ｆ ｉ ，然后寻找一组权 值 ｕ ，使这些 ｆ ｉ 的组合最优，在寻找最优的过程中同 步更新权值和 ｆ ｉ 。 换句话说，若核函数的组合为线 第 ３ 期 张钢，等：面向大数据流的半监督在线多核学习算法 ·３５７·