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 O(2^2d) n queries and Kushilevitz-Mansour in a deterministic polynomial time algorithm that asks 2^18d+o(d) n queries. We improve the query complexity of both algorithms. We give a randomized polynomial time algorithm that asks O(2^2d) + 2^d n queries and a deterministic polynomial time algorithm that asks 2^5.83d+2^2d+o(d) n queries.

Tasks

Reproductions