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=1mα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)},yiR,希望学得一个形如(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.52),仅当样本不落入间隔带中,相应的

  将(6.47)代入(6.7) f ( x ) = w T x + b f(x)=w^Tx+b f(x)=wTx+b中,则SVR解形如:
在这里插入图片描述
在这里插入图片描述

6.6核方法

在这里插入图片描述
在这里插入图片描述在这里插入图片描述
在这里插入图片描述

  

  

  

  

  

  

  

  

  

  

Logo

助力广东及东莞地区开发者,代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展,成为松山湖开发者首选的工作与学习平台

更多推荐