• Chapter8 支持向量机

    1 理解支持向量机SVM的原理和目标（what） 

    1.1 原理

    SVM的基本原理时在特征空间中寻找间隔最大化的分离超平面的线性分类器。

    • 当训练样本线性可分，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机。
    • 当训练数据近似线性可分，可引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机。
    • 当训练数据线性不可分，通过核函数以及软间隔最大化，学习分线性支持向量机。

    1.2 目标

    找出所有样本距离无数条线性函数f(x,w,b)最小的距离，再中这些距离中找出最大距离所在的那条直线，即求取w,b的值

    如图所示：f(x,w,b)=sign(w\cdot x-b)，其中w,x代表向量。

    样本距离该函数之间的距离为：\frac{(w_{j}x^{(i)}+b_{j})y^{i}}{||w||}

    所以目标为：w^{*},b^{*}=arg max(\underset{i=1,2...n}{min}\frac{(w_{j}x^{(i)}+b_{j})y^{i}}{||w||})

    2 掌握支持向量机的计算过程和算法步骤（how）

    2.1 计算过程

    假设给定一个特征空间上的训练数据集T={(x_{1},y_{1}),(x_{2},y_{2})...(x_{N},y_{N})}，其中x_{i}\epsilon R^{n},y_{i}\epsilon (+1,-1),i=1,2...N；

    x_{i}表示为第i个实例（若n大于1，则x_{i}为向量）；

    y_{i}为x_{i}的类标记，即当y_{i}=+1时，x_{i}为正例，当y_{i}=-1时x_{i}为负例。

    (x_{i},y_{i})称为样本点。

    给定线性可分训练数据集，通过间隔最大化得到的分离超平面为y(x)=w^{T}\Phi (x)+b，相应的分类决策函数f(x)=sign(w^{T}\Phi (x)+b)，该决策函数称为线性可分支持向量机。

    \varphi (x)是某个确定的特征空间转换函数，它的作用是将x映射到（最高的）维度。

    求解分离超平面问题=求解相应的凸二次规划问题。

    （1）根据题设y(x)=w^{T}\Phi (x)+b，有当y(x_{i})>0\Leftrightarrow y_{i}=+1，y(x_{i})<0\Leftrightarrow y_{i}=-1

    从而y_{i}\cdot y(x_{i})> 0。【y(x_{i})为预测值 y_{i}为真实值】

     按一定的比例改变w,b（此时超平面的位置不会改变，但可以使得函数间隔改变），则t*y的值同样改变，从而：

    \frac{y_{i}\cdot y(x_{i})}{||w||}=\frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}，其中||w||为w的L_{2}范数。

    目标函数：\underset{w,b}{argmax}\left \{ \frac{1}{||w||}\underset{i}{min} [y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)]\right \}

    (2)(假如几何距离为B，即\frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}=B（B为常数）

    等式两边除以B：

    \frac{1}{B}\cdot \frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}=1，此时几何距离变成了1。

     通过等比例缩放w的方法，使得这两类点的函数值都满足|y| \geq 1，即约束条件。

     (3)因此原问题可以转化为以下问题:

    约束条件——y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)\geq 1,i=1,2,...,n

    原目标函数——\underset{w,b}{argmax}\left \{ \frac{1}{||w||}\underset{i}{min} [y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)]\right \}

    新目标函数——\underset{w,b}{argmax}\frac{1}{||w||}，即\underset{w,b}{max}\frac{1}{||w||}，即\underset{w,b}{min}\frac{1}{2}||w||^{2}

    （4）所用方法：拉格朗日乘子法

    设函数L(w,b,\alpha )=\frac{1}{2}||w||^{2}-\sum_{i=1}^{n}\alpha _{i}(y_{i}(w^{T}\cdot \Phi (x_{i})+b)-1)

    原问题是极小极大问题：\underset{w,b}{min}\underset{\alpha }{max}L(w,b,\alpha )

    原问题的对偶问题是极大极小问题：\underset{\alpha }{max}\underset{w,b}{min}L(w,b,\alpha )

    然后分别对w,b求偏导，令其为0：

    \frac{\partial L}{\partial w}=0 \Rightarrow w=\sum_{i=1}^{n}\alpha _{i}y_{i}\Phi (x_{n})

    \frac{\partial L}{\partial b }=0\Rightarrow 0=\sum_{i=1}^{n}\alpha _{i}y_{i}

    即在0=\sum_{i=1}^{n}\alpha _{i}y_{i}约束条件下求解： 

    添加负号变为求解：

     

    2.2 举例说明

     我们可以看到 \alpha _{2}=0，则x_{2}为非支持向量。

    2.3 拉格朗日乘子法

    约束条件：f_{i}(x)\leq 0,i=1,2,...,n，h_{j}(x)=0,j=1,2,...,m

    目标：min f(x)

    构造函数：G(x,\mu ,\lambda )=f(x)+\sum_{i=1}^{n}\mu _{i}f_{i}(x)+\sum_{i=1}^{m}\lambda _{j}h_{j}(x),其中\mu _{i}\geq 0,\lambda _{j}任意值。

    所以

    minf(x)=\underset{x}{min}(\underset{\mu _{i}\geq 0,\lambda \epsilon R}{max}G(x,\mu ,\lambda ))(原始问题)

    对偶函数为 \underset{\mu _{i}\geq 0,\lambda \epsilon R}{max}\underset{x}{min}G(x,\mu ,\lambda )

    所以接下来对\lambda求导，使其为0。

    3 理解软间隔最大化的含义

    当训练数据近似线性可分，可增加松弛变量\xi _{i}\geq 0，通过软间隔最大化，使得汉化间隔加上松弛变量大于等于1，这样约束条件就变成了y_{i}\cdot (w^{T}\cdot x_{i}+b)\geq 1-\xi _{i}，而目标函数就变为\underset{w,b}{min}\frac{1}{2}||w||^{2} + C\sum_{i=1}^{N}\xi _{i}

    C小则过渡带越宽，所以有泛化能力。C大时，为了目标函数最小，实际上需要使得\xi _{i}=0，即变成线性可分。

    所以：带松弛因子的SVM拉格朗日函数如下：

     

     

     ps:实际上损失函数为\sum_{i=1}^{n}\xi _{i}+\frac{1}{2}\cdot \lambda ||w||^{2}

    4 核函数

    4.1 定义

    可以使用核函数，将原始输入空间映射到新的特征空间，从而，使得原本线性不可分的样本可能在核空间可分。

    多项式核函数：k(x_{1},x_{2})=(x_{1}\cdot x_{2}+c)^{d}

    高斯核RBF函数：k(x_{1},x_{2})=exp(-\gamma \cdot ||x_{1}-x_{2}||^{2})

    Sigmoid核函数：k(x_{1},x_{2})=tanh(x_{1}\cdot x_{2}+c)

    在实际应用中，往往依赖先验领域知识/交叉验证等方案才能选择有效的核函数。

    没有更多先验信息，则使用高斯核函数。

    4.2 多项式核

    k(\overrightarrow{x},\overrightarrow{y})=(\overrightarrow{x}\cdot \overrightarrow{y}+c)^{2}

    (\overrightarrow{x}\cdot \overrightarrow{y}+c)^{2}=(\overrightarrow{x}\cdot \overrightarrow{y})^{2}+2c\overrightarrow{x}\cdot \overrightarrow{y}+c^{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}(x_{i}x_{j})(y_{i}y_{j})+\sum_{i=1}^{n}((\sqrt{2c})x_{i}\cdot (\sqrt{2c})x_{j})+c^{2}

    \Rightarrow \Phi (\overrightarrow{x})=(vec(x_{i}x_{j})|_{i,j=1}^{n},vec(\sqrt{2c}x_{j})|_{i=1}^{n},c)

    例如：当n=3时，\Phi (\overrightarrow{x})=\begin{bmatrix} x_{1}x_{1}\\ x_{1}x_{2}\\ x_{1}x_{3}\\ x_{2}x_{1}\\ x_{2}x_{2}\\ x_{2}x_{3}\\ x_{3}x_{1}\\ x_{3}x_{2}\\ x_{3}x_{3}\\ \sqrt{2c}x_{1}\\ \sqrt{2c}x_{2}\\ \sqrt{2c}x_{3}\\ c \end{bmatrix}

     

     5 总结

    （1）SVM可以用来划分多类别：若有1，2，3，4类，可以通过

    1 vs rest：1——234，2——134，3——124，4——123

    1 vs 1：1——2，1——3，1——4，2——3，2——4，4——4

    （2）SVM和Logistic回归的比较

    SVM：直接输出类别，不给出后验概率；

    Logistic回归：会给出属于哪个类别的后验概率。

    重点：两者目标函数的异同。

     

  • 相关阅读:
    OpenCV---视频操作
    （一）LTspice简介
    this 关键字
    Android 阿里云OSS 上传文件，使外网可以直接访问
    常见音频编码格式解析
    Shopee 一面算法题：颠倒给定的 32 位无符号整数
    java中继承的介绍
    matplotlib绘制动态正弦曲线
    【愚公系列】2022年09月 微信小程序-WebGL动画的使用
    Java 18的未来：新特性和编程实践
  • 原文地址：https://blog.csdn.net/qwertyuiop0208/article/details/126050379