http://www.ma-xy.com
目录
第一章 基本支持向量机 1
1.1 支持向量机简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 支持向量机的引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 凸二次规划介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 凸集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.3
凸函数
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.4 凸规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 支持向量机的求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 为什么要讲凸规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 拉格朗日对偶解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.3 支持向量机对偶问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.4 KKT 条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 容错支持向量机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 核技术的引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 SVM 解决 xor 问题的小例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1
http://www.ma-xy.com
第一章 基本支持向量机
1.1 支持向量机简介
支持向量机 (Support Vector Machine，SVM) 由 Corinna Cortes 和 Vapnik 等人于 1995 年
首先提出，最初被用于解决二分类问题。它在解决小样本、非线性及高维模式识别中表现出许多
特有的优势，被广泛的应用于各种机器学习问题当中。
1.2 支持向量机的引入
考虑这样一个二分类问题：特征变量 (输入变量) 是二维的，且总体类型只有两类，类别标
签为 (−1, +1)，其数据如表 (1.1) 所示
表 1.1: 模拟数据
data x
1
x
2
y
1 2 2 1
2 3 1 1
3 2 0 -1
.
.
.
.
.
.
.
.
.
.
.
.
m · · ·
我们用 X = (x
1
, x
2
) ⊂ R
2
表示特征空间，y 为样本类别，y 的具体取值为标签值，例如: 第 k
个样本的标签值为 y
k
= 1。事实上，样本类别与样本的标签值无关，即 (-1,+1) 可以改为 (0,+1)，
这并不影响类的本质，值得一提的是：后面介绍的某些方法 (如 SVM，logistics regression 等)，
其建模方法是依赖于标签值的。假设共有 m 个样本，用 x
k
(k = 1, 2, ..., m) 表示第 k 个样本的特
征值，x
k
∈ R
2
，例如：第一个样本的特征值写为 x
1
= (3, 2)。我们可以将整个数据放在集合中，
记为 S = {x
k
, y
k
}
m
k=1
。现在的问题是：找一个分类器 y = f(x)，使它能够很好的将样本分开，并
且由它得到的错误率等指标又可以接受。
我们用一个图形来表示上面的问题，如图 (1.1) 所示
1
http://www.ma-xy.com
1.2 支持向量机的引入 第一章 基本支持向量机
图 1.1: 二分类问题示意图
假设样本是线性可分的，我们用 ⊕ 来表示 y = +1，用 ⊖ 来表示 y = −1，每个样本即为图中的
一个点，那么这个二分类问题就变为如何找到一条分割线 (这里仅考虑直线)，将 ⊕ 和 ⊖ 分割开。
在这个 x
1
Ox
2
平面直角坐标系中，任意一条直线将表示成 x
2
= ax
1
+b，也即 w
1
x
1
+w
2
x
2
+b = 0
，从直线表达式可以看出，只要确定了直线中的参数 (w, b)，直线也就确定了。所以，现在我们
要思考的问题是：我们依据什么样的准则来确定直线参数？这里我们提出以下几种准则:
1. 在参数 (w, b) 的空间 Θ 中，取 w, b 使得两个群体点到直线的平均距离最大。
2. 在 w, b ∈ Θ 空间中，取 w, b 使得两个群体到直线的平均距离最大。
3. 在 w, b ∈ Θ 空间中，取 w, b 使得两个群体的中点到直线的距离最大。
4. 在 w, b ∈ Θ 空间中，取 w, b 使得两个群体距离直线最近的点的距离最大。
当然，还有其它一些准则可以使用，我们姑且记准则集合为 $。为了求直线，我们需要知道
点到直线的距离，对平面上的某点 x
k
= (x
k
1
, x
k
2
)，其到直线 w
1
x
1
+ w
2
x
2
+ b = 0 的距离 d 为
d =
|w
1
x
k
1
+ w
2
x
k
2
+ b|
∥w∥
=
|w
1
x
k
1
+ w
2
x
k
2
+ b|
w
2
1
+ w
2
2
其中：∥w∥ 为 w = (w
1
, w
2
) 的 L
2
范数。并且如果 w
1
x
k
1
+ w
2
x
k
2
+ b > 0，则数据点 x
k
位于直线
上方；如果 w
1
x
k
1
+ w
2
x
k
2
+ b < 0，则数据点位于直线下方。平面上一条直线将平面分为两部分
(y = ±1)。
下面，我们在支持向量机的准则 $
SV M
下求解分类线 f(分类器)。支持向量机的准则 $
SV M
是：求直线 f ，y = ±1 位于直线的两侧，并且距离直线的最近的两类数据点的距离最大。没错，
这也就是上面的准则 4，我们用图形来展示这一准则，如图 (1.2) 所示
图 1.2: SVM 分类准则示意图
图 (1.2) 中，我们通过平移直线 f
2
到 f
1
的位置，使得原本 f
2
的最小距离 d
min
尽可能大。
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.2 支持向量机的引入
为了书写方便，我们将第 i 个样本 x
i
写为 x
i
，记 x
i
到直线 f
1
的距离为
r
i
=
|w
T
x
i
+ b|
||w||
我们的目标是寻找 w, b(下面的 w 省略粗写)，使得 max inf{r
i
}
m
i=1
，也即使得两类样本点中
距离直线 f
1
最近的点的距离最大，记最小距离为 d。一定要注意的是 y = ±1 要位于直线的两
侧。现在，我们可以写出下面的优化模型
max
w,b
d
s.t.
|w
T
x
i
+ b|
||w||
⩾ d
∀i, j(i, j ∈ m)y
i
= 1, y
j
= −1, 有 (w
T
x
i
+ b)(w
T
x
j
+ b) < 0
上面的第二个约束是指：两类样本位于直线的两侧。我们将上面模型中的绝对值 | · | 去掉，
同时处理约束 s.t.，可将模型转化为下面相等的优化问题
max
w,b
d
s.t.
y
i
(w
T
x
i
+ b)
||w||
⩾ d
i = 1, 2, . . . , m
其中：d = inf{r
i
}
m
i=1
=
|w
T
x
∗
i
+b|
||w||
，x
∗
i
为距离最小的样本，即支撑向量 (支持向量)。
于是，最优化问题变为
max
w,b
|w
T
x
∗
i
+ b|
||w||
s.t. y
i
(w
T
x
i
+ b) ⩾ |w
T
x
∗
i
+ b| = y
∗
i
(w
T
x
∗
i
+ b)
由于平面上距离的相对性，例如只有 3 个距离：
d
1
d
2
=
|w
T
x
1
+b|
|w
T
x
2
+b|
，如图 (1.3) 所示
图 1.3: 距离相对性的示意图
不妨设 |w
T
x
1
+ b| 为元距离1 (单位距离 or 最小距离)。于是，原优化问题变为
max
w,b
1
||w||
s.t. y
i
(w
T
x
i
+ b) ⩾ 1
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.3 凸二次规划介绍 第一章 基本支持向量机
注意：1、满足 (w
T
x
i
+ b) = 1 的 x
i
即为支持向量，换句话说，支持向量记为最小距离点。2、支
持向量必然是 y = ±1 皆有的，并且支持向量数目要大于等于 2(未讨论)，因为在平移直线的过
程中，必然会接触另一边的点才能停止。3、解的唯一性？
下面，我们来求解这一优化问题。按照常规的思路，用 Lagrange 对偶解法进行求解。观察
上述优化问题的目标函数：
1
||w||
=
1
√
w
2
1
+w
2
2
，要使
1
√
w
2
1
+w
2
2
最大化，也即为
w
2
1
+ w
2
2
最小化。
同时，我们来处理平方
√
·，于是，上述优化问题等价于
min
w,b
1
2
||w||
2
=
1
2
(w
2
1
+ w
2
2
)
s.t. y
i
(w
T
x
i
+ b) ⩾ 1
注：我们在上面的目标中添加了
1
2
，在后面的分析中你可以看到它的作用。上面的问题是一个凸
二次规划问题，下面我们就来着手处理这个凸二次规划问题。
1.3 凸二次规划介绍
上面建立的支持向量机模型最终变为一个凸二次规划问题，下面，我们来看什么是凸集、凸
函数、什么是二次规划、什么是拉格朗日对偶解法。当然，对于上面的凸二次规划问题，我们可
以在原参数空间 w, b ∈ Θ 上进行求解 (后面，我们会给出一些求解二次规划的程序和算法)，不
过，如果在对偶空间 (即拉格朗日乘子 α ∈ A) 上求解，会有更神奇的效果，下面我们来逐步讨
论这个神奇之处。
1.3.1 二次规划
二次规划是指如下的优化问题
max
w
1
2
w
T
Hw + c
T
w
s.t.
Aeq · w = beq
Aw ⩾ b
其中：H 为 n × n 对称矩阵，Aeq, A 为矩阵，w, beq, b 为列向量。
二次规划问题是一类特殊的非线性规划问题。如果 H 为半正定矩阵，则称此二次规划问题
为凸二次规划，非凸二次规划中存在许多驻点，求解困难。常用的用于求解凸二次规划的算法有：
lagrange 法、起作用集法和路径跟踪等，MATLAB 中用 quadprog 函数进行求解。关于二次规
划的具体问题，我们会在后面的章节进行详细说明。
1.3.2 凸集
定义 (凸集) 设 S 是 R
n
中的一个集合，S ⊂ R
n
，如果对 S 中的任意两点 x
1
, x
2
，连接他们的
线段仍属于 S，则 S 为凸集。用数学语言描述为：∀x
1
, x
2
∈ S，∀λ ∈ [0, 1]，有 λx
1
+(1 −λ)x
2
∈ S，
则 S 为凸集。
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.3 凸二次规划介绍
凸集与非凸集的示意图如图 (1.4) 所示
图 1.4: 凸集与非凸集的示意图
1.3.3 凸函数
记得第一次接触凸函数的概念是在《数学分析讲义》刘玉琏一书中看到的，当时引入函数凸
性是为了说明函数单调递增速度的问题 (书上是在一元函数上进行说明的)。他给的例子是：同样
是单调递增的两个函数 y =
√
x 与 y = x
2
(x ∈ [0, ∞)) 的增长方式不同。
定义 (凸函数) 设 f 在开区间 I I ∈ R
1
有定义，对 ∀x
1
, x
2
∈ I 和 ∀λ ∈ (0, 1)，有
f(λx
1
+ (1 −λ)x
2
) ⩽ λf(x
1
) + (1 − λ)f(x
2
)
则称函数 f 为下凸函数。
一维下凸函数示意图如图 (1.5) 所示
图 1.5: 一维下凸函数示意图
几何语言描述为：在 λx
1
+ (1 − λ)x
2
处的函数值不大于 f(x
1
), f(x
2
) 的加权平均 λf (x
1
) +
(1 + λ)f(x
2
)，即任意两点的连线在曲线的下方。若 f 在 I 区间是下凸的，则有 Jenson 不等式：
f(q
1
x
1
+ q
2
x
2
+ ··· + q
n
x
n
) ⩽ q
1
f(x
1
) + q
2
f(x
2
) + ··· + q
n
f(x
n
)
其中：x
i
∈ I，q
i
> 0，且
n
i=1
q
i
= 1。
上面的凸函数是在一维情况下定义的，现在，我们将函数的凸性引入到高维空间。设 S 是
R
n
中的非空凸集，f 是 S 上的实函数，如果 ∀x
1
, x
2
∈ S，∀λ ∈ (0, 1)，有
f
(
λx
1
+ (1
−
λ
)
x
2
)
⩽
λf
(
x
1
) + (1
−
λ
)
f
(
x
2
)
则称函数 f 为 S 上的凸函数。
上面给出了凸函数的定义，我们一般不能根据定义来判断函数是否为凸函数，我们只能根据
凸函数的性质，找到凸函数的充分性、必要性以及充分必要性。
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.4 支持向量机的求解 第一章 基本支持向量机
凸函数的二阶充要条件 S 是 R
n
中的非空开凸集，f 是 S 上二次可微函数，f 为凸函数的充要
条件为：在每一个 x ∈ S 上，Hesse 矩阵是半正定的。
注：函数 f 在 x
∗
的 Hesse 矩阵 (Hessian Matrix) 定义为
H(x
∗
) =
∂
2
f(x
∗
)
∂x
2
1
∂
2
f(x
∗
)
∂x
1
∂x
2
···
∂
2
f(x
∗
)
∂x
1
∂x
n
∂
2
f(x
∗
)
∂x
2
∂x
1
∂
2
f(x
∗
)
∂x
2
2
···
∂
2
f(x
∗
)
∂x
2
∂x
n
.
.
.
.
.
.
.
.
.
.
.
.
∂
2
f(x
∗
)
∂x
n
∂x
1
∂
2
f(x
∗
)
∂x
n
∂x
2
···
∂
2
f(x
∗
)
∂x
2
n
并且，H 正定的充要条件是 H 左上角各阶主子式都大于 0。
凸函数的一阶充要条件 S 是 R
n
中的非空开凸集，f 在 S 上有一阶连续偏导数，f 为凸函数的
充要条件为：∀x
1
, x
2
∈ S，x
1
= x
2
，有
f(x
2
) > f(x
1
) + ∇f(x
1
)
T
(x
2
− x
1
)
1.3.4 凸规划
上面给出了二次规划以及凸函数，下面我们来看凸规划问题 (关于规划问题的详细说明，参
考后面优化章节)。凸规划是一类特殊的优化问题，含约束的非线性规划问题定义如下
min
w∈R
n
f
(
w
)
s.t.
g
i
(w) ⩽ 0 i = 1, 2, . . . , l
h
j
(w) = 0 j = 1, 2, . . . , m
而凸规划是指 g
i
为连续可微的凸函数，h
j
为仿射函数的规划。仿射函数是指可以用矩阵 A
和向量 b 表示成 f(w) = Aw + b 形式的函数，因为仿射矩阵有空的 Hesse 矩阵，因而为凸。对
于前面提到过的二次规划问题，显然，当 H 为半正定时，二次规划为凸二次规划。
1.4 支持向量机的求解
1.4.1 为什么要讲凸规划
在求解优化问题时，我们会运用到各式各样的算法。然而，绝大多数算法可能求解的是局部
最优解，而非全局最优解。那么是否有特殊类型的规划，它的局部最优解等价于全局最优解呢？
后面将提到 KKT 条件 (库恩 - 塔克) 给出了算法迭代的方向：最优解必定满足 KKT，但满足
KKT 的不一定就是最优解 (即最优解仅属于 KKT 的子集)。但是，如果问题是凸规划问题，那
么 KKT 条件与最优解等价 (充要条件)。
凸规划的局部最优解就是全局最优解，且极值点集合为凸集，如果凸规划的目标是严格凸，
又存在极值点，那么极值点唯一。(证明可以参见《支持向量机：理论算法和拓展》P11)
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.4 支持向量机的求解
1.4.2 拉格朗日对偶解法
下面来考虑我们要求解的问题
min
w,b
f(w) =
1
2
||w||
2
=
1
2
(w
2
1
+ w
2
2
) (1.1)
s.t. g
i
(w) = 1 − y
i
(w
T
x
i
+ b) ⩽ 0
上面，我们是在 X = (x
1
, x
2
) ⊂ R
2
上讨论的，一般的，我们可以将 X 扩展到 R
n
(共 n 个
特征变量，m 个样本)，这样，待求的 w 变为 w ∈ R
n
。如果不是学习 SVM，单纯的来看这个模
型，会觉得很像《数学分析》里讲的条件极值问题，我们使用拉格朗日乘数法求解的条件极值问
题。事实上，二者之前只差了一个符号。如果把上面问题的 ⩽ 0 变为 = 0 就可以求解了。回忆
一下拉格朗日乘数法：求
min
w∈R
n
f(w)
s.t. h
j
(
w
) = 0
j = 1, 2, . . . , m
解法为：
1、做拉格朗日辅助函数
L(w, λ) = f(w) + λ
1
h
1
(w) + λ
2
h
2
(w) + ··· + λ
m
h
m
(w)
= f (w) +
m
j=1
λ
j
h
j
(w)
其中：λ
j
, j = 1 , 2, . . . , m 称为拉格朗日乘子。
2、求偏导，令偏导数为 0，求解 w 和参数 λ
∂L
∂w
1
= 0
.
.
.
∂L
∂w
n
= 0
∂L
∂λ
1
= 0
.
.
.
∂L
∂λ
m
= 0
上述求解过程只是针对等式约束的优化问题，并不能用于处理我们的不等式约束。下面，我
们引入广义拉格朗日函数来求解如下一般形式的含不等式约束的优化问题
min
w∈R
n
f(w) (1.2)
s.t.
g
i
(w) ⩽ 0 i = 1, 2, . . . , l
h
j
(w) = 0 j = 1, 2, . . . , m
定义广义拉格朗日函数为
L(w, α, β) = f (w) +
l
i=1
α
i
g
i
(w) +
m
j=1
β
j
h
j
(w)
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.4 支持向量机的求解 第一章 基本支持向量机
在上面的广义拉格朗日函数的基础上，我们来求解原问题 (1.2) 定义参函数 θ(w)(我们经常
用到含参数的函数，在书中，我们都统一写为 f(x|θ) 或者 f (x; θ))
θ(w) = max
α,β
α
i
⩾0
L(α, β|w)
给定某个 w 后，当 g
i
(w) 或者 h
j
(w) = 0 时，可以选取某个 α
i
或者 β
j
，使 α
i
(β
j
) → ∞，
这样可以使 max L(α, β|w) → ∞。而当 g(w), h(w) 满足原约束 s.t. 时，θ (w) = f(w)，即
θ(w) =
f(w) 当 w 满足 s.t.
+∞ 其他
如果我们在此基础上考虑最小化 θ(w)，即 min
w
θ(w)，那么，min
w
θ(w) 应该完全等价于 min
w
f(w)，
因为当 w 不满足 s.t. 时，θ(w) → ∞，这不是最小化 min 所需要的。我们称
min
w
max
α,β
α
i
⩾0
L(α, β|w) (1.3)
为广义拉格朗日函数的极小极大问题。下面，我们来分析一下这个问题：
在 w 空间 w 上，给定具体的某个 w
i
时，在 α, β 空间上寻找 maxL。姑且记其值为 L
i
，于
是，每一个 w
i
都有一个 L
i
，我们找到 min L
i
时的 w
i
即可。我们设最优解为 p
∗
= (α, β, w)，但
是，我们想要求解此问题是不容易的。
我们来定义上面极小极大问题 (1.3) 的对偶问题，可以想象着将其写出来：
max
α,β
α
i
⩾0
min
w
L(w|α, β) (1.4)
没错，就是上面的形式了。我们设置其最优解为 d
∗
= (α, β, w)。我们前面说到，原始的极小
极大问题 (1.3) 是不容易求解的 (你可以用我们的问题进行尝试)，所以，我们给出了其对偶问题
(1.4)，此问题易解 (解法后面讨论)。我们自然希望二者 (1.3)(1.4) 的最优解是相等的，即 d
∗
= p
∗
，
但是，事与愿违，我们来分析一下二者的大小：其实，对于 d
∗
和 p
∗
有如下关系
d
∗
= max
α,β
α
i
⩾0
min
w
L(w|α, β) ⩽ max
α,β
α
i
⩾0
{∀w, L(w|α, β)} ⩽ min
w
max
α,β
L(α, β|w) = p
∗
即对偶问题 (1.4) 给出了原问题 (1.3) 最优解 p
∗
的下界。如果不容易理解，我们可以将参数
α, β 简化为 θ，于是有
max
θ
min
w
L
(
w
|
θ
)
⩽
min
w
max
θ
L
(
θ
|
w
)
上面的关系式是显然成立的，可以用一个二元函数 L(w, θ) 进行示例。其次，从二者的名称
上，我们也可以很容易理解：max min ⩽ min max 是如此自然。也就是说，对于一般的优化问题
(非凸)，d
∗
⩽ p
∗
，但是，值得庆幸的是，对于凸规划而言，有 d
∗
= p
∗
= (α
∗
, β
∗
, w
∗
)，即原问题
与对偶问题的最优解是等价的。
注：max
α,β
α
i
⩾0
min
w
L(w|α, β) 为凸优化问题。
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.4 支持向量机的求解
1.4.3 支持向量机对偶问题
上述拉格朗日对偶解法说明了：对偶问题的最优解在一定条件下可以是原问题的最优解。下
面，我们对支持向量机运用拉格朗日对偶解法。
1、支持向量机的原问题为
min
w,b
f(w) =
1
2
||w||
2
(1.5)
s.t.
g
i
(w) = 1 − y
i
(w
T
x
i
+ b) ⩽ 0
i = 1, 2, . . . , n
注意：这里的样本量由原来的 m 变为了 n。
2、上面优化问题的广义拉格朗日函数为
L(w, b, α) =
1
2
w
T
w −
n
i=1
α
i
[y
i
(w
T
x
i
+ b) −1]
3、广义拉格朗日极小极大问题为
min
w,b
max
α
α
i
⩾0
L(α|w, b)
4、对偶问题 - 极大极小问题为
max
α
α
i
⩾0
min
w,b
L(w, b|α) (1.6)
为了求解 (1.6) 的解 d
∗
，先写 min
w,b
L(w, b|α)，即将 α 视为参数，求 L(w, b) 的最小值。用 L
对 w, b 分别求偏导，并令其为 0，有
∂L
∂w
= 0
∂L
∂b
= 0
or
∇
w
L = 0
∇
b
L = 0
由上式推得
w −
n
i=1
α
i
y
i
x
i
= 0
n
i=1
α
i
y
i
= 0
(1.7)
注：x
i
, y
i
为第 i 个样本，
∂L
∂w
= 0 体现了 ∥w∥
2
添加
1
2
的优势。
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.4 支持向量机的求解 第一章 基本支持向量机
将 (1.7) 带入 L 中，继而在 α ⩾ 0 上对其求最大值，有
L(w, b, α) =
1
2
w
T
w −
n
i=1
α
i
y
i
(w
T
x
i
+ b) −1
=
1
2
w
T
w −
n
i=1
α
i
y
i
w
T
x
i
−
n
i=1
α
i
y
i
b
=0
+
n
i=1
α
i
=
n
i=1
α
i
−
n
i=1
α
i
y
i
w
T
x
i
+
1
2
w
T
·
n
i=1
α
i
y
i
x
i
=
n
i=1
α
i
−
1
2
n
i=1
α
i
y
i
x
i
· w
T
=
n
i=1
α
i
−
1
2
n
i=1
n
j=1
α
i
α
j
x
i
x
j
y
i
y
j
= f (α)
于是，原 SVM 问题变为对偶问题 (1.8)
max
α
α
i
⩾0
min
w,b
L(w, b|α) = max
α
α
i
⩾0
f(α) (1.8)
= max
α
α
i
⩾0
n
i=1
α
i
−
1
2
n
i=1
n
j=1
α
i
α
j
x
i
x
j
y
i
y
j
重新整理为
max
α
f(α) =
n
i=1
α
i
−
1
2
n
i=1
n
j=1
α
i
α
j
x
i
x
j
y
i
y
j
(1.9)
s.t.
n
i=1
α
i
y
i
= 0
α
i
⩾ 0
i = 1, 2, . . . , n
设上述对偶问题的最优解为 α
∗
，同时，注意到这个问题是一个凸二次规划问题。
1.4.4 KKT 条件
无论是前面的 SVM 原问题，还是上述的对偶问题，我们最终都需要求解一个非线性的凸规
划问题 (凸二次规划)，我们下面将介绍 KKT 条件，来求解规划问题的最优解 d
∗
(α, w, b)。KKT
条件用来指引我们“什么样的解可能是最优解”，这将为我们的数值计算提供方向。
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.4 支持向量机的求解
对一般的非线性规划问题
min
w∈R
n
f(w) (1.10)
s.t.
g
i
(w) ⩽ 0 i = 1, 2, . . . , l
h
j
(w) = 0 j = 1, 2, . . . , m
引理 (等式约束问题的最优解的一阶必要条件) w
∗
是最优解的必要条件：∃β
∗
(拉格朗日乘
子) 当然，w
∗
必须满足等式约束条件，或者
∂L
∂λ
= 0。使
∂L
∂w
=
∂f
∂w
∗
+
m
j=1
β
∗
j
∂h
∂w
w
∗
= 0 (1.11)
引理 (不等式约束问题的最优解的一阶必要条件 (即 KKT 条件))
∂f
∂w
+
l
i=1
α
i
∂g
∂w
= 0
α
i
g
i
(w) = 0
α
i
⩾ 0
当然，w
∗
必须满足不等式约束 g
i
(w) ⩽ 0。
引理 (含等式和不等式约束的最优解的一阶必要条件) w
∗
是最优解的必要条件：∃α
∗
β
∗
，有
∇f(w) +
l
i=1
α
i
g
i
(w
∗
) +
m
j=1
β
j
h
j
(w
∗
) = 0
α
i
g
i
(w) = 0
α
i
⩾ 0
注：只需用 h
i
(w) ⩾ 0 和 h
i
(w) ⩽ 0 替代 h
i
(w) = 0 进入 s.t. 即可。
下面，我们来简单看一下 KKT 条件 (在一般优化教材上都可以看到)。我们着眼于解的可行
域 (自变量 w 的定义域)：如果 g(w) < 0，那么，我们只需要在其内求 ∇f (w) = 0 即可；如果
g(w) = 0 或者 g
i
(w) ⩽ 0(即在 g(w) 可行域边界上求解)，则需要进行讨论，下面我们就来看一下
这种情况。
设 w 位于第一个不等式约束的边界上 (即 g
1
(w) = 0)，如果 w 是极小点，则 ∇g
1
(w) 必
与 ∇f(w) 在一条直线上，并且方向相反，否则，该点就存在可行下降方向，即 ∃α
1
⩾ 0，使
∇f(w) + α
1
∇g
1
(w) = 0。
设 w 位于第一个不等式约束和第二个不等式约束的边界上，有 g
1
(w) = 0�g
2
(w) = 0。如果
w 是极小点，并且 ∇g
1
(w) 与 ∇g
2
(w) 线性无关，则 ∇f (w) 必处于 ∇g
1
(w) 与 ∇g
2
(w) 的夹角
内，即 ∃α
1
, α
2
⩾ 0，使
∇f(w) + α
1
∇g
1
(w) + α
2
∇g
2
(w) = 0
http://www.ma-xy.com 11 http://www.ma-xy.com
http://www.ma-xy.com
1.4 支持向量机的求解 第一章 基本支持向量机
递归上面的内容，有
∇f(w) +
l
i=1
α
i
∇g
i
(w) = 0
同时，当 g
i
(w) = 0 时，有 α
i
= 0；当 g
i
(w) = 0 时，α
i
可以不为 0，于是有
α
i
g
i
(w) = 0
α
i
⩾ 0
前面，我们曾经提到过，对于凸规划而言，满足 KKT 条件的极小点 (KKT 点) 即为最优点，
即 KKT 条件是最优点的充分必要条件。而且我们还提到过，对于凸规划而言，对偶问题的最优
解即为原问题的最优解：
对偶问题的极小解
KKT
−−−→ 对偶问题的最优解 −→ 原问题最优解
现在，我们可以利用 KKT 条件来求解 SVM 的对偶问题 (
1.8)
的最优解
α
∗
, w
∗
, b
∗
，假设我
们通过一定的算法 (算法迭代的思路是依据 KKT 条件的，使解不断满足 KKT 条件) 得到了 α
∗
，
那么后面的问题是如何求 w
∗
, b
∗
？
d
∗
= (α
∗
, w
∗
, b
∗
) = p
∗
满足 KKT 条件，即
∇
w
L(w
∗
, b
∗
, α
∗
) = 0
∇
b
L(w
∗
, b
∗
, α
∗
) = 0
α
∗
i
(y
i
(w
∗
x
i
+ b
∗
) −1) = 0
y
i
(w
∗
x
i
+ b
∗
) −1 = 0
α
∗
i
⩾ 0
于是，有
w =
i
α
i
y
i
x
i
其中，至少有一个 α
∗
j
，对此 j，我们有
y
j
(w
∗
x
j
+ b
∗
) −1 = 0
⇒ y
j
(
i
α
∗
i
y
i
x
i
x
j
+ b
∗
) −1 = 0
⇒ y
j
(
i
α
∗
i
y
i
x
i
x
j
+ b
∗
) = 1 =: y
2
j
⇒ b
∗
= 1 −
i
α
∗
i
y
i
x
i
x
j
至此，SVM 基本的任务已经完成了，存留的问题：用算法求解对偶问题 (对偶问题是一个凸
二次规划) 的最优解 α
∗
，即拉格朗日乘子，此问题后面说明。
注：1、(凸) 二次规划的常用解法有：块选算法、分解算法、SMO 序列最优算法、起作用集法、
路径跟踪法、Lemke 算法等。2、α
∗
中只有一些 α
∗
i
的值不为 0，对应的是支持向量 x
i
，而且非
常稀疏。
http://www.ma-xy.com 12 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.5 容错支持向量机
1.5 容错支持向量机
走到这里，对于一个简单的二分类问题，我们的 SVM 建模已经基本结束了，不过还存在一
个 α
∗
的凸二次规划算法没有说明，这个留在后部分。虽然我们已经能够将两类样本分割开来，
但这是在理想数据上进行的 (即 y = ±1 是严格线性可分的)，现实中的数据情况要复杂的多。下
面，我们将上面建立的模型一步步改进，让它适用于不同的问题。
先来看一个图示的例子。在处理数据时，经常会看到异常的数据，甚至是错误的数据。还有
时候会发现个别情况 (特例/野点)，如图 (1.6) 所示
图 1.6: 分类问题异常值示意图
当然，我们有专门用于挖掘奇点 (1、2、3、4) 的算法 (SVM 就可以)，它们是值得研究的，但
不是我们的重点。这里，我们希望能够“丢弃”这些污染，比如对于分类问题异常值示意图
(a)
而言，可以如图 (1.7) 那样来处理。我们丢弃这些污染，使得分类更加的清晰 (最小距离最大化)。
这也为预处理数据提供一定的思路。在使用 SVM 之前，可以先对异常值进行处理，如平滑数据，
当然，也可以用 SVM 来挖掘奇点。
先来看图 (1.7)
图 1.7: SVM 处理奇点的示意图
在前面，我们定义了 |w
T
x
∗
i
+ b| = 1，所有非支持向量 (样本点) 的 y
i
(w
T
+ b) > 1，但是，
对于图 (1.7) 中的点 1 点 2 来讲，显然不是的，它们虽然不是支持向量，但是二者的 y
i
(w
T
+ b)
却是负值。为此，在其中引入松弛变量 ξ
i
，ξ ⩾ 0(如其名，ξ
i
是一个变量，作用是放宽某些条件)
y
1
(w
T
x
1
+ b) > 1 −ξ
1
y
2
(w
T
x
2
+ b) > 1 −ξ
2
但是，这种“丢弃”行为会给我们造成一定的损失：¬ 错判损失； 样本信息损失。为此，我们
需要定义损失函数来控制这种损失，如果任由损失泛滥，则有可能导致如图 (1.8) 的现象。
http://www.ma-xy.com 13 http://www.ma-xy.com
http://www.ma-xy.com
1.5 容错支持向量机 第一章 基本支持向量机
图 1.8: 误分现象图
损失函数：显然损失与 ξ
i
的大小有关，对于某点 (x
i
, y
i
) 而言，如果 ξ
i
= 0，就不存在损失；
如果 ξ
i
⩾ 0，就存在损失；当 0 < ξ
i
< 1 时，(x
i
, y
i
) 样本并未被误分；当 ξ
i
> 1 时，样本 (x
i
, y
i
)
被误分，相比之下，我们更不希望这种情况的发生。令 f (ξ
i
) 为损失函数。于是，可以设置如下
极小化损失的目标
min
w,b,ξ
n
i=1
f(ξ
i
)
注：f (ξ
i
) = ξ
i
, f(ξ
i
) = ξ
2
i
, f(ξ
i
) = I(ξ
i
−1) 等等，这些函数形式都可以，不过我们最好还是选取
凸函数作为目标！
将上述损失目标和原始目标 (最小距离最大 or 分割距离最大) 结合起来，可以构建如下多目
标问题
max
1
∥w∥
min
n
i=1
f(ξ
i
)
s.t.
y
i
(w
T
x
i
+ b) ⩾ 1 −ξ
i
ξ
i
⩾ 0
i = 1, 2, ··· , n
将上面优化问题中的 max 转化为 min，并取 f (ξ
i
) = ξ
i
，用权重 c 来设置第二个目标的重要
性，有
min
w,b,ξ
1
2
w
T
w
+
c
n
i=1
ξ
i
(1.12)
s.t.
y
i
(w
T
x
i
+ b) ⩾ 1 −ξ
ξ
i
⩾ 0
i = 1, 2, ··· , n
容错支持向量机的模型已经建好了，就是在原 SVM 模型上进行改进的，注意，上面的模型
仍然是一个凸二次规划问题，我们可以依据前面的思路，对其进行拉格朗日对偶求解。在此之前，
值得一提的是：目标中的第二项
n
i=1
ξ
i
在统计学习理论中叫做经验风险，广义上可以记为 Ω(f)，
第一项 w
T
w 叫做结构风险。在统计学习理论中，有许多最优超平面 (即高维的分割面) 的性质和
定理，这里不多做说明，可以参考《统计学习理论》Vapnilk 一书。下面，我们来求解 (1.12) 模
http://www.ma-xy.com 14 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.6 核技术的引入
型，限于篇幅，这里不做展开，直接给出其对偶问题
max
α
n
i=1
α
i
−
1
2
n
i=1
n
i=1
α
i
α
j
y
i
y
j
x
i
x
j
(1.13)
s.t.
n
i
=1
α
i
y
i
= 0
0 ⩽ α
i
⩽ c
i = 1, 2, ··· , n
将上述模型 (1.13) 写为矩阵形式，且转化为最小化问题，有
min
α
1
2
α
T
Qα − e
T
α (1.14)
s.t.
y
T
α = 0
0 ⩽ α
i
⩽ c or 0 ⩽ α ⩽ ce
其中：e 是全 1 向量，Q 是对称矩阵，Q
ij
= y
i
y
j
x
i
x
j
上述问题仍是一个凸规划问题，其求解方式仍然在后面的章节。我们姑且称上述容错二分类
支持向量机为 C-SVM。
注：如何确定外来参数 c：CV 方法或者 (智能) 优化；能否在原参数空间上求解 C-SVM？
1.6 核技术的引入
上面建立的 C-SVM 使得我们可以处理一些非完全线性可分数据，但是，在实际工作中，要
求绝不会如此简单，有许多非线性问题等待我们讨论，比如下面这些图中的问题，非线性可分如
图 (1.9) 所示
图 1.9: 非线性可分示意图
如果存在某些奇点 (干扰点/野点/离群点)，会有非线性非完全可分问题，如图 (1.10) 的情况
http://www.ma-xy.com 15 http://www.ma-xy.com
http://www.ma-xy.com
1.6 核技术的引入 第一章 基本支持向量机
图 1.10: 非线性非完全可分示意图
图 (1.10) 的情况是在图 (1.9) 上引入松弛变量 ξ 的情况，我们来看一下图 (1.9) 中的分类器：
• 图 (1.9)(a) 的分类线为：(x
1
− a)
2
+ (x
2
− b)
2
= r
2
；
• 图 (1.9)(b) 的分类线为：x
2
= ax
2
1
+ bx
1
+ c；
上面两个分类线都是 x
1
Ox
2
中的非线性函数，将 (x
1
− a)
2
+ (x
2
− b)
2
= r
2
变形，有
x
2
1
− 2ax
1
+ x
2
2
− 2bx
2
+ a
2
+ b
2
− r
2
= 0 (1.15)
也即
w
1
x
2
1
+ w
2
x
1
+ w
3
x
2
2
+ w
4
x
2
+ b = 0 (1.16)
可以看出，非线性分类线 (1.15) 虽然不是 x
1
, x
2
的线性函数，但却是它们变形后 (x
1
, x
2
1
, x
2
, x
2
2
)
的线性函数 (1.16)。
我们称 X = (x
1
, x
2
) ⊂ R
2
为原始特征空间，称 X
∗
= (x
1
, x
2
1
, x
2
, x
2
2
) ⊂ R
4
是变换后的新特
征空间。我们可以定义一个变化 ϕ(·)，ϕ(·) 使得 X 变为 X
∗
ϕ(X) = X
∗
从数据上看，ϕ(·) 的作用是这样的
x
1
x
2
.
.
.
.
.
.
ϕ(·)
−−→
x
1
x
2
1
x
2
x
2
2
.
.
.
.
.
.
.
.
.
.
.
.
就上面的问题而言，在变换后的新空间上建立线性的 C-SVM 就可以解决这个非线性分类问
题。但一般而言，我们并不知道新特征空间的形式 (即 X 变换后的 X
∗
中只有 x
1
, x
2
1
, x
2
, x
2
2
)，那
么该如何确定转换 ϕ(·) 呢？
想一个复杂的变换：我们将所有可能的情况都列举出来
(x
1
, x
2
) −→ (x
1
x
2
1
x
3
1
···x
l
1
, x
2
x
2
2
x
3
2
···x
l
2
, x
1
x
2
x
2
1
x
2
···)
l→∞
(1.17)
当不存在上面变换后的某项时，我们令其权重 w 为 0 即可。可是，如果像上式 (1.17) 那
样来处理 ϕ(·)，会给我们的处理以及计算带来很多麻烦，而且还要限定一些外来参数 l。为了解
http://www.ma-xy.com 16 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.6 核技术的引入
决这个问题，我们引入核函数这个工具，在此之前，我们来看一下前面 C-SVM 的分类线 (如果
X ⊂ R
n
，则称分类线为分类超平面)。
w
∗
x + b
∗
= 0
其中：x ∈ R
2
，w
∗
=
n
i=1
α
∗
i
y
i
x
i
，所以，上式又可以写为
n
i=1
α
∗
i
y
i
x
i
x + b = 0
上式中除了有 x 外，还有 x
i
x，如此看来，我们除了要关心变换 ϕ(·) 以外，还要关心 ϕ(x
i
)ϕ(x)。
定义 (核函数) 设 X 是原特征空间 (X ⊂ R
n
)，设 H 是新的特征空间 (H 是 Hilber 空间：
Hilber 空间可以看作 n 维欧式空间的无穷维推广)，如果存在一个从 X → H 的映射
ϕ(X) : X → H
使得对于所有的 x
i
, x
j
(x
i
, x
j
∈ X ⊂ R
n
)，有函数 K(x
i
, x
j
)
K(x
i
, x
j
) = ϕ(x
i
)ϕ(x
j
)
则称函数 K(x
i
, x
j
) 为核函数。其中：ϕ(x
i
)ϕ(x) 表示内积，所以 K 亦被称为内积核函数。
注：对于给定的核函数 K，H 和 ϕ 二者的取法不唯一；内积核函数为对称核函数：K(x
i
, x
j
) =
K(x
j
, x
i
)；核函数 K(x, y) 是定义在 R
n
× R
n
上的函数，即 x
i
, x
j
∈ X ⊂ R
n
。
前面，提问过该如何确定 ϕ(·)？其实，ϕ(·) 在未分类之前 (分类器 SVM 未构建之前) 是不能
确定的，我们只能假设它是某种形式，例如：可以将其假设为 ϕ(X) = (x
1
, x
2
, x
1
x
2
)，也可以假
设为 ϕ(X) = (x
1
, x
2
2
, x
1
x
2
2
) 等等形式，当然也可以像前面的“最复杂的变换”式 (1.17)。这种做
法的本质目的是将原始特征空间 X 引入到新的高维特征空间。前面说过即便给定了 K(·)，其映
射变换 ϕ(·) 也是不确定的。而 ϕ(·) 本身就是我们假设的 (本身即不确定)，所以可以跳过 ϕ(·) 而
直接假设 K(·) 的形状。K(·) 的作用仍就是将原始空间投影到高维空间。值得一提的是：并不是
K(·) 或者 ϕ(·) 的形式越复杂越好，像前面提到的“最复杂的变换”，即上式 (1.17)，因为那样会
出现过拟合现象。
我们可以来事先假设内积核函数 K(·) 的形状，但是什么样的函数是内积核函数呢？Mercer
定理给了我们答案。
定理 (Mercer 定理) 任何半正定的函数都可以作为核函数。其实内积核函数 K(x
i
, x
j
)(x
i
, x
j
∈
X ⊂ R
n
) 是泛函分析中 Mercer 定理的一种特殊形式。如果 K(x
i
, x
j
) 是定义在 X × X(L
2
(X))
上的连续对称函数，其中，X 是 R
n
的紧集，且有
X
X
K(x
i
, x
j
)g(x
i
)g(x
j
)dx
i
dx
j
⩾ 0 成立
(∀g ∈ L
2
(X))，则 ∃ϕ(·)，使得 K(x
i
, x
j
) = ϕ(x
i
)ϕ(x
j
)，反之亦成立。
Mercer 定理可以帮助我们判断一个函数 K(·) 是否可以作为核函数，如果是核函数，那么就
可以将其运用到 SVM 中。下面给出一些常用的核函数，至于如何构建核函数，这里就不做讨论
了。常见的核函数如表 (1.2) 所示
http://www.ma-xy.com 17 http://www.ma-xy.com
http://www.ma-xy.com
1.6 核技术的引入 第一章 基本支持向量机
表 1.2: 常见的核函数
核函数 表达式
线性核： k(x
i
y
i
) = x
i
· y
i
多项式核： k(x
i
y
i
) = (γx
i
· y
i
+ r)
d
d ⩾ 1 γ > 0
高斯核： k(x
i
y
i
) = exp(−
∥x
i
−y
i
∥
2
2σ
2
) σ > 0
RBF 核： k(x
i
y
i
) = exp(−γ∥x
i
− y
i
∥
2
) γ > 0
B 样条核： k(x
i
y
i
) = B
2N+1
(∥x
i
− y
i
∥)
sigmoid 核： k(x
i
y
i
) = tanh(x
i
· y
i
+ r) tanh(x) =
e
x
e
x
+1
γ > 0 r < 0
拉普拉斯核： k(x
i
y
i
) = exp(−
1
6
∥x
i
− y
i
∥) σ > 0
小波核：
混合核：
核函数的性质 如果 K
1
和 K
2
是 X × X(L
2
(X)) 上的核函数，则 αK(α ⩾ 0)，K
1
+ K
2
和
K
1
· K
2
也是核函数。并且 ∀g，g(x)k(x, y)g(y) 亦为核函数。
那么问题来了：
• 这么多的核函数，如何选择适合的核函数呢？评价标准是什么？
• 核函数中有一些外来的参数 γ 等等，如何确定这些参数？
注：关于正定核，我们没有讨论，设 K 是 L
2
(X) 上的对称函数，K 为正定核的充要条件是：对
∀x
i
∈ X(i = 1, 2, . . . , n)，K 对应的矩阵 K = [K(x
i
, x
j
)] ，K
ij
= K(x
i
, x
j
) 是半正定的。Mercer
核是正定核，多项式核、高斯核也是正定核。
现在，可以将核函数 K 引入到前面的 C-SVM 中，使 C-SVM 可以处理非线性分类情况。设
我们假设的 (挑选的) 核函数为 K，其变换 (映射) 为 ϕ。对于 C-SVM，有
min
w,b,x
1
2
w
T
w + c ·
n
i=1
ξ
s.t.
y
i
(w
T
ϕ(x
i
) + b) ⩾ 1 − ξ
i
ξ ⩾ 0
i = 1, 2, ··· , n
其对应的对偶问题 (写成 min 形式) 为：
min
α
1
2
n
i=1
n
j=1
α
i
α
j
y
i
y
j
k(x
i
y
i
) −
n
i=1
α
i
s.t.
n
i=1
α
i
y
i
= 0
0 ⩽ α
i
⩽ c
i = 1, 2, ··· , n
http://www.ma-xy.com 18 http://www.ma-xy.com
http://www.ma-xy.com
第一章 基本支持向量机 1.7 SVM 解决 XOR 问题的小例子
至此，支持向量机模型已经基本构建完毕，后面的工作是对 C-SVM 的性能的讨论以及模型
的变换与改进。关于 SVM 的性能我们可以讨论其优化模型的求解算法，模型中参数的选取以及
核函数的性质等诸多方面。而关于 SVM 的变种与派生更是数不胜数。
在讨论 SVM 的性能之前，我们先来看一个小例子
¬
，这个例子可以更好地帮助我们理解
SVM。
1.7 SVM 解决 xor 问题的小例子
给出原始数据 data
x
1
x
2
y
−1 −1 −1
−1 +1 +1
+1 −1 +1
+1 +1 −1
为了进行分割，先给出核函数 K, 选定的核函数为
K(x
i
, y
i
) = (1 + x
i
y
i
)
2
= 1 + x
2
i1
x
2
j1
+ 2x
i1
x
i2
x
j1
x
j2
+ x
2
i2
x
2
j2
+ 2x
i1
x
2
j1
+ 2x
i2
x
j2
可以写出 K 在 H 为 6 时的 ϕ(x)
ϕ(x
i
) =
1, x
2
i1
,
√
2x
i1
x
i2
, x
2
i2
,
√
2x
i1
,
√
2x
i2
T
可以写出 K 在 α
i
(i = 1, 2, 3, 4) 上对应的 Gram 矩阵 K
ij
K =
q 1 1 1
1 q 1 1
1 1 q 1
1 1 1 q
SV M 的对偶问题为
max
α
α
1
+ α
2
+ α
3
+ α
4
−
1
2
(9α
2
1
− 2α
1
α
2
− 2α
1
α
3
+ 2α
1
α
4
+ 9α
2
2
+ 2α
2
α
3
− 2α
2
α
4
+ 9α
3
α
4
+ 9α
2
4
)
s.t.
n
i=1
α
i
y
i
= 0
0 ⩽ α
i
i = 1, 2, 3, 4
¬
《神经网络原理》SimonHaykin 著，叶世伟译 P241
http://www.ma-xy.com 19 http://www.ma-xy.com
http://www.ma-xy.com
1.7 SVM 解决 XOR 问题的小例子 第一章 基本支持向量机
对 Lagrange 乘子优化产生下列方程组
9α
1
− α
2
− α
3
+ α
4
= 1
− α
1
+ 9α
2
+ α
3
− α
4
= 1
− α
1
+ α
2
+ 9α
3
− α
4
= 1
α
1
− α
2
− α
3
+ 9α
4
= 1
因此，Lagrange 乘子 α 的最优值 α
∗
为
α
1
= α
2
= α
3
= α
4
=
1
8
说明数据中的 4 个向量皆为支持向量，目标函数最优值为
1
4
，最优权重 w
∗
为
w
∗
=
n
i=1
α
∗
y
i
· φ(x
i
)
=
1
8
[−φ(x
1
) + φ(x
2
) + φ(x
3
) −φ(x
4
)]
=
1
8
−
1
1
√
2
1
−
√
2
−
√
2
+
1
1
−
√
2
1
−
√
2
√
2
+
1
1
−
√
2
1
√
2
−
√
2
−
1
1
√
2
1
√
2
√
2
=
0
0
−
1
√
2
0
0
0
最优偏量 b
∗
为 w 的第一个分量为 0 。
最优超平面为
w
∗
· φ(x) = 0
0, 0, −
1
√
2
, 0, 0, 0
1
x
2
1
√
2x
1
x
2
x
2
2
√
2x
1
√
2x
2
= 0
http://www.ma-xy.com 20 http://www.ma-xy.com
