Composing Biases by Using CP to Decompose Minimal Functional Dependencies for Acquiring Complex Formulae
Ramiz Gindullin, Nicolas Beldiceanu, Jovial Cheukam-Ngouonou, Rémi Douence, Claude-Guy Quimper
Abstract
Given a table with a minimal set of input columns that functionally determines an output column, we introduce a method that tries to gradually decompose the corresponding minimal functional dependency (mfd) to acquire a formula expressing the output column in terms of the input columns. A first key element of the method is to create sub-problems that are easier to solve than the original formula acquisition problem, either because it learns formulae with fewer inputs parameters, or as it focuses on formulae of a particular class, such as Boolean formulae; as a result, the acquired formulae can mix different learning biases such as polynomials, conditionals or Boolean expressions. A second key feature of the method is that it can be applied recursively to find formulae that combine polynomial, conditional or Boolean sub-terms in a nested manner. The method was tested on data for eight families of combinatorial objects; new conjectures were found that were previously unattainable. The method often creates conjectures that combine several formulae into one with a limited number of automatically found Boolean terms.
BibTeX
@article{Gindullin_Beldiceanu_Cheukam-Ngouonou_Douence_Quimper_2024, title={Composing Biases by Using CP to Decompose Minimal Functional Dependencies for Acquiring Complex Formulae}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/28641}, DOI={10.1609/aaai.v38i8.28641}, abstractNote={Given a table with a minimal set of input columns that functionally determines an output column, we introduce a method that tries to gradually decompose the corresponding minimal functional dependency (mfd) to acquire a formula expressing the output column in terms of the input columns. A first key element of the method is to create sub-problems that are easier to solve than the original formula acquisition problem, either because it learns formulae with fewer inputs parameters, or as it focuses on formulae of a particular class, such as Boolean formulae; as a result, the acquired formulae can mix different learning biases such as polynomials, conditionals or Boolean expressions. A second key feature of the method is that it can be applied recursively to find formulae that combine polynomial, conditional or Boolean sub-terms in a nested manner. The method was tested on data for eight families of combinatorial objects; new conjectures were found that were previously unattainable. The method often creates conjectures that combine several formulae into one with a limited number of automatically found Boolean terms.}, number={8}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Gindullin, Ramiz and Beldiceanu, Nicolas and Cheukam-Ngouonou, Jovial and Douence, Rémi and Quimper, Claude-Guy}, year={2024}, month={Mar.}, pages={8030-8037} }