图解机器学习读书笔记-CH8:SVM分类

间隔最大化分类

考虑二分类:
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存在时,称训练样本线性可分.

硬间隔SVM

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

2018-08-29 at 上午9.38.png
  • 正则化间隔m_i:
    m_i = \frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}
  • m_i最大化:
    \max\left\{\frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}\right\}_{I=1}^n = \frac{1}{\|\omega\|}

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

软间隔SVM

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

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

通常的SVM指软间隔SVM.

2018-08-29 at 上午9.44.png

SVM分类器求解

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

二次规划求解

导入拉格朗日变量:
L( \omega, \gamma, \xi, \alpha, \beta) = \frac{1}{2}\|\delta\|^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}L = 0 => \alpha_i + \beta_i = C, \forall i=1,\cdots,n

消去松弛变量\varepsilon可得拉格朗日对偶问题如下公式:

\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^T \right]\; 约束条件\;\sum_{i=1}^n\alpha_iy_i = 0, 0 \le \alpha_i \le C\;, \forall i = 1,\cdots,n
上述最优化问题, 利用只有n个最优变量的二次规划问题, 求解比原始最优化问题跟高效. 原始的最优化问题:
min_{\omega,\gamma,\varepsilon}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\varepsilon_i\right]\; 约束条件\;(\omega^Tx_i + \gamma)y_i \ge 1- \varepsilon_i, \varepsilon_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

稀疏性

KKT条件

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

KKT条件

核映射非线性模型

核映射使得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)

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

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) ]

Ramp损失的鲁棒学习

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容