Technical Summary: Algebraic Machine Learning for Small-to-Medium Datasets

Problem Statement

The prevailing paradigm in supervised machine learning relies on numerical optimization over parameterized models (e.g., neural networks, boosted trees), where inductive bias is encoded through architecture and hyperparameters tuned via cross-validation. While effective, this approach requires significant data and computational resources for validation, particularly in low-data regimes where every labeled example is scarce. Conversely, classical symbolic AI, which relies on explicit rules and logical relations, has largely been deemed non-competitive on realistic supervised tasks unless combined with modern numerical learners.

This paper challenges the assumption that symbolic methods cannot compete with strong standard baselines. It investigates Algebraic Machine Learning (AML), a framework that learns through the subdirect decomposition of algebraic structures rather than gradient-based optimization, to determine if a generic algebraic inductive bias can rival modality-specific baselines (like CNNs for images or XGBoost for tabular data) without the need for cross-validation or task-dependent hyperparameter tuning.

Methodology

The AML Framework

AML encodes classification tasks into an algebraic structure, specifically a semilattice.

• Encoding: Data points are represented as products (terms) of constants corresponding to feature-value pairs and class labels. For numerical variables, order relations are encoded via oppositely-ordered chains of constants.
• Learning Mechanism: Instead of optimizing parameters, AML performs subdirect decomposition. The learning process involves finding an "atomization" of the algebra that satisfies the classification constraints: no atom discriminates positive examples (examples belonging to the true class), while at least one atom discriminates every negative example.
• Algorithm: The Sparse Crossing algorithm iteratively constructs this atomization. It starts with the freest semilattice and enforces batches of "duples" (pairs of a term and a label). It removes atoms that incorrectly discriminate positive examples and adds atoms to discriminate negative examples, generalizing to unseen data.
• Classification: The paper evaluates two readout strategies:
  1. Fewest Misses: A direct algebraic classification based on the number of atoms failing to discriminate the example.
  2. Logistic Regression Readout: A linear layer trained on the atomization vector (where entries indicate if an atom is below the example's term). The paper primarily reports results using this readout, as it consistently yields higher F1 scores.

Experimental Setup

The study evaluates AML against strong, cross-validated baselines across two modalities:

• Image Classification: 12 datasets (e.g., MNIST, CIFAR-10, MedMNIST) ranging from 2 to 49 classes. Inputs are restricted to resolutions of 32x32 or lower (except COIL-20 at 128x128) due to computational costs.
• Tabular Classification: 29 datasets with mixed categorical and numerical features (2–308 features).
• Training Regimes: Experiments are conducted on training set sizes of 50, 100, 200, 500, 1000, and 2000 examples.
• Baselines:
  • Images: CNNs, MLPs, SVMs, XGBoost, LightGBM, Random Forests.
  • Tabular: XGBoost, LightGBM, Random Forests, MLPs, SVMs.
  • All baselines undergo 5-fold cross-validation for hyperparameter selection. AML uses fixed hyperparameters and no validation set.

Key Contributions

1. Systematic Empirical Evaluation: A comprehensive comparison of AML against standard supervised baselines across 41 datasets (12 image, 29 tabular) and varying training sizes (50–2000).
2. Performance in Low-Data Regimes: Demonstration that AML, utilizing a generic algebraic inductive bias and requiring no hyperparameter tuning, achieves competitive or superior performance compared to state-of-the-art methods when data is scarce.
3. Modality-Agnostic Success: Evidence that a single algebraic encoding framework can effectively handle structurally distinct data types (dense pixel grids and heterogeneous feature tables) without architectural redesign.

Results

Image Classification

• Aggregate Performance: Across all training sizes, AML (with logistic regression readout) is the best-performing method in aggregate, statistically distinguishable from all baselines.
• Low-to-Medium Data (50–1000 examples): AML achieves the highest macro-F1 score on a plurality of datasets in the 200–1000 example range, outperforming CNNs and other baselines by a significant margin.
• Large Data (2000 examples): CNNs become competitive with AML, consistent with the expectation that parameterized models better exploit task-specific biases as data volume increases.
• Statistical Significance: Post-hoc tests confirm AML significantly outperforms CNNs, XGBoost, LightGBM, Random Forests, SVMs, and MLPs in the image domain.

Tabular Classification

• Aggregate Performance: XGBoost remains the strongest method overall, statistically outperforming AML.
• Competitiveness: AML is comparable to other strong tabular baselines like LightGBM and Random Forests. It is not statistically distinguishable from these methods in aggregate, though it is distinguishable from XGBoost.
• Specific Regimes: AML achieves the best result on a plurality of datasets at the 1000-example training size.
• Readout Impact: While the logistic regression readout improves performance over the "fewest misses" variant, the algebraic model alone (fewest misses) still achieves a mean rank competitive with several baselines (outperforming MLPs and SVMs on tabular data).

Significance and Claims

The paper posits that symbolic learning can be competitive in realistic supervised tasks when the symbolic structure is learned from data rather than manually engineered. The significance of these findings rests on three main points:

1. Efficiency in Low-Data Regimes: AML's ability to learn without a held-out validation set allows it to utilize every labeled example for training. This provides a distinct advantage when data is scarce, as standard baselines must sacrifice data for hyperparameter tuning.
2. Fixed Inductive Bias: AML's inductive bias is derived from the algebraic structure itself, not from hyperparameters tuned on data. This allows it to sidestep the problem of selecting architectures and regularization parameters from limited data, a challenge that often hinders standard methods in small-data settings.
3. Viability of Algebraic Decomposition: The results suggest that subdirect decomposition is a viable learning mechanism. While AML currently lacks the extensive optimization and hardware co-design of deep learning or gradient-boosted trees, its competitiveness with a single unoptimized implementation indicates that algebraic decomposition is a promising direction for learning, particularly where data is limited and modality-agnostic approaches are desired.

The authors conclude modestly that while AML is currently competitive, scaling to larger datasets, additional modalities, and diverse task types remains an open empirical question requiring future work, including algorithmic acceleration and system optimization.