LIPIcs.STACS.2022.17.pdf
- Filesize: 0.72 MB
- 16 pages
Document
On Testing Decision Tree
Authors
-
Part of:
Volume:
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-03-09
Cite AsGet BibTex
Nader H. Bshouty and Catherine A. Haddad-Zaknoon. On Testing Decision Tree. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.17
https://doi.org/10.4230/LIPIcs.STACS.2022.17
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Oracles and decision trees
Keywords
- Testing decision trees
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 210-220, 2011. URL: https://doi.org/10.1109/CCC.2011.31.
- Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan. Properly learning decision trees in almost polynomial time. CoRR, abs/2109.00637, 2021. URL: http://arxiv.org/abs/2109.00637.
- Guy Blanc, Jane Lange, and Li-Yang Tan. Testing and reconstruction via decision trees. CoRR, abs/2012.08735, 2020. URL: http://arxiv.org/abs/2012.08735.
- Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
- Nader H. Bshouty. Almost optimal testers for concise representations. Electronic Colloquium on Computational Complexity (ECCC), 26:156, 2019. URL: https://eccc.weizmann.ac.il/report/2019/156.
- Nader H. Bshouty. Almost optimal testers for concise representations. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 5:1-5:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.5.
- Nader H. Bshouty and Catherine A. Haddad-Zaknoon. Adaptive exact learning of decision trees from membership queries. In Aurélien Garivier and Satyen Kale, editors, Algorithmic Learning Theory, ALT 2019, 22-24 March 2019, Chicago, Illinois, USA, volume 98 of Proceedings of Machine Learning Research, pages 207-234. PMLR, 2019. URL: http://proceedings.mlr.press/v98/bshouty19a.html.
- Nader H. Bshouty and Yishay Mansour. Simple learning algorithms for decision trees and multivariate polynomials. SIAM J. Comput., 31(6):1909-1925, 2002. URL: https://doi.org/10.1137/S009753979732058X.
- Sourav Chakraborty, David García-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 545-556, 2011. URL: https://doi.org/10.1007/978-3-642-22006-7_46.
- Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 549-558, 2007. URL: https://doi.org/10.1109/FOCS.2007.32.
- Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
- Michael J. Kearns and Dana Ron. Testing problems with sublearning sample complexity. J. Comput. Syst. Sci., 61(3):428-456, 2000. URL: https://doi.org/10.1006/jcss.1999.1656.
- Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: https://doi.org/10.1137/S0097539793255151.