概要
被认为是最好的“现成”分类器，最小化经验风险
优点：泛化错误率低，计算开销不大，结果易解释
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于二分类问题，效率慢，工业界不适用
适用数据类型：数值型和标称型数据
决策边界：分隔超平面
SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）．一般的升维都会带来计算的复杂化，SVM方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．这一切要归功于核函数的展开和计算理论．
间隔
点到分隔面的距离：间隔 = γ/||w||
最大化间隔是SVM的基本型式
提高分类器的健壮性=希望间隔尽可能的大
支持向量：离分隔超平面最近的那些点
分隔超平面的形式： wTx+b,常数b类似于截距
点到分隔面的距离为点到分隔面的法线或垂线的长度，该值为|wTA+b|/||w||
使用类似海维赛德阶跃函数对wTx+b作用得到f(wTx+b),当u<0时f(u)=-1,反之f(u)=1
求解
求解min 1/2*||w||^2 s.t. yi(wTxi+b)>=1
本身是个凸二次规划问题，能直接用现成的优化计算包求解
更高效的方法是使用拉格朗日乘子法可到对偶问题:
max Σai - 1/2 ΣΣaiajyiyjxiTxj
如使用一般二次规划求解，该问题的规模正比于训练样本数，在实际任务中会造成很大开销
以及使用SMO“序列最小化”算法解对偶问题
基本思想：固定 除 ai之外的所有参数，求ai上的极值，流程:
1 选取一个需要更新的ai,aj
2.固定ai,aj以外的参数，求解上式获得更新后的ai,aj
SMO首先选取违背KKT条件程度最大的变量，第二选择一个使目标函数数值增长最快的变量
但由于比较各变量所对应的目标函数数值增幅的代价过高，采用启发式：
使选取的两变量所对应样本之间的间隔最大
详见西瓜书P123
核函数
如果原始空间是有限维，一定存在高维特征空间使样本可分
max Σai - 1/2 ΣΣaiajyiyjΦ(xi)TΦxj
求解Φ(xi)TΦxj是困难的，可以通过设计核函数求解
核函数的意义：xi,xj在特征空间上的内积等于它们在原始样本空间中通过核函数计算的结果
选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种：
(1)线性核函数K(xi,xj)=xiT·xj；
(2)多项式核函数K(xi,xj)=[xiT·xj]^d,d =1时退化成线性核
(3)RBF.高斯核，径向基函数K(xi,xj)=exp(-||xi-xj||^2/2σ^2） σ称为带宽
(4)拉普拉斯核K(xi,xj) =exp(-||xi-xj||/σ）σ>0
(5)Sigmoid核，二层神经网络核函数K(xi,xj)=tanh(a(xiT·xj)+b）
此外，核函数的线性组合，乘积也是核函数
软间隔
现实任务中很难确定合适的核函数使得训练样本在特征空间内线性可分，即使确定了，也很难保证结果不是过拟合导致的
软间隔允许支持向量在一些样本上出错
min 1/2*||w||^2 + CΣl(yi*wTxi+b)-1) C无穷大即求硬间隔
l()是0/1损失函数， L(z) = 1 if z<0 else 0
但l()非凸非连续，数学性质不好
常用替代损失函数：
hinge损失：Lhinge(z) = max(0, 1-z）
指数损失：Lexp(z) = e^(1-z)
对率损失: Llog(z) = log(1+e^(-z))
核方法
人们发展处一系列基于核函数的学习方法，统称为核方法。
最常见的是通过“核化”来讲线性学习器拓展为非线性学习器、
KLDA 核线性判别
详见西瓜书P138
SVM在文本分类任务中显示出卓越性能，成为首选技术。
一个可能的原因是:若将每个单词作为文本数据的一个属性，则该属性空间维数很高，冗余度很大，其描述能力足以将不同文档打散。
如何提高效率，使SVM能适用于大规模数据一直是研究重点。
多核学习：集成学习机制，通过学习获得最优凸组合。
网友评论