SaDe: Learning Models that Provably Satisfy Domain Constraints

Kshitij Goyal; Sebastijan Dumancic; Hendrik Blockeel

doi:10.1007/978-3-031-26419-1_25

SaDe: Learning Models that Provably Satisfy Domain Constraints

Kshitij Goyal^*, Sebastijan Dumancic, Hendrik Blockeel

^*Corresponding author for this work

Algorithmics

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

17 Downloads (Pure)

Abstract

In many real world applications of machine learning, models have to meet certain domain-based requirements that can be expressed as constraints (for example, 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 fulfill 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.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings
Editors	Massih-Reza Amini, Stéphane Canu, Asja Fischer, Tias Guns, Petra Kralj Novak, Grigorios Tsoumakas
Publisher	Springer
Pages	410-425
Number of pages	16
ISBN (Print)	9783031264184
DOIs	https://doi.org/10.1007/978-3-031-26419-1_25
Publication status	Published - 2023
Event	22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022 - Grenoble, France Duration: 19 Sept 2022 → 23 Sept 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13717 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022
Country/Territory	France
City	Grenoble
Period	19/09/22 → 23/09/22

Bibliographical note

.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Constrained optimization
Domain constraints
Satisfiability modulo theories

Access to Document

10.1007/978-3-031-26419-1_25

978-3-031-26419-1_25Final published version, 460 KB

Cite this

Goyal, K., Dumancic, S., & Blockeel, H. (2023). SaDe: Learning Models that Provably Satisfy Domain Constraints. In M.-R. Amini, S. Canu, A. Fischer, T. Guns, P. Kralj Novak, & G. Tsoumakas (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings (pp. 410-425). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13717 LNAI). Springer. https://doi.org/10.1007/978-3-031-26419-1_25

Goyal, Kshitij ; Dumancic, Sebastijan ; Blockeel, Hendrik. / SaDe : Learning Models that Provably Satisfy Domain Constraints. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. editor / Massih-Reza Amini ; Stéphane Canu ; Asja Fischer ; Tias Guns ; Petra Kralj Novak ; Grigorios Tsoumakas. Springer, 2023. pp. 410-425 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f7858888aee74625966e100f0d36abe2,

title = "SaDe: Learning Models that Provably Satisfy Domain Constraints",

abstract = "In many real world applications of machine learning, models have to meet certain domain-based requirements that can be expressed as constraints (for example, 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 fulfill 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.",

keywords = "Constrained optimization, Domain constraints, Satisfiability modulo theories",

author = "Kshitij Goyal and Sebastijan Dumancic and Hendrik Blockeel",

note = ".Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022 ; Conference date: 19-09-2022 Through 23-09-2022",

year = "2023",

doi = "10.1007/978-3-031-26419-1_25",

language = "English",

isbn = "9783031264184",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "410--425",

editor = "Massih-Reza Amini and St{\'e}phane Canu and Asja Fischer and Tias Guns and {Kralj Novak}, Petra and Grigorios Tsoumakas",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings",

}

Goyal, K, Dumancic, S & Blockeel, H 2023, SaDe: Learning Models that Provably Satisfy Domain Constraints. in M-R Amini, S Canu, A Fischer, T Guns, P Kralj Novak & G Tsoumakas (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13717 LNAI, Springer, pp. 410-425, 22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022, Grenoble, France, 19/09/22. https://doi.org/10.1007/978-3-031-26419-1_25

SaDe: Learning Models that Provably Satisfy Domain Constraints. / Goyal, Kshitij; Dumancic, Sebastijan; Blockeel, Hendrik.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. ed. / Massih-Reza Amini; Stéphane Canu; Asja Fischer; Tias Guns; Petra Kralj Novak; Grigorios Tsoumakas. Springer, 2023. p. 410-425 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13717 LNAI).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - SaDe

T2 - 22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022

AU - Goyal, Kshitij

AU - Dumancic, Sebastijan

AU - Blockeel, Hendrik

N1 - .Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2023

Y1 - 2023

N2 - In many real world applications of machine learning, models have to meet certain domain-based requirements that can be expressed as constraints (for example, 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 fulfill 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.

AB - In many real world applications of machine learning, models have to meet certain domain-based requirements that can be expressed as constraints (for example, 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 fulfill 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.

KW - Constrained optimization

KW - Domain constraints

KW - Satisfiability modulo theories

UR - http://www.scopus.com/inward/record.url?scp=85151064600&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-26419-1_25

DO - 10.1007/978-3-031-26419-1_25

M3 - Conference contribution

AN - SCOPUS:85151064600

SN - 9783031264184

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 410

EP - 425

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings

A2 - Amini, Massih-Reza

A2 - Canu, Stéphane

A2 - Fischer, Asja

A2 - Guns, Tias

A2 - Kralj Novak, Petra

A2 - Tsoumakas, Grigorios

PB - Springer

Y2 - 19 September 2022 through 23 September 2022

ER -

Goyal K, Dumancic S, Blockeel H. SaDe: Learning Models that Provably Satisfy Domain Constraints. In Amini MR, Canu S, Fischer A, Guns T, Kralj Novak P, Tsoumakas G, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. Springer. 2023. p. 410-425. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-26419-1_25