关于SVM - 在路上

有云，连SVM都不会还搞什么ML。
SVM前后也有看了3、4次了，但是每次看完都忘掉，然后下次看又要重新看。。
正好最近要做与SVM有关的事情，顺便复习并整理下SVM的知识，方便之后再次捡起。

先记录下，比较零散，之后写完再统一整理。。。。

下面默认都讨论的是二分类的SVM

primal hypothesis

SVM定义了一个线性决策面的二分类问题。

$y = sign(\langle w,x \rangle +b)$

hard margin

需要优化的损失函数是：

$\min_\omega \frac{1}{2}\left \| \omega \right \|^2 \qquad s.t.\quad y*(\langle w,x \rangle +b)\geqslant 1$

hard margin，需要在训练集上样本完全的线性可分才能够训练出来，这个条件很苛刻，所以一般很少直接用hard margin。
而是允许一定程度的分类误差，将hard margin变成soft margin。
所以hard margin就记录到这里了。

soft margin

需要优化的损失函数是：

$\min_\omega \frac{1}{2}\left \| \omega \right \|^2+C\sum_{i=1}^{N}\varepsilon _i \qquad s.t.\quad y*(\langle w,x \rangle +b)\geqslant 1-\varepsilon _i$

无约束下可以写成：

$\min_\omega \frac{1}{2}\left \| \omega \right \|^2+C\sum_{i=1}^{N}\max(0, 1-y*(\langle w,x \rangle +b)))$

其中 $\max(0, 1-y*(\langle w,x \rangle +b))$ 称为hinge loss（下面再展开叙述）
一般会用拉格朗日定理得到对偶问题进行求解。
为何要用对偶问题求解？

方便引入核函数
对偶问题更容易求解（据说）

反正，经过引入拉格朗日乘子对偶，求偏导，最后化简，得到的soft margin的对偶问题为：

$\min_\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. \sum_{i=1}^{N}\alpha_i y_i = 0$
$\quad 0\leq \alpha_i \leq C, i = 1,2,\cdot\cdot\cdot,N$

Hypothesis更改成：

$y=sign\left (\sum_{i=1}^{N}\alpha_iy_i(x\cdot x_i)+b\right )$

得到对偶问题后，一般的求解过程为：

优化得到$\alpha$的取值
用上面新得到的Hypothesis进行求解（虽然看上去，复杂度与训练集大小有关，但一般情况下，$\alpha$大部分为0，所以运算量不会很大。又及，$\alpha$不为0对应的样本成为Support Vector，即分布在间隔上的样本点）
也通过$\alpha$计算$\omega$和$b$的值后，代入到primal hypothesis进行求解

关于hinge loss

hinge loss中文可以翻译成“合页损失函数”，为啥叫“合页”（hinge）？因为函数图像长得像翻开的书页，如下图：

该图来自Andrew Ng在Coursera的Machine Learning课件，课件中的符号和本文的符号不尽相同，但大致可以看明白其中的对应关系。

图中的式子对应的是上文的soft margin下的无约束下的公式。
式子的中括号部分即是上文所说的hinge loss，可以看出，当y=1时，hinge loss取cost1，也就是图中靠左的曲线。y=0时，hinge loss取cost0，也就是右图靠右的曲线。可以清晰看看出他们都是因为max而产生的分段函数（如果没有max，那么就是一条斜线）
C表示惩罚系数
- C→∞时，soft margin退化成hard margin
- C→0时，没有任何成为，式子的最优解是theta也为0，也就是“基本无视了数据”（basically ignores the data）

附加上hinge loss和logicstic regression loss的对比：

简单来说，hinge loss在1和-1附近比logicstic regression loss要陡峭得多——于是让z的取值往大于1（小于-1）的方向靠。