Emerging IoT applications are transitioning from battery-powered to grid-powered nodes. DRP, a contention-based data dissemination protocol, was developed for these applications. Traditional contention-based protocols resolve collisions through control packet exchanges, significantly reducing goodput. DRP mitigates this issue by employing a distributed delay timer mechanism that assigns transmission-start delays based on the average link quality between a sender and its children, prioritizing highly connected nodes for early transmission. However, our in-field experiments reveal that DRP is unable to accommodate real-world link quality fluctuations, leading to overlapping transmissions from multiple senders. This overlap triggers CSMA’s random back-off delays, ultimately degrading the goodput performance. To address these shortcomings, we first conduct a theoretical analysis that characterizes the design requirements induced by real-world link quality fluctuations and DRP’s passive acknowledgments. Guided by this analysis, we design EDRP, which integrates two novel components: (i) Link-Quality Aware CSMA (LQ-CSMA) and (ii) a Machine Learning-based Block Size Selection (ML-BSS) algorithm for rateless codes. LQ-CSMA dynamically restricts the back-off delay range based on real-time link quality estimates, ensuring that nodes with stronger connectivity experience shorter delays. ML-BSS algorithm predicts future link quality conditions and optimally adjusts the block size for rateless coding, reducing overhead and enhancing goodput. In-field evaluations of EDRP demonstrate an average goodput improvement of 39.43% than the competing protocols.

Mesoscale IoT applications, such as P2P energy trade and real-time industrial control systems, demand high throughput and low latency, with a secondary emphasis on energy efficiency as they rely on grid power or large-capacity batteries. MARS, a multi-radio architecture, leverages ML to instantaneously select the optimal radio for transmission, outperforming single-radio systems. However, MARS encounters a significant issue with cost sensitivity, where high-cost errors account for 40% throughput loss. Current cost-sensitive ML algorithms assign a misclassification cost for each class, but not for each data sample. In MARS, each data sample has different costs, making it tedious to employ existing cost-sensitive ML algorithms. First, we address this issue by developing COMNETS, an ML-based radio selector using oblique trees optimized by (TAO). TAO incorporates sample-specific misclassification costs to avert high-cost errors, and achieves a 50% reduction in the decision tree size, making it more suitable for resource-constrained IoT devices. Second, we prove the stability property of TAO and leverage it to understand the critical factors affecting the radio-selection problem. Finally, our real-world evaluation of COMNETS at two different locations shows an average throughput gain of 20.83%, 17.39% than MARS.

IoT is rapidly expanding from traditional small-scale (0–100m) applications like smart homes and large-scale (1–5km) applications like Microsoft’s FarmBeats to emerging mesoscale (0.1–1.5km) applications such as smart-grid NANs and peer-to-peer energy trading in smart homes. These applications demand high throughput and low latency but currently lack dedicated radio technologies. Our qualitative analysis identified Zigbee and LoRa as promising candidates. Further quantitative analysis revealed that a multi-radio architecture combining these radios achieves the best throughput. However, within the 500–1200m range, termed the gray region, it is unpredictable which radio offers higher throughput at any given moment. To address this, we developed MARS, a Multi-radio Architecture with Radio Selection, powered by TAO-optimized decision trees that select the high-throughput radio at the time of transmission. These decision trees require instantaneous path quality estimates, but traditional multi-hop Zigbee networks cannot provide these promptly due to propagation and queuing delays. We overcome this challenge by introducing Decision Tree-based updates to instantaneously estimate end-to-end path quality. Large-scale, real-world experiments with MARS demonstrated average throughput gains of 48.2% and 49.79% at two different locations.

We propose the use of oblique decision trees and forests, originally a supervised machine learning approach, as a model of a single image. This results in a hierarchical partition into constant-color polygons ("poxels") that best approximates the source image. The tree or forest can be trained using a recent algorithm that applies alternating optimization over the nodes of a tree and the trees of a forest. In this paper, we use this for aesthetic effects, such as restyling an image to look like a cubist painting or a stained-glass window. We illustrate this with multiple examples and compare it with the results achieved by Generative AI and Neural Style Transfer.

We explore ensembles of axis-aligned decision stumps, which can be viewed as a generalized additive model (GAM). In this model, stumps utilizing the same feature are grouped to form a shape function for that feature. Instead of relying on boosting or bagging, we employ alternating optimization to learn a fixed-size stump forest. We optimize the parameters of each stump exactly through enumeration, given the other stumps are fixed. For fixed stump splits, the leaf values are optimized jointly by solving a convex problem. To address the overfitting issue inherent in naive optimization of stump forests, we propose effective regularization techniques. Our regularized stump forests achieve accuracy comparable to state-of-the-art GAM methods while using fewer parameters. This work is the first to successfully learn stump forests without employing traditional ensembling techniques like bagging or boosting.

Important applications such as fraud or spam detection or churn prediction involve binary classification problems where the datasets are imbalanced and the cost of false positives greatly differs from the cost of false negatives. We focus on classification trees, in particular oblique trees, which subsume both the traditional axis-aligned trees and logistic regression, but are more accurate than both while providing interpretable models. Rather than using ROC curves, we advocate a loss based on minimizing the false negatives subject to a maximum false positive rate, which we prove to be equivalent to minimizing a weighted 0/1 loss. This yields a curve of classifiers that provably dominates the ROC curve, but is hard to optimize due to the 0/1 loss. We give the first algorithm that can iteratively update the tree parameters globally so that the weighted 0/1 loss decreases monotonically. Experiments on various datasets with class imbalance or class costs show this indeed dominates ROC-based classifiers and significantly improves over previous approaches to learn trees based on weighted purity criteria or over- or undersampling.

NLP tasks such as language models or document classification involve classification problems with thousands of classes. In these situations, it is difficult to get high predictive accuracy and the resulting model can be huge in number of parameters and inference time. A recent, successful approach is the softmax tree (ST): a decision tree having sparse hyperplane splits at the decision nodes (which make hard, not soft, decisions) and small softmax classifiers at the leaves. Inference here is very fast because only a small subset of class probabilities need to be computed, yet the model is quite accurate. However, a significant drawback is that it assumes a complete tree, whose size grows exponentially with depth. We propose a new algorithm to train a ST of arbitrary structure. The tree structure itself is learned optimally by interleaving steps that grow the structure with steps that optimize the parameters of the current structure. This makes it possible to learn STs that can grow much deeper but in an irregular way, adapting to the data distribution. The resulting STs improve considerably the predictive accuracy while reducing the model size and inference time even further, as demonstrated in datasets with thousands of classes. In addition, they are interpretable to some extent.

Decision forests are among the most accurate models in machine learning. This is remarkable given that the way they are trained is highly heuristic: neither the individual trees nor the overall forest optimize any well-defined loss. While diversity mechanisms such as bagging or boosting have been until now critical in the success of forests, we think that a better optimization should lead to better forests—ideally eliminating any need for an ensembling heuristic. However, unlike for most other models, such as neural networks, optimizing forests or trees is not easy, because they define a non-differentiable function. We show, for the first time, that it is possible to learn a forest by optimizing a desirable loss and regularization jointly over all its trees and parameters. Our algorithm, Forest Alternating Optimization, is based on defining a forest as a parametric model with a fixed number of trees and structure (rather than adding trees indefinitely as in bagging or boosting). It then iteratively updates each tree in alternation so that the objective function decreases monotonically. The algorithm is so effective at optimizing that it easily overfits, but this can be corrected by averaging. The result is a forest that consistently exceeds the accuracy of the state-of-the-art while using fewer, smaller trees.

Ensemble methods based on decision trees, such as Random Forests or boosted forests, have long been established as some of the most powerful, off-the-shelf machine learning models, and have been widely used in computer vision and other areas. In recent years, a specific form of boosting, gradient boosting (GB), has gained prominence. This is partly because of highly optimized implementations such as XGBoost or LightGBM, which incorporate many clever modifications and heuristics. However, one gaping hole remains unexplored in GB: the construction of individual trees. To date, all successful GB versions use axis-aligned trees trained in a suboptimal way via greedy recursive partitioning. We address this gap by using a more powerful type of trees (having hyperplane splits) and an algorithm that can optimize, globally over all the tree parameters, the objective function that GB dictates. We show, in several benchmarks of image and other data types, that GB forests of these stronger, well-optimized trees consistently exceed the test accuracy of axis-aligned forests from XGBoost, Light-GBM and other strong baselines. Further, this happens using many fewer trees and sometimes even fewer parameters overall.

Boosting, one of the most effective machine learning frameworks, has attracted an enduring interest since its introduction 30 years ago. The majority of boosting methods use trees as base learner and, while much work has focused on theoretical and empirical variations of boosting, there has been surprisingly little progress on the tree learning procedure itself. To this day, each individual tree is typically axis-aligned (which is ill-suited to model correlations and results in relatively weak classifiers), and is learned using a greedy divide-and-conquer approach such as CART or C5.0, which produces suboptimal trees. We show we can improve boosted forests drastically by making each tree a much stronger classifier. We do this by using sparse oblique trees, which are far more powerful than axis-aligned ones, and by optimizing them using “tree alternating optimization” (TAO), suitably modified to handle the base learner optimization problem dictated by the boosting framework. Focusing on two versions of AdaBoost, we show that the resulting forests not only are consistently and considerably more accurate than random forests or gradient boosting, but that they use a very small number of trees and a comparable number of parameters.

Recent years have seen a renewed interest in interpretable machine learning, which seeks insight into how a model achieves a prediction. Here, we focus on the relatively unexplored case of interpretable clustering. In our approach, the cluster assignments of the training instances are constrained to be the output of a decision tree. This has two advantages: 1) it makes it possible to understand globally how an instance is mapped to a cluster, in particular to see which features are used for which cluster; 2) it forces the clusters to respect a hierarchical structure while optimizing the original clustering objective function. Rather than the traditional axis-aligned trees, we use sparse oblique trees, which have far more modelling power, particularly with high-dimensional data, while remaining interpretable. Our approach applies to any clustering method which is defined by optimizing a cost function and we demonstrate it with two k-means variants.

Classification problems having thousands or more classes naturally occur in NLP, for example language models or document classification.A softmax or one-vs-all classifier naturally handles many classes, but it is very slow at inference time, because every class score must be calculated to find the top class.We propose the "softmax tree", consisting of a binary tree having sparse hyperplanes at the decision nodes (which make hard, not soft, decisions) and small softmax classifiers at the leaves.This is much faster at inference because the input instance follows a single path to a leaf (whose length is logarithmic on the number of leaves) and the softmax classifier at each leaf operates on a small subset of the classes.Although learning accurate tree-based models has proven difficult in the past, we are able to overcome this by using a variation of a recent algorithm, tree alternating optimization (TAO).Compared to a softmax and other classifiers, the resulting softmax trees are both more accurate in prediction and faster in inference, as shown in NLP problems having from one thousand to one hundred thousand classes.

Decision tree boosting is considered as an important and widely recognized method in image classification, despite dominance of the deep learning based approaches in this area. Provided with good image features, it can produce a powerful model with unique properties, such as strong predictive power, scalability, interpretability, etc. In this paper, we propose a novel tree boosting framework which capitalizes on the idea of using shallow, sparse and yet powerful oblique decision trees (trained with recently proposed Tree Alternating optimization algorithm) as the base learners. We empirically show that the resulting model achieves better or comparable performance (both in terms of accuracy and model size) against established boosting algorithms such as gradient boosting or AdaBoost in number of benchmarks. Further, we show that such trees can directly and efficiently handle multiclass problems without using one-vs-all strategy employed by most of the practical boosting implementations.

Regression forests (ensembles of trees) are considered as the leading off-the-shelf method for regression. One of the main approaches of constructing such forests is based on boosting. However, majority of the current boosting implementations employ an axis-aligned tree as a base learner, where each decision node tests for a single feature. Moreover, such trees are usually trained by greedy top-down algorithms such as CART which is shown to be suboptimal. We instead use oblique trees, where each decision node tests for a linear combination of features and train them with the recently proposed non-greedy tree learning method-Tree Alternating Optimization (TAO). We embed the TAO algorithm into the boosting framework and show its effectiveness in the regression setting. We show that it produces much better forests than other types of tree ensembling methods in terms of error, model size and inference time. The result has an immense practical impact on various applications such as in signal processing, data mining, computer vision, etc.

Learning decision trees is a difficult optimization problem: nonconvex, nondifferentiable and over a huge number of tree structures. The dominant paradigm in practice, established in the 1980s, are axis-aligned trees trained with a greedy recursive partitioning algorithm such as CART or C5.0. Several non-greedy optimization algorithms have been proposed recently, which optimize all the nodes' parameters jointly, and we compare experimentally some of them in a range of classification and regression datasets, in terms of accuracy, training time and tree size. The non-greedy algorithms do not improve over CART significantly with one exception, tree alternating optimization (TAO). TAO scales to large datasets and produces axis-aligned and especially oblique trees that consistently outperform all other algorithms, often by a large margin. TAO makes oblique trees preferable to axis-aligned ones in many cases, since they are much more accurate while remaining small and interpretable. This suggests a change in paradigm in practical applications of decision trees.