《机器学习》周志华-CH6(支持向量机)
我们希望样本在特征空间内线性可分,因此特征空间的好坏对支持向量机的性能至关重要。
6.1间隔与支持向量
给定训练样本 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } , y i ∈ { − 1 , + 1 } D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\},y_i\in\{-1,+1\} D={(x1,y1),(x2,y2),...,(xm,ym)},yi∈{−1,+1}分类学习最基本的想法是基于训练集 D D D在样本空间找到一个划分超平面,将不同类别样本分析。
应该找位于两类训练样本“正空间”的划分超平面,如红色的,泛化能力最强,鲁棒性最强。
划分超平面可通过如下线性方程描述:
w
T
x
+
b
=
0
\begin{equation} w^Tx+b=0 \tag{6.1} \end{equation}
wTx+b=0(6.1)
w = ( w 1 , ; w 2 ; . . . w d ) w=(w_1,;w_2;...w_d) w=(w1,;w2;...wd)为法向量, b b b为维向量,决定超平面与原点之间距离
划分超平面由法向量 w w w和位移 b b b确定,记为 ( w , b ) (w,b) (w,b)
任意点
x
x
x到超平面
(
w
,
b
)
(w,b)
(w,b)的距离可写为:
r
=
∣
w
T
x
+
b
∣
∣
∣
x
∣
∣
\begin{equation} r=\frac{|w^{T}x+b|}{||x||} \tag{6.2} \end{equation}
r=∣∣x∣∣∣wTx+b∣(6.2)
假设超平面
(
w
,
b
)
(w,b)
(w,b)可将训练样本正确分类
欲找到具有“最大间隔”(maximum margin)的划分超平面,也就是要找满足约束的
w
w
w和
b
b
b,使得
γ
\gamma
γ最大,即:
6.2对偶问题
求解(6.6)来得到最大划分对应模型
解出 α \alpha α后,求出 w w w与 b b b即可得模型
f
(
x
)
=
w
T
+
b
=
∑
i
=
1
m
α
i
y
i
x
i
T
x
+
b
\begin{equation} f(x)=w^T+b=\sum_{i=1}^m\alpha_{i}y_{i}x_{i}^{T}x+b \tag{6.12} \end{equation}
f(x)=wT+b=i=1∑mαiyixiTx+b(6.12)
对任意训练样本 ( x i , y i ) (x_i,y_i) (xi,yi)总有 α i = 0 \alpha_i=0 αi=0或 y i f ( x i ) = 1 y_if(x_i)=1 yif(xi)=1
若 α i = 0 \alpha_i=0 αi=0,则样本不会在(6.12)中出现,不会对 f ( x ) f(x) f(x)有影响
若 α i > 0 \alpha_i>0 αi>0,则必有 y i f ( x i ) = 1 y_if(x_i)=1 yif(xi)=1,对应样本点位于最大间隔边界上,是支持向量。
支持向量机性质:
训练完成后,大部分训练样本都不需要保留,最终模型仅与支持向量有关。
如何求解(6.11)?
二次规划算法正比于训练样本数,会造成较大开销。
SMO(Sequential Minimal Optimization)是高效算法,著名代表。
SMO基本思路:
先固定 α i \alpha_i αi之外的所有参数,然后求 α i \alpha_i αi上的极值。
参数初始化后,SMO不断执行如下两个步骤至收敛:
- 选取一对需更新的变量 α i \alpha_i αi和 α j \alpha_j αj;
- 固定 α i \alpha_i αi和 α j \alpha_j αj以外的参数,求解(6.11)获得更新后的 α i \alpha_i αi和 α j \alpha_j αj
KKT条件违背的程度越大,则变量更新后可能导致的目标函数值减幅越大
使选取的两变量所对应样本之间的间隔最大
SMO高效因为在固定其他参数后,优化两个参数的过程能做到非常高效
仅考虑 α i \alpha_i αi和 α j \alpha_j αj时,(6.11)约束可写为:
6.3核函数
可将样本从原始空间映射到一个更高维的特征空间
如果原始空间是有限维,属性数有限,一定存在一个高维特征空间使样本可分:
(6.24)显示模型最优解可通过训练样本的核函数展开,亦称“支持向量展开式”
若已知合适映射 ϕ ( ⋅ ) \phi(\cdot) ϕ(⋅)的具体形式,则可写成核函数 κ ( ⋅ , ⋅ ) \kappa(\cdot,\cdot) κ(⋅,⋅)
定理6.1(核函数):
令 χ \chi χ为输入空间, κ ( ⋅ , ⋅ ) \kappa(\cdot,\cdot) κ(⋅,⋅)是定义在 χ × χ \chi\times\chi χ×χ的对称函数,则 κ \kappa κ是核函数当且仅当对于任意数据 D = { x , , x 2 , . . . , x m } D=\{x_,,x_2,...,x_m\} D={x,,x2,...,xm},“核矩阵”(kernel matrix) K K K总是半正定的;
只要一个对称函数所对应的矩阵半正定,它总能作为核函数使用
对于一个半正定核矩阵,总能找到一个与之对应的映射 ϕ \phi ϕ
任意一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”(Reproducing Kernel Hilbert Space,简称RKHS)的特征空间
我们希望样本在特征空间内线性可分,因此特征空间的好坏对支持向量机的性能至关重要。
也可通过函数组合得到:
- 若
κ
1
\kappa_1
κ1和
κ
2
\kappa_2
κ2为核函数,则对于任意正数
γ
1
、
γ
2
\gamma_1、\gamma_2
γ1、γ2,其线性组合
γ 1 κ 1 + γ 2 κ 2 也是核函数 \begin{equation} \gamma_1\kappa_1+\gamma_2\kappa_2 \quad\quad\quad也是核函数 \tag{6.25} \end{equation} γ1κ1+γ2κ2也是核函数(6.25) - 若 κ 1 \kappa_1 κ1和 κ 2 \kappa_2 κ2为核函数,则核函数的直积
κ 1 ⊗ κ 2 ( x , z ) = κ 1 ( x , z ) κ 2 ( x , z ) 也是核函数 \begin{equation} \kappa_1\otimes\kappa_2(x,z)=\kappa_1(x,z)\kappa_2(x,z) \quad\quad\quad也是核函数 \tag{6.26} \end{equation} κ1⊗κ2(x,z)=κ1(x,z)κ2(x,z)也是核函数(6.26)
- 若 κ 1 \kappa_1 κ1为核函数,则对于任意函数 g ( x ) g(x) g(x)
κ 1 ( x , z ) = g ( x ) κ 1 ( x , z ) g ( z ) 也是核函数 \begin{equation} \kappa_1(x,z)=g(x)\kappa_1(x,z)g(z) \quad\quad\quad也是核函数 \tag{6.26} \end{equation} κ1(x,z)=g(x)κ1(x,z)g(z)也是核函数(6.26)
6.4软间隔与正则化
前面讨论在,假定存在一个超平面可将不同类样本完全分开。然而,现实中很难出现这种完美情况,缓解该问题办法是允许支持向量机在一些样本上出错,引出“软间隔”(soft margin)概念。
能否用对率损失函数来替代损失函数?
- 支持向量机与对率回归优化目标相近,通常性能相当
- 优势在于输出具有自然的概率意义
- 对率回归可直接用于多分类任务
- 对率回归的解依赖于更多的训练样本,预测开销更大
6.5支持向量回归
给定训练样本 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } , y i ∈ R D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\},y_i\in{R} D={(x1,y1),(x2,y2),...,(xm,ym)},yi∈R,希望学得一个形如(6.7) f ( x ) = w T + b f(x)=w^T+b f(x)=wT+b的回归模型,使得 f ( x ) f(x) f(x)与 y y y尽可能相近, w , b w,b w,b得求。
支持向量回归(Suport Vector Regressiom,SVR) 假设完美能容忍
f
(
x
)
f(x)
f(x)与
y
y
y之间最多有
ξ
\xi
ξ的偏差,仅当
f
(
x
)
f(x)
f(x)与
y
y
y之间差别绝对值大于
ξ
\xi
ξ才计算损失。
相当于以
f
(
x
)
f(x)
f(x)为中心,构建了一个宽度为
ξ
\xi
ξ的间隔带,若落入此带,则认为被预测正确,带中不计算损失
将(6.47)代入(6.7)
f
(
x
)
=
w
T
x
+
b
f(x)=w^Tx+b
f(x)=wTx+b中,则SVR解形如:
6.6核方法
更多推荐
所有评论(0)