Partial Queries for Constraint Acquisition
This work addresses the efficiency of constraint acquisition for users in fields like AI and operations research, offering a polynomial-time solution to a previously exponential problem, though it is incremental in improving query-based learning methods.
The paper tackles the problem of learning constraint networks, which previously required an exponential number of queries, by introducing partial queries that classify assignments to subsets of variables. It presents the QUACQ algorithm, which identifies constraints with a logarithmic number of queries per negative example and learns the entire network with a polynomial number of queries, achieving optimality in some cases.
Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, 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, called QUACQ, 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. The whole constraint network can then be learned with a polynomial number of partial queries. 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.