Skip to main content

TS

Constraint acquisition via partial queries

Authors

Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper and Toby Walsh

NICTA

UNSW

Abstract

In 2007, Bessiere et al. have proposed a framework for learning constraint networks via membership queries, that is, by asking the user to classify total assignments of the variables as positive or negative. In this paper we consider the case where the user is able to answer partial queries, that is, to classify assignments on subsets of the variables. We provide an algorithm that given a negative example is able to focus on a constraint of the target network in a number of queries logarithmic in the size of the example. We give lower bounds for learning some simple classes of constraint networks and we show that our generic algorithm is optimal on some of them. Finally we evaluate our algorithm on some benchmark problems.

BibTeX Entry

  @inproceedings{Bessiere_CHKLNQW_13,
    author           = {Bessiere, Christian and Coletta, Remi and Hebrard, Emmanuel and Katsirelos, George and Lazaar,
                        Nadjib and Narodytska, Nina and Quimper, Claude-Guy and Walsh, Toby},
    month            = aug,
    year             = {2013},
    keywords         = {learning constraints, constraint networks},
    title            = {Constraint Acquisition via Partial Queries},
    booktitle        = {23rd International Joint Conference on Artificial Intelligence (IJCAI 2013)},
    pages            = {N/A},
    address          = {Beijing, China}
  }

Download

Served by Apache on Linux on seL4.