TR#: | MSC-2018-11 |
Class: | MSC |
Title: | On Polynomial time Constructions of Minimum Height Decision Tree |
Authors: | Waseem Makhoul |
Supervisors: | Nader Bshouty |
Currently accessibly only within the Technion network | |
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.
We further study the combinatorial measure, the extended teaching dimension, ETD(C) of a class C. We show an algorithm that achieves a ETD(C)-approximation of the optimal height. When the extended dimension is small, this approximation is better than the log(|C|)-approximation known from the literature. We also show that there is no better approximation ratio 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.
|
Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2018/MSC/MSC-2018-11), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the MSC technical reports of 2018
To the main CS technical reports page