机器学习导论6 支持向量机 [待修订]

分类:Machine Learning, 发布于:2019-04-03 14:05:04, 更新于:2019-04-19 00:12:14。 评论

历史

  • 神经网络 [89-94]: BP算法
  • 支持向量机 [95-05]: 核方法、统计学习
  • 神经网络 [06-?]: 深度学习
模型 支持向量机 神经网络
灵活性 灵活 更灵活
能力 能力强 能力强
理论依据 数学理论扎实 理论不清,来自认知
最优解 全局最优解 局部最优解
调参 不需要人工调参 依赖人工调参
计算开销 开销大 可大可小
通用性 领域知识嵌入困难 领域知识无处不在
领域 科学界 工业界

线性模型:在样本空间中寻找一个超平面将不同类样本分开。

Q:超平面有很多,选哪个好呢?

A:选择“正中间”,容忍性好,鲁棒性高,泛华能力最强。

间隔:过最近的样本与超平面$C: \boldsymbol{w}^T\boldsymbol{x}+b = 0$平行的超平面$S: \boldsymbol{w}^T\boldsymbol{x}+b = 1$与超平面$C$之间的距离。间隔定义为$\gamma = \dfrac{2}{\Vert \boldsymbol{w} \Vert}$

支持向量:距离超平面最近的几个样本点使得$\boldsymbol{w}^T\boldsymbol{x}+b = \pm 1$等号成立,称为“支持向量”。

最大间隔:寻找$\boldsymbol{w}$$b$,使得$\gamma$最大。(支持向量机的原始形式)

对偶问题

拉格朗日函数 $$L(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \dfrac{1}{2} \lVert \boldsymbol{w} \rVert^2 + \sum_{i=1}^m \alpha_i \left( 1 - y_i \left( \boldsymbol{w}^T \boldsymbol{x} + b \right)\right)$$

(推导见书本P123-124)

最终模型: $$f(\boldsymbol{x}) = \boldsymbol{w}^T \boldsymbol{x} + b = \sum_{i=1}^m \alpha_i y_i \boldsymbol{x_i}^T\boldsymbol{x} + b$$

求解方法:SMO (P124-125)

核函数

Q:如果不存在一个能正确划分两类样本的超平面,怎么办?

A:将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。

在映射后的特征空间中划分超平面所对应的模型可以表示为 $$f(\boldsymbol{x}) = \boldsymbol{w}^T\phi(\boldsymbol{x}) + b$$

核函数:$\kappa(\boldsymbol{x_i}, \boldsymbol{x_j} = \phi(\boldsymbol{x_i})^T \phi(\boldsymbol{x_j})$,只要一个对称函数所对应的核矩阵半正定,则它就能作为核函数来使用。

软间隔

在最大化间隔的同时,不满足约束的样本应该尽可能少。于是,优化目标可以写为

$$\min_{\boldsymbol{w}, b} \dfrac{1}{2} \lVert \boldsymbol{w} \rVert^2 + C \sum_{i = 1}^m \mathcal{l}_{0/1} \left( y_i \left( \boldsymbol{w}^T \boldsymbol{x}_i + b \right) - 1\right)$$

其中$C > 0$是一个常数,$\mathcal{l}_{0/1}$是“0/1损失函数”(P130),但其非凸、不连续,数学性质不好,所以通常用其他函数来替代,称为“替代损失”。

支持向量机的更一般的形式:

$$\min_{f} \Omega(f) + C \sum_{i = 1}^m \mathcal{l} \left( f(\boldsymbol{x}_i), y_i \right)$$

正则化问题与$L_p$范数(P133)

支持向量回归

(上课开火箭完全没听懂)

核方法

???(下课了)

评论