TL;DR
This paper introduces a novel method for automatically discovering complex mathematical formulas from data. By decomposing the problem into smaller, manageable sub-problems and leveraging constraint programming, the authors can synthesize formulas that combine different types of mathematical expressions, leading to the discovery of previously unattainable conjectures.
What Problem Does This Paper Address?
The automatic acquisition of mathematical formulas from data is a challenging problem, especially when the desired formulas are complex and involve a wide range of mathematical constructs (e.g., polynomials, conditionals, Boolean logic). Existing methods often rely on predefined grammars that limit the types of formulas they can discover, or they struggle with the combinatorial explosion of possibilities when trying to learn complex expressions all at once. This paper addresses the gap in effectively combining different "learning biases" (assumptions about the form of the target formula) to acquire more sophisticated and nested formulas.
Methods
The core of the proposed method is a recursive decomposition technique. Instead of trying to learn a single, complex formula, the approach breaks it down into simpler sub-problems. This decomposition is guided by analyzing minimal functional dependencies (MFDs) within the data. The key ideas are:
- Decomposition into Sub-problems: The method identifies parts of a formula that can be learned independently, potentially using different learning biases. This makes each sub-problem easier to solve.
- Recursive Application: These sub-problems can themselves be decomposed, allowing for the creation of nested formulas where, for example, a conditional expression might contain a polynomial term, which in turn contains a Boolean expression.
- Constraint Programming (CP): CP is used to solve these sub-problems, efficiently finding coefficients and validating candidate formula structures.
- Four Decomposition Types: The paper formalizes four types of decompositions:
- Adding a Boolean Expression: Decomposing a function into a primary function and a 0-1 error term, useful for approximating bounds.
- Isolating a Parameter: Separating a parameter that only appears in a specific part of the formula.
- Isolating a Parameter with a 0-1 Slack: A generalization of the previous type, introducing a slack variable.
- Introducing a Conditional: Splitting the problem based on a condition, allowing for different formulas in the "then" and "else" branches.
Datasets
The paper evaluates its method on datasets derived from combinatorial objects. These include: DIGRAPH, ROOTED TREE, ROOTED FOREST, ROOTED FOREST2, PARTITION, PARTITIONO, STRETCH, and CYCLIC STRETCH. The data consists of tables where input parameters functionally determine an output parameter (e.g., a sharp lower or upper bound). The authors mention that their benchmark dataset represents 12 GB of data.
Key Insights and Ideas
- Decomposition is Key: The most significant insight is that breaking down a complex formula acquisition problem into smaller, composable sub-problems is more effective than trying to learn the entire formula at once.
- Combining Biases: The method elegantly handles the combination of different learning biases (polynomial, conditional, Boolean) in a nested fashion, which was a major limitation of prior work.
- Constraint Programming as a Solver: Leveraging CP is crucial for efficiently searching for candidate sub-formulas and determining their coefficients.
- Discovering Non-Obvious Conjectures: The decomposition approach enabled the discovery of new, non-trivial conjectures that were previously unattainable with simpler methods.
Key Results
The paper presents experimental results comparing a baseline acquisition tool (using biases (i)-(iii)) with their enhanced version (using biases (i)-(iii) plus the four decomposition types).
- The enhanced version found conjectures for 17255 secondary or output parameters, compared to 16078 for the baseline.
- The enhanced version expressed 14% more conjectures using only input parameters, aligning with a stated goal.
- The enhanced version found 6% more conjectures related to sharp bounds (types II and IV).
- For 16.5% of the parameters, the enhanced version used decompositions (6)-(9), with 26% of these using multiple decompositions within a single conjecture.
- The method successfully discovered and proved four new conjectures (Conj. (1)-(4)) that were outside the scope of the baseline method.
Limitations and Future Work
- Computational Cost: While the decomposition approach is powerful, the paper notes that applying the conditional decomposition recursively proved to be "very time-consuming."
- Future Work: The authors suggest using the acquired conjectures to synthesize efficient filtering algorithms, as a lack of sharp bounds is identified as a weakness in CP. They also mention that the acquired conjectures can be used to prove their validity.
Summary updated