前言
之前讲了有关基本的SVM的数学模型（机器学习入门学习笔记：（4.1）SVM算法）。这次主要介绍介绍svm的核函数、软间隔等概念，并进行详细的数学推导。这里仅将自己的笔记记录下来，以便以后复习查看和分享。
核函数
在此前的讨论中，我们都是默认假设数据集是线性可分的，即存在一个超平面能将给出的样本数据正确分类。然而，有时也许在原始的样本空间中找不到一个能正确分类的超平面。
如上图所示，一堆数据在二维空间中无法使用直线划分，而将其映射到三维空间中，便可以使用超平面划分。
所以，当遇到此类问题时，我们可以考虑：将超平面从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如果原始空间是有限的，那么一定存在一个高维特征空间使得样本数据可分。
另ϕ(x)表示将x映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可以表示为：
f(x)=ωTx+b
这里使用这个条件重新再快速走一遍推导流程：
首先，回到前面求解
SVM的参数
ω个
b的最优化问题：
min12∥ω∥2s.t.yi(ωTϕ(xi)+b)≥1,i=1,2,...,m
转为求解其对偶问题，可以得到：
maxα∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjϕ(xi)ϕ(xj)s.t.∑i=1mαiyi=0
与之前的结果差不多，唯一的区别就是这个：
ϕ(xi)ϕ(xj)。这是样本
xi和
xj映射到特征空间之后的内积。在引入核函数之前，对应的是：
xixj，本身这个也是一个核函数，叫做线性核。
由于特征空间的维数有可能很高，甚至是无穷维，因此，直接计算
ϕ(xi)ϕ(xj)这个式子，复杂度为
O(m2),limm→+∞。计算量非常大，所以此时计算
ϕ(xi)ϕ(xj)比较困难。为了回避这个问题，可以设想如下函数：
K(xi,xj)=<ϕ(xi),ϕ(xj)>=ϕ(xi)Tϕ(xj)
即将
ϕ(xi)和
ϕ(xj)的内积转化为求解这个函数
K(xi,xj)。
SVM的优化问题可以重写为：
maxα∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjK(xi,xj)s.t.∑i=1mαiyi=0
这还是一个二次规划问题，我们可以通过一些现成的优化算法或者QP工具包求解出
α的值。
之后由
α值可以求出
ω和
b。这些结果都与前面一样，就直接给出结果了。
ω=∑i=1mαiyixib=1|S|∑s∈S(ys−∑i∈SαiyixTixs)
原来的SVM模型可以表示如下：
f(x)=ωTϕ(x)+b=∑i=1mαiyiϕ(xi)Tϕ(x)+b=∑i=1mαiyiK(xi,xj)+1|S|∑s∈S(ys−∑i∈SαiyixTixs)
其中的
K(⋅,⋅)为核函数。
补充
当然核函数还有很多性质，这里不做介绍，下面给一个有详细的介绍的链接：
svm核函数的理解和选择
软间隔
前面有关支持向量机的约束条件：
{ωTxi+b≥1,yi=+1ωTxi+b≤−1,yi=−1
优化问题：
minω,b∥ω∥22s.t.yi(ωTxi+b)≥1,i=1,2,...,m
此时要求所有的样本都划分正确，这被称为
“硬间隔”。
而
“软间隔”就是允许一些样本不符合条件：
yi(ωTxi+b)≥1
在最大化
间隔的同时，也应当使这些不满足约束的样本点尽可能少，于是优化问题变为：
minω,b∥ω∥22+C∑i=1ml0/1(yi(ωTxi+b)−1)s.t.yi(ωTxi+b)≥1,i=1,2,...,m
其中
C≥0且为常数；
l0/1是“0/1损失函数”。
l0/1(x)={1,ifx≤0;0,otherwise
讨论如下情况：
1. 如果
C→∞，那么最小值就是
∞本身，此时所有样本都能满足条件；
2. 如果
C是一个有限值，那么最小值也会取到一个有限值，此时，会允许一些样本不满足条件。
当然l0/1这样的函数是不连续不可导的，这会使得问题不好求解。所以常常还会使用其他一些函数来替代“0/1损失函数”，这些函数称为“替代函数”。这些替代函数有更好的数学性质，通常都是凸函数，且连续可导。
三种常用的替代函数：
⎧⎩⎨⎪⎪hinge损失：lhinge(z)=max(0,1−z)指数损失：lexp(z)=exp(−z)对率损失：llog(z)=log(1+exp(−z))
若采用hinge损失，原问题变为：
minω,b∥ω∥22+C∑i=1mmax(0,1−yi(ωTxi+b))s.t.yi(ωTxi+b)≥1,i=1,2,...,m
引入
松弛变量(slack variables)
ξ：
minω,b∥ω∥22+C∑i=1mξis.t.yi(ωTxi+b)≥1,i=1,2,...,m
由于：
ξi=max(0,1−yi(ωTxi+b))
所以条件变为：
ξi≥0&&ξi≥1−yi(ωTxi+b)
现在得到
软间隔支持向量机表示如下：
minω,b∥ω∥22+C∑i=1mξis.t.yi(ωTxi+b)≥1−ξiξi≥0,i=1,2,...,m
接下来，与之前的博客
（机器学习入门学习笔记：（4.1）SVM算法）中一样，我们要将这个问题转换为对偶问题求解：
这仍然是一个二次规划问题，我们构建拉格朗日函数：
L(ω,b,α,ξ,μ)=∥ω∥22+C∑i=1mξi+∑i=1mαi(1−ξ−yi(ωTxi+b))+∑i=1mμi(−ξi)
其中
αi≥0,μi≥0。
接下来对
L(ω,b,α,ξ,μ)关于
ω,b,ξ求偏导，令其为0：
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪∂L∂ω=ω−∑mi=1αiyiωTxi∂ω=ω−∑mi=1αiyixi=0∂L∂b=−∑mi=1αiyib∂b=∑mi=1αiyi=0∂L∂ξi=C−∑mi=1αiξi∂ξ−∑mi=1μiξi∂ξi=C−αi−μi=0
得到新的约束条件：
⎧⎩⎨⎪⎪ω=∑mi=1αiyixi∑mi=1αiyi=0C=αi+μi
重点关注这个新多出来的条件：
C=αi+μi，又由于KKT条件，我们还有
αi≥0,μi≥0：
所以,对于
αi有：
0≤αi≤C
将上面推出的新的约束条件代回到拉格朗日函数，消去
ω,b,ξ（中间的推导我省略了，太长了）：
L(ω,b,α)=∥ω∥22+C∑i=1mξi+∑i=1mαi(1−ξ−yi(ωTxi+b))+∑i=1mμi(−ξi)=∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjxixj
这东西跟原来的还是一模一样的，区别在于约束条件。写出问题最后的形式：
maxα∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjxixj,s.t.∑i=1mαiyi=00≤αi≤C,i=1,2,...,m
接下来的工作就是解这个二次规划问题，我们可以采用现成的QP工具包来解决，也可以采用ＳＭＯ算法来解出答案。求出合适的α后，逆推出ω和b。
后记
SVM算法相对其他的机器学习算法来说还是比较复杂的，涉及概念也比较多。这样子详细再推导一次，很多概念都能理解地更深了。下次再总结归纳ＳＭＯ算法。
参考资料：
《机器学习》周志华
svm核函数的理解和选择
