前言

支持向量机(Support Vector Machine,SVM)是一个能求解通用二元分类问题的模型。SVM使用Kernel trick，使得自己在能够表示非线性函数的同时Loss是有闭式解的Convex function。也有人把SVM当作线性模型向神经网络过渡的中间阶段。

SVM

对于

$$D = \{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\} , y_i \in \{-1,+1\}$$

的分类问题，SVM试图在n维空间上找一个超平面，wx+b，使得

• 当wx_i+b≥1时，yi=+1
• 当wx_i+b≤1时，yi=-1

并且超平面应该离两侧最近的点都尽可能远。解出这一组w和b就解出了SVM。

其实如果在将w和b并在一起作为新的w,将x后接1,则SVM可以进一步简化为wx:

$$f(x)= \sum_i w_ix_i+b = \left[ \begin{array}{c} w \\ b \end{array} \right] \cdot \left[ \begin{array}{c} x \\ 1 \end{array} \right]$$

Hinge loss

回到分类问题本身，通常Loss会选择在整个训练集上分类错误的次数：

$$L(f)=\sum_i \delta(g(x^n) \not ={\hat{y}^n})$$

其中δ函数的为真时值为1，反之值为0。
正如对率回归中所说，
在分类问题上使用这类函数是不利于训练的，因此希望找到一个函数

$$l(f(x^n),\hat y^n)$$

来近似代替δ函数。

hinge loss就是这样的一个函数。他是这么定义的：

$$l(f(x^n),\hat y^n)=\max(0,1-\hat y^nf(x))$$

图中紫色的线就是hinge loss。横坐标1处，hinge loss把两条直线连接起来，就像是连接骨头的关节(hinge)，因此得名。

从图上可以看出

• MSE随着横坐标的增加loss反而增加，根本不适用
• sigmoid+square loss对横坐标的变化不敏感(saturate)，训练起来也不好做
• sigmoid+cross entropy会积极的将坐标点往右推，但其实只要横坐标超过了1就已经足够了

cross entropy好像完美主义者，而hinge loss会想着及格就好。既然在现实世界里两者的性能是一致的，我们也就乐得省下这些无畏的开销。

Gradient descent

hinge loss对w的偏微分后，得到梯度下降的公式

$$w_{i+1}=w_i-\eta\sum_n c^n(w)x_i^n$$

其中

$$c^n(w) = -\delta(\hat y^nf(x^n)<1)\hat y^nx_i$$

soft margin

将整体的损失函数L

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

中的l用ε代替，得到下列形式

$$L = \sum_n\epsilon^n+\lambda|w|_2$$ $$\hat y^nf(x) \ge1-\epsilon^n$$

而不是硬性规定

$$\hat y^nf(x) \ge1$$

ε作为边界条件的放松，被称作松弛变量(slack variable)

Support vector

SVM的w是所有训练样本点的线性组合，并且多数点的系数都是0(sparsity)。

这个性质可以从KKT系数反映出来

当然，它也可以从另一个角度说明。

考虑梯度下降的式子

$$w_{i+1}=w_i-\eta\sum_n c^n(w)x_i^n$$

其中

$$c^n(w) =\frac{\partial l(f(x^n),\hat y^n)}{\partial f(x^n)}=-\delta(\hat y^nf(x^n)<1)\hat y^nx_i$$

当w被初始化为0向量时，每一次参数更新加上了一个样本点的线性组合；而hinge loss有大约一半的定义域里微分是0，因此大部分系数会为0

Kernel method

既然w是X的一个线性组合，将其写作w=Xα。
带入f(x)

$$f(x)=w^\top x = \sum_n \alpha_n(x^n \cdot x)$$

将x^n与x的内积用函数K(kernel function)表示，则

$$f(x)=\sum_n \alpha_nK(x^n,x)$$

将得到的f(x)带入loss，发现L(f)与x已经无关了，可以直接进行梯度下降。这就是Kernel trick

若我们先对x做feature transform φ(x)，φ(x)·φ(z)有时可以表示为K(x,z)。这即扩展了SVM的表述能力，也提高了效率。

在使用RBF Kernel时，可以在无穷维空间做内积

SVM and Neural network

SVM也可以被看作是有一层hidden unit的神经网络:

每一个neural的weight是x^n与x的内积，所有neural的输出经过tanh后再以α为权值求和就得到输出了。

实际上，SVM也可以看作是一个神经网络。

• Kernel function相当于是神经网络中做feature transform的hidden layer
• SVM学到的分类器与神经网络的输出层学到的分类器是一致的。