Zero-error rule induction using a memetic algorithm
- Resource Type
- Conference
- Authors
- Narayanan, Ajit; Ross, Koz; Johnson, Kenneth
- Source
- 2020 IEEE Symposium Series on Computational Intelligence (SSCI) Computational Intelligence (SSCI), 2020 IEEE Symposium Series on. :647-654 Dec, 2020
- Subject
- Computing and Processing
General Topics for Engineers
Robotics and Control Systems
Signal Processing and Analysis
Memetics
Machine learning
Task analysis
Semantics
Standards
Optimization
Heuristic algorithms
Evolutionary computation
genetic algorithms
memetic algorithms
heuristics
zero-error rule induction
- Language
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.