Tree-based models are used in many high-stakes application domains such as finance and medicine, where robustness and interpretability are of utmost importance. Yet, methods for improving and certifying their robustness are severely under-explored, in contrast to those focusing on neural networks. Targeting this important challenge, we propose deterministic smoothing for decision stump ensembles. Whereas most prior work on randomized smoothing focuses on evaluating arbitrary base models approximately under input randomization, the key insight of our work is that decision stump ensembles enable exact yet efficient evaluation via dynamic programming. Importantly, we obtain deterministic robustness certificates, even jointly over numerical and categorical features, a setting ubiquitous in the real world.

Semi-supervised learning seeks to learn a machine learning model when only a small amount of the available data is labeled. The most widespread approach uses a graph prior, which encourages similar instances to have similar predictions. This has been very successful with models ranging from kernel machines to neural networks, but has remained inapplicable to decision trees, for which the optimization problem is much harder. We solve this based on a reformulation of the problem which requires iteratively solving two simpler problems: a supervised tree learning problem, which can be solved by the Tree Alternating Optimization algorithm; and a label smoothing problem, which can be solved through a sparse linear system. The algorithm is scalable and highly effective even with very few labeled instances, and makes it possible to learn accurate, interpretable models based on decision trees in such situations.

Random forests have been widely used for their ability to provide so-called importance measures, which give insight at a global (per dataset) level on the relevance of input variables to predict a certain output. On the other hand, methods based on Shapley values have been introduced to refine the analysis of feature relevance in tree-based models to a local (per instance) level. In this context, we first show that the global Mean Decrease of Impurity (MDI) variable importance scores correspond to Shapley values under some conditions. Then, we derive a local MDI importance measure of variable relevance, which has a very natural connection with the global MDI measure and can be related to a new notion of local feature relevance. We further link local MDI importances with Shapley values and discuss them in the light of related measures from the literature. The measures are illustrated through experiments on several classification and regression problems.

Several recent publications report advances in training optimal decision trees (ODTs) using mixed-integer programs (MIPs), due to algorithmic advances in integer programming and a growing interest in addressing the inherent suboptimality of heuristic approaches such as CART. In this paper, we propose a novel MIP formulation, based on 1-norm support vector machine model, to train a binary oblique ODT for classification problems. We further present techniques, such as cutting planes, to tighten its linear relaxation, to improve run times to reach optimality. Using 36 datasets from the University of California Irvine Machine Learning Repository, we demonstrate that our training approach outperforms its counterparts from literature in terms of out-of-sample performance (around 10% improvement in mean out-of-sample testing accuracy). Towards our goal of developing a scalable framework to train multivariate ODT on large datasets, we propose a new linear programming based data selection method to choose a subset of the data, and use it to train a decision tree through our proposed MIP model.

Random forests are some of the most widely used machine learning models today, especially in domains that necessitate interpretability. We present an algorithm that accelerates the training of random forests and other popular tree-based learning methods. At the core of our algorithm is a novel node-splitting subroutine, dubbed MABSplit, used to efficiently find split points when constructing decision trees. Our algorithm borrows techniques from the multi-armed bandit literature to judiciously determine how to allocate samples and computational power across candidate split points. We provide theoretical guarantees that MABSplit improves the sample complexity of each node split from linear to logarithmic in the number of data points.

This is a fairly serious omission, and casual readers would remember the wrong conclusions. This must be fixed for publication, but I think it would be straightforward to fix. Officially, NIPS reviewers are not required to look at the supplementary material. Because of having only three weeks to review six manuscripts, I was not able to make the time during my reviewing. So I worry that publishing this work would mean publishing results without sufficient peer review. DETAILED COMMENTS * p. 1: I'm not sure it is accurate to say that deep, unsupervised trees grown with no subsampling is a common setup for learning random forests. It appears in Geurts et al. (2006) as a special case, sometimes in mass estimation [1, 2], and sometimes in Wei Fan's random decision tree papers [3-6]. I don't think these are used very much.

Summary: This paper proposes a modification of Mondorian Forest which is a variant of Random Forest, a majority vote of decision trees. The authors show that the modified algorithm has the consistency property while the original algorithm does not have one. In particular, when the conditional probability function is Lipschitz, the proposed algorithm achieves the minimax error rate, where the lower bound is previously known. Comments: The technical contribution is to refine the original version of the Mondorian Forest and prove its consistency. The theoretical results are nice and solid. The main idea comes from the original algorithm, thus the originality of the paper is a bit incremental.

The authors describe a method for label distribution learning based on differentiable decision trees. The authors use differentiable sigmoid units to estimate a label distribution using leaf nodes of trees. Learning in split nodes is done via backprop. The authors compare their work with relevant methods on learning label distributions and show the competitiveness of their method. I think this is a good paper, providing a sound methodology for learning LD.

Effective management and early detection of BPSD are crucial to reduce the stress and burden on caregivers and healthcare systems. Despite the advancements in machine learning for dementia prediction, there is a considerable gap in utilizing these methods for BPSD prediction. This study aims to fill this gap by presenting a novel personalized framework for BPSD prediction, utilizing physiological signals from smart wearable devices. Our personalized fine-grained BPSD prediction method accurately predicts BPSD occurrences by extracting individual behavioral patterns, while the generalized models identify diverse patterns and differentiate between various BPSD symptoms. Detailed comparisons between the proposed personalized method and conventional generalized methods reveals substantial improvements across all performance metrics, including a 16.0% increase in AUC. These results demonstrate the potential of our proposed method in advancing dementia care by enabling proactive interventions and improving patient outcomes in real-world scenarios. To the best of our knowledge, this is the first study that leverages physiological signals from smart wearable devices to predict BPSD, marking a significant stride in dementia care research.

Unlike regular models, these very simple models--often referred to as toy models--are not required to be linked to the real world through structural similarity or resemblance relations. They are not meant to be approximations of the target world system, and in some cases, they are not even required to be representational. In semantic terms, they do not accurately map onto their targets. Despite these limitations, they are still useful in understanding theoretical concepts and possible configurations of the target system. Paradigmatic examples of toy models include Boyle's law and the Ising model in physics, the Lotka-Volterra model in population ecology, and the Schelling model in the social sciences (Weisberg, 2013). In recent years, philosophers of science have become interested in toy models (Grüne-Yanoff, 2009; Luczak, 2017; Reutlinger et al., 2018; Frigg & Nguyen, 2017; Nguyen, 2020). The main purpose of this literature is to explore the nature of these models and examine how they perform their epistemic function. Despite lacking the regular descriptive and predictive features of full-scale scientific models, they often offer an elementary understanding of a phenomenon. Their definitions of "toy model" differ as well as their assessment of the importance of representation in modelling generally, but they all agree that toy models play an important epistemic role in scientific research, exploration, and pedagogy.