IT博客汇 | 机器学习（五）：SVM支持向量机

机器学习（五）：SVM支持向量机_Python

summer发表于 2016-11-10 03:28:32

机器学习

四、SVM支持向量机

github地址:https://github.com/lawlite19/MachineLearning_Python
由于公式使用的是LaTex，解析使用的google的Chart API，所以显示有问题，可以移步github（可以翻墙就不用了）

1、代价函数

在逻辑回归中，我们的代价为：
$\cos t({h_\theta }(x),y) = \left{ {\begin{array}{c} { - \log ({h_\theta }(x))} \\ { - \log (1 - {h_\theta }(x))} \end{array} \begin{array}{c} {y = 1} \\ {y = 0} \end{array} } \right.$ ，
其中： ${h_\theta }({\text{z}}) = \frac{1}{{1 + {e^{ - z}}}}$ ， $z = {\theta ^T}x$
如图所示，如果y=1，cost代价函数如图所示

我们想让 ${\theta ^T}x > > 0$ ，即z>>0，这样的话cost代价函数才会趋于最小（这是我们想要的），所以用途中红色的函数 $\cos {t_1}(z)$ 代替逻辑回归中的cost
当y=0时同样，用 $\cos {t_0}(z)$ 代替
最终得到的代价函数为：
$J(\theta ) = C\sum\limits_{i = 1}^m {[{y^{(i)}}\cos {t_1}({\theta ^T}{x^{(i)}}) + (1 - {y^{(i)}})\cos {t_0}({\theta ^T}{x^{(i)}})} ] + \frac{1}{2}\sum\limits_{j = 1}^{\text{n}} {\theta _j^2}$
最后我们想要 $\mathop {\min }\limits_\theta J(\theta )$
之前我们逻辑回归中的代价函数为：
$J(\theta ) = - \frac{1}{m}\sum\limits_{i = 1}^m {[{y^{(i)}}\log ({h_\theta }({x^{(i)}}) + (1 - } {y^{(i)}})\log (1 - {h_\theta }({x^{(i)}})] + \frac{\lambda }{{2m}}\sum\limits_{j = 1}^n {\theta _j^2}$
可以认为这里的 $C = \frac{m}{\lambda }$ ，只是表达形式问题，这里C的值越大，SVM的决策边界的margin也越大，下面会说明

2、Large Margin

如下图所示,SVM分类会使用最大的margin将其分开
先说一下向量内积
- $u = \left[ {\begin{array}{c} {{u_1}} \\ {{u_2}} \end{array} } \right]$ ， $v = \left[ {\begin{array}{c} {{v_1}} \\ {{v_2}} \end{array} } \right]$
- $||u||$ 表示u的欧几里得范数（欧式范数）， $||u||{\text{ = }}\sqrt {{\text{u}}_1^2 + u_2^2}$
- 向量V在向量u上的投影的长度记为p，则：向量内积：
  ${{\text{u}}^T}v = p||u|| = {u_1}{v_1} + {u_2}{v_2}$
  
  根据向量夹角公式推导一下即可， $\cos \theta = \frac{{\overrightarrow {\text{u}} \overrightarrow v }}{{|\overrightarrow {\text{u}} ||\overrightarrow v |}}$
前面说过，当C越大时，margin也就越大，我们的目的是最小化代价函数J(θ),当margin最大时，C的乘积项 $\sum\limits_{i = 1}^m {[{y^{(i)}}\cos {t_1}({\theta ^T}{x^{(i)}}) + (1 - {y^{(i)}})\cos {t_0}({\theta ^T}{x^{(i)}})} ]$ 要很小，所以近似为：
$J(\theta ) = C0 + \frac{1}{2}\sum\limits_{j = 1}^{\text{n}} {\theta _j^2} = \frac{1}{2}\sum\limits_{j = 1}^{\text{n}} {\theta _j^2} = \frac{1}{2}(\theta _1^2 + \theta _2^2) = \frac{1}{2}{\sqrt {\theta _1^2 + \theta _2^2} ^2}$ ，
我们最后的目的就是求使代价最小的θ
由
$\left{ {\begin{array}{c} {{\theta ^T}{x^{(i)}} \geqslant 1} \\ {{\theta ^T}{x^{(i)}} \leqslant - 1} \end{array} } \right.\begin{array}{c} {({y^{(i)}} = 1)} \\ {({y^{(i)}} = 0)} \end{array}$ 可以得到：
$\left{ {\begin{array}{c} {{p^{(i)}}||\theta || \geqslant 1} \\ {{p^{(i)}}||\theta || \leqslant - 1} \end{array} } \right.\begin{array}{c} {({y^{(i)}} = 1)} \\ {({y^{(i)}} = 0)} \end{array}$ ，p即为x在θ上的投影
如下图所示，假设决策边界如图，找其中的一个点，到θ上的投影为p,则 $p||\theta || \geqslant 1$ 或者 $p||\theta || \leqslant - 1$ ，若是p很小，则需要 $||\theta ||$ 很大，这与我们要求的θ使 $||\theta || = \frac{1}{2}\sqrt {\theta _1^2 + \theta _2^2}$ 最小相违背，所以最后求的是large margin

3、SVM Kernel（核函数）

对于线性可分的问题，使用线性核函数即可
对于线性不可分的问题，在逻辑回归中，我们是将feature映射为使用多项式的形式 $1 + {x_1} + {x_2} + x_1^2 + {x_1}{x_2} + x_2^2$ ，SVM中也有多项式核函数，但是更常用的是高斯核函数，也称为RBF核
高斯核函数为： $f(x) = {e^{ - \frac{{||x - u|{|^2}}}{{2{\sigma ^2}}}}}$
假设如图几个点，

令：
${f_1} = similarity(x,{l^{(1)}}) = {e^{ - \frac{{||x - {l^{(1)}}|{|^2}}}{{2{\sigma ^2}}}}}$
${f_2} = similarity(x,{l^{(2)}}) = {e^{ - \frac{{||x - {l^{(2)}}|{|^2}}}{{2{\sigma ^2}}}}}$
.
.
.
可以看出，若是x与 ${l^{(1)}}$ 距离较近，==》 ${f_1} \approx {e^0} = 1$ ，（即相似度较大）
若是x与 ${l^{(1)}}$ 距离较远，==》 ${f_2} \approx {e^{ - \infty }} = 0$ ，（即相似度较低）
高斯核函数的σ越小，f下降的越快
如何选择初始的 ${l^{(1)}}{l^{(2)}}{l^{(3)}}...$
- 训练集： $(({x^{(1)}},{y^{(1)}}),({x^{(2)}},{y^{(2)}}),...({x^{(m)}},{y^{(m)}}))$
- 选择： ${l^{(1)}} = {x^{(1)}},{l^{(2)}} = {x^{(2)}}...{l^{(m)}} = {x^{(m)}}$
- 对于给出的x，计算f,令： $f_0^{(i)} = 1$ 所以： ${f^{(i)}} \in {R^{m + 1}}$
- 最小化J求出θ，
  $J(\theta ) = C\sum\limits_{i = 1}^m {[{y^{(i)}}\cos {t_1}({\theta ^T}{f^{(i)}}) + (1 - {y^{(i)}})\cos {t_0}({\theta ^T}{f^{(i)}})} ] + \frac{1}{2}\sum\limits_{j = 1}^{\text{n}} {\theta _j^2}$
- 如果 ${\theta ^T}f \geqslant 0$ ，==》预测y=1