HongYiLee SVM Notes

标签： SVM MachineLearning Notes

HongYiLee Support Vector Machine Notes

简单来说，我们可以将支持向量机看成是Hinge Loss一个特殊的Loss Function加上Kernel Method 核技巧.

Hinge Loss

回到机器学习三步走：

Define a Function Set
Define a Loss Function
Pick the Best Function in Your Set

在Binary Classification二分类问题中，我们可以定义这样的函数集合：

g (x) = {\begin{cases} + 1 f (x) > 0 \\ - 1 f (x) < 0 \end{cases}

这里定义为+1或者-1都是为了方便起见，1或者0都是一样的效果，并不会影响分类效果，但是为了方便推导，这里定为+1和-1.

在这样的情况下，理想情况下的Loss Function会是这样（用 $L (f)$ 来表示）：

L (f) = \sum_{n} δ (g (x^{n}) \neq {\hat{y}}^{n})

${\hat{y}}^{n}$ 表示的是训练集上的每一个实例的标签， $g (x^{n})$ 是我们的预测结果。 $δ$ 函数源于信号与系统，当 $g (x^{n})$ 与 ${\hat{y}}^{n}$ 不相等时，为1.

这是一个理想的Loss Function，但是理想总是过于丰满（QAQ）。这个函数不可微分，那么意味着我们不能用Gradient Descent 来求解最优解。所以我们想要找到一个替代的Loss Function 用 $l (f)$ 来表示，来取得近似的结果，这个函数需要可微。
也即：

L (f) = \sum_{n} l (f (x^{n}), {\hat{y}}^{n})

那下面的问题就是如何来找到一个合适的 $l (f)$ 了。

简单来说，我们希望在 ${\hat{y}}^{n}$ 为+1时， $f (x^{n})$ 要越大越好， ${\hat{y}}^{n}$ 为-1时， $f (x^{n})$ 要越小越好。整体来说，我们希望这两者要是同号的，而且 ${\hat{y}}^{n} f (x^{n})$ 的值要是越大越好。因此如果我们以 ${\hat{y}}^{n} f (x^{n})$ 为横坐标，loss 的值为纵坐标，那么在 $x$ 的右边值应该要下降，而在左边应该要上升。

那么下面做几个尝试：

平方误差，也就是最常用的Square Loss

l (f (x^{n}), {\hat{y}}^{n}) = ({\hat{y}}^{n} f (x^{n}) - 1)^{2} = {\begin{cases} (f (x^{n}) - 1)^{2} {\hat{y}}^{n} = 1 \\ (f (x^{n}) + 1)^{2} {\hat{y}}^{n} = - 1 \end{cases}

这个函数显然是不合理的，因为在 ${\hat{y}}^{n} f (x^{n})$ 大于零且变得更正的时候，误差竟然变得很大，这显然是不合理的。

Square Loss + Sigmoid Function

l (f (x^{n}), {\hat{y}}^{n}) = (σ ({\hat{y}}^{n} f (x^{n})) - 1)^{2} = {\begin{cases} (σ (f (x^{n})) - 1)^{2} {\hat{y}}^{n} = 1 \\ (σ (f (x^{n})))^{2} {\hat{y}}^{n} = - 1 \end{cases}

然而我们知道这样的表现也不会是很好，从曲线中可以看到，但loss 的值和很大的时候，下降的速率却不是很快，这并不是我们想要的。在分类问题中，我们常用的还有交叉熵。

Cross Emtrypy + sigmoid
在使用交叉熵的时候，损失函数可以写成如下：

l (f (x^{n}), {\hat{y}}^{n}) = l n (1 + e x p (- {\hat{y}}^{n} f (x^{n})))

这时，这个函数虽然不能够表示为原来理想情况下的损失函数，但是却可以成为它的一个上界。

Hinge Loss

l (f (x^{n}), {\hat{y}}^{n}) = m a x (0, 1 - {\hat{y}}^{n} f (x))

进一步做分析，可以看到，Hinge Loss中出现了0项，那么当什么情况下Loss 的值会是0或者被认为是“完美无缺”呢？

if ${\hat{y}}^{n} = 1$ :

l (f (x^{n}), {\hat{y}}^{n}) = m a x (0, 1 - f (x)) = {\begin{cases} 0, f (x) > 1 \\ 1 - f (x), f (x) < 1 \end{cases}

if ${\hat{y}}^{n} = - 1$ :

l (f (x^{n}), {\hat{y}}^{n}) = m a x (0, 1 + f (x)) = {\begin{cases} 0, f (x) < - 1 \\ 1 + f (x), f (x) > - 1 \end{cases}

可以看出，Hinge Loss实际上是一种很懒惰的函数，若 ${\hat{y}}^{n}$ 为+1，当 $f (x^{n})$ 大于1的时候，就认为是足够好而不再下降， ${\hat{y}}^{n}$ 为-1，当$f(x^n)小于-1则认为是足够好而不再下降。但是正是因为这种懒惰特性，使其对于离群点outlier 的情况更加的稳定，而不容易受到影响。绘制其特图像，会发现很像ReLU 函数。这样的函数在某些点是不连续的，但是仍然是大部分可微的，可以用梯度下降来求解。

下面是上述各损失函数的对比图像：
HongYiLee SVM Notes

Linear SVM

总结一下，我们得到了线性情况下的支持向量机，

Function Set
$f (x) = \sum_{i} w_{i} x_{i} + b = [\begin{matrix} w \\ b \end{matrix}] \times [\begin{matrix} x \\ 1 \end{matrix}] = w^{T} x$
Loss Function

l (f (x^{n}), {\hat{y}}^{n}) = m a x (0, 1 - {\hat{y}}^{n} f (x))

Gradient Descent

\frac{\partial l (f (x^{n}), {\hat{y}}^{n})}{\partial w_{i}} = \frac{\partial l (f (x^{n}), {\hat{y}}^{n})}{\partial f (x^{n})} \frac{\partial f (x^{n})}{\partial w_{i}} x_{i}^{n}

这里：

f (x^{n}) = w^{T} x^{n}

\frac{\partial m a x (0, 1 - {\hat{y}}^{n} f (x^{n}))}{\partial f (x^{n})} = {\begin{cases} - {\hat{y}}^{n}, {\hat{y}}^{n} f (x^{n}) < 1 \\ 0, {\hat{y}}^{n} f (x^{n}) > 1 \end{cases}

\frac{\partial L (f)}{\partial w_{i}} = \sum_{i} - δ ({\hat{y}}^{n} f (x^{n}) < 1) {\hat{y}}^{n} x_{i}^{n}

我们可以让 $c^{n} (w) = - δ ({\hat{y}}^{n} f (x^{n}) < 1) {\hat{y}}^{n}$ 这一项是取决于当前的 $w$ 的。

如果我们定义 $ε^{n} = m a x (0, 1 - {\hat{y}}^{n} f (x))$ 那么损失函数可以写作：

L (f) = \sum_{n} ε^{n} + λ | | w | |_{2}

在要求minimizing的情况下，义 $ε^{n} = m a x (0, 1 - {\hat{y}}^{n} f (x))$ 与下面等价：

{\begin{cases} ε^{n} \geq 0 \\ ε^{n} \geq 1 - {\hat{y}}^{n} f (x) \end{cases}

所以我们可以推出：

{\hat{y}}^{n} f (x) \geq 1 - ε^{n} ε^{n} \geq 0

这个就是常见的SVM，支持向量机。

那么对于线性的支持向量机，Linear Suppor Vector Machine 我们可以直接使用梯度下降的方式来求解，并且能够得到收敛的结果。而对于更高维的情况我们需要用到Kernel Method 。对于核技巧的方面，在下一篇记录和讲解。

HongYiLee SVM Notes

HongYiLee SVM Notes

HongYiLee Support Vector Machine Notes

Hinge Loss

Linear SVM

相关推荐