Linear SVM model

Step1: Function Model

$f(x) = \sum_{i}{w_ix_i+b} = \begin{bmatrix}w \\ b\end{bmatrix}\cdot \begin{bmatrix}x \\ 1\end{bmatrix}=w^Tx$

Step2: Loss Function

$L(f) = \sum_n{l(f(x^n, \hat{y}^n))+\lambda\left\|w\right\|_2} \\ l(f(x^n, \hat{y}^n)) = max(0, 1-\hat{y}^nf(x))$

Loss function的第一项是一个凸函数，第二项也是个凸函数，因此loss function整体也是凸函数。有不可微分的地方，但是可以用梯度下降做优化器。第一项的定义涉及了loss function，也就是Hinge Loss的方法。

第一项中的是代表属于哪一个class的label，是预测后的分类结果。

Step3: Gradient Descent

第一种理解

做微分，先不考虑第二项。

$\begin{array}{ll} \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)}}\cdot\frac{\partial{f(x^n)}}{\partial w_i}\\ &=\frac{\partial{l(f(x^n, \hat{y}^n))}}{\partial{f(x^n)}}\cdot x_i^n \\ &= c^n(w) \cdot x_i^n \end{array}$

diff

第二种理解

用一个极小项取代损失函数L中的，我们叫这个极小项是一个slack variable。

lossfunctionequal

Kernel Method

Dual Representation

hingeloss

如果对于之前求出的迭代更新的式子，把初始化为0，式子变成所有数据的线性组合。

线性参数可能是0，因为结合前面在定义Loss function的时候选择了Hinge Loss。也就是有可能就是取0（在fit很好的情况下），有可能不是0（在fit不好的情况下），到最后模型越fit，线性参数线性参数取0越多，越sparse。

support vectors就是那些线性参数不为0的。

这样结合的好处是：不是支持向量的数据点（有可能是outlier），去掉（线性参数是0）也不会有多大影响。如果用了Cross Entropy定义loss function，每一笔data对模型参数的迭代结果都有影响。

Kernel Trick

改写函数集为Kernel Function

重新表示模型参数为

modelinput

重新表示模型函数集为

$f(x) = w^Tx = \boldsymbol{\alpha}^TX^Tx=\sum_na_n(x^n\cdot x)$

modeloutput

把内积写成核方法就是核函数，称为核技巧。写成这样的好处就是，不用具体的知道每一个data的向量表示求出内积，我们只需要知道Kernel Function的输出就可以了。

接下来最小化损失函数，也就是训练目的：找一组，是loss function最小。好处是只需要知道input data vector之间的内积。

什么时候用Kernel Trick？

不止用在SVM中。当我们对data的表示比较困难，或者说需要对input data用好几个hidden layer做feature transform，这时候Kernel trick is useful when we transform all x to 。

我们需要把feature transform后的多个data vector做inner product，因为做feature transform之后维度变大了，所以运算量很大。

而Kernel Trick告诉我们，你直接算原来的data vector，做inner product再平方就可以了，和上面的过程得出的结果是一样的。

依据核函数的定义方式有很多变化。

Radial Basis Function Kernel

在一个无穷多维的空间做inner product。推导涉及exp函数的泰勒展开。

Sigmoid Kernel

$K(x,z) = tanh(x \cdot z)\\ f(x) = \sum{\alpha_nK(x^n,x)} = \sum{\alpha_n tanh(x^n \cdot z)}$

每一个函数都可以看作一个Neuron Network。原始数据到第一层neuron的weight就是每一个data point，neuron的数目就是support vectors的数目。

sigmoidkernel