Research map / Architectures and efficiency / RNNs and normalization
Composing Biases by Using CP to Decompose Minimal Functional Dependencies for Acquiring Complex Formulae
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Decomposes minimal functional dependencies in tables with CP-based sub-problem analysis to acquire complex formulae that combine polynomial, conditional and Boolean sub-terms recursively for combinatorial conjecture discovery.
Problem
Acquiring complex formulae that express an output column as a function of a minimal set of input columns (minimal functional dependency) when a single learning bias (polynomial, conditional, Boolean) is insufficient.
Approach
Decompose the formula into simpler sub-terms (sum with a 0-1 term, isolating a parameter with a unary function, conditional splitting) by analysing the table's minimal functional dependency with CP, and apply the decomposition recursively to combine learning biases in a nested manner.
Key results
- The 2nd version (with decompositions) found conjectures for 17255 secondary/output parameters versus 16078 for the 1st version, a 7% increase over all tables.
- Conjectures using input parameters only rose by 14% with decompositions.
- In the 2nd version, 2857 parameters (16.5%) had conjectures using decompositions (6)-(9); 26% of these combined several decompositions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add decompositions (6)–(9) to biases (i)–(iii) | Formula acquisition tool · 4378 tables | parameters with acquired conjectures: 16078 -> 17255 | Helped |
| Add decompositions (6)–(9) to biases (i)–(iii) | Formula acquisition tool · 4378 tables | input-only parameters with acquired conjectures: 9141 -> 10384 | Helped |
| Add decompositions (6)–(9) to biases (i)–(iii) | Formula acquisition tool · 4378 tables | acquired conjectures: 21497 -> 23747 | Helped |
| Add decompositions (6)–(9) to biases (i)–(iii) | Formula acquisition tool · 4378 tables | sharp-bound conjectures: +6% | Helped |
| Add decompositions (6)–(9) to biases (i)–(iii) | Formula acquisition tool · 4378 tables | acquisition time (hours): 5888 -> 25053 | Hurt |
Surprising findings
- Acquisition time increased substantially: 25053 hours for the 2nd version versus 5888 hours for the 1st version.
Limitations
- Conditional decomposition is not applied recursively because it was too time-consuming.
- Decomposition makes acquisition much slower (about 4x total time).
- Some conjectures found were invalidated (54 for the 2nd version).
Experimental setup
Datasets: Gindullin et al. 2023 combinatorial object bound tables (about 12 GB)
Benchmarks: Gindullin et al. 2023 combinatorial object tables (4378 tables, 21797 parameters)
Metrics: number of parameters with acquired conjectures number of conjectures acquisition time invalidated conjectures
Baselines: 1st version of acquisition tool (biases (i)-(iii) only)
Builds on: Beldiceanu et al. 2022 CP conjecture system Udrescu et al. AI Feynman
Closest papers by meaning
- Unsupervised Discovery of Formulas for Mathematical Constants (NeurIPS 2024 · similarity 0.84)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.84)
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.83)
- An Approximate Skolem Function Counter (AAAI 2024 · similarity 0.83)
- MUSTARD: Mastering Uniform Synthesis of Theorem and Proof Data (ICLR 2024 · similarity 0.82)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.