Adaptive Exact Learning of Decision Trees from Membership Queries
Abstract
In this paper we study the adaptive learnability of decision trees of depth at most $d$ from membership queries. This has many applications in automated scientific discovery such as drugs development and software update problem. Feldman solves the problem in a randomized polynomial time algorithm that asks $\tilde O(2^{2d})\log n$ queries and Kushilevitz-Mansour in a deterministic polynomial time algorithm that asks $ 2^{18d+o(d)}\log n$ queries. We improve the query complexity of both algorithms. We give a randomized polynomial time algorithm that asks $\tilde O(2^{2d}) + 2^{d}\log n$ queries and a deterministic polynomial time algorithm that asks $2^{5.83d}+2^{2d+o(d)}\log n$ queries.
Cite
Text
Bshouty and Haddad-Zaknoon. "Adaptive Exact Learning of Decision Trees from Membership Queries." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.Markdown
[Bshouty and Haddad-Zaknoon. "Adaptive Exact Learning of Decision Trees from Membership Queries." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.](https://mlanthology.org/alt/2019/bshouty2019alt-adaptive/)BibTeX
@inproceedings{bshouty2019alt-adaptive,
title = {{Adaptive Exact Learning of Decision Trees from Membership Queries}},
author = {Bshouty, Nader H. and Haddad-Zaknoon, Catherine A.},
booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory},
year = {2019},
pages = {207-234},
volume = {98},
url = {https://mlanthology.org/alt/2019/bshouty2019alt-adaptive/}
}