笔记：支持向量机
1、线性可分支持向量机
线性可分支持向量机是指在训练数据集线性可分的情况下，寻找一条几何间隔最大化的直线（也称硬间隔最大化），将正样本和负样本完全分开。
1.1、目标函数
设有数据集D{(x(1),y(1))，(x(2),y(2))，(x(3),y(3))...(x(m),y(m))}含有m个样本，其中x∈Rn，y∈(-1,+1)。(x为n维向量)，分割样本的直线方程为y=ω.x+b（ω∈Rn属于n维向量），目标函数为：
1.2 对偶理论求解目标函数
1）1.1中的问题称为函数优化的原问题，构造广义拉格朗日函数L(ω,b,α): 其中，α为拉格朗日乘子，数学上可以证明，构造的拉格朗日函数的最小最大问题(先对α求最大值，再对ω,b求最小值）与原问题等价，即min ω,b max α L(ω,b,α)与原问题等价。
2）容易证明，min ω,b max α L(ω,b,α)与其对偶问题max α min ω,b L(ω,b,α)满足以下关系：
上式被成为弱对偶关系
3）如果原问题是一个凸二次规划问题，则满足强对偶关系，即：
此外，原问题与对偶问题满足强对偶关系的充要条件是KKT条件：
1.3 对偶问题的解
由强对偶关系，可以将求原问题转化为求对偶问题，通过KKT条件，可以得到将对偶问题的优化问题最终转化为：
该问题为凸二次规划问题，可以利用一些优化算法进行求解，比如SMO算法等。
1.4分类超平面和决策函数
由1.3求得最优解α * 后，可分别得到ω * 和b * 。
选择α * 中的一个正分量α * j >0，可得b * ：
分离超平面为：y=ω * .x+b *
决策函数为f(x)=sign(ω * .x+b * )
线性可分支持向量机求得的超平面唯一。
1.5支持向量
只有那些拉格朗日乘子α不为0对应的点才对最终的决策函数有贡献，这些点均位于分割边界上，被称为支持向量。
2、线性支持向量机
对于训练集出现某些异常点，导致无法线性可分，线性支持向量机目的在于寻找一条直线，在剔除这些异常点后，使大部分训练数据是线性可分的，实现软间隔最大化。
2.1 目标函数
其中，参数C用来对误分类进行惩罚，C越大，对误分类容忍度越小；ζ表示松弛因子。
2.2对偶问题的求解
最终转化为对偶问题的优化为：
2.3分类超平面和决策函数
由1.3求得最优解α * 后，可分别得到ω * 和b * 。
选择α * 中的一个正分量0<α * j <C，可得b * ,注意，此时求得的b值不唯一：
分离超平面为：y=ω * .x+b *
决策函数为f(x)=sign(ω * .x+b * )
注意，线性支持向量机求得的超平面不唯一。
2.4支持向量
支持向量由在函数间隔边界上的点、超平面与间隔边界上的点、位于超平面上的点和误分类点组成。
3、非线性支持向量机与核函数
非线性支持向量机用来解决线性不可分数据集的分类问题。现实中存在一些数据集，在现有特征维度下完全线性不可分（与只存在一些异常点不同，使用软间隔最大化的线性支持向量及也不能解决），非线性支持向量机通过核函数，将低维数据集通过映射函数转换为高维数据，这些高维数据是线性可分的。
3.1 核函数
1）设X是输入空间，H为特征空间，如果存在映射函数φ(x)使在输入空间X的数据映射到特征空间H中，使得对于输入空间X中的任意x,z∈X，都有：
则称K(x,z)为核函数。
2）常用核函数
（1）多项式核函数
其中，p为多项式次数。
（2）高斯核函数
对应的支持向量机为高斯径向基函数分类器。
高斯核函数中的参数δ较大时，导致高偏差，低方差；
δ参数较小时，导致低偏差，高方差。
（3）字符串核函数
定义在字符串上的核函数
3.2目标函数
目标函数转化为对偶问题的求解，并应用核函数后，可以转化为：
3.3 决策函数
在3.2求得α值后，不必通过映射函数φ(x)求参数ω，而是通过核函数求得决策函数：
将数据从低维空间通过映射函数映射到高维空间，当做优化计算时，不必显式求得映射函数，而是通过核函数在低维空间做计算，这种方式称为为核技巧。
注意：吴恩达机器学习课程中，称高斯核函数K(x i ,x)为样本x与参考点x i (i=1,2,...m)的相似度函数。对于容量为m训练数据集，选择这m个数据作为参考点，将样本x与参考点x i 的高斯核函数(相似度函数)构建新的特征f i ，最终的决策函数可以表示为：
其中，θ 0 对应着公式3.3中的b * ，θ i 对应着α i * y i ，f i 对应着K(x i ,x)。
