Lecture 16:SVM

Hinge Loss+kernel method = SVM

Hinge Loss

SVM与logistic regression的区别即在于loss function的不同,logistic是cross entropy,而SVM是hinge loss

也即如果分类间隔大于1,则 $L(m_i)=max(0,1−m_i(w))$,则损失为0。因此SVM更具鲁棒性,因为对离群点不敏感。

对于linear SVM:

  • 定义函数 $f(x)=\sum_i w_i x_i +b=w^T x$
  • 定义损失函数 $L(f)=\sum_n l(f(x^n),\hat{y}^n)+\lambda ||w||_2$,其中$l(f(x^n),\hat{y}^n)=max(0,1-\hat{y}^n f(x))$
  • 梯度下降求解(省略了正则化)

因此最终有:

我们接下来用$c^n(w)$替代$-\delta(\hat{y}^n f(x^n)<1) \hat{y}^n$

Kernel Method

一个事实:$w$是$x$的线性加和,其中$α$不等于0对应的$x$就是support vectors

证明:
我们前面说过,更新过程:

将其组织成向量形式:

如果我们将$w$初始化成0向量,那么$w$最终就是$x$的线性组合。证毕

因为$c(w)$是hinge loss,因此大多数的值是0,会造成$α$稀疏。
如果我们将训练数据$x$组织成一个矩阵,那么有:

也即:

所以对于$f(x)$,有:

实际上$X^Tx$就是每个训练数据和$x$进行点积的结果,但实际上线性函数往往表达能力不强,我们希望$x$能够变成非线性的。如果我们引入kernel,将点积换成kernel,则会有:

所以我们的问题就变成了:

  • 定义函数 $f(x)=\sum_n \alpha_n K(x_n,x)$
  • 找到最佳的α,最小化loss function:$L(f)=\sum_n l(f(x^n),\hat{y}^n)=\sum_n l(\sum_{n’} \alpha_{n’} K(x^{n^{‘}},x^n),\hat{y}^n)$

实际上我们不需要真的知道$x$的非线性的具体形式,我们只需要会算$K$就行,这种绕过$x$的具体形式的方法就是kernel trick。直接计算$K$,比先将$x$非线性转化再做点积来得高效。甚至有时候,我们对$x$做的非线性是无穷多维的,是无法直接做非线性化的。比如RBF核:

通过泰勒展开可以知道,RBF核是无穷维的。

另一个kernel的例子是sigmoid kernel:

当我们使用sigmoid kernel时,就相当于一层hidden layer的神经网络,如图:

给定一个输入,共有n个neuron,其中的weight就是每个训练数据的向量值,然后再将这些neuron加和得到输出。当然大部分的α的值是0,因此实质上神经元的个数和support vector的个数一致。

我们可以直接设计kernel,而不需要考虑x的非线性变换的形式,只要kernel符合mercer’s theory即可。