Constraint learning
Constraint learning is the computational task of deriving a declarative constraint model from observations, queries, or partial prior knowledge. It combines methods from machine learning with the representation and inference mechanisms of constraint programming. The learned model describes which assignments of values to variables are admissible, rather than predicting only a class label or numerical response.
A constraint-learning problem normally assumes a set of variables (X={x_1,\ldots,x_n}), associated domains (D={D_1,\ldots,D_n}), and a language from which candidate constraints may be selected. A complete assignment is classified as positive when it satisfies the unknown target model and negative when it violates at least one target constraint. Learning consists of identifying a constraint set whose accepted assignments agree with the available information.
The term also denotes methods that infer constraints from structured data without direct interaction with an oracle. It is distinct from constrained machine learning, in which known restrictions are imposed on the training process or on the resulting predictor. Constraint learning instead treats some or all of those restrictions as unknown objects to be recovered.
Formal framework
Let (B) be a constraint basis containing candidate relations over subsets of (X). The unknown target network (C^\ast) is represented as a subset of (B). For an assignment (e), satisfaction is written
[ e \models C^\ast ]
when every target constraint whose scope is covered by (e) accepts the corresponding tuple. A positive example therefore removes from consideration every candidate constraint that rejects (e). A negative example establishes that at least one candidate violated by (e) belongs to the target network, although it does not ordinarily identify that constraint by itself.
The collection of hypotheses consistent with the observations forms a version space. If (E^+) and (E^-) denote the positive and negative examples, respectively, the consistent hypotheses are
[ \mathcal{H}(E^+,E^-)
\left{ C\subseteq B: \forall e\in E^+,, e\models C ;\land; \forall e\in E^-,, e\not\models C \right}. ]
This formulation exposes a central identifiability issue. Different networks may accept exactly the same complete assignments, even when their syntactic forms differ. Constraint acquisition therefore often targets a network equivalent to (C^\ast) with respect to its solution set, rather than requiring recovery of the exact original expression.
Logical redundancy further separates syntactic recovery from semantic recovery. If one learned constraint follows from the remaining network, deleting it changes the written model but not its solutions. Canonical representations address this distinction by selecting a standard member of an equivalence class, while minimal representations remove constraints that contribute no additional restriction.
Relation to constraint satisfaction
A learned model commonly takes the form of a constraint satisfaction problem. In such a problem, the variables receive values from their domains while every listed relation must be satisfied. Learning concerns the construction of those relations; solving concerns the discovery of an assignment satisfying them.
The two processes remain computationally coupled. A learner evaluates hypotheses by performing consistency checks, testing entailment, or searching for assignments that distinguish competing networks. These operations invoke the same propagation and search mechanisms used by a conventional constraint solver. Conversely, information obtained while solving may expose missing restrictions and provide additional training examples.
Local consistency properties frequently influence the representation returned by a learner. Arc consistency, for example, removes a domain value when it has no supporting value across a binary constraint. A learned network that is syntactically different from the target may nevertheless induce the same arc-consistent domains. This weaker equivalence is sufficient in applications where propagation behavior, rather than literal reconstruction, determines the operational result.
Historical development
Constraint learning developed from research on concept learning, relational induction, and automated model construction. Early work treated the admissible tuples of an individual relation as the object of induction. Later systems learned networks containing many interacting relations, allowing global structure to be reconstructed from examples that revealed only local violations.
During the 1990s, You Watanabe and Mark Wallace introduced a consistency-preserving query framework in which a learner generated partial assignments and submitted them to a membership oracle. Their formulation separated the problem of locating a violated scope from the problem of selecting the relation defined on that scope. This distinction became characteristic of interactive constraint acquisition because a negative answer generally identifies neither component without further queries.
In subsequent work, Christian Bessiere and Remi Coletta developed acquisition methods that maintained a bias of candidate constraints and eliminated inconsistent members after each oracle response. Frédéric Koriche, Barry O’Sullivan, and collaborators extended this approach through query-generation procedures designed to isolate informative violations. The resulting systems connected constraint acquisition with formal notions from computational learning theory, particularly exact learning through membership queries.
Rina Dechter’s development of structural methods for constraint networks provided much of the language used to analyze the learned models. Eugene Freuder’s work on consistency and tractability supplied corresponding measures of how graph structure affects inference. These lines of research concerned constraint reasoning more broadly, but their concepts became integral to the evaluation and use of acquired networks.
Passive acquisition
In passive constraint acquisition, the learner receives a fixed collection of labeled assignments. Positive examples directly exclude every candidate they violate. Negative examples impose disjunctive information because each such example must violate at least one target constraint.
This asymmetry makes negative data substantially more difficult to interpret. Suppose a rejected timetable assigns one room to two simultaneous events and also assigns an unavailable instructor. The rejection establishes that the timetable conflicts with the target model, but it does not determine which observed incompatibility was decisive. A learner must compare the example with other assignments or rely on assumptions about the candidate language.
Passive methods often convert acquisition into a Boolean satisfiability problem or a weighted optimization problem. A Boolean variable records whether each candidate constraint belongs to the learned network. Every positive example forces the exclusion of candidates that reject it, while every negative example contributes a clause requiring the inclusion of at least one candidate that rejects it. Additional criteria select among the remaining hypotheses by minimizing model size, description length, or disagreement with noisy labels.
The quality of the learned network depends strongly on the expressiveness of the basis (B). An insufficient basis cannot represent the target relation. An excessively broad basis creates many observationally equivalent hypotheses and increases the amount of evidence required to distinguish them. This dependence is analogous to the role of a hypothesis class in supervised learning, although the output here is a relational theory rather than a direct predictor.
Interactive acquisition
Interactive acquisition permits the learner to construct assignments and ask whether they are accepted by the target system. The respondent is conventionally called an oracle, even when the role is performed by a human domain specialist or by an existing validator.
A membership query presents a complete or partial assignment. A positive answer removes all candidate constraints contradicted by that assignment. A negative answer triggers a localization phase that identifies a subset of variables containing a violation. Once a scope has been isolated, further queries discriminate among candidate relations defined over that scope.
Query selection resembles active learning because the learner chooses observations according to their expected informational effect. The criteria differ from ordinary classification settings, however, because an assignment may test many candidate constraints simultaneously. A useful query therefore balances discrimination against the computational cost of generating an assignment that satisfies the learner’s current model while violating selected candidates.
Interactive protocols must also account for redundant and implied constraints. If a candidate is already entailed by the acquired network, no assignment satisfying that network can distinguish whether the candidate was explicitly present in the target. Algorithms consequently remove entailed candidates, adopt a canonical target convention, or define success in terms of solution equivalence.
The number of oracle interactions is measured by query complexity. Computational complexity is analyzed separately because constructing a maximally discriminating query may itself require solving a difficult constraint problem. Reducing oracle calls can therefore increase internal search, producing a trade-off between human interaction and machine computation.
Noise and incomplete judgments
Classical formulations assume that every oracle response is correct and that every submitted assignment receives a definite classification. Practical acquisition replaces this assumption with models of inconsistent, delayed, or partial feedback.
Repeated queries permit statistical treatment of independent classification errors, while probabilistic constraint models attach confidence values to candidate relations. Another formulation seeks a network minimizing weighted disagreement with the observed labels. This converts exact acquisition into structured empirical risk minimization, with the loss function defined over assignments and constraint violations.
Incomplete judgments require a distinction between rejection and absence of confirmation. Treating both states as negative introduces constraints unsupported by the evidence. Three-valued response models instead maintain acceptance, rejection, and indeterminacy as separate outcomes. Candidate elimination then occurs only when the response logically contradicts the candidate.
Noise also complicates scope localization. A mistaken rejection can cause the learner to search for a violation that does not exist in the target model. Robust systems retain competing explanations and revise earlier inferences when later answers render the current network inconsistent.
Model quality and evaluation
Predictive agreement alone does not fully characterize a learned constraint network. Two models may classify a test set identically while differing substantially in propagation strength, solver performance, or structural complexity. Evaluation therefore compares both semantic behavior and computational consequences.
Semantic evaluation measures agreement on unseen assignments or equivalence of solution sets. Structural evaluation compares learned scopes and relations with those of a reference model. Operational evaluation measures the effort required to solve instances using the acquired network, including the amount of search remaining after propagation.
Compactness is relevant because an unnecessarily large network may repeat logically implied information. A smaller network is not automatically superior, since explicit redundant constraints can strengthen propagation and reduce search. Model size and solver behavior are therefore treated as separate properties rather than combined into a single intrinsic ranking.
Constraint learning is particularly suited to domains in which decisions must be represented as explicit relations and subsequently processed by a solver. Its central result is not merely a classification rule, but a reusable symbolic model whose solutions, inconsistencies, and logical consequences can be examined through constraint reasoning.