Learning CNF Theories Using MDL and Predicate Invention

Jain, Arcchit; Gautrais, Clément; Kimmig, Angelika; de Raedt, Luc

doi:10.24963/ijcai.2021/358

Learning CNF Theories Using MDL and Predicate Invention

Arcchit Jain, Clément Gautrais, Angelika Kimmig, Luc De Raedt

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2599-2605.

https://doi.org/10.24963/ijcai.2021/358

Keywords

Machine Learning: Relational Learning
Constraints and SAT: Constraints and Data Mining; Constraints and Machine Learning

Abstract

We revisit the problem of learning logical theories from examples, one of the most quintessential problems in machine learning. More specifically, we develop an approach to learn CNF-formulae from satisfiability. This is a setting in which the examples correspond to partial interpretations and an example is classified as positive when it is logically consistent with the theory.

We present a novel algorithm, called Mistle -- Minimal SAT Theory Learner, for learning such theories. The distinguishing features are that 1) Mistle performs predicate invention and inverse resolution, 2) is based on the MDL principle to compress the data, and 3) combines this with frequent pattern mining to find the most interesting theories.

The experiments demonstrate that Mistle can learn CNF theories accurately and works well in tasks involving compression and classification.

Arcchit Jain, Clément Gautrais, Angelika Kimmig, and Luc de Raedt. 2021. Learning CNF Theories Using MDL and Predicate Invention. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2599–2605. https://doi.org/10.24963/ijcai.2021/358

@inproceedings{ijcai2021p358,
  title     = {Learning CNF Theories Using MDL and Predicate Invention},
  author    = {Jain, Arcchit and Gautrais, Clément and Kimmig, Angelika and de Raedt, Luc},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {2599--2605},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/358},
  url       = {https://doi.org/10.24963/ijcai.2021/358},
}

TY  - CPAPER
TI  - Learning CNF Theories Using MDL and Predicate Invention
AU  - Jain, Arcchit
AU  - Gautrais, Clément
AU  - Kimmig, Angelika
AU  - de Raedt, Luc
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 2599
EP  - 2605
DO  - 10.24963/ijcai.2021/358
UR  - https://doi.org/10.24963/ijcai.2021/358
ER  -