机器学习算法深度总结(4)-SVM

2018-10-08 本文已影响37人婉妃

1. 间隔最大化分类

考虑二分类:
$f_{\omega,\gamma}(x) = \omega^Tx + \gamma$
$\omega$ 为分割样本的超平面的法线, $\gamma$ 为截距.

2018-08-29 at 上午9.27.png

对各样本间隔 $m_i=f_{\omega, \gamma}(x_i)y_i$ 为正时的 $\omega$ 和 $\gamma$ 学习.

闭集约束条件: $(\omega^Tx_i+\gamma)y_i \ge 1, \forall i = 1, \cdots, n$

以上 $\omega$ 和 $\gamma$ 存在时,称训练样本线性可分.

2. 硬间隔SVM

分割最充分的超平面为最优解, 对应正则化后的间隔的最小值:

2018-08-29 at 上午9.38.png

正则化间隔 $m_i$ :
$m_i = \frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}$
$m_i$ 最小化:
$min\left\{\frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}\right\}_{I=1}^n = \frac{1}{\|\omega\|}$

从几何学来讲, 间隔为两端的两个超平面 $\omega^Tx+\gamma=+1$ 和 $\omega^Tx+\gamma=-1$ 的间距的一半, 使这个间隔最大的超平面对应的分类器称为硬间隔支持向量机分类器:

3. 软间隔SVM

硬间隔SVM假定训练样本线性可分, 软件个SVM允许间隔计算出现少量误差:
$min_{\omega,\gamma,\varepsilon}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\xi_i\right]\; 约束条件\;(\omega^Tx_i + \gamma)y_i \ge 1- \xi_i, \xi_i =\ge 0,\forall i=1,\cdots, n$

C>0是调整误差范围参数, C越大, $\sum_{i=1}^n\xi_i$ 越接近0, 软间隔SVM越接近硬间隔SVM.

通常的SVM指软间隔SVM.

2018-08-29 at 上午9.44.png

4. SVM求解

SVM最优化问题是目标函数为二次函数, 约束条件为线性的典型二次规划问题:

二次规划求解

导入拉格朗日变量:
$L( \omega, \gamma, \xi, \alpha, \beta) = \frac{1}{2}\|\omega\|^2 + C \sum_{i=1}^n\xi_i - \sum_{i=1}^n\alpha_i \left( ( \omega^T x_i+\gamma)y_i - 1 + \xi_i \right) - \sum_{i=1}^n\beta_i\xi_i$
考虑最优化问题等价表现形式--拉格朗日对偶问题:
$\underset{ \alpha, \beta}{max} \; \underset{ \omega, \gamma, \xi}{inf}\; L( \omega, \gamma, \xi, \alpha, \beta)\; s.t.\; \alpha \ge 0, \beta \ge 0$
根据最优解条件可得:
$\frac{\partial }{\partial \omega}L = 0 => \omega = \sum_{i=1}^n\alpha_iy_ix_i \\ \frac{\partial }{\partial \gamma}L = 0 => \sum_{i=1}^n\alpha_iy_i = 0 \\ \frac{\partial }{\partial \xi_i}L = 0 => \alpha_i + \beta_i = C, \forall i=1,\cdots,n$
消去松弛变量 $\xi_i$ 可得拉格朗日对偶问题如下公式:
$\hat \alpha = \underset{\alpha}{argmax}\left[\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \right]\; 约束条件\;\sum_{i=1}^n\alpha_iy_i = 0, 0 \le \alpha_i \le C\;, \forall i = 1,\cdots,n$
上述最优化问题, 利用只有n个最优变量的二次规划问题, 求解比原始最优化问题跟高效. 原始的最优化问题:
$min_{\omega,\gamma,\xi}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\xi_i\right]\; 约束条件\;(\omega^Tx_i + \gamma)y_i \ge 1- \xi_i, \xi_i =\ge 0,\forall i=1,\cdots, n$

拉格朗日对偶问题的解用 $\hat \alpha$ 表示, 则SVM的解 $\hat \omega$ 为:
$\hat\omega = \sum_{i=1}^n\hat \alpha_iy_i\mathbf x_i$
截距的解 $\hat \gamma$ :
$\hat \gamma = y_i - \sum_{j:\hat \alpha_i>0} \hat \alpha_jy_jx_i^Tx_j$

5. 稀疏性

KKT条件
对偶解的最优条件即KKT条件. 对偶变量和约束条件满足互补关系:
$\alpha_i(m_i-1+\xi_i) = 0,\beta_i\xi_i = 0,\forall i = 1, \cdots, n$
KKT条件:

KKT条件

6. 核映射

核映射非线性模型
核映射使得SVM可以应用于非线性模型. 使用非线性函数 $\psi$ 对输入样本 $\{x_i\}_{=1}^n$ 使用线性SVM分类器.这种特征空间内的线性分类器, 在输入空间是非线性分类器.

如果特征空间维数比输入空间维数d更高,则样本线性可分的可能性更大, 然而特征空间维数过大, 计算量也会响应增加.

核映射可显著降低计算量: 学习时, 线性SVM分类器样本空间输入只存在内积形式 $x_i^Tx_j=\langle x_i,x_j \rangle$ ; 非线性SVM分类器特征空间输入只存在内积形式 $\langle \psi(x_i), \psi(x_j) \rangle$

核映射优势:

通过核函数 $K( x,x')$ 定义内积 $\langle \psi(x_i), \psi(x_j)\rangle$ , 不需要知道特征变换 $\psi$ 具体是什么.
输入 $x$ 不是向量, 也可以正确分类.

常见的核函数:
多项式核函数
$K( x, x') = ( x^Tx' + c)^p$
高斯核函数
$K( x, x') = \exp\left(- \frac{\| x -x'\|^2}{2h^2}\right)$

核映射方法适用于只关注内积的任何算法, 如聚类分析, 降维,将现行算法轻松转化为非线性.

7. hinge损失的二乘求解

考虑将SVM分类作为最小二乘分类的扩展.
SVM分类器将0/1损失作为间隔 $m = f_\theta( x)y$ 的函数单调非增, 但是二乘 $L_2$ 损失不是单调非增, 直接应用有些不自然, 故考虑将如下Hinge损失作为代理损失:
$max\{0, 1-m\}$
Hinge损失在m<1时有线性递增趋势, 即分类错误时, 损失无穷递增

Hinge损失和0/1损失函数图像:

Hinge损失和0/1损失

Hinge损失最小化学习:
$min_{\theta} = \sum_{i=1}^nmax\{0, 1-f_{\theta}( x_i)y_i\}$

回顾线性分类问题和和模型分类问题
线性分类:
$f_{\omega, \gamma}(x) = \omega^Tx+\gamma = \sum_{i=1}^n\omega_ix_i + \gamma$

核模型分类问题:
$f_{\theta, \gamma} = \sum_{j=1}^n\theta_jK(x,x_j)+\gamma$

对核模型分类问题进行Hinge损失最小化学习, 引入核矩阵 $K_{i,j} = K(x_i, x_j)$ 的 $L_2$ 正则化项:
$\underset{\theta, \gamma}{min}[ C\sum_{i=1}^nmax\{0, 1- f_{\theta, \gamma}(x_i)y \} + \frac{1}{2}\sum_{i,j=1}^n\theta_i\theta_jK(x_i, x_j) ]$