论文标题
局部查询以获取约束
Partial Queries for Constraint Acquisition
论文作者
论文摘要
已知学习约束网络需要许多变量数量中的成员资格查询指数。在本文中，我们通过询问用户部分查询来学习约束网络。也就是说，我们要求用户将作业分配给变量的子集为正或负面。我们提供了一种称为Quacq的算法，在给定一个负面示例中，该算法集中在示例大小的许多查询对数中的目标网络的约束上。然后可以通过多项式的部分查询来学习整个约束网络。我们为学习一些简单的约束网络类别提供了信息理论下限，并表明我们的通用算法在某些情况下是最佳的。
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.
