SVM 思路

1. 逻辑回归

如果给定一些样本,每个样本被表示为 $n$ 维特征 $\mathbf{x}$,类别 $y$($0$ 或 $1$),现在要求使用一个线性分类器将他们分开,那么该分类器可以表示为: $$ \mathbf{w}\mathbf{x} + b = 0 $$

其中 $\mathbf{w}$ 也为 $n$ 维向量,$b$ 为一维标量。那么样本 $\mathbf{x}$ 属于 $y=1$ 的概率 $p$ 的计算如下: $$ \begin{aligned} z &= f(\mathbf{x}) =\mathbf{w}\mathbf{x} + b \\ p &= \sigma(z) = \frac{1}{1 + e^{-z}} \\ \end{aligned} $$

决策函数为: $$ \operatorname{sign}(\mathbf{w} \mathbf{x} + b) $$ 当 $z>0$ 时,该样本属于正类($y=1$),反之则属于负类。

2. 函数间隔、集合间隔

在超平面 $\mathbf{w}\mathbf{x}+b=0$ 已经确定的情况下,$|\mathbf{w}\mathbf{x}+b|$ 能够表示点 $\mathbf{x}$ 到超平面的距离远近,而通过观察 $\mathbf{w}\mathbf{x}+b$ 的符号与类标记 $y$ 的符号是否一致可判断分类是否正确,所以,我们可以用 $y \cdot (\mathbf{w}\mathbf{x}+b)$ 的正负性来判定或表示分类的正确性。于此,我们便可以引出 函数间隔(Functional Margin)来表示点到超平面的距离。对于某个样本 $\mathbf{x}_i$ 来说,其函数间隔 $\hat{\gamma}_i$ 计算如下: $$ \hat{\gamma}(\mathbf{x}_i) = y \cdot (\mathbf{w}\mathbf{x}_i+b) = y \cdot f(\mathbf{x}_i) $$

其中乘上 $y$ 是为了摒弃符号的影响。

超平面 $f(\mathbf{x})$ 关于所有样本点 $(\mathbf{x}, y)$ 的函数间隔则是所有样本点与该超平面的函数间隔的最小值,即 $$ \hat{\gamma} = \min(\hat{\gamma}(\mathbf{x}_i)) $$ 但其实这样有个问题,当所有数据 $\mathbf{w}$、$\mathbf{x}$ 都放大若干倍时,函数间隔 $\hat{\gamma}$ 也会被同样放大若干倍,但实际上超平面 $f(\mathbf{x})$ 并没有变。

因此我们可以定义 几何间隔(Geometrical Margin)来解决样本与参数的尺度影响间隔的问题。对于某个样本 $\mathbf{x}_i$ 来说,其几何间隔 $\gamma_i$ 计算如下: $$ \gamma_i(\mathbf{x}_i) = y \cdot \frac{f(\mathbf{x}_i)}{||\mathbf{w}||} = \frac{\hat{\gamma}(\mathbf{x}_i)}{||\mathbf{w}||} $$ 其中 $||\mathbf{w}||$ 表示参数 $\mathbf{w}$ 的二范数(相当于向量模长),从而解决了尺度的问题。

类似地,超平面 $f(\mathbf{x})$ 关于所有样本点 $(\mathbf{x}, y)$ 的几何间隔则是所有样本点与该超平面的几何间隔的最小值,即 $$ \gamma = \min(\gamma(\mathbf{x}_i)) $$

3. 最大化间隔分类器

对一个数据点进行分类,当超平面离数据点的 几何间隔 越大,分类的置信度(Confidence)也越大。因此,为了使得分类的置信度尽可能高,需要让所选择的超平面能够最大化这个几何间隔。构成最大化几何间隔的两个边界被称为 支撑向量(Support Vector)

我们的目标表示为: $$ \begin{aligned} &\max \gamma &, s.t., \gamma_i \ge \gamma \end{aligned} $$ 将几何间隔替换成函数间隔,我们得到: $$ \begin{aligned} &\max \frac{\hat{\gamma}}{||\mathbf{w}||} &, s.t., \frac{\hat{\gamma}_i}{||\mathbf{w}||} \ge \frac{\hat{\gamma}}{||\mathbf{w}||} \end{aligned} $$ 为了方便推导与优化,我们可以令最小函数间隔 $\hat{\gamma} = 1$,从而得到: $$ \begin{aligned} &\max \frac{1}{||\mathbf{w}||} &, s.t., \frac{\hat{\gamma}_i}{||\mathbf{w}||} \ge \frac{1}{||\mathbf{w}||} \end{aligned} $$ 即: $$ \begin{aligned} &\max \frac{1}{||\mathbf{w}||} &, s.t., y_i \cdot (\mathbf{w} \mathbf{x}_i + b) \ge 1 \end{aligned} $$

为了方便计算(去掉范数计算),该优化目标相当于: $$ \begin{aligned} &\min \frac{1}{2} ||\mathbf{w}||^2 &, s.t., y_i \cdot (\mathbf{w} \mathbf{x}_i + b) \ge 1 \end{aligned} $$

4. 拉格朗日乘子法

上节我们推出的优化目标其实是个带约束的优化问题,对于这种问题,我们可以通过给每一个约束条件都乘上一个 拉格朗日乘子(Lagrange Multiplier),将约束条件融合到目标函数里,从而只用一个函数表达式便能清楚的表达出我们的问题,该函数被称为 拉格朗日函数。通过求 拉格朗日函数的极值点,我们可以找到我们需要求得的解。

具体来说,我们定义拉格朗日函数:

$$ \mathcal{L}(\mathbf{w}, b, \alpha) = \frac{1}{2} ||\mathbf{w}||^2 - \sum_{i=1}^m \alpha_i (y_i \cdot (\mathbf{w} \mathbf{x}_i + b) - 1) $$

然后令: $$ \theta(\mathbf{w}) = \max_{\alpha_i \ge 0} \mathcal{L}(\mathbf{w}, b, \alpha) $$

容易验证,当某个约束条件不满足时(例如 $y_i \cdot (\mathbf{w}^\mathrm{T} \mathbf{x}_i + b) < 1$),那么显然有 $\theta(\mathbf{w})=\infty$(只要令 $\alpha_i=\infty$ 即可)。而当所有约束条件都满足时,则最优值为 $\theta(\mathbf{w})=\frac{1}{2} ||\mathbf{w}||^2$,亦即最初要最小化的量。

因此,在要求约束条件得到满足的情况下最小化 $\frac{1}{2} ||\mathbf{w}||^2$,实际上等价于直接最小化 $\theta(\mathbf{w})$(当然,这里也有约束条件,就是 $\alpha \ge 1$,$i=1,2,3,\cdots, m$),因为如果约束条件没有得到满足,$\theta(\mathbf{w})$会等于无穷大,自然不会是我们所要求的最小值。

此时优化目标转化为: $$ \min_{\mathbf{w}, b} \theta(\mathbf{w}) = \min_{\mathbf{w}, b} \max_{\alpha_i \ge 0} \mathcal{L}(\mathbf{w}, b, \alpha) $$

注意,截至目前,我们需要优化的变量不仅包括 $\mathbf{w}$ 的 $n$ 个变量,还包括了 $l$ 个拉格朗日乘子 $\alpha$,一共需要优化 $(n + l)$ 个变量。

5. 对偶问题、KKT 条件

我们可以将上面的原始问题转化为它的 对偶问题(Dual Problem),通过求解对偶问题可以得到原始问题的最优解(在满足某些条件下其解相同)。转化成对偶问题的好处是:

  1. 对偶问题往往 更容易求解
  2. 可以自然地 引入核函数,进而推广到非线性分类问题。

对于上面的优化目标,我们假设其最优值为 $p^*$,即 $$ \min_{\mathbf{w}, b} \theta(\mathbf{w}) = \min_{\mathbf{w}, b} \max_{\alpha_i \ge 0} \mathcal{L}(\mathbf{w}, b, \alpha) = p^* $$ 对于该问题,我们很难直接求解,因此我们尝试解决其对偶问题: $$ \max_{\alpha_i \ge 0} \min_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \alpha) = d^* $$ 这里这两个问题其实是 弱对偶关系,即 $\min \max \mathcal{L} \le \max \min \mathcal{L}$,最大值里面的最小值比最小值的最大值要大。而为了能够使对偶问题的最优解 $d^*$ 等同原问题的最优解 $p^*$,这两个问题必须满足 强对偶关系,即 $\min \max \mathcal{L} = \max \min \mathcal{L}$。

而强对偶关系的充要条件是 KKT 条件(Karush–Kuhn–Tucker Conditions),其具体内容如下:

满足 KKT 条件则 $p^* = d^*$。

上面的式子满足。

6. 求解对偶问题

  1. 求 $\min$
  2. 求 $\max$
  3. 用 SMO 算法求解

7. SMO 算法

8. 核函数

  1. 如果数据在线性空间不可分,我们尝试将其映射到高维空间中。
  2. 如果真的映射之后再计算,首先维度巨高,空间代价高,其次计算内积的计算量很大,时间代价很高。
  3. 因此引入 核函数(Kernel Function)来 在低维空间中计算两个向量在高维空间中的映射的内积

举个例子对于一个从低维到高维的映射:

$$ \phi((x, y)) = (x^2, \sqrt 2 xy, y^2) $$

两个向量 $\vec{A}$、$\vec{B}$ 坐标分别为 $(1, 2)^\mathrm{T}$、$(3, 4)^\mathrm{T}$,那么他们在高维空间中的内积为: $$ \begin{aligned} \phi(\vec{A}) \cdot \phi(\vec{B}) &= (1, 2\sqrt2, 4)^\mathrm{T} \cdot (9, 12\sqrt2, 16)^\mathrm{T} \\ &= 9 + 48 + 64 \\ &= 121 \end{aligned} $$ 事实上,该映射对应的核函数为:

$$ k(\vec{A}, \vec{B}) = (\vec{A}^\mathrm{T} \cdot \vec{B}^\mathrm{T})^2 $$

我们可以利用该核函数来在低维空间中计算高维空间中的内积: $$ \begin{aligned} k(\vec{A}, \vec{B}) &= ((1, 2)^\mathrm{T} \cdot (3,4)^\mathrm{T})^2 \\ &= (3 + 8)^2 \\ &= 121 \end{aligned} $$

那么核函数怎么选?靠经验……

9. 松弛变量

  • 数据可能有异常点,无法完全线性可分,否则太过复杂甚至严重过拟合
  • 因此 SVM 允许数据点在一定程度上偏离一下超平面,这里「允许的偏移程度」就是 松弛变量(Slack Variable),具体表现在原优化目标的不等式约束上。

旧文参考

  1. linear classifier

$$ f(x)=\langle W,x\rangle+b $$

  1. lagrangian multiplier

$$ \begin{align} W&=\sum_{i=1}^ma_iy_ix_i \\ f(x)&=\sum_{i=1}^ma_iy_i\langle x_i,x\rangle+b \end{align} $$

  1. nolinear / high-dimensional space

$$ \begin{align} x'&=\operatorname{highDim}(x) \\ x_i'&=\operatorname{highDim}(x_i) \\ f(x)&=\sum_{i=1}^ma_iy_i\langle x_i',x'\rangle+b \end{align} $$

  1. kernel

$$ \begin{align} K(a,b)&=\langle \operatorname{highDim}(a),\operatorname{highDim}(b)\rangle\\ f(x)&=\sum_{i=1}^ma_iy_i\langle x_i',x'\rangle+b \\ &=\sum_{i=1}^ma_iy_iK(x_i,x)+b \end{align} $$

常见核函数

常见问题

  • SVM 可以做回归吗?
  • 为什么说 SVM 适合用在小样本数据上?
  • 为什么里面设定了 SVM 函数间隔为 1?
  • SVM 会过拟合吗?受异常点的影响怎样?
  • SVM 可以用在数据维度很大的推荐系统吗?
  • 为什么可以用拉格朗日乘子?
  • 为什么可以转化为对偶问题?

补充:libSVM

参考