Overcoming Over-Fitting in Constraint Acquisition via Query-Driven Interactive Refinement

Vasileios Balafas, Dimos Tsouros, Nikolaos Ploskas, Kostas Stergiou · 2025

Read Overcoming Over-Fitting in Constraint Acquisition via Query-Driven Interactive Refinement by Vasileios Balafas, Dimos Tsouros, Nikolaos Ploskas, Kostas Stergiou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24489.txt.

Introduction

Learning a constraint model from examples can overfit, inventing global rules that the true model never had. Vasileios Balafas and 3 co-authors built a hybrid acquisition framework to fight that failure. Passive learning drafts candidate constraints first. A query-driven phase then refines them, using confidence scores seeded by machine learning priors to hunt the over-fitted ones.

A subset exploration step rescues valid parts from rejected candidates, and a final active phase ensures completeness. On diverse benchmarks, the interactive refinement proved crucial for coverage and accuracy from few examples. Query counts stayed manageable. The design targets robust modeling where data is scarce.

Catalog record

CREATORVasileios Balafas, Dimos Tsouros, Nikolaos Ploskas, Kostas Stergiou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24489

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Overcoming Over-Fitting in Constraint Acquisition via Query-Driven Interactive Refinement Vasileios Balafas, Dimos Tsouros, Nikolaos Ploskas, Kostas Stergiou Abstract 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. \catchline keywords {history} 1 Introduction Constraint Programming (CP) is a powerful paradigm for solving combinatorial problems across diverse applications [ rossi2006handbook , baptiste2001constraint , lin2013csp ] . However, its adoption is often hindered by the modeling bottleneck [ freuder2014grand , bessiere2016new , osullivan2010automated ] : translating real-world requirements into a correct and efficient CP model requires significant expertise and time. This challenge is especially acute when dealing with expressive global constraints such as AllDifferent or Sum [ VanHoeve2006 ] , where an incorrect formulation can cripple a model. Constraint Acquisition (CA) [ Bessiere2017 , DeRaedt_Passerini_Teso_2018 ] aims to automate the modeling process by learning the target constraint network from examples or user interaction. CA approaches range from passive learning [ bessiere2005sat , BelSim ] , which infers constraints from a fixed dataset but is prone to over-fitting due to the typically small number of examples [ balafas2024impact ] , to active learning , which queries an oracle to resolve ambiguities but can suffer from a high query burden [ bessiere2013constraint , tsouros2018efficient ] . Hybrid methods [ balafashybrid ] combine these, but they also lack mechanisms to specifically address the over-fitting of (global) constraints identified in the initial passive phase. Over-fitting is a critical challenge that arises when passive learning identifies constraints that are consistent with the few available examples but are overly specific, capturing coincidental patterns rather than true problem rules. Accepting such constraints as part of the model, or passing them to an active learning phase, in the context of hybrid CA, can lead to bad models or inefficient refinement, while discarding them risks losing valuable structural information. This study introduces a framework to systematically identify and refine such over-fitted global constraints, leveraging the speed of initial pattern detection while handling the resulting inaccuracies through targeted oracle interaction. Our research addresses the following questions: 1. RQ1: How can potentially over-fitting sets of global constraints be systematically evaluated and refined to converge towards the true constraints, preserving valid structures while eliminating spurious generalizations? 2. RQ2: Which interactive strategies for query generation, confidence management, and resource allocation can most efficiently guide this refinement process, minimizing the interaction cost for the oracle? To address these questions, we have developed an enhanced hybrid CA framework. The process begins with (1) a passive learning phase that generates initial candidate (global) constraints from a few positive examples. The core of our method is (2) a Query-Driven Interactive Refinement stage. This phase vets each candidate constraint by assigning it a machine learning-based confidence score, and then posts targeted queries to an oracle. Based on the feedback, if a candidate constraint is rejected as over-fitted, a Subset Exploration mechanism attempts to recover valid sub-constraints (i.e., similar constraints on smaller sets of variables). Finally, (3) the active learning phase learns any remaining simple constraints to complete the model. Our primary contributions, which enable this CA process, include the following: 1. A three-phase hybrid architecture featuring a central Query-Driven Interactive Refinement phase that explicitly targets the rejection or refinement of over-fitted global constraints. 2. A specialized Subset Exploration mechanism that recovers valid substructures from rejected global constraints by modifying their scope while preserving parameters, thereby preventing information loss. 3. The integration of machine learning-based prior probability estimation and a Bayesian confidence framework to provide information about the probable existence of the learned constraints in the model, and principled evidence-based belief updates during interactive refinement. Empirical validation on diverse benchmarks demonstrated that our framework achieves high accuracy and target model coverage from limited examples with manageable query complexity, highlighting the crucial role of the interactive refinement phase in overcoming over-fitting. The remainder of this paper details our methodology (Section 4 ) after reviewing background and related work (Section 2 - 3 ), presents our experimental evaluation (Section - ), and concludes with future directions (Section ). 2 Background 2.1 Constraint Satisfaction Problems (CSPs) A Constraint Satisfaction Problem (CSP) [ rossi2006handbook ] is formally defined as a triple \mathcal{P}=(X,D,\mathcal{C}) , where X=\{x_{1},\ldots,x_{n}\} is a set of variables; D=\{D(x_{1}),\ldots,D(x_{n})\} is a set of corresponding domains of possible values; and \mathcal{C}=\{c_{1},\ldots,c_{m}\} is a set of constraints. Each constraint c_{j}\in\mathcal{C} is a pair (\text{vars}(c_{j}),\text{rel}(c_{j})) , where its scope \text{vars}(c_{j})\subseteq X is the set of variables it applies to, and its relation \text{rel}(c_{j}) specifies the allowed combinations of values for those variables. The number of variables in the scope, |\text{vars}(c_{j})| , represents the constraint’s arity . An assignment maps variables to values from their domains; it is complete if all variables in X are assigned, and partial otherwise. An assignment satisfies a constraint if the combination of values for the variables in its scope is allowed by its relationship. A solution to CSP is a complete assignment that satisfies all constraints in \mathcal{C} . The set of all solutions is denoted as \text{sol}(\mathcal{C}) . 2.2 Global Constraints Global constraints represent complex combinatorial substructures involving an arbitrary number of variables (as opposed to fixed-arity constraints such as binary ones) and are crucial for modeling expressiveness and solver efficiency [ VanHoeve2006 , beldiceanu2007global ] . Our work focuses on acquiring models that include such constraints with the following examples: • AllDifferent (S) : Requires all variables in set S to take distinct values. • Sum (S,\bowtie,b) : Requires the sum of values for variables in S to satisfy a relation \bowtie\in\{=,\neq,<,\leq,>,\geq\} with a bound b . • Count (S,v,\bowtie,k) : Requires the number of variables in S assigned value v to satisfy a relation \bowtie with a count k . 2.3 Constraint Acquisition Constraint Acquisition (CA) aims to automatically learn a target constraint network \mathcal{C}_{T} given a vocabulary (X,D) , a language of possible constraint types \Gamma , and a source of information [ bessiere2013constraint ] . The set of all possible constraints that can be formed from \Gamma over (X,D) is constraint bias B . The information source can be a set of positive examples (solutions) E^{+} and negative examples (non-solutions) E^{-} , or an oracle O that can classify assignments. The goal is to learn a network \mathcal{C}_{L}\subseteq B such that its solution set is equivalent to the target’s, i.e., \text{sol}(\mathcal{C}_{L})=\text{sol}(\mathcal{C}_{T}) . It is assumed that \mathcal{C}_{T} is representable

Read the complete text