Classifier-based constraint acquisition
Loading...
Files
Published version
Date
2021-04-17
Authors
Prestwich, Steven D.
Freuder, Eugene C.
O'Sullivan, Barry
Browne, David
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Published Version
Abstract
Modeling a combinatorial problem is a hard and error-prone task requiring significant expertise. Constraint acquisition methods attempt to automate this process by learning constraints from examples of solutions and (usually) non-solutions. Active methods query an oracle while passive methods do not. We propose a known but not widely-used application of machine learning to constraint acquisition: training a classifier to discriminate between solutions and non-solutions, then deriving a constraint model from the trained classifier. We discuss a wide range of possible new acquisition methods with useful properties inherited from classifiers. We also show the potential of this approach using a Naive Bayes classifier, obtaining a new passive acquisition algorithm that is considerably faster than existing methods, scalable to large constraint sets, and robust under errors.
Description
Keywords
Constraint acquisition , Classifier , Bayesian , Boolean satisfiability
Citation
Prestwich, S. D., Freuder, E. C., O’Sullivan, B. and Browne, D. (2021) 'Classifier-based constraint acquisition', Annals of Mathematics and Artificial Intelligence, (20 pp). doi: 10.1007/s10472-021-09736-4