数据挖掘 3.5 支持向量机——边界和正则化

3.5 Margin and Regularization
3.5 边界和正则化

求一个点距离线性分类器的距离

考虑一个线性分类器，其分界面为：

$$f(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b=0\text{对于所有在边界上的}\mathbf{x}$$

向量 $\mathbf{w}$ 垂直于线性判别式

证明过程
假设在边界上有两个点 ${\mathbf{x}}^{(1)}$ 和 ${\mathbf{x}}^{(2)}$：

$$f({\mathbf{x}}^{(1)})={\mathbf{w}}^T{\mathbf{x}}^{(1)}+b=0\text{\hspace{1em}(1)}$$

$$f({\mathbf{x}}^{(2)})={\mathbf{w}}^T{\mathbf{x}}^{(2)}+b=0\text{\hspace{1em}(2)}$$

用式 (2) 减去式 (1)：

$${\mathbf{w}}^T\left({\mathbf{x}}^{(2)}-{\mathbf{x}}^{(1)}\right)=0$$由此可得： $\mathbf{w}\perp \left({\mathbf{x}}^{(2)}-{\mathbf{x}}^{(1)}\right)$

即权重向量 W 与边界上的任意两个点的连线方向垂直。

求距离margin

设 ${\mathbf{x}}^{(s)}$ 是特征空间中的一个点，它在边界上的投影为 ${\mathbf{x}}^{(p)}$：

$$f({\mathbf{x}}^{(p)})={\mathbf{w}}^T{\mathbf{x}}^{(p)}+b=0\text{\hspace{1em}(3)}$$

根据向量计算， $${\mathbf{x}}^{(s)}={\mathbf{x}}^{(p)}+r\hat{\mathbf{w}}\text{\hspace{1em}(4)}$$

$\hat{\mathbf{w}}$是 $\mathbf{w}$的方向向量，长度为1，

$$\hat{\mathbf{w}}=\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\text{\hspace{1em}(5)}$$

求训练数据点 ${\mathbf{x}}^{(s)}$的标签值， $f({\mathbf{x}}^{(s)})={\mathbf{w}}^T{\mathbf{x}}^{(s)}+b$， 将（4）代入，
$$\begin{gathered} f({\mathbf{x}}^{(s)})={\mathbf{w}}^T\left({\mathbf{x}}^{(p)}+r\hat{\mathbf{w}}\right)+b \\ f({\mathbf{x}}^{(s)})={\mathbf{w}}^T{\mathbf{x}}^{(p)}+r{\mathbf{w}}^T\hat{\mathbf{w}}+b \end{gathered}$$将（5）代入，
$$f({\mathbf{x}}^{(s)})={\mathbf{w}}^T{\mathbf{x}}^{(p)}+b+r{\mathbf{w}}^T\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }$$
代入（3），

$$\begin{gathered} f({\mathbf{x}}^{(s)})=0+r{\mathbf{w}}^T\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert } \\ f({\mathbf{x}}^{(s)})=0+r\frac{{\mathbf{w}}^T\mathbf{w}}{\Vert \mathbf{w}\Vert } \\ f({\mathbf{x}}^{(s)})=0+r\Vert \mathbf{w}\Vert \\ f({\mathbf{x}}^{(s)})=r\Vert \mathbf{w}\Vert \end{gathered}$$

由此，

$$r=\frac{f({\mathbf{x}}^{(s)})}{\Vert \mathbf{w}\Vert }$$

解释： $r$ 表示点 ${\mathbf{x}}^{(s)}$ 到边界的有符号距离，$\mathbf{w}$ 是法向量，$\hat{\mathbf{w}}$ 是单位法向量。

举一个实例

$r$ 的距离是如何计算出来的？

$$r=\frac{f({\mathbf{x}}^{(s)})}{\Vert \mathbf{w}\Vert }=\frac{4+2\ast 2+3}{\sqrt{1^2+2^2}}=\frac{11}{\sqrt{5}}\approx 4.92$$

支持向量机的另一个视角

Hinge Loss: $$l(f(x),y)=\max (0,1-yf(x))$$

基于链式损失函数限制：
$$y\cdot f(x)\ge 1$$

对于正类（$y=+1$）：
$$f(x)\ge 1$$

对于负类（$y=-1$）：
$$f(x)\le -1$$

恰好在间隔边界上的支持向量满足：
$$y\cdot f(x)=1$$

因此正类支持向量：
$$f(x^{(s)})=1$$

代入得到：
$$r=\frac{f({\mathbf{x}}^{(s)})}{\Vert \mathbf{w}\Vert }$$

$$r=\frac{1}{\Vert \mathbf{w}\Vert }$$

SVM（支持向量机）优化问题的两种等价形式

无约束优化问题 (Unconstrained Optimization Problem)

min ⁡ w      1 2 w ⊤ w    +    C N ∑ i = 1 N max ⁡  ⁣ { 0 ,    1 − y i   f ( x i ; w ) } \min_{w}\;\; \frac{1}{2} w^{\top} w \;+\; \frac{C}{N}\sum_{i=1}^{N} \max\!\{0,\; 1 - y_i\, f(x_i; w)\} wmin​21​w⊤w+NC​i=1∑N​max{0,1−yi​f(xi​;w)}

有约束优化问题 (Constrained Optimization Problem)

$$\begin{array}{rl}\underset{w,\xi }{\min }& \frac{1}{2}{w}^{\top }w+\frac{C}{N}\sum _{i=1}^N{\xi }_i\\ \text{s.t.}& y_{i}f(x_i;w)\ge 1-{\xi }_i,i=1,\dots ,N,\\ & {\xi }_i\ge 0.\end{array}$$

对应关系

ξ i    =    max ⁡ { 0 ,    1 − y i   f ( x i ; w ) } \xi_i \;=\; \max\{0,\; 1 - y_i\, f(x_i; w)\} ξi​=max{0,1−yi​f(xi​;w)}

Note： 边距最大化 = 正则化