笔记：支持向量机

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维向量），目标函数为：
$\left\{\begin{matrix}min \frac{1}{2} \left \| \omega \right \|^{2}\\ y_{i}(\omega \cdot x_{i}+b)-1\geq 0 (i=1,2...m) \end{matrix}\right.$
1.2 对偶理论求解目标函数
1）1.1中的问题称为函数优化的原问题，构造广义拉格朗日函数L(ω,b,α): $L(ω,b,α)=\frac{1}{2} \left \| \omega \right \|^{2}-\sum_{i=1}^{m}\alpha_{i} y_{i}(\omega \cdot x_{i}+b)-\alpha_{i} (\alpha_{i}\geq 0)$ 其中，α为拉格朗日乘子，数学上可以证明，构造的拉格朗日函数的最小最大问题(先对α求最大值，再对ω,b求最小值）与原问题等价，即min_ω,bmax_αL(ω,b,α)与原问题等价。
2）容易证明，min_ω,bmax_αL(ω,b,α)与其对偶问题max_αmin_ω,bL(ω,b,α)满足以下关系：
$min_{ω,b}max_{α}L(ω,b,α)\geq max_{α}min_{ω,b}L(ω,b,α)$ 上式被成为弱对偶关系
3）如果原问题是一个凸二次规划问题，则满足强对偶关系，即：
$min_{ω,b}max_{α}L(ω,b,α)=max_{α}min_{ω,b}L(ω,b,α)$ 此外，原问题与对偶问题满足强对偶关系的充要条件是KKT条件：
$▽L_{ω}(ω,b,α)=0;$ $▽L_{b}(ω,b,α)=0;$ $▽L_{α}(ω,b,α)=0;$ $α\geq 0;$ $y_{i}(\omega \cdot x_{i}+b)-1\geq 0;$ $α(y_{i}(\omega \cdot x_{i}+b)-1)=0$
1.3 对偶问题的解
由强对偶关系，可以将求原问题转化为求对偶问题，通过KKT条件，可以得到将对偶问题的优化问题最终转化为：
$min_{\alpha } \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}(x_{i}\cdot x_{j})-\sum_{i=1}^{m}\alpha _{i}$ $\sum_{i=1}^{m}\alpha _{i}y_{i}=0$ $\alpha _{i}\geq 0,i=1,2...m$
该问题为凸二次规划问题，可以利用一些优化算法进行求解，比如SMO算法等。
1.4分类超平面和决策函数
由1.3求得最优解α^*后，可分别得到ω^*和b^*。
$\omega ^{*}=\sum_{i=1}^{m}\alpha _{i}^{*} y_{i}x_{i}$ 选择α^*中的一个正分量α^*_j>0，可得b^*：
$b ^{*}=y_{j}-\sum_{i=1}^{m}\alpha _{i}^{*} y_{i}(x_{i}\cdot x_{j})$
分离超平面为：y=ω^*.x+b^*
决策函数为f(x)=sign(ω^*.x+b^*)
线性可分支持向量机求得的超平面唯一。
1.5支持向量
只有那些拉格朗日乘子α不为0对应的点才对最终的决策函数有贡献，这些点均位于分割边界上，被称为支持向量。
2、线性支持向量机
对于训练集出现某些异常点，导致无法线性可分，线性支持向量机目的在于寻找一条直线，在剔除这些异常点后，使大部分训练数据是线性可分的，实现软间隔最大化。
2.1 目标函数
$\left\{\begin{matrix}min \frac{1}{2} \left \| \omega \right \|^{2}+C\sum_{i=1}^{m}\zeta _{i} \\ y_{i}(\omega \cdot x_{i}+b)\geq 1-\zeta _{i} (i=1,2...m) \\ \zeta _{i}\geq 0 \end{matrix}\right.$
其中，参数C用来对误分类进行惩罚，C越大，对误分类容忍度越小；ζ表示松弛因子。
2.2对偶问题的求解
最终转化为对偶问题的优化为：
$min_{\alpha } \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}(x_{i}\cdot x_{j})-\sum_{i=1}^{m}\alpha _{i}$ $\sum_{i=1}^{m}\alpha _{i}y_{i}=0$ $0\leq\alpha _{i}\leq C,i=1,2...m$
2.3分类超平面和决策函数
由1.3求得最优解α^*后，可分别得到ω^*和b^*。
$\omega ^{*}=\sum_{i=1}^{m}\alpha _{i}^{*} y_{i}x_{i}$ 选择α^*中的一个正分量0<α^*_j<C，可得b^*,注意，此时求得的b值不唯一：
$b ^{*}=y_{j}-\sum_{i=1}^{m}\alpha _{i}^{*} y_{i}(x_{i}\cdot x_{j})$
分离超平面为：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)=\varphi (x)\cdot \varphi (z)$
则称K(x,z)为核函数。
2）常用核函数
（1）多项式核函数
$K(x,z)=(x\cdot z+1)^{p}$ 其中，p为多项式次数。
（2）高斯核函数
$K(x,z)=exp(-\frac{\left \| x-z \right \|^{2}}{2\sigma ^{2}})$
对应的支持向量机为高斯径向基函数分类器。
高斯核函数中的参数δ较大时，导致高偏差，低方差；
δ参数较小时，导致低偏差，高方差。
（3）字符串核函数
定义在字符串上的核函数
3.2目标函数
目标函数转化为对偶问题的求解，并应用核函数后，可以转化为：
$min_{\alpha } \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha _{i}\alpha _{j}y_{i}y_{j}K(x_{i},x_{j})-\sum_{i=1}^{m}\alpha _{i}$ $\sum_{i=1}^{m}\alpha _{i}y_{i}=0$ $0\leq\alpha _{i}\leq C,i=1,2...m$
3.3 决策函数
在3.2求得α值后，不必通过映射函数φ(x)求参数ω，而是通过核函数求得决策函数：
$f(x) = sign(\sum_{i=1}^{m}\alpha _{i}^{*} y_{i}K(x_{i},x)+b^{*} ) ---- (3.3)$
将数据从低维空间通过映射函数映射到高维空间，当做优化计算时，不必显式求得映射函数，而是通过核函数在低维空间做计算，这种方式称为为核技巧。

注意：吴恩达机器学习课程中，称高斯核函数K(x_i,x)为样本x与参考点x_i(i=1,2,...m)的相似度函数。对于容量为m训练数据集，选择这m个数据作为参考点，将样本x与参考点x_i的高斯核函数(相似度函数)构建新的特征f_i，最终的决策函数可以表示为：
$f(x)=sign(\theta _{0}+\theta _{1}f_{1}+\theta _{2}f_{2}+...+\theta _{m}f_{m})$ 其中，θ₀对应着公式3.3中的b^*，θ_i对应着α_i^*y_i，f_i对应着K(x_i,x)。