Timezone: »

 
Spotlight
Optimal Sparse Decision Trees
Xiyang Hu · Cynthia Rudin · Margo Seltzer

Wed Dec 11 04:55 PM -- 05:00 PM (PST) @ West Exhibition Hall C + B3
in Track 1 Session 4 »

Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithms are often greedy or myopic, and sometimes produce unquestionably suboptimal models. Hardness of decision tree optimization is both a theoretical and practical obstacle, and even careful mathematical programming approaches have not been able to solve these problems efficiently. This work introduces the first practical algorithm for optimal decision trees for binary variables. The algorithm is a co-design of analytical bounds that reduce the search space and modern systems techniques, including data structures and a custom bit-vector library. We highlight possible steps to improving the scalability and speed of future generations of this algorithm based on insights from our theory and experiments.

[ Paper]  [ Poster]  [ Slides]  [ Slides]  [ 3 min Video] 

Author Information

Xiyang Hu (Carnegie Mellon University)
Cynthia Rudin (Duke)
Margo Seltzer (University of British Columbia)

**MARGO I. SELTZER** is Canada 150 Research Chair in Computer Systems and the Cheriton Family chair in Computer Science at the University of British Columbia. Her research interests are in systems, construed quite broadly: systems for capturing and accessing data provenance, file systems, databases, transaction processing systems, storage and analysis of graph-structured data, new architectures for parallelizing execution, and systems that apply technology to problems in healthcare. She is the author of several widely-used software packages including database and transaction libraries and the 4.4BSD log-structured file system. Dr. Seltzer was a co-founder and CTO of Sleepycat Software, the makers of Berkeley DB, recipient of the 2020 ACM SIGMOD Systems Award. She serves on Advisory Council for the Canadian COVID alert app and the Computer Science and Telecommunications Board (CSTB) of the (US) National Academies. She is a past President of the USENIX Assocation and served as the USENIX representative to the Computing Research Association Board of Directors and on the Computing Community Consortium. She is a member of the National Academy of Engineering, the American Academy of Arts and Sciences, a Sloan Foundation Fellow in Computer Science, an ACM Fellow, a Bunting Fellow, and was the recipient of the 1996 Radcliffe Junior Faculty Fellowship. She is recognized as an outstanding teacher and mentor, having received the Phi Beta Kappa teaching award in 1996, the Abrahmson Teaching Award in 1999, the Capers and Marion McDonald Award for Excellence in Mentoring and Advising in 2010, and the CRA-E Undergraduate Research Mentoring Award in 2017. Professor Seltzer received an A.B. degree in Applied Mathematics from Harvard/Radcliffe College and a Ph. D. in Computer Science from the University of California, Berkeley.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors