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 是定义在输入空间
n
R
上的二元函数，设H 中的规范正交基为12(),(),...,(),
...n x x x φφφ。如果
2
2
1
(,)((),()),
{}k k k k k K x y a x y a l
φφ∞
==
∈∑
，
那么取1
()()
k k k x a x φφ∞
==∑
即为所求的非线性嵌入映射。由于核函数(,)K x y 的定义
域是原来的输入空间，而不是高维的特征空间。因此，巧妙地避开了计算高维内
积
(),())x y φφ（所需付出的计算代价。实际计算中，我们只要选定一个(,)K x y ，
并不去重构嵌入映射1
()
()
k k k x a x φφ∞
==
∑
。所以寻找核函数(,)K x y （对称且非负）
就是主要任务了。满足以上条件的核函数很多，例如
● 可以取为d-阶多项式：(,)
(1)
d
K x y x y =+ ，其中y 为固定元素。
● 可以取为径向函数：()2
2
(,)
ex p ||||/K x y x y σ
=-，其中y 为固定元素。
● 可以取为神经网络惯用的核函数：()
12(,)tan h ()K x y c x y c =
+ ，其中y 为固
定元素。
一般地，核函数的存在性只依赖于如何寻找一个平方收敛的非负序列{}k a 。这样的序列在2l 空间的正锥{}{}
22
|0,k
k l a l
a k +
=
∈≥∀中的序列都满足。但哪一个最
佳还有待于进一步讨论。经验表明，分类问题对于核函数不太敏感。当然，重新构造一个核函数也不是一个简单的事。因此，实际操作中往往就在上述三类中挑出一个来使用就可以了。
支持向量机的结构示意图可以表示如下：
图1 支持向量机结构示意图
其中输入层是为了存贮输入数据，并不作任何加工运算；中间层是通过对样本集的学习，选择(,),
1,2,3,...,i K x x i L
=；最后一层就是构造分类函数
1
s g n ((,))
L
i i i i y y a K x x b ==+∑
整个过程等价于在特征空间中构造一个最优超平面。
支持向量机的作用之一就是分类。根据分类的任务，可以划分为一分类，二分类以及多分类。对于多类分类问题，可以用若干种手法将其分解为若干个二分类问题叠加。因此，为了实现支持向量机分类的算法，我们只要针对二分类，从头来给出它的数学原理。
3.1.2 支持向量机分类的数学原理
设样本集为{}{}
(,)|;1,1,1,...,n
i i i i x y x R y i I ∈∈-+=，我们的目的是寻找一个最优
超平面H 使得标签为＋1 和－1的两类点不仅分开且分得间隔最大。
当在n 维欧几里德空间中就可以实现线性分离时，也即存在超平面将样本集
按照标签－1与＋1分在两边。由于超平面在n 维欧几里德空间中的数学表达
式是一个线性方程 ,0
w x b <
>+=，其中，w 为系数向量，x 为n 维变量，
,w x <>
内积，
b
为常数。空间中点
i
x 到超平面
L
的距离
|,|
(,)||
||
i
i
w x b d x L w <>+=。欲使得(,)i d x H 最大，等价于
2
1||||
2w 最小。于是，
得到一个在约束条件下的极值问题
2
1m in ||||2(,)1,
1,2,...,i
i w y w x b i I
⎧⎪
⎨
⎪<>+≥=⎩
引入Lagrange 乘子12(,,...,)
I α
ααα=，可以解得关于该参变量的方程
12
1
,1
(),I I
i
i j i j i j i i j Q y y x x αα
αα===
-
<>
∑∑
称之为Lagrange 对偶函数。其约束条件为
,1
0,0,1,2,...,I
i i i i j y i I
αα==≥=∑
在此约束条件之下， 使得()Q α达到最大值的α的许多分量为0，不为0的i α 所对应的样本i x 就称为支持向量。这就是支持向量的来历。
当在输入空间不能实现线性分离，假设我们找到了非线性映射φ将样本集
{}{}
(,)|;1,1,1,...,n
i
i i i x
y x R y i I ∈∈-+=映射到高维特征空间H 中，此时我们
考虑在H 中的集合{}{}((),)|;1,1,1,...,n
i i i i x y x R y i I φ∈∈-+=的线性分类，即
在H 中构造超平面，其权系数w 满足类似的极值问题。由于允许部分点可以例外，那么可以引入松弛项，即改写为：
2
1
1m in ||||2(,)1,
0,1,2,...,L
i i i
i i i w C y w x b i I
ξξξ=⎧+⎪
⎨⎪<>+≥-≥=⎩∑
最终转化为一个二次型在约束条件下的二次规划问题：
''
'11m in 20,0(,...,)(,...,)T T I
D c y A C C α
ααααααα⎧+⎪⎨
⎪=≤=≤=⎩
其中，1(,...,)
T
I y
y y =，(1, (1)
T
c
=--，()
1,(,)i
j
i j
i j I
D
K x x
y y ≤≤=
为矩阵。(,)K x s
是核函数。
