支持向量机

本文将简述支持向量机(SVM)的原理与大致推导过程.

1 支持向量与间隔

给定训练样本$D=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\dots,(\boldsymbol{x}_N,y_N)\},\boldsymbol{x}_i\in\mathbb{R}^L,y_i\in\{-1,+1\}$，其中输入数据的特征维度为$L$，类别标签为二分类. 直观上，我们希望在样本空间中用一个超平面将样本分为两类，该超平面可以表示为：

$$\boldsymbol{w}^T\boldsymbol{x}+b=0, \tag{1}$$

其中，$\boldsymbol{w}=[w_1;w_2;\dots,w_L]$为超平面的法向量.

为了能使超平面将样本很好地分类，我们希望最大化最小间隔，所以下面计算点到超平面的距离：

设$\boldsymbol{x}$投影到超平面上的点为$\boldsymbol{x}_0$，有$\boldsymbol{x}_{\perp}=\boldsymbol{x}-\boldsymbol{x}_0$与法向量$\boldsymbol{w}$平行. 则点$\boldsymbol{x}$到超平面的距离为$r=||\boldsymbol{x}_{\perp}||$.

$$\begin{align} \boldsymbol{x}_{\perp}&=r\frac{\boldsymbol{w}}{||\boldsymbol{\boldsymbol{w}}||}, \newline r&=\frac{\boldsymbol{w}^T\boldsymbol{x}_{\perp}}{||\boldsymbol{w}||} \newline &=\frac{(\boldsymbol{w}^T\boldsymbol{x}+b)-(\boldsymbol{w}^T\boldsymbol{x}_0+b)}{||\boldsymbol{w}||} \newline &=\frac{\boldsymbol{w}^T\boldsymbol{x}+b}{||\boldsymbol{w}||}. \tag{2} \end{align}$$

若该超平面能将训练样本正确分类，则始终有：

$$y_i(\boldsymbol{w}^Tx_i+b)\geqslant1. \tag{3}$$

使等号成立的向量即”支持向量”(support vector).

由公式$(2)$，我们需要最大化两个类别的支持向量到超平面的距离之和$\frac{2}{||\boldsymbol{w}||}$，即”间隔”(margin). 最大化该距离等价于下面的优化问题，也即找到具有最大间隔的划分超平面：

$$\begin{align} \min\limits_{\boldsymbol{w},b}\quad&{\frac{1}{2}||\boldsymbol{w}||^2} \newline \text{s.t.}\quad&y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\geqslant1,\quad i=1,2,\dots,m. \end{align} \tag{4}$$

公式$(4)$即支持向量机的基本型.

2 对偶问题

公式$(4)$很难进行最优化求解，所以这种情况下可以使用拉格朗日乘子法构造最优化问题$(4)$的”对偶问题”(dual problem)，来求解该最优化问题. 对式$(4)$的每个约束条件添加拉格朗日乘子$\alpha_i\geqslant0$，则该问题的拉格朗日函数为：

$$L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}||\boldsymbol{w}||^2+\sum_{i=1}^N\alpha_i(1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)), \tag{5}$$

其中，$\boldsymbol{\alpha}=(\alpha_1;\alpha_2;\dots;\alpha_N)$.

令$L(\boldsymbol{w},b,\boldsymbol{\alpha})$分别对$\boldsymbol{w}$和$b$的偏导为0，再代入式$(5)$中将$\boldsymbol{w}$与$b$消去，则得到了原优化问题的对偶问题：

$$\begin{align} \max\limits_{\alpha}\quad&{\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j}. \newline \text{s.t.}\quad&\sum_{i=1}^N\alpha_iy_i=0, \newline &\alpha_i\geqslant0,\quad i=1,2,\dots,N. \end{align} \tag{6}$$

此外，上式还需满足$K.K.T.$条件：

$$\begin{align} &\alpha_i\geqslant0; \newline &y_if(\boldsymbol{x}_i)-1\geqslant0; \newline &\alpha_i(y_if(\boldsymbol{x}_i)-1)=0. \end{align} \tag{7}$$

解出$\boldsymbol{\alpha}$后得到模型：

$$f(\boldsymbol{x})=\sum_{i=1}^N\alpha_iy_i\boldsymbol{x}_i^T\boldsymbol{x}+b. \tag{8}$$

3 核函数

注意到若样本$\boldsymbol{x}$在原始空间中线性不可分，那么我们希望将样本从原始空间映射到一个线性可分的更高维的空间，因此通过映射后的模型可以表示为：

$$f(\boldsymbol{x})=\boldsymbol{w}^T\phi(\boldsymbol{x})+b. \tag{9}$$

但求解式$(9)$的对偶问题需要计算$\phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}_j)$，其计算代价通常很大. 所以我们设想一个函数：

$$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\langle\phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}_j)\rangle. \tag{10}$$

将式$(10)$代入式$(6)$，重写以后求解可得到模型在使用核函数时的表示：

$$f(\boldsymbol{x})=\sum_{i=1}^N\alpha_yy_i\kappa(\boldsymbol{x},\boldsymbol{x}_i)+b. \tag{11}$$

公式$(10)$被称为”核函数”(kernel function).

4 折页损失

通常，由于很难恰巧找到一个可以将所有样本分类的超平面，我们引入了软间隔的概念来放松约束条件. 在这种情况下，一种常用的损失函数是折页损失 (Hinge Loss)：

$$l_{hinge}(z)=\max(0,1-z). \tag{12}$$