.358 智能系统学报 第9卷 性时，在线多核学习问题可以两步求解，先使用基础 有标记数据样本：(x,y) 的训练集为每一个核函数训练一个学习器，之后使 输出：更新后的权重u 用这些学习器进行在线学习，每读入一个训练样本 1)y·=sign(w·F(x) 时，根据当前的加权组合学习器对当前训练样本的 2)ify'=y then 输出结果，使用一种策略更新该核函数的权值和所 3)p=0 对应的单个学习器，则最优的核函数为各个核函数 4)else 使用该最优权值的加权组合体。即式(1)可以转化 5)9=1 为以下问题： 6)end if 7)fori=1,2,…,mdo min max uJieHK,ac[0,C]Ti= ：fs+ 8)p=p(min(e,-yf(x)+0.5)) ∑a,(1-y∑uf(x)） (2) 9)u:=u:B”/更新u 10)f:=f+pyk(x,·) 11)end for 图1描述了上述求解过程的主要步骤。 12)return u 基本训练集 算法1在输人有标记数据样本时，同时更新核权 学习器训练 m个学习器 权重u 重和每个核所对应的学习器。当样本被当前学习器分 核函数集K 初始化 类正确时，p为0，此时不执行更新动作：若分类错误， 读入样本 是否有标记 Y更新权重 则减少该学习器的权重，见算法1的第8)和第9)行。 输出 核函数 第lO)行根据Representer定理对每个核所对应的最优 学习器进行调整。最大错误容忍水平e控制以多大的 数据依赖更新组合学习器 力度去惩罚被学习器错分的样本。 由于仅对训练数据集进行一次扫描，算法1并 多核在线学习 不能达到离线批处理学习器的性能。但可依据感知 图1多核在线学习算法的主要框架 器训练过程对算法1的收敛性分析如下。算法第 Fig.1 The main framework of online multiple kernel 10)行对各个f进行更新，且各个f相互独立，相当 learning 于m个独立的感知器训练过程，当输入样本线性可 对式(2)进行分析可知，由于各个f之间没有 分时，各个f可以收敛于当前训练集下的最优学习 关联，因此f的最优值可以单独求出，再用类似感知 器，进而确定其最优组合：当输入样本线性不可分 器的权值更新算法求解最优的组合权值u。由Re- 时，其收敛性依赖于各个学习器的核函数，一般情况 presenter定理可知，使式(2)最优的f方必定满足 下并不收敛于最优解，但实验部分的第4组实验说 f)=(,) 明经过一段时间后学习器的性能会趋于稳定，逼近 (3) i=1 一个可接受的较优解。 式(3)给出了一种在线学习f的方法，当读入一个 2.2基于数据依赖的核函数修改 训练样本时，先判断f能否给出正确的标签，然后采 数据依赖核[]是一种无监督的核函数学习方 用f=f+yk,(x,·)更新，其中p为指示函数，当 法，实质是对核函数在训练样本集上的值进行修改， 对x正确分类时其值为1，反之为0。Jin等在文献 使其所反映的在可见数据样本上的距离更加符合数 [9]中实现了上述思想。算法1描述了整个过程。 据样本点的空间分布，而不考虑样本标签。它可以 算法1在线多核学习 对任意现有核函数根据可见的数据样本进行修改， 输入 实质是对由核函数所诱导的希尔伯特空间的内积进 核函数集合：Kn={k1,k2,…,km} 行修改。首先给出数据依赖核的主要结论，然后 初始化学习器：F={fif,…fm} 再提出针对大数据和高速数据流的数据依赖核在线 更新因子：B∈(0,1) 核学习算法。 最大分类错误的容忍水平：e 给定一个核函数k和一个数据集D={x1,x2, 当前的权重向量：u ,xn},记k=(k(x:,x),…,k(,xn)）,M=性时，在线多核学习问题可以两步求解，先使用基础 的训练集为每一个核函数训练一个学习器，之后使 用这些学习器进行在线学习，每读入一个训练样本 时，根据当前的加权组合学习器对当前训练样本的 输出结果，使用一种策略更新该核函数的权值和所 对应的单个学习器，则最优的核函数为各个核函数 使用该最优权值的加权组合体。 即式（１）可以转化 为以下问题： ｍｉｎ ｕ，ｆ ｉ∈ＨＫ ｉ ｍａｘ α∈［０，Ｃ］ Ｔ∑ ｍ ｉ ＝ １ ｕｉ ‖ｆｉ‖２ ＨＫ ｉ ＋ ∑ Ｔ ｔ ＝ １ αｉ（１ － ｙｔ∑ ｍ ｉ ＝ １ ｕｉ ｆ ｉ（ｘｔ）） （２） 图 １ 描述了上述求解过程的主要步骤。 图 １ 多核在线学习算法的主要框架 Ｆｉｇ．１ Ｔｈｅ ｍａｉｎ ｆｒａｍｅｗｏｒｋ ｏｆ ｏｎｌｉｎｅ ｍｕｌｔｉｐｌｅ ｋｅｒｎｅｌ ｌｅａｒｎｉｎｇ 对式（２）进行分析可知，由于各个 ｆ ｉ 之间没有 关联，因此 ｆ ｉ 的最优值可以单独求出，再用类似感知 器的权值更新算法求解最优的组合权值 ｕ 。 由 Ｒｅ⁃ ｐｒｅｓｅｎｔｅｒ 定理可知，使式（２）最优的 ｆ ｉ 必定满足 ｆ ｉ（·） ＝ ∑ ｎ ｊ ＝ １ αｊ ｙｊ ｋｉ（ｘｊ，·） （３） 式（３）给出了一种在线学习 ｆ ｉ 的方法，当读入一个 训练样本时，先判断 ｆ ｉ 能否给出正确的标签，然后采 用 ｆ ｉ ＝ ｆ ｉ ＋ φｙｘ ｋｉ（ｘ，·） 更新，其中 φ 为指示函数，当 ｆ ｉ 对 ｘ 正确分类时其值为 １，反之为 ０。 Ｊｉｎ 等在文献 ［９］中实现了上述思想。 算法 １ 描述了整个过程。 算法 １ 在线多核学习 输入： 核函数集合： Ｋｍ ＝ ｛ｋ１ ，ｋ２ ，…，ｋｍ ｝ 初始化学习器： Ｆ ＝ ｛ｆ １ ，ｆ ２ ，…，ｆｍ ｝ 更新因子： β ∈ （０，１） 最大分类错误的容忍水平： ｅ 当前的权重向量： ｕ 有标记数据样本： （ｘ，ｙ） 输出：更新后的权重 ｕ １） ｙ ∗ ＝ ｓｉｇｎ（ｗ Ｔ·Ｆ（ｘ）） ２）ｉｆ ｙ ∗ ＝ ｙ ｔｈｅｎ ３） φ ＝ ０ ４）ｅｌｓｅ ５） φ ＝ １ ６）ｅｎｄ ｉｆ ７）ｆｏｒ ｉ ＝ １，２，…，ｍ ｄｏ ８） ｐ ＝ φ（ｍｉｎ（ｅ， － ｙｆ Ｔ ｉ （ｘ） ＋ ０．５）） ９） ｕｉ ＝ ｕｉβ ｐ ／ ／ 更新 ｕ １０） ｆｉ ＝ ｆｉ ＋ φｙｋｉ（ｘ，·） １１）ｅｎｄ ｆｏｒ １２）ｒｅｔｕｒｎ ｕ 算法 １ 在输入有标记数据样本时，同时更新核权 重和每个核所对应的学习器。 当样本被当前学习器分 类正确时， φ 为 ０，此时不执行更新动作；若分类错误， 则减少该学习器的权重，见算法 １ 的第 ８）和第 ９）行。 第 １０）行根据 Ｒｅｐｒｅｓｅｎｔｅｒ 定理对每个核所对应的最优 学习器进行调整。 最大错误容忍水平 ｅ 控制以多大的 力度去惩罚被学习器错分的样本。 由于仅对训练数据集进行一次扫描，算法 １ 并 不能达到离线批处理学习器的性能。 但可依据感知 器训练过程对算法 １ 的收敛性分析如下。 算法第 １０）行对各个 ｆ ｉ 进行更新，且各个 ｆ ｉ 相互独立，相当 于 ｍ 个独立的感知器训练过程，当输入样本线性可 分时，各个 ｆ ｉ 可以收敛于当前训练集下的最优学习 器，进而确定其最优组合；当输入样本线性不可分 时，其收敛性依赖于各个学习器的核函数，一般情况 下并不收敛于最优解，但实验部分的第 ４ 组实验说 明经过一段时间后学习器的性能会趋于稳定，逼近 一个可接受的较优解。 ２．２ 基于数据依赖的核函数修改 数据依赖核［１１］ 是一种无监督的核函数学习方 法，实质是对核函数在训练样本集上的值进行修改， 使其所反映的在可见数据样本上的距离更加符合数 据样本点的空间分布，而不考虑样本标签。 它可以 对任意现有核函数根据可见的数据样本进行修改， 实质是对由核函数所诱导的希尔伯特空间的内积进 行修改［１２］ 。 首先给出数据依赖核的主要结论，然后 再提出针对大数据和高速数据流的数据依赖核在线 核学习算法。 给定一个核函数 ｋ 和一个数据集 Ｄ ＝ ｛ｘ１ ，ｘ２ ， …， ｘｎ ｝ ， 记 ｋｘｉ ＝ （ｋ（ｘｉ，ｘ１ ），…，ｋ（ｘｉ，ｘｎ ）） ， Ｍ ＝ ·３５８· 智 能 系 统 学 报 第 ９ 卷