Decision tree splitting criteria: Theory and applications
February 24, 2021 (Zoom - See email or contact organizers for link)
Abstract: Decision trees have applications throughout computer science. A natural approach for constructing a decision tree to approximate some function f is recursive: Use a splitting criterion to decide what variable to put at the root and then recurse on the left and right subtrees. We prove the existence of an efficient splitting criterion for which the resulting tree well-approximates f and apply it to solve problems in diverse areas such as property testing, explainable machine learning, and query strategies for priced information. Joint work with Neha Gupta, Jane Lange, and Li-Yang Tan.