支持向量机平凡解判别与修正的新方法
刘春明，左磊，吴军
(国防科技大学 机电工程与自动化学院，湖南 长沙，410073)
摘 要：
题，提出一种新的线性支持向量机(SVM)产生平凡解的判别与修正方法，证明如下SVM平凡解判别定理：SVM最优解是平凡解的充要条件是在样本空间的任意方向上，正负类训练样本的分布满足某种不等式关系，该不等式与正负类训练样本各自的惩罚因子C+、C-有关，与公共的惩罚因子C无关。在以上判别定理的基础上，通过筛选训练样本点及各自的惩罚因子来修正SVM优化求解过程，为有效避免SVM平凡解的产生提供理论依据和技术手段。仿真计算实例表明该方法有效。
关键词：
中图分类号：TP181 文献标志码：A 文章编号：1672-7207(2012)07-2648-07
A new method for discrimination and modification of null solutions in support vector machines
LIU Chun-ming, ZUO Lei, WU Jun
(College of Mechatronics Engineering and Automation, National University of Defence Technology,
Changsha 410073, China)
Abstract: For binary classification problems, a new method for discrimination and modification of null solutions in linear support vector machines (SVMs) was proposed. The following theorems for discrimination of null solutions in SVMs were proved: The necessary and sufficient conditions for the optimal solution of SVMs being a null solution are that for a given training set, the distribution of the positive and negative samples must satisfy an inequality which is related to the respective penalty parameters C+, C- of the two classes, and is independent of the shared penalty parameter C. Based on the above results, a modification method for null solutions in SVMs was presented by selecting samples in the training set, and adjusting the values of penalty parameters, which provides theoretical support and technique method for avoiding generating null solutions in SVMs. Computational examples illustrate the effectiveness of the proposed methods.
Key words: support vector machine; penalty parameter; null solution; convex hull
基于结构风险最小化原理的统计学习理论是近年来计算学习理论的重要研究成果，为研究有限训练样本情况下的统计模式识别，并为更广泛的机器学习问题建立一个较好的理论框架。同时，该理论也发展了一种高效的分类器学习算法——支持向量机(SVM)[1-4]。支持向量机在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，能够获得优于传统模式识别方法的分类性能。但在采用支持向量机构造分类器的时候，可能会出现判别平面的法向量为零的情况，这是由于训练样本在样本空间中的分布以及各自的惩罚因子不同而产生的平凡解问题。如果支持向量机产生平凡解，那么线性判别函数将把样本空间中的所有样本归为一类，这样得到的线性分类器将毫无作用。因此，分析支持向量机平凡解产生的本质原因，在理论和实际应用中都具有重要的意义。在支持向量机与统计学习理论的已有研究中，重点在如何避免这一情况的发生，如采用非线性判别函数或者级联结构等[5-11]，但对平凡解产生的本质原因还缺乏全面深入的分析。研究平凡解产生的原因不仅有益于指导分类器的设计，而且可以使支持向量机理论更加完善。Bennett等[12]给出一种平凡解产生的判别方法。该方法通过求某类训练样本的加权系数列来进行判断，但满足条件的系数列很难求得，并且不能直观地指导我们筛选训练样本和调整惩罚因子，Arreola 等[13-15]也给出类似的结论。本文首先对线性支持向量机的目标函数和训练样本的分布进行分析，提出一种新的基于样本分布的平凡解判别方法，继而给出相关推论；然后讨论各类训练样本的惩罚因子对平凡解产生的影响；最后给出避免平凡解产生的技术途径措施。仿真计算实验表明：本文的结论能够直观地指导筛选训练样本和调整惩罚因子，避免SVM平凡解的产生。
1 线性支持向量机概述
支持向量机的结构风险最小化原则(SRM)要优于传统的经验风险最小化原则(ERM)。不同于ERM试图最小化训练集上的误差的做法，SRM试图利用对函数结构复杂性的控制来最小化期望风险的上界，从而使学习机器获得更好的推广性能，这恰恰是统计学习理论最重要的目标之一[4]。支持向量机的基本算法和模型是针对二类分类问题的，因此本文的讨论重点是使用支持向量机进行二值分类。
图1所示为特征空间中的最优判别平面。如图1所示，考虑一个用某特征空间的超平面对训练样本集进行二值分类的问题。训练样本点为：
(1)
其中：向量xi可能是从对象样本集抽取某些特征直接构造的向量，也可能是原始向量通过某个核函数映射到核空间中的映射向量。
图1 特征空间中的最优判别平面
Fig.1 Optimal distinguish plane in feature space
在特征空间中构造判别平面为：
(2)
使得：
(3)
其中：i=1, 2, …, l。
可以计算出，边界的最小距离为：
(4)
根据SVM对优化判别平面的定义，对该判别平面的求解问题进行简化：在满足条件式(3)的情况下，计算出使
最大化时的判别平面的法向量w和偏移量b。可见，最优判别平面的求解等价于最小化式(5)：
(5)
通过式(5)求得的判别平面为
，平面
和
上的样本点叫做支持向量。
对于线性不可分的训练集，可以引入松弛变量
，公共惩罚因子C＞0，把式(5)改写为下面的求解问题：
(6)
对式(5)和(6)的求解是一个典型的有约束的二次型优化问题。
2 一维特征空间中平凡解的判别定理
图2所示为一维特征空间中的平凡解产生情况。在对图2中的训练样本求解判别平面时，无论式(6)中的C取何值，只要大于等于0，得到的判别平面都是平凡的结果：
。的解就是平凡解。
在上面的例子中，判别函数
就是定义域为实轴的直线。为便于分析，图3分别按照坐标
和
给出正负类训练样本点。在图3中可见：判别函数的斜率是w，目标函数附加项
中的
，就是图3中虚线段的长度和。
图2 一维特征空间中的平凡解产生情况
Fig.2 Condition of generating null solutions in one dimension
图3 目标函数的几何意义
Fig.3 Geometric signification of objective function
最小化，就是最小化图3中虚线段的长度和。由图3可见：当判别函数为
时，使得取得最小值2C。即w=0，b=-1时，取得最小值2C；与此同时，
也取得最小值0。因此，最小化目标函数式(6)，得到的判别平面为
，即把所有的特征点都归为负类。
如果平凡解产生，那么当正类训练样本的数目大于负类训练样本的数目时，得到的判别平面为
，反之是
，数目相等时为
，其中
。
为不失一般性，总假设正类训练样本的数目小于等于负类训练样本的数目。如果平凡解产生，总是满足条件的一个解(以下默认产生的平凡解就是)。如果没有产生平凡解，则必存在一个x0使得
。所以，对式(6)求解得到的任何判别函数，总是存在x 0，使得
，即
(7)
在训练样本中，假设正类样本为：
，负类样本为：
，其中
。引入变量
和
分别标识样本是否受到惩罚，受惩罚的样本
，否则
。为极小化目标函数，未受惩罚的样本所对应的
，受惩罚的样本需要满足条件：
所以应用式(7)消去变量b后，极小化的目标函数为：
(8)
在以上分析讨论的基础上，可给出如下的SVM平凡解判别定理：
定理1 在一维特征空间中，应用式(6)求解得到平凡解的充分必要条件是：对训练样本数目多的一类(数目相等时的每一类，这里假设为负类)中的每个训练样本x0，满足：
(9)
证明：
对式(6)求解得到的任何判别函数，总是存在x0，使得。目标函数式(8)式w的二次多项式，所以当它取极小值时，w=0等价于对所有的线性判别函数，满足：
即
为不失一般性，这里只讨论w＞0的情况，w＜0时同理。
当w＞0时，因为，满足
＞x0的负类样本点都是受惩罚的样本，其对应的
，否则
。即对于给定的x0，
为定值。满
足
的都是受惩罚的样本点，其对应的
。然而对于
＞x0的正类样本，若全部受到惩罚，产生平凡解需满足：
也就是对所有的线性判别函数满足：
所以，极小化目标函数时，w=0等价于对所有的线性判别函数，满足：
即对所有的x0，满足：
(10)
把负类样本从小到大排序为：
，不影响分类结果。对任意
，所有的负类样本都是受惩罚的样本，此时判别式(10)，等价于判别
；对任意
，所有的负类样本都不是受惩罚的样本，此时判别式(10)，等价于判别
；对任意
，其中i=1, …, n-1，此时负类样本受惩罚的数目为n-i，此时判别式(10)，等价于判别
和
。故只需对负类训练样本中的每个样本x0，满足式(10)。
证毕。
3 多维特征空间中的平凡解判别
在多维特征空间，应用式(6)求解得到SVM平凡解的判别条件可以从一维情形得到推广：
定理2 在特征空间中，应用式(6)求解得到平凡解等价于对训练样本数目多的一类(数目相等时的每一类，这里假设为负类)中的每个训练样本x 0，在任意方向w上，满足：
(11)
其中：
是判别函数
对负类样本的惩罚标识，惩罚为1，否则为0。
在一维特征空间中，方向有2个：正向和负向；在二维特征空间中，方向有360°。然而，在多维特征空间中，方向更多，样本点是否被惩罚也难以判断，故不容易计算。下面我们先引入闭凸包的概念[14]：
设x1, x2, …, xn是特征空间中的n个点，记Q是包含这些点的最小闭凸集(闭凸包)。则：
，
，
，
。
如果2类训练样本的闭凸包不相交，那么2闭凸包之间最短线段的中垂面(超平面) f(x)=0就是线性支持向量机的最优解[14]，并且对所有的正类训练样本满足f(x)≥1，负类训练样本满足f(x)≤-1。为了便于对训练样本进行分析，有：
推论1 在特征空间中，如果训练样本数目少的一类(数目相等时中的每一类)的训练样本重心，落在另一类训练样本生成的闭凸包之外，那么应用式(6)求解必不产生平凡解。
证明：为不失一般性，设正类样本为：
，负类样本为：
，其中m≤n。正
类样本的重心
不落在负类样本生成的闭凸包内，即正类样本重心生成的闭凸包与负类样本生成的闭凸包不相交，则存在一个线性判别函数，使得：
用f(x)对样本进行分类时，所有的负类样本都不受到惩罚，故存在x0，使得：
所以有：
＜
上式不满足式(11)的要求，故应用式(6)求解得到的不是平凡解，命题得证。
图4给出重心落在另一类的闭凸包内且不产生平凡解的情况。在图4中，正类样本的重心和负类样本的重心分别落在另一类的闭凸包内，但求解得到的不是平凡解，所以推论1只是充分条件，不是必要条件。
图4 重心都落在另一类的闭凸包内且不产生平凡解的情况
Fig.4 Center of gravity falling within closed convex hull of other class and not generating null solutions
推论2 在特征空间中，数目相同的2类训练样本，应用(6)式求解得到平凡解等价于2类样本训练的重心重合。
证明：必要性。在任意方向w上，存在判别函数
，使得所有的负类样本受到惩罚，其中
。再由定理2，若产生平凡解则有：
所以：
因为2类训练样本数目相同，同理有：
于是
由w的任意性，可得
。
充分性。对负类样本中的每个样本x0，在任意方向w上，是判别函数
对负类样本的惩罚标识，即
＞0时，；
时，，所以有：
故求解得到平凡解，命题得证。
4 基于惩罚因子C的平凡解判别与 修正
在2类样本利益不同的情况下，需引入不同的惩罚因子
和
。此时的目标函数为：
(12)
等价于式(6)中C=1，正负类样本的数目分别增加到倍和倍的情形，同理可得：
定理3 在特征空间中，应用式(12)求解得到平凡解等价于对集合
中大的一类(相等时中的每一类，这里假设为负类)中的每个训练样本x0，在任意方向w上，满足式(13)。
(13)
其中：是判别函数对负类样本的惩罚标识，惩罚为1，否则为0。
推论3 在特征空间中，如果集合中小的一类(相等时中的每一类)的训练样本重心，落在另一类训练样本生成的闭凸包之外，那么应用(12)式求解必不产生平凡解。
推论4 在特征空间中，满足
的2类训练样本，应用式(12)求解得到平凡解等价于2类训练样本的重心重合。
Bennett等[12]也得到与推论4相同的结论，由于2类训练样本重心重合的情况很少发生，所以可以较稳定地获得线性规划分类器。
有些时候，要求某一类必须分得正确(即此类的惩罚因子是
)，有如下结论：
推论5 在特征空间中，要求某一类必须分得正确，那么应用式(12)求解得到平凡解等价于另一类的训练样本重心落在该类训练样本生成的闭凸包之内。
证明 这里假设负类必须分得正确。
必要性。因为式(12)中的惩罚因子
，所以
，由推论3得证；
充分性。由定理3可知：得到平凡解等价于对负类中的每个样本x0，在任意方向w上有：
(14)
当存在负类样本受到惩罚时，＞0，式(14)显然成立；
不存在负类样本受到惩罚时，
，并且
，其中i=1, …, n。又因为正类样本的重心落在负类样本生成的闭凸包内，所以存在
列，使得：
式(14)成立，命题得证。
根据上述定理，可以给出基于惩罚因子的SVM平凡解修正方法，即：
当惩罚因子不能改变时，可以筛选一些样本，使得训练样本数目少的一类(数目相等时中的每一类)的训练样本重心，不落在另一类训练样本生成的闭凸包内；或者使2类的训练样本数目相同，只要避免2类的训练样本重心重合即可。
当惩罚因子可以改变时，可以改变惩罚因子的大小，也可以筛选一些样本，使得集合中小的一类(相等时中的任一类)的训练样本重心，不落在另一类训练样本生成的闭凸包内；或者使2类满足，只要避免2类的训练样本重心重合即可。
当要求某一类必须分得正确时，只能够通过筛选样本，使得另一类的训练样本重心落在该类样本生成的闭凸包之外。
5 计算实例
图5所示为二维特征空间中正负类训练样本分布。正类训练样本的数目小于负类训练样本的数目。应用式(6)求解得到了平凡解。
图5 仿真试验中的训练样本分布
Fig.5 Training sample distribution in simulation experiment
如果把正类训练样本中的(-4, 0)去掉，那么正类训练样本的重心就落在负类训练样本生成的闭凸包之外，故可以避免平凡解的产生，如图6所示，其中C=1。又因为正类训练样本的重心与负类训练样本的重心不重合，所以调整正负类各自的惩罚因子也可以避免平凡解的产生，如图7所示，其中C+=4，C-=3。
当要求负类训练样本必须分得正确时，同样把正类训练样本中的(-4, 0)去掉，那么正类训练样本的重心就落在了负类训练样本生成的闭凸包之外，结果如图6所示，其中C+=4。当要求正类训练样本必须分得正确时，把负类训练样本中的(-2, 2)去掉，那么负类训练样本的重心就落在正类训练样本生成的闭凸包之外，结果如图8所示，其中C-=4。
图6 通过筛选样本点来避免平凡解的产生(要求负类样本被正确分类)
Fig.6 Avoiding generation of null solutions by filtering some samples (Negative-class training samples must be properly distinguished)
图7 通过调整各自惩罚因子来避免平凡解的产生
Fig.7 Avoiding generation of null solutions by adjusting respective penalty factors
图8 通过筛选样本点来避免平凡解的产生(要求正类样本被正确分类)
Fig.8 Avoiding generation of null solutions by filtering some samples (Positive-class training samples must be properly distinguished)
6 结论
1) 理论分析线性支持向量机产生平凡解的原因，得到一维特征空间中平凡解产生的新的判别方法，继而推广到多维特征空间。然后给出一些推论，及避免平凡解产生的一些措施，最后实验验证方法的有效性。
2) 提出避免平凡解产生的方法，通过筛选训练样本点来改变训练样本重心，将会失去很多的样本特性，在很大的程度上扭曲样本的分布，况且有时样本的筛选也不够容易，所以最方便的办法就是在2类样本重心不重合的情况下，修改2类样本的惩罚因子，使得。
3) 在平凡解产生的情况下，虽然通过一些措施可以避免平凡解的产生，然而得到的分类器的分类误差很大，所以这时应当提取更加合适的样本特征及进行必要的特征变换。
参考文献：
[1] Cristianini N, Shawf-Taylor J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge University Press, 2000.
[2] Burges C J C. A tutorial on support vector machine for pattern recognition[J]. Data Mining and Knowledge Discovery, 1998, 2(2): 121-167.
[3] Cortes C, Vapnik V. Support vector networks[J]. Machine Learning, 1995, 20: 273-297.
[4] 陈毅松, 汪国平, 董士海. 基于支持向量机的渐进直推式分类学习算法[J]. 软件学报, 2003, 14(3): 451-460.
CHEN Yi-song, WANG Guo-ping, DONG Shi-hai. A progressive transductive inference algorithm based on support vector machine[J]. Journal of Software, 2003, 14(3): 451-460.
[5] Bennett K, Blue J. A support vector machine approach to decision trees[R]. Troy, NY: Rensselaer Polytechnic Institute Math Repot, 1997
[6] Frphlich H, Chapelle O, Scholkopf B. Feature selection for support vector machines using genetic algorithm[J]. International Journal on Artificial Intelligence Tools, 2004, 13(4): 791-800
[7] Wan V, Renals S. Speaker verification using sequence discriminant support vector machines[J]. IEEE Transactions on Speech and Audio Processing, 2005, 13(2): 203-210
[8] Sungmoon C, Sang H O, Soo-Young L. Support vector machines with binary tree architecture for multi-class classification[J]. Neural Information Processing-Letters and Reviews, 2004, 2(3): 47-51
[9] Howley T, Madden MG. The genetic kernel support vector machine: description and evaluation[J]. Artificial Intelligence Review, 2005, 24(3/4): 379-395
[10] 陶晓燕, 姬红兵, 马志强. 基于样本分布不平衡的近似支持向量机[J]. 计算机科学, 2007, 34(5): 174-176
TAO Xiao-yan, JI Hong-bing, MA Zhi-qiang. Proximal support vector machines for samples with unbalanced distribution[J]. Computer Science, 2007, 34(5): 174-176.
[11] 陶卿, 孙德敏, 范劲松, 等. 基于闭凸包收缩的最大边缘线性分类器. 软件学报, 2002, 13(3): 404-409
TAO Qing, SUN De-min, FAN Jing-song, et al. Maximal margin linear classifier based on the contraction of the closed convex hull[J]. Journal of Software, 2002, 13(3): 404-409.
[12] Bennett K P, Mangasarian O L. Robust linear programming discrimination of two linearly inseparable sets[J]. Optimization Methods and Software, 1992, 1(1): 23-34.
[13] Arreola K Z, Fehr J, Burkhardt H. Fast support vector machine classification using linear SVMs[C]//18th International Conference on Pattern Recognition. Hong Kong: Pattern Recognition, 2006: 366-369.
[14] Arreola K Z, Fehr J, Burkhardt H. Fast support vector machine classification of very large datasets[R]. Freiburg: Albert Ludwigs University Freiburg Institute for Information, 2007.
[15] 刘小茂, 全廷伟, 张钧. 线性支持向量分类机的平凡解[J]. 华中科技大学学报: 自然科学版, 2007, 35(10): 57-59.
LIU Xiao-mao, QUAN Ting-wei, ZHANG Jun. Degenerate solution to linear support vector machine[J]. Journal of Huazhong University of Science and Technology: Nature Science Edition, 2007, 35(10): 57-59.
(编辑 邓履翔)
收稿日期：2011-05-03；修回日期：2011-09-07
基金项目：国家自然科学基金资助项目(60774076, 90820302)
通信作者：刘春明(1981-)，黑龙江讷河人，博士研究生，从事模式识别与智能系统方面研究；电话：13974914442；E-mail: lccmmm@126.com
摘要：针对二类分类问题，提出一种新的线性支持向量机(SVM)产生平凡解的判别与修正方法，证明如下SVM平凡解判别定理：SVM最优解是平凡解的充要条件是在样本空间的任意方向上，正负类训练样本的分布满足某种不等式关系，该不等式与正负类训练样本各自的惩罚因子C+、C-有关，与公共的惩罚因子C无关。在以上判别定理的基础上，通过筛选训练样本点及各自的惩罚因子来修正SVM优化求解过程，为有效避免SVM平凡解的产生提供理论依据和技术手段。仿真计算实例表明该方法有效。
