Constraint acquisition

被引：56
作者：
Bessiere, Christian [1 ]
Koriche, Frederic [2 ]
Lazaar, Nadjib [1 ]
O'Sullivan, Barry [3 ]
机构：
[1] Univ Montpellier, Montpellier, France
[2] Univ Artois, Arras, France
[3] Univ Coll Cork, Cork, Ireland
来源：
ARTIFICIAL INTELLIGENCE | 2017年 / 244卷
基金：
爱尔兰科学基金会;
关键词：
Constraint programming; Constraint learning;
D O I：
10.1016/j.artint.2015.08.001
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Constraint programming is used to model and solve complex combinatorial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist the non-expert user in the modeling task. This paper presents the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose CONACQ, a system that uses a concise representation of the learner's version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated. (C) 2015 Elsevier By. All rights reserved.
引用
收藏
页码：315 / 342
页数：28
相关论文
共 36 条
  • [1] Queries revisited
    Angluin, D
    [J]. THEORETICAL COMPUTER SCIENCE, 2004, 313 (02) : 175 - 194
  • [2] [Anonymous], 2012, Model ensembles,'' inMachine Learning: The Art and Scienceof Algorithms That Make Sense of Data
  • [3] Apt K., 2003, Principles of Constraint Programming
  • [4] Beldiceanu Nicolas, 2012, Principles and Practice of Constraint Programming. Proceedings 18th International Conference, CP 2012, P141, DOI 10.1007/978-3-642-33558-7_13
  • [5] Global constraint catalogue: Past, present and future
    Beldiceanu, Nicolas
    Carlsson, Mats
    Demassey, Sophie
    Petit, Thierry
    [J]. CONSTRAINTS, 2007, 12 (01) : 21 - 62
  • [6] Bessiere C, 2005, LECT NOTES ARTIF INT, V3720, P23, DOI 10.1007/11564096_8
  • [7] Bessiere C, 2004, LECT NOTES COMPUT SC, V3258, P123
  • [8] Bessiere C., 2007, IJCAI, P44
  • [9] Bessiere C., 2013, P 23 INT JOINT C ART, P475, DOI DOI 10.5555/2540128.2540198
  • [10] Bessiere C., 2006, PROC AAAI C ARTIFICI, P1565
1234