Learning CNF Theories Using MDL and Predicate Invention
2021 (English)In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence / [ed] Zhi-Hua Zhou, International Joint Conferences on Artificial Intelligence , 2021, p. 2599-2605Conference paper, Published paper (Refereed)
Abstract [en]
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.
Place, publisher, year, edition, pages
International Joint Conferences on Artificial Intelligence , 2021. p. 2599-2605
Keywords [en]
Machine Learning, Relational Learning, Constraints and SAT: Constraints and Data Mining, Constraints and Machine Learning
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-96663DOI: 10.24963/ijcai.2021/358ISBN: 9780999241196 (electronic)OAI: oai:DiVA.org:oru-96663DiVA, id: diva2:1631663
Conference
30th International Joint Conference on Artificial Intelligence (IJCAI 2021), Montreal, Canada, (Virtual conference), August 19-27, 2021
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)EU, Horizon 2020
Note
Funding agency:
Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme
2022-01-242022-01-242022-01-25Bibliographically approved