0 引言

近年来, 支持向量机(SVM)^[1-3]在机器学习领域尤其是非监督式学习中逐渐发展成为一种具有高效计算性能的方法.由于它自身一些独特的数学特性, 在很多应用领域中^[4-6], 其性能表现更加优于其他已有的机器学习技术.第一, 在训练模型中, 并不像传统的监督式学习算法那样仅仅最小化经验风险, 还采用了结构风险最小化(SRM)原则, 使得算法产生的二元分类器具有“最大间隔”的特性, 因此提升了模型的泛化能力.第二, SVM模型是通过求解一个二次凸优化问题产生最优分类超平面的, 因此保证了模型求出的最优解一定是全局最优解.第三, 由于模型公式的数学特性, 使得核技巧^[7]可以很容易地被合并到SVM模型中, 从而实现高维空间中任意两个向量內积的隐式计算.

为了加速SVM模型的计算速度, Khewehandani等^[8]提出了孪生支持向量机(TWSVM), 该模型被视为稀疏核学习的一个里程碑. TWSVM旨在求解两个最优的非平行超平面, 每一个超平面离本类样本集最近并且尽可能地离他类样本集远.尽管TWSVM的公式构造与SVM的公式构造在思想上很相似, 但它们在基础的公式构造上还是有很大的不同.在TWSVM模型中, 需要求解两个规模较小的QPP而不是SVM中单一的规模较大的QPP, 并且所有样本点相对于分类器的分布遵循这样的规则(以二元分类为例):来自某一类别的样本集决定着另一个类别所对应的QPP中的约束条件, 反之亦然.因此, TWSVM比传统的SVM模型具有更快的训练速度.

由于采用了分解思想, 将一个较大规模的优化问题分解成两个独立的规模较小的优化问题, TWSVM模型的计算速度得到了提升.因此, 近年来, TWSVM备受研究者的关注, 并在此基础上提出很多TWSVM的变体模型, 例如双子边界支持向量机(TBSVM)^[9-10]、v-孪生支持向量机(v-TWSVM)^[11]、基于球体的孪生支持向量机(sphere-based TWSVM)^[12-14]、基于结构化信息的孪生支持向量机(structure information based TWSVM)^[15-16]、粗糙的基于间隔的v-TWSVM(rough margin-based v-TWSVM)^[17-18]以及其他相关变体模型^[19-20]. Shao等^[9]提出了双子边界支持向量机(TBSVM), 通过在模型的目标函数中加入一个正则项, 实现了基于TWSVM模型的结构风险最小化(SRM)原则. Peng等^[11]提出了v-TWSVM, 引入了一对先验参数(v)来分别控制边界错误所占比例的上界和支持向量所占比例的下界.另外, 在TWSVM中的单位距离被松弛化为一个可以在原始问题中被优化的变量ρ.在粗糙的基于间隔的v-TWSVM(rough margin-based v-TWSVM)模型^[17]中, 对于不同的违反边界的样本点, 根据它们距离分类器的相对位置赋予它们不同的惩罚值, 因此在一定程度上提高了模型的分类精度. Wang等^[18]在粗糙的基于间隔的v-TWSVM的基础上引入结构风险最小化原则来最大化分类间隔, 不仅提高了测试数据集的分类精度, 而且避免了大矩阵的求逆运算, 降低了模型的计算复杂度.

这些基于TWSVM的变体模型, 包括TWSVM本身, 其模型公式构造的结果均是求解高维空间里的二次规划问题的对偶形式.然而, 当需要处理大规模数据集时, 求解这些二次规划问题将面临巨大的计算复杂度和时间开支.为了使得TWSVM及其变体模型能够更加适应于大规模数据集的分类学习, 本文提出定点孪生支持向量机(fixed-point TWSVM, FP-TWSVM)来加速模型的训练速度, 从而降低时间消耗.此外, 该算法的思想还可以用于TWSVM的变体模型中. FP-TWSVM的主要特性如下:

1) FP-TWSVM的公式构造思想继承了TWSVM, 将传统SVM模型中单一的规模较大的QPP分解成两个独立的规模较小的QPP, 从而产生两个最邻近的分割超平面, 每一个超平面都离本类样本集最近, 离他类样本集尽可能地远.

2) 与TWSVM模型不同的是, FP-TWSVM并不是直接求解高维空间内的标准QPP, 而是设计了一种定点算法, 将单个QPP转换成一系列有限多个一维空间里的单峰函数优化问题, 因此一些高效的线性搜索方法, 例如斐波那契算法和黄金分割法, 都可以用来求解一维单峰函数优化问题, 避免了大规模二次型矩阵的存储问题, 极大地提高了模型的训练速度和存储效率.

3) 通过引入核生成曲面, 核技巧能够与FP-TWSVM结合使用, 从而实现FP-TWSVM算法在非线性情形中的应用.当使用线性核函数时, FP-TWSVM的非线性形式退化成了线性形式.

1 孪生支持向量机(TWSVM)

这一部分简要回顾TWSVM的基本数学构造.考虑一个在d维空间内的二元分类问题, 有m个正类别样本点和n个负类别样本点.所有的正类别样本点存放在数据矩阵A∈ R^{m× d}中, 所有的负类别样本点存放在数据矩阵B∈ R^{n× d}中, d是特征空间的维度. A_i(i=1, 2, ..., m)表示矩阵A的第i行, B_i(i=1, 2, ..., n)表示矩阵B的第i行, y∈{-1, +1}表示样本的标签值.

1.1 线性孪生支持向量机(linear TWSVM)

TWSVM^[8]是一种非常优秀的分类算法, 可以将传统SVM模型中单一的规模较大的QPP分解成两个规模较小的独立的QPP, 由此降低了计算复杂度和时间消耗.两个非平行分割超平面如下:

(1)

其中: w₁和w₂是权值向量, b₁和b₂是超平面的截距.

TWSVM公式构造的思想与SVM很相似, 然而它们的基本构造还是有很大区别的.在TWSVM模型中, 旨在找到两个最优分割超平面(1), 要求在这两个分割超平面的周围尽可能多地聚集着本类别的样本点.另外, 在每一个QPP中的约束条件集合中, 并不同时包含所有的数据点, 只有那些他类的样本点的数量才决定着本类别对应求解的QPP的约束条件集合的大小.通过求解以下两个QPP, 可以得到TWSVM的分类器:

(2)

(3)

其中: c₁, c₂ >0是常数, 分别用来权衡每个分类器到本类样本集的距离和对应的松弛变量的惩罚值; ξ₁和ξ₂是由松弛变量组成的向量; e₁和e₂是实数空间里具有合适维度的单位向量.以上优化问题(2)和(3)中的目标函数的第1项分别是各个非平行超平面到本类样本点的距离之和, 因此最小化第1项就相当于使得每个超平面离本类的样本集最接近.问题(2)和问题(3)中的约束条件要求每个分割超平面到他类样本点的距离至少为单位1. ξ₁和ξ₂是针对每个超平面分别用来记录那些到本类分类器距离小于1的他类样本点的距离违反量.目标函数的第2项是惩罚函数, 分别用来记录每个类别的分类器对应的他类样本违反量的总和, 因此等同于最小化边界错误.

通过引入两组拉格朗日乘子, 上述的原始优化问题可以被构造成对偶形式^[8]的优化问题.原始问题(2)对应的拉格朗日函数如下:

(4)

其中α =(α₁, α₂, ..., α_m)^T和β =(β₁, β₂, ..., β_m)^T是由拉格朗日乘子组成的向量.将KKT条件代入拉格朗日函数(4)中, 所有的原始变量均被消去, 原始问题(2)会被转换成一个关于对偶变量的对偶形式的优化问题, 如下所示:

(5)

其中: H=[A, e₁], G=[B, e₂]. u=[w₁, b₁]^T是一个扩展的权值向量, 因此u可以用对偶变量α_i (i=1, 2, ..., n)和样本数据点表示如下:

(6)

采用与原始问题(2)相同的推导思路, 可以得到原始问题(3)对应的对偶问题

(7)

其中: P=[A, e₁], Q=[B, e₂].同样地, v=[w₂, b₂]^T是一个扩展的权值向量, 可以用对偶变量γ_i (i=1, 2, ..., m)和样本数据点表示如下:

(8)

通过求解对偶的QPP (5)和(7)获得了最邻近分割超平面(1)后, 可以根据如下判别式赋予任意新的数据点x ∈ Rⁿ的类别标签:

1.2 非线性孪生支持向量机(nonlinear TWSVM)

通过引入如下两个核生成曲面, 可以将1.1节的线性TWSVM^[8]拓展到非线性情形:

(9)

其中: C^T =[A, B]^T, K是一个选择适当的核函数.式(1)可以被看成是式(9)的一种特殊情况, 因为在式(1)中相当于使用了线性核函数.可以用与线性情况相同的推导方法得出非线性情形中正类别对应的原始问题, 如下所示:

(10)

问题(10)对应的对偶问题如下:

(11)

其中: S=[K(A, C^T), e₁], R=[K(B, C^T), e₂].记z=[u₁, b₁]^T, 则z可以通过下式求解:

(12)

同理, 非线性情形下的负类别对应的原始问题如下:

(13)

问题(13)的对偶问题如下:

(14)

其中: L=[K(A, C^T), e], N=[K(B, C^T), e₂].记z₂ =[u₂, b₂]^T, 同样, z₂可以由下式求出:

(15)

求解完对偶问题(11)和(14)得到两个核生成曲面(9)后, 可以使用与线性情形同样的判别规则来预测新的数据点x ∈ Rⁿ的标签值.

通常SVM模型的复杂度不超过N³, 其中N是正、负类别训练样本的总数.然而, 由于TWSVM将SVM中单一的规模较大的优化问题分解成了两个规模较小的独立的优化问题(2)和(3), 并且每个优化问题的规模约为N /2, 因此SVM模型和TWSVM模型的训练时间之比为[N³ /(2×(N/2)³)]=4.由此可得, TWSVM的训练速度大约是传统SVM模型训练速度的4倍^[8].

在实际应用中, 若某个应用在正类别或者负类别需要大规模的训练集, 则可以使用矩形核技术^[21-22]来降低问题(10)和(13)的数据维度.此外, 在线性情形中, 需要引入一个正则项εI来应对需要求逆的矩阵S^TS和N^TN可能存在的病态性.这样, 可以进一步使用Sherman-Morrison-Woodbury公式求解矩阵的逆, 降低需要求逆的矩阵的阶数.

2 定点孪生支持向量机(FP-TWSVM)

无论是TWSVM还是它的变体模型, 最后均要求解对偶的标准二次规划问题(QPP)得到最优分割超平面.在处理规模适中的数据集时, 这些算法的训练时间可以控制在一个合理的范围.但是, 当需要处理超大规模数据集时, 这些模型的计算复杂度就会相当高, 其时间开支已经超出了实际应用程序的可接受范围.为解决这一问题, 该部分将提出定点孪生支持向量机FP-TWSVM算法.与引言中的算法不同的是, FP-TWSVM算法在求解优化问题的过程中引入了定点思想, 将TWSVM算法中的求解单个标准对偶QPP问题转换成求解一系列连续的一维单峰函数优化问题, 每一个优化问题都可以采用高效的线性搜索方法求得最佳解.并且, 每个被分解的标准QPP问题中的目标函数一定随着每个一维单峰函数优化问题的最优解的求出呈单调递减趋势.与TWSVM相同的是, FP-TWSVM也可以通过构造核生成曲面由线性分类拓展到非线性分类.在2.1节中先将定点思想运用在线性情形中, 然后再扩展到非线性情况.该定点思想在TWSVM的其他变体模型中同样适用.

为了方便本文中的后续数学推导, 先给出一些与TWSVM模型中不一样的数学符号.考虑到计算的简便性, 去掉了偏移量b, 并将它隐式地加在权值向量w的最后一个维度.因此, 每个数据点要用n+1维的向量来表示, 且每个样本向量的最后一个维度固定设为1.为了更好地体现本文新提出的算法的定点思想, 数学推导中将使用求和符号将所有的数据点以及原始变量和对偶变量显式地表示出来, 而不是像TWSVM中那样将所有的正类别和负类别样本点分别集中放在两个数据矩阵中, 将所有的原始变量和对偶变量表示成向量形式.

考虑一个二元分类问题.假设正负类别的样本点分别有m个和n个; {x_i⁽¹⁾}_i=1^m表示正类别样本数据集, {x_j⁽²⁾}_j=1ⁿ表示负类别样本数据集, i和j分别表示正类别和负类别的样本索引; w₁和w₂分别表示正类别和负类别的维度扩展的权值向量.

2.1 线性孪生支持向量机(linear FP-TWSVM) 2.2.1 构建FP-TWSVM的非平行分类器

在线性FP-TWSVM中, 目标是要求解如下两个分割超平面:

(16)

仿照TWSVM模型, 可以通过求解两个规模较小的QPP问题来得到上述两个最优非平行二元分类器.在此, 只展示正类别对应的数学推导, 负类别的分类器的求解过程与正类别几乎一致.正类别对应的最优分割超平面可以通过求解以下QPP得到:

(17)

其中: c₁ >0是平衡常数, ξ_i是松弛变量.对应的拉格朗日函数如下:

(18)

其中α_j和β_j是拉格朗日乘子.将函数(18)关于w₁和ξ_j的偏导数分别设为零, 得到以下Karush-Kuhn-Tucker (KKT)^[23]条件:

(19)

(20)

由互补松弛定理得到:

(21)

(22)

由式(19)可得

(23)

其中A是正类别数据矩阵, 它的第i行表示第i个正类别的样本点.将式(20)和(23)代入(18)中, 得到如下简化的拉格朗日函数:

(24)

其中H被记为H=(A^TA)^-1.因此, 可以得到正类别的对偶问题如下:

(25)

求解问题(25)之后, 可以得到正类别对应的最优权值向量.

2.2.2 分解对偶优化问题

对偶问题(5)包含了n个变量, 可以用标准的求解二次规划问题的方法来得到问题(25)的最佳解.然而, 如果负类别包含的样本点规模很大, 则在正类别的原始问题中会包含大量的约束条件, 就需要大量的拉格朗日乘子来代表这些约束条件, 从而构成对偶问题.将对偶的规划问题(25)写成标准的QP形式需要一个n× n的数据矩阵, 当n很大时, 求解这样的QP问题的计算复杂度就会非常大.同时, 由于有大规模的二次型矩阵的存在, 会消耗大量的存储空间.因此, 需要寻找新的求得拉格朗日乘子最优解的方法, 而不是直接用标准的QP方法来求解问题(25).接下来, 将提出一种“定点”思想来解决这一问题.

这种算法思想的核心在于将问题(25)中的约束条件集合划分成n个互不相交的子集{α_j|α_j≥ 0, α_j ≤ c₁}_j=1ⁿ.整个算法按照多个轮次运行, 每个轮次需要选择一个样本索引p, 在约束条件α_j ≥ 0和α_j ≤ c₁下, 通过更新对偶变量α_p来提高目标函数值的大小.这样的若干轮次构成了一系列连续的小规模优化问题.

接下来仅仅关注样本索引p, 重新构造问题(25)中的目标函数, 将目标函数用对偶变量α_p表示出来.将那些关于α_p的项从整个目标函数Q中独立出来, 如下所示:

(26)

另外, 定义如下变量:

(27)

(28)

(29)

将式(27) ~ (29)中定义的变量代入目标函数中, 得到

(30)

为简化起见, 消去那些不影响求解过程的项.因此, 经过上述的分解步骤以后, 每一个轮次需要求解的优化问题仅包含一个变量和两个条件, 如下所示:

(31)

定义

(32)

完全平方之后, 问题(31)可以表示成如下更简洁的形式:

(33)

可以采用高效的线性搜索方法, 如黄金分割法或者斐波那契算法, 求得该一维单峰函数优化问题的最佳解.由式(23)可知, 正类别对应的权值向量可以表示为

(34)

当求解完一系列与问题(33)类似的一维单峰函数优化问题得到一组最优解v_j^* (j=1, 2, ..., m)之后, 可以求出对应的拉格朗日乘子α_j^* (j=1, 2, ..., n)的最优解, 最优权值向量为

(35)

正类别对应的QPP问题求解过程的算法框架如下所示(用α_j^* =0, 对算法进行初始化, j=1, 2, ..., n).

算法1

Input: {(x₁⁽¹⁾, y₁⁽¹⁾), (x₂⁽¹⁾, y₂⁽¹⁾), ..., (x_m⁽¹⁾, y_m⁽¹⁾), (x₁⁽²⁾, y₁⁽²⁾), (x₂⁽²⁾, y₂⁽²⁾), ..., (x_n⁽²⁾, y_n⁽²⁾)};

Initialize: α₁=0, ..., α_m=0.

Repeat:

1) Choose a pattern p (vis KKT conditions).

2) Calculate the constants for the reduced optimization problem:

3) Find optimal solution for the following rduced problem using a simple line search method in one dimension:

4) Calculate α_p via , until a certain stopping criterion is satisfied.

Output: .

为了完成该算法框架的细节问题, 需要讨论以下几个问题:

1) 需要设计一种机制来选择每一轮次所需关注的样本点, 得到如式(33)所示的优化问题.有两种常用的方法对每一轮的样本点进行选择, 一种是随机抽样, 另一种是按照某种序列对训练集进行扫描逐一选择样本点.本文则提出一种新的样本选择策略, 这种策略与常用的两种方法相比具有更好的表现.

2) 如何设置算法1框架中的主循环的终止条件.其中一种简单的方法是使得算法运行完固定的轮次后即可停止, 这就意味着只需要求解一系列有限多个类似于式(33)的小规模优化问题.而在本文后续部分, 将要介绍的一种更好的设置终止条件的策略是提前设置一个精度条件, 当该精度条件满足时, 才会终止算法1中的主循环.本文将在2.1.3节详细说明这两种策略.

求解负类别对应的最优权值向量的过程与上述过程基本类似.负类别的最优权值向量如下:

求解得到正负类别的权值向量以后, 可以根据判别式来确定新的样本点x_i ∈ R^d的标签值k.其中: w_k ∈ R^d+1是维度扩展的权值向量, 偏移量b被隐式地添加在最后一个维度; w_k^- ∈ R^d是不含偏移量的权值向量.

2.1.3 样本选择策略

在该部分, 将以正类别求解分割超平面的过程为例, 详细介绍如何进行样本选择.因此在TWSVM模型中, 针对正类别, 需要求解的对偶QPP问题如下:

与问题(25)是一致的.

首先, 需要使用Karush-Kuhn-Kucker定理^[23]寻找使得α_j成为问题(25)的最佳解的必要条件.因而, 再次引入一组新的拉格朗日乘子, 并构造问题(25)的对偶问题.问题(25)的拉格朗日函数如下所示:

(36)

其中u_j和v_j分别是约束条件α_j ≥ 0和α_j ≤ c₁对应的拉格朗日乘子.因此, 问题(25)的对偶问题如下所示:

(37)

设问题(37)中的目标函数关于α_j的偏导数为零可得到如下等式:

(38)

定义

(39)

这样, 式(38)可以写成

(40)

根据互补松弛定理, 有

(41)

和

(42)

第1种情况是α_j -c₁ =0, 这种情况下, 等式(42)自然成立.结合问题(37)中的条件v_j ≥ 0和等式(40), 可得

(43)

第2种情况是α_j -c₁ < 0, 为了使等式(42)成立, 必须有F_j =u_j.可以用两个不等式条件F_j ≥ u_j和F_j ≤ u_j来代替单一的等式约束F_j=u_j, 由此可得

(44)

对于样本索引j, 将式(43)和(44)合成为一个不等式约束, 有

(45)

最后, 去掉u_j可得

(46)

定义

(47)

由于, 在可行域中使得α_j成为问题(37)的最优解的充分必要条件是ψ_j =0.因此, 变量ψ_j可以帮助选择每一轮所要关注的样本点, 从而构建出特定的小规模优化问题.在数值实验中, 需要保持存储空间的消耗尽可能小, 因此每个循坏只选取一个样本点, 并针对该样本点对应的拉格朗日乘子作更新, 这种思想称为定点思想.首先选择最大的ψ_p对应的样本点索引p, 然后通过求解一维单峰函数优化问题(33)得到最优解α_p或v_p.由于α_p的改变, 需要对所有的样本点的F_j和ψ_j值作更新.在数值实验中, 只需要寻找满足ψ_j ≤ ε条件的α_j作更新即可, ε是预先设置好的精度参数.因此, 只要还存在至少一个样本点(x_j⁽²⁾, y_j⁽²⁾), 其对应的ψ_j值比预先设定的阈值ε大, 则继续执行算法1的主循环.经过有限多轮后, 上述优化机制可以保证收敛到最优解, 这是因为每一轮中, 被分解的含有n个变量的目标函数均会单调递减.由于空间限制, 读者可以参考文献^[24]中提供的相关收敛性证明.

2.2 非线性孪生支持向量机(nonlinear FP-TWSVM)

通过构造以下两个核生成曲面, 可以很容易地将“定点”思想从线性TWSVM拓展到非线性情形:

(48)

然后可以依照与线性情况类似的推导过程得到非线性分类问题的最优非平行分类器.由于负类别分类器的求解过程与正类别相同, 不失一般性, 以正类别的求解过程为例.对应的原始问题如下:

(49)

其中c₃ >0是平衡常数. K是选择适当的核函数, 当使用线性核函数时, 核生成曲面(48)就会退化成线性分类器.构造拉格朗日函数如下:

(50)

与2.1.1节的推导类似, 由KKT条件可得

(51)

将KKT条件代入函数(50)中得到简化的拉格朗日函数(为防止推导过程冗余, 省略了KKT条件的推导过程)

(52)

其中Q=[k(A^T, C^T)k(A, C^T)]^-1.

综上, 原始问题(49)可以被转化成如下的对偶问题:

(53)

其中θ_j (j=1, 2, ..., n)是拉格朗日乘子.

非线性情况下, 包含分类器的构造与分解策略的FP-TWSVM算法框架与算法1类似, 只需要将x_j⁽²⁾替换成k(x_j^2T, C^T).因此, 为防止冗余, 省略了详细的步骤.

非线性情况的分解策略如下.首先, 需要为问题(53)构造拉格朗日函数

(54)

其中δ_j和u_j (j=1, 2, ..., n)是为约束条件θ_j≥ 0和θ_j ≤ c₃ (j=1, 2, ..., n)新引入的拉格朗日乘子.因此, 问题(53)的对偶问题如下:

(55)

设目标函数(54)关于θ_j的偏导数为零, 进而寻找使得θ_j成为问题(53)的最优解的充分必要条件.

(56)

定义

(57)

与2.1.3节的推导类似, 定义变量ω_j = E_j - E_j, 可以用来选择每一轮次的样本点, 并对其拉格朗日乘子作更新.求解完一系列小规模的优化问题以后, 可以得到一组最优的拉格朗日乘子θ_j (j=1, 2, ..., n), 进而得出最优的权值向量u₁ (式(51))和正类别对应的最邻近分割超平面.负类别的最优分割超平面的推导过程与上述过程基本类似.最后根据判别式来预测新的样本点的标签值k.其中: u_k是扩展的权值向量, 偏移量b被隐式地添加到该向量的最后一个维度; u_k^-是不含偏移量b的权值向量.

3 实现细节

至此, 已经讨论了定点孪生支持向量机(FP-TWSVM)模型设计的基本原则和算法细节.然而, 为了使算法更加适用于大规模数据集, 更加具有实用性, 本文还做了一些实现技术上的改进.尽管这些改进并不会改变算法的整体框架和设计原则, 但是它们可以在实际操作中对算法的表现性能有很大的提升.因此, 该部分将着重介绍这些实现细节上的改进策略.

3.1 通过KKT条件进行样本选择

不失一般性, 同样以正类别为例.对于每一个样本索引j, 计算出F_j的值, 从而得到ψ_j.如2.1.3节所述, 在每一个轮次中, 选择ψ_p最大的样本点p构造一个一维优化问题, 然后反复这样的过程, 直到所有的ψ_j值均小于预先设定的精度参数ε.事实上, ε的选择对于算法最终输出结果的影响并不是很大, 在一个较大范围内选择ε都可以使算法取得良好的分类表现. ε越大, 算法1的主循环终止越早.为了确保算法有良好的泛化能力, 将ε设成一个较大的值. 图 1分别绘制了运行时间(running time)和测试错误(testing error)关于ε的函数图象.这两个函数图象说明, ε的中间值0.1具有很好的泛化能力.因此, 只要选取的ε值不是非常大, 算法的表现性能对于实际的ε取值是不太敏感的.

3.2 构建主动集(active set)

基于上述的实现, 需要依次扫描负类别所有的训练样本, 并计算出它们的ψ_j.然而, 如果只有一小部分样本对于最优分割超平面的求解有较大影响, 也就是说, 有很多样本对应的拉格朗日乘子α_j为零, 将会花费很多时间在那些对最终解没有贡献的样本点上.考虑到这个问题, 将负类别样本点划分成两个互不相交的子集.第1个子集记为M, 称为主动集, 由那些对最优解有贡献的样本点组成, 因此M={x_j|α_j ≠ 0}.第2个集合是主动集M的补集, 也就是M^c={x_j|α_j =0}.在执行主循环时, 首先根据3.1节所述的利用KKT条件从主动集中选择一个样本点, 对它的拉格朗日乘子作更新.只有当主动集中这样的样本点不存在时, 意味着∀j∈M, ψ_j < ε, 才会从补集中选择ψ_p最大的样本点, 将其移出补集, 加到主动集中, 用该样本点构造一个一维单峰函数优化问题, 对α_p作一次更新.整个过程将大量的时间用于更新主动集中的样本点对应的拉格朗日乘子, 并且只有当主动集中没有符合条件的样本点作更新时才会去访问补集, 并将补集中ψ_p最大的样本点加入到主动集中.这种构建主动集的策略可以大大降低运行时间.

3.3 调节精度参数

尽管主动集的引入可以显著降低时间消耗, 但是这种机制仍然要迫使算法不断更新主动集中的α_j值, 只要主动集中还存在至少一个样本点索引j, 满足ψ_j >ε.这样的做法可能会导致目标函数Q减小的速率很慢. 图 2绘制了当精度阈值为固定值时, 拉格朗日函数Q关于轮次总数的函数图象, 如实线所示, 该函数图象呈阶梯状.仔细观察目标函数Q明显降低时对应的轮次可以发现, 在这些轮次中, 新的样本点刚好被加进了主动集中.当一个新的样本点被加入到主动集中后, 又需要很多的轮次来更新主动集中的样本点对应的α_j, 这就使得目标函数Q在后续的一段时间内变化量不大.为了加速这一过程, 逐渐改变精度参数ε的值而不是使ε在整个算法过程中保持不变.在算法前阶段, 将ε设成一个较大的值, 根据3.2节所述, 可以频繁地向主动集中添加新的样本点.这样一来, 在前阶段, 算法就可以平衡对所有训练样本的关注度, 而不会花费很多时间在初始化步骤所产生的主动集样本上.随着轮次的增加, 逐渐降低阈值ε, 将算法的注意力从总体样本中转移到支持向量上, 也就是主动集样本上.将这一缓慢减小精度参数的过程称为cooling, 并选取对数函数ε(t)=ε₀/log₁₀(t+10)作为算法的cooling规则.该函数在t较小时保持一个相对较大的值, 继而缓慢减小.这种cooling策略使得目标函数Q的值下降更平稳光滑, 下降速率更快, 如图 2虚线所示.该策略将Q的下降速率提高了一个数量级, 使得整个优化算法可以更快地收敛.

4 数值实验

为了验证本文算法的分类效果, 将FP-TWSVM与TWSVM^[8]、TBSVM^[9]和v-TWSVM^[11]作比较来验证新算法在训练速度(训练时间)和存储效率方面的优越性.本文将从分类精度和计算效率(反应在平均训练时间上)的角度对各个算法的性能进行衡量.实验使用的是具有3.40 GHz CPU和16 GB RAM的PC机, 在Microsoft Windows环境中运行, 使用的是Matlab 2012a版本.

4.1 参数设置

在进行实验之前, 首先进行最优参数选择.在后续实验中, 采用网格搜索法^[25]对参数c_i(i=1, 2, 3, 4)进行调节.其中: c₁和c₂分别是正类别在线性和非线性情况下的平衡常数, c₃和c₄分别是负类别在线性和非线性情况下的平衡常数.对于非线性情况, 采用的是高斯核函数exp(-σ||x-y||²), 其中σ是核宽度参数, 同样需要与c_i (i=1, 2, 3, 4)一起进行参数调节.为了避免偏倚和过度拟合情况的发生, 采用10折交叉验证技术^[26-28]来选择c_i(i=1, 2, 3, 3)和σ的最优参数值.对于每一个数据集, 随机抽取10 %的样本点构成验证集.在实验中, 从{10ⁱ, i=-5  to   -1}范围中选择c₁和c₃的最优参数值, 从{0.1  -1}范围中调节参数c₂和c₄的数值.对于每一个数据集, 在10个验证集上计算平均分类精度, 分类精度accuracy有如下定义:

(58)

其中TP、TN、FP和FN分别是分类正确的正类别点(true positive)、分类正确的负类别点(true negative)、分类错误的负类别点(false positive)和分类错误的正类别点(false negative)的样本总数.

4.2 标准数据集

为了验证新算法的有效性, 在一系列数据集上, 包括UCI和NDC这些经常用来作机器学习算法测试的数据集上进行数值实验.其中一些NDC数据集规模较大, 有利于凸显出新算法在训练速度(由训练时间反应)方面相对于其他算法的优越性.此外, 样本点在训练之前进行了归一化, 使得每个维度的特征值都集中在[0, 1]范围内, 并分别采用线性核和高斯核获得最优非平行超平面.

4.2.1 lUCI数据集

选择8个用于二元分类的UCI数据集, 数据集特性如表 1所示.正类别和负类别样本总数的比值用(N_P: N_N)来表示.数据集Breast Cancer Wisconsin (prognostic)简称为WPBC, Australian Credit Approval简称为ACA, Contraceptive Method Choice简称为CMC, Connectionist Bench简称为Sonar, Congressional Voting Records简称为Votes.

4.2.2 lexp-NDC datasets

NDC数据集是由David Musicants NDC数据生成器生成, 数据集中的样本成正态分布.为了方便测试新算法的有效性, 将对数正态分布作为转换函数, 对NDC数据集作倾斜化处理.根据概率论, 如果一个连续型随机变量的对数服从正态分布, 则该随机变量本身服从对数正态分布.由此可得, 如果随机变量X₁服从对数正态分布, 则X₂ =ln|X₁|服从正态分布; 同样地, 如果随机变量X₂服从正态分布, 则X₁ =exp(X₂)服从对数正态分布, 该概率密度函数向右倾斜.因此, 倾斜化的NDC数据集称为exp-NDC, 每个样本点有32个特征维度, 并且一个NDC数据集的规模可以在500 ~ 100 000范围内浮动.为了体现新算法在训练速度上的优越性, 在一组规模递增的exp-NDC数据集上运行各个算法.关于exp-NDC数据集的其他详细特性见表 2.

4.3 分类结果: UCI数据集和exp-NDC数据集 4.3.1 线性结果

算法FP-TWSVM、TWSVM、TBSVM和v-TWSVM在线性情形下的实验结果记录在表 1中.黑色字体代表每一个数据集在分类精度或者训练时间方面的最优结果.对于分类精度, 取的是每个数据集的10折验证集上的平均值, 其结果和标准差一起记录在表 1中, 简记为MA, 用百分数表示.对于表 1中的大部分数据集, FP-TWSVM的平均分类精度与TWSVM相当, 略低于TBSVM和v-TWSVM. FP-TWSVM算法在表 1中所有的数据集上的平均精度为88.61 %, 而TWSVM、TBSVM和v-TWSVM在所有数据集上的平均分类精度分别是88.70 %、90.68 %和90.51 %.由此可得, 在大多数UCI数据集上, 使用线性分类器时, 相比于TWSVM和它的变体模型, FP-TWSVM同样可以取得理想的分类精度.在分类精度上, exp-NDC数据集上的实验结果同UCI数据集类似.

本文提出的算法改进了TWSVM模型, 旨在加速训练时间, 并减少内存和时间的消耗, 尤其是在处理大规模数据集时, 通过将一个标准QPP分解成一系列连续的一维单峰函数优化问题, 避免存储大规模的二次型矩阵, 可以显著提升存储效率, 加快训练时间, 提高处理数据的能力.因此, 从直觉上可以推断出, FP-TWSVM在训练时间、存储效率和处理数据的能力上明显要胜于TWSVM及其变体模型.为了验证这一观点, 在表 1的UCI数据集上记录了每个算法的训练时间(简记为TT).在规模适中的UCI数据集上, 训练时间由平均CPU时间来表示, 用的是10折交叉验证技术来计算时间. 表 1记录的实验结果表明, 对于每一个数据集, FP-TWSVM计算出最优分割超平面所需的时间明显少于其他算法. FP-TWSVM在所有UCI数据集上的平均训练时间为5.67×10^-3s, TWSVM、TBSVM和v-TWSVM在所有UCI数据集上的平均训练时间分别为10.25 × 10^-3s、8.95 × 10^-3s和9.65 ×10^-3s.

为了更好地体现新算法的时间高效性和存储高效性, 同样在一组规模递增的exp-NDC数据集(包含了大规模数据集)上进行了线性分类实验, 实验结果如表 2所示.训练样本总数和测试样本总数记为“train-test”, 正类别样本总数和负类别样本总数之比记为N_P :N_N.在保持与其他算法相当的分类精度的条件下, FP-TWSVM的训练速度明显快于其他算法, 并且具有比其他3种算法更高的存储效率, 尤其是在处理大规模数据集(exp-NDC-10k, exp-NDC- 50k, exp-NDC-100k)时, 这种优势体现得更为明显.这些优越性归功于新算法中采用的分解策略、样本选择策略以及其他实现技术上的改进, 这些改进加速了算法的收敛.随着exp-NDC数据集规模的逐渐增大, FP-TWSVM的训练时间也在逐渐增加, 然而, 训练时间的增加速率比其他算法要明显缓慢.值得注意的是, 在一些超大规模的数据集(例如exp-NDC-50k和exp-NDC-100k数据集)上, 其他3种算法由于内存溢出而无法得出最终分类结果, 而FP-TWSVM仍然可以在一个合理的时间范围内产生最优分割超平面, 这无疑证实了FP-TWSVM在面对大规模数据集时的存储高效性, 反应了它强大的数据处理能力.

4.3.2 非线性结果

通过引入两个非平行核生成曲面, 新算法可以很容易地被推广到非线性分类问题中.非线性情况下, 4种算法在UCI数据集和exp-NDC数据集上的分类精度和训练时间记录在表 3和表 4中.

所有算法均采用高斯核函数K(x, x')=exp(-σ||x-x'||²), 并且选取的是相同的核宽度参数.实验结果同样证实了非线性的FP-TWSVM消耗的CPU时间最少, 占有的存储空间最小, 同时又可以保持与其他算法相当的分类精度.在UCI和exp-NDC数据集上最好的平均训练时间分别是8.13 × 10^-3 s和3.53 ×10^-2 s, 均为FP-TWSVM所达到的训练时间, 再次说明了FP-TWSVM强大的数据处理能力.

5 结论

本文提出了一种孪生支持向量机的改进模型, 称为定点孪生支持向量机(fixed-point twin support vector machine, FP-TWSVM).通过将每个QPP分解成一系列有限多个连续的一维优化问题, 显著提高了训练速度, 减少了存储空间.其中, 每个一维的优化问题都是一个单峰函数最小化问题, 可以使用高效的线性搜索方法(例如斐波那契算法或者黄金分割法)求出问题的最佳解.另外, 本文提出了一些实现技术上的改进, 例如样本选择策略、构建主动集以及调节精度参数的cooling技术, 均有利于加快算法的收敛.此外, 通过引入两个非平行核生成曲面, 可以实现FP-TWSVM从线性分类情形到非线性分类情形的推广.实验结果表明, 在保持与其他算法相当的分类精度的同时, FP-TWSVM相比于其他算法具有明显的时间高效性和存储高效性, 因此更加适用于处理大规模数据集.

本文提出的这种“定点”思想以及相关的建立在特定算法设计上的实现技术改进策略, 是否同样适用于TWSVM其他的变体模型将是下一步的研究工作.