Zero-error rule induction using a memetic algorithm

Rule induction in traditional machine learning (ML) concentrates on finding rules that minimize error to produce high accuracy through a trade-off between sensitivity and specificity. But what if the machine learning task is to produce minimal length rules with zero error (the error-free ML optimization problem)? In its most basic form, the problem can be recast as reverse-engineering the syntactically-minimal well-formed formula (wff) that correctly covers all rows of a given Boolean truth table. The main problem for evolutionary approaches to zeroerror rule induction is the design of a suitable fitness function to cope with a search landscape that is not amenable to hillclimbing. In this paper we demonstrate how using the ratio of true to false rows in the truth table can be used as a heuristic to guide a memetic algorithm for exploring and exploiting the search for zero-error, syntactically minimal wffs in randomly generated truth tables for up to 12 variabes. The search depth of candidate solutions is determined by the number of variables in the data and the size of a solution is allowed to increase as long as its coverage improves. Significant differences in solution size were found depending on the ratio of true to false values in the data. The results provide a basis for further formalization and development of zero-error rule induction if ML is to be used confidently in safety critical situations where no error in induced rules is permissible.