机器学习（十七）- SVMs - Large Margin Classification

Large Margin Classification

Optimization Objective

对于SVMs，我们从目标函数开始讲起，由于SVM的目标函数和逻辑回归的目标函数很相似，所以我们从逻辑回归的目标函数开始一点点给出区别。
第一，不再使用−log11+e−z$-\log \frac{1}{1+e^{-z}}$，而是将其替换为一个cost1(z)${\text{cost}}_1(z)$方程，方程在坐标轴中表示为下图左下角的紫红色线条，同样−log(1−11+e−z)$-\log (1-\frac{1}{1+e^{-z}})$也被替换为一个cost0(z)${\text{cost}}_0(z)$方程，方程在坐标轴中表示为下图右下角的紫红色线条。不再平滑而是一条折线。

第二将系数 1m$\frac{1}{m}$ 去掉，并不影响我们求取方程达到最小时 θ$\theta$ 的值。
第三不再使用 λ$\lambda$ ，而是使用 C$C$ 来进行两项的trade-off 。
最终结合起来，SVMs的目标函数就变为下图最下方的方程。

最后，通过目标函数求出了 θ$\theta$ ，在进行新样本预测的时候，只要 θTx≥0${\theta }^{T}x\ge 0$，就判定为1类，否则为0类。因为SVMs其实本质上也是在空间中拟合一条曲线θTx${\theta }^{T}x$进行空间分隔。

Large Margin Intuition

有些时候，SVMs又被称作Large Margin Classifier（大间距分类器）
我们知道我们是要最小化下面这个函数。

接下来我们考虑比较极端的一种情况，就是C是一个特别大的正数，为了最小化目标函数，我们必须让前面一项等于0，只要满足下图中的上面两个条件，第一个项就等于0，相当于我们仅仅最小化

12∑j=1nθ2j$$\frac{1}{2}\sum _{j=1}^n{\theta }_j^2$$

那么我们的问题就转化为了一个带有不等式约束的最值问题：

minθs.t.12∑j=1nθ2j  θTx(i)≥1      if   y(i)=1  θTx(i)≤−1   if   y(i)=0(1)(2)(3)$$\begin{array}{}\text{(1)}& \underset{\theta }{min}& \frac{1}{2}\sum _{j=1}^n{\theta }_j^2\text{(2)}& \text{s.t.}& {\theta }^T{x}^{(i)}\ge 1\text{if}{y}^{(i)}=1\text{(3)}& & {\theta }^T{x}^{(i)}\le -1\text{if}{y}^{(i)}=0\end{array}$$

对于线性可分隔数据集，这个数学问题在二维坐标系（考虑只有两个参数的情况，多维可以扩展）中就被转化为求一条直线可以完美地分隔我们的正负数据集的决策边界，如下图绿色，紫红色和黑色的直线都做到了分隔数据集，但是明显黑色线条分隔的更好，而上述最值问题求解出的就是黑色这条直线，这条黑色直线拥有所谓”很大的margin”，margin指的是正负样本到直线的最小距离。而别的直线拥有的margin就很小。这也就是Large Margin Classifier中large margin的由来，等会儿再详细讲解数学原理。

刚刚是我们针对一个完美的线性可分的数据集，现在假设我们有一些异常值，比如下图的情况，明显我们希望我们拟合出的曲线能够不考虑异常值得到黑色这条直线而不是紫红色这条。可喜的是，我们可以通过常数C来进行调节，如果C很大就会拟合出紫红色线条，如果C不是很大就会拟合出黑色线条。为什么呢？
这一点我们可以联系我们带正则项的逻辑回归来理解，C很大，其实就是对应 λ$\lambda$ 很小的情况，也就是正则项几乎不起作用，模型会过拟合数据，正好也就对应我们下图紫红色线条的情况，会想要去完美的分隔正负数据集，相反C不是很大，泛化能力强，就”just right”。

Mathematics Behind Large Margin Classification

为了方便推导和直观的理解，我们考虑只有两个参数的情况（多维可以推广）并将 θ0${\theta }_0$ 简化处理为0。首先我们对最小化函数进行转化，可以发现我们的最小化函数，其实就是我们系数向量在二维平面上的长度的平方。我们的约束条件 θTx(i)${\theta }^T{x}^{(i)}$ 两个向量的内积，其实是等价于 p(i)⋅‖θ‖$p^{(i)}\cdot \Vert \theta \Vert$ , p(i)$p^{(i)}$ 为向量 x(i)$x^{(i)}$ 在 θ$\theta$ 上的投影，‖θ‖$\Vert \theta \Vert$ 为向量 θ$\theta$ 的长度。

我们知道我们其实是要拟合一条直线去分隔这个平面，而直线方程就是 θTx=0${\theta }^{T}x=0$ ， 那么对应的向量 θ$\theta$ 就是直线的法向量。如果我们拟合出下图左下角的绿色直线，那么这种情况下，我们发现x(i)$x^{(i)}$ 在 θ$\theta$ 上的最小的投影非常小，那么为了满足约束条件，θ$\theta$ 长度就得很大，而我们需要最小化的就是 θ$\theta$ 的长度，那么显然这条线就不合理，不是我们所求，在看右下角的图，x(i)$x^{(i)}$ 在 θ$\theta$ 的最小投影相对取到最大，那么 θ$\theta$ 的长度就能对应的取到最小，也就是我们所求。

---

小广告

淘宝choker、耳饰小店 物理禁止
女程序员编码时和编码之余 都需要一些美美的choker、耳饰来装扮自己
男程序员更是需要常备一些来送给自己心仪的人
淘宝小店开店不易 希望有缘人多多支持 (O ^ ~ ^ O)
本号是本人 只是发则小广告 没有被盗 会持续更新深度学习相关博文和一些翻译
感谢大家 不要拉黑我 ⊙﹏⊙|||°