所属栏目：数学论文范文发布时间：2026-04-22浏览量:449
摘要: 随着大模型所代表的AI技术革命浪潮的兴起，以数据为中心的AI研究快速崛起，使得包括线性可分性在内的数据分析技术愈发受到研究者的重视。线性可分判定作为数据分析的基础性数学问题，在大数据时代的应用背景下，高效的判定方法依然是个未被充分满足的需求。本文提出并论证了一种基于球面模型的点与集合线性可分的充分必要条件;并基于该充要条件，进一步提出并论证了两集合线性可分的并行化快速初筛检测方法。本文方法的优势在于：(1)内在并行化特点，具备低时间复杂度，执行效率要远优于现有方法。(2)并行化适用性，任何线性可分性判定方法均可以使用本文的并行化框架来实现加速。文中基于基准数据集和人工数据集的验证实验也充分展示了本文方法的准确性和实现的高效性。
关键词: 线性可分;计算几何;凸技术;数据分析;并行化
论文《一种并行化快速两集合线性可分检测方法》发表在《计算数学》，版权归《计算数学》所有。本文来自网络平台，仅供参考。
1. 引言
机器学习研究主要包括两个层面：一个层面是围绕数据端的研究，其核心是数据分布[1,2];另一个层面是围绕行为端的研究，核心是学习模型，涉及模型选择[3,4]、结构设计[5,6]、以及学习算法设计[7]等。训练数据是学习行为的基础，对学习行为的选择起到制约作用，进而影响学习效果。
线性可分性作为一个基本的数学概念，是对两类数据在空间分布上的一种定性描述，在机器学习领域，尤其是分类学习中扮演着基础性角色。这充分体现在机器学习模型的选择和模型结构设计方面。
在模型选择方面。对于一个线性不可分任务，若选择线性分类模型，如感知机[8]、线性SVM[9]，将找不到应有的问题解;相反，对于一个线性可分任务，若选择非线性分类模型，如非线性SVM[10]、MLP[11]、深度学习[12]等，虽然能得到问题解[13]，但其泛化性能存在因问题空间转化而被削弱的风险，如多数文本分类问题，由于其在高维空间中稀疏分布，就常见这种情况。
在模型设计方面，主要是非线性模型结构设计方面，迄今依然缺乏有效的指导理论和技术手段，更多地依赖于用户对样本知识的领域经验，通过反复的工程实验尝试去加以选择。这种困难充分体现在神经网络模型的层数及隐层神经元的个数设计上，以及SVM模型中核函数的参数的选择上。本质上，非线性模型的求解过程，也是通过空间映射，来实现线性不可分到线性可分的形式转换。具体而言，在非线性模型的学习训练中，当模型无法收敛的时候，用户难以分析是网络结构不够导致的、还是训练算法自身的技术缺陷导致的、亦或训练时间不够导致的。(1)如果能够知晓具体到哪一层数据变得可分，那便能够确定网络结构是足够的，则后续各隐层可以直接裁减，并仅针对裁撤后的输出层进行训练学习即可让模型收敛，达到模型重构、减少结构冗余的目的;(2)若各隐层输出依然是线性不可分，则可通过增加隐层，加大模型结构，使之于问题的复杂程度相匹配。从这个意义上讲，线性可分判定作为一种基本的数据分析手段，在机器学习过程中，是具有指导性意义的。
此外，作为一个基本数学问题，线性可分与凸包[14,15]为代表的凸技术[16]紧密相关。而凸包技术在诸如Delaunay三角形划分[17]、维诺图[18]、图像处理[19,20]、视觉跟踪[21,22]、计算机可视化[23,24]等领域存在着广泛的应用。目前制约凸包技术应用的主要瓶颈在于其高时间复杂度，难以满足现实应用在效率上的需求，尤其在高维数据空间上。因此，一个更加高效的线性可分判断方法，对进一步提升以凸包为代表的凸技术的效率，具有潜在的理论价值。
长期以来，线性可分判定问题吸引了众多研究者的深入关注，先后取得了许多富有成效的研究成果。从所采用的技术路线上，主要研究成果大致可分为以下几类：(1)基于统计的方法，其代表是Fisher线性判别法[25]。1936年Fisher通过最小化类内数据点的方差和最大化类间数据点的平均间隔，提出了一种线性可分判断方法。但该方法本质上是一种可分程度的近似度量，不能准确地给出可分或不可分判断;(2)基于线性规划的方法，其中最流行的是Fourier-Kuhn消去法[26,27]、Simplex(单纯形法)[28]和Interior Point Method(内点法)[29]。该类方法通过构建并求解一组线性不等式来判断线性可分性，若有解，则数据集为线性可分，否则，为线性不可分。在时间效率上，Interior Point Method的最坏复杂度是多项式级别的，而Fourier-Kuhn消去法和Simplex的最坏时间复杂度随着数据维度的增长而呈指数增长;(3)基于机器学习的方法，例如SVM[10]和感知机[8]。理论上，对于线性可分数据集，线性SVM和感知机算法通过有限次迭代后一定能收敛，但实际应用中很难去确定其所需的迭代次数;(4)子空间投影方法(Subspace projection method, SP)[30]。该方法将线性可分判定问题等价转换为判定矩阵(与两类点集相关)的域中是否存在严格正点的问题，并通过子空间投影方法来迭代验证是否存在这样一个严格正点，若存在，则线性可分，否则线性不可分。当n>d(其中n表示规模，d表示维度)时，SP的时间复杂度仅为O(nd^3)。然而，当n
现有方法的主要缺点如下：(1)时间复杂度高;(2)适用性差;(3)理论上不完整，仅为近似判断;或(4)只有理论结论，难以实现。
到目前为止，执行效率和判断准确性仍然是线性可分判断问题研究的主要矛盾和焦点。作为一个被深入研究的议题，本文继续对线性可分判断问题进行研究，其意义和目的在于追求一种不仅理论完备，而且实现高效的方法，以满足实现层面日益增长的效率需求。
对于线性可分判断议题，在技术路线的选择上，空间几何具备直观形象、逻辑性强的优点。为此，本文从计算几何的角度，提出并论证了一个基于球面模型的点与集合线性可分(或不可分)的充分必要条件;并以此进一步提出并论证了具备并行特点的两集合线性可分(或不可分)的快速初筛检测。
本文判定方法的显著特点在于：(1)执行层面，具备可高度并行化的特点;(2)实现层面，具备低时间复杂度。
本文余下内容组织如下：第2节，相关概念定义及符号表示。介绍线性可分问题的相关概念以及符号说明;第3节，点与集合的线性可分判定。首先，对点与集合的线性可分判定问题进行了几何建模，确立其球面模型，并论证了该模型的正确性和合理性;其次，提出并论证了点与集合线性可分(不可分)的充分必要条件;第4节，两集合线性可分的判定。本节提出并证明了集合与集合线性可分(不可分)的并行化初筛检测方法;第5节，算法设计及时间复杂度分析。本节给出了线性可分检测算法的形式化描述，并对其时间复杂度展开了分析;第6节，验证与分析。本节通过一些基于基准数据集和人工数据集的对比实验，来展现本文方法的正确性和高效性;最后是小结与展望。
2. 相关概念定义及符号表示
2.1. 相关概念定义
为便于理解，在下文中需要用到的一些概念，分别定义如下：
在几何空间中，两集合线性可分可直观地表述为：存在一个线性边界(直线/平面/超平面)，将空间一分为二，两集合数据点分属边界两侧。以下是其形式化定义：
定义1. (线性可分和线性不可分): 如果存在超平面mathscr{P}，满足egin{cases}vec{w}^T x + b > 0, & x in A \ vec{w}^T x + b leq 0, & x in Bend{cases}，则称集合A与B线性可分，记为A parallel B，mathscr{P}为集合A和B的线性解;否则，称集合A和B线性不可分，记为A parallel B。
显然，点与集合线性可分是集合与集合线性可分的一种特例。
计算几何中的基本概念“最小包围球”也将在下文线性可分充要条件的论证过程中用到，在此，先给出其数学定义。
定义2. (最小包围球): 使得集合M中的点都在球内或球面上且半径最小的球，称为集合M的最小包围球，记为B_M。
2.2. 符号表示
为阅读的方便，本节列出下文中将用到的符号及其说明：
表1 文中所用符号的类别描述
类别 符号
点集 A, B, C, M
点 p, x, y, t
标量 b, h, r, r_0, r_M, r_1, r_2, r_{SC}
几何体 S_0, B_0, B_M, S_C, ext{hemi}_S, ext{Cir}
表2 文中的一些关键符号以及他们的含义
符号 含义
A, B, C 点集
p 点
S_0 模型球面(以p为球心，r_0为半径的球面)
B_0 模型球(S_0的球体)
r_0 S_0(B_0)的半径
M 从点p作射线到集合C与模型球面S_0相交所得的集合
ext{MCB} 最小包围球
B_M 集合M的最小包围球
r_M B_M的半径
备注: 带*的符号是本文中的高频符号。
3. 点与集合的线性可分判定
3.1. 球面模型
直观上，点p与集合C的线性可分只与集合C中的点相对于点p的方向有关，与远近无关。点与集合线性可分的这种特性，本文称为“点与集合线性可分的方向不变性”。下面定理1是线性可分方向不变性定理的描述及证明。
定理1. 如果集合C中的点相对于点p的方向保持不变，那么即使距离发生改变(距离 eq 0)，点p与集合C之间的线性可分性仍然保持不变。
证明. [简便起见，我们将坐标轴进行平移，使得点p与坐标原点重合，显然，这不影响该命题中的线性可分性。]
(1) p parallel C情形(如图1)：
根据定义1，有
ecause p parallel C
herefore exists ext{超平面} mathscr{P}: vec{w}^T x = 0, egin{cases} vec{w}^T x > 0, & x in C \ vec{w}^T x = 0, & x = p end{cases}
herefore egin{cases} vec{w}^T x_i > 0, & x_i in C, 1 leq i leq C
\ vec{w}^T x = 0, & x = p end{cases}
herefore egin{cases} vec{w}^T (lambda_i x_i) > 0, & x_i in C, lambda_i > 0, 1 leq i leq C
\ vec{w}^T x = 0, & x = p end{cases}
令$C' = {lambda_1 x_1, ldots, lambda_i x_i, ldots}, x_i in C, lambda_i > 0, 1 leq i leq C
$，有
egin{cases} vec{w}^T x > 0, & x in C' \ vec{w}^T x = 0, & x = p end{cases}
herefore p parallel C'
(2) p parallel C情形(如图2)：
根据定义1，有
p parallel C
Rightarrow forall vec{w} exists x_i exists x_j left( (x_i in C) land (x_j in C) land (i eq j) land (vec{w}^T x_i > 0) land (vec{w}^T x_j leq 0) ight)
[注：对于任何过点p的平面/超平面，集合C中至少有两个不同的点，一个点在该平面/超平面上方，另一个点在该平面/超平面下方或在平面上。]
Leftrightarrow forall vec{w} forall lambda_i forall lambda_j exists x_i exists x_j left( (lambda_i > 0) land (lambda_j > 0) land (x_i in C) land (x_j in C) land (i eq j) land (vec{w}^T (lambda_i x_i) > 0) land (vec{w}^T (lambda_j x_j) leq 0) ight)
Rightarrow p parallel C' quad C' = {lambda_1 x_1, ldots, lambda_i x_i, ldots}, x_i in C, lambda_i > 0, 1 leq i leq C
定理1揭示的客观事实是：点与集合线性可分性仅仅取决于集合中的点相对于该点的方向分布，与距离无关。方向分布不变，则点与集合线性可分性不变。
然而，点与集合中各点的距离通常存在差异性，这种距离上的差异性，将严重阻碍点与集合线性可分问题的进一步探讨和解决。为此，下文进一步提出了球面模型，来消除这种距离上的差异性。
依据定理1，可按照如下步骤，进一步为“点p与集合C线性可分问题”建立相应的球面模型：
以点p为球心，r_0为半径，构建一个模型球(记为B_0，其相应的球面记为S_0)。在以球心p为端点，分别向集合C中的各点作射线，射线与球面S_0相交，所得交点为元素构成新的点集，记为M。如图3所示。
根据定理1，将新集合M取代原集合C，不改变其与点p之间的线性可分性。
这样，“点p与集合C线性可分问题”可简化为“球面模型下，球心p与球面点集M的线性可分问题”。
显然，集合M上的点相对于点p的方向分布，决定了其在模型球面上的空间分布。因此，球面模型的确立，使得线性可分问题的讨论焦点，由原来的“方向分布”转为“空间分布”(即，集合M在模型球面上的空间分布)。这为下文线性可分问题的进一步探讨及其充要条件的提出，提供了坚实的数学框架。
3.2. 点与集合可分(不可分)的充分必要条件
在3.1节，点与集合的线性可分问题在球面模型上得到了简约表达，使得线性可分问题研究焦点从难计算的“方向分布”转为可计算的“空间分布”。
直观上，如果球面点集M处在模型球面S_0的某个半球面上，则球面点集M与球心p线性可分。反之亦然。
问题是：该如何有效感知点集M是否分布在半球面上呢?
为了计算点集M在模型球面上的“空间分布”，最小包围球的概念被引入，下文统一将点集M的最小包围球记为B_M(o_M为球心，r_M为半径)。最小包围球能很好刻画点集的空间分布状态，其在理论上具备客观唯一性，在实现上具备技术可行性。
图4展示了点集在半球面上(左图)和不在半球面上(右图)的两种情形。左图中，最小包围球要小于模型球;右图中，最小包围球与模型球重合。那么，是否可依据两球的大小关系，来感知点集在模型球面上的空间分布?进而确定其与球心p的线性可分性呢?
基于上述猜想，定理2和定理3提出并证明了用于判定点与集合之间线性可分性的必要充分条件，具体如下。
定理2. (p parallel M准则): 球面S_0上的集合M和S_0的球心p线性可分，当且仅当集合M的最小包围球的半径r_M小于S_0的半径r_0。即，p parallel M Leftrightarrow r_M < r_0 (具体证明见附录B)。
定理3. (p parallel M准则): 球面S_0上的集合M和S_0的球心p线性不可分，当且仅当集合M的最小包围球的半径r_M等于S_0的半径r_0。即，p parallel M Leftrightarrow r_M = r_0 (具体证明见附录B)。
推论1. (p parallel C准则): 给定点p与集合C，S_0为以点p为球心，r_0(任意正常数)为半径的模型球面，M为由点p向集合C中的各个点作射线，这些射线与S_0相交得到的交点集合，B_M为集合M的最小包围球，r_M为B_M的半径。则有，点p和集合C线性可分当且仅当r_M小于r_0，即p parallel C Leftrightarrow r_M < r_0。
证明. 根据定理1(点与集合线性可分的方向不变性)，有
p parallel C Leftrightarrow p parallel M
根据定理2，有
p parallel M Leftrightarrow r_M < r_0
由上面两式，可以得到，
p parallel C Leftrightarrow r_M < r_0. qquad square
推论2. (p parallel C准则): 给定点p与集合C，S_0为以点p为球心，r_0(任意正常数)为半径作模型球，M为由点p向集合C中的各个点作射线，这些射线与S_0相交得到的交点集合，B_M为集合M的最小包围球，r_M为B_M的半径。则有，点p和集合C是线性不可分的当且仅当r_M等于r_0，即p parallel C Leftrightarrow r_M = r_0。
显然，推论2是推论1的逆否命题，结论自然成立。
4. 集合与集合的线性可分判定
直觉上，若集合A与集合B线性可分，则集合A中的任意一点与集合B线性可分，集合B中的任意一点与集合A线性可分。反之也成立吗?下面定理4和定理5给出了这方面的证明。
为了辅助定理4和定理5的提出，引理1首先被提出，用于证明当且仅当在某一特定情况下，集合A与集合B中的任意一点均与异类集合线性可分，但集合A与集合B却线性不可分。
引理1. 给定集合A与集合B，集合A和集合B的凸包分别为 ext{convex}(A)和 ext{convex}(B)，记 ext{convex}(A)和 ext{convex}(B)的交集为C_{AB}。集合A与集合B中的任意点都与异类集合线性可分，但集合A与集合B线性不可分，当且仅当，A、B两集合的凸包相交(即C_{AB}不为空)，但A、B中的任意点都不属于该相交区域。可形式化描述为：forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A) land (A parallel B) Leftrightarrow (C_{AB} eq varnothing) land forall p(p in A cup B ightarrow p otin C_{AB})。
证明. (1) 充分性：forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A) land (A parallel B) Rightarrow (C_{AB} eq varnothing) land forall p(p in A cup B ightarrow p otin C_{AB})。
首先，我们将构造出左式“forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A) land (A parallel B)”所对应的情形。
第一步，“A parallel B”。下面图5给出了三种A与B线性不可分的例子。
如果用凸包对它们进行进一步描述，如图6和图7所示。
为了满足“forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A)”，在A、B集合的凸包交集区域不能存在任何点，否则必然是线性不可分的。因此需要将它们的交集区域C_{AB}中的点清空。如图8所示。
可以发现，情形1中集合A和B原本各自只有一簇(在空间中是连续的一个整体)，在清空相交区域后，集合A和集合B仍然各为一簇，但由于相交部分被清除，其变得线性可分了。
情形2中集合A和B同样原本各自只有一簇，在清空相交区域后，集合B被分解为了两簇，集合A仍为一簇，从整体上看集合A与集合B也是变得线性可分了。
而在情形3中，在清空凸包交集区域后，A、B两集合均被分解为多个子簇，其子簇的存在使得其在主类上仍基本保持着原本的轮廓，整体上依旧线性不可分。也就是说，只有情形3这种情况符合了命题的左式“forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A) land (A parallel B)”。
在这一情形下，根据上面的步骤可知，A、B两集合的凸包存在交集，且在其交集区域，既没有A的点也没有B的点，即“(C_{AB} eq varnothing) land forall p(p in A cup B ightarrow p otin C_{AB})”。
至此，充分性得证。
(2) 必要性：(C_{AB} eq varnothing) land forall p(p in A cup B ightarrow p otin C_{AB}) Rightarrow forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A) land (A parallel B)。
首先，我们将构造出“(C_{AB} eq varnothing) land forall p(p in A cup B ightarrow p otin C_{AB})”所对应的情形。
第一步，“(C_{AB} eq varnothing)”即A、B两集合的凸包存在相交(如图9(a))，其相交区域记为C_{AB}(如图9(b))。
第二步，“forall p(p in A cup B ightarrow p otin C_{AB})”，即集合A与集合B均没有点在C_{AB}中。为此，我们将C_{AB}中所有点清除，使得其满足该条件，如图10所示。至此，左式“(C_{AB} eq varnothing) land forall p(p in A cup B ightarrow p otin C_{AB})”所对应的情形已被构建出。
当C_{AB}变为空白地带时，原本的集合A和集合B实际上被分解为了多个独立的子类(如图11所示)，它们各自的凸包都是不相交的，即各个子类之间是线性可分的，因此，此时集合A和集合B中的任意点与异类集合都是线性可分的，而集合A与集合B仍然是线性不可分的。
至此，充分性得证。
根据引理1必要性证明中的图11，可以发现，如果A、B两类中没有或者只有一个类具有“类内异质性”(存在多个异质的子类)，是无法满足“A、B两集合线性不可分，且两集合中的任意点与异类集合线性可分“这一条件的(如图11(a)、图11(b)所示)。只有两集合同时具备明显的类内异质性，并且其在主类层面上存在相交，且相交区域完全处于各个子类之间的空白中间地带，使得从子类层面上不存在任何交集，才能够满足该条件。实际上，从机器学习的角度看，该情形中集合A和集合B的凸包相交区域是一个“矛盾地带”，因为其同时归属于两个互斥的类别。为方便后续描述，本文将该情形命名为“异质间隙性交叠”，缩写作HGO(Heterogeneous Gap Overlap)。
在引理1的基础上，定理4和定理5得以提出。
定理4. 在非HGO情形下，集合A与集合B线性可分，当且仅当集合A中的任意一点与集合B线性可分，且集合B中的任意一点与集合A也线性可分。即，在非HGO情形下，
A parallel B Leftrightarrow forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A).
证明. (1) 充分性：在非HGO情形下，A parallel B Rightarrow forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A)。
(反证法)：假设结论forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A)不成立。这意味着至少存在一个来自集合A或集合B的点，该点与另一个集合B或集合A线性不可分。
而无论集合A中存在点与集合B线性不可分，还是集合B中存在点与集合A线性不可分，根据集合可分定义可得，集合A与集合B线性不可分，即A parallel B。
“集合A与集合B线性不可分(A parallel B)”与已知前提“集合A与集合B线性可分(A parallel B)”矛盾，因此，原假设不成立!命题得证。
(2) 必要性：在非HGO情形下，forall p(p in A ightarrow p parallel B) land forall p(p in B ightarrow p parallel A) Rightarrow A parallel B。
(反证法)：假设结论A parallel B不成立。这意味着集合A的凸包 ext{convex}(A)和集合B的凸包 ext{convex}(B)相交(即C_{AB} eq varnothing)，又因为集合A和集合B的分布属于非HGO情形，因此，C_{AB}必存在至少一个点，即
exists p left( (p in A cup B) land (p in ext{convex}(A) cap ext{convex}(B)) ight)
进而有exists p((p in A land p parallel B) lor (p in B land p parallel A))成立。
“集合A或集合B中至少存在一点与另一集合A或集合B线性不可分”，与前提“集合A或集合B中的任意一点都与另一个集合A或集合B线性可分”矛盾，因此，原假设不成立!命题得证。
定理5. 在非HGO情形下，集合A与集合B线性不可分，当且仅当集合A中至少存在一点与集合B线性不可分，或集合B中至少存在一点与集合A线性不可分。即，在非HGO情形下，A parallel B Leftrightarrow exists p(p in A land p parallel B) lor exists p(p in B land p parallel A)。
显然，定理5是定理4的逆否命题，定理4成立，则定理5自然成立。
为方便论述，下文所有的情形均默认在非HGO情形下讨论。
基于点与集合的线性可分判定，定理4和定理5提出并证明了集合与集合线性可分(不可分)的充分必要条件。该充分必要条件，为最终判定算法的实现提供了可高度并行化的理论基础。
5. 算法设计与分析
基于前文点与集合线性可分的判定定理(推论1和推论2)，以及集合与集合线性可分的判定定理(定理4和定理5)，集合与集合间的线性可分判定算法设计如下：
并行化地对集合A和B中的每一个点p进行如下操作：利用推论1和推论2，判断点p与另一个集合是否线性可分。根据定理4和定理5，如果所有点都与另一个集合线性可分，那么两集合线性可分，否则线性不可分。详细的步骤见算法1。
算法1 基于球面模型的并行化线性可分判定算法
输入: 集合A和集合B。
1. 根据定理4和定理5，对于集合A和集合B中的每一点p，与另一集合(集合B或集合A)并行地作线性可分判定：
(1) 基于定理1，构建球面模型。以点p为球心，作半径为r_0(可任意设定，通常设为1)的模型球面S_0;由点p向另一集合中的所有点作射线，计算与模型球面S_0的交点，并将这些交点保存为球面点集M;
(2) 求集合M的最小包围球B_M，球心记为o_M，半径记为r_M;
(3) 基于推论1和推论2，如果r_M < r_0，则点p与另一集合线性可分;否则，线性不可分;
2. 根据定理4和定理5，若步骤1中存在线性不可分的情况，则线性不可分。否则线性可分。
3. 结束。
输出: 线性可分性(可分或不可分)。
依据上述线性可分判定算法，集合与集合线性可分的判定被分解为并行执行的点与集合线性可分判定，而点与集合的线性可分判定，其时间耗费主要集中在球面点集的最小包围球的构建上。因此，本文算法的时间复杂度最终取决于最小包围球的构建算法。考虑到目前计算最小包围球的最优算法[33]的最坏时间复杂度是O(nd^2)(n为点集规模，d为维度)，本文算法在并行化下的最坏时间复杂度为O(nd^2)。
6. 实验验证
本节分为两个部分，第一部分是通过一组2D、3D实例来展示本文方法的直观效果;第二部分是通过比较现有方法与本文方法的时间耗费来验证本文方法的执行效率。
6.1. 实例展示
本节选择了四个2D数据案例(其中两个是线性可分的，两个是线性不可分的)和两个3D数据案例(一个线性可分和一个线性不可分)进行实验。
在实验结果的展示方面，为每个案例设计了四张图，用来可视化呈现线性可分性判定的整个过程。其中(a)是线性可分问题的初始状态，即集合A与集合B;(b)并行化判断集合A与集合B中的任意一点p是否与另一个集合线性可分，图中展示的是集合A中的一点与集合B之间的线性可分性判定;(c)是建立球面模型，即点p和集合B之间的线性可分问题等价变换为球心p和球面集合M之间的线性可分问题;(d)根据推论1和推论2，比较集合M的最小包围球B_M的半径与模型球半径的大小，可以得到集合A中的点p与集合B的线性可分性。基于集合A或B中的每一个点与另一集合B或A的线性可分判定结果，依据定理4和定理5，可以得到集合A与集合B的线性可分性。实验结果如图13-16所示。
三维实例依然具有可观测性，同样能用来展示本文方法理论的合理性。因此，增加了两个三维实例(一个可分和一个不可分)，如图17和图18所示。
上述来自2D和3D的实验结果，与人们直觉可感知的可分情况判定是一致的，这也佐证了本文判定理论的正确性。
6.2. 时间效率验证
为了实证比较本文提出的方法与现有测试方法(SP、Simplex、Interior Point Method、Convex hull)的时间成本差异，同时兼顾各对比方法的适用性、实验效果的直观性、以及数据集在维度和类型方面的多样性，选择了如表3所示的一些基准数据集。所有方法都在相同的硬件和软件环境下进行(MATLAB R2023b, a PC with an Intel(R) Xeon(R) Silver 4210 2.20GHz processor and 32.0 GB RAM, equipped with an NVIDIA Quadro RTX 4000 graphics card)。对于每个数据集，记录了每种方法的实际执行时间。如果执行时间超过18000s，算法将终止，并且执行时间统一记录为“>18000s”。实验结果显示在表4中。在本文的实验部分中，数据规模(n)表示A、B两集合的总点数。
表3 实验所用数据集
数据名称 类别数 维度(d) 数据规模(n) 备注
Iris 3 4 150 无
Glass 7 9 214 无
MNIST 10 784 10000 MNIST-test
Fashion-MNIST 10 784 10000 Fashion-MNIST-test
此外，由于Simplex和Interior Point Method在默认参数ConstraintTolerance下有时会出现误判情况，我们选择了三个不同的约束容忍值(即ConstraintTolerance=1e-3、1e-6、1e-9)来进行相关实验(在本文实验中，Simplex和Interior Point Method是通过调用MATLAB R2023b中Optimization Tool的‘linprog’函数来实现)。
如表4所示，在现有方法中，Simplex和Interior Point Method在大多数情况下表现稳定;SP和凸包法在低维度(<10D)下表现良好，但在高维度下时间成本显著增加。本文方法在低维度下与现有方法相似，但在高维度下优于它们。
为了使时间效率验证实验更具统计意义，下面从维度和规模两个方面增加了基于人工数据集的对比验证实验(关于人工数据集的生成方法，请参考附录C)。
(1) 关于维度的对比实验
对于每个给定的维度d，从以坐标原点为中心的d维单位立方体中随机抽样20组规模为5000的数据集(其中10组线性可分数据集，10组线性不可分数据集)。记录每种方法在这20个数据集上的执行时间，并计算其平均执行时间作为比较指标值。对于平均执行时间超过18000s的，记录为“>18000s”。实验结果显示在表5中。
为了更直观地描述随着维度增加不同方法的时间成本变化，根据表5中的实验统计数据，生成了相应的统计趋势图(图19)。考虑到不同方法之间的时间成本差异较大，将它们放在一个图中进行比较会影响对比度和展示效果，我们另外单独比较了本文方法与其他各个方法的时间成本，趋势对比图分别显示在图20的(a)、(b)和(c)中。
从表5和图19-20中可以看出，在现有方法中，Simplex和Interior Point Method这两个同属线性规划技术路线的方法，它们在时间效率性能上表现相似，普遍优于其他现有方法;SP的时间成本随维度的增加而迅速增长，显示出它对维度相对敏感;而Convex hull的时间成本总是超过本文设定的时间上限。相对而言，本文中的方法在大多数情况下比其他方法的时间成本更低，特别是在高维情况下，其优势更为突出。
此外，我们还可以从表5中看到，在一些高维实验中，Simplex和Interior Point Method存在误判的情况，而且这种误判的发生随着维度的增加变得越来越明显。误判的发生归因于Simplex和Interior Point Method的算法实现，这些方法需要设定一个约束容忍度参数，即ConstraintTolerance。超出约束条件但在这个约束容忍度范围内的解被视为可行解。因此，对于不可分任务，如果ConstraintTolerance设置得太大，有可能会被误判为可分的。从表5中还可以进一步看出，降低ConstraintTolerance值可以提高判断结果的准确性，但同时也会相应增加时间成本。
(2) 关于规模的对比实验
对于每个给定的集合规模n，从以坐标原点为中心的1000维单位立方体中随机抽样20组n点的数据集(其中10组线性可分数据集，10组线性不可分数据集)。记录每种方法在20个数据集上的执行时间，并计算其平均执行时间作为比较指标值。对于平均执行时间超过18000s的，记录为“>18000s”。实验结果显示在表6中。
图21是基于表6中的实验统计数据的统计趋势图。为了更清楚地说明本文方法与其他方法之间的时间成本差异，针对每种方法与本文方法的时间成本，分别提供了单独的比较图，如图22的(a)、(b)和(c)所示。
从表6和图21-22可以看出，当点集规模相对较小时，Simplex和Interior Point Method的时间表现接近且相对良好;然而，当规模增加到15000及以上时，由于超过内存限制，Interior Point Method的时间成本显著上升，而Simplex的表现则相对稳定。SP的时间成本随着规模的增加迅速增长。Convex hull的时间成本总是超过本文设定的上限。与现有方法相比，本文方法所需的执行时间在大多数情况下都要低得多。
上述实验表明，本文提出的线性可分性测试方法在实施时的时间效率明显高于由SP、Simplex、Interior Point Method和Convex hull代表的传统方法。
6.3. 并行化框架验证
定理4和定理5为两集合线性可分判定问题的并行化处理提供了理论依据。鉴于点与集合线性可分判定问题可视为集合与集合线性判定问题的一种特例，因此，已有的其它线性可分判定方法，都可通过本文提供的并行化框架，实现并行化处理。
在理想并行化下，“两集合之间的线性可分性判定”耗时相当于子任务“一个点与异类集合的线性可分性判定”的最大耗时。不过在实际中，受限于硬件资源等因素，理想的并行化往往是难以达到的。表7是已有的几种代表性线性可分判定算法，在本文提供的并行化框架下的实验结果。
根据表7可以看到，在本文的并行化框架下，各个方法的效率都得到了不同程度的提升，但由于硬件条件的限制，很难做到n个任务的并行处理，因此它们的加速比并不能达到理论上限。其中SP方法的加速相对有限，Simplex的加速比较明显，而从绝对耗时上来看，本文方法在绝大多数情况下仍然是有明显优势的。
如果将所有“点与集合线性可分性判定”子任务的串行执行作为本文方法的串行版本，可以对本文方法的加速比进行以下分析：并行化情况下本文方法是同时处理n个子任务，理论上其耗时是单个子任务的时间，而在串行情况下本文方法是逐个地处理n个子任务，其耗时是n个子任务的时间总和。从这个角度讲，本文方法并行化的理论加速比为n。但在实际中，硬件环境中不一定有足够的核心数来同时执行如此多的子任务，因此其加速比往往达不到n。为此，我们对其串行版本做了一系列实验，以评估在本文计算环境下本文方法并行化的加速比，发现其加速比会随具体任务的规模、维度而变化，在本文的实验中，其加速比大约在7到38，详细的实验数据可见附录D。
6.4. 算法准确性检验
在上述的实验中，正如表格中所显示的，本文方法的线性可分性判定结果与实际情况均一致。但这并不意味着本文方法在所有情形下都是完全准确的，因为理论上本文方法在HGO情形下会出现误判情形。
HGO情形的出现概率受实验数据集的生成方式影响，在一些生成方式下，该情形是几乎不可能出现的。在前面的实验中，我们所使用的数据生成方式(如附录C中所示)是使用超平面/足够弯曲的超曲面来对单位立方体中的无标签数据进行划分，从而得到线性可分/线性不可分的两数据集。在这样的生成模式下，同一类数据在空间中总是相对连续的整体。而HGO情形的出现不仅需要A、B两类是线性不可分的，还需要A、B两点集都不是连续的整体，每一类都要存在多个子簇，且子簇之间存在明显的间隔(用于后续作为两类的相交区域)，因此之前所使用的超平面/超曲面方法生成的数据几乎并不会出现HGO的情形。
为了更为全面的对本文算法的准确性进行检验，下面将专门设计实验用于观察本文方法在各个情形下的准确率(或者说观察非HGO情形的广泛性)，除了前面所给出的真实数据集(如表3所示)，下面还将增加多种不同的数据生成模式，从而增强实验的普适性。
鉴于HGO情形只出现在线性不可分数据中，除前面所使用的“超平面/超曲面分割法”，本文还额外选取了四种不同的线性不可分数据生成方式，包括：高斯分布重叠法(使用高斯分布来生成A、B两集合，同时通过控制参数使得两集合有一定程度的重叠，从而线性不可分)，同心圆法(使用多层的同心圆，在各层之间交替的生成A、B两集合，使之线性不可分)，随机标签法(首先在单位立方体中生成n个无标签的数据，然后对各个点随机的给定标签)，多聚类中心法(对于A、B两类，分别随机生成多个聚类中心，然后按每个聚类中心生成点，从而形成多簇的两类数据。该方法不一定总能保证生成不可分数据，因此其生成的数据都会经过其他方法(如SP)的验证才会投入实验。)。对于人工数据集，我们取规模为5000，均匀地在[100, 500]中取5个维度，在每一个维度下均用以上的五种数据生成方法分别做100次重复随机实验，将实验结果与实际线性可分性进行一致性验证得到准确率，实验结果如下表所示。
表8 不同数据下本文方法的准确率
数据 Ours准确率
真实数据(如表3所示) 100.0%
人工数据
线性可分数据 100.0%
线性不可分数据 超曲面分割法 100.0%
高斯分布重叠 100.0%
同心圆法 100.0%
随机标签法 100.0%
多聚类中心法 99.9%
通过表格可以发现，在线性可分情况下，本文方法总是准确的，在线性不可分的绝大部分情形下，本文方法仍然是准确的，极少数的误判情形来自于“多聚类中心法”所生成的数据。在该数据生成模式下，每一个类别都存在“类内异质性”，而“线性不可分”和“类内异质性”仅仅初步符合了HGO的形成条件。HGO的形成还需要所有的子簇之间不存在任何重叠，而往往子簇完全不存在重叠的时候主类都是实际可分的，因此要同时符合“子簇不重叠”且“主类线性不可分”这两个条件并不容易，即使在最容易出现HGO情形的“多聚类中心”数据中这也是少见的。
综上所述，本文方法对于实际线性可分的任务总是准确的，对于实际线性不可分的任务，在绝大多数情况下是准确的，仅在少数出现HGO分布的情形下本文方法会出现误判。换而言之，对于本文方法所给出的“线性不可分”的判定是可以完全信任的，而本文方法给出的“线性可分”的判定，在绝大多数情况下是可靠的，但对于存在多聚类中心的数据(这一点可能可以通过聚类算法进行分析)，仍然需要考虑数据有没有可能刚好处于HGO的情形。总而言之，除去对于准确率有极高要求的场景，本文方法的判定可以作为数据线性可分性的一种有效的快速检测。
7. 总结与展望
围绕集合与集合的线性可分议题，本文提出了一个全新的线性可分判定方法，该方法：(1)形式简单、易于计算;(2)高度并行化的内在特点，确保了实现算法的低时间复杂度。本文方法的提出，能更好地满足来自实现层面日益增长的效率需求，促进线性可分判定技术的应用拓展，进一步夯实和丰富凸技术领域的理论基础和技术储备。
本文方法仍然存在一定的不适用情形(HGO)，在线性不可分的多聚类中心的数据分布上其仍有小概率会出现误判，这是我们未来一步探讨完善的方向之一。虽然随着计算机的发展对于算法的空间复杂度要求逐渐降低，但本文方法在完全并行化下所需空间复杂度仍然是可观的，这是本文方法目前的局限性，这也是我们未来将进一步探讨研究的另一议题。
现有的人工神经网络模型，更多是非线性模型，其本质就是实现非线性问题的线性变换。基于此，可以尝试探讨用本文的研究成果来指导模型的具体构建，缓解模型构建中的现实困境。此外，在凸优化研究领域，基于本文的研究成果，来提升现有凸技术的实现效率，降低其时间复杂度，也是我们试图去探讨的方向。
参考文献
[1] Taori R, Dave A, Shankar V, Carlini N, Recht B, and Schmidt L. Measuring robustness to natural distribution shifts in image classification[J]. Advances in Neural Information Processing Systems, 2020, 33: 18583-18599.
[2] Miller J P, Taori R, Raghunathan A, Sagawa S, Koh P W, Shankar V, Liang P, Carmon Y, and Schmidt L. Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization[C]. In International Conference on Machine Learning, PMLR, 2021, 7721-7735.
[3] Barron A R. Predicted squared error: a criterion for automatic model selection[C]. In Self-organizing methods in modeling, CRC Press, 2020, 87-103.
[4] Ding J, Tarokh V, and Yang Y H. Model selection techniques: An overview[J]. IEEE Signal Processing Magazine, 2018, 35(6): 16-34.
[5] Baymurzina D, Golikov E, and Burtsev M. A review of neural architecture search[J]. Neurocomputing, 2022, 474: 82-93.
[6] Ren P Z, Xiao Y, Chang X J, Huang P Y, Li Z H, Chen X J, and Wang X. A comprehensive survey of neural architecture search: Challenges and solutions[J]. ACM Computing Surveys (CSUR), 2021, 54(4): 1-34.
[7] Niu Z Y, Zhong G Q, and Yu H. A review on the attention mechanism of deep learning[J]. Neurocomputing, 2021, 452: 48-62.
[8] Rosenblatt F. The perceptron: a probabilistic model for information storage and organization in the brain[J]. Psychological review, 1958, 65(6): 386.
[9] Cortes C and Vapnik V. Support-vector networks[J]. Machine learning, 1995, 20: 273-297.
[10] Chauhan V K, Dahiya K, and Sharma A. Problem formulations and solvers in linear svm: a review[J]. Artificial Intelligence Review, 2019, 52(2): 803-855.
[11] Shaban A, Cheng C A, Hatch N, and Boots B. Truncated back-propagation for bilevel optimization[C]. In The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, 1723-1732.
[12] Dong S, Wang P, and Abbas K. A survey on deep learning and its applications[J]. Computer Science Review, 2021, 40: 100379.
[13] Minsky M and Papert S. An introduction to computational geometry[J]. Cambridge tiass., HIT, 1969, 479: 480.
[14] Barber C B, Dobkin D P, and Huhdanpaa H. The quickhull algorithm for convex hulls[J]. ACM Transactions on Mathematical Software (TOMS), 1996, 22(4): 469-483.
[15] Sartipizadeh H and Vincent T L. Computing the approximate convex hull in high dimensions. arXiv preprint arXiv:1603.04422, 2016.
[16] Rockafellar R T. Convex analysis[M]. Princeton university press, 1997, 11.
[17] Fisher J. Visualizing the connection among convex hull, voronoi diagram and delaunay triangulation[C]. In 37th Midwest instruction and computing symposium. Citeseer, 2004.
[18] Burch M, van Lith J, van de Waterlaat N, and van Winden J. Voronoier: from images to voronoi diagrams[C]. In Proceedings of the 13th International Symposium on Visual Information Communication and Interaction, 2020, 1-9.
[19] Jayaram M A and Fleyeh H. Convex hulls in image processing: a scoping review[J]. American Journal of Intelligent Systems, 2016, 6(2): 48-58.
[20] Cevikalp H, Yavuz H S, and Triggs B. Face recognition based on videos by using convex hulls[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2019, 30(12): 4481-4495.
[21] Wang G F, Qin X Y, Zhong F, Liu Y, Li H B, Peng Q S, and Yang M H. Visual tracking via sparse and local linear coding[J]. IEEE Transactions on Image Processing, 2015, 24(11): 3796-3809.
[22] Bo C J and Wang D. Online object tracking based on convex hull representation[C]. In 2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS), IEEE, 2016, 1221-1224.
[23] Poco J, Etemadpour R, Paulovich F V, Long T V, Rosenthal P, Oliveira M C F, Linsen L, and Minghim R. A framework for exploring multidimensional data with 3d projections[C]. In Computer Graphics Forum, Wiley Online Library, 2011, 30: 1111-1120.
[24] Guo Z H, Liu C, Zhang X S, Jiao J B, Ji X Y, and Ye Q X. Beyond bounding-box: Convex-hull feature adaptation for oriented and densely packed object detection[C]. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, 8792-8801.
[25] Fisher R A. The use of multiple measurements in taxonomic problems[J]. Annals of eugenics, 1936, 7(2): 179-188.
[26] Fourier J B J. Reported in: Analyse des travaux de l'academie royale des sciences pendant l'année 1824. Partie mathématique, Histoire de l'Académie Royale des Sciences de l'Institut de France, 7: xlvii-lv, 1827.
[27] Kuhn H W. Solvability and consistency for linear equations and inequalities[J]. The American Mathematical Monthly, 1956, 63(4): 217-232.
[28] Wolfe P. The simplex method for quadratic programming[J]. Econometrica: Journal of the Econometric Society, 1959, 382-398.
[29] Silva L M and Oliveira A R L. Modified controlled cholesky factorization for preconditioning linear systems from the interior-point method[J]. Computational and Applied Mathematics, 2021, 40(4): 154.
[30] Yogananda A P, Murty M N, and Gopal L. A fast linear separability test by projection of positive points on subspaces[C]. In Proceedings of the 24th International Conference on Machine Learning (ICML-07), 2007, 713-720.
[31] Elizondo D. The linear separability problem: Some testing methods[J]. IEEE Transactions on neural networks, 2006, 17(2): 330-344.
[32] Gabidullina Z R. A linear separability criterion for sets of euclidean space[J]. Journal of optimization theory and applications, 2013, 158(1): 145-171.
[33] Cavaleiro M and Alizadeh F. A faster dual algorithm for the euclidean minimum covering ball problem[J]. Annals of Operations Research, 2017, (1).