 |
HAL-LIRMM - Open Archive |  |
Conference papers
Constraint Acquisition via Partial Queries
Abstract : We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. Finally we evaluate our algorithm on some benchmarks.
Cited literature [12 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00830325
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Tuesday, June 4, 2013 - 4:52:25 PM
Last modification on : Tuesday, October 19, 2021 - 1:58:40 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 4:53:03 PM
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Tuesday, June 4, 2013 - 4:52:25 PM
Last modification on : Tuesday, October 19, 2021 - 1:58:40 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 4:53:03 PM
File
ijcai13-quacq.pdf
Explicit agreement for this submission