Overcoming Over-Fitting in Constraint Acquisition via Query-Driven Interactive Refinement
This addresses the bottleneck of manual modeling in Constraint Programming for data-limited scenarios, representing a substantial but incremental advancement.
The paper tackles the problem of over-fitting in Constraint Acquisition (CA) when trained on limited data, which leads to spurious constraints. Their hybrid framework combining passive learning, query-driven interactive refinement, and active learning achieves high model coverage and accuracy with manageable query complexity.
Manual modeling in Constraint Programming is a substantial bottleneck, which Constraint Acquisition (CA) aims to automate. However, passive CA methods are prone to over-fitting, often learning models that include spurious global constraints when trained on limited data, while purely active methods can be query-intensive. We introduce a hybrid CA framework specifically designed to address the challenge of over-fitting in CA. Our approach integrates passive learning for initial candidate generation, a query-driven interactive refinement phase that utilizes probabilistic confidence scores (initialized by machine learning priors) to systematically identify over-fitted constraints, and a specialized subset exploration mechanism to recover valid substructures from rejected candidates. A final active learning phase ensures model completeness. Extensive experiments on diverse benchmarks demonstrate that our interactive refinement phase is crucial for achieving high target model coverage and overall model accuracy from limited examples, doing so with manageable query complexity. This framework represents a substantial advancement towards robust and practical constraint acquisition in data-limited scenarios.