Counterexample-Guided Learning of Monotonic Neural Networks

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

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.

Introduction: The Challenge of Monotonicity

In many high-stakes domains, such as finance, healthcare, and safety-critical engineering, we expect models to behave logically. A primary expectation is monotonicity: if an input feature increases (e.g., an applicant's income), the output should not decrease (e.g., the loan approval amount).

Standard deep learning models, despite their power, are "black boxes" that often fail to respect these constraints. Existing solutions typically either restrict the network architecture (limiting expressivity) or use "soft" penalties during training that offer no guarantees at runtime. This paper introduces COMET, a framework that provably enforces monotonicity in standard ReLU neural networks without architecture restrictions.

Methodology: Envelopes and Counterexamples

COMET employs a two-pronged strategy using Satisfiability Modulo Theories (SMT) solvers to identify and correct monotonicity violations.

1. Monotonic Envelopes (Prediction Time)

Instead of relying solely on raw neural network outputs, COMET constructs a "monotonic envelope." When a prediction at a point $x$ violates monotonicity relative to another point $x'$, the SMT solver identifies the necessary adjustment to ensure consistency. This provides a mathematical guarantee of monotonicity for any ReLU network on-the-fly.

Figure 1: Illustration of the Monotonic Envelope correcting a raw Neural Network output for the Boston Housing dataset.

2. Counterexample-Guided Training (CGL)

To improve the base model, COMET uses an iterative training loop. The model is first trained normally. Then, an SMT solver searches for "counterexamples"—pairs of inputs where the model's output decreases when it should increase. These points are labeled and reintegrated into the training set. This process uses monotonicity as an inductive bias, guiding the model toward a smoother, more logical function that generalizes better to unseen data.

Experimental Evaluation

The researchers evaluated COMET on several real-world datasets, including Auto MPG (fuel efficiency), Boston Housing (house prices), Heart Disease (medical diagnosis), and Adult (income levels).

Key Results

The experiments revealed that enforcing monotonicity often acts as a powerful regularizer, improving overall model quality by preventing overfitting to noise.

Figure 5: Performance comparison (MSE) between baseline neural networks (NNb) and the Monotonic Envelope approach on Auto-MPG and Boston datasets.
  • State-of-the-Art Performance: COMET outperformed existing monotonic models like Min-Max networks and Deep Lattice Networks (DLN) across nearly all regression benchmarks.
  • Error Reduction: On the Boston Housing dataset, COMET reduced the Mean Squared Error (MSE) from 14.37 (baseline) to 11.07 (as reported in the study).
  • Violation Reduction: The iterative training process (CGL) reduced the number of monotonicity violations in the base model by an average of 62% before the envelope was even applied.
  • Provable Guarantees: Unlike "soft" penalties, the monotonic envelope provides a mathematical guarantee that the output will be monotonic, which is essential for legal and safety-critical applications.

Conclusion and Future Work

COMET demonstrates that it is possible to achieve provable monotonicity in deep learning without sacrificing architectural flexibility. By treating monotonicity as a global constraint and using formal verification tools to find violations, COMET provides both safety guarantees and improved predictive performance. Future work aims to scale these SMT-based methods to larger architectures and extend the framework to other constraints, such as algorithmic fairness.

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