感知机是SVM的基础，详细介绍请戳http://blog.csdn.net/akirameiao/article/details/79436859

一、原理

1. 线性可分支持向量机

问题的输入输出
X = {x1,x2,...,xn$x_1,x_2,...,x_n$}
Y = {+1, -1}

模型：
感知机的目的是找到一个可以正确分类数据的超平面S：ω⋅x+b=0$\omega \cdot x+b=0$, 得到感知机模型 f(x)=sign(ω⋅x+b)$f(x)=sign(\omega \cdot x+b)$，其中ω⋅x+b>0$\omega \cdot x+b>0$为正类，ω⋅x+b<0$\omega \cdot x+b<0$为负类。SVM和感知机最大的差别就是SVM寻找的间隔最大的超平面，所谓间隔，可以理解为实例点到超平面最小的距离，所以SVM找的是把数据正确分隔的”最开”的超平面。

间隔
函数间隔：对于给定的训练数据集T和超平面(ω,b$\omega ,b$)， 定义超平面关于样本点(xi,yi$x_i,y_i$)的函数间隔为 γ̂ i=yi(ω⋅xi+b)${\hat{\gamma }}_i=y_i(\omega \cdot x_i+b)$
几何间隔：对于给定的训练数据集T和超平面(ω,b$\omega ,b$)， 定义超平面关于样本点(xi,yi$x_i,y_i$)的几何间隔为 γi=1||ω||yi(ω⋅xi+b)=γ̂ i||ω||${\gamma }_i=\frac{1}{||\omega ||}{y}_i(\omega \cdot x_i+b)=\frac{{\hat{\gamma }}_i}{||\omega ||}$

所以我们可以建立模型：

输入: T={(x1,y1),(x2,y2),⋯,(xi,yi)}$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_i,y_i)\}$
输出: 分离超平面：ω⋅x+b=0$\omega \cdot x+b=0$ 决策函数：f(x)=sign(ω⋅x+b)$f(x)=sign(\omega \cdot x+b)$

策略：
接下来的问题就是找到间隔最大的超平面，记超平面关于实例点的的几何间隔【1||ω||yi(ω⋅xi+b)≥γi$\frac{1}{||\omega ||}{y}_i(\omega \cdot x_i+b)\ge {\gamma }_i$ 】, 定义超平面关于所有实例点的几何间隔为【γ=maxγi$\gamma =max{\gamma }_i$】, 则问题就可以写成【 maxω,bγ$ma{x}_{\omega ,b}\gamma$ ，s.t.yi(ω⋅xi+b)≥γi$s.t.y_i(\omega \cdot x_i+b)\ge {\gamma }_i$ 】
有几何间隔和函数间隔的关系，问题可以改写为【maxγ̂ ||ω||$max\frac{\hat{\gamma }}{||\omega ||}$】【s.t.yi(ω⋅xi+b)≥γ̂ ,i=1,2,⋯,N$s.t.y_i(\omega \cdot x_i+b)\ge \hat{\gamma },i=1,2,\cdots ,N$】
由于同时成比例的改变 ω$\omega$ 和 b ，不会影响超平面的位置，也不会影响不等式约束和目标函数的优化，可以令【γ̂ =1$\hat{\gamma }=1$】,为了求解的方便，把优化目标改成：min12||ω||2$min\frac{1}{2}||\omega |{|}^2$，约束条件改成yi(ω⋅xi+b)−1≥0,i=1,2,⋯,N$y_i(\omega \cdot x_i+b)-1\ge 0,i=1,2,\cdots ,N$

算法:

原始算法：

输入：线性可分数据集T={(x1,y1),(x2,y2),⋯,(xn,yn)}$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)\}$，其中，xi∈Rn,yi∈{+1,−1},i=1,2,⋯,N$x_i\in R^n,y_i\in \{+1,-1\},i=1,2,\cdots ,N$
输出：最大间隔分离超平面：ω∗⋅x+b∗=0${\omega }^{\ast }\cdot x+b^{\ast }=0$ 分类决策函数：f(x)=sign(ω∗⋅x+b∗)$f(x)=sign({\omega }^{\ast }\cdot x+b^{\ast })$

过程：(1)minω,b12||ω||2$(1)mi{n}_{\omega ,b}\frac{1}{2}||\omega |{|}^2$, s.t.$s.t.$ yi(ω⋅xi+b)−1≥0,i=1,2,⋯,N$y_i(\omega \cdot x_i+b)-1\ge 0,i=1,2,\cdots ,N$，求的最优解 ω∗,b∗${\omega }^{\ast },b^{\ast }$

(2)得到分离超平面 w∗⋅x+b=0$w^{\ast }\cdot x+b=0$，决策函数 f(x)=sign(ω∗⋅x+b∗)$f(x)=sign({\omega }^{\ast }\cdot x+b^{\ast })$

对偶算法：

首先构建原始问题的拉格朗日函数 L(ω,b,α)=12||ω||2+∑Ni=1αi(1−yi(ω⋅xi+b))$L(\omega ,b,\alpha )=\frac{1}{2}||\omega |{|}^2+\sum _{i=1}^N{\alpha }_i(1-y_i(\omega \cdot x_i+b))$ 由拉格朗日对偶性，原始问题的对偶问题的极大极小问题 maxαminω,bL(ω,b,α)$\underset{\alpha }{max}mi{n}_{\omega ,b}L(\omega ,b,\alpha )$ 接下来是求解过程

a. 对ω,b$\omega ,b$ 求偏导数，并令其等于0，【∇ωL(ω,b,α)=ω−∑Ni=1αiyixi=0${\mathrm{\nabla }}_{\omega }L(\omega ,b,\alpha )=\omega -\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0$ 】, 【∇bL(ω,b,α)=∑Ni=1αiyi${\mathrm{\nabla }}_{b}L(\omega ,b,\alpha )=\sum _{i=1}^N{\alpha }_i{y}_i$】，得到【ω=∑Ni=1αiyixi,∑Ni=1αiyi=0$\omega =\sum _{i=1}^N{\alpha }_i{y}_i{x}_i,\sum _{i=1}^N{\alpha }_i{y}_i=0$】

b. 将a中得到的结果代入拉格朗日函数，化简得到
【 minω,bL(ω,b,α)=−12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)+∑Ni=1αi$mi{n}_{\omega ,b}L(\omega ,b,\alpha )=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^N{\alpha }_i$】

c. 接下来求【maxα−12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)+∑Ni=1αi$ma{x}_{\alpha }-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^N{\alpha }_i$,s.t ∑Ni=1αiyi=0$\sum _{i=1}^N{\alpha }_i{y}_i=0$, αi≥0${\alpha }_i\ge 0$】, 【i=1,2,⋯,N$i=1,2,\cdots ,N$】

d. 转化为求【minα12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αi$mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i$, s.t∑Ni=1αiyi=0$\sum _{i=1}^N{\alpha }_i{y}_i=0$, αi≥0，i=1,2,⋯,N${\alpha }_i\ge 0，i=1,2,\cdots ,N$】

拉格朗日函数的KKT条件
∇ωL(ω,b,α)=0${\mathrm{\nabla }}_{\omega }L(\omega ,b,\alpha )=0$
αi≥0${\alpha }_i\ge 0$
yif(xi)−1≥0$y_{i}f(x_i)-1\ge 0$
αi(yif(xi)−1)=0${\alpha }_i(y_{i}f(x_i)-1)=0$

e. 由KKT条件，ω∗=∑Ni=1α∗yixi${\omega }^{\ast }=\sum _{i=1}^N{\alpha }^{\ast }{y}_i{x}_i$ , 由于ω≠0$\omega \ne 0$可知存在下标 j，使得α∗j>0${\alpha }_j^{\ast }>0$ , 那么yi(ω⋅xi+b)=0,$y_i(\omega \cdot x_i+b)=0,$将 ω$\omega$ 代入，得到 b∗=yj−∑Ni=1α∗iyi(xi⋅xj)$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)$
输入：线性可分数据集T={(x1,y1),(x2,y2),⋯,(xn,yn)}$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)\}$，其中，xi∈Rn,yi∈{+1,−1},i=1,2,⋯,N$x_i\in R^n,y_i\in \{+1,-1\},i=1,2,\cdots ,N$

f.计算出 α$\alpha$ 之后，可以得到ω,b$\omega ,b$,分离超平面∑Ni=1α∗iyi(x⋅xi)+b∗$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast }$ , 分类决策f(x)=sign(∑Ni=1α∗iyi(x⋅xi)+b∗)$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast })$

2. 线性支持向量机

如果数据中大部分点是线性可分的，但是存在少数点是线性不可分，这种情况下，就可以使用软间隔支持向量机，每个实例支付一个代价 ξi${\xi }_i$ ，将约束条件写成 yi(ω⋅xi+b)≥1−ξi$y_i(\omega \cdot x_i+b)\ge 1-{\xi }_i$ , 将优化目标函数写成 12||ω||2+C∑Niξi$\frac{1}{2}||\omega |{|}^2+C\sum _i^N{\xi }_i$, C是调和两者的参数，这样的叫做软间隔支持向量机

策略:

min12||ω||2+C∑Niξi$min\frac{1}{2}||\omega |{|}^2+C\sum _i^N{\xi }_i$
s.t.yi(ω⋅xi+b)≥1−ξi$s.t.y_i(\omega \cdot x_i+b)\ge 1-{\xi }_i$
ξ≥0$\xi \ge 0$

算法：

a.L(ω,b,ξ,α,μ)=12||ω||2+C∑Niξi+∑Niαi[1−ξi−yi(ω⋅xi+b)]+∑Ni(−μiξi)$a.L(\omega ,b,\xi ,\alpha ,\mu )=\frac{1}{2}||\omega |{|}^2+C\sum _i^N{\xi }_i+\sum _i^N{\alpha }_i[1-{\xi }_i-y_i(\omega \cdot x_i+b)]+\sum _i^N(-{\mu }_i{\xi }_i)$

展开后得到
L(ω,b,ξ,α,μ)=12||ω||2+C∑Niξi+∑Niαi−∑Niαiξi−∑Niαiyiωxi−∑Niαiyib−∑Niμiξi$L(\omega ,b,\xi ,\alpha ,\mu )=\frac{1}{2}||\omega |{|}^2+C\sum _i^N{\xi }_i+\sum _i^N{\alpha }_i-\sum _i^N{\alpha }_i{\xi }_i-\sum _i^N{\alpha }_i{y}_i\omega x_i-\sum _i^N{\alpha }_i{y}_{i}b-\sum _i^N{\mu }_i{\xi }_i$

b.原始问题的对偶问题ω,b,ξ$\omega ,b,\xi$求偏导数，得到
∇ωL=ω−∑Niαiyixi${\mathrm{\nabla }}_{\omega }L=\omega -\sum _i^N{\alpha }_i{y}_i{x}_i$
∇bL=−∑Niαiyi${\mathrm{\nabla }}_{b}L=-\sum _i^N{\alpha }_i{y}_i$
∇ξiL=C−αi−μi${\mathrm{\nabla }}_{{\xi }^i}L=C-{\alpha }_i-{\mu }_i$

令偏导数为0，得到
ω=∑Niαiyixi$\omega =\sum _i^N{\alpha }_i{y}_i{x}_i$
∑Niαiyi=0$\sum _i^N{\alpha }_i{y}_i=0$
C−αi−μi=0$C-{\alpha }_i-{\mu }_i=0$

c.将b中的结果代入拉格朗日函数，得到对偶问题
【 minω,bL(ω,b,α)=−12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)+∑Ni=1αi$mi{n}_{\omega ,b}L(\omega ,b,\alpha )=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^N{\alpha }_i$】

d. 接下来求
maxα−12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)+∑Ni=1αi$ma{x}_{\alpha }-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^N{\alpha }_i$,s.t ∑Ni=1αiyi=0$\sum _{i=1}^N{\alpha }_i{y}_i=0$, αi≥0${\alpha }_i\ge 0$】, 【i=1,2,⋯,N$i=1,2,\cdots ,N$】

e. 转化为求
minα12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αi$mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i$,
s.t ∑Ni=1αiyi=0$\sum _{i=1}^N{\alpha }_i{y}_i=0$,
αi≥0，i=1,2,⋯,N${\alpha }_i\ge 0，i=1,2,\cdots ,N$
μi≥0${\mu }_i\ge 0$
αi(yi(ω⋅xi+b)−1+ξi)=0${\alpha }_i(y_i(\omega \cdot x_i+b)-1+{\xi }_i)=0$

f.计算出 α$\alpha$ 之后，可以得到ω,b$\omega ,b$,分离超平面∑Ni=1α∗iyi(x⋅xi)+b∗$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast }$ , 分类决策f(x)=sign(∑Ni=1α∗iyi(x⋅xi)+b∗)$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast })$

3. 非线性支持向量机

当数据在当前输入空间线性不可分时，可以使用映射函数，ϕ(x)$\varphi (x)$ 将样本映射到特征空间，使它们变得线性可分

核函数：
K(xi,xj)=ϕ(xi)⋅ϕ(xj)$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$

优化目标可以写成
分离超平面∑Ni=1α∗iyiK（x⋅xi)+b∗$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K（x\cdot x_i)+b^{\ast }$ , 分类决策 f(x)=sign(∑Ni=1α∗iyiK(x⋅xi)+b∗)$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K(x\cdot x_i)+b^{\ast })$

核函数一般的由高斯核函数、

SMO算法
1.选出两个优化变量αi,αj${\alpha }_i,{\alpha }_j$之后，通过代数方法求解二次规划问题
2.选出一个变量αi${\alpha }_i$,如何选择第二个变量αj${\alpha }_j$

二、白板推导