当前位置: 首页 > news >正文

近似线性可分支持向量机的原理推导

近似线性可分的意思是训练集中大部分实例点是线性可分的,只是一些特殊实例点的存在使得这种数据集不适用于直接使用线性可分支持向量机进行处理,但也没有到完全线性不可分的程度。所以近似线性可分支持向量机问题的关键就在于这些少数的特殊点。

相较于线性可分情况下直接的硬间隔最大化策略,近似线性可分问题需要采取一种称为“软间隔最大化”的策略来处理。少数特殊点不满足函数间隔大于1的约束条件,近似线性可分支持向量机的解决方案是对每个这样的特殊实例点引入一个松弛变量 ξ i ⩾ 0 \xi_i \geqslant 0 ξi0 ,使得函数间隔加上松弛变量后大于等于1,约束条件就变为:
y i ( w ⋅ x i + b ) + ξ i ⩾ 1 (9-37) y_i(w \cdot x_i + b) + \xi_i \geqslant 1 \tag{9-37} yi(wxi+b)+ξi1(9-37)

对应的目标函数也变为:
1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i (9-38) \frac{1}{2} ||w||^2 + C \sum_{i=1}^{N} \xi_i \tag{9-38} 21∣∣w2+Ci=1Nξi(9-38)

其中 C C C 为惩罚系数,表示对误分类点的惩罚力度。

跟线性可分支持向量机一样,近似线性可分支持向量机可形式化为一个凸二次规划问题:
min ⁡ w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i s.t.  y i ( w ⋅ x i + b ) ≥ 1 − ξ i , i = 1 , 2 , ⋯ , N ξ i ≥ 0 , i = 1 , 2 , ⋯ , N (9-39) \begin{aligned} & \min_{w,b,\xi} \quad \frac{1}{2} \| w \|^2 + C \sum_{i=1}^{N} \xi_i \\ & \text { s.t. } \quad y_i (w \cdot x_i + b) \geq 1 - \xi_i, \quad i = 1, 2, \cdots, N \\ & \quad \xi_i \geq 0, \quad i = 1, 2, \cdots, N \tag{9-39} \end{aligned} w,b,ξmin21w2+Ci=1Nξi s.t. yi(wxi+b)1ξi,i=1,2,,Nξi0,i=1,2,,N(9-39)

类似于 9.2.1 节的线性可分离支持向量机的凸二次规划问题,我们同样将其转化为对偶问题进行求解。式(9-39)的对偶问题为:
min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s.t.  ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , ⋯ , N (9-40) \begin{aligned} & \min_{\alpha} \quad \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i \\ & \text { s.t. } \quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ & \quad 0 \leq \alpha_i \leq C, \quad i = 1, 2, \cdots, N \tag{9-40} \end{aligned} αmin21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαi s.t. i=1Nαiyi=00αiC,i=1,2,,N(9-40)

式(9-39)的拉格朗日函数为:
L ( w , b , ξ , α , μ ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i − ∑ i = 1 N α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − ∑ i = 1 N μ i ξ i (9-41) L(w, b, \xi, \alpha, \mu) = \frac{1}{2} \| w \|^2 + C \sum_{i=1}^{N} \xi_i - \sum_{i=1}^{N} \alpha_i (y_i (w \cdot x_i + b) - 1 + \xi_i) - \sum_{i=1}^{N} \mu_i \xi_i \tag{9-41} L(w,b,ξ,α,μ)=21w2+Ci=1Nξii=1Nαi(yi(wxi+b)1+ξi)i=1Nμiξi(9-41)

原始问题为极小极大化问题,则对偶问题为极大极小化问题。同样先对 L ( w , b , ξ , α , μ ) L(w, b, \xi, \alpha, \mu) L(w,b,ξ,α,μ) w , b , ξ w, b, \xi w,b,ξ 的极小,再对其求 α \alpha α 的极大。首先求 L ( w , b , ξ , α , μ ) L(w, b, \xi, \alpha, \mu) L(w,b,ξ,α,μ) 关于 w , b , ξ w, b, \xi w,b,ξ 的偏导,如下:
∂ L ∂ w = w − ∑ i = 1 N α i y i x i = 0 (9-42) \frac{\partial L}{\partial w} = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \tag{9-42} wL=wi=1Nαiyixi=0(9-42)

∂ L ∂ b = − ∑ i = 1 N α i y i = 0 (9-43) \frac{\partial L}{\partial b} = - \sum_{i=1}^{N} \alpha_i y_i = 0 \tag{9-43} bL=i=1Nαiyi=0(9-43)

∂ L ∂ ξ i = C − α i − μ i = 0 (9-44) \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \tag{9-44} ξiL=Cαiμi=0(9-44)

可解得:
w = ∑ i = 1 N α i y i x i (9-45) w = \sum_{i=1}^{N} \alpha_i y_i x_i \tag{9-45} w=i=1Nαiyixi(9-45)

∑ i = 1 N α i y i = 0 (9-46) \sum_{i=1}^{N} \alpha_i y_i = 0 \tag{9-46} i=1Nαiyi=0(9-46)

C − α i − μ i = 0 (9-47) C - \alpha_i - \mu_i = 0 \tag{9-47} Cαiμi=0(9-47)

将式(9-45)~式(9-47)代入式(9-41),有:

min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i (9-48) \min_{w,b,\xi} \quad L(w, b, \xi, \alpha, \mu) = - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^{N} \alpha_i \tag{9-48} w,b,ξminL(w,b,ξ,α,μ)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi(9-48)

然后对 min ⁡ w , b , ξ \min_{w,b,\xi} minw,b,ξ L ( w , b , ξ , α , μ ) L(w,b,\xi,\alpha,\mu) L(w,b,ξ,α,μ) α \alpha α 的极大,可得对偶问题为:

max ⁡ α L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 C − α i − μ i = 0 α i ≥ 0 μ i ≥ 0 , i = 1 , 2 , … , N (9-49) \begin{aligned} & \max_\alpha L(w,b,\xi,\alpha,\mu) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i \\ & s.t. \quad \sum_{i=1}^N \alpha_i y_i = 0 \\ & \quad C - \alpha_i - \mu_i = 0 \\ & \quad \alpha_i \geq 0 \\ & \quad \mu_i \geq 0, \quad i = 1, 2, \dots, N \tag{9-49} \end{aligned} αmaxL(w,b,ξ,α,μ)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαis.t.i=1Nαiyi=0Cαiμi=0αi0μi0,i=1,2,,N(9-49)

将式(9-49)的第2~4个约束条件式进行变换,消除变量 μ i \mu_i μi 后可简化约束条件为:
0 ≤ α i ≤ C (9-50) 0 \leq \alpha_i \leq C \tag{9-50} 0αiC(9-50)

联合式(9-48)和式(9-49),并将极大化问题转化为极小化问题,即式(9-40)的对偶问题。跟线性可分支持向量机求解方法一样,近似线性可分问题也是通过求解对偶问题而得到原始问题的解,进而确定线性分隔超平面和分类决策函数。

假设 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) T \alpha^* = (\alpha_1^*, \alpha_2^*, \dots, \alpha_N^*)^T α=(α1,α2,,αN)T 是对偶最优化问题式(9-40)的解,根据拉格朗日对偶理论相关推论,式(9-40)满足KKT(Karush-Kuhn-Tucker)条件,有:
∂ L ∂ w = w ∗ − ∑ i = 1 N α i ∗ y i x i = 0 (9-51) \frac{\partial L}{\partial w} = w^* - \sum_{i=1}^N \alpha_i^* y_i x_i = 0 \tag{9-51} wL=wi=1Nαiyixi=0(9-51)

∂ L ∂ b = − ∑ i = 1 N α i ∗ y i = 0 (9-52) \frac{\partial L}{\partial b} = -\sum_{i=1}^N \alpha_i^* y_i = 0 \tag{9-52} bL=i=1Nαiyi=0(9-52)

∂ L ∂ ξ = C − α ∗ − μ ∗ = 0 (9-53) \frac{\partial L}{\partial \xi} = C - \alpha^* - \mu^* = 0 \tag{9-53} ξL=Cαμ=0(9-53)

α i ∗ ( y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ ) = 0 (9-54) \alpha_i^*(y_i(w^* \cdot x_i + b^*) - 1 + \xi_i^*) = 0 \tag{9-54} αi(yi(wxi+b)1+ξi)=0(9-54)

μ i ∗ ξ i ∗ = 0 (9-55) \mu_i^* \xi_i^* = 0 \tag{9-55} μiξi=0(9-55)

y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ ≥ 0 (9-56) y_i(w^* \cdot x_i + b^*) - 1 + \xi_i^* \geq 0 \tag{9-56} yi(wxi+b)1+ξi0(9-56)

ξ i ∗ ≥ 0 (9-57) \xi_i^* \geq 0 \tag{9-57} ξi0(9-57)

α i ∗ ≥ 0 (9-58) \alpha_i^* \geq 0 \tag{9-58} αi0(9-58)

μ i ∗ ≥ 0 , i = 1 , 2 , … , N (9-59) \mu_i^* \geq 0, \quad i = 1, 2, \dots, N \tag{9-59} μi0,i=1,2,,N(9-59)

可解得:
w ∗ = ∑ i = 1 N α i ∗ y i x i (9-60) w^* = \sum_{i=1}^N \alpha_i^* y_i x_i \tag{9-60} w=i=1Nαiyixi(9-60)

b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) (9-61) b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i (x_i \cdot x_j) \tag{9-61} b=yji=1Nαiyi(xixj)(9-61)

以上就是近似线性可分支持向量机的基本推导过程。从过程来看,近似线性可分问题求解推导与线性可分问题的求解推导非常类似。


以下是部分公式更加详细的解释:
公式 9-37
公式 9-38
公式 9-40
公式 9-41
公式 9-50
公式 9-51 ~ 9-59

http://www.lryc.cn/news/473019.html

相关文章:

  • Golang开发环境
  • 测试华为GaussDB(DWS)数仓,并通过APISQL快速将(表、视图、存储过程)发布为API
  • 使用GetX实现GetPage中间件
  • Navicat 17 功能简介 | SQL 预览
  • ubuntu、Debian离线部署gitlab
  • 数据库编程 SQLITE3 Linux环境
  • 独孤思维:总有一双眼睛默默观察你做副业
  • 医院信息化与智能化系统(10)
  • 基于YOLO11/v10/v8/v5深度学习的危险驾驶行为检测识别系统设计与实现【python源码+Pyqt5界面+数据集+训练代码】
  • Flink CDC系列之:学习理解核心概念——Transform
  • MyBatis-Plus:简化 CRUD 操作的艺术
  • Windows on ARM编译安装openBLAS
  • FPGA编程语言VHDL与Verilog的比较分析!!!
  • C语言——八股文(笔试面试题)
  • 解决 Oracle 数据库错误 ORA-12516:监听器无法找到匹配协议栈的处理程序
  • Flarum:简洁而强大的开源论坛软件
  • 方法+数组
  • 驱动-----adc
  • js实现点击图片,使图片跟随鼠标移动(把注释打开是图片随机位置)
  • MacOS的powermetrics命令查看macbook笔记本的耗能情况,附带查看ANE的工作情况
  • 字符串函数
  • Java数组的地址和元素访问 C语言空指针与野指针
  • 如何在Linux系统中使用SSH进行安全连接
  • Pandas 数据可视化指南:从散点图到面积图的全面展示
  • Flink + Kafka 实现通用流式数据处理详解
  • Docker常用命令汇总
  • 【Java笔记】0-为什么学习Java
  • 海外云手机是什么?对外贸电商有什么帮助?
  • 【找到了】有人知道怎么在本地用记事本方式打开Linux文本文件吗?
  • docker 安装postgresql