A Geometrical Approach to Constructing Neural Networks for Perfect Training-set Classification
Authors: Akos Hajnal
Organizations: Laboratory of Parallel and Distributed Systems Institute for Computer Science and Control (SZTAKI) · John von Neumann Faculty of Informatics Obuda University Budapest, Hungary
This paper proposes a method for constructing a neural network that achieves perfect classification of all samples in a given training set, without taking regularization into account. The network is constructed on-demand, with its layer sizes and neuron parameters determined through a geometrical analysis of the input data, in which separating hyperplanes are created and mapped to neurons with step activation functions. The proposed architecture consists of two hidden layers with distinct roles: inter-class separation and transformation of the data into a linearly separable representation. Inter-class separation requires every bi-chromatic pair of samples belonging to different classes to be separated by at least one hyperplane. We show that when this separation is achieved through a hierarchical partitioning of the data, the leaf nodes of the oblique decision tree, obtained as a byproduct, directly define the neurons of the linear separability layer, whose size is only one neuron greater than that of the inter-class separation layer. Experiments on the MNIST dataset demonstrate that the proposed method achieves perfect training-set classification, and compact models. The direct correspondence between the decision tree and network neurons enhances interpretability and explainability, while the construction procedure offers opportunities for parallel implementation and improved scalability.
0: 73 s 1: 75 s 2: 95 s 3: 101 s 4: 77 s 5: 93 s 6: 76 s 7: 79 s 8: 121 s 9: 109 s
899 s
194 951
100%
Table 1: Binary classifier ensembles recognizing individual digits, constructed using different hyperplane selection methods on the MNIST training dataset.
Figure 1: An example of an oblique decision tree and its corresponding neural network.
Method
Layer sizes
Total number of neurons
Total construction time (sequential)
Total number of parameters
Training accuracy
Linear Discriminant Analysis (LDA)
625-626-10
1 261
384 s
888 771
100%
Support Vector Machine (SVC)
356-357-10
723
2 070 s
410 489
100%
Logistic Regression (LR)
278-279-10
567
582 s
298 871
100%
Table 2: Multi-class classifiers recognizing individual digits, constructed using different hyperplane selection methods on the MNIST training dataset.
Neural network memorization studies how models store and retrieve training examples, how this differs from generalization, and how memory can be measured or controlled.
Understanding the features captured by the hidden layers of neural networks is a fundamental challenge in machine learning, despite their widespread success across various classification problems. In this work, we propose an algebraic framework for examining neural networks that model classification problems. Certain results, such as the correspondence between the neural network and neural ideals, algorithms for computing the neural ideals, and a stabilization theorem that enables approximation of the neural ideals, are first established. As an application to the framework, we present algorithms to identify and interpret the features captured by each hidden-layer neuron. Along with these theoretical developments, the practical performance has been demonstrated on the MNIST digit dataset, and the results highlight the pivotal role of neural ideals as a mathematical and computational tool for analyzing the features captured by neural networks. Further, we develop an interactive software that builds on the presented framework to visualize the features captured by each neuron. This tool is available at https://github.com/yvs1967/neural-network-representation-explorer
The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.
We develop a principled framework for constructing neural networks whose specific parameter realizations admit an explicit algorithmic interpretation. Existing algorithm-inspired architectures can explain the computational structure of a network, yet after standard training the learned parameters need not retain a clear relation to the motivating algorithm. We address this gap as follows. First, we model each data point as a sample of a class-dependent stochastic process and assume that statistics of this process can be estimated from a single sample and these statistics are sufficient to distinguish the classes. We then construct a neural network whose initial parameters exactly implement an algorithm for estimating these statistics, making the network fully interpretable. To account for mismatch between the idealized model and real data, we fine-tune this network while controlling its deviation from the algorithmic initialization. The trained network hence roughly retains the interpretation of the initial network. A PAC-Bayesian analysis yields a uniform generalization bound whose complexity term scales with the fine-tuning radius, providing a statistical motivation for our approach. We instantiate the framework for texture classification using the scattering transform to estimate the discriminative statistics.
Yanglin Zhang, Anneke von Seeger, Gilad Lerman +1
Technion – Israel Institute of Technology, Faculty of Mathematics · University of Minnesota, School of Mathematics