“机器学习3：支持向量机”

---

支持向量机，SVM的全称是Support Vector Machine
支持向量机算法是一种二分类模型
核心思想：找到空间中的一个能够将所有数据样本划开的超平面，并且使得所有数据到这个超平面的距离最短

一、支持向量机的前导基本概念

• $D_0$ 和 $D_1$ 是 $n$ 维欧氏空间中的两个点集
• 如果存在 $n$ 维向量 $w$ 和实数 $b$
• 使得所有属于 $D_0$ 的点都有 $w{x}_i+b>0$ ,
• 而对于所有属于 $D_1$ 的点则有 $w{x}_j+b<0$ ,
• 则称 $D_0$ 和 $D_1$ 线性可分
  
  分类器应选择”正中间”，容忍性好，鲁棒性高，泛化能力最强

1、SVM最优化问题的数学推导

点到线的距离

超平面公式演化

距离最大化

s.t. = subject to

2、拉格朗日乘数法

有约束优化问题的集合意象

拉格朗日乘数法定义——等式约束优化问题

• 拉格朗日乘数法(Lagrange multipliers,也译作拉格朗日乘子法)

  • 是一种寻找多元函数在一组约束下的极值的方法

• 多元函数微积分，以二元函数为例

  • 目标函数：z=f(x,y)

  • 约束条件：g(x,y)=0

    • 拉格朗日辅助函数： $L(x,y,\lambda )=f(x,y)+\lambda g(x,y)$ ，其中，实数为拉格朗日乘数

    • 求偏导数，令其为零，等到方程组：

      $$\begin{cases} L_x(x,y,\lambda)=f_x(x,y)+{\lambda}g_x(x,y)=0 \ L_y(x,y,\lambda)=f_y(x,y)+{\lambda}g_y(x,y)=0 \ L_{\lambda}(x,y,\lambda)=g_x(x,y)=0 \end{cases} \tag{1} 　$$

    • 解此方程组，得到结果： $(x,y)$

拉格朗日运算示例

3、凸优化问题

凸集

凸函数

• 凸函数同时满足以下条件
  　- 函数的定义域是向量空间 $R^n$ 上的凸集
  • 定义域内有任意两点 $x_1$ , $x_2$ ,并且，存在 $\theta \in (0,1)$ ，得：
    　　　　　　　　 $f(\theta x_1+(1-\theta )x_2)\le \theta f(x_1)+(1-\theta )f(x_2)$
    　　　　 那么函数 $f(x)$ 为凸函数

弦一定在函数曲线的上方

凸优化

• 凸优化：凸优化是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问
  题。其中

• 目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。

• 目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的　　　　　　优化问题为约束优化问题。

• 凸优化性质：
  1、目的是求取目标函数的最小值；
  2、目标函数和不等式约束函数都是凸函数，定义域是凸集;
  3、若存在等式约束函数，则等式约束函数为仿射函数；
  4、对于凸优化问题具有良好的性质，局部最优解便是全局最优解。

  $\underset{x}{min} f(x)$
  　　　　　　　　　　　　　　　　　　　　　　　　　 $s.t. h_i(x)=0(i=1,..,m),$
  　　　　　　　　　　　　　　　　　　　　　　　　　 $g_j(x)\le 0(j=1,..,n).$

KKT条件

4、拉格朗日对偶问题

• 拉格朗日对偶问题的思路演进
  • 有约束的原始目标函数优化问题
  • 新构造的拉格朗日目标函数优化问题
  • 拉格朗日对偶函数的优化问题

对偶问题

二、SVM最优化问题的计算

• 求阶SVM总共分为五步：
  • 1）构造拉格朗日函数
  • 2）构造拉格朗日对偶3）使用SMO算法
  • 4）计算参数值
  • 5）预测

SMO算法

• SMO(Sequential Minimal Optimization)算法
  　－序列最小优化算法
• 核心思想
  • 先固定住所有参数，然后放开一个参数
  • 每次只优化这一个参数
  • 仅求当前这个优化参数的极值

三、软间隔，核函数，SVM优缺点分析

1、软间隔

现实任务中很难使得训练样本在特征空间中线性可分

• 硬间隔约束条件： $y_i(w{x}_i+b)\ge 1$

  • 引入“松弛变量”(slack variables) ${\xi }_i\ge 0$ ，允许SVM在一些样本上出错，即允许某些样本不满足约束 $y_i(w{x}_i+b)\ge 1$
  • 在最大化间隔的同时，不满足约束的样本应尽可能少
    　
    　　　　　　　 $\underset{\omega ,b,{\xi }_i}{min}\frac{1}{2}||\omega |{|}^2+\lambda \sum _{i=0}^m{\xi }_i$
    　　　　　　　
    　　　　　　 $s.t. y_i(w^T{x}_i+b)\ge 1-{\xi }_i$
    　　　　　　
    　　　　　　　 ${\xi }_i\ge 0,i=1,2,...,m$
    　
    　　　　　 $\lambda$ 越大，模型对分类错误的容忍度越低
    　
    　　　　　 $\lambda$ 越小，模型对分类错误的容忍度越高

• hinge损失函数： $l_{hinge}(z)=max(0,1-z)$

2、核函数

线性不可分

非线性可分

建立空间直角坐标系

数据升维

• 通过核函数来升维
• 旧目标函数： $f(x)=wx+b$
• 新目标函数： $f(x)=w\varphi (x)+b$

常见的核函数

• 线性核函数： $K(x_i,x_j)=x_i\times x_j$

• 多项式核函数： $K(x_i,x_j)=(x_i\times x_j{)}^d$

• 高斯核函数： $K(x_i,x_j)=e^{(-\frac{||x_i-x_j||}{2{\delta }^2})}$

3、SVM的优缺点

• 优点
  1）有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
  2）能找出对任务至关重要的关键样本（即：支持向量）；
  3）采用核技巧之后，可以处理非线性分类/回归任务；
  4）最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
• 缺点
  1）训练时间长。当采用SMO算法时，由于每次都需要挑选一对参数，因此时间复杂度为 $O(N^2)$ ,其中N为训练样本的数量；
  2）当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 $O(N^2)$
  3）模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。

因此样本数量较大时,我们使用深度学习算法