Counterexample-Guided Learning of Monotonic Neural Networks

Aishwarya Sivaraman, Golnoosh Farnadi, Todd D. Millstein, Guy Van den Broeck

Introduction

COMET is a novel framework that leverages formal verification techniques to guarantee that neural networks adhere to monotonicity constraints. In many practical applications, it is crucial that a model's output moves in a specific direction as a given input increases—for example, ensuring that a higher credit score never results in a lower loan limit. By utilizing Satisfiability Modulo Theories (SMT) solvers to identify and resolve "counterexamples" during both training and prediction phases, COMET achieves provable monotonicity without the performance trade-offs or architectural restrictions typical of previous methods.

The Challenge of Monotonicity in Deep Learning

In high-stakes domains such as finance, medicine, and autonomous systems, models are expected to follow "common sense" monotonic rules. If a drone's altitude decreases, its speed should generally decrease; if an applicant’s income rises, their approved loan amount shouldn't inexplicably drop.

Standard deep learning models frequently fail these intuitive tests because they prioritize fitting the training data, which often contains noise or outliers that contradict these underlying rules. Previous attempts to address this issue generally fell into two categories:

  1. Architectural Restrictions: Designing "monotonic-by-construction" networks (like Lattice Networks). While guaranteed to be monotonic, these are often less flexible and harder to scale.
  2. Soft Constraints: Employing regularization during training to encourage monotonicity. These remain flexible but offer no mathematical guarantee that the model won't produce a non-monotonic prediction at test time.

COMET bridges this gap, enabling the use of standard, highly flexible ReLU neural networks while still providing a strict mathematical guarantee of monotonicity.

Methods: The COMET Framework

The authors introduce COMET (COunterexample-guided Monotonicity Enforced Training), which employs two primary strategies to enforce constraints:

  • Monotonic Envelopes (Prediction Time): When the model makes a prediction, COMET uses an Optimization Modulo Theories (OMT) solver to check if the prediction violates monotonicity relative to other possible inputs. If a violation is detected, it constructs a "monotonic envelope" (either an upper or lower bound) on-the-fly. This effectively "nudges" the output to the nearest value that satisfies the monotonicity constraint.
Monotonic envelopes bounding a neural network's prediction to enforce monotonicity.
  • Counterexample-Guided Learning (CGL - Training Time): This involves an iterative training loop. After an initial training phase, a solver searches for "counterexamples"—pairs of points where the model's output decreases despite an increase in a monotonic feature. These counterexamples are labeled using a smoothing heuristic and injected back into the training set. This imparts the "inductive bias" of monotonicity to the model, making it naturally more compliant.

Crucially, because COMET relies on SMT/OMT solvers, these counterexamples are identified globally across the entire input space, rather than just in the immediate vicinity of existing training data points.

Datasets Evaluated

The authors evaluated COMET on four well-known real-world datasets, each with specific monotonic features:

  • Auto MPG: Predicting fuel efficiency (monotonic in weight, displacement, and horsepower).
  • Boston Housing: Predicting house prices (monotonic in number of rooms and crime rate).
  • Heart Disease: Predicting the presence of heart disease (monotonic in blood pressure and cholesterol).
  • Adult: Predicting income levels (monotonic in capital gains and hours worked per week).

Key Insights

  • Monotonicity as a Regularizer: One of the most striking findings is that enforcing monotonicity often improves overall model quality. By forcing the model to ignore non-monotonic noise in the training data, COMET acts as a powerful regularizer that prevents overfitting.
  • No Architectural "Straightjacket": Unlike prior work requiring specialized layers or weight constraints, COMET operates on standard ReLU networks. This allows practitioners to utilize the best-performing architectures for their specific tasks.
  • Provable vs. Empirical Guarantees: Most "monotonic" models are only empirically monotonic where tested. COMET leverages formal verification to provide a mathematical proof that the model is monotonic across the entire defined input range.
  • Efficiency of Local Search: While formal verification is notoriously slow, narrowing the search to a single input's "envelope" at prediction time allows COMET to yield results in seconds, making it practical for real-world deployment.

Key Results

  • Superior Performance: COMET outperformed state-of-the-art monotonic learners, such as Min-Max networks and Deep Lattice Networks (DLN), across all tested regression datasets.
  • Guarantees with No Penalty: In many cases, the "Envelope" version of the model (which provides the strict mathematical guarantee) achieved similar or even better Mean Squared Error (MSE) than the unconstrained baseline. For example, on the Boston Housing "Rooms" feature, the baseline MSE was 14.37, while the monotonic envelope improved it to 14.19.
Performance comparison showing the Envelope method maintaining or improving MSE compared to the baseline neural network.
  • Significant Violation Reduction: The CGL training process alone reduced the number of monotonicity violations by an average of 62% before the prediction-time envelope was even applied.
  • Robustness to Outliers: When the authors intentionally injected 1% "noisy" (non-monotonic) data into the training sets, COMET remained stable, whereas the baseline models' performance degraded significantly.

Limitations and Future Work

  • Scalability: While efficient for the tested datasets, SMT solving is an NP-complete problem. Scaling this verification approach to massive, billion-parameter "foundation models" remains a significant computational hurdle.
  • Activation Functions: The current implementation is heavily optimized for ReLU networks because their piecewise linear nature is relatively easy to encode for SMT solvers. Extending this framework to smooth activations like Sigmoid or Tanh would require entirely different verification backends.
  • Beyond Monotonicity: The authors suggest that this counterexample-guided approach could be adapted for other types of domain knowledge, such as enforcing algorithmic fairness constraints or safety invariants in control systems.

Summary updated

Abstract

The widespread adoption of deep learning is often attributed to its automatic feature construction with minimal inductive bias. However, in many real-world tasks, the learned function is intended to satisfy domain-specific constraints. We focus on monotonicity constraints, which are common and require that the function's output increases with increasing values of specific input features. We develop a counterexample-guided technique to provably enforce monotonicity constraints at prediction time. Additionally, we propose a technique to use monotonicity as an inductive bias for deep learning. It works by iteratively incorporating monotonicity counterexamples in the learning process. Contrary to prior work in monotonic learning, we target general ReLU neural networks and do not further restrict the hypothesis space. We have implemented these techniques in a tool called COMET. Experiments on real-world datasets demonstrate that our approach achieves state-of-the-art results compared to existing monotonic learners, and can improve the model quality compared to those that were trained without taking monotonicity constraints into account.
BibTeX
@inproceedings{sivaraman2020counterexample,
  author = {Aishwarya Sivaraman and Golnoosh Farnadi and Todd D. Millstein and Guy Van den Broeck},
  title = {{Counterexample-Guided Learning of Monotonic Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=aHRlmcizahc},
}
Figure