Adaptive Exact Learning of Decision Trees from Membership Queries

Nader H. Bshouty, Catherine A. Haddad-Zaknoon
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:207-234, 2019.

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 this Paper

BibTeX
@InProceedings{pmlr-v98-bshouty19a, 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}, pages = {207--234}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/bshouty19a/bshouty19a.pdf}, url = {https://proceedings.mlr.press/v98/bshouty19a.html}, 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.} }
Endnote
%0 Conference Paper %T Adaptive Exact Learning of Decision Trees from Membership Queries %A Nader H. Bshouty %A Catherine A. Haddad-Zaknoon %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-bshouty19a %I PMLR %P 207--234 %U https://proceedings.mlr.press/v98/bshouty19a.html %V 98 %X 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.
APA
Bshouty, N.H. & Haddad-Zaknoon, C.A.. (2019). Adaptive Exact Learning of Decision Trees from Membership Queries. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:207-234 Available from https://proceedings.mlr.press/v98/bshouty19a.html.

Related Material