# SaDe: Learning Models that Provably Satisfy Domain Constraints

arXiv: https://arxiv.org/abs/2112.00552 · HTML: https://mlsanity.com/paper/2112.00552/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 18 of 18)

- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Fairness in Machine Learning](https://mlsanity.com/paper/2012.15816/) (2020)
- [Harnessing Deep Neural Networks with Logic Rules](https://mlsanity.com/paper/1603.06318/) (2016)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Label-Free Supervision of Neural Networks with Physics and Domain Knowledge](https://mlsanity.com/paper/1609.05566/) (2016)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [The Modern Mathematics of Deep Learning](https://mlsanity.com/paper/2105.04026/) (2021)
- [MultiplexNet: Towards Fully Satisfied Logical Constraints in Neural Networks](https://mlsanity.com/paper/2111.01564/) (2021)
- [Counterexample-Guided Learning of Monotonic Neural Networks](https://mlsanity.com/paper/2006.08852/) (2020)
- [Efficient non-greedy optimization of decision trees](https://mlsanity.com/paper/1511.04056/) (2015)
- [MLIC: A MaxSAT-Based framework for learning interpretable classification rules](https://mlsanity.com/paper/1812.01843/) (2018)
- [Verifying Robustness of Gradient Boosted Models](https://mlsanity.com/paper/1906.10991/) (2019)
- [Versatile Verification of Tree Ensembles](https://mlsanity.com/paper/2010.13880/) (2020)
- [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (2021)
- [Structured Learning Modulo Theories](https://mlsanity.com/paper/1405.1675/) (2014)

## Built on by (most cited first, 3 of 3)

- [DeepSaDe: Learning Neural Networks that Guarantee Domain Constraint Satisfaction](https://mlsanity.com/paper/2303.01141/) (2023)
- [Automatic Generation of Product Concepts from Positive Examples, with an Application to Music Streaming](https://mlsanity.com/paper/2210.01515/) (2022)
- [Safe AI -- How is this Possible?](https://mlsanity.com/paper/2201.10436/) (2022)

## Abstract (arXiv)

In many real world applications of machine learning, models have to meet certain domain-based requirements that can be expressed as constraints (e.g., safety-critical constraints in autonomous driving systems). Such constraints are often handled by including them in a regularization term, while learning a model. This approach, however, does not guarantee 100% satisfaction of the constraints: it only reduces violations of the constraints on the training set rather than ensuring that the predictions by the model will always adhere to them. In this paper, we present a framework for learning models that provably fulfil the constraints under all circumstances (i.e., also on unseen data). To achieve this, we cast learning as a maximum satisfiability problem, and solve it using a novel SaDe algorithm that combines constraint satisfaction with gradient descent. We compare our method against regularization based baselines on linear models and show that our method is capable of enforcing different types of domain constraints effectively on unseen data, without sacrificing predictive performance.