Composing Biases by Using CP to Decompose Minimal Functional Dependencies for Acquiring Complex Formulae

• Main Authors: Gindullin, Ramiz, Beldiceanu, Nicolas, Cheukam-Ngouonou, Jovial, Douence, Rémi, Quimper, Claude-Guy
• Format: Conference Proceeding
• Language: English
• ISSN: 2159-5399; 2374-3468
• DOI: 10.1609/aaai.v38i8.28641

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.