Adaptive Exact Learning of Decision Trees from Membership Queries

Nader H. Bshouty; Catherine A. Haddad-Zaknoon

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

Download PDF