Support Vector Machine

1. Problem Setup

SVM 主要用于处理分类任务.

具体地, 我们有如下训练集 $(x_1,y_1),\dots ,(x_n,y_n)$, 希望能够构造一个函数 $f(\cdot )$, such that

$$f(x_i)=y_i,i=1,2,\dots ,n,x_i\in {\mathbb{R}}^n,y_i\in \{-1,1\}.$$

进一步, 为了模型的简便性, 我们希望构造的函数是线性的, 或至少是仿射的 (affine):

$$f(x)=w^{T}x+b.$$

可以认为上述 $f(x)$ 构造了一个超平面 (hyperplane). 由解析几何知识可知, $w$ 是超平面的法向量, $b$ 是超平面的截距.

2. Naive Optimization Objective

首先定义点 $x$ 到平面的距离 $d(x,f)$:

$$d(x,f)=\frac{1}{\Vert w\Vert }|w^{T}x+b|.$$

Proof of point-to-hyperplane distance

已知 $w$ 是平面上的法向量, $x$ 是平面外的一点, $x_0$ 是 $x$ 向平面做垂线的垂足, 则有

$$x-x_0\perp f\Rightarrow x-x_0//w.$$

故

$$|w^T(x-x_0)|=|w^{T}x-w^T{x}_0|=|w^{T}x+b|=\Vert w\Vert \cdot \underset{d(x,f)}{\underbrace{\Vert x-x_0\Vert }}.$$

命题由上式最后一个等号变形即证.

$\square$

再定义点集 $A$ 到超平面的距离 $d(A,f)$:

$$d(A,f)=\underset{x\in A}{\min }d(x,f).$$

将这个距离称为 margin.

在给出上述定义后, 给出理想超平面的分类准则, 即希望得到的超平面对任意类别的集合的距离最大:

$$\begin{array}{r}\underset{w,b}{\max }\left(\frac{w^T{x}^{(A)}+b}{\Vert w\Vert }+\frac{w^T{x}^{(B)}+b}{\Vert w\Vert }\right).(1)\end{array}$$

由对称性, 有 $|w^T{x}^{(A)}+b|=|w^T{x}^{(B)}+b|:=a$, 故上式可化为:

$$\begin{array}{r}\underset{w,b}{\max }\left(\frac{2a}{\Vert w\Vert }\right).(2)\end{array}$$

观察上式, 会发现 $a$ 对于超平面的优化没有影响. 换言之, 我们可以通过坐标变换, 在不改变超平面的法向量 $w$ 和截距 $b$ 的情况下, 改变 $a$ 的值.

因此, 可以不妨令 $a$ 归一化为 $1$. 此时上式变为:

$$\begin{array}{r}\underset{w,b}{\max }\left(\frac{2}{\Vert w\Vert }\right)\iff \underset{w,b}{\min }\Vert w\Vert .(3)\end{array}$$

但是我们还需要在优化问题中指示分类的正误与否. 具体而言, 对于 margin 上的两个点 $x^{(1)}$ 和 $x^{(-1)}$, 希望它们被正确分类:

$$\begin{array}{r}\{\begin{array}{l}{w}^T{x}^{(1)}+b=1,\\ w^T{x}^{(-1)}+b=-1.\end{array}\end{array}$$

考虑到 margin 上的点已经是该类别点中的最小值, 则其余点的距离都将大于 $1$. 由此整合, 得到正确分类时的条件:

$$\begin{array}{r}(w^T{x}_i+b)y_i\ge 1.(4)\end{array}$$

结合 (3)(4) 两式, 最终得到正式的朴素分类优化目标:

$$\begin{array}{rl}\underset{w,b}{\min }& \Vert w\Vert \\ \text{s.t.}& y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,\dots ,n.\end{array}$$

3. Mathematical Derivation

为了方便, 继续对上述优化目标进行变形. 首先该优化目标等价于:

$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2\\ \text{s.t.}& y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,\dots ,n.\end{array}$$

为解决这一优化问题, 引入 Lagrange multiplier, 希望优化目标 Lagrange 函数为:

$$\begin{array}{r}{L}^{\ast }(w,b,\mathbf{\lambda })=\frac{1}{2}\Vert w{\Vert }^2+\sum _{i=1}^m{\lambda }_i\underset{\text{Penalty}}{\underbrace{\left[-y^{(i)}(w^T{x}^{(i)}+b)+1\right]}}.\ast \end{array}$$

其中, 记 $\mathbf{\lambda }=[{\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_m{]}^T$. 此外, 注意式中 penalty 项中的符号方向.

但是 $\ast$ 中的优化函数存在问题:

• 考虑数据集中远离超平面的数据点, 会发现这些点会使得 penalty 项很负, 从而极大地影响优化结果.
• 然而, 事实上超平面的位置并不应该被这些远离 margin 的点影响.
• Ideally, 我们只需要优化函数指示分类是否大于 $1$. 对于大于 $1$ 的 case, 即不在 margin 上的点, 我们并不关心它们的具体位置.

因此得到修改后的最终 Lagrange 优化函数:

$$\begin{array}{rl}L(w,b,\mathbf{\lambda })& =\frac{1}{2}\Vert w{\Vert }^2+\sum _{i=1}^n{\lambda }_i\cdot \underset{\text{Nonlinear}}{\underbrace{\mathcal{H}inge\left[1-y^{(i)}(w^T{x}^{(i)}+b)\right]}}.\end{array}$$

其中引入截断函数:

$$\mathcal{H}inge(z)=\max (0,z).$$

# Hinge Function Plot
import numpy as np
import matplotlib.pyplot as plt
 
x = np.linspace(-2, 2, 100)
y = np.maximum(0, x)
plt.plot(x, y)
plt.xlabel("x")
plt.ylabel("y")
plt.title("Hinge Function")
plt.show()

4. Convex Optimization Transformations

4.1 Squeezing / Relaxing

继续整理上述优化内容, 得到:

$$\begin{array}{rl}{†}^1:\underset{w,b,z}{\min }& \frac{1}{2}\Vert w{\Vert }^2+\sum _{i=1}^n{z}_i\\ \text{s.t.}& z_i\ge 1-y^{(i)}(w^T{x}^{(i)}+b),i=1,\dots ,n,\\ & z_i\ge 0,i=1,\dots ,n.\end{array}$$

Intuition (Squeezing).

• 上述优化内容中, $\frac{1}{2}\Vert w{\Vert }^2$ 表示需要优化的 margin, 后面 $\sum z_i$ 是 penalty.
• 由于 $\sum z_i$ 的加入, 优化中希望这一项尽可能小, 但至少要大于等于 $0$.
• 可以近似将 $z_i$ 看作是 $1-y_i(w^T{x}_i+b)$ 的 inf.
• 因此在不断缩小 $z_i$ 的同时, 就在不断缩小 $1-y_i{w}^T{x}_i$, 也就是在不断增大 margin.

Intuition (Relaxing).

首先有下列事实:

$$\begin{array}{rl}& z_i\ge 1-y_i\cdot (w^T{x}_i+b)\ge 0\\ \iff & y_i\cdot (w^T{x}_i+b)\ge 1-z_i.\end{array}$$

这一事实可以理解为:

• 可以放宽原先的 $y_i(w^T{x}_i+b)\ge 1$ 约束, 允许一些误分类的点存在; 即将原约束放宽为 $y_i(w^T{x}_i+b)\ge 1-z_i$, 其中 $z_i\ge 0$.
• 接着希望误分类的情况尽可能少出现, 即最小化 ${\sum }_{i=1}^m{z}_i$.

Note: Squeezing and relaxing

Squeezing 和 relaxing 都是在优化中常见的处理非线性等复杂情况的手段.

4.2 Lagrange Duality

一般地, 有下列约束问题:

$$\begin{array}{rl}\underset{x}{\min }& f_0(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,n,\\ & h_i(x)=0,i=1,\dots ,m.\end{array}$$

得到对应的 Lagrange 函数:

$$\begin{array}{rl}L(x,\lambda ,\mu )& =f_0(x)+\sum _{i=1}^n{\lambda }_i{g}_i(x)+\sum _{i=1}^m{\mu }_i{h}_i(x).\end{array}$$

为了解决上述优化问题, 可以将 Lagrange 函数处理成 inner 和 outer 两个优化问题.

Inner Optimization Problem.

$$x_{\lambda ,\mu }^{\ast }=\arg \underset{x\in D}{\min }L(x,\lambda ,\mu ).$$

Outer Optimization Problem.

代入上面已经得到的最优化 $x^{\ast }$, 进行优化有:

$${\lambda }^{\ast },{\mu }^{\ast }=\arg \underset{\lambda ,\mu }{\max }L(x_{\lambda ,\mu }^{\ast },\lambda ,\mu ).$$

这是一个 minimax 的策略.

Explanation of the minimax strategy

首先当 $x\in D$ 即处于可行域中时, 一定恒有

$$f_0(x)\ge f_0(x)+\underset{g_i\le 0}{\underbrace{\sum {\lambda }_i{g}_i}}+\underset{h_i=0}{\underbrace{\sum {\mu }_i{h}_i}}.\text{(1)}$$

而 RHS 就是 Lagrange Function, 即 $f_0(x)\ge L$, 由此得到了 $L$ 的一个 sup.

由此推出, 定有:

$$f_0(x)\ge \underset{x\in D}{\min }L(x,\lambda ,\mu ),\forall x\in D.\text{(2)}$$

进一步, 亦有:

$$\underset{x\in D}{\min }{f}_0(x)\ge \underset{x\in D}{\min }L(x,\lambda ,\mu ).\text{(3)}$$

当控制住 $x$ 的取值时, 再改变 $\lambda ,\mu$ 将不会再改变 (3) 中的符号方向, 故有

$$\underset{x\in D}{\min }{f}_0(x)\ge \underset{\lambda ,\mu }{\max }\underset{x\in D}{\min }L(x,\lambda ,\mu ).\text{(4)}$$

上式中对 $\lambda ,\mu$ 取 $\max$ 的原因是, $f_0(x)$ 是我们的优化目标, 在满足约束条件的前提下, 希望最终优化的结果可以尽可能接近 $f_0(x)$.

说明:

• 在满足一定条件下, (4) 中的不等号将严格取等, 即对于 Lagrange Function 的 minimax 策略最终完全逼近其 sup.
• 我们称该条件为 Slater’s Condition.
• 对于能够严格取等的情况, 称为 strong duality; 反之则为 weak duality.

进一步处理, 首先恒有如下不等式:

$$f_0(x)\ge \underset{x\in D}{\min }L(x,\lambda ,\mu )\ge \underset{x}{\min }L(x,\lambda ,\mu ).$$

代入到上述 (3)(4) 中, 就可以将约束优化转化为无约束优化:

$$\underset{x\in D}{\min }{f}_0(x)\ge \underset{x}{\min }L(x,\lambda ,\mu ).\text{(3*)}$$ $$\underset{x\in D}{\min }{f}_0(x)\ge \underset{\lambda ,\mu }{\max }\underset{x}{\min }L(x,\lambda ,\mu ).\text{(4*)}$$

可以证明, 对于满足 Slater’s Condition 的情况, 等号依然可以严格取到.

4.3 Example of Lagrange Duality

Example (Minimum distance hyperplane). 考虑如下优化问题: 寻找一个经过 $x$ 的平面使得到原点的距离最小, 即

$$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }^2\\ \text{s.t.}& w^{T}x+b=0.\end{array}$$

Solution

构造 Lagrange Function:

$$L(w,b,\lambda )=\frac{1}{2}\Vert w{\Vert }^2+\lambda (w^{T}x+b).$$

再构造对偶问题.

Inner optimization:

$${\nabla }_{w}L(w,b,\lambda )=w+\lambda x=0\Rightarrow w^{\ast }=-\lambda x.$$

Outer optimization:

$$L_{{\omega }^{\ast }}(\lambda )=-\frac{1}{2}(x^{T}x){\lambda }^2+\lambda b\Rightarrow {\lambda }^{\ast }=\arg \underset{\lambda }{\min }{L}_{{\omega }^{\ast }}(\lambda ).$$

上例很好地体现了 Lagrange dual problem 的优势: 其有效地将原问题转化为 inner 和 outer 两个相对更好解决的问题:

• Inner problem 由前面的证明已知, 是一个无约束问题.
• Outer problem 在代入 inner problem 之后得到一个更为简单的优化问题.

4.4 Lagrange Duality for SVM

回忆原 SVM 优化问题为:

$$\begin{array}{rl}[{†}^1]:\underset{w,b,z}{\min }& \frac{1}{2}\Vert w{\Vert }^2+\sum _{i=1}^n{z}_i\\ \text{s.t.}& z_i\ge 1-y^{(i)}(w^T{x}^{(i)}+b),i=1,\dots ,n,\\ & z_i\ge 0,i=1,\dots ,n.\end{array}$$

写作 Lagrange multiplier form:

$$\begin{array}{rl}L(w,b,z,\lambda ,c)& =\frac{1}{2}\Vert w{\Vert }^2+\sum _{i=1}^n{z}_i+\sum _{i=1}^n{c}_i{z}_i+\sum _{i=1}^n{\lambda }_i(z_i-(1-y_i(w^T{x}_i+b)))\\ & =\frac{1}{2}{w}^{T}w+\sum _{i=1}^n(1+c_i+{\lambda }_i)z_i-\sum _{i=1}^n{\lambda }_i(1-y_i(w^T{x}_i+b)).\end{array}$$

进行 Lagrange duality.

Inner Problem.

$$\begin{array}{r}\{\begin{array}{l}{\nabla }_{w}L(w,b,z,\lambda ,c)=w+{\sum }_{i=1}^n{\lambda }_i{y}_i{x}_i=0,\\ {\nabla }_{b}L(w,b,z,\lambda ,c)={\sum }_{i=1}^n{\lambda }_i{y}_i=0,\\ {\nabla }_{z}L(w,b,z,\lambda ,c)=1+c_i+{\lambda }_i=0,i=1,\cdots ,n.\end{array}\end{array}$$

Outer Problem.

Bring the inner problem into the outer problem:

$$\begin{array}{rl}L(w,b,z,\lambda ,c)& =\frac{1}{2}{w}^{T}w+w^T\left(\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)+\sum _{i=1}^n{\lambda }_i\\ & =\frac{1}{2}{\left(-\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)}^T\left(-\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)\\ & +{\left(-\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)}^T\left(\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)+\sum _{i=1}^n{\lambda }_i\\ & =-\frac{1}{2}{\left(\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)}^T\left(\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\right)+\sum _{i=1}^n{\lambda }_i\\ & =-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n(y_i{y}_j{x}_i^T{x}_j){\lambda }_i{\lambda }_j+\sum _{i=1}^n{\lambda }_i,\end{array}$$

subject to

$$\sum _{i=1}^n{\lambda }_i{y}_i=0.$$

故得到最终的对偶优化问题:

$$\begin{array}{rl}\underset{\lambda }{\max }& -\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n(y_i{y}_j{x}_i^T{x}_j){\lambda }_i{\lambda }_j+\sum _{i=1}^n{\lambda }_i\\ \text{s.t.}& \sum _{i=1}^n{\lambda }_i{y}_i=0.\end{array}$$

这一对偶问题是一个非常典型的二次规划问题 (Quadratic Programming Problem), 具有成熟算法可以解决. 因此可以认为已经得到了最优解 ${\lambda }^{\ast }$, 进而得到最优的 $w^{\ast }$ 和 $b^{\ast }$.

Definition (Support Vector Machine). 上述约束优化问题称为支持向量机.

5. Notes on SVM

1. 最终得到的决策超平面为:

   $$f(x)=w^{T}x+b=\sum _{i=1}^n{\lambda }_i{y}_i{x}_i^{T}x+b.$$

2. 关于支持向量: 通过优化计算可以发现, 最终得到的 ${\lambda }^{\ast }$ 是稀疏的, 即只有少数 ${\lambda }_i$ 不为 $0$. 这些 ${\lambda }_i$ 对应的样本点 $x_i$ 就是支持向量, 它们是决策超平面的关键点. 事实上, 这些支持向量就是接近决策边界的点, 它们支持着决策边界.

Related Notes

• Kernel Methods
• Linear Models for Classification
• Convex Optimization CMU