Technical Summary: Deep Variational Inference Symbolic Regression (DVISR)

Problem Statement

Symbolic Regression (SR) aims to discover explicit, interpretable mathematical relationships between independent and dependent variables without assuming a functional form a priori. While traditional methods like Genetic Programming (GP) and Deep Symbolic Regression (DSR) successfully identify single best-fitting expressions, they lack the ability to infer a probability distribution over candidate models. This limitation prevents the quantification of uncertainty, which is critical when dealing with noisy or limited real-world data.

Existing Bayesian approaches, such as Markov-chain Monte Carlo (MCMC), can accurately sample from the posterior distribution but struggle with scalability in high-dimensional spaces and are computationally slower than variational methods. Conversely, Variational Inference (VI) offers faster, scalable alternatives but has seen limited application in SR. Prior attempts at variational SR have been restricted to polynomial neural networks or subsets of the expression space due to computational intractability. There is a need for a scalable, variational Bayesian approach that infers posteriors over both expression trees and their associated constants.

Methodology

The authors propose Deep Variational Inference Symbolic Regression (DVISR), a variational Bayesian extension of the Deep Symbolic Regression (DSR) algorithm. DVISR utilizes a Recurrent Neural Network (RNN) to generate symbolic expressions and employs the REINFORCE policy gradient method for optimization.

Key Architectural and Algorithmic Modifications

1. Distribution over Constants: Unlike DSR, which optimizes constants downstream via separate procedures, DVISR extends the RNN output to include parameters (mean and variance) for normal distributions over constant values. When a constant token is sampled, its value is drawn from this learned distribution.
2. Enhanced Input Context: To assist the RNN in sampling, the network receives the previous token, parent, and sibling tokens (if they exist) as inputs, along with the values of previously sampled constants. This addresses limitations in DSR where the network might not "see" all previous tokens.
3. Reward Function and Objective:
   • DSR: Maximizes a reward based on the Normalized Root-Mean-Squared Error (NRMSE) bounded by a squashing function to find a single best model.
   • DVISR: Replaces the NRMSE reward with the integrand of the Evidence Lower Bound (ELBO). The reward function is defined as:
     $$R(f) = \log \mathcal{L}_\theta(f|X, y) + \log p(f) - \log q_\phi(f)$$
     Where $\mathcal{L}_\theta$ is the likelihood, $p(f)$ is the prior, and $q_\phi(f)$ is the variational distribution.
   • By maximizing this reward via REINFORCE, DVISR indirectly minimizes the Kullback-Leibler (KL) divergence between the variational distribution $q_\phi(f)$ and the true posterior $p(f|X, y)$.
4. Likelihood Calculation: The likelihood of an expression $f$ is calculated as the product of the likelihoods of its tokens and constants, conditioned on all previously sampled tokens and constants.

Key Contributions

1. Novel Algorithm: Introduction of DVISR, the first algorithm to perform variational inference over the full symbolic regression space, including both expression trees and continuous constant parameters.
2. Posterior Recovery: Demonstration that DVISR can correctly converge to the true posterior in simple settings, both with and without constant tokens.
3. Scalability Analysis: An examination of how DVISR performance degrades as the size of the expression space increases, identifying the limits of the current architecture.

Experimental Results

The authors conducted experiments to validate the convergence and scalability of DVISR.

1. Convergence to True Posterior (No Constants)

In simple experiments using data generated from $y=x_0^2$, $y=x_0$, and $y=0.5$ with a restricted token library, the model space was small and finite.

• Results: The ELBO converged to the log of the evidence, and the KL divergence approached zero.
• Validation: Table 1 shows that the median variational probabilities matched the true posterior values to eight decimal places across 10 runs.

2. Convergence with Constants

Experiments included a constant token ($c$) in the library, allowing for expressions like $x_0 \cdot c$.

• Method: The true posterior was calculated by marginalizing out constants using a numerical integrator.
• Results: Table 2 demonstrates that the variational distribution over expression trees converged to the exact true posterior (marginalized over constants) to eight decimal places.

3. Scalability

The authors varied the maximum expression size from 1 to 12 tokens to test scalability.

• Findings: As the maximum expression size increased, the estimated KL divergence between the true posterior and the variational distribution increased.
• Limitation: Experiments beyond size 12 were not performed due to the computational difficulty of calculating the evidence at that scale. This indicates that while DVISR works for small spaces, performance degrades as the search space expands.

Significance and Claims

The paper positions DVISR as a significant step toward scalable Bayesian symbolic regression that provides uncertainty quantification over full symbolic models.

• Interpretability and Uncertainty: By inferring a posterior distribution rather than a single point estimate, DVISR addresses the "black-box" nature of some regression models and accounts for noise and data limitations.
• Advancement over MCMC: It offers a faster alternative to MCMC for Bayesian SR, which is typically slow and struggles with high dimensions.
• Modest Scope: The authors acknowledge current limitations, including small expression sizes, low numbers of independent variables, and the absence of real-world datasets. They do not claim immediate superiority on complex, real-world problems but argue that DVISR establishes a foundational framework.
• Future Directions: The paper suggests that future work could improve scalability through hyperparameter sweeps, advanced architectures (e.g., Transformers), or more sophisticated reinforcement learning algorithms (e.g., PPO).