Teaching the Old Dog New Tricks: Supervised Learning with Constraints

Fabrizio Detassis, Michele Lombardi, Michela Milano

Introduction

As machine learning (ML) moves into high-stakes domains like law, medicine, and autonomous systems, there is an increasing need for models that respect specific rules—be they physical laws, safety requirements, or fairness indicators. Traditional approaches to "constrained learning" typically involve post-processing, complex architectural changes, or differentiable regularization. However, these methods often fail to handle complex, discrete, or relational constraints effectively.

The "Moving Targets" (MT) framework addresses these challenges by allowing any standard ML model to satisfy non-differentiable or relational constraints without changing its architecture. By iteratively adjusting training labels using a dedicated constraint solver, the framework "teaches" the model to prioritize rule-following alongside accuracy.

Methodology: The Moving Targets Framework

The core idea of MT is to decouple the "learning" process from "constraint satisfaction" by alternating between two distinct steps:

  1. The Learner Step: A standard, "black-box" ML model (the "Old Dog") is trained to predict a vector of targets. This step requires no knowledge of the constraints.
  2. The Master Step: A specialized constraint solver (the "New Trick") takes the model's predictions and the original ground-truth labels to calculate a new set of "adjusted targets." These targets are designed to be as close as possible to the original labels while strictly satisfying the required constraints.
Conceptual visualization of the Moving Targets framework, illustrating how targets move toward the feasible region C.

By iterating this process, the targets "move" toward a state where a standard ML model can learn to satisfy the constraints. The framework is governed by two primary parameters: $\alpha$, which balances the trade-off between original labels and current predictions during infeasibility, and $\beta$, which controls the "trust region" when the model is already feasible.

The Moving Targets algorithm pseudocode, detailing the iterative Learner and Master steps.

Experimental Setup

The authors evaluated the MT framework using seven datasets from the UCI Machine Learning repository:

  • Classification with Balance Constraints: Iris, Redwine, Whitewine, Shuttle, and Dota2. The goal was to force models to predict classes in a roughly uniform distribution, even with highly skewed training data.
  • Fairness Constraints: Adult (Census Income) and Crime (Communities and Crime). These experiments used the "Disparate Impact Deleterious Index" (DIDI) to ensure the model did not discriminate based on protected attributes like race.

Key Insights and Results

The MT framework demonstrated several key advantages over existing methods:

  • Model Agnosticism: Because the Master and Learner steps are isolated, users can swap between different models, such as Neural Networks or Tree Ensembles, without changing the constraint logic.
  • Handling Non-Differentiable Constraints: MT handles "hard" constraints (e.g., exact percentage requirements) easily because the Master step utilizes combinatorial optimization (like MILP), which natively supports discrete logic.
  • Superior Constraint Satisfaction: On highly unbalanced datasets like Shuttle and Whitewine, MT achieved near-perfect constraint satisfaction where other state-of-the-art methods, such as Semantic Based Regularization, failed.
  • Scalability and Efficiency: Despite the potential complexity of the Master step, modern solvers like CPLEX handled large datasets (e.g., Dota2 with 74,000+ examples) in seconds, often faster than the model training itself.
  • Generalization: Constraints learned on the training set held up on unseen test data, suggesting the model actually "learned" the underlying rules rather than just memorizing adjusted labels.

Conclusion and Future Work

The Moving Targets framework provides a robust, model-agnostic approach to integrating complex constraints into supervised learning. While the framework is highly effective, the authors note that enforcing strict constraints often comes at a cost to predictive accuracy, particularly when the data is heavily biased. Future work will focus on exploring heuristic solvers to further improve scalability and investigating whether the pretraining step can be simplified or removed.

Summary updated

Abstract

Adding constraint support in Machine Learning has the potential to address outstanding issues in data-driven AI systems, such as safety and fairness. Existing approaches typically apply constrained optimization techniques to ML training, enforce constraint satisfaction by adjusting the model design, or use constraints to correct the output. Here, we investigate a different, complementary, strategy based on "teaching" constraint satisfaction to a supervised ML method via the direct use of a state-of-the-art constraint solver: this enables taking advantage of decades of research on constrained optimization with limited effort. In practice, we use a decomposition scheme alternating master steps (in charge of enforcing the constraints) and learner steps (where any supervised ML model and training algorithm can be employed). The process leads to approximate constraint satisfaction in general, and convergence properties are difficult to establish; despite this fact, we found empirically that even a naive setup of our approach performs well on ML tasks with fairness constraints, and on classical datasets with synthetic constraints.
BibTeX
@inproceedings{detassis2021teaching,
  author = {Fabrizio Detassis and Michele Lombardi and Michela Milano},
  title = {{Teaching the Old Dog New Tricks: Supervised Learning with Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16491},
}
Figure