On Linear Separability of the MNIST Handwritten Digits Dataset
Ákos Hajnal · 2026
Read On Linear Separability of the MNIST Handwritten Digits Dataset by Ákos Hajnal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12850.txt.
Introduction
Ákos Hajnal asks a basic open question: is the MNIST handwritten digit dataset linearly separable? The dataset is a classic benchmark, yet sources disagree on this point. No full answer had been given despite its small size and long history. The paper reviews theory and tools for testing separability. It then checks pairwise and one-vs-rest splits across training, test, and combined sets. Findings are reported for each assembly in a systematic way.
Catalog record
| CREATOR | Ákos Hajnal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23497 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12850
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Linear Separability of the MNIST Handwritten Digits Dataset Ákos Hajnal Abstract The MNIST dataset containing thousands of handwritten digit images is still a fundamental benchmark for evaluating various pattern-recognition and image-classification models. Linear separability is a key concept in many statistical and machine-learning techniques. Despite the long history of the MNIST dataset and its relative simplicity in size and resolution, the question of whether the dataset is linearly separable has never been fully answered – scientific and informal sources share conflicting claims. This paper aims to provide a comprehensive empirical investigation to address this question, distinguishing pairwise and one-vs-rest separation of the training, the test and the combined sets, respectively. It reviews the theoretical approaches to assessing linear separability, alongside state-of-the-art methods and tools, then systematically examines all relevant assemblies, and reports the findings. Keywords MNIST dataset \cdot Linear separability \cdot Machine learning 1 Introduction The MNIST dataset created in the late 1990s by Yann LeCun at al. [ 18 ] is still a fundamental benchmark for evaluating pattern-recognition and image-classification methods. It consists of 70,000 gray-scale images of handwritten digits in 28x28-pixel resolution, as illustrated in Fig. 1 . The dataset is split into 60,000 training and 10,000 test samples. The goal is to accurately recognize all digits in the test set by teaching the model exclusively on the training data. Figure 1: Samples from the MNIST dataset. First and last three images of the training (first row) and the test set (second row) are shown. Sub-captions indicate the digit (label) and the index of the sample in the series. Various machine learning approaches had been applied to this dataset, including linear models, k-Nearest Neighbor, Random Forest, Support Vector Machines (SVM), both shallow and Deep Neural Networks, Convolutional Neural Networks (CNN). At the time of writing, the best published result was obtained using an ensemble of CNNs [ 2 ] , achieving 99.91% accuracy, which surpasses estimated human performance of approximately 0.2% error [ 19 ] . Linear models and the notion of linear separability, separating hyperplanes are central to many fields, including statistics and optimization. Classic algorithms like the Perceptron algorithm [ 22 ] , SVM [ 7 ] , logistic regression rely on these concepts, and constitute the fundamental basis of the operation performed by an artificial neuron. Linear separability is the property of a dataset that allows a single linear decision boundary to separate the data points belonging to two classes. Formally, given n samples \{x_{1},\dots,x_{n}\} ( x_{i}\in\mathbb{R}^{d} for i=1,...,n , d is the number of features) and labels y_{i}\in\{-1,1\} corresponding to one of the two classes associated with sample x_{i} , the dataset is linearly separable if there exist a separating hyperplane w^{\top}x_{i}+b=0 ( normal vector w\in\mathbb{R}^{d} , bias b\in\mathbb{R} ) such that w^{\top}x_{i}+b>0 for all x_{i} where y_{i}=1 , otherwise w^{\top}x_{i}+b<0 . The separating hyperplane , if exists, therefore passes between the data points dividing all the points with positive labels on one side and negatives on the other side. Testing linear separability is the task to only decide the existence of a separating hyperplane, without providing one. Samples in the MNIST dataset fall into ten classes corresponding to the digits 0–9. Linear separability can be investigated in two settings: (1) pairwise linear separability and (2) one-vs-rest linear separability . In the pairwise case, we ask whether samples of one digit (e.g., 0) can be linearly separated from samples of another digit (e.g., 1). In the one-vs-rest case, we ask whether samples of a given digit (e.g., 0) can be linearly separated from all other digits (1–9). Despite the long history of the MNIST dataset and its relative simplicity (in number of samples and resolution) only a few papers examined these questions thoroughly. Zhong et al. [ 24 ] carried out experiments to determine linear separability of the MNIST test set of digit 0 and each of the remaining 9 digits (pairwise), furthermore, computed the so called degree of linear separability for all digit pairs (45), but without claiming linear separability between these latter pairs. Another study [ 13 ] investigated a single digit pair (3 vs 7) on a reduced subset, on down-scaled samples, and stated that "the MNIST training set is not linearly separable" citing [ 18 ] , which paper did not actually make this claim. The authors in research [ 20 ] trained so called Phase Separation Binary Classifier models for each digit pair for the MNIST dataset, but they didn’t address and report linear separability. [ 8 ] conducted empirical study on all-pairs (45) and 1-vs-rest separation of the MNIST dataset; the results provided (accuracy comparison with another method) are however not conclusive with regard to the linear separability. This paper aims to clarify the question of linear separability of the MNIST dataset and to provide comprehensive analysis and empirical evidence – even if the findings might merely confirm the widespread but informal consensus that "MNIST is not linearly separable". Section 2 presents an overview of existing approaches and state-of-the-art methods. After selecting and applying a suitable technique, section 3 evaluates and reports the results of the linear separability experiments. Finally, the paper is concluded. 2 Approaches to Testing Linear Separability Linear separability has been studied for many decades. Fisher’s Linear Discriminant Analysis [ 11 ] introduced a statistical method for separating datasets (1936), however, it does not directly address linear separability. The Perceptron algorithm [ 22 ] proposed by Rosenblatt (extended later by many variants, such as [ 16 ] ) guarantees convergence at finding the separating hyperplane in finite steps – provided the dataset is indeed separable. The number of steps required is typically unknown in advance (and can be extremely large); non-termination cannot conclude non-separability, regardless of the number of iterations performed so far. Support Vector Machine (SVM) introduced by Cortes and Vapnik [ 7 ] aimed to find the separating hyperplane with largest margin. Determining linear separability is a special case of support vector machines, known as a hard-margin SVM with a linear kernel. SVM solvers, such as LIBSVM [ 6 ] (which is the solver backend in Scikit-learn and other data mining toolkits) include a cost parameter to penalize misclassifications. In practice, this parameter is set to a large value to enforce, or closely approximate perfect separation. However, when the dataset is high-dimensional or contains a large number of samples, this can demand an excessive number of iterations or yield non-perfect separation. Computational geometrical approaches treat data samples as points in a high-dimensional space. The separating hyperplane theorem guarantees linear separability, if the two classes of data form disjoint, convex sets. To verify this, one can compute the convex hulls of each class and then check whether these hulls intersect. The time complexity of computing the convex hulls (e.g. with the QuickHull algorithm [ 3 ] ) can increase exponentially with data dimension. Zhong et al. [ 24 ] transformed the linear separability problem to an equivalent Minimum Enclosing (Covering) Ball (MEB) problem. Earlier MEB algorithms exhibited exponential time complexity [ 17 ] ; recent studies have come to a polynomial-time solution [ 9 , 5 ] . These findings make this approach competitive with linear programming solutions – proved to be faster