On Testing Decision Tree
| Autor: | Bshouty, Nader H., Haddad-Zaknoon, Catherine A. |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.4230/lipics.stacs.2022.17 |
| Popis: | In this paper, we study testing decision tree of size and depth that are significantly smaller than the number of attributes n. Our main result addresses the problem of poly(n,1/��) time algorithms with poly(s,1/��) query complexity (independent of n) that distinguish between functions that are decision trees of size s from functions that are ��-far from any decision tree of size ��(s,1/��), for some function �� > s. The best known result is the recent one that follows from Blanc, Lange and Tan, [Guy Blanc et al., 2020], that gives ��(s,1/��) = 2^{O((log��s)/����)}. In this paper, we give a new algorithm that achieves ��(s,1/��) = 2^{O(log�� (s/��))}. Moreover, we study the testability of depth-d decision tree and give a distribution free tester that distinguishes between depth-d decision tree and functions that are ��-far from depth-d�� decision tree. LIPIcs, Vol. 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), pages 17:1-17:16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|