Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences

Yaohui Zhu, Kaiming Sun, Zhengdong Luo, Lingfeng WangAAAI 2025 · DOI

TL;DR

This paper introduces a "Progressive Self-Learning" (PSL) method to tackle the challenge of discovering mathematical formulas for integer sequences, even when the training data distribution differs significantly from the target sequences. By strategically constructing source data and iteratively refining the model with newly discovered target formulas, PSL significantly outperforms existing methods and even discovers novel mathematical patterns.

What Problem Does This Paper Address?

Symbolic Regression of Integer Sequences (SRIS) aims to find explicit mathematical formulas that generate given integer sequences. While neural machine translation (NMT) models have shown promise, they typically struggle to generalize to new, unseen sequences because the randomly generated training data doesn't adequately represent the distribution of real-world target sequences. This "domain gap" is a major hurdle. The paper specifically addresses Domain Adaptation on Symbolic Regression of Integer Sequences (DASRIS), a problem that has been largely unexplored, especially for integer sequences where the "formula space" is vast and complex, unlike simpler domains like image classification.

Methods

The core of the proposed method, Progressive Self-Learning (PSL), involves two main phases:

  • Source Data Construction with Initial Term of Target Domain (ITTD): Instead of purely random data, the source dataset is augmented with initial terms from the target sequences. This helps to bridge the distribution gap between the source and target domains. The method focuses on recurrence formulas, which are more general and can capture patterns that might not have a simple closed-form expression.
  • Self-Learning Loop: This iterative process refines the model's ability to learn the target sequence-formula distribution.
  • Model Learning: An NMT (Transformer) model is trained to map sequences to formulas.
  • Candidate Formula Generation: The trained model uses beam search to generate multiple potential formulas for target sequences.
  • Formula Verification: Generated formulas are checked for correctness by predicting sequence terms and comparing them to the actual target sequence.
  • Data Augmentation: Verified correct formulas are added back into the training data for the next iteration, progressively teaching the model about the target domain. The selection of formulas for retraining prioritizes those with fewer operators and lower recurrence degrees (Occam's Razor principle).

Datasets

  • Source Domain Data: Generated using recurrence formulas and ITTD. The paper details parameters for generating both ordinary and linear recurrence formulas.
  • Target Domain Data: Sequences from the Online Encyclopedia of Integer Sequences (OEIS). Two specific test sets were created:
  • OEIS Easy25: First 10,000 "easy" sequences with at least 25 terms.
  • OEIS Easy35: First 10,000 "easy" sequences with at least 35 terms.

Key Insights and Ideas

  • Bridging the Domain Gap is Crucial: The paper strongly emphasizes that simply training on random data is insufficient for SRIS. Actively incorporating information from the target domain (via ITTD and self-learning) is key to achieving good generalization.
  • Iterative Refinement is Powerful: The self-learning loop, where the model learns from its own successful predictions on target data, is the engine for progressive improvement. This allows the model to gradually "understand" the target domain's patterns.
  • Simplicity as a Guiding Principle: Prioritizing formulas with fewer operators and lower recurrence degrees during the self-learning process aligns with Occam's Razor and helps discover more fundamental and generalizable patterns.
  • The Value of Recurrence Formulas: The paper highlights that recurrence formulas are a more robust and general approach for SRIS compared to general formulas, as they can capture patterns that might be difficult to express otherwise.

Key Results

  • State-of-the-Art Performance: PSL significantly outperforms existing methods, including function-based approaches (FSF, FLR) and a baseline deep symbolic regression (DSR) method. For example, on OEIS Easy25 with $n_p=1$ (predicting one term), PSL achieved 53.1% accuracy, compared to DSR's 33.4%.
  • Discovery of New Formulas: The method successfully discovered numerous formulas for OEIS sequences, including some that were previously unknown or difficult to find.
  • Scalability: The self-learning process discovered over 9500 formulas during training, culminating in over 12,000, demonstrating its ability to handle a large number of sequences.
  • Longer Sequences Aid Learning: Performance generally improved when using longer sequences (OEIS Easy35 vs. Easy25), suggesting that more data points help the model better capture underlying rules.

Limitations and Future Work

  • Single Model for All Sequences: The current PSL uses a single model for all sequences, which can be challenging for capturing highly diverse formula patterns.
  • Future Work: The authors suggest investigating a "mixture of expert models" to better identify and handle various formula patterns. This could involve specialized models for different types of sequences or formulas.

Summary updated

BibTeX
@inproceedings{zhu2025progressive,
  author = {Yaohui Zhu and Kaiming Sun and Zhengdong Luo and Lingfeng Wang},
  title = {{Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i2.32162},
}
Figure