ML——SVM-支持向量机

手动推导流程

假设有N样本:$X = (x_{1}, x_{2}, x_{3},\dots x_{N})$
- 样本点为: $((x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}),\dots (x_{N}, y_{N}))$
假设$x_{i}$等所有向量都为列向量, $w$为行向量(这里是为了推到方便,与<<统计学习方法>>一致)
- 实际代码实现时与行列向量无关,取二者的内积np.inner(w,x)即可

确定分类决策函数

分类超平面
$$w^{\star}x + b^{\star} = 0$$
- 分类超平面由$(w, b)$唯一确定(注意: LR的分类超平面由$(w, b)$和阈值唯一确定)
分类决策函数
$$f(x) = sign(w^{\star}x + b^{\star})$$

确定优化目标

间隔定义

函数间隔定义
- 点$(x_{i}, y_{i})$到超平面$(w,b)$的函数间隔为:
  $$\hat{\gamma}_{i} = y_{i}(w\cdot x_{i} + b)$$
- 所有训练样本$X = (x_{1}, x_{2}, x_{3},\dots x_{m})$到超平面$(w,b)$的函数间隔为:
  $$\hat{\gamma} = \min_{i=1,\dots,N}\hat{\gamma}_{i}$$
几何间隔的定义
- 点$(x_{i}, y_{i})$到超平面$(w,b)$的几何间隔为:
  $$\gamma_{i} = y_{i} (\frac{w}{||w||}\cdot x_{i} + \frac{b}{||w||})$$
- 进一步推导得:
  $$\gamma_{i} = \frac {y_{i}(w\cdot x_{i} + b)}{||w||} = \frac{\hat{\gamma}}{||w||}$$
- 所有训练样本$X = (x_{1}, x_{2}, x_{3},\dots x_{m})$到超平面$(w,b)$的几何间隔为:
  $$\gamma = \min_{i=1,\dots,N}\gamma_{i}$$

确定优化目标

求解能够正确划分训练数据集并且几何间隔最大的分类超平面(分离超平面)
定义约束优化问题:
$$
\begin{align}
&\max_{w,b} \quad \gamma \\
&s.t. \quad y_{i} (\frac{w}{||w||}\cdot x_{i} + \frac{b}{||w||}) \geq \gamma, i = 1,2,\dots,N
\end{align}
$$
将$\gamma = \frac{\hat{\gamma}}{||w||}$带入并在条件中消去分母上的$||w||$,得
$$
\begin{align}
&\max_{w,b} \quad\frac{\hat{\gamma}}{||w||} \\
&s.t.\quad y_{i} (w\cdot x_{i} + b) \geq \hat{\gamma}, i = 1,2,\dots,N
\end{align}
$$
上面的式子中,函数间隔$\hat{\gamma}$的值不影响最优化问题的解,于是我们设置$\hat{\gamma}=1$
- 因为将参数$(w,b)$同时扩大或缩小为$(\lambda w,\lambda b)$, 函数间隔对应变成$\lambda \hat{\gamma}$
- 两个等价的优化方法:
  - 设置$\hat{\gamma}=1$再对原始问题进行最优化得到参数$(w^{\star},b^{\star})$
  - 先对原始问题最优化求得参数$(w,b)$,再将参数同时扩大或缩小为$(\lambda w,\lambda b)$,使得$\lambda \hat{\gamma}=1$得到的最终参数$(w^{\star},b^{\star}) = (\lambda w,\lambda b)$等价
    $$
    \begin{align}
    &\max_{w,b}\quad \frac{1}{||w||} \\
    &s.t.\quad y_{i} (w\cdot x_{i} + b) \geq 1, i = 1,2,\dots,N
    \end{align}
    $$
进一步分析,由于最大化$\frac{1}{||w||}$与最小化$\frac{1}{2}||w||^{2}$等价(这里$w$为行向量时,$||w||^{2} = ww^{T}$), 最优化问题可等价表示为:
$$
\begin{align}
&\min_{w,b}\quad \frac{1}{2}||w||^{2} \\
&s.t.\quad y_{i} (w\cdot x_{i} + b) \geq 1, i = 1,2,\dots,N
\end{align}
$$
- 这是一个凸二次规划问题(convex quadratic programming),凸优化问题参考Math——凸二次优化问题和拉格朗日对偶性

优化问题的求解(对偶)

首先将SVM优化问题转换为一般凸优化形式
$$
\begin{align}
&\min_{w,b}\quad \frac{1}{2}||w||^{2} \\
&s.t.\quad 1 - y_{i} (w\cdot x_{i} + b) \leq 0, i = 1,2,\dots,N
\end{align}
$$
由上述优化问题定义拉格朗日函数
$$
\begin{align}
L(w,b,\alpha) = \frac{1}{2}||w||^{2} + \sum_{i=1}^{N}\alpha_{i}(1-y_{i}(w\cdot x_{i} + b))
\end{align}
$$
根据拉格朗日对偶性,
$$
\begin{align}
\min_{w,b}\max_{\alpha:\alpha_{i} \geq 0}L(w,b,\alpha) = \max_{\alpha:\alpha_{i} \geq 0}\min_{w,b}L(w,b,\alpha)
\end{align}
$$
- 左边:原始问题为极小极大问题
- 右边:对偶问题为极大极小问题
解对偶问题:
先求
$$
\begin{align}
\min_{w,b}L(w,b,\alpha)
\end{align}
$$
求导数为0得
$$
\begin{align}
\nabla_{w}L(w,b,\alpha) &= w - \sum_{i=1}^{N}\alpha_{i}y_{i}x_{i} = 0 \\
\nabla_{b}L(w,b,\alpha) &= \sum_{i=1}^{N}\alpha_{i}y_{i} = 0
\end{align}
$$
解得:
$$
\begin{align}
&w = \sum_{i=1}^{N}\alpha_{i}y_{i}x_{i} \\
&\sum_{i=1}^{N}\alpha_{i}y_{i} = 0
\end{align}
$$
代入原来的拉格朗日函数有:

$$
\begin{align}
\min_{w,b}L(w,b,\alpha) &= \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}(1-y_{i}(\left [\sum_{j=1}^{N}\alpha_{j}y_{j}x_{j}\right]\cdot x_{i} + b)) \\
&= \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}y_{i}\left [\sum_{j=1}^{N}\alpha_{j}y_{j}x_{j}\right]\cdot x_{i} + \sum_{i=1}^{N}\alpha_{i}y_{i}b + \sum_{i=1}^{N}\alpha_{i}\\
&= \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}\sum_{j=1}^{N}\alpha_{i}y_{i}\alpha_{j}y_{j}(x_{j}\cdot x_{i}) + \sum_{i=1}^{N}\alpha_{i}y_{i}b + \sum_{i=1}^{N}\alpha_{i}\\
&= -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}(x_{i}\cdot x_{j}) + 0 + \sum_{i=1}^{N}\alpha_{i}\\
&= -\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}
\end{align}
$$

上面的$\min_{w,b}L(w,b,\alpha)$对$\alpha$求极大值有:
$$
\begin{align}
\max_{\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} \\
s.t. \quad &\sum_{i=1}^{N}\alpha_{i}y_{i} = 0 \\
\quad &\alpha_{i} \geq 0, i = 1,2,\dots,N
\end{align}
$$
转换为一般优化问题
$$
\begin{align}
\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} \\
s.t. \quad &\sum_{i=1}^{N}\alpha_{i}y_{i} = 0 \\
\quad &-\alpha_{i} \leq 0, i = 1,2,\dots,N
\end{align}
$$
假设上面的式子能够求得$\alpha$的解为:
$$
\begin{align}
\alpha^{\star} = (\alpha_{1}^{\star}, \alpha_{2}^{\star},\dots, \alpha_{N}^{\star})
\end{align}
$$
根据拉格朗日对偶问题与原始问题的解对应的条件,Math——凸优化问题和拉格朗日对偶性,如果上面的式子中存在下标$j$,满足$-\alpha_{j}^{\star} < 0$,即满足:
$$\exists j \quad \alpha_{j}^{\star} > 0$$
那么最终可求得:
$$
\begin{align}
&w^{\star} = \sum_{i=1}^{N}\alpha_{i}^{\star}y_{i}x_{i} \\
\end{align}
$$
$b^{\star}$的表达式由$\alpha_{j}^{\star} > 0$,和KKT条件$\alpha_{j}^{\star}(y_{j}(w^{\star}\cdot x_{j} + b^{\star})-1) = 0$可解得:
$$
\begin{align}
y_{j}(w^{\star}\cdot x_{j} + b^{\star})-1 = 0 \\
\end{align}
$$
注意到$y_{j}\in \{-1, 1\}$, 所以$y_{j}^{2}=1$
$$
\begin{align}
y_{j}^{2}(w^{\star}\cdot x_{j} + b^{\star})-y_{j} = 0 \\
w^{\star}\cdot x_{j} + b^{\star} = y_{j} \\
\end{align}
$$
所以有
$$
\begin{align}
b^{\star} &= y_{j} - w^{\star}\cdot x_{j} \\
&= y_{j} - \sum_{i=1}^{N}\alpha_{i}^{\star}y_{i}(x_{i}\cdot x_{j})
\end{align}
$$
综合$w^{\star}$和$b^{\star}$的表达式,我们有分类超平面为:
$$
\begin{align}
w^{\star}x + b^{\star} &= 0 \\
\sum_{i=1}^{N}\alpha_{i}^{\star}y_{i}(x_{i}\cdot x) + b^{\star} &= 0
\end{align}
$$
分类决策函数为:
$$
\begin{align}
f(x) &= sign(w^{\star}x + b^{\star}) \\
f(x) &= sign\left (\sum_{i=1}^{N}\alpha_{i}^{\star}y_{i}(x_{i}\cdot x) + b^{\star}\right )
\end{align}
$$
- 这就是分线性可分SVM的对偶形式
- 分类决策函数只与待预测的样本$x$和已有训练数据$x_{j}$的输入内积$(x_{j}\cdot x)$相关
  - 注意$b^{\star}$是通过原始训练样本算出来的定值,$b^{\star}, w^{\star}$的值与待预测的未知样本无关,训练样本确定,参数就确定了, 内积的出现是在加入位置样本后$w^{\star}\cdot x$产生的
- SVM的对偶形式使得我们可以用核函数来扩展SVM(非线性核函数可使得SVM能解决非线性问题)

支持向量

优化问题的推导过程中,又一步,对偶问题与原始问题能够相等的条件是存在下标$j$,满足$-\alpha_{j}^{\star} < 0$,即满足:
$$\exists j \quad \alpha_{j}^{\star} > 0$$
上面的$j$对应的样本点$(x_{j}, y_{j})$就是支持向量
- 支持向量一定在间隔边界上:
  $$y_{j}(w^{\star}\cdot x_{j}+b^{\star})-1 = 0$$
- 或者
  $$w^{\star}\cdot x_{j}+b^{\star} = \pm 1$$
  - $y_i$ 的取值为 1 或者 -1
- 实际上,在训练时参数$(w^{\star}, b^{\star})$只依赖于$\alpha_{j} > 0$的点,即只依赖支持向量
  $$
  \begin{align}
  &w^{\star} = \sum_{i=1}^{N}\alpha_{i}^{\star}y_{i}x_{i} \\
  &b^{\star} = y_{j} - \sum_{i=1}^{N}\alpha_{i}^{\star}y_{i}(x_{i}\cdot x_{j})
  \end{align}
  $$
- 所有非支持向量对应的$\alpha_{i} = 0$,所以对最终参数$(w^{\star}, b^{\star})$只与支持向量相关

核函数

$\phi(x)$定义为从输入空间到希尔伯特空间的映射
$$
\begin{align}
K(x,z) = \phi(x)\phi(z)
\end{align}
$$
将SVM对偶形式中的内积$(x_{i}\cdot x_{j})$用核函数$K(x_{i},x_{j}) = \phi(x_{i})\phi(x_{j})$来替代即可在SVM中应用核技巧

常用核函数

多项式核函数
$$K(x,z) = (x\cdot z + 1)^{p}$$
高斯核函数
$$K(x,z) = e^{\left( -\frac{||x-z||^{2}}{2\sigma^{2}}\right )}$$
字符串核函数
[待更新]

序列最小最优化算法(SMO)

为什么要用SMO?
- 前面我们的推导将 SVM的参数求解 转化为了一个求解凸二次优化的问题
- 凸二次优化问题有全局最优解(有很多优化算法可以求解凸二次优化问题)
- 但是当样本量太大时,普通的凸二次优化算法会变得十分低效,导致实际操作中无法使用
- 所以我们需要一个能高效实现的算法 SMO
基本思路
- 如果所有变量的解都满足最优化问题的KKT条件,那么这个最优化问题的解就得到了
  - 原因: KKT条件是该最优化问题的充要条件
- 否则,存在某些解不满足KKT条件,选择两个变量,固定其他变量,
  - 两个变量中其中一个是最不满足KKT条件的变量,
  - 另一个在第一个确定后,自动由约束条件确定下来
- 针对这两个变量构建二次规划问题的解,这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解
  - 原因: 因为二次规划问题的目标函数值变得更小
  - 此时可通过解析方法求解(由于只有两个变量,比较简单),整个算法的速度会很快
- SMO算法不断的将原问题分解为子问题,迭代更新参数,每次更新两个参数,最终得到近似解
优点:
- 训练速度快

补充说明

SVM需要特征归一化

是必要的

因为SVM寻找的是所谓的间隔(margin), 就是两个支持向量的间隔
如果不归一化的话, 这个间隔会因为不同特征的单位等, 数值被放大或者缩小, 从而造成无法评估间隔, 所以归一化对于SVM很重要
线性SVM依赖数据表达的距离测度，所以需要对数据先做normalization
- 个人理解: 非线性的SVM其实也应该归一化,不然核函数映射到高位空间后以后还是可能受数值影响?

损失函数自带正则

由于优化目标中就自带了参数 $\frac{1}{2}||w||^2$, 所以SVM实际上已经自己带了L2正则化了
这也是SVM也叫结构风险最小化算法的原因
- 结构风险最小化就是模型复杂度最小化