טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMakhoul Waseem
SubjectOn Polynomial Time Constructions of Minimum Height
Decision Tree
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty


Abstract

We address the problem of constructing a minimum height decision tree of a class C in polynomial time. This problem has many interesting applications that include, to name a few, computer vision, group testing, exact learning from membership queries, and game theory.


In this work, we further study the combinatorial measure, ETD(C), which is the extended teaching dimension of a class C. We show an algorithm that achieves an ETD(C)-approximation of the optimal height. When the extended dimension is small, this approximation is better than the log(|C|)-approximation already known from the literature. We also show that no better approximation ratio can be achieved unless P=NP.


We then apply our results to learning the class of disjunctions of predicates from membership queries, Bshouty et al. (2017). We show that the extended teaching dimension of this class is bounded from above by the degree d of its Hasse diagram. This gives optimal algorithms when the degree is constant.