• 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回归：会给出属于哪个类别的后验概率。

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

     

  • 相关阅读:
    为了方便问题的快速定位，如您在使用
    计算机网络第5章（传输层）----总结1
    莫名其妙: conda错误ko及总结
    Nginx（反向代理，负载均衡，动静分离）
    golang中的string与其他格式数据的转换方法
    艾美捷内毒素水平＜0.1 EU/mg的卵清蛋白(OVA)
    快速掌握数据分析思路
    JAVA多线程
    一键生成PDF即刻呈现：轻松创建无忧体验
    xshell安装完成在windows不能打开
  • 原文地址：https://blog.csdn.net/qwertyuiop0208/article/details/126050379