Abstract:
Constraint acquisition (CA) methods aim to learn constraint satisfaction problems (CSPs) from data, thus automating the difficult and error-prone task of constraint modelling. Most CA methods learn CSPs of a certain size from examples of that size, for example an 8-queens CSP from 8-queens solutions. A few methods can learn a CSP from solutions of other sizes, or learn a generalised CSP for all sizes, which is more challenging but also more useful in practice. This paper describes a new approach to learning a CSP: extrapolation from learned CSPs of other sizes. This has the advantage that the training CSPs can be learned by any convenient CA method, thus potentially handling positive-only, negative-only, positive-negative, noisy or unlabelled data. We model the problem as classification, and show that a symbolic classifier based on genetic programming outperforms alternatives such as random forests and deep learning.
