3．支持向量机（回归） 3.1.1 支持向量机 支持向量机（SVM）是美国Vapnik教授于1990年代提出的，2000年代后成为了很受欢迎的机器学习方法。它将输入样本集合变换到高维空间使得其分离性状况得到改善。它的结构酷似三层感知器，是构造分类规则的通用方法。SVM方法的贡献在于，它使得人们可以在非常高维的空间中构造出好的分类规则，为分类算法提供了统一的理论框架。作为副产品，SVM从理论上解释了多层感知器的隐蔽层数目和隐节点数目的作用，因此，将神经网络的学习算法纳入了核技巧范畴。

所谓核技巧，就是找一个核函数(,)Kxy使其满足(,)((),())Kxyxy，代替在特征空间中内积(),())xy（的计算。因为对于非线性分类，一般是先找一个非线性映射将输入数据映射到高维特征空间，使之分离性状况得到很大改观，此时在该特征空间中进行分类，然后再返会原空间，就得到了原输入空间的非线性分类。由于内积运算量相当大，核技巧就是为了降低计算量而生的。

特别， 对特征空间H为Hilbert空间的情形，设(,)Kxy是定义在输入空间nR上的二元函数，设H中的规范正交基为12(),(),...,(),...nxxx。如果

221(,)((),()),{}kkkkkKxyaxyal



，

那么取1()()kkkxax即为所求的非线性嵌入映射。由于核函数(,)Kxy的定义域是原来的输入空间，而不是高维的特征空间。因此，巧妙地避开了计算高维内积(),())xy（所需付出的计算代价。实际计算中，我们只要选定一个(,)Kxy， 并不去重构嵌入映射1()()kkkxax。所以寻找核函数(,)Kxy（对称且非负）就是主要任务了。满足以上条件的核函数很多，例如

可以取为d-阶多项式：(,)(1)dKxyxy，其中y为固定元素。 可以取为径向函数：22(,)exp||||/Kxyxy，其中y为固定元素。 可以取为神经网络惯用的核函数：12(,)tanh()Kxycxyc，其中y为固定元素。

一般地，核函数的存在性只依赖于如何寻找一个平方收敛的非负序列ka。这样的序列在2l空间的正锥22|0,kklalak中的序列都满足。但哪一个最佳还有待于进一步讨论。经验表明，分类问题对于核函数不太敏感。当然，重新构造一个核函数也不是一个简单的事。因此，实际操作中往往就在上述三类中挑出一个来使用就可以了。

支持向量机的结构示意图可以表示如下：

图1 支持向量机结构示意图 其中输入层是为了存贮输入数据，并不作任何加工运算；中间层是通过对样本集的学习，选择(,),1,2,3,...,iKxxiL；最后一层就是构造分类函数

1sgn((,))LiiiiyyaKxxb 整个过程等价于在特征空间中构造一个最优超平面。 支持向量机的作用之一就是分类。根据分类的任务，可以划分为一分类，二分类以及多分类。对于多类分类问题，可以用若干种手法将其分解为若干个二分类问题叠加。因此，为了实现支持向量机分类的算法，我们只要针对二分类，从头来给出它的数学原理。

3.1.2 支持向量机分类的数学原理 设样本集为(,)|;1,1,1,...,niiiixyxRyiI，我们的目的是寻找一个最优超平面H使得标签为＋1 和－1的两类点不仅分开且分得间隔最大。

当在n维欧几里德空间中就可以实现线性分离时，也即存在超平面将样本集按照标签－1与＋1分在两边。由于超平面在n维欧几里德空间中的数学表达

式是一个线性方程 ,0wxb，其中，w为系数向量，x为n维变量，

,wx内积，b为常数。空间中点ix到超平面L的距离|,|(,)||||iiwxbdxLw。欲使得(,)idxH最大，等价于21||||2w最小。于是，

得到一个在约束条件下的极值问题

21min||||2(,)1,1,2,...,iiw

ywxbiI

引入Lagrange乘子12(,,...,)I，可以解得关于该参变量的方程 121,1(),IIiijijijiijQyyxx



称之为Lagrange对偶函数。其约束条件为 ,10,0,1,2,...,IiiiijyiI

在此约束条件之下， 使得()Q达到最大值的的许多分量为0，不为0的i 所对应的样本ix就称为支持向量。这就是支持向量的来历。

当在输入空间不能实现线性分离，假设我们找到了非线性映射将样本集(,)|;1,1,1,...,niiiixyxRyiI映射到高维特征空间H中，此时我们

考虑在H中的集合((),)|;1,1,1,...,niiiixyxRyiI的线性分类，即在H中构造超平面，其权系数w满足类似的极值问题。由于允许部分点可以例外，那么可以引入松弛项，即改写为：

211min||||2(,)1,0,1,2,...,LiiiiiiwCywxbiI









最终转化为一个二次型在约束条件下的二次规划问题： '''11min20,0(,...,)(,...,)TTI

DcyACC





其中，1(,...,)TIyyy，(1,...,1)Tc，1,(,)ijijijIDKxxyy为矩阵。(,)Kxs 是核函数。 一分类问题是一个极端情形但却又是非常有用的，它可以表示为如下数学模型：设|,1,...,niixxRiI为空间nR的有限观测点，找一个以a为心，以R为半径的包含这些点的最小球体。因此，一分类是对于求一个化合物成分的最小包络曲面的最佳方法。与前面完全相同的手法，设是由某个核函数(,)Kxs导出的从输入空间到特征空间中的嵌入映射，最后可以得到二次规划问题

'''11min20,0(,...,)(,...,)TTI

DcyACC





其中，1(,...,)TIyyy， (1,...,1)Tc， 1,(,)ijijijIDKxxyy为矩阵。(,)Kxs

是核函数。此时

111()(,)2(,)(,)LLLiiijijijifxKxxKxxKxx

此时几乎所有的点满足2()fxR。参数C起着控制落在球外点的数目,变化区间为：1/1LC.

3.1.3基于线性规划的SVM分类 由于分类问题的自然推理过程都会归结到二次规划求解，计算复杂度相对较高。如果能将其简化为线性规划而且没有较大的误差， 那么计算量将急速减少。于是提出了基于线性规划的SVM分类。此方法经过数学严格推理，是合理的（因为涉及泛函的知识较多，推理过程放在附录中）。因此产生了基于线性规划一分类、二分类、多分类。此处，我们仅给出基于线性规划的SVM分类的最终形式：

111min.(,),1,...,;1;,0LiiLLiijjiiiiiCstKxxjL















 解出与则得出决策函数1()(,)LiijifxKxx以及阈值。参数C控制着满足条件()fx的样本数量。特别核函数取为径向函数时，参数2越小，精度越高。 另外，要提醒注意的是，在求解大规模分类问题得SVM算法实现时，需要以下辅助手段：

停机准则：由于分类问题等价于求对偶问题在约束条件下的极值

1111max(,)..0,0,1,2,...,LLLiijijijiijLiiijyyKxxstyCiL









 而KKT条件 [(,())1]0()0,1,2,...,iiiiiiywxbCiL



是收敛的充分必要条件。 因此通过监控KKT条件来得到停机条件

110,0,1,2,...,1,0,((,))1,0,1,,LiiijiLiiiijijiyCiLiyyKxxbCiCi















 这个条件中的不等式不必严格成立，只要在一定误差条件下成立就可以用了。 选块算法＋分解法

1. 给定参数0M，0， 0k。 选取初始工作集0WT，记其对应的样本点的下标集为0J。令kWT第k次更新的工作集，其对应的样本点的下标集为kJ。 2. 基于工作集kWT， 由优化问题

1111max(,)..0,0,LLLiijijijiijLiiikjyyKxxstyCiJ









 求出最优解ˆ{,}jkajJ，构造 1(,...,)kkkL按照如下方式：