Learning constraints through partial queries

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 QuAcQ2, that, given a negative example, elucidates 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. We provide a version of QuAcQ2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcQ2 in practice, especially in the case where QuAcQ2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcQ2 requires significantly fewer queries to learn a network than its predecessor QuAcQ1.(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

In this paper, we propose a method to learn constraint networks by asking users partial queries. We present an algorithm called QuAcQ2, which can elucidate a constraint of the target network with a logarithmically proportional number of queries to the negative example. Our experiments show that QuAcQ2 requires significantly fewer queries compared to its predecessor, QuAcQ1, for network learning. This research has important implications for improving the efficiency of learning constraint networks.