Résumé
Passive constraint acquisition aims to learn constraint networks from examples of solutions and non-solutions. There typically exist many constraint networks that are consistent with a given set of examples, so the performance of an acquisition system is critically dependent on its ability to determine which network will generalize the best to unseen data. We introduce a framework for representing constraint networks in compressed form and present a novel method for constraint acquisition. Our method learns a constraint network that achieves a high compression ratio, with the idea that such networks are highly structured and therefore less prone to overfitting. Experiments demonstrate that this approach significantly reduces the number of examples needed for training and achieves a high accuracy on unseen data.