Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference

Matthias Nickles

doi:10.1007/978-3-319-99960-9_6

Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference

Matthias Nickles

Computer Science

Research output: Chapter in Book or Conference Publication/Proceeding › Conference Publication › peer-review

1 Citation (Scopus)

Abstract

This paper proposes multi-model optimization through SAT witness or answer set sampling, with common probabilistic reasoning tasks as primary use cases (including deduction-style probabilistic inference and hypothesis weight learning). Our approach enhances a state-of-the-art SAT/ASP solving algorithm with Gradient Descent as branching literal decision approach, and optionally a cost backtracking mechanism. Sampling of models using these methods minimizes a task-specific, user-provided multi-model cost function while adhering to given logical background knowledge (either a Boolean formula in CNF or a normal logic program under stable model semantics). Features of the framework include its relative simplicity and high degree of expressiveness, since arbitrary differentiable cost functions and background knowledge can be provided.

Original language	English
Title of host publication	Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings
Editors	Fabrizio Riguzzi, Elena Bellodi, Riccardo Zese
Publisher	Springer-Verlag
Pages	88-104
Number of pages	17
ISBN (Print)	9783319999593
DOIs	https://doi.org/10.1007/978-3-319-99960-9_6
Publication status	Published - 2018
Event	28th International Conference on Inductive Logic Programming, ILP 2018 - Ferrara, Italy Duration: 2 Sep 2018 → 4 Sep 2018

Publication series

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

Conference

Conference	28th International Conference on Inductive Logic Programming, ILP 2018
Country/Territory	Italy
City	Ferrara
Period	2/09/18 → 4/09/18

Keywords

Answer set programming
Numerical optimization
Probabilistic logic programming
Projective gradient descent
Relational AI
SAT

Access to Document

10.1007/978-3-319-99960-9_6

Cite this

Nickles, M. (2018). Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference. In F. Riguzzi, E. Bellodi, & R. Zese (Eds.), Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings (pp. 88-104). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11105 LNAI). Springer-Verlag. https://doi.org/10.1007/978-3-319-99960-9_6

Nickles, Matthias. / Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference. Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings. editor / Fabrizio Riguzzi ; Elena Bellodi ; Riccardo Zese. Springer-Verlag, 2018. pp. 88-104 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4347c0e433524676b412cbce144d242b,

title = "Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference",

abstract = "This paper proposes multi-model optimization through SAT witness or answer set sampling, with common probabilistic reasoning tasks as primary use cases (including deduction-style probabilistic inference and hypothesis weight learning). Our approach enhances a state-of-the-art SAT/ASP solving algorithm with Gradient Descent as branching literal decision approach, and optionally a cost backtracking mechanism. Sampling of models using these methods minimizes a task-specific, user-provided multi-model cost function while adhering to given logical background knowledge (either a Boolean formula in CNF or a normal logic program under stable model semantics). Features of the framework include its relative simplicity and high degree of expressiveness, since arbitrary differentiable cost functions and background knowledge can be provided.",

keywords = "Answer set programming, Numerical optimization, Probabilistic logic programming, Projective gradient descent, Relational AI, SAT",

author = "Matthias Nickles",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 28th International Conference on Inductive Logic Programming, ILP 2018 ; Conference date: 02-09-2018 Through 04-09-2018",

year = "2018",

doi = "10.1007/978-3-319-99960-9\_6",

language = "English",

isbn = "9783319999593",

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

publisher = "Springer-Verlag",

pages = "88--104",

editor = "Fabrizio Riguzzi and Elena Bellodi and Riccardo Zese",

booktitle = "Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings",

}

Nickles, M 2018, Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference. in F Riguzzi, E Bellodi & R Zese (eds), Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11105 LNAI, Springer-Verlag, pp. 88-104, 28th International Conference on Inductive Logic Programming, ILP 2018, Ferrara, Italy, 2/09/18. https://doi.org/10.1007/978-3-319-99960-9_6

Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference. / Nickles, Matthias.
Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings. ed. / Fabrizio Riguzzi; Elena Bellodi; Riccardo Zese. Springer-Verlag, 2018. p. 88-104 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11105 LNAI).

Research output: Chapter in Book or Conference Publication/Proceeding › Conference Publication › peer-review

TY - GEN

T1 - Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference

AU - Nickles, Matthias

PY - 2018

Y1 - 2018

N2 - This paper proposes multi-model optimization through SAT witness or answer set sampling, with common probabilistic reasoning tasks as primary use cases (including deduction-style probabilistic inference and hypothesis weight learning). Our approach enhances a state-of-the-art SAT/ASP solving algorithm with Gradient Descent as branching literal decision approach, and optionally a cost backtracking mechanism. Sampling of models using these methods minimizes a task-specific, user-provided multi-model cost function while adhering to given logical background knowledge (either a Boolean formula in CNF or a normal logic program under stable model semantics). Features of the framework include its relative simplicity and high degree of expressiveness, since arbitrary differentiable cost functions and background knowledge can be provided.

AB - This paper proposes multi-model optimization through SAT witness or answer set sampling, with common probabilistic reasoning tasks as primary use cases (including deduction-style probabilistic inference and hypothesis weight learning). Our approach enhances a state-of-the-art SAT/ASP solving algorithm with Gradient Descent as branching literal decision approach, and optionally a cost backtracking mechanism. Sampling of models using these methods minimizes a task-specific, user-provided multi-model cost function while adhering to given logical background knowledge (either a Boolean formula in CNF or a normal logic program under stable model semantics). Features of the framework include its relative simplicity and high degree of expressiveness, since arbitrary differentiable cost functions and background knowledge can be provided.

KW - Answer set programming

KW - Numerical optimization

KW - Probabilistic logic programming

KW - Projective gradient descent

KW - Relational AI

KW - SAT

UR - https://www.scopus.com/pages/publications/85053181568

U2 - 10.1007/978-3-319-99960-9_6

DO - 10.1007/978-3-319-99960-9_6

M3 - Conference Publication

AN - SCOPUS:85053181568

SN - 9783319999593

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

SP - 88

EP - 104

BT - Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings

A2 - Riguzzi, Fabrizio

A2 - Bellodi, Elena

A2 - Zese, Riccardo

PB - Springer-Verlag

T2 - 28th International Conference on Inductive Logic Programming, ILP 2018

Y2 - 2 September 2018 through 4 September 2018

ER -

Nickles M. Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference. In Riguzzi F, Bellodi E, Zese R, editors, Inductive Logic Programming - 28th International Conference, ILP 2018, Proceedings. Springer-Verlag. 2018. p. 88-104. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-99960-9_6

Sampling-Based SAT/ASP Multi-model Optimization as a Framework for Probabilistic Inference

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this