When a scheduling or puzzle model is learned from examples, the learner is really trying to answer one question: why is a bad assignment bad? Each infeasible assignment fails because it breaks at least one true rule, such as "no nurse works two consecutive night shifts" or "all cells in a row differ." Each feasible assignment keeps every true rule intact. Classical planning research calls this kind of reasoning a causal link: a recorded reason that one step makes another step work, which a good abstraction must keep valid in every instance it is applied to. We propose to learn constraint models by treating every candidate rule, at every level of abstraction, as an "expert" that claims to explain failures. These experts are weighted with Winnow, a classical online learner that multiplies a weight up or down after each mistake instead of adding to it. The number of examples Winnow needs grows only with the logarithm of the number of candidate rules, so the space of rules the learner considers can grow by orders of magnitude while the data it needs grows only a little.
The practical payoff targets the main weakness of current methods that learn general constraint models. Methods that generalize across problem sizes avoid huge rule spaces by restricting their grammar: they enumerate a limited set of rule shapes and then filter them heavily, or they classify candidates using a few hand-built features. Both choices block exactly the expressiveness that is missing, including higher-arity rules, rules whose constants do not come from known problem parameters, and richer symbolic bounds. If the cost of a larger hypothesis space is logarithmic, the grammar can be opened up rather than pruned in advance. We also propose a specific mechanism for abstraction. A rule that holds only in one concrete instance "sleeps" on instances of other sizes. A lifted rule stays awake on every instance and gathers credit across all of them. Abstraction then emerges from how the weights move, without relying on a hand-tuned generalization step.
Core Claim
Target constraint models are conjunctions of a small number $k$ of rule templates drawn from a pool of size $d$. Under this view, "this assignment is infeasible" is a disjunction: some target template is violated. Monotone disjunctions are the setting where Winnow is provably attribute-efficient. Let $v_j(x)\in\{0,1\}$ indicate that candidate template $j$, instantiated on the current instance, is violated by assignment $x$, and let $w_j$ be its weight. The learner predicts "infeasible" when
$$\sum_{j \in A(x)} w_j \, v_j(x) \ \ge\ \theta,$$
where $A(x)$ is the set of templates that apply ("are awake") on the instance containing $x$, and $\theta$ is a threshold. After a mistake, violated templates are multiplied by $\alpha>1$ if the assignment was actually infeasible, or by $1/\alpha$ if it was actually feasible. Standard Winnow analysis bounds the number of mistakes by $O(k\log d)$ plus a term proportional to the number of label errors. This bound comes from tracking the relative entropy between the weights and the target. The sleeping-experts variant replaces $d$ with the effective pool awake on each instance.
The claim we will test is that this learner recovers exact, size-general constraint models with an example count that stays nearly flat as the template pool grows by factors of 100 to 1000. We also expect it to be more robust to label noise than the elimination and tree-based approaches it replaces.
Where This Sits
The causal-link side supplies the abstraction target. Explanation-Based Generalization of Partially Ordered Plans computes, in polynomial time, the weakest constraints under which a plan's causal links survive every ordering. Plan Abstraction Based on Operator Generalization lifts plan steps to the highest ancestor in an operator taxonomy that still preserves those links. Both are deductive and need a complete domain theory, which is the knowledge bottleneck that Acquiring Schemata Through Understanding and Generalizing Plans identifies. We keep their goal, the most general template that still accounts for why failures fail, but replace deduction with credit assignment from examples. This lets the domain theory be overcomplete and noisy rather than exact.
Three constraint-acquisition systems motivate the proposal and also define what it must beat. Learning Constraint Programming Models from Data Using Generate-And-Aggregate (COUNT-CP) enumerates grammar expressions over feasible solutions, keeps bounds observed across examples, and filters away 96.7% of candidates. Its admitted limits are language bias and over-constraint from unrepresentative examples. Generalizing Constraint Models in Constraint Acquisition (GENCON) classifies candidate ground constraints with decision trees and random forests over parameter-relative features, then reads off parameterized specifications. It explicitly cannot handle constants unrelated to problem parameters. Learning to Learn in Interactive Constraint Acquisition uses classifier probabilities to guide an interactive acquisition system, but only within a single fixed instance. None of these maintains weights over lifted templates, and none has a sample-complexity guarantee that tolerates a growing grammar.
The multiplicative side supplies the method. The limits of squared Euclidean distance regularization proves that additive, weight-decay learners stay stuck on irrelevant features in sparse problems, while multiplicative updates suppress them exponentially fast. This is the core reason to prefer Winnow over a perceptron on a large pool. Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain introduces the "specialists" idea: features vote only when active. We reuse it as the sleeping mechanism that separates ground templates from lifted ones. Distributed Multiplicative Weights Methods for DCOP applies multiplicative weights to the assignments inside a single constraint problem and finds that rounding breaks hard constraints. We apply the weights to rules rather than assignments, so the output is a discrete model that a constraint solver enforces exactly. That design sidesteps the rounding failure instead of inheriting it.
Research Program
The first component is the template pool. Starting from the CPMpy-based candidate generators in Dimosts/ActiveConLearn, we generate ground candidate constraints on each training instance. We then add their liftings: the same relation applied over a variable partition (rows, blocks, shifts per day), over a sequence condition, with constants re-expressed as symbolic functions of instance parameters, and, deliberately, with raw constants left unlifted. Every lifting level becomes its own template, so a single ground constraint can appear in the pool as one ground template and several lifted versions of it. Pool size is a controlled experimental variable. We will grow it from GENCON-scale grammars up to arity-3 relations, nested aggregates, and arbitrary constants, reaching roughly $10^6$ templates.
The second component is the learner. Training data are feasible solutions plus infeasible assignments. In batch mode, the infeasible assignments come from local perturbations of feasible solutions, labeled by the benchmark's ground-truth model. In interactive mode, they come from membership queries. Violation indicators are computed lazily, so each example touches only the templates it violates. Sleeping templates receive no update. We will analyze the mistake bound under noise and under sleeping, and characterize when lifted templates provably come to dominate their ground versions: whenever the training set spans at least two instance sizes on which the lifted template is relevant.
The third component is extraction and soundness. Templates above a weight threshold form the model. We then remove redundant templates by checking with a solver whether each one is implied by the others, and verify that every positive example satisfies the final model. Because the output is a set of rules handed to an exact solver, satisfying hard constraints is guaranteed by construction.
Baselines
The naive reference point is the elimination learner on the same template pool. It starts with every template and deletes any template violated by a feasible example. This is the classical version-space learner for conjunctions, and it is what COUNT-CP's keep-what-holds step amounts to. It needs no negatives, so it is cheap. It shows whether multiplicative weighting adds anything beyond the enlarged pool. We expect it to over-constrain with few examples and to collapse under label noise, since one mislabeled positive permanently deletes a true rule.
The strongest existing methods are COUNT-CP and GENCON, run with their published grammars and features on the same instances and the same example budgets. COUNT-CP reports 100% precision from one example and 100% recall with five examples on Sudoku, Magic Square, N-Queens, Graph Coloring, and Nurse Rostering, with about five minutes of training on Nurse Rostering (Learning Constraint Programming Models from Data Using Generate-And-Aggregate). GENCON is reported as achieving high precision and recall under leave-one-in cross-validation on Sudoku, Golomb, Exam Timetabling, and Nurse Rostering and staying robust to 20% label noise. No specific precision or recall figure for GENCON was found on Lacuna, so we will rerun it. Because COUNT-CP already saturates on its own benchmarks, beating it there is impossible. The test is whether our learner matches it there and keeps exact recovery when the grammar is expanded or the data are noisy, which are conditions COUNT-CP was not designed for. GENCON will receive the same perturbation-labeled candidates our learner sees. Each method gets an equal tuning budget of 20 configurations, selected on held-out instance sizes.
The interactive comparison is random-forest guidance in GrowAcq, which reports an average query reduction of 52% and up to 72% on Nurse Rostering relative to unguided GrowAcq (Learning to Learn in Interactive Constraint Acquisition). We replace only its probability source with our weights, under the same query oracle. Beating it means fewer queries to convergence at equal final model accuracy.
Three ablations isolate the key ingredients. The first is an additive perceptron and an L1-regularized logistic regression on the identical pool, which tests whether the multiplicative update matters. The second is Winnow without sleeping, with all templates always awake, which tests whether sleeping drives abstraction. The third is Winnow over ground templates only, which tests whether lifting in the pool is necessary.
Why not just…?
Why not just use L1-regularized logistic regression on the same template pool? This is the most serious threat, because L1 penalties are also attribute-efficient in theory (The limits of squared Euclidean distance regularization groups L1 with multiplicative methods as the ones that suppress irrelevant weights quickly). If batch L1 matches Winnow on example efficiency and noise robustness, then the contribution is the lifted, sleeping template-pool formulation, not the update rule, and we will report it that way. The likely differences are practical. L1 needs the full example-by-template matrix and retraining on each new label, which matters in the interactive setting. L1 also lacks a natural sleeping-expert treatment for templates that do not apply on some instances. The ablation above settles this directly.
Why not just keep random forests over GENCON-style features? Random forests work when a few hand-built features describe each candidate. They cannot express a template whose constant is unrelated to instance parameters, which GENCON states as a limitation (Generalizing Constraint Models in Constraint Acquisition). In an analogous sparse, open-vocabulary setting, Winnow beat decision trees, reaching 75% accuracy against 64% on calendar location prediction and staying stable as features were added (Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain). That result is evidence from a different domain, not proof for this one. The unparameterized-constant experiment below tests it directly.
Why not just enlarge COUNT-CP's grammar and keep its filtering? Enumeration plus elimination has no noise tolerance, and its over-constraint grows with the size of the pool. More candidate rules means more spurious rules that happen to hold on the few observed solutions, which is the incomplete-data weakness COUNT-CP acknowledges. The elimination baseline on our expanded pool is exactly this alternative. If it matches our learner at clean data and large $d$, the multiplicative machinery is unnecessary for the noiseless case.
Proposed Experiments
The first decisive check is the grammar-scaling curve. On Sudoku, Nurse Rostering, Exam Timetabling, and Golomb, we train on two instance sizes and test exact model recovery on a third, unseen size. We sweep the pool from about $10^3$ to $10^6$ templates and record the number of examples needed for full precision and recall on the unseen size. Winnow's bound predicts growth roughly linear in $\log d$. Elimination, the perceptron, and GENCON should grow faster or lose recall. If the curves are similar, the core claim fails.
The second check is noise: 0, 10, and 20% flipped labels, matching GENCON's robustness range, measuring precision and recall of the extracted model. The third check uses unparameterized constants. We modify Exam Timetabling so that room capacities are fixed arbitrary numbers, and modify Golomb with an imposed fixed forbidden distance. GENCON cannot represent either by its own account, so success here is a capability result, not a margin. The fourth check targets abstraction. We train on Sudoku sizes 4×4 and 9×9, test on 16×16 as COUNT-CP did, and measure how much final weight sits on lifted templates compared with ground ones, with and without sleeping. The fifth check is the interactive replacement in GrowAcq on Nurse Rostering and Sudoku, with the query count compared against the reported 52% and 72% reductions under an identical oracle and per-query time under the reported two-second ceiling.
References
- Explanation-Based Generalization of Partially Ordered Plans
- Plan Abstraction Based on Operator Generalization
- Acquiring Schemata Through Understanding and Generalizing Plans
- Learning Constraint Programming Models from Data Using Generate-And-Aggregate
- Generalizing Constraint Models in Constraint Acquisition
- Learning to Learn in Interactive Constraint Acquisition
- The limits of squared Euclidean distance regularization
- Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain
- Distributed Multiplicative Weights Methods for DCOP