Chain Length and CSPs Learnable with Few Queries
Abstract
The goal of constraint acquisition is to learn exactly a constraint network given access to an oracle that answers truthfully certain types of queries. In this paper we focus on partial membership queries and initiate a systematic investigation of the learning complexity of constraint languages. First, we use the notion of chain length to show that a wide class of languages can be learned with as few as O(n log(n)) queries. Then, we combine this result with generic lower bounds to derive a dichotomy in the learning complexity of binary languages. Finally, we identify a class of ternary languages that eludes our framework and hints at new research directions.
Cite
Text
Bessiere et al. "Chain Length and CSPs Learnable with Few Queries." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I02.5499Markdown
[Bessiere et al. "Chain Length and CSPs Learnable with Few Queries." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/bessiere2020aaai-chain/) doi:10.1609/AAAI.V34I02.5499BibTeX
@inproceedings{bessiere2020aaai-chain,
title = {{Chain Length and CSPs Learnable with Few Queries}},
author = {Bessiere, Christian and Carbonnel, Clément and Katsirelos, George},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {1420-1427},
doi = {10.1609/AAAI.V34I02.5499},
url = {https://mlanthology.org/aaai/2020/bessiere2020aaai-chain/}
}