线性分类器与几何间隔

两种间隔 ​

对标签 $y\in \{-1,+1\}$，

$$h_{w,b}(x)=\mathrm{sign}(⟨w,x⟩+b).$$

样本 $(x,y)$ 的函数间隔是 $y(⟨w,x⟩+b)$，几何间隔是

$$\gamma (x,y)=\frac{y(⟨w,x⟩+b)}{\Vert w{\Vert }_{\ast }},$$

欧氏情形分母为 $\Vert w{\Vert }_2$。把 $(w,b)$ 同乘正数会任意放大函数间隔，却不改变分类边界；除以范数后才得到点到超平面的有符号距离。

数据半径 $R=\underset{i}{max}\Vert x_i\Vert$ 与最小几何间隔 $\gamma =\underset{i}{min}\gamma (x_i,y_i)$ 共同控制 perceptron 和 margin 泛化界，且依赖所选范数。Bias 可通过增广坐标齐次化，但这会改变增广空间的范数与半径，不能静默省略。

不可分数据的最小间隔非正，需要 slack、代理损失或只统计多数点的 margin 分布。参数个数相同的两个分隔面可有迥异 margin；几何余量描述数据与规则的配合，不只是类的全局容量。

在 ${\mathbb{R}}^2$ 中取 $w=(1,1),b=-1$。正样本 $x=(1,1)$ 的函数间隔为 $1$，几何间隔为 $1/\sqrt{2}$；把参数改成 $(10w,10b)$ 后函数间隔变成 10，几何间隔仍为 $1/\sqrt{2}$。这直接检验了为什么不除以范数会得到可任意操纵的“信心”。

若已知 $\Vert x_i\Vert \le R$ 且存在单位向量以 margin $\gamma >0$ 分开数据，感知机分析给错误数至多 $(R/\gamma {)}^2$：每次错误使参数朝真方向至少前进 $\gamma$，参数范数平方却至多增加 $R^2$，再以 Cauchy–Schwarz 比较两种增长。该证明要求可分和正 margin；在含噪样本上原界没有有限结论。

范数决定 margin 的几何。若输入使用 ${\ell }_1$ 范数，则对偶参数范数是 ${\ell }_{\mathrm{\infty }}$；欧氏公式中的点到超平面距离不能不加修改地搬过去。特征重缩放同样会改变 $R$ 与 $\gamma$：把某坐标乘一千会改变几何难度，即使可分标签不变，因此预处理属于模型规范的一部分。

Margin 与 VC 维回答不同层次。所有仿射半空间的 VC 维只依赖维度，而半径—间隔界会随具体样本的 $R/\gamma$ 改变；后者可在高维但大间隔数据上更有信息。软间隔 SVM 允许违例并惩罚 slack，不能继续声称最小几何 margin 为正。

参考资料

• Rosenblatt, “The Perceptron,” 1958; Novikoff, 1962.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, Ch. 9.