线性可分性 · aiwiki.page

线性可分性是欧几里得空间中两个点集的一种性质：存在一个超平面，能使一个点集中的所有点位于其一侧，而另一个点集中的所有点位于另一侧。在二维空间中，分隔边界是一条直线；在三维空间中，则是一个平面。这一概念将几何学与机器学习联系起来，尤其与监督学习中的二分类问题有关。它描述的是某种决策边界是否存在，而不是如何学习得到这一边界。(web.stanford.edu)

数学定义

设一组有限的训练数据由样本对 $(x_i,y_i)$ 表示，其中 $x_i\in\mathbb{R}^{d}$ ， $y_i\in\{-1,+1\}$ ，且两种标签均有出现。如果存在非零向量 $w\in\mathbb{R}^{d}$ 和标量 $b\in\mathbb{R}$ ，使得

y_i(w^\top x_i+b)>0 \qquad\text{对所有 }i\text{ 均成立},

则称这些数据严格线性可分。

表达式 $w^\top x$ 是标准内积。超平面 $w^\top x+b=0$ 将空间划分为两个开半空间，表达式的正负号决定预测类别。(web.stanford.edu)

虽然习惯上称之为“线性”，但当 $b\neq0$ 时，评分函数 $w^\top x+b$ 实际上是一个仿射映射。截距使边界可以不经过原点。如果 $b=0$ ，分隔边界就是齐次的，必须经过原点。将 $x$ 替换为 $(x,1)$ ，将 $w$ 替换为 $(w,b)$ ，就可以在增加一个维度的空间中，把仿射评分表示为内积。(web.stanford.edu)

严格分隔不允许观测点落在边界上。弱分隔则允许使用非严格不等式，但仍要求法向量非零；它可能使两类中的某些点都落在超平面上，因此不一定能得到类别判定明确的分类器。对于有限的严格可分数据，最小带符号评分为正，因此通过对 $w$ 和 $b$ 进行缩放，可以得到等价约束

y_i(w^\top x_i+b)\geq1.

检验这些约束是否可满足，是一个线性规划可行性问题。(stanford.edu)

凸几何与反例

对于两个非空有限点集，严格线性可分等价于它们的凸包不相交。凸包是包含一个集合的最小凸集，也等价于该集合中各点的所有凸组合构成的集合。如果一个仿射评分在每个点上都为正，那么它在这些点的任意凸组合上也为正；因此，凸包相交就不可能实现严格分隔。反过来，不相交的有限点集的凸包是紧凸集，因而存在严格分隔它们的超平面。有限性在这里至关重要：对于任意无限集合，分隔结果需要更仔细地区分严格分隔与一致的正间隙。(stanford.edu)

一个经典反例是异或（XOR）。将 $(0,1)$ 和 $(1,0)$ 标记为正类，将 $(0,0)$ 和 $(1,1)$ 标记为负类。每一类的凸包都是单位正方形的一条对角线段。这两条线段在 $(1/2,1/2)$ 处相交，因此不存在能严格分隔两类的直线。这体现的是模型表示能力的局限，而不是优化过程的失败。(cs.toronto.edu)

间隔与学习算法

仅有可分性并不能确定唯一的边界。一个分隔超平面在有限数据集上的几何间隔为

\gamma=\min_i \frac{y_i(w^\top x_i+b)}{\|w\|_2},

其中 $\|w\|_2$ 是欧几里得范数。这一间隔衡量观测点到边界的最小垂直距离；将两个参数同时乘以一个正数，不会改变它的值。(cs.cornell.edu)

感知机会在遇到误分类样本后更新参数。其收敛定理保证：对于有限的严格可分数据集，反复输入这些样本，经过有限次更新后就能得到一个分隔超平面。在齐次形式下，如果 $\|x_i\|\leq R$ ，且一个法向量长度为 1 的分隔超平面能够达到至少为 $\gamma$ 的间隔，那么更新次数的上界为 $(R/\gamma)^2$ 。仿射情形可以用增广向量处理。这一保证并不意味着感知机会找到间隔最大的分隔超平面。(cs.cornell.edu)

相比之下，硬间隔支持向量机通过凸优化选择最大间隔边界：

\min_{w,b}\frac12\|w\|_2^2 \quad\text{满足约束}\quad y_i(w^\top x_i+b)\geq1.

决定边界的观测点称为支持向量。当数据不可分时，软间隔形式会引入非负松弛变量，允许违反间隔约束，甚至允许分类错误，同时对这些情况施加惩罚。(web.stanford.edu)

对表示方式的依赖

线性可分性取决于所选的特征。特征工程可以将不可分的输入转换为可分的表示。对于异或问题，映射

\phi(x_1,x_2)=(x_1,x_2,x_1x_2)

使这四个样本变得可分：评分 $x_1+x_2-2x_1x_2-\tfrac12$ 恰好只在两个正类样本上为正。它对于变换后的特征是仿射的，但对于原始坐标是非线性的。这一显式评分展示了特征映射的构造方式。(cs.toronto.edu)

核方法通过函数 $K(x,z)=\langle\phi(x),\phi(z)\rangle$ 实现相关构造，使算法无需显式构造每一个变换后的坐标，就能使用特征空间中的内积。核并不会自动保证可分性；结果取决于表示方式以及带标签的观测数据。(cs.cornell.edu)

统计学影响

可分性对未正则化的逻辑回归有一个特殊影响。在完全分隔的情况下，增大能够实现分隔的参数向量的大小，会使拟合概率趋近于观测标签。似然不断接近其上确界，却无法在有限参数处达到该值，因此不存在有限的最大似然估计。正则化可以限制这种参数增长。(stat.cmu.edu)

最后，训练样本可分，并不意味着其所属的总体也可分，也不意味着模型能够可靠地泛化到未见过的样本。训练误差为零只涉及已观测到的点；模型在独立测试集上的表现回答的是另一个问题。(courses.cs.cornell.edu)

参考来源

Margins and separating hyperplanes — STATS 202web.stanford.edu
Convex Optimization: Geometric Problemsweb.stanford.edu
The Perceptroncs.cornell.edu
Convex Optimization — Slidesstanford.edu
Convex Optimizationstanford.edu
CSC 311: Introduction to Machine Learningcs.toronto.edu
Support vector machines: The linearly separable casenlp.stanford.edu
Machine Learning for Intelligent Systems: Mistake Boundscs.cornell.edu
CS4787/5777 — Lecture 18cs.cornell.edu
Lecture 13: Kernelscs.cornell.edu
Linear Classifiers and Logistic Regressionstat.cmu.edu
The Implicit Bias of Gradient Descent on Separable Dataarxiv.org