Constraint Acquisition via Partial Queries
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 475-480.
Abstract
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 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. 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. Finally we evaluate our algorithm on some benchmarks.
@inproceedings{ijcai2013p78,
title = {Constraint Acquisition via Partial Queries},
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},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {475--480},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/78},
}
TY - CPAPER TI - Constraint Acquisition via Partial Queries AU - Bessiere, Christian AU - Coletta, Remi AU - Hebrard, Emmanuel AU - Katsirelos, George AU - Lazaar, Nadjib AU - Narodytska, Nina AU - Quimper, Claude-Guy AU - Walsh, Toby T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 475 EP - 480 UR - https://ijcai.org/proceedings/2013/78 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
