3．支持向量机（回归）
3.1.1 支持向量机
支持向量机（SVM ）是美国Vapnik 教授于1990年代提出的，2000年代后成为了很受欢迎的机器学习方法。它将输入样本集合变换到高维空间使得其分离性状况得到改善。它的结构酷似三层感知器，是构造分类规则的通用方法。SVM 方法的贡献在于，它使得人们可以在非常高维的空间中构造出好的分类规则，为分类算法提供了统一的理论框架。作为副产品，SVM 从理论上解释了多层感知器的隐蔽层数目和隐节点数目的作用，因此，将神经网络的学习算法纳入了核技巧范畴。
所谓核技巧，就是找一个核函数K (x , y ) 使其满足K (x , y ) =(φ(x ), φ(y )) ，代
替在特征空间中内积（φ(x ), φ(y )) 的计算。因为对于非线性分类，一般是先找一个非线性映射φ将输入数据映射到高维特征空间，使之分离性状况得到很大改观，此时在该特征空间中进行分类，然后再返会原空间，就得到了原输入空间的非线性分类。由于内积运算量相当大，核技巧就是为了降低计算量而生的。
特别， 对特征空间H 为Hilbert 空间的情形，设K (x , y ) 是定义在输入空间
R
n
上的二元函数，设H 中的规范正交基为φ1(x ), φ2(x ),..., φn (x ),
... 。如果
∞
K (x , y ) =
∑
k =1
a k (φk (x ), φk (y )),
2
{a k }∈l
2
，
∞
那么取φ(x ) =∑
k =1
a k φk (x )
即为所求的非线性嵌入映射。由于核函数K (x , y ) 的定义
域是原来的输入空间，而不是高维的特征空间。因此，巧妙地避开了计算高维内
（φ(x ), φ(y )) 所需付出的计算代价。实际计算中，我们只要选定一个K (x , y ) ，积
∞
并不去重构嵌入映射φ(x )
=
∑
k =1
a k φk (x )
。所以寻找核函数K (x , y ) （对称且非负）
就是主要任务了。满足以上条件的核函数很多，例如
● 可以取为d-阶多项式：K (x , y )
=(1+x y )
d
，其中y 为固定元素。
● 可以取为径向函数：K (x , y )
=ex p (||x -y ||/σ
2
2
)，其中y 为固定元素。
● 可以取为神经网络惯用的核函数：K (x , y ) =
定元素。
tan h (c 1(x y ) +c 2)
，其中y 为固
一般地，核函数的存在性只依赖于如何寻找一个平方收敛的非负序列{a k }。这样的序列在l 2空间的正锥l 2+
=
{{a }∈l
k
2
|a k ≥0, ∀k }
中的序列都满足。但哪一个最
佳还有待于进一步讨论。经验表明，分类问题对于核函数不太敏感。当然，重新构造一个核函数也不是一个简单的事。因此，实际操作中往往就在上述三类中挑出一个来使用就可以了。
支持向量机的结构示意图可以表示如下：
图1 支持向量机结构示意图
其中输入层是为了存贮输入数据，并不作任何加工运算；中间层是通过对样本集的学习，选择K (x , x i ),
i =1, 2, 3,..., L
；最后一层就是构造分类函数
L
y =s g n (∑y i a i K (x , x i ) +b )
i =1
整个过程等价于在特征空间中构造一个最优超平面。
支持向量机的作用之一就是分类。根据分类的任务，可以划分为一分类，二分类以及多分类。对于多类分类问题，可以用若干种手法将其分解为若干个二分类问题叠加。因此，为了实现支持向量机分类的算法，我们只要针对二分类，从头来给出它的数学原理。
3.1.2 支持向量机分类的数学原理
设样本集为{(x i , y i ) |x i ∈R ; y i ∈{-1, +1}, i =1,..., I }
n
，我们的目的是寻找一个最优
超平面H 使得标签为＋1 和－1的两类点不仅分开且分得间隔最大。
当在n 维欧几里德空间中就可以实现线性分离时，也即存在超平面将样本集
按照标签－1与＋1分在两边。由于超平面在n 维欧几里德空间中的数学表达
式是一个线性方程
w , x >+b =0
，其中，w 为系数向量，x 为n 维变量，
x i
内积，
|i
|w |
b
为常数。空间中点
+b |
到超平面
12||w ||
2
L
的距离
d (x , L =) i
||
。欲使得d (x i , H ) 最大，等价于
最小。于是，
得到一个在约束条件下的极值问题
1⎧2
m in ||w ||⎪
2⎨
⎪y (+b ) ≥1,
i ⎩i
i =1, 2,..., I
引入Lagrange 乘子α
=(α1, α2,..., αI )
，可以解得关于该参变量的方程
I I
i
Q (α) =
∑α
i =1
-
12
∑
i , j =1
αi αj y i y j
称之为Lagrange 对偶函数。其约束条件为
I
∑
i , j =1
αi y i =0, αi ≥0, i =1, 2,..., I
在此约束条件之下， 使得Q (α) 达到最大值的α的许多分量为0，不为0的αi 所对应的样本x i 就称为支持向量。这就是支持向量的来历。
当在输入空间不能实现线性分离，假设我们找到了非线性映射φ将样本集
{(x
i
, y i ) |x i ∈R ; y i ∈{-1, +1}, i =1,..., I }
n
n
映射到高维特征空间H 中，此时我们
考虑在H 中的集合{(φ(x i ), y i ) |x i ∈R ; y i ∈{-1, +1}, i =1,..., I }的线性分类，即
在H 中构造超平面，其权系数w 满足类似的极值问题。由于允许部分点可以例外，那么可以引入松弛项，即改写为：
1⎧2
m in ||w ||+C ∑ξi ⎪
2⎨i =1
⎪y (+b ) ≥1-ξ,
i i ⎩i
L
ξi ≥0, i =1, 2,..., I
最终转化为一个二次型在约束条件下的二次规划问题：
1' ⎧'
m in αD α+c α⎪α
2⎨
⎪y ' α=0, 0≤α=(α,..., α) T ≤A =(C ,..., C ) T ⎩1I
其中，y
=(y 1,..., y I )
T
，c
=(-1,..., -1)
T
，D
=
(K (x , x
i
j
) y i y j
)
1≤i , j ≤I
为矩阵。K (x , s )
是核函数。
一分类问题是一个极端情形但却又是非常有用的，它可以表示为如下数学模型：设{x i
|x i ∈R , i =1,..., I }
n
为空间R n 的有限观测点，找一个以a 为心，以R 为半径
的包含这些点的最小球体。因此，一分类是对于求一个化合物成分的最小包络曲面的最佳方法。与前面完全相同的手法，设φ是由某个核函数K (x , s ) 导出的从输入空间到特征空间中的嵌入映射，最后可以得到二次规划问题
1' ⎧'
m in αD α+c α⎪α
2⎨
⎪y ' α=0, 0≤α=(α,..., α) T ≤A =(C ,..., C ) T ⎩1I
其中，y
=(y 1,..., y I )
T
， c
=(-1,..., -1)
T
， D
=
(K (x , x
i
j
) y i y j
)
1≤i , j ≤I
为矩阵。K (x , s )
是核函数。此时
L L L
i
f (x ) =K (x , x ) -2∑αi K (x , x i ) +
i =1
∑∑α
j =1
i =1
αj K (x i , x j )
此时几乎所有的点满足为：1/L
f (x ) ≤R
2
。参数C 起着控制落在球外点的数目, 变化区间
3.1.3基于线性规划的SVM 分类
由于分类问题的自然推理过程都会归结到二次规划求解，计算复杂度相对较高。
如果能将其简化为线性规划而且没有较大的误差， 那么计算量将急速减少。于是提出了基于线性规划的SVM 分类。此方法经过数学严格推理，是合理的（因为涉及泛函的知识较多，推理过程放在附录中）。因此产生了基于线性规划一分类、二分类、多分类。此处，我们仅给出基于线性规划的SVM 分类的最终形式：
⎧⎛m in ⎪ -ρ+C
⎝⎪⎪⎨s . t
L
∑
i =1
ξi ⎪
⎭
⎫
L
⎪L
⎪∑αi K (x i , x j ) ≥ρ-ξj , j =1,..., L ; ⎪⎩i =1
∑α
i =1
i
=1; αi , ξi ≥0
L
解出α与ρ则得出决策函数件
f (x ) =
∑α
i =1
i
K (x i , x j )
以及阈值。参数C 控制着满足条
f (x ) ≥ρ
的样本数量。特别核函数取为径向函数时，参数σ2越小，精度越高。
另外，要提醒注意的是，在求解大规模分类问题得SVM 算法实现时，需要以下辅
助手段：
停机准则：由于分类问题等价于求对偶问题在约束条件下的极值
⎧
⎪m a x ∑αi -∑∑αi αj y i y j K (x i , x j )
i =1i =1j =1⎪
⎨L ⎪s . t .
∑αi y i =0, 0≤αi ≤C , i =1, 2,..., L ⎪j =1⎩
L
L
L
而KKT 条件
⎧αi [y i (+b ) -1+ξi ]=0
⎨
⎩(C -αi ) ξi =0, i =1, 2,..., L
是收敛的充分必要条件。 因此通过监控KKT 条件来得到停机条件
⎧
⎪∑αi y i =0, 0≤αi ≤C , i =1, 2,..., L ⎪j =1⎪
⎧≥1, αi =0, ∀i ⎨L
⎪⎪
y i (∑αi y i K (x i , x j ) +b ) ⎨=1, 0
L
这个条件中的不等式不必严格成立，只要在一定误差条件下成立就可以用了。
选块算法＋分解法
1. 给定参数M
>0
，ε
>0
，
k =0
。 选取初始工作集W 0
⊂T
，记其对应的样
本点的下标集为J 0。令W k 集为J k 。 2. 基于工作集W k
⊂T
⊂T
第k 次更新的工作集，其对应的样本点的下标
， 由优化问题
⎧
⎪m a x ∑αi -∑∑αi αj y i y j K (x i , x j )
i =1i =1j =1⎪
⎨L ⎪s . t .
∑αi y i =0, 0≤αi ≤C , i ∈J k
⎪j =1⎩
L
L
L
ˆj , 求出最优解{a j ∈J k }，构造 α
k
=(α1,..., αL )
k k
按照如下方式：
α
k j
ˆj , ⎧⎪α=⎨⎪⎩0,
k
j ∈J k j ∉J k
3. 如果αk 已经在精度ε内满足停机准则，那么以此权系数构造决策函数即可。
否则继续下一步。 4. 在T
\W k
中找出M 个最严重破坏条件
⎧≥1,
⎪
y i (∑αi y i K (x i , x j ) +b ) ⎨=1,
j =1⎪
⎩≤1,
L
αi =0, ∀i
0
αi =C , ∀i
加入W k 得出新的工作集W k +1，相应的下标集记为J k +1。 5． 重复2）－3），直到样本集耗完为止。
序列最小优化算法（SMO ） Input: the observed dataset
ε>0
S ={(x 1, y 1),..., (x l , y l ) |x i ∈R , y j ∈R }
n
, 输入精度要求
及指定核函数K (x , y ) ，初始化α0
=0
，k
=0
。
Output: the classification of these samples Step1. 由更新公式
α2α1
k +1
=α2+
k
k
y (E -E )
k
k +1
k +1
=α1+y 1y 2(α2-α2
)
Step2. 如果第k 步时达到停机要求，取近似解αˆ
停机为止，取为近似解。
=α
k
，否则继续迭代，直到满足
3.2 支持向量回归（SVR ）模型
对于分类，支持向量机相当于导师样本为有限集的情形。考虑导师集合为不可数的情形，例如训练集可以为形如
S ={(x 1, y 1),..., (x l , y l ) |x i ∈R , y j ∈R }
n
的情形，则演化出支持向量回归概念。
支持向量回归也分为线性回归和非线性回归两种，但不是统计学中的线性或者非线性回归了，而是根据是否需要嵌入到高维空间来划分的，我们简述如下：
● 对于给定的样本集S , 以及任意给定的ε
面称
f (x ) =+b ,
w ∈R , b ∈R
n
>0
，如果在原始空间R n 存在超平
∀(x i , y i ) ∈S
使得 |
y i -f (x i ) |≤ε,
，则
f (x ) =+b
是样本集合S 的ε－线性回归。
∀(x i , y i ) ∈S
与初等代数类似，|平面
y i -f (x i ) |≤ε,
等价于S 中任何点(x i ,
y i )
到超
f (x ) =+
b 。由于我们是分类，所以希望距离都尽可能大。也即使得
调整超平面的斜率w 使得与S 中任点(x i ,
y
i )
最大化，这等价于要求m in {||w ||2}。于是，ε－线性回归问题转化
为优化问题：
⎧⎪m in ⎨⎪⎩s . t .
1
2
||w ||
2
|+b -y i |≤ε, i =1, 2,..., l
于是，引入松弛变量，并使用Lagrange 乘子法，得到优化问题的对偶形式：
l
⎧⎧1l
***
⎪m in ⎨-∑(αi -αi )(αj -αj ) +∑(αi -αi ) y i -⎪i =1⎩2i , j =1⎨
l
**⎪
s . t . (αi -αi ) =0, 0≤αi , αi ≤C , i =1, 2,..., l ∑⎪⎩
i =1
l
∑
i =1
(αi +αi ) ε⎬
*
⎫⎭
● 对于不可能在原始空间R n 就可以线性分离的样本集S ，先用一个非线性映射
φ
将数据S 映射到一个高维特征空间中，使得φ(S ) 在特征空间H 中具有很好
的线性回归特征，先在该特征空间中进行线性回归，然后返回到原始空间R n 中。这就是支持向量非线性回归。
于是，支持向量非线性回归的对偶优化问题如下：
l
⎧⎧1l
***
⎪m in ⎨-∑(αi -αi )(αj -αj ) +∑(αi -αi ) y i -⎪i =1⎩2i , j =1⎨
l
**⎪
s . t . (αi -αi ) =0, 0≤αi , αi ≤C , i =1, 2,..., l ∑⎪⎩
i =1
l
∑
i =1
(αi +αi ) ε⎬
*
⎫⎭
于是，非线性回归问题的实施步骤为：
1．寻找一个核函数K (s , t ) 使得K (x i , x j )
=
，
2．求优化问题
l
⎧⎧1l
***
⎪m in ⎨-∑(αi -αi )(αj -αj ) K (x i , x j ) +∑(αi -αi ) y i -⎪i =1⎩2i , j =1
⎨
l
**⎪
s . t . (αi -αi ) =0, 0≤αi , αi ≤C , i =1, 2,..., l ∑⎪⎩
i =1
l
∑
i =1
(αi +αi ) ε⎬
*
⎫⎭
的解α
3． 计算
i
, αi
*
。
⎧
y +ε-⎪j ⎪b =⎨
⎪y -ε-
j ⎪⎩
l
∑
i , j =1l
(αi -αi ) K (x j , x i ),
*
当
αi ∈（0，C )
(αi -αi ) K (x j , x i ),
*
∑
i , j =1
当
αi ∈（0，C )
*
4．构造非线性函数
l
f (x ) =
∑
i =1
(αi -αi ) K (x j , x ) +b ,
*
x i ∈R , b ∈R
n
。
3.2.2支持向量机分类与支持向量回归的关系
支持向量机用以分类和回归，两者到底是什么关系？为了建立回归与分类的关系，我们在特征空间中考虑如下的上下移动集合：
D
+
={((φ(x i ), y i +ε+1) |(x i , y i ) ∈S }，D
-
={((φ(x i ), y i -ε-1) |(x i , y i ) ∈S }
对于充分大的ε，D +与D -是线性可分离的。于是得出关于D +与D -分类。引入松弛变量ξ，由SVM 分类方法得到
1⎧2
ˆ||+C ∑ξi m in ||w ⎪
2i =1⎨⎪ˆ, z i >+b ) -ξi ≤-1, ⎩s . t .
ˆˆ改写为w 将目标函数中的w
L
ˆ, z i >+b ) +ξi ≥1, z i ∈D ,
ˆ2 特别令w
L
+
z i ∈D , ξi ≥0, i =1, 2,..., l
-
=-1
, 那么上式变成
1⎧2
ˆ1||+1m in ||w +C ∑ξi
2⎪
2i =1
⎪⎪
ˆ1, φ(x i ) >-y i -ε-1+b -ξi ≤-1, ⎨s . t .
⎪⎪⎩
ˆ1, φ(x i ) >-y i +ε+1+b +ξi ≤1,
ξi ≥0, i =1, 2,..., l
而基于观测集S
={(x 1, y 1),..., (x l , y l ) |x i ∈R , y j ∈R }
n
，在特征空间中寻找单参数约
束下的回归函数
f (x ) =+b
的问题等价于
L
1⎧2
m in ||w ||+C ∑ξi ⎪
2i =1
⎪⎪
⎨s . t . y i --b ≤ξi +ε, ⎪⎪⎪⎩
-y i +b ≤ξi +ε,
ξi ≥0, i =1, 2,..., l
也就是说，回归问题可以通过分类的算法来实现。
附录：基于线性规划的分类的合理性
设输入向量的空间为R n ， 记L p (R n ), 1≤
g
p ≤∞,
为R n 上一切p －绝对值可积函数），按照通常的加法和数乘，构成
（即 一切可测且满足⎰
R
n
|g (x ) |d μ(x )
p
的线性空间。一般地，我们偏好选则一个非线性映射φ将R n 嵌入到L 2(R n ) 空间。因为在该Hilbert 空间中，任意闭子空间的正交补子空间存在问题是一个已解决了的问题，而在L p (R n ),
p ≠2,
还是一个没有被完全解决的问题。如前所述，在此
空间中得到的结果，特别是诱导出的核函数是一个非常好的亮点。
在有限维空间中，任何距离都是等价的。这一特征也是有限维空间独有的。类似于上面所述，我们可以在有限维空间R n 上赋予L p 范数：
⎛p ⎫
||x ||p = ∑|x i |⎪
⎝i =1⎭
n
1p
m a x 1≤i ≤n |x i |
p L 1
取遍区间
特别，L ∞[1,+∞]，范数就是通常的最大值范数：||x ||∞=
，
范数就是通常的绝对值求和范数，L 2范数就是通常的欧式范数。如果用
表示内积，那么由Holder 不等式，我们得|
q =1
w , x >|≤||w |q |||x |p |
+，其中
p
是
[1,+∞]
中的一对共轭数。假设一对平行的超平面为：
，那么，两个平面之间的距离为
|b 1-b 2|||w ||q
f 1(x ) =+b 1
与
f 2(x ) =+b 2
d (f 1, f 2) =
特别，如果R n 上赋予的是L 1范数，则
d (f 1, f 2) =
|b 1-b 2|||w ||∞
于是，导出相应的优化问题
⎧⎪m in {w , b }m a x j |w j |⎨⎪⎩s . t . y i (+b ) ≥1,
i =1, 2,..., l
于是得到线性规划：
⎧m in a ⎪
⎨s . t . y i (+b ) ≥1, i =1, 2,..., l ⎪n a ≥w j , a ≥-w j , j =1, 2,..., l , a , b ∈R , w ∈R ⎩
简化了计算。同理，对于不可分离的情况，引入松弛变量后可得
⎧⎧m in ⎨a +C ⎪
⎩⎪⎪⎨s . t .
l
∑
i =1
ξi ⎬
⎭
⎫
⎪y (+b ) ≥1-ξ, i =1, 2,..., l i i i ⎪
n
⎪a ≥w j , a ≥-w j , ξj ≥0, j =1, 2,..., l , a , b ∈R , w ∈R ⎩
同理，对于非线性分类的情况，换成核函数
l
⎧⎧⎫m in a +C ξ⎨∑i ⎬⎪
i =1⎩⎭⎪
⎪s . t . ⎪⎨
⎛l ⎫⎪y αy K (x , x ) +b ⎪≥1-ξi , i =1, 2,..., l i ∑j j j i ⎪
⎝j =1⎭⎪
n
a ≥αj , a ≥-αj , ξj ≥0, j =1, 2,..., l , a , b ∈R , w ∈R ⎪⎩
同样也采用L ∞范数，此时相应的优化问题为
n ⎧⎧⎫m in a ⎨∑i ⎬⎪
⎩i =1⎭⎪⎪⎨s . t .
⎪y (+b ) ≥1, i =1, 2,..., l i i ⎪
n
⎪a j ≥w j , a j ≥-w j , ξj ≥0, j =1, 2,..., n , a , b ∈R , w ∈R ⎩
而非线性问题的松弛条件下的优化问题为：
n l
⎧⎧⎫m in a +C ξ⎨∑i ∑i ⎬⎪
i =1i =1⎩⎭⎪
⎪s . t . ⎪⎨
⎛l ⎫⎪y αy K (x , x ) +b ⎪≥1-ξi , i =1, 2,..., l i ∑j j j i ⎪
⎝j =1⎭⎪
n
a ≥αj , a j ≥-αj , ξj ≥0, j =1, 2,..., l , a , b ∈R , w ∈R ⎪⎩j
无论是那种，都简化了运算。但是由此会付出多大的代价呢？如果记S V M 1，
S V M
2
，S V M ∞分别为基于上述相应范数得出的支持向量机，我们留作习题，请
大家自己选择一个样本数据库，然后基于该库中数据，对三种在时间复杂度，精
度，鲁棒性进行比较，也即填写如下表格：
小节
SVM 的程序会很多，基于不同范数得到不同计算复杂度的程序。选择不同的核函数计算复杂度也会有区别；核函数的选取有研究价值，但难度大。目前见到的核函数对于精度的影响从某种意义上讲是“不大”。但我们已经从个案中发现，有时差异很大，于是，最优核函数的存在性问题值得深入讨论。
SVM 的用途很多，可以取代神经网络的角色（支持向量回归SVR ）；可以求有界集的“最小体积”（一分类问题）；多分类问题。其它的应用还在探索中，与随机图，与粗糙集的结合也已经有人在做，我已经审阅过的期刊论文就是这样。
3．支持向量机（回归）
3.1.1 支持向量机
支持向量机（SVM ）是美国Vapnik 教授于1990年代提出的，2000年代后成为了很受欢迎的机器学习方法。它将输入样本集合变换到高维空间使得其分离性状况得到改善。它的结构酷似三层感知器，是构造分类规则的通用方法。SVM 方法的贡献在于，它使得人们可以在非常高维的空间中构造出好的分类规则，为分类算法提供了统一的理论框架。作为副产品，SVM 从理论上解释了多层感知器的隐蔽层数目和隐节点数目的作用，因此，将神经网络的学习算法纳入了核技巧范畴。
所谓核技巧，就是找一个核函数K (x , y ) 使其满足K (x , y ) =(φ(x ), φ(y )) ，代
替在特征空间中内积（φ(x ), φ(y )) 的计算。因为对于非线性分类，一般是先找一个非线性映射φ将输入数据映射到高维特征空间，使之分离性状况得到很大改观，此时在该特征空间中进行分类，然后再返会原空间，就得到了原输入空间的非线性分类。由于内积运算量相当大，核技巧就是为了降低计算量而生的。
特别， 对特征空间H 为Hilbert 空间的情形，设K (x , y ) 是定义在输入空间
R
n
上的二元函数，设H 中的规范正交基为φ1(x ), φ2(x ),..., φn (x ),
... 。如果
∞
K (x , y ) =
∑
k =1
a k (φk (x ), φk (y )),
2
{a k }∈l
2
，
∞
那么取φ(x ) =∑
k =1
a k φk (x )
即为所求的非线性嵌入映射。由于核函数K (x , y ) 的定义
域是原来的输入空间，而不是高维的特征空间。因此，巧妙地避开了计算高维内
（φ(x ), φ(y )) 所需付出的计算代价。实际计算中，我们只要选定一个K (x , y ) ，积
∞
并不去重构嵌入映射φ(x )
=
∑
k =1
a k φk (x )
。所以寻找核函数K (x , y ) （对称且非负）
就是主要任务了。满足以上条件的核函数很多，例如
● 可以取为d-阶多项式：K (x , y )
=(1+x y )
d
，其中y 为固定元素。
● 可以取为径向函数：K (x , y )
=ex p (||x -y ||/σ
2
2
)，其中y 为固定元素。
● 可以取为神经网络惯用的核函数：K (x , y ) =
定元素。
tan h (c 1(x y ) +c 2)
，其中y 为固
一般地，核函数的存在性只依赖于如何寻找一个平方收敛的非负序列{a k }。这样的序列在l 2空间的正锥l 2+
=
{{a }∈l
k
2
|a k ≥0, ∀k }
中的序列都满足。但哪一个最
佳还有待于进一步讨论。经验表明，分类问题对于核函数不太敏感。当然，重新构造一个核函数也不是一个简单的事。因此，实际操作中往往就在上述三类中挑出一个来使用就可以了。
支持向量机的结构示意图可以表示如下：
图1 支持向量机结构示意图
其中输入层是为了存贮输入数据，并不作任何加工运算；中间层是通过对样本集的学习，选择K (x , x i ),
i =1, 2, 3,..., L
；最后一层就是构造分类函数
L
y =s g n (∑y i a i K (x , x i ) +b )
i =1
整个过程等价于在特征空间中构造一个最优超平面。
支持向量机的作用之一就是分类。根据分类的任务，可以划分为一分类，二分类以及多分类。对于多类分类问题，可以用若干种手法将其分解为若干个二分类问题叠加。因此，为了实现支持向量机分类的算法，我们只要针对二分类，从头来给出它的数学原理。
3.1.2 支持向量机分类的数学原理
设样本集为{(x i , y i ) |x i ∈R ; y i ∈{-1, +1}, i =1,..., I }
n
，我们的目的是寻找一个最优
超平面H 使得标签为＋1 和－1的两类点不仅分开且分得间隔最大。
当在n 维欧几里德空间中就可以实现线性分离时，也即存在超平面将样本集
按照标签－1与＋1分在两边。由于超平面在n 维欧几里德空间中的数学表达
式是一个线性方程
w , x >+b =0
，其中，w 为系数向量，x 为n 维变量，
x i
内积，
|i
|w |
b
为常数。空间中点
+b |
到超平面
12||w ||
2
L
的距离
d (x , L =) i
||
。欲使得d (x i , H ) 最大，等价于
最小。于是，
得到一个在约束条件下的极值问题
1⎧2
m in ||w ||⎪
2⎨
⎪y (+b ) ≥1,
i ⎩i
i =1, 2,..., I
引入Lagrange 乘子α
=(α1, α2,..., αI )
，可以解得关于该参变量的方程
I I
i
Q (α) =
∑α
i =1
-
12
∑
i , j =1
αi αj y i y j
称之为Lagrange 对偶函数。其约束条件为
I
∑
i , j =1
αi y i =0, αi ≥0, i =1, 2,..., I
在此约束条件之下， 使得Q (α) 达到最大值的α的许多分量为0，不为0的αi 所对应的样本x i 就称为支持向量。这就是支持向量的来历。
当在输入空间不能实现线性分离，假设我们找到了非线性映射φ将样本集
{(x
i
, y i ) |x i ∈R ; y i ∈{-1, +1}, i =1,..., I }
n
n
映射到高维特征空间H 中，此时我们
考虑在H 中的集合{(φ(x i ), y i ) |x i ∈R ; y i ∈{-1, +1}, i =1,..., I }的线性分类，即
在H 中构造超平面，其权系数w 满足类似的极值问题。由于允许部分点可以例外，那么可以引入松弛项，即改写为：
1⎧2
m in ||w ||+C ∑ξi ⎪
2⎨i =1
⎪y (+b ) ≥1-ξ,
i i ⎩i
L
ξi ≥0, i =1, 2,..., I
最终转化为一个二次型在约束条件下的二次规划问题：
1' ⎧'
m in αD α+c α⎪α
2⎨
⎪y ' α=0, 0≤α=(α,..., α) T ≤A =(C ,..., C ) T ⎩1I
其中，y
=(y 1,..., y I )
T
，c
=(-1,..., -1)
T
，D
=
(K (x , x
i
j
) y i y j
)
1≤i , j ≤I
为矩阵。K (x , s )
是核函数。
一分类问题是一个极端情形但却又是非常有用的，它可以表示为如下数学模型：设{x i
|x i ∈R , i =1,..., I }
n
为空间R n 的有限观测点，找一个以a 为心，以R 为半径
的包含这些点的最小球体。因此，一分类是对于求一个化合物成分的最小包络曲面的最佳方法。与前面完全相同的手法，设φ是由某个核函数K (x , s ) 导出的从输入空间到特征空间中的嵌入映射，最后可以得到二次规划问题
1' ⎧'
m in αD α+c α⎪α
2⎨
⎪y ' α=0, 0≤α=(α,..., α) T ≤A =(C ,..., C ) T ⎩1I
其中，y
=(y 1,..., y I )
T
， c
=(-1,..., -1)
T
， D
=
(K (x , x
i
j
) y i y j
)
1≤i , j ≤I
为矩阵。K (x , s )
是核函数。此时
L L L
i
f (x ) =K (x , x ) -2∑αi K (x , x i ) +
i =1
∑∑α
j =1
i =1
αj K (x i , x j )
此时几乎所有的点满足为：1/L
f (x ) ≤R
2
。参数C 起着控制落在球外点的数目, 变化区间
3.1.3基于线性规划的SVM 分类
由于分类问题的自然推理过程都会归结到二次规划求解，计算复杂度相对较高。
如果能将其简化为线性规划而且没有较大的误差， 那么计算量将急速减少。于是提出了基于线性规划的SVM 分类。此方法经过数学严格推理，是合理的（因为涉及泛函的知识较多，推理过程放在附录中）。因此产生了基于线性规划一分类、二分类、多分类。此处，我们仅给出基于线性规划的SVM 分类的最终形式：
⎧⎛m in ⎪ -ρ+C
⎝⎪⎪⎨s . t
L
∑
i =1
ξi ⎪
⎭
⎫
L
⎪L
⎪∑αi K (x i , x j ) ≥ρ-ξj , j =1,..., L ; ⎪⎩i =1
∑α
i =1
i
=1; αi , ξi ≥0
L
解出α与ρ则得出决策函数件
f (x ) =
∑α
i =1
i
K (x i , x j )
以及阈值。参数C 控制着满足条
f (x ) ≥ρ
的样本数量。特别核函数取为径向函数时，参数σ2越小，精度越高。
另外，要提醒注意的是，在求解大规模分类问题得SVM 算法实现时，需要以下辅
助手段：
停机准则：由于分类问题等价于求对偶问题在约束条件下的极值
⎧
⎪m a x ∑αi -∑∑αi αj y i y j K (x i , x j )
i =1i =1j =1⎪
⎨L ⎪s . t .
∑αi y i =0, 0≤αi ≤C , i =1, 2,..., L ⎪j =1⎩
L
L
L
而KKT 条件
⎧αi [y i (+b ) -1+ξi ]=0
⎨
⎩(C -αi ) ξi =0, i =1, 2,..., L
是收敛的充分必要条件。 因此通过监控KKT 条件来得到停机条件
⎧
⎪∑αi y i =0, 0≤αi ≤C , i =1, 2,..., L ⎪j =1⎪
⎧≥1, αi =0, ∀i ⎨L
⎪⎪
y i (∑αi y i K (x i , x j ) +b ) ⎨=1, 0
L
这个条件中的不等式不必严格成立，只要在一定误差条件下成立就可以用了。
选块算法＋分解法
1. 给定参数M
>0
，ε
>0
，
k =0
。 选取初始工作集W 0
⊂T
，记其对应的样
本点的下标集为J 0。令W k 集为J k 。 2. 基于工作集W k
⊂T
⊂T
第k 次更新的工作集，其对应的样本点的下标
， 由优化问题
⎧
⎪m a x ∑αi -∑∑αi αj y i y j K (x i , x j )
i =1i =1j =1⎪
⎨L ⎪s . t .
∑αi y i =0, 0≤αi ≤C , i ∈J k
⎪j =1⎩
L
L
L
ˆj , 求出最优解{a j ∈J k }，构造 α
k
=(α1,..., αL )
k k
按照如下方式：
α
k j
ˆj , ⎧⎪α=⎨⎪⎩0,
k
j ∈J k j ∉J k
3. 如果αk 已经在精度ε内满足停机准则，那么以此权系数构造决策函数即可。
否则继续下一步。 4. 在T
\W k
中找出M 个最严重破坏条件
⎧≥1,
⎪
y i (∑αi y i K (x i , x j ) +b ) ⎨=1,
j =1⎪
⎩≤1,
L
αi =0, ∀i
0
αi =C , ∀i
加入W k 得出新的工作集W k +1，相应的下标集记为J k +1。 5． 重复2）－3），直到样本集耗完为止。
序列最小优化算法（SMO ） Input: the observed dataset
ε>0
S ={(x 1, y 1),..., (x l , y l ) |x i ∈R , y j ∈R }
n
, 输入精度要求
及指定核函数K (x , y ) ，初始化α0
=0
，k
=0
。
Output: the classification of these samples Step1. 由更新公式
α2α1
k +1
=α2+
k
k
y (E -E )
k
k +1
k +1
=α1+y 1y 2(α2-α2
)
Step2. 如果第k 步时达到停机要求，取近似解αˆ
停机为止，取为近似解。
=α
k
，否则继续迭代，直到满足
3.2 支持向量回归（SVR ）模型
对于分类，支持向量机相当于导师样本为有限集的情形。考虑导师集合为不可数的情形，例如训练集可以为形如
S ={(x 1, y 1),..., (x l , y l ) |x i ∈R , y j ∈R }
n
的情形，则演化出支持向量回归概念。
支持向量回归也分为线性回归和非线性回归两种，但不是统计学中的线性或者非线性回归了，而是根据是否需要嵌入到高维空间来划分的，我们简述如下：
● 对于给定的样本集S , 以及任意给定的ε
面称
f (x ) =+b ,
w ∈R , b ∈R
n
>0
，如果在原始空间R n 存在超平
∀(x i , y i ) ∈S
使得 |
y i -f (x i ) |≤ε,
，则
f (x ) =+b
是样本集合S 的ε－线性回归。
∀(x i , y i ) ∈S
与初等代数类似，|平面
y i -f (x i ) |≤ε,
等价于S 中任何点(x i ,
y i )
到超
f (x ) =+
b 。由于我们是分类，所以希望距离都尽可能大。也即使得
调整超平面的斜率w 使得与S 中任点(x i ,
y
i )
最大化，这等价于要求m in {||w ||2}。于是，ε－线性回归问题转化
为优化问题：
⎧⎪m in ⎨⎪⎩s . t .
1
2
||w ||
2
|+b -y i |≤ε, i =1, 2,..., l
于是，引入松弛变量，并使用Lagrange 乘子法，得到优化问题的对偶形式：
l
⎧⎧1l
***
⎪m in ⎨-∑(αi -αi )(αj -αj ) +∑(αi -αi ) y i -⎪i =1⎩2i , j =1⎨
l
**⎪
s . t . (αi -αi ) =0, 0≤αi , αi ≤C , i =1, 2,..., l ∑⎪⎩
i =1
l
∑
i =1
(αi +αi ) ε⎬
*
⎫⎭
● 对于不可能在原始空间R n 就可以线性分离的样本集S ，先用一个非线性映射
φ
将数据S 映射到一个高维特征空间中，使得φ(S ) 在特征空间H 中具有很好
的线性回归特征，先在该特征空间中进行线性回归，然后返回到原始空间R n 中。这就是支持向量非线性回归。
于是，支持向量非线性回归的对偶优化问题如下：
l
⎧⎧1l
***
⎪m in ⎨-∑(αi -αi )(αj -αj ) +∑(αi -αi ) y i -⎪i =1⎩2i , j =1⎨
l
**⎪
s . t . (αi -αi ) =0, 0≤αi , αi ≤C , i =1, 2,..., l ∑⎪⎩
i =1
l
∑
i =1
(αi +αi ) ε⎬
*
⎫⎭
于是，非线性回归问题的实施步骤为：
1．寻找一个核函数K (s , t ) 使得K (x i , x j )
=
，
2．求优化问题
l
⎧⎧1l
***
⎪m in ⎨-∑(αi -αi )(αj -αj ) K (x i , x j ) +∑(αi -αi ) y i -⎪i =1⎩2i , j =1
⎨
l
**⎪
s . t . (αi -αi ) =0, 0≤αi , αi ≤C , i =1, 2,..., l ∑⎪⎩
i =1
l
∑
i =1
(αi +αi ) ε⎬
*
⎫⎭
的解α
3． 计算
i
, αi
*
。
⎧
y +ε-⎪j ⎪b =⎨
⎪y -ε-
j ⎪⎩
l
∑
i , j =1l
(αi -αi ) K (x j , x i ),
*
当
αi ∈（0，C )
(αi -αi ) K (x j , x i ),
*
∑
i , j =1
当
αi ∈（0，C )
*
4．构造非线性函数
l
f (x ) =
∑
i =1
(αi -αi ) K (x j , x ) +b ,
*
x i ∈R , b ∈R
n
。
3.2.2支持向量机分类与支持向量回归的关系
支持向量机用以分类和回归，两者到底是什么关系？为了建立回归与分类的关系，我们在特征空间中考虑如下的上下移动集合：
D
+
={((φ(x i ), y i +ε+1) |(x i , y i ) ∈S }，D
-
={((φ(x i ), y i -ε-1) |(x i , y i ) ∈S }
对于充分大的ε，D +与D -是线性可分离的。于是得出关于D +与D -分类。引入松弛变量ξ，由SVM 分类方法得到
1⎧2
ˆ||+C ∑ξi m in ||w ⎪
2i =1⎨⎪ˆ, z i >+b ) -ξi ≤-1, ⎩s . t .
ˆˆ改写为w 将目标函数中的w
L
ˆ, z i >+b ) +ξi ≥1, z i ∈D ,
ˆ2 特别令w
L
+
z i ∈D , ξi ≥0, i =1, 2,..., l
-
=-1
, 那么上式变成
1⎧2
ˆ1||+1m in ||w +C ∑ξi
2⎪
2i =1
⎪⎪
ˆ1, φ(x i ) >-y i -ε-1+b -ξi ≤-1, ⎨s . t .
⎪⎪⎩
ˆ1, φ(x i ) >-y i +ε+1+b +ξi ≤1,
ξi ≥0, i =1, 2,..., l
而基于观测集S
={(x 1, y 1),..., (x l , y l ) |x i ∈R , y j ∈R }
n
，在特征空间中寻找单参数约
束下的回归函数
f (x ) =+b
的问题等价于
L
1⎧2
m in ||w ||+C ∑ξi ⎪
2i =1
⎪⎪
⎨s . t . y i --b ≤ξi +ε, ⎪⎪⎪⎩
-y i +b ≤ξi +ε,
ξi ≥0, i =1, 2,..., l
也就是说，回归问题可以通过分类的算法来实现。
附录：基于线性规划的分类的合理性
设输入向量的空间为R n ， 记L p (R n ), 1≤
g
p ≤∞,
为R n 上一切p －绝对值可积函数），按照通常的加法和数乘，构成
（即 一切可测且满足⎰
R
n
|g (x ) |d μ(x )
p
的线性空间。一般地，我们偏好选则一个非线性映射φ将R n 嵌入到L 2(R n ) 空间。因为在该Hilbert 空间中，任意闭子空间的正交补子空间存在问题是一个已解决了的问题，而在L p (R n ),
p ≠2,
还是一个没有被完全解决的问题。如前所述，在此
空间中得到的结果，特别是诱导出的核函数是一个非常好的亮点。
在有限维空间中，任何距离都是等价的。这一特征也是有限维空间独有的。类似于上面所述，我们可以在有限维空间R n 上赋予L p 范数：
⎛p ⎫
||x ||p = ∑|x i |⎪
⎝i =1⎭
n
1p
m a x 1≤i ≤n |x i |
p L 1
取遍区间
特别，L ∞[1,+∞]，范数就是通常的最大值范数：||x ||∞=
，
范数就是通常的绝对值求和范数，L 2范数就是通常的欧式范数。如果用
表示内积，那么由Holder 不等式，我们得|
q =1
w , x >|≤||w |q |||x |p |
+，其中
p
是
[1,+∞]
中的一对共轭数。假设一对平行的超平面为：
，那么，两个平面之间的距离为
|b 1-b 2|||w ||q
f 1(x ) =+b 1
与
f 2(x ) =+b 2
d (f 1, f 2) =
特别，如果R n 上赋予的是L 1范数，则
d (f 1, f 2) =
|b 1-b 2|||w ||∞
于是，导出相应的优化问题
⎧⎪m in {w , b }m a x j |w j |⎨⎪⎩s . t . y i (+b ) ≥1,
i =1, 2,..., l
于是得到线性规划：
⎧m in a ⎪
⎨s . t . y i (+b ) ≥1, i =1, 2,..., l ⎪n a ≥w j , a ≥-w j , j =1, 2,..., l , a , b ∈R , w ∈R ⎩
简化了计算。同理，对于不可分离的情况，引入松弛变量后可得
⎧⎧m in ⎨a +C ⎪
⎩⎪⎪⎨s . t .
l
∑
i =1
ξi ⎬
⎭
⎫
⎪y (+b ) ≥1-ξ, i =1, 2,..., l i i i ⎪
n
⎪a ≥w j , a ≥-w j , ξj ≥0, j =1, 2,..., l , a , b ∈R , w ∈R ⎩
同理，对于非线性分类的情况，换成核函数
l
⎧⎧⎫m in a +C ξ⎨∑i ⎬⎪
i =1⎩⎭⎪
⎪s . t . ⎪⎨
⎛l ⎫⎪y αy K (x , x ) +b ⎪≥1-ξi , i =1, 2,..., l i ∑j j j i ⎪
⎝j =1⎭⎪
n
a ≥αj , a ≥-αj , ξj ≥0, j =1, 2,..., l , a , b ∈R , w ∈R ⎪⎩
同样也采用L ∞范数，此时相应的优化问题为
n ⎧⎧⎫m in a ⎨∑i ⎬⎪
⎩i =1⎭⎪⎪⎨s . t .
⎪y (+b ) ≥1, i =1, 2,..., l i i ⎪
n
⎪a j ≥w j , a j ≥-w j , ξj ≥0, j =1, 2,..., n , a , b ∈R , w ∈R ⎩
而非线性问题的松弛条件下的优化问题为：
n l
⎧⎧⎫m in a +C ξ⎨∑i ∑i ⎬⎪
i =1i =1⎩⎭⎪
⎪s . t . ⎪⎨
⎛l ⎫⎪y αy K (x , x ) +b ⎪≥1-ξi , i =1, 2,..., l i ∑j j j i ⎪
⎝j =1⎭⎪
n
a ≥αj , a j ≥-αj , ξj ≥0, j =1, 2,..., l , a , b ∈R , w ∈R ⎪⎩j
无论是那种，都简化了运算。但是由此会付出多大的代价呢？如果记S V M 1，
S V M
2
，S V M ∞分别为基于上述相应范数得出的支持向量机，我们留作习题，请
大家自己选择一个样本数据库，然后基于该库中数据，对三种在时间复杂度，精
度，鲁棒性进行比较，也即填写如下表格：
小节
SVM 的程序会很多，基于不同范数得到不同计算复杂度的程序。选择不同的核函数计算复杂度也会有区别；核函数的选取有研究价值，但难度大。目前见到的核函数对于精度的影响从某种意义上讲是“不大”。但我们已经从个案中发现，有时差异很大，于是，最优核函数的存在性问题值得深入讨论。
SVM 的用途很多，可以取代神经网络的角色（支持向量回归SVR ）；可以求有界集的“最小体积”（一分类问题）；多分类问题。其它的应用还在探索中，与随机图，与粗糙集的结合也已经有人在做，我已经审阅过的期刊论文就是这样。