CISPA
Browse

What Are the Rules? Discovering Constraints from Data

Download (219.38 kB)
conference contribution
posted on 2024-04-17, 11:17 authored by Boris Wiegand, Dietrich Klakow, Jilles VreekenJilles Vreeken
Constraint programming and AI planning are powerful tools for solving assignment, optimization, and scheduling problems. They require, however, the rarely available combination of domain knowledge and mathematical modeling expertise. Learning constraints from exemplary solutions can close this gap and alleviate the effort of modeling. Existing approaches either require extensive user interaction, need exemplary invalid solutions that must be generated by experts at great expense, or show high noise-sensitivity. We aim to find constraints from potentially noisy solutions, without the need of user interaction. To this end, we formalize the problem in terms of the Minimum Description Length (MDL) principle, by which we select the model with the best lossless compression of the data. Solving the problem involves model counting, which is #P-hard to approximate. We therefore propose the greedy URPILS algorithm to find high-quality constraints in practice. Extensive experiments on constraint programming and AI planning benchmark data show URPILS not only finds more accurate and succinct constraints, but also is more robust to noise, and has lower sample complexity than the state of the art.

History

Editor

Wooldridge MJ ; Dy JG ; Natarajan S

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

National Conference of the American Association for Artificial Intelligence (AAAI)

Journal

Proceedings of the AAAI Conference on Artificial Intelligence

Volume

38

Page Range

8182-8190

Publisher

Association for the Advancement of Artificial Intelligence (AAAI)

Open Access Type

  • Gold

BibTeX

@inproceedings{Wiegand:Klakow:Vreeken:2024, title = "What Are the Rules? Discovering Constraints from Data", author = "Wiegand, Boris" AND "Klakow, Dietrich" AND "Vreeken, Jilles", editor = "Wooldridge, Michael J" AND "Dy, Jennifer G" AND "Natarajan, Sriraam", year = 2024, month = 3, journal = "Proceedings of the AAAI Conference on Artificial Intelligence", number = "8", pages = "8182--8190", publisher = "Association for the Advancement of Artificial Intelligence (AAAI)", issn = "2159-5399", doi = "10.1609/aaai.v38i8.28658" }