Classification of integers based on residue classes via modern deep learning algorithms

Technical Summary: Classification of Integers Based on Residue Classes via Modern Deep Learning Algorithms

Problem Statement
The study investigates the capacity of modern machine learning systems to classify integers based on their residue classes when divided by small prime numbers (specifically $p=2, 3, 7$, and up to $31$). While humans can easily determine parity (mod 2) or apply digit-sum rules for divisibility by 3, the authors posit that this task presents a non-trivial challenge for computers, particularly for Artificial Intelligence systems expected to autonomously discern mathematical patterns without explicit human-designed rules. The core question is whether state-of-the-art deep learning architectures, Automated Machine Learning (AutoML) platforms, and Large Language Models (LLMs) can effectively learn these divisibility rules from raw data or if they fundamentally rely on human-engineered features.

Methodology
The authors conducted a comprehensive evaluation across four distinct methodological categories using a sample space of non-negative integers up to $2^{32}-1$.

1. Deep Neural Networks (DNNs): The study tested Artificial Neural Networks (ANN), Convolutional Neural Networks (CNN), Recurrent Neural Networks (RNN), and Bidirectional Encoder Representations from Transformers (BERT).

   • Feature Engineering: A critical component of the methodology was the systematic application of various feature representations to the input integers. These included:
     • Raw integer values.
     • Binary and Base-three representations.
     • N-gram encodings (One-gram, Two-gram, Three-gram, and combinations thereof) treating digits as sequences.
     • Enhanced encodings incorporating the sum of digits or the sum of digits modulo $p$ (specifically for $p=3$).
   • Architecture: The ANN used a simple two-layer structure (64 and 32 neurons). CNNs utilized 1D convolution and max-pooling layers. RNNs employed a single LSTM layer. BERT models were fine-tuned for sequence classification.

2. Automated Machine Learning (AutoML): The authors evaluated pipelines from Amazon (AWS Sagemaker), Google (Vertex AI), and Microsoft (Azure ML Studio). These platforms were tested with raw data and various engineered features to determine if they could autonomously select optimal models and features.

3. Fourier Series Regression: A novel mathematical approach was proposed utilizing linear regression on Fourier series basis vectors. For a given modulus $p$, the input $x$ was transformed into sine and cosine vectors: $\sin(2\pi j x / p)$ and $\cos(2\pi j x / p)$ for $j=1, \dots, \lfloor p/2 \rfloor$. Ordinary Least Squares (OLS) regression was used to fit the labels, with predictions rounded to the nearest integer.

4. Large Language Models (LLMs): The study assessed the mathematical reasoning capabilities of open-source models (GPT-J-6B, LLaMA-7B, Falcon-40B) and closed-source models (ChatGPT, GPT-4 with code interpreter). Prompts were designed to elicit explanations of divisibility rules or the design of algorithms to solve the classification problem.

Key Results

• Dependence on Feature Space: The performance of all deep learning models was critically dependent on the input feature space.

  • Mod 2: Raw data yielded accuracy near random guessing (~0.5). Binary representation achieved 1.000 accuracy. N-gram encodings improved accuracy to ~0.8.
  • Mod 3: Raw data and simple N-gram encodings performed poorly. However, incorporating the "sum of digits" or "sum of digits mod 3" into the feature vector allowed models to achieve high accuracy (>0.9).
  • BERT Specifics: BERT achieved 1.000 accuracy with the "One-gram + sum" encoding but failed (~0.33) with "One-gram" alone. The authors attribute this to BERT's pre-training embedding space, which likely captures the recursive nature of digit sums, whereas other networks treated the sum as a large, unseen continuous value.

• AutoML Limitations: AutoML platforms failed to achieve effective classification when provided with raw data. They only succeeded when provided with explicitly engineered features (e.g., the sum of digits for mod 3). The platforms heavily favored tree-based algorithms over deep learning for this task.

• Fourier Series Success: The proposed linear regression method using Fourier basis vectors achieved 1.000 accuracy for both mod 3 and mod 7 problems. Notably, this was achieved with a minimal dataset (200 samples), demonstrating that the periodic nature of the residue function can be perfectly captured with few training examples when the correct mathematical basis is used.

• LLM Failures:

  • Open-source LLMs (GPT-J, LLaMA, Falcon) consistently produced inaccurate and uninformative responses regarding divisibility rules for primes $p \geq 7$, and often failed for smaller primes as well.
  • ChatGPT showed improved performance for small primes but resorted to using the modulo operator (%) for $p \geq 23$, providing no informative mathematical rule.
  • GPT-4, when asked to design a deep learning algorithm for the problem, generated code that was syntactically correct but failed to identify appropriate feature engineering techniques or select optimal algorithms, resulting in an ineffective solution.

Significance and Conclusions
The paper concludes that despite the advancements in AutoML and the reasoning capabilities of Large Language Models, feature engineering remains an indispensable task for improving model performance and interpretability.

1. Feature Engineering is Paramount: The study demonstrates that increasing model complexity or dataset size cannot compensate for the lack of appropriate feature engineering. Without domain-specific transformations (such as binary representation for mod 2 or digit sums for mod 3), even sophisticated models fail to learn simple mathematical patterns.
2. Limitations of Current AI: The inability of AutoML to autonomously discover these features and the failure of LLMs to articulate or design algorithms for these problems suggests that current AI systems lack a systematic, autonomous approach to discerning fundamental mathematical patterns from training data.
3. Mathematical Interpretability: The Fourier series regression method offers a highly effective, interpretable, and data-efficient alternative to deep learning for periodic classification problems, achieving perfect accuracy with minimal training data.

In summary, the authors argue that in the era of AutoML and LLMs, human domain knowledge applied through feature engineering is still the primary driver of success in solving structured mathematical problems, and reliance on these models for such tasks without careful data preparation is risky and often ineffective.