机器学习算法总结 SVM
- 格式：pdf
- 大小：387.40 KB
- 文档页数：13
, : i 0
（5-15）
这里的 p 代表 primal，即原始问题。因此，
f ( x), x满足原始问题约束 p ( x) +， 其它
（5-16）
f ( x ) 就可以转换成求 min p ( x) ，进而 这样，我们原来要求的 m in n n
x R
xR
图 5.3
分类间隔
我们将问题延伸到高维数据上，并进行形式化的表示。假设给定一个特征空 间上的训练集：
其中， ，为第个特征向量，也称为实例，为的类标记，称为样本点，假设训练数 据集是线性可分的。
定义 5-1（函数间隔）
对于给定的训练数据集和超平面 ( w, b) ，定义超
平面 ( w, b) 关于样本点 ( xi , yi ) 的函数间隔为
第 5 章 支持向量机
5.1 引言
支持向量机 (Support Vector Machine ，简称 SVM) 是于 1995 年由 Cortes 和 Vapnik 首先提出的， 它在解决小样本、 非线性及高维模式识别中表现出许多特有 的优势， 并能够推广应用到函数拟合等其他机器学习问题中。它通过寻求结构化 风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到 在统计样本量较少的情况下，亦能获得良好统计规律的目的。 支持向量机是一种二类分类模型。 其基本模型定义为特征空间上的间隔最大 的线性分类器， 即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸 二次规划问题的求解。支持向量机的学习算法就是求解凸二次规的最优化算法。
5.2.2 分类间隔
显然，图 5.1 中间那条分界线并不是唯一的，我们把它稍微旋转一下，只要 不把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以（如图 5.2 所示） 。此时就牵涉到一个问题，对同一个问题存在多个分类函数的时候，哪 一个函数更好呢？显然必须要先找一个指标来量化“好”的程度，通常使用的都 是叫做“分类间隔”的指标。
5.2 线性可分支持向量机 5.2.1 线性可分
线性分类器是最简单也很有效的分类器形式。在一个线性分类器中，可以看 到 SVM 形成的思路，并接触很多 SVM 的核心概念。 用一个二维空间里仅有两类样本的分类问题来举个小例子。如图 1.1 所示
图 5.1
二维空间两样本分类问题
C1 和 C2 是要区分的两个类别，在二维平面中它们的样本如图 1.1 所示。中间
min p ( x)= min max L( x, , ) n n
xR xR
, : i 0
（5-17）
p ( x) ，定义原始问题的最优值为 为了方便，我们用 p* 来表示 min n
xR
p* min p ( x) n
xR
（5-18）
但是，对于上式，如果直接求解，首先面对的是两个参数，且 i 又是不等式
w ,b
首先求 L( w, b, ) 的最小值，此时 i 可视为固定值。将 L( w, b, ) 对 w,b 求偏导并令
其等于 0。
w L( w, b, ) w i yi xi 0 b L( w, b, ) i yi 0
N i 1
N
i*ci ( x* ) 0,
ci ( x* ) 0,
i 1, 2, , k i 1, 2, , k i 1, 2, , k i 1, 2, , k
i* 0,
h j ( x* ) 0,
其中，式（5-26 ）称为 KKT 的对偶互补条件（KKT dual complementarity） 。这个条件隐 含了如果 i 0 ，那么 ci ( x ) 0 。
* * * * * *
*
*
外， x 和 , 满足 Karush-Kuhn-Tucker（KKT）条件：
* * *
x L( x* , * , * ) 0 L ( x * , * , * ) 0 L( x* , * , * ) 0
（5-23） （5-24） （5-25） （5-26） （5-27） （5-28） （5-29）
min i
i 1,, N
（5-5）
从前面的两个定义我们可以看到，函数间隔和几个间隔有下面的关系
实际上，
ˆ
wห้องสมุดไป่ตู้
（5-6）
i 就是样本点 xi 到超平面 ( w, b) 的距离。同时，当 w 1 时，函数 ˆ 间隔与几何间隔是相等的。 也就是说，前面提到的对 i 的规范化的结果就是几何 w 间隔。此时如果同时扩大 w 和 b ， 也会随之扩大多少倍，对于最终的几何间 隔 并无影响。
, : i 0 xR
（5-20）
这个问题是原问题的对偶问题，定义对偶问题的最优值
d * max D ( , )
, : i 0
（5-21）
在一般情况下
d * max min L ( x, , ) min max L ( x, , ) p* n n
ˆ w
（5-7） （5-8）
函数间隔 ˆ 的取值并不影响最优化问题的解。事实上，假设将 w 和 b 按比例 改变为 实际上， i 就是样本点 xi 到超平面 ( w, b) 的距离。同时，当 w 1 时，函数 间隔与几何间隔是相等的。 也就是说，前面提到的对 ˆi 的规范化的结果就是几何 间隔。此时如果同时扩大 w 和 b ， w 也会随之扩大多少倍，对于最终的几何间 隔 并无影响。 不妨对 ˆ 做一些限制，以保证我们的解是唯一的。这里为了简便我们取 ˆ 1 ，将离超
的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性 函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性 可分的。 线性函数，在一维空间里就是一个点，在二维空间里就是一条直线，在三维 空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函 数还有一个统一的名称——超平面（Hyper Plane） ！ 实际上，一个线性函数是一个实值函数（即函数的值是连续的实数） ，而我 们的分类问题 （例如这里的二元分类问题——回答一个样本属于还是不属于一个 类别的问题）需要离散的输出值，例如用 1 表示某个样本属于类别 C1 ，而用 0 表示不属于（不属于 C1 也就意味着属于 C2 ） ，这时候只需要简单的在实值函数的 基础上附加一个阈值即可， 通过分类函数执行时得到的值大于还是小于这个阈值 来确定类别归属。 例如我们有一个线性函数
（5-2） 定义超平面 ( w, b) 关于训练数据集 T 的函数间隔为超平面 ( w, b) 关于 T 中 所有样本点
( xi , yi )
ˆi yi ( w xi b)
的函数间隔之最小值，即
ˆ min ˆi
i 1,, N
（5-3）
函数间隔可以表示分类预测的正确性。如果考虑 w 和 b ，如果同时成比例的
T 改变为 2 w 和 2b 。因为我们要求解的是 w x b 0 ，同时扩大 w 和 b 对结果是无 影响的。但是，函数间隔 ˆ 却成为了原来的 2 倍。因此，我们需要对其法向量 w
加一些约束， 对其进行规范化。 我们可以取 由这一事实到处几何间隔的概念。 定义 5-2（几何间隔）
w 1
5.2.3 间隔最大化
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔 最大的分离超平面。 我们不需要考虑所有的点都必须远离超平面，我们关心求得 的超平面能够让所有点中离它最近的点具有最大间距。 我们可以对该问题进行形
式化的表示：
max
w ,b
s.t.
yi ( w xi b) ˆ , i 1, 2, , N
引进一般的拉格朗日函数
L(x, , ) f ( x ) ic i ( x ) jh j ( x )
i 1 j 1 k l
（5-14）
这里 i 和 j 是拉格朗日乘子，由于 ci ( x ) 在这里是不等式约束，因此需要考虑下面的
函数：
p ( x) max L( x, , )
, : i 0 xR
xR , : i 0
（5-22）
当满足后面的条件时则会有 d p ： 假设函数 f ( x ) 和 ci ( x ) 是凸函数， h j ( x ) 是仿射函数；并且假设不等式约束 ci ( x ) 是严 格可行的，此时一定存在 x 和 , 使得 x 是原始问题的解， , 是对偶问题的解。另
， 这样函数间隔便也就确定了。
对于给定的训练数据集和超平面 ( w, b) ，定义超
平面 ( w, b) 关于样本点 ( xi , yi ) 的函数间隔为
i yi
w b xi w w
（5-4）
定义超平面 ( w, b) 关于训练数据集 T 的函数间隔为超平面 ( w, b) 关于 T 中所有 (x , y ) 样本点 i i 的几何函数间隔之最小值，即
图 5.2
不同的分类线
如图 5.3，方形点和圆形点代表两类样本, H 为分类线， H1 和 H 2 分别为过各 类中离分类线最近的样本且平行于分类线的直线 , 它们之间的距离叫做分类间 隔(margin)。所谓的最优分类线就是要求分类线不但能将两类正确分开，而且使 得分类间隔最大。 而将这一理论推广到高维空间， 最优分类线就变为最优分类面。
5.2.4 拉格朗日对偶
拉格朗日对偶性常用于带约束的最优化问题中， 其将原始问题转化为对偶问 题，并通过解对偶问题而得到原始问题的解。 考虑约束最优化问题
m in f (x) n
x R
（5-11） （5-12） （5-13）
s.t. ci ( x ) 0,
i=1,2, ,k
（5-15）
这里的 p 代表 primal，即原始问题。因此，
f ( x), x满足原始问题约束 p ( x) +， 其它
（5-16）
f ( x ) 就可以转换成求 min p ( x) ，进而 这样，我们原来要求的 m in n n
x R
xR
图 5.3
分类间隔
我们将问题延伸到高维数据上，并进行形式化的表示。假设给定一个特征空 间上的训练集：
其中， ，为第个特征向量，也称为实例，为的类标记，称为样本点，假设训练数 据集是线性可分的。
定义 5-1（函数间隔）
对于给定的训练数据集和超平面 ( w, b) ，定义超
平面 ( w, b) 关于样本点 ( xi , yi ) 的函数间隔为
第 5 章 支持向量机
5.1 引言
支持向量机 (Support Vector Machine ，简称 SVM) 是于 1995 年由 Cortes 和 Vapnik 首先提出的， 它在解决小样本、 非线性及高维模式识别中表现出许多特有 的优势， 并能够推广应用到函数拟合等其他机器学习问题中。它通过寻求结构化 风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到 在统计样本量较少的情况下，亦能获得良好统计规律的目的。 支持向量机是一种二类分类模型。 其基本模型定义为特征空间上的间隔最大 的线性分类器， 即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸 二次规划问题的求解。支持向量机的学习算法就是求解凸二次规的最优化算法。
5.2.2 分类间隔
显然，图 5.1 中间那条分界线并不是唯一的，我们把它稍微旋转一下，只要 不把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以（如图 5.2 所示） 。此时就牵涉到一个问题，对同一个问题存在多个分类函数的时候，哪 一个函数更好呢？显然必须要先找一个指标来量化“好”的程度，通常使用的都 是叫做“分类间隔”的指标。
5.2 线性可分支持向量机 5.2.1 线性可分
线性分类器是最简单也很有效的分类器形式。在一个线性分类器中，可以看 到 SVM 形成的思路，并接触很多 SVM 的核心概念。 用一个二维空间里仅有两类样本的分类问题来举个小例子。如图 1.1 所示
图 5.1
二维空间两样本分类问题
C1 和 C2 是要区分的两个类别，在二维平面中它们的样本如图 1.1 所示。中间
min p ( x)= min max L( x, , ) n n
xR xR
, : i 0
（5-17）
p ( x) ，定义原始问题的最优值为 为了方便，我们用 p* 来表示 min n
xR
p* min p ( x) n
xR
（5-18）
但是，对于上式，如果直接求解，首先面对的是两个参数，且 i 又是不等式
w ,b
首先求 L( w, b, ) 的最小值，此时 i 可视为固定值。将 L( w, b, ) 对 w,b 求偏导并令
其等于 0。
w L( w, b, ) w i yi xi 0 b L( w, b, ) i yi 0
N i 1
N
i*ci ( x* ) 0,
ci ( x* ) 0,
i 1, 2, , k i 1, 2, , k i 1, 2, , k i 1, 2, , k
i* 0,
h j ( x* ) 0,
其中，式（5-26 ）称为 KKT 的对偶互补条件（KKT dual complementarity） 。这个条件隐 含了如果 i 0 ，那么 ci ( x ) 0 。
* * * * * *
*
*
外， x 和 , 满足 Karush-Kuhn-Tucker（KKT）条件：
* * *
x L( x* , * , * ) 0 L ( x * , * , * ) 0 L( x* , * , * ) 0
（5-23） （5-24） （5-25） （5-26） （5-27） （5-28） （5-29）
min i
i 1,, N
（5-5）
从前面的两个定义我们可以看到，函数间隔和几个间隔有下面的关系
实际上，
ˆ
wห้องสมุดไป่ตู้
（5-6）
i 就是样本点 xi 到超平面 ( w, b) 的距离。同时，当 w 1 时，函数 ˆ 间隔与几何间隔是相等的。 也就是说，前面提到的对 i 的规范化的结果就是几何 w 间隔。此时如果同时扩大 w 和 b ， 也会随之扩大多少倍，对于最终的几何间 隔 并无影响。
, : i 0 xR
（5-20）
这个问题是原问题的对偶问题，定义对偶问题的最优值
d * max D ( , )
, : i 0
（5-21）
在一般情况下
d * max min L ( x, , ) min max L ( x, , ) p* n n
ˆ w
（5-7） （5-8）
函数间隔 ˆ 的取值并不影响最优化问题的解。事实上，假设将 w 和 b 按比例 改变为 实际上， i 就是样本点 xi 到超平面 ( w, b) 的距离。同时，当 w 1 时，函数 间隔与几何间隔是相等的。 也就是说，前面提到的对 ˆi 的规范化的结果就是几何 间隔。此时如果同时扩大 w 和 b ， w 也会随之扩大多少倍，对于最终的几何间 隔 并无影响。 不妨对 ˆ 做一些限制，以保证我们的解是唯一的。这里为了简便我们取 ˆ 1 ，将离超
的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性 函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性 可分的。 线性函数，在一维空间里就是一个点，在二维空间里就是一条直线，在三维 空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函 数还有一个统一的名称——超平面（Hyper Plane） ！ 实际上，一个线性函数是一个实值函数（即函数的值是连续的实数） ，而我 们的分类问题 （例如这里的二元分类问题——回答一个样本属于还是不属于一个 类别的问题）需要离散的输出值，例如用 1 表示某个样本属于类别 C1 ，而用 0 表示不属于（不属于 C1 也就意味着属于 C2 ） ，这时候只需要简单的在实值函数的 基础上附加一个阈值即可， 通过分类函数执行时得到的值大于还是小于这个阈值 来确定类别归属。 例如我们有一个线性函数
（5-2） 定义超平面 ( w, b) 关于训练数据集 T 的函数间隔为超平面 ( w, b) 关于 T 中 所有样本点
( xi , yi )
ˆi yi ( w xi b)
的函数间隔之最小值，即
ˆ min ˆi
i 1,, N
（5-3）
函数间隔可以表示分类预测的正确性。如果考虑 w 和 b ，如果同时成比例的
T 改变为 2 w 和 2b 。因为我们要求解的是 w x b 0 ，同时扩大 w 和 b 对结果是无 影响的。但是，函数间隔 ˆ 却成为了原来的 2 倍。因此，我们需要对其法向量 w
加一些约束， 对其进行规范化。 我们可以取 由这一事实到处几何间隔的概念。 定义 5-2（几何间隔）
w 1
5.2.3 间隔最大化
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔 最大的分离超平面。 我们不需要考虑所有的点都必须远离超平面，我们关心求得 的超平面能够让所有点中离它最近的点具有最大间距。 我们可以对该问题进行形
式化的表示：
max
w ,b
s.t.
yi ( w xi b) ˆ , i 1, 2, , N
引进一般的拉格朗日函数
L(x, , ) f ( x ) ic i ( x ) jh j ( x )
i 1 j 1 k l
（5-14）
这里 i 和 j 是拉格朗日乘子，由于 ci ( x ) 在这里是不等式约束，因此需要考虑下面的
函数：
p ( x) max L( x, , )
, : i 0 xR
xR , : i 0
（5-22）
当满足后面的条件时则会有 d p ： 假设函数 f ( x ) 和 ci ( x ) 是凸函数， h j ( x ) 是仿射函数；并且假设不等式约束 ci ( x ) 是严 格可行的，此时一定存在 x 和 , 使得 x 是原始问题的解， , 是对偶问题的解。另
， 这样函数间隔便也就确定了。
对于给定的训练数据集和超平面 ( w, b) ，定义超
平面 ( w, b) 关于样本点 ( xi , yi ) 的函数间隔为
i yi
w b xi w w
（5-4）
定义超平面 ( w, b) 关于训练数据集 T 的函数间隔为超平面 ( w, b) 关于 T 中所有 (x , y ) 样本点 i i 的几何函数间隔之最小值，即
图 5.2
不同的分类线
如图 5.3，方形点和圆形点代表两类样本, H 为分类线， H1 和 H 2 分别为过各 类中离分类线最近的样本且平行于分类线的直线 , 它们之间的距离叫做分类间 隔(margin)。所谓的最优分类线就是要求分类线不但能将两类正确分开，而且使 得分类间隔最大。 而将这一理论推广到高维空间， 最优分类线就变为最优分类面。
5.2.4 拉格朗日对偶
拉格朗日对偶性常用于带约束的最优化问题中， 其将原始问题转化为对偶问 题，并通过解对偶问题而得到原始问题的解。 考虑约束最优化问题
m in f (x) n
x R
（5-11） （5-12） （5-13）
s.t. ci ( x ) 0,
i=1,2, ,k
