5.1 线性分类

考虑一个输入空间 $\mathcal{X}$，它是 ${\mathbb{R}}^N$ 的子集，具有 $N\ge 1$，输出或目标空间 $\mathcal{Y}=\{-1,+1\}$，设 $f:\mathcal{X}\to \mathcal{Y}$ 为目标函数。 给定一个从 $\mathcal{X}$ 映射到 $\mathcal{Y}$ 的函数假设集 $\mathcal{H}$，二分类任务可以表述如下。 学习者接收到一个大小为 $m$ 的训练样本 $S$，该样本独立同分布地从 $\mathcal{X}$ 中根据某种未知的分布 $\mathcal{D}$, $S=\left(\left(x_1,y_1\right),\dots ,\left(x_m,y_m\right)\right)\in {\left(\mathcal{X}\times \mathcal{Y}\right)}^m$抽取，对于所有 $i\in \left[m\right]$ 有 $y_i=f\left(x_i\right).$ 问题在于确定一个假设 $h\in \mathcal{H}$，一个二分类器，具有较小的泛化误差:

$$R_{\mathcal{D}}\left(h\right)=\underset{x\sim \mathcal{D}}{\mathbb{P}}\left[h\left(x\right)\ne f\left(x\right)\right]\text{\hspace{1em}(5.1)}$$

对于这个任务，可以选择不同的假设集 $\mathcal{H}$。 鉴于第3章中呈现的结果，该结果形式化了 奥卡姆剃刀原则 (Occam’s Razor principle)，具有较小复杂度的假设集 在所有其他条件相同时提供更好的学习保证。

• 例如，较小的VC维数或Rademacher复杂度

一个具有相对较小复杂度的自然假设集是线性分类器或超平面的集合， 其定义如下:

$$\mathcal{H}=\left\{\mathbf{x}\mapsto \mathrm{sign}\left(\mathbf{w}\cdot \mathbf{x}+b\right):\mathbf{w}\in {\mathbb{R}}^N,b\in \mathbb{R}\right\}.\text{\hspace{1em}(5.2)}$$

然后，该学习问题被称为 线性分类问题。 在 ${\mathbb{R}}^N$ 中超平面的通用方程是 $\mathbf{w}\cdot \mathbf{x}+b=0$ 其中

• $\mathbf{w}\in {\mathbb{R}}^N$ 是一个非零向量，
• 垂直于超平面并且 $b\in \mathbb{R}$ 一个标量。

形如 $\mathbf{x}\mapsto \mathrm{sign}\left(\mathbf{w}\cdot \mathbf{x}+b\right)$ 的假设因此

• 将所有落在超平面一侧的点标记为正，
• 将所有其他点标记为负 $\mathbf{w}\cdot \mathbf{x}+b=0$。