.png){kind=icon}
返回
Learning constraints through partial queries
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2023.103896.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Constraint programming
Constraint acquisition
Active learning
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
查看更多机构
引用论文
.png){kind=icon}
分享收藏 没有更多内容