Support Vector Machine

方法论

对于一个普通的线性二分类问题，我们期望找到这么一个决策边界$\omega ^Tx+b=0$（式中$\omega$与$x$均为向量），使得该决策边界能够完全地把数据集中正类和负类隔开：

Fig. 1. Linear binary classification

在逻辑回归（Logistic Regression）中，我们用的方法本质上是通过凸优化逐步拟合该边界的参数，使得正负类分别位于直线两侧：

$$
\begin{align*}
\hat{y}^{(i)}=&\frac{1}{1+\exp(-\omega ^Tx-b)}\\
L=\frac{1}{m}\sum _{i=1} ^{m}[-y ^{(i)}\log&(\hat{y}^{(i)})-(1-y ^{(i)})log(1-\hat{y}^{(i)})]
\end{align*}
$$

式中，$m$为训练集样本数。由于所有的样本点都将参与到损失函数$L$中，任何一个样本点的偏移都会产生新的梯度而导致决策边界发生一定的偏移。然而，样本终究只是数据的观测值，总会存在一定的噪声使得观测值与真实值存在偏差，假设该噪声表现为最一般的高斯噪声，则一个样本的真实数据值实际上在该样本值的附近：

Fig. 2. Gaussian noise

由于逻辑回归未考虑这些噪声，近似得到的决策边界可能不是最佳的边界。而SVM则不同，它只考虑距离决策边界近的点，并期望这些离决策边界近的点距离决策边界越远越好。这样做的好处是远离决策边界的点无论怎么偏移都不会对决策边界造成影响：

Fig. 3. Decision boundary

上图便是采用SVM得出的决策边界，该决策边界实际上只由个别几个距离决策边界近的点决定，而这几个样本点就是支持决策边界的支持向量。

线性分类

对于如何获得线性分类问题的决策边界，逻辑回归和SVM采用了两种不同的思路。逻辑回归通过凸优化和梯度下降来迭代地获得近似解；SVM则通过最大化距离决策边界最近点到决策边界的距离来获得解析解。

Fig. 4. Linear binary classification

具体来说，对于任何一个二维平面（或超平面）内的决策边界$\omega ^Tx+b=0$，样本$(x ^{(i)},y ^{(i)})$到决策边界的函数间隔（Functional Margin）可以定义为：

$$
\hat{\gamma} ^{(i)}=y ^{(i)}(\omega ^Tx ^{(i)}+b)
$$

式中，$y ^{(i)}$正类取1，负类取-1，括号内的项实际上就是未用$||\omega||$归一化的$(x ^{(i)},y ^{(i)})$到直线$\omega ^Tx+b=0$的距离（带正负），而$y ^{(i)}$正好可以使得$\hat{\gamma} ^{(i)}$始终为正，因而$\hat{\gamma} ^{(i)}$就是广义的“距离”，称函数间隔。若将$\hat{\gamma} ^{(i)}$归一化，我们可以得到几何间隔（Geometric Margin）：

$$
\gamma ^{(i)}=\frac{\hat{\gamma} ^{(i)}}{||\omega||}=y ^{(i)}\frac{(\omega ^Tx ^{(i)}+b)}{||\omega||}
$$

要得到决策边界，我们只需要让距离决策边界最近的点距离决策边界最远即可，即：

$$
\max _{\omega,b}(\min _{i=1,...,m}\gamma ^{(i)})
$$

式中，我们使用了几何间距。几何间距实际上是限制向量$\omega$为单位向量后的函数间距。这种限制的缺点在于，$\omega$的值只能在一个单位圆域的边界上取得：

$$
||\omega||=1
$$

进而导致$\omega$的取值域不是一个凸集，我们也就很难以凸优化的方法来求解决策边界。

在欧氏空间中，凸集是对于集合内的每一对点，连接该对点的直线段上的每个点也在该集合内。显然，只包括边界的圆不是凸集。

Fig. 5. Circle field

所以，采用$\gamma ^{(i)}$的原始形式更好：

$$
\max _{\omega,b}(\min _{i=1,...,m}\frac{\hat{\gamma} ^{(i)}}{||\omega||}) \tag{1}
$$

此时，$\omega$的取值将不再受到限制。更进一步地：
$$
\min _{i=1,...,m}\frac{\hat{\gamma} ^{(i)}}{||\omega||}
$$

可以直接用$\hat{\gamma}/{||\omega||}$表示，其中：

$$
y ^{(i)}(\omega ^Tx ^{(i)}+b)\ge\hat{\gamma},\space\space i=1,...,m
$$

上式可被视作一个限定条件，限定$\omega$与$b$必须在一个指定的集合中：

Fig. 6. Inequality field

线性不等式切出的域一定是个凸集。

则我们实际上可以简单地令$\hat{\gamma}=1$，于是式$(1)$便简化为：

$$
\max _{\omega,b}\frac{1}{||\omega||} \tag{2}
$$

进一步地将$\omega$放在分母，我们可得：

$$
\min _{\omega,b} \frac{||\omega|| ^2}{2}\space\space\text{s.t} \space\space y ^{(i)}(\omega ^Tx ^{(i)}+b)\ge 1,\space\space i=1,...,m \tag{3}
$$

平方与分母中的$2$是为了方便求导。

采用拉格朗日乘数法分别求解限定条件下边界和内部的极值便可得到决策边界的解析解。得到解析解后，对任意点$x$计算$\text{sign}(\omega ^Tx+b)$便可得到它的分类结果。这就是SVM，它实际上是一种最大间隔分类（Maximum Margin Classification）。

实际求解要更加复杂，常用的方法有内点法（Interior Point Method, IPM）和序列最小优化（Sequential Minimal Optimization, SMO）。

软边距

式$(3)$对于Fig. 1（Fig. 4）所示的样本分布实际上是无解的，因为负例中有一个点混入了正例中，导致无法得到一个能够完全划分正例和负例的决策边界。为了解决这个问题，可以在式$(3)$的限定条件中加入松弛变量$\xi$（Slack Variable），使得某些样本点到决策边界的距离不一定严格地大于$1$，甚至可以小于$0$：

$$
\begin{align*}
y ^{(i)}(\omega ^Tx ^{(i)}&+b)\ge 1-\xi _i,\space\space i=1,...,m\\
&\xi _i \ge0\space\space i=1,...,m
\end{align*}
$$

引入松弛变量后，式$(3)$变为：

$$
\begin{align*}
\min _{\omega,b, \xi} (\frac{||\omega|| ^2}{2}&+C\sum _1 ^m \xi _i) \tag{4} \\
\text{s.t} \space\space y ^{(i)}(\omega ^Tx ^{(i)}+b)\ge 1-&\xi _i,\space\space \xi _i \ge 0,\space\space i=1,...,m
\end{align*}
$$

式中$C$是一个超参数，新加入的项$\sum _1 ^m \xi _i$是一个正则项，称L1 regularization。该正则项是一类关于模型“先验知识”，可以提高SVM分类的鲁棒性和效率。

这样的SVM称软边距SVM，而之前的则称硬边距SVM。

非线性分类

非线性分类问题，即仅用一条直线无法将正负类区分开的问题，如下图所示，我们必须用两条直线才能将这四个交叉分布的样本点区分开（1、3象限为负，2、4象限为正）：

Fig. 7. Non-linear classification

对于这样的问题，常规的线性SVM是无法解的。一个很自然的想法是用函数$\phi(x)$将$x$映射到新空间，使得$x$在新空间线性可分，这时，式$(4)$便变为：

$$
\begin{align*}
\min _{\omega,b, \xi} &(\frac{||\omega|| ^2}{2}+C\sum _1 ^m \xi _i) \tag{5} \\
\text{s.t} \space\space y ^{(i)}[\omega ^T\phi(x ^{(i)})+b]& \ge 1-\xi _i,\space\space \xi _i \ge 0,\space\space i=1,...,m
\end{align*}
$$

但是，实际上我们并不会直接定义函数$\phi(x)$，而是定义核函数（Kernel Function）：

$$
K(x ^{(i)},x ^{(j)})=\phi(x ^{(i)}) ^T\phi(x ^{(j)})
$$

使用核函数的原因是，对决策边界的求解可以转为对其对偶问题的求解：

$$
\begin{align*}
\max _\alpha \sum _{i=1} ^m\alpha _i&-\frac{1}{2}\sum _{i=1} ^m \sum _{j=1} ^m[\alpha _i \alpha _j y ^{(i)}\phi(x ^{(i)}) ^T\phi(x ^{(j)})y ^{(j)}]\\
\text{s.t}\space\sum _{i=1} ^m\alpha _i &y ^{(i)}=0,\space\space 0\le\alpha _i\le C,\space\space i=1,...,m
\end{align*}
$$

对偶问题我也不太懂。

而后续的预测实际上用到的也只是$\phi(x ^{(i)}) ^T\phi(x)$：

$$
\begin{align*}
\omega^Tx+b=&[\sum _{i=1} ^m \alpha _i y ^{(i)}\phi(x ^{(i)})] ^T\phi(x)+b\\
=&\sum _{i=1} ^m\alpha _iy ^{(i)}\phi(x ^{(i)})^T\phi(x)+b
\end{align*}
$$

因此我们完全可以只定义核函数，而无需理会$\phi(x)$，只要保证核函数对各个$x ^{(i)}$和$x ^{(j)}$求值后得到的核矩阵$K$是半正定矩阵以保证$\phi(x)$的存在即可：

$$
K _{ij} =\phi(x ^{(i)}) ^T\phi(x ^{(j)})
$$

核矩阵是半正定矩阵的核函数的$\phi(x)$存在的证明略。

只定义核函数的另一个好处在于，一个很简单的核函数的$\phi(x)$可能十分复杂，如对于最常用的高斯核函数RBF Kernel：

$$
K(x,z)=\exp(-\frac{||x-z|| ^2}{2\sigma ^2})
$$

其$\phi(x)$是无穷维的。

不难看出$\phi(x)$与神经网络的编码器存在一定的等价性。