Ch07
ZhuYuanxiang
2020-10-12 18:15:39
Categories：
Tags：
C07. 支持向量机
- 支持向量机 ( Support Vector Machine， SVM ) 是一种二类分类模型。
- 基本模型是定义在特征空间上的间隔最大的线性分类器
- 基本概念
- 支持向量决定了最优分享超平面
- 最终判别时，只需要很少的“重要”训练样本，大幅减少计算量。
- 间隔 ( 看懂数学公式就可以理解间隔，判别在数据的维度上又增加了一个维度 )
- 与其他模型的比较
- 与感知机的区别 : 间隔最大化产生最优超平面；
- 与线性模型的区别 : 使用核技巧成为非线性分类器。
- 分类
- 线性可分支持向量机，硬间隔支持向量机。
- 线性支持向量机，软间隔支持向量机，是最基本的支持向量机。
- 非线性支持向量机
- 学习
- 线性可分支持向量机 (linear support vector machine in linearly separable case)
- 条件 : 训练数据线性可分；
- 学习策略 : 硬间隔最大化
- 求解能够正确划分训练数据集并且几何间隔最大的分离超平面
- 对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类
- 这样的超平面对未知原新实例有很好的分类预测能力
- 解的特征
- 最优解存在且唯一； ( _唯一性证明_，建议跳过 )
- 支持向量由位于间隔边界上的实例点组成；
- 线性支持向量机 (linear support vector machine)
- 条件
- 训练数据近似线性可分；
- 训练数据中存在一些特异点 (outlier)
- 学习策略 : 软间隔最大化
- 惩罚参数 C * 替代损失函数 f，表示误判的代价；
- hinge 损失 ( 合页损失函数 ) : 保持了稀疏性
- 指数损失
- 对率损失 : 相似于对率回归模型
- 目标是使间隔尽量大，误分类点尽量少。
- 解的特征
- 权值唯一，偏置不唯一；
- 支持向量由位于间隔边界上的实例点、间隔边界与分离超平面之间的实例点、分离超平面误分一侧的实例点组成；
- 最优分享超平面由支持向量完全决定。
- 非线性支持向量机 (non-linear support vector machine)
- 基本概念
- 线性空间 : 满足线性性质的空间
- 距离 : 是一种度量
- 距离的集合 ⟶ 度量空间 + 线性结构 ⟶ 线性度量空间
- 范数 : 表示某点到空间零点的距离
- 范数的集合 ⟶ 赋范空间 + 线性结构 ⟶ 线性赋范空间
- 内积空间 : 添加了内积运算的线性赋范空间
- 欧氏空间 : 有限维的内积空间
- 希尔伯特空间 : 内积空间满足完备性，即扩展到无限维
- 巴拿赫空间 : 赋范空间满足完备性
- 条件 :
- 训练数据非线性可分；
- 通过非线性变换 ( 核函数 ) 将输入空间 ( 欧氏空间或离散集合 ) 转化为某个高维特征空间 ( 希尔伯特空间 ) 中的线性可分；
- 在高维特征空间中学习线性支持向量机。
- 学习策略 : 核技巧 + 软间隔最大化
- 最大间隔法
- 间隔概念
- 函数间隔 : 表示分类的正确性及确信度
- 几何间隔 : 规范化后的函数间隔，实例点到超平面的带符号的距离
- 分类
- 硬间隔最大化 (hard margin maximization)
- 软间隔最大化 (soft margin maximization)
- 间隔最大化的形式化
- 求解凸二次规划问题
- 正则化的合页损失函数的最小化问题
- 求解过程
- 原始最优化问题应用拉格朗日对偶性；
- 通过求解对偶问题得到原始问题的最优解。
- 中间也可以根据需要自然引入核函数。
- 核技巧 (kernel method) 通用的机器学习方法
- 应用条件
- 非线性可分训练数据可以变换到线性可分特征空间；
- 目标函数中的内积可以使用非线性函数的内积替换；
- 非线性函数的内积可以使用核函数替换；
- 核函数使非线性问题可解。
- 常用的核函数
- 线性核 : 对应于线性可分问题
- 多项式核函数
- 高斯核函数
- Sigmoid 核函数
- 函数组合得到的核函数
- 两个核函数的线性组合仍然是核函数，k1(x,z) 和 k2(x,z) 是核函数，c1 和 c2 是任意正数，则 k(x,z)=c1k1(x,z)+c2k2(x,z) 也是核函数。
- 两个核函数的直积仍然是核函数，k1(x,z) 和 k2(x,z) 是核函数，则 k(x,z)=k1(x,z)k2(x,z) 也是核函数。
- k1(x,z) 是核函数，g(z) 是任意函数，则 k(x,z)=g(z)k1(x,z)g(z) 也是核函数。
- SMO 算法
- 支持向量机学习的启发式快速算法
- 流程
- 将原二次规划问题分解为只有两个变量的二次规划子问题；
- 第一个变量是违反 KKT 条件最严重的变量；
- 第二个变量是使目标函数增长最快的变量；
- 目标是使两个变量所对应样本之间的间隔最大。
- 对子问题进行解析分解；
- 直到所有变量满足 KKT 条件为止。
- 学习总结
- 支持向量机与神经网络是两大重要的机器学习算法；
- 结合周老师的书一起看，对于理解支持向量机会有较大帮助。[^周志华，2018] C06
- 深入了解支持向量机的理论分析。[^Haykin,2011] C06