A New Sufficient & Necessary Condition for Testing Linear Separability between Two Sets

IEEE Trans Pattern Anal Mach Intell. 2024 Jan 22:PP. doi: 10.1109/TPAMI.2024.3356661. Online ahead of print.

Abstract

As a fundamental mathematical problem in the field of machine learning, the linear separability test still lacks a theoretically complete and computationally efficient method. This paper proposes and proves a sufficient and necessary condition for linear separability test based on a sphere model. The advantage of this test method is two-fold: (1) it provides not only a qualitative test of linear separability but also a quantitative analysis of the separability of linear separable instances; (2) it has low time cost and is more efficient than existing test methods. The proposed method is validated through a large number of experiments on benchmark datasets and artificial datasets, demonstrating both its correctness and efficiency.