Identifying Μ-Formula Decision Trees with Queries
Abstract
Abstract We consider a learning problem for the representation class of μ-formula decision trees, a generalization of μ-formulas and μ-decision trees. (The “μ” form of a representation has the restriction that each variable appears no more than once). The learning model is one of exact identification by oracle queries, where learner's goal is to discover an unknown function by asking membership queries (is the function true on some specified input?) and equivalence queries (is the function identical to some hypothesis we present, and if not what is an input on which they differ?). We present an identification algorithm using these two types of queries that runs in time polynomial in the number of variables, and show that no such polynomial time algorithm exists that uses either membership or equivalence queries alone (in the latter case under the stipulation that the hypotheses are drawn from the same representation class).
Cite
Text
Hancock. "Identifying Μ-Formula Decision Trees with Queries." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50005-9Markdown
[Hancock. "Identifying Μ-Formula Decision Trees with Queries." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/hancock1990colt-identifying/) doi:10.1016/B978-1-55860-146-8.50005-9BibTeX
@inproceedings{hancock1990colt-identifying,
title = {{Identifying Μ-Formula Decision Trees with Queries}},
author = {Hancock, Thomas R.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1990},
pages = {23-37},
doi = {10.1016/B978-1-55860-146-8.50005-9},
url = {https://mlanthology.org/colt/1990/hancock1990colt-identifying/}
}