[omscs-ml] Support Vector Machine：从几何直觉到 Kernel SVM

这篇笔记整理 SVM 的核心概念：

1. SVM 想找什么分类边界
2. $x$、$w$、$b$ 分别是什么
3. 为什么 $w$ 垂直于分类平面
4. 为什么 margin 是 $\frac{2}{\|w\|}$
5. hard-margin SVM 的优化目标
6. Lagrange multiplier 和 dual form
7. support vectors 和 $\alpha_i$
8. kernel trick 和 nonlinear SVM

---

1. SVM 的核心直觉

SVM，全称是 Support Vector Machine。

它做二分类时，不只是想找一条线把两类点分开，而是想找一条最稳的分界线。

所谓最稳，就是：

在所有能正确分开两类点的边界里面，选择离两类最近点都最远的那条边界。

这个“离最近点的距离”叫 margin。

所以 SVM 的核心目标是：

$$\text{maximize margin}$$

---

2. 分类边界怎么写？

SVM 的线性分类边界写成：

$$w^T x + b = 0$$

在二维空间里，这是一条线；在三维空间里，这是一个平面；在更高维空间里，这叫 hyperplane。

---

3. $x$ 是什么？

$x$ 是一个样本的特征向量。

比如一个样本有两个特征：

$$x = [x_1, x_2]$$

可以理解成二维平面上的一个点。

例如：

$$x = [2,3]$$

表示这个样本在二维空间里的坐标是 $(2,3)$。

在 SVM 图里面，每一个 $+$ 或 $-$ 点，都是一个样本 $x_i$。

---

4. $w$ 是什么？

$w$ 是权重向量，也是分类边界的法向量 normal vector。

如果：

$$x = [x_1, x_2]$$

那么：

$$w = [w_1, w_2]$$

于是：

$$w^T x = w_1x_1 + w_2x_2$$

例如：

$$w = [2,-1]$$ $$x = [3,4]$$

那么：

$$w^T x = 2\times3 + (-1)\times4 = 2$$

几何上，$w$ 决定了分类边界的方向。更准确地说，$w$ 是垂直于分类边界的方向。

---

5. $b$ 是什么？

$b$ 是 bias，也叫截距。

它控制分类边界整体往哪里平移。

例如：

$$w = [1,1]$$ $$b = -3$$

那么分类边界是：

$$w^Tx+b=0$$

也就是：

$$x_1+x_2-3=0$$

所以：

$$x_1+x_2=3$$

如果把 $b$ 改成 $-5$：

$$x_1+x_2-5=0$$

也就是：

$$x_1+x_2=5$$

线的方向没有变，但整体平移了。

---

6. SVM 怎么用这个公式分类？

对于一个样本 $x$，计算：

$$w^Tx+b$$

如果：

$$w^Tx+b>0$$

预测为正类。

如果：

$$w^Tx+b<0$$

预测为负类。

如果：

$$w^Tx+b=0$$

说明这个点刚好在分类边界上。

---

7. 为什么 $w$ 垂直于 plane？

分类边界是：

$$w^T x + b = 0$$

假设这个 plane 上有两个点：

$$x_a$$ $$x_b$$

因为它们都在 plane 上，所以：

$$w^T x_a + b = 0$$ $$w^T x_b + b = 0$$

两式相减：

$$w^T x_a + b - (w^T x_b + b)=0$$

得到：

$$w^T(x_a-x_b)=0$$

$x_a-x_b$ 是 plane 上的一个方向向量。

它和 $w$ 的 dot product 是 0，所以它和 $w$ 垂直。

因为 plane 上任意两个点都可以这样做，所以：

$w$ 垂直于 plane 上所有方向，因此 $w$ 是这个 plane 的法向量。

---

8. 法向量 normal vector 是什么？

法向量就是：

垂直于一条线、一个平面、或者一个超平面的向量。

在二维里，分类边界是一条线。垂直于这条线的向量就是法向量。

例如这条线：

$$x+y=3$$

可以写成：

$$[1,1]^T[x,y]-3=0$$

所以：

$$w=[1,1]$$

是这条线的法向量。

这条线上的一个方向是：

$$[1,-1]$$

dot product：

$$[1,1]\cdot[1,-1] = 1\times1 + 1\times(-1)=0$$

所以 $[1,1]$ 垂直于线的方向。

---

9. Margin 线是什么？

SVM 不只看中间的分类边界：

$$w^Tx+b=0$$

还看两条平行的 margin 线：

$$w^Tx+b=1$$ $$w^Tx+b=-1$$

正类最近的点通常落在：

$$w^Tx+b=1$$

负类最近的点通常落在：

$$w^Tx+b=-1$$

这些刚好贴在 margin 线上的点，就是 support vectors。

---

10. 为什么 margin 是 $\frac{2}{\|w\|}$？

假设正类 margin 上有一个点 $x_1$：

$$w^Tx_1+b=1$$

负类 margin 上有一个点 $x_2$：

$$w^Tx_2+b=-1$$

两式相减：

$$w^Tx_1+b-(w^Tx_2+b)=1-(-1)$$

得到：

$$w^T(x_1-x_2)=2$$

但是 $w^T(x_1-x_2)$ 不是直接的几何距离，它是沿着 $w$ 方向的 dot product。

要得到真实距离，需要除以 $w$ 的长度：

$$\|w\|$$

所以两条 margin 线之间的距离是：

$$\frac{w^T(x_1-x_2)}{\|w\|} = \frac{2}{\|w\|}$$

因此：

$$\text{margin} = \frac{2}{\|w\|}$$

---

11. $\|w\|$ 是什么？

$\|w\|$ 是 $w$ 这个向量的长度。

如果：

$$w=[w_1,w_2]$$

那么：

$$\|w\|=\sqrt{w_1^2+w_2^2}$$

如果：

$$w=[3,4]$$

那么：

$$\|w\|=\sqrt{3^2+4^2}=5$$

因此 margin 是：

$$\frac{2}{\|w\|}=\frac{2}{5}=0.4$$

---

12. SVM 的优化目标

因为：

$$\text{margin}=\frac{2}{\|w\|}$$

所以最大化 margin 等价于最小化 $\|w\|$。

实际优化时通常写成：

$$\min_{w,b} \frac{1}{2}\|w\|^2$$

这里的 $\frac{1}{2}$ 没有特别神秘的意义，主要是为了求导方便。

---

13. Hard-margin SVM 的 constraint

SVM 还要求所有点都被正确分类，并且至少在 margin 外面：

$$y_i(w^Tx_i+b)\ge 1$$

其中：

$$y_i \in \{+1,-1\}$$

如果 $y_i=+1$，那么 constraint 变成：

$$w^Tx_i+b\ge 1$$

如果 $y_i=-1$，那么：

$$-(w^Tx_i+b)\ge 1$$

等价于：

$$w^Tx_i+b\le -1$$

所以这一行公式同时表达：

1. 正类点要在 $+1$ 那边
2. 负类点要在 $-1$ 那边

---

14. Hard-margin SVM 的 primal problem

完整写法是：

$$\min_{w,b} \frac{1}{2}\|w\|^2$$

subject to：

$$y_i(w^Tx_i+b)\ge 1,\quad \forall i$$

这叫 hard-margin SVM。

它的意思是：

在保证所有训练点都正确分类的情况下，让 margin 最大。

因为目标函数是二次的，constraints 是线性的，所以这是一个 quadratic programming 问题。

---

15. Lagrange multiplier 是什么？

SVM 是一个 constrained optimization 问题：

$$\min_{w,b}\frac{1}{2}\|w\|^2$$

subject to：

$$y_i(w^Tx_i+b)\ge 1$$

为了处理这些 constraints，可以用 Lagrange multiplier。

先把 constraint 改写成：

$$y_i(w^Tx_i+b)-1\ge 0$$

然后给每个 constraint 配一个系数：

$$\alpha_i\ge 0$$

这个 $\alpha_i$ 就是 Lagrange multiplier。

---

16. SVM 的 Lagrangian

把目标函数和 constraints 合起来：

$$L(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i[y_i(w^Tx_i+b)-1]$$

展开：

$$L(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i y_i(w^Tx_i+b) + \sum_i\alpha_i$$

再把 $b$ 分开：

$$L(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i y_iw^Tx_i - b\sum_i\alpha_iy_i + \sum_i\alpha_i$$

---

17. 对 $w$ 求导

为了消掉 $w$，对 $w$ 求导并令其为 0：

$$\frac{\partial L}{\partial w} = w-\sum_i\alpha_iy_ix_i = 0$$

所以：

$$w=\sum_i\alpha_iy_ix_i$$

这说明最终的 $w$ 是由训练样本加权组合出来的。

---

18. 对 $b$ 求导

对 $b$ 求导：

$$\frac{\partial L}{\partial b} = -\sum_i\alpha_iy_i = 0$$

所以：

$$\sum_i\alpha_iy_i=0$$

这就是 dual problem 里的一个 constraint。

---

19. Dual objective 是怎么来的？

从 Lagrangian：

$$L = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i y_iw^Tx_i - b\sum_i\alpha_iy_i + \sum_i\alpha_i$$

因为：

$$\sum_i\alpha_iy_i=0$$

所以 $b$ 那一项消失。

又因为：

$$w=\sum_i\alpha_iy_ix_i$$

所以：

$$\sum_i\alpha_iy_iw^Tx_i = w^T\sum_i\alpha_iy_ix_i = w^Tw = \|w\|^2$$

因此：

$$L = \frac{1}{2}\|w\|^2-\|w\|^2+\sum_i\alpha_i$$

也就是：

$$L = \sum_i\alpha_i-\frac{1}{2}\|w\|^2$$

接下来展开 $\|w\|^2$。

因为：

$$w=\sum_i\alpha_iy_ix_i$$

所以：

$$\|w\|^2=w^Tw$$ $$= \left(\sum_i\alpha_iy_ix_i\right)^T \left(\sum_j\alpha_jy_jx_j\right)$$

展开：

$$\|w\|^2 = \sum_i\sum_j\alpha_i\alpha_jy_iy_jx_i^Tx_j$$

所以 dual objective 是：

$$W(\alpha) = \sum_i\alpha_i - \frac{1}{2} \sum_i\sum_j \alpha_i\alpha_jy_iy_jx_i^Tx_j$$

subject to：

$$\alpha_i\ge 0$$ $$\sum_i\alpha_iy_i=0$$

---

20. $\alpha_i$ 是什么？

每个训练点 $x_i$ 都有一个自己的 $\alpha_i$。

可以把 $\alpha_i$ 理解成：

第 $i$ 个训练样本对最终分类边界的重要程度。

如果：

$$\alpha_i=0$$

说明这个点对最终边界没有贡献。

如果：

$$\alpha_i>0$$

说明这个点会影响最终边界。

这些 $\alpha_i>0$ 的点就是：

$$\text{support vectors}$$

所以 SVM 的名字来自这里：真正 support 这个 boundary 的，是少数 support vectors。

---

21. 为什么大部分点不重要？

SVM 的分类边界主要由离边界最近的点决定。

离边界很远的点，即使移动一点，也不会改变最大 margin 的位置。

数学上，它们对应：

$$\alpha_i=0$$

而刚好卡在 margin 上的点，对应：

$$\alpha_i>0$$

所以：

$$w=\sum_i\alpha_iy_ix_i$$

实际上通常只由少数 support vectors 决定。

---

22. 新样本怎么分类？

训练完之后，对一个新样本 $x$，分类函数是：

$$f(x)=\text{sign}(w^Tx+b)$$

因为：

$$w=\sum_i\alpha_iy_ix_i$$

所以：

$$w^Tx = \left(\sum_i\alpha_iy_ix_i\right)^Tx = \sum_i\alpha_iy_ix_i^Tx$$

因此：

$$f(x) = \text{sign} \left( \sum_i\alpha_iy_ix_i^Tx+b \right)$$

由于大部分 $\alpha_i=0$，实际计算时主要用 support vectors。

---

23. SVM 只能是 linear 吗？

不是。

更准确地说：

SVM 本质上是在某个空间里找 linear hyperplane，但这个空间不一定是原始 $x$ 空间。

如果在原始空间里做：

$$w^Tx+b=0$$

这就是 linear SVM。

但如果先把 $x$ 映射到新空间：

$$x\rightarrow \phi(x)$$

然后在新空间里做：

$$w^T\phi(x)+b=0$$

那么在新空间里仍然是 linear boundary，但映射回原始空间后，边界可以是 nonlinear 的。

---

24. 一个 nonlinear 的简单例子

假设原始特征是：

$$x=[x_1,x_2]$$

linear SVM 只能学：

$$w_1x_1+w_2x_2+b=0$$

这是直线。

但如果加入一个新特征：

$$z=x_1^2+x_2^2$$

那么模型可以学：

$$z=c$$

也就是：

$$x_1^2+x_2^2=c$$

这在二维原始空间里是一个圆。

所以 nonlinear SVM 的直觉是：

在高维特征空间里线性可分，回到原始空间后就是弯曲边界。

---

25. Kernel trick 从哪里来？

Dual objective 里出现的是：

$$x_i^Tx_j$$

也就是两个训练样本之间的 dot product。

Kernel SVM 把它替换成：

$$K(x_i,x_j)$$

于是 dual objective 变成：

$$W(\alpha) = \sum_i\alpha_i - \frac{1}{2} \sum_i\sum_j \alpha_i\alpha_jy_iy_jK(x_i,x_j)$$

这里：

$$K(x_i,x_j)$$

可以理解成两个样本在某个高维空间里的相似度。

更准确地说，如果存在某个映射 $\phi$，使得：

$$K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$

那么我们就可以不显式计算 $\phi(x)$，而直接用 $K(x_i,x_j)$。

这就是 kernel trick。

---

26. Kernel 为什么有用？

Kernel trick 让 SVM 可以在高维甚至无限维空间里做 linear classification，却不需要真的把每个样本转换成高维向量。

原来：

$$x_i^Tx_j$$

现在换成：

$$K(x_i,x_j)$$

所以分类函数变成：

$$f(x) = \text{sign} \left( \sum_i\alpha_iy_iK(x_i,x)+b \right)$$

这就允许 SVM 在原始空间里形成 nonlinear boundary。

---

27. 常见 kernel

Linear kernel

$$K(x,y)=x^Ty$$

这就是普通 linear SVM。

---

Polynomial kernel

简单二次形式：

$$K(x,y)=(x^Ty)^2$$

更一般形式：

$$K(x,y)=(x^Ty+c)^p$$

其中：

• $p$ 是 polynomial degree

• $c$ 是常数

它可以捕捉多项式关系，比如：

$$x_1^2,\quad x_2^2,\quad x_1x_2$$

所以边界可以是抛物线、椭圆、二次曲线等。

---

RBF / Gaussian kernel

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

它的直觉是：

• $x$ 和 $y$ 越近，$K(x,y)$ 越接近 1

• $x$ 和 $y$ 越远，$K(x,y)$ 越接近 0

RBF kernel 是最常用的 nonlinear kernel 之一。

---

Sigmoid kernel

$$K(x,y)=\tanh(\alpha x^Ty+\theta)$$

这个形式和神经网络里的 activation 有点像。

不过 sigmoid kernel 不是在所有参数下都合法，所以实际使用时要小心。

---

28. Mercer condition 是什么？

不是随便写一个相似度函数都能当 kernel。

一个合法 kernel 需要满足 Mercer condition。粗略理解就是：

这个 $K$ 必须真的能对应某个高维空间里的 dot product。

也就是必须存在某个 $\phi(x)$，使得：

$$K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$

如果 kernel 不合法，SVM 的优化问题可能不再是稳定的 convex optimization。

---

29. Kernel 和 domain knowledge

因为 kernel 可以理解成“相似度函数”，所以有时可以根据领域知识设计 kernel。

例如：

• 文本分类里，可以设计字符串相似度相关的 kernel

• 分子结构里，可以设计 graph kernel 或 fingerprint similarity kernel

• 序列数据里，可以设计 sequence kernel

核心思想是：

只要这个相似度函数满足 kernel 条件，就可以放进 SVM 的 dual form 里。

---

30. 全文总结

SVM 的主线可以这样记：

1. 分类边界是

   $$w^Tx+b=0$$

2. $w$ 是分类边界的法向量，垂直于 boundary。

3. 两条 margin 线是

   $$w^Tx+b=1$$

   和

   $$w^Tx+b=-1$$

4. margin 是

   $$\frac{2}{\|w\|}$$

5. 最大化 margin 等价于最小化

   $$\frac{1}{2}\|w\|^2$$

6. hard-margin SVM 的 primal problem 是

   $$\min_{w,b}\frac{1}{2}\|w\|^2$$

   subject to

   $$y_i(w^Tx_i+b)\ge 1$$

7. 用 Lagrange multiplier 可以得到 dual objective：

   $$W(\alpha) = \sum_i\alpha_i - \frac{1}{2} \sum_i\sum_j \alpha_i\alpha_jy_iy_jx_i^Tx_j$$

8. 大多数 $\alpha_i=0$，只有 $\alpha_i>0$ 的点决定边界，这些点叫 support vectors。

9. dual form 里只出现 $x_i^Tx_j$，所以可以替换成 kernel：

   $$K(x_i,x_j)$$

10. Kernel SVM 本质上是在高维空间里做 linear SVM，但映射回原始空间后可以得到 nonlinear boundary。