Timezone: »
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.
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)
-
2019 Poster: Optimal Sparse Decision Trees »
Thu. Dec 12th 01:00 -- 03:00 AM Room East Exhibition Hall B + C #15
More from the Same Authors
-
2022 : Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction »
Ali Behrouz · Margo Seltzer -
2022 : Making the World More Equal, One Ride at a Time: Studying Public Transportation Initiatives Using Interpretable Causal Inference »
Gaurav Rajesh Parikh · Albert Sun · Jenny Huang · Lesia Semenova · Cynthia Rudin -
2022 Panel: Panel 3A-2: Linear tree shap… & Exploring the Whole… »
peng yu · Cynthia Rudin -
2022 : Spotlight: Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction »
Ali Behrouz · Margo Seltzer -
2022 : Panel Discussion »
Cynthia Rudin · Dan Bohus · Brenna Argall · Alison Gopnik · Igor Mordatch · Samuel Kaski -
2022 : Let’s Give Domain Experts a Choice by Creating Many Approximately-Optimal Machine Learning Models »
Cynthia Rudin -
2022 Poster: ADBench: Anomaly Detection Benchmark »
Songqiao Han · Xiyang Hu · Hailiang Huang · Minqi Jiang · Yue Zhao -
2022 Poster: BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs »
Kay Liu · Yingtong Dou · Yue Zhao · Xueying Ding · Xiyang Hu · Ruitong Zhang · Kaize Ding · Canyu Chen · Hao Peng · Kai Shu · Lichao Sun · Jundong Li · George H Chen · Zhihao Jia · Philip S Yu -
2022 Poster: Exploring the Whole Rashomon Set of Sparse Decision Trees »
Rui Xin · Chudi Zhong · Zhi Chen · Takuya Takagi · Margo Seltzer · Cynthia Rudin -
2022 Poster: Rethinking Nonlinear Instrumental Variable Models through Prediction Validity »
Chunxiao Li · Cynthia Rudin · Tyler H. McCormick -
2022 Poster: FasterRisk: Fast and Accurate Interpretable Risk Scores »
Jiachang Liu · Chudi Zhong · Boxuan Li · Margo Seltzer · Cynthia Rudin -
2021 : AME: Interpretable Almost Exact Matching for Causal Inference »
Haoning Jiang · Thomas Howell · Neha Gupta · Vittorio Orlandi · Sudeepa Roy · Marco Morucci · Harsh Parikh · Alexander Volfovsky · Cynthia Rudin -
2020 : Contributed Talk - Cryo-ZSSR: multiple-image super-resolution based on deep internal learning »
Qinwen Huang · Reed Chen · Cynthia Rudin -
2020 Workshop: Self-Supervised Learning -- Theory and Practice »
Pengtao Xie · Shanghang Zhang · Pulkit Agrawal · Ishan Misra · Cynthia Rudin · Abdelrahman Mohamed · Wenzhen Yuan · Barret Zoph · Laurens van der Maaten · Xingyi Yang · Eric Xing -
2020 : How should researchers engage with controversial applications of AI? »
Logan Koepke · CATHERINE ONEIL · Tawana Petty · Cynthia Rudin · Deborah Raji · Shawn Bushway -
2020 Workshop: Fair AI in Finance »
Senthil Kumar · Cynthia Rudin · John Paisley · Isabelle Moulinier · C. Bayan Bruss · Eren K. · Susan Tibbs · Oluwatobi Olabiyi · Simona Gandrabur · Svitlana Vyetrenko · Kevin Compher -
2019 Poster: This Looks Like That: Deep Learning for Interpretable Image Recognition »
Chaofan Chen · Oscar Li · Daniel Tao · Alina Barnett · Cynthia Rudin · Jonathan K Su -
2019 Spotlight: This Looks Like That: Deep Learning for Interpretable Image Recognition »
Chaofan Chen · Oscar Li · Daniel Tao · Alina Barnett · Cynthia Rudin · Jonathan K Su -
2018 : Invited Talk 6: Is it possible to have interpretable models for AI in Finance? »
Cynthia Rudin -
2018 : Poster Session 1 (note there are numerous missing names here, all papers appear in all poster sessions) »
Akhilesh Gotmare · Kenneth Holstein · Jan Brabec · Michal Uricar · Kaleigh Clary · Cynthia Rudin · Sam Witty · Andrew Ross · Shayne O'Brien · Babak Esmaeili · Jessica Forde · Massimo Caccia · Ali Emami · Scott Jordan · Bronwyn Woods · D. Sculley · Rebekah Overdorf · Nicolas Le Roux · Peter Henderson · Brandon Yang · Tzu-Yu Liu · David Jensen · Niccolo Dalmasso · Weitang Liu · Paul Marc TRICHELAIR · Jun Ki Lee · Akanksha Atrey · Matt Groh · Yotam Hechtlinger · Emma Tosch