SVM基础

SVM算法的效果是非常好的。对于一个线性可分的数据集（假设是二分类），以前的感知器算法就是找一条线将其分开就可以了，线的最终方程是随机的，它与分割线的初始化情况，与遇到训练点的顺序有关，因为它是遇到一个训练点，如果错误才改正。而现在的支持向量机算法就是能够在如此多的看似成功的线中找出一条最好的线，结果是唯一的。

那这个线是什么线呢？

定义：
1.
函数距离

$$\widehat{{\gamma ^{i}}}=y^{i}(w^{T}x+b)$$
函数边界：就是最小的函数距离 $$\widehat{\gamma} =\underset{}{min} \gamma^{i}$$
几何距离 $$\gamma ^{i}=y^{i}((\frac{w}{||w||})^{T}x+\frac{b}{||w||})$$
几何边界：就是最小的函数距离 $$\gamma =\underset{}{min} \gamma^{i}$$
其中 $\gamma$= $\frac{\widehat{\gamma}{}}{||w||}$
推导几何距离公式：
令点A的坐标为 $x^i$,分割线的单位法向量为 $\frac{w}{||w||}$,点A到该分割线的距离为 $\gamma^i$,做点A到分割线的垂线，交点为B ，坐标为 $c$,则$x^i$-c= $\gamma^i$ $\frac{w}{||w||}$,得c=$x^i$-$\gamma^i$ $\frac{w}{||w||}$，由c在分割线上面，分割线方程为wx+b=0,代入方程，化简得 $$\gamma ^{i}=y^{i}((\frac{w}{||w||})^{T}x+\frac{b}{||w||})$$

现在我们开始求最优边界！
目标：最大化几何边界$\gamma$
条件： $\gamma$应为支持向量，即其他所有的几何距离都大于几何间距。
则
目标：$\underset{\gamma ,w,b}{max}$ $\gamma$
条件1：$\widehat{\gamma}$=1 既然是约束条件，那么||w||=1,和$\widehat{\gamma}$=1都可以。（我认为是这样的，如果不是，还请告知）
条件2: $\gamma ^{i}=y^{i}((\frac{w}{||w||})^{T}x+\frac{b}{||w||})$>=$\gamma$
化简条件 $y^{i}((\frac{w}{||w||})^{T}x+\frac{b}{||w||})$>=$\frac{\widehat{\gamma}{}}{||w||}$
去掉||w||,即得$y^{i}(w^{T}x+b)$>=$\widehat{\gamma}$

则可化简为
目标：$\underset{\gamma ,w,b}{max}$$\frac{\widehat{\gamma}{}}{||w||}$
条件1：$y^{i}(w^{T}x+b)$>=$\widehat{\gamma}$
条件2：$\widehat{\gamma}$=1

条件2$\widehat{\gamma}$=1的作用？
正规化，作用同||w||,其值为1，或2，什么的都可以。
则最终优化问题为：

目标：$\frac{1}{2}$$\underset{\gamma ,w,b}{min}$$||w||^2$
条件1：$y^{i}(w^{T}x^i+b)$>=1
正是一个二次规划问题，可用商业软件求出答案。比如LINGO软件。