碎碎念

好久不更新,四月重新开始!

台大李宏毅机器学习——SVM

机器学习的算法太多了,但是很多算法之间的差异实际上不大。SVM是曾经风靡一时,一度虐杀神经网络的算法,不过DL出现以后,没落了不少啊。真是三十年河东三十年河西。

这里简单学习一下SVM。SVM跟其他的机器学习算法的差别在于,第一,loss function不一样,第二,有一个kernel function。其中的kernel function是大杀器。

现在我们假想我们要学的是一个二分类的问题,我们回顾一下几种损失函数。最开始的时候,我们学的是平方误差,也就是MSE,在二分类问题上,我们想要达到的效果就是当\(y=1\)的时候,\(f(x)\)越接近1越好,同理,\(y=-1\)的时候,\(f(x)\)越接近-1越好。那么基于square error,我们可以得到: \[ \begin{cases} (f(x) - 1)^2 & \mbox{if } y = 1 \\ (f(x) + 1)^2 & \mbox{if } y = -1 \end{cases} \] 那其实上面两个式子可以统一成\((yf(x) - 1)^2\)

那逻辑回归的loss function是cross entropy,那实际上也可以写作是\(\ln(1+\exp(-yf(x)))\)。之前的adaboost的loss function我们也可以用exponential loss来表示,也就是\(\exp(-yf(x))\),那么我们将这几种loss function跟最简单的\(\delta(f(x) \ne y)\)对比一下:

那我们回过头看一下,如果是用\(\delta\)函数,那么我们根本就没有办法求梯度。而如果我们用square loss,我们可以发现,左右两边的loss都很大,但是实际上,当\(f(x)\)\(y\)的方向一致,两个乘积非常大,本质上loss应该趋近于0才对,所以square loss不是非常合适。那另外的logistics loss跟exponential loss,都可以做到越远越好。另外这里需要注意一下,为了让logistics loss能够成为\(\delta\)函数的upper bound,我们会将原来的公式除以\(\ln 2\)

那么SVM呢?SVM用的是hinge loss,hinge loss表示为:\(\max(0, 1-yf(x))\)。那hinge loss的一个好处就是,当\(f(x)\)\(y\)一致,就可以了,那么hinge loss的好处就是,hinge loss对异常值比较不敏感,差不多就好了,而cross entropy跟exponential loss都会拼命去拟合异常值。

那linear SVM实际上就是logistics regression把loss function换成hinge loss。所以假设也是: \[ f(x) = \sum_i w_i x_i + b \] 而loss function就是: \[ L(f) = \sum_n(l(f(x_n), y_n)) + \lambda \|w_i\|_2 \] 那么,实际上,如果我们神经元用了一个linear SVM,一样也是可以做deep learning的。所以,嗯,别整天BB自己在做DL,好好学基础再BB。

那么SVM的loss function不是处处可微分的,有没有可能做梯度下降呢。实际上,DL中的ReLU函数都可以,所以SVM实际上也是可以做的。那求导的过程是这样的: \[ \frac{\partial l(f(x_n), y_n)}{\partial wi} = \frac{\partial l(f(x_n), y_n)}{\partial f(x_n)} \frac{\partial f(x_n)}{\partial w_i} \] 那其实\(\frac{\partial f(x_n)}{\partial w_i}\)就是\(x_n^i\)

\(\frac{\partial l(f(x_n), y_n)}{\partial f(x_n)}\)怎么计算呢,这是一个分段函数,所以分段求导: \[ \frac{\partial \max(0, 1 - y_n f(x_n))}{\partial f(x_n)} = \begin{cases} -y_n & \mbox{if } y_n f(x_n) < 1 \\ 0 & \mbox{if } y_n f(x_n) \ge 1 \end{cases} \] 所以实际上linear SVM的梯度就是: \[ \frac{\partial L(f)}{\partial w_i} = \sum_n -\delta(y_n f(x_n) < 1) y_n x_n^i \]

现在我们回过头看一下,因为用梯度下降,所以我们可以用一个linear combination来表示\(w\),也就是表示为:\(w^* = \sum_n \alpha_n^* x_n\)。那实际上可以这样表示是因为: \[ w_i^t = w_i^{t-1} - \eta \sum_n -\delta(y_n f(x_n) < 1) y_n x_n^i \] 这个式子如果将\(w\)串成一个vector来看,那么就是 \[ w^t = w^{t-1} - \eta \sum_n -\delta(y_n f(x_n) < 1) y_n x_n \] 那实际上这个迭代到最后,\(w\)就是\(x\)的一个linear combination。这样一来,我们就可以把\(w\)直接表示为\(w = \boldsymbol{X \alpha}\)。那我们因为用的是hinge loss,所以正确分类的sample就不会再提供梯度,所以\(\boldsymbol{\alpha}\)是一个sparse的向量,这个向量我们就叫做support vector。这里要注意一点,如果没有做特殊说明,所有的vector这里都是表示列向量,所以这边的\(\boldsymbol{X}\)的行表示feature,列表示sample。

现在因为我们的模型是linear的,所以\(f(x) = w^{\top} x = \boldsymbol{\alpha}^{\top} \boldsymbol{X}^{\top} x = \sum_n \alpha_n K(x_n, x)\),这样我们就把kernel function带出来了。

kernel function的好处就是,非常方便快速可以做到feature transform。比如说,我们的kernel用的是polynomial,那么我们就是将\(x\)投影到\(\phi(x)\)。比如说我们要做的一个polynomial是将\(\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\)变成\(\begin{bmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{bmatrix}\),那么不用kernel function的话,我们需要先做feature transform,把所有的feature变成这样,然后计算。现在因为有了kernel function,所以我们要做的事情就很简单,我们只要做\(\phi(x)\)跟对应的\(\phi(z)\)的inner product就可以了。也就是: \[ \begin{align} K(x, z) &= \phi(x) \cdot \phi(z) = \begin{bmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{bmatrix} \cdot \begin{bmatrix} z_1^2 \\ \sqrt{2} z_1 z_2 \\ z_2^2 \end{bmatrix} \\ &= x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2 \\ &= (x_1 z_1 + x_2 z_2)^2 \\ &= (x \cdot z)^2 \end{align} \] 所以有了这个kernel function,我们就可以很快速做到feature transform。那上面这个变化就是做了一个二阶的多项式变化。

那如果我们用的是radial的kernel,实际上我们就做到了无穷多阶的polynomial。怎么说呢?radial的kernel做的事情是\(K(x, z) = \exp(-\frac{1}{2} \|x - z\|_2)\),我们化简一下这个公式: \[ \begin{align} K(x, z) &= \exp(-\frac{1}{2} \|x - z\|_2) \\ &= \exp(-\frac{1}{2} \|x\|_2 -\frac{1}{2} \|z\|_2 + x \cdot z) \\ &= \exp(-\frac{1}{2} \|x\|_2) \exp(-\frac{1}{2} \|z\|_2) \exp(x \cdot z) \\ &= C_x C_z \exp(x \cdot z) \end{align} \] 现在开始表演了,我们得到\(\exp(x \cdot z)\),根据泰勒展开,我们得到的是\(\sum_0^{\infty} \frac{(x \cdot z)^i}{i!}\),这就是一个无穷多维的多项式了,也就意味着,我们将原来的feature映射到了无穷多维的空间中去,而不需要提前做feature transform。不过这里的问题就是,因为维度太高了,一来运算慢,二来很可能过拟合。

最后介绍一个很常见的kernel,就是sigmoid kernel。sigmoid kernel的公式是\(K(x, z) = tanh(x \cdot z)\),那在实作的时候,其实我们的公式是这样的\(K(x_n, x)\),所以我们可以将这个过程看作是一个单层的神经网络,结构如下:

也就是说将每个\(x\)的各个维度的值当做为weight,所以有多少样本就有多少neuron。