SVM

支持向量机

支持向量机（support vector machines）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，它在学习复杂的非线性方程时能提供一种更加清晰和强大的方法。

在 Logistic 回归中，如果要令 $y = 1$，则有 $h_\theta(x) = \dfrac{1}{1+e^{-\theta^Tx}} \approx 1$，即 $\theta^Tx \gg 0$；当 $y=0$ 时有 $h_\theta(x)\approx 0$，即 $\theta^Tx\ll 0$。

对于 Logistic 回归，其代价函数为

$$-(y\log h_\theta(x) + (1 - y) \log (1 - h_\theta(x)))$$

将 $h_\theta(x)$ 代入上述函数得

$$-y\log\dfrac 1{1+e^{-\theta^Tx}} - (1-y) \log (1 - \dfrac 1{1+e^{-\theta^Tx}})$$

当 $y = 1$ 时，代价函数变为 $-\log \dfrac1{1+e^{-z}}$，此时令 $z \to +\infty$，代价函数将会趋近于 0，这也是为什么在看见 $y = 1$ 这样的样本时，会将 $z$ 赋值为一个极大值；类似地，当看见 $y = 0$ 这样的样本时，会将 $z$ 赋值为一个极小值。

在 Logistic 回归中，我们的代价函数 $J(\theta)$ 为

$$J(\theta) = \min_{\theta}\dfrac 1m\left[\sum\limits_{i = 1}^my^{(i)}\left(-\log h_{\theta}(x^{(i)})\right) + (1 - y^{(i)})\left(-\log (1 - h_\theta(x^{(i)}))\right)\right] + \dfrac{\lambda}{2m}\sum\limits_{j = 1}^n \theta_j^2$$

上式中后一项为正则化参数。

在 SVM 中，代价函数为

$$J(\theta) = \min_\theta \left[C\sum\limits_{i = 1}^my^{(i)}\operatorname{cost}_1(\theta^Tx^{(i)}) + (1 - y^{(i)})\operatorname{cost}_0(\theta^Tx^{(i)})\right] + \dfrac{1}{2}\sum\limits_{j = 1}^n\theta_j^2$$

其中 $\operatorname{cost}_0$，$\operatorname{cost}_1$ 为合页损失函数。由于 $\dfrac 1m$ 是常数，对 $\theta$ 的取值不会造成影响，于是将 $\dfrac 1m$ 约去。在 SVM 中，权重参数将不在正则化项上，而是在前一项，按照惯例设为 $C$。

SVM 的输出并不是概率，而是预测值，即：

$$\begin{aligned} h_\theta(x) = \begin{cases} 1, &\text{if } \theta^\mathrm Tx \geq 0 \\ 0, &\text{otherwise} \end{cases} \end{aligned}$$

Large Margin Intuition

当 $C$ 非常大时，我们希望使第一项的值尽量为 0，则当 $y^{(i)} = 1$ 时，我们希望得到 $\theta^\mathrm Tx \geq 1$；当 $y^{(i)} = 0$ 时，我们希望得到 $\theta^\mathrm Tx \leq -1$，则此时最优化问题变为

$$\begin{aligned} &\min_{\theta} \dfrac 12 \sum\limits_{j=1}^n{\theta_j^2} \\ &\text{s.t. } \begin{cases} \theta^\mathrm Tx^{(i)} \geq 1, &\text{if } y^{(i)} = 1 \\ \theta^\mathrm Tx^{(i)} \leq -1, &\text{if } y^{(i)} = 0 \end{cases} \end{aligned}$$

通过求解上述的最优化问题，我们可以得到一个更加鲁棒的超平面（决策边界）。

距离超平面最近的几个训练样本点被称为支持向量，两个不同类支持向量到超平面的距离之和被称为间隔（margin）。

当 $C$ 非常大时，模型会对离群值非常敏感，有可能为了追求正确率而将间隔变小，所以我们需要调整参数 $C$ 以权衡间隔和错误率。

当样本不是线性可分时，也会出现上述情况，我们需要通过核化法将问题升维，以转化为线性可分的问题，或者容忍合适的错误率，以获取鲁棒的超平面。

The mathematics behind large margin classification

首先回顾向量的内积：设 $\vec u = \begin{bmatrix}u_1 \\ u_2\end{bmatrix}$，$\vec v = \begin{bmatrix}v_1 \\ v_2\end{bmatrix}$，则 $\vec u$ 和 $\vec v$ 的内积为 ${\vec u}^\mathrm T \vec v = p \cdot \|u\| = {\vec v}^\mathrm T \vec u = u_1v_1 + u_2v_2$，其中 $p$ 是 $\vec v$ 在 $\vec u$ 上的投影，$\|\vec u\|$ 表示 $\vec u$ 的长度（范数）。

在下面的过程中，我们对要最优化的目标函数做一些简化：令 $\theta_0 = 0$，$n = 2$，目标函数可以写做

$$\begin{aligned} &\dfrac 12 \sum\limits_{j=1}^n{\theta_j^2}\\ = &\dfrac 12\left(\theta_1^2 + \theta_2^2\right) \\ = &\dfrac 12 \left(\sqrt{\theta_1^2 + \theta_2^2}\right)^2 \\ = &\dfrac 12 ||\vec \theta||^2 \end{aligned}$$

其中，$\vec\theta = \begin{bmatrix}b_1 \\ b_2\end{bmatrix}$。

观察原最优化问题的限制条件：

$$\begin{cases} \theta^\mathrm Tx^{(i)} \geq 1, &\text{if } y^{(i)} = 1 \\ \theta^\mathrm Tx^{(i)} \leq -1, &\text{if } y^{(i)} = 0 \end{cases}$$

将限制条件和向量内积做对比，可以得到：

$$\begin{cases} p^{(i)} \cdot ||\vec\theta|| \geq 1, &\text{if } y^{(i)} = 1 \\ p^{(i)} \cdot ||\vec\theta|| \leq -1, &\text{if } y^{(i)} = 0 \end{cases}$$

其中 $p^{(i)}$ 表示 $x^{(i)}$ 在 $\vec \theta$ 上的投影。

此时原最优化问题成为：

$$\begin{aligned} &\min_{\theta} \dfrac 12 ||\vec \theta||^2 \\ &\text{s.t. } \begin{cases} p^{(i)} \cdot ||\vec\theta|| \geq 1, &\text{if } y^{(i)} = 1 \\ p^{(i)} \cdot ||\vec\theta|| \leq -1, &\text{if } y^{(i)} = 0 \end{cases} \end{aligned}$$

对于上图这个超平面，它并不是最优的，这是因为 $\vec \theta$ 是这个超平面的法向量，作出后如下图所示：

将 $p^{(i)}$ 画出后，可以发现所有的 $|p^{(i)}|$ 都比较小:

这意味着，如果要满足最优化问题的限制条件，$\|\vec \theta\|$ 需要尽可能地大，这与最优化问题中最优化的表达式相违背！由此可以看出，这不是一个好的超平面。

当选择这个超平面时，$|p^{(i)}|$ 会大得多，$\|\vec\theta\|$ 从而会相应的小很多，于是 SVM 会选择这个超平面，而不是上面那一个。

当 $\theta_0 \neq 0$ 时，超平面将不再经过 $(0, 0)$ 点，但 SVM 依然会做类似的工作，使得 margin 最大。

Kernels

我们令 $f_i$ 表示第 $i$ 个特征变量，则预测函数 $h_\theta(x)$ 成为

$$h_\theta(x) = \left[\theta_0 + \theta_1f_1 + \theta_2f_2 + \cdots \geq 0\right]$$

其中 $[x]$ 表示如果布尔表达式 $x$ 为真，则取值为 1，反之为 0。

有没有一种较好的方法来合理地选取各个特征变量？下面介绍一种构造方法。

下面例子中，我们只构造三个特征变量 $f_1$，$f_2$，$f_3$，特征为 $x_1$，$x_2$。

我们在 $x_1$，$x_2$ 形成的二维空间上选取三个点 $l^{(1)}$，$l^{(2)}$ 和 $l^{(3)}$，则每个特征变量由下式构造得到：

$$f_i = \kappa(x, l^{(i)}) = \exp\left(-\dfrac{\|x - l^{(i)}\|^2}{2\sigma^2}\right) = \exp\left(-\dfrac{\sum_{j=1}^n{(x_j - l^{(1)}_j)^2}}{2\sigma^2}\right)$$

其中，$\kappa(\cdot, \cdot)$ 被称为核函数，此处我们使用的是高斯核函数。此处的 $\sigma$ 与正态分布中的 $\sigma$ 对图像的影响类似，当 $\sigma$ 缩小时，图像会更加的陡峭，从最高点处向下时，下降的速度会更快；反之则会更平缓，下降的速度会更慢。我们称 $\sigma$ 影响着图像的平滑程度。

当 $x$ 和 $l^{(i)}$ 非常接近时，$f_i \approx 1$，而当二者之间的距离非常远时，$f_i \approx 0$。

假设我们已经得到参数的值：$\theta_0 = -0.5$，$\theta_1 = 1$，$\theta_2 = 1$，$\theta_3 = 0$，则靠近 $l^{(1)}$ 和 $l^{(2)}$ 的点将会被预测为 $y = 1$，其余位置将会被预测为 $y = 0$。根据参数，我们可以得到一个超平面，落入这个超平面中的所有数据点都会被预测为 $y = 1$。

具体实践中，我们可以将每个数据 $x^{(i)}$ 在超平面上的位置作为一个标记点 $l^{(i)}$，这样我们可以得到 $m$ 个标记，其中 $m$ 为训练集规模。

此时我们可以得到 $m$ 个特征变量 $f_1$，$f_2$，$\dots$，$f_m$。我们将其写作一个向量，同时按照惯例，我们在向量中加入 $f_0$，即

$$\vec f = \begin{bmatrix}f_0 = 1 \\ f_1 \\ f_2 \\ \vdots \\ f_m\end{bmatrix}$$

对于训练集中的一个数据 $\left\{x^{(i)}, y^{(i)}\right\}$，我们可以计算得到一个新的特征向量

$$\overrightarrow{f^{(i)}} = \begin{bmatrix} f_0^{(i)} = 1 \\ f_1^{(i)} = \kappa(x^{(i)}, l^{(1)}) \\ f_2^{(i)} = \kappa(x^{(i)}, l^{(2)}) \\ f_3^{(i)} = \kappa(x^{(i)}, l^{(3)}) \\ \vdots \\ f_m^{(i)} = \kappa(x^{(i)}, l^{(m)}) \end{bmatrix}$$

这样，我们可以把一个 $n + 1$ 维的数据 $x^{(i)}$ 转化为一个 $m + 1$ 的特征向量 $\overrightarrow{f^{(i)}}$。此时，预测函数将会变为

$$h_\theta(x) = \left[\theta^\mathrm T \overrightarrow{f^{(i)}} \geq 0\right]$$

其中，$\theta \in \mathbb{R}^{m + 1}$，$\overrightarrow{f^{(i)}} \in \mathbb R^{m + 1}$。

最优化问题为：

$$\underset{\theta}{\arg\min}\ C\sum\limits_{i = 1}^m{\operatorname{cost}_1(\theta^\mathrm T \overrightarrow{f^{(i)}}) + (1 - y^{(i)})\operatorname{cost}_0(\theta^\mathrm T \overrightarrow{f^{(i)}})} + \dfrac 12\sum\limits_{j = 1}^m{\theta_j^2}$$

当把 $\theta_0$ 省略后，L2 正则项可以写作 $\displaystyle \dfrac 12 \theta^\mathrm T\theta$。

在上式中，$C$ 的作用与 $\dfrac 1\lambda$ 基本相当：

• 当 $C$ 较大时，偏差小，方差大，容易过拟合；
• 当 $C$ 较小时，偏差大，方差小，容易欠拟合。

常用的核函数有如下几种：

名称	表达式	参数
线性核	$\kappa(x, l) = x^\mathrm Tl$
多项式核	$\kappa(x, l) = \left(x^\mathrm Tl + r\right)^d$	$r$ 为偏移量，$d \geq 1$ 为多项式次数
高斯核	$\kappa(x, l) = \exp\left(-\dfrac{|x - l|^2}{2\sigma^2}\right)$	$\sigma > 0$ 为高斯核的带宽
拉普拉斯核	$\kappa(x, l) = \exp\left(-\dfrac{|x - l|}{\sigma}\right)$	$\sigma > 0$
Sigmoid 核	$\kappa(x, l) = \tanh\left(\beta x^\mathrm Tl + \theta\right)$	$\beta > 0$，$\theta < 0$