200,996 results on '"Decision Trees"'
Search Results
2. Sparse oblique decision trees: a tool to understand and manipulate neural net features
- Author
-
Hada, Suryabhan Singh, Carreira-Perpiñán, Miguel Á., and Zharmagambetov, Arman
- Published
- 2024
- Full Text
- View/download PDF
3. Automated grading of anatomical objective structured practical examinations using decision trees: An artificial intelligence approach.
- Author
-
Bernard J, Sonnadara R, Saraco AN, Mitchell JP, Bak AB, Bayer I, and Wainman BC
- Subjects
- Humans, Education, Medical, Undergraduate methods, Automation, Curriculum, Decision Trees, Anatomy education, Educational Measurement methods, Educational Measurement statistics & numerical data, Artificial Intelligence
- Abstract
An Objective Structured Practical Examination (OSPE) is an effective and robust, but resource-intensive, means of evaluating anatomical knowledge. Since most OSPEs employ short answer or fill-in-the-blank style questions, the format requires many people familiar with the content to mark the examinations. However, the increasing prevalence of online delivery for anatomy and physiology courses could result in students losing the OSPE practice that they would receive in face-to-face learning sessions. The purpose of this study was to test the accuracy of Decision Trees (DTs) in marking OSPE questions as a first step to creating an intelligent, online OSPE tutoring system. The study used the results of the winter 2020 semester final OSPE from McMaster University's anatomy and physiology course in the Faculty of Health Sciences (HTHSCI 2FF3/2LL3/1D06) as the data set. Ninety percent of the data set was used in a 10-fold validation algorithm to train a DT for each of the 54 questions. Each DT was comprised of unique words that appeared in correct, student-written answers. The remaining 10% of the data set was marked by the generated DTs. When the answers marked by the DT were compared to the answers marked by staff and faculty, the DT achieved an average accuracy of 94.49% across all 54 questions. This suggests that machine learning algorithms such as DTs are a highly effective option for OSPE grading and are suitable for the development of an intelligent, online OSPE tutoring system., (© 2023 The Authors. Anatomical Sciences Education published by Wiley Periodicals LLC on behalf of American Association for Anatomy.)
- Published
- 2024
- Full Text
- View/download PDF
4. Imagining the severe asthma decision trees of the future.
- Author
-
Bourdin A, Bardin P, and Chanez P
- Subjects
- Humans, Clinical Decision-Making, Decision Support Techniques, Algorithms, Adrenal Cortex Hormones adverse effects, Adrenal Cortex Hormones administration & dosage, Adrenal Cortex Hormones therapeutic use, Artificial Intelligence, Administration, Inhalation, Risk Factors, Asthma drug therapy, Asthma physiopathology, Asthma diagnosis, Decision Trees, Anti-Asthmatic Agents therapeutic use, Anti-Asthmatic Agents adverse effects, Severity of Illness Index
- Abstract
Introduction: There are no validated decision-making algorithms concerning severe asthma (SA) management. Future risks are crucial factors and can be derived from SA trajectories., Areas Covered: The future severe asthma-decision trees should revisit current knowledge and gaps. A focused literature search has been conducted., Expert Opinion: Asthma severity is currently defined a priori , thereby precluding a role for early interventions aiming to prevent outcomes such as exacerbations (systemic corticosteroids exposure) and lung function decline. Asthma 'at-risk' might represent the ultimate paradigm but merits longitudinal studies considering modern interventions. Real exacerbations, severe airway hyperresponsiveness, excessive T2-related biomarkers, noxious environments and patient behaviors, harms of OCS and high-doses inhaled corticosteroids (ICS), and low adherence-to-effectiveness ratios of ICS-containing inhalers are predictors of future risks. New tools such as imaging, genetic, and epigenetic signatures should be used. Logical and numerical artificial intelligence may be used to generate a consistent risk score. A pragmatic definition of response to treatments will allow development of a validated and applicable algorithm. Biologics have the best potential to minimize the risks, but cost remains an issue. We propose a simplified six-step algorithm for decision-making that is ultimately aiming to achieve asthma remission.
- Published
- 2024
- Full Text
- View/download PDF
5. Markov-switching decision trees
- Author
-
Adam, Timo, Ötting, Marius, and Michels, Rouven
- Published
- 2024
- Full Text
- View/download PDF
6. Training Gradient Boosted Decision Trees on Tabular Data Containing Label Noise for Classification Tasks
- Author
-
Eisenbürger, Anita, Otten, Daniel, Hudde, Anselm, and Hopfgartner, Frank
- Subjects
Computer Science - Machine Learning - Abstract
Label noise refers to the phenomenon where instances in a data set are assigned to the wrong label. Label noise is harmful to classifier performance, increases model complexity and impairs feature selection. Addressing label noise is crucial, yet current research primarily focuses on image and text data using deep neural networks. This leaves a gap in the study of tabular data and gradient-boosted decision trees (GBDTs), the leading algorithm for tabular data. Different methods have already been developed which either try to filter label noise, model label noise while simultaneously training a classifier or use learning algorithms which remain effective even if label noise is present. This study aims to further investigate the effects of label noise on gradient-boosted decision trees and methods to mitigate those effects. Through comprehensive experiments and analysis, the implemented methods demonstrate state-of-the-art noise detection performance on the Adult dataset and achieve the highest classification precision and recall on the Adult and Breast Cancer datasets, respectively. In summary, this paper enhances the understanding of the impact of label noise on GBDTs and lays the groundwork for future research in noise detection and correction methods.
- Published
- 2024
7. OPTDTALS: Approximate Logic Synthesis via Optimal Decision Trees Approach
- Author
-
Hu, Hao and Cai, Shaowei
- Subjects
Computer Science - Artificial Intelligence - Abstract
The growing interest in Explainable Artificial Intelligence (XAI) motivates promising studies of computing optimal Interpretable Machine Learning models, especially decision trees. Such models generally provide optimality in compact size or empirical accuracy. Recent works focus on improving efficiency due to the natural scalability issue. The application of such models to practical problems is quite limited. As an emerging problem in circuit design, Approximate Logic Synthesis (ALS) aims to reduce circuit complexity by sacrificing correctness. Recently, multiple heuristic machine learning methods have been applied in ALS, which learns approximated circuits from samples of input-output pairs. In this paper, we propose a new ALS methodology realizing the approximation via learning optimal decision trees in empirical accuracy. Compared to previous heuristic ALS methods, the guarantee of optimality achieves a more controllable trade-off between circuit complexity and accuracy. Experimental results show clear improvements in our methodology in the quality of approximated designs (circuit complexity and accuracy) compared to the state-of-the-art approaches.
- Published
- 2024
8. Development of Multistage Machine Learning Classifier using Decision Trees and Boosting Algorithms over Darknet Network Traffic
- Author
-
Nair, Anjali Sureshkumar and Nitnaware, Prashant
- Subjects
Computer Science - Machine Learning ,Computer Science - Cryptography and Security - Abstract
In recent years, the clandestine nature of darknet activities has presented an escalating challenge to cybersecurity efforts, necessitating sophisticated methods for the detection and classification of network traffic associated with these covert operations. The system addresses the significant challenge of class imbalance within Darknet traffic datasets, where malicious traffic constitutes a minority, hindering effective discrimination between normal and malicious behavior. By leveraging boosting algorithms like AdaBoost and Gradient Boosting coupled with decision trees, this study proposes a robust solution for network traffic classification. Boosting algorithms ensemble learning corrects errors iteratively and assigns higher weights to minority class instances, complemented by the hierarchical structure of decision trees. The additional Feature Selection which is a preprocessing method by utilizing Information Gain metrics, Fisher's Score, and Chi-Square test selection for features is employed. Rigorous experimentation with diverse Darknet traffic datasets validates the efficacy of the proposed multistage classifier, evaluated through various performance metrics such as accuracy, precision, recall, and F1-score, offering a comprehensive solution for accurate detection and classification of Darknet activities., Comment: 6 pages, 5 figures
- Published
- 2024
9. Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance
- Author
-
van der Linden, Jacobus G. M., Vos, Daniël, de Weerdt, Mathijs M., Verwer, Sicco, and Demirović, Emir
- Subjects
Computer Science - Machine Learning - Abstract
Decision trees are traditionally trained using greedy heuristics that locally optimize an impurity or information metric. Recently there has been a surge of interest in optimal decision tree (ODT) methods that globally optimize accuracy directly. We identify two relatively unexplored aspects of ODTs: the objective function used in training trees and tuning techniques. Additionally, the value of optimal methods is not well understood yet, as the literature provides conflicting results, with some demonstrating superior out-of-sample performance of ODTs over greedy approaches, while others show the exact opposite. In this paper, we address these three questions: what objective to optimize in ODTs; how to tune ODTs; and how do optimal and greedy methods compare? Our experimental evaluation examines 13 objective functions, including four novel objectives resulting from our analysis, seven tuning methods, and six claims from the literature on optimal and greedy methods on 165 real and synthetic data sets. Through our analysis, both conceptually and experimentally, we discover new non-concave objectives, highlight the importance of proper tuning, support and refute several claims from the literature, and provide clear recommendations for researchers and practitioners on the usage of greedy and optimal methods, and code for future comparisons.
- Published
- 2024
10. RIFF: Inducing Rules for Fraud Detection from Decision Trees
- Author
-
Martins, João Lucas, Bravo, João, Gomes, Ana Sofia, Soares, Carlos, and Bizarro, Pedro
- Subjects
Computer Science - Machine Learning ,Computer Science - Artificial Intelligence - Abstract
Financial fraud is the cause of multi-billion dollar losses annually. Traditionally, fraud detection systems rely on rules due to their transparency and interpretability, key features in domains where decisions need to be explained. However, rule systems require significant input from domain experts to create and tune, an issue that rule induction algorithms attempt to mitigate by inferring rules directly from data. We explore the application of these algorithms to fraud detection, where rule systems are constrained to have a low false positive rate (FPR) or alert rate, by proposing RIFF, a rule induction algorithm that distills a low FPR rule set directly from decision trees. Our experiments show that the induced rules are often able to maintain or improve performance of the original models for low FPR tasks, while substantially reducing their complexity and outperforming rules hand-tuned by experts., Comment: Published as a conference paper at RuleML+RR 2024
- Published
- 2024
11. Vanilla Gradient Descent for Oblique Decision Trees
- Author
-
Panda, Subrat Prasad, Genest, Blaise, Easwaran, Arvind, and Suganthan, Ponnuthurai Nagaratnam
- Subjects
Computer Science - Machine Learning ,Computer Science - Artificial Intelligence - Abstract
Decision Trees (DTs) constitute one of the major highly non-linear AI models, valued, e.g., for their efficiency on tabular data. Learning accurate DTs is, however, complicated, especially for oblique DTs, and does take a significant training time. Further, DTs suffer from overfitting, e.g., they proverbially "do not generalize" in regression tasks. Recently, some works proposed ways to make (oblique) DTs differentiable. This enables highly efficient gradient-descent algorithms to be used to learn DTs. It also enables generalizing capabilities by learning regressors at the leaves simultaneously with the decisions in the tree. Prior approaches to making DTs differentiable rely either on probabilistic approximations at the tree's internal nodes (soft DTs) or on approximations in gradient computation at the internal node (quantized gradient descent). In this work, we propose DTSemNet, a novel semantically equivalent and invertible encoding for (hard, oblique) DTs as Neural Networks (NNs), that uses standard vanilla gradient descent. Experiments across various classification and regression benchmarks show that oblique DTs learned using DTSemNet are more accurate than oblique DTs of similar size learned using state-of-the-art techniques. Further, DT training time is significantly reduced. We also experimentally demonstrate that DTSemNet can learn DT policies as efficiently as NN policies in the Reinforcement Learning (RL) setup with physical inputs (dimensions $\leq32$). The code is available at {\color{blue}\textit{\url{https://github.com/CPS-research-group/dtsemnet}}}., Comment: Published in ECAI-2024. Full version (includes supplementary material)
- Published
- 2024
12. Percolation Inequalities and Decision Trees
- Author
-
Gladkov, Nikita
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60K35, 05C80, 82B43 - Abstract
The use of decision trees for percolation inequalities started with the celebrated O'Donnell--Saks--Schramm--Servedio (OSSS) inequality. We prove decision tree generalizations of the Harris--Kleitman (HK), van den Berg--Kesten (vdBK), and other inequalities. These inequalities are then applied to estimate the connection probabilities in Bernoulli bond percolation on general graphs., Comment: 20 pages
- Published
- 2024
13. Improved Precision in $Vh(\rightarrow b\bar b)$ via Boosted Decision Trees
- Author
-
Englert, Philipp
- Subjects
High Energy Physics - Phenomenology - Abstract
Extracting bounds on BSM operators at hadron colliders can be a highly non-trivial task. It can be useful or, depending on the complexity of the event structure, even essential to employ modern analysis techniques in order to measure New-Physics effects. A particular class of such modern methods are Machine-Learning algorithms, which are becoming more and more popular in particle physics. We attempt to gauge their potential in the study of $Vh(\rightarrow b\bar b)$ production processes, focusing on the leptonic decay channels of the vector bosons. Specifically, we employ boosted decision trees using the kinematical information of a given event to discriminate between signal and background. Based on this analysis strategy, we derive bounds on four dimension-6 SMEFT operators and subsequently compare them with the ones obtained from a conventional cut-and-count analysis. We find a mild improvement of $\mathcal{O}(\mathrm{few}\, \%)$ across the different operators.
- Published
- 2024
14. Mining individual daily commuting patterns of dockless bike-sharing users: a two-layer framework integrating spatiotemporal flow clustering and rule-based decision trees
- Author
-
Zhuang, Caigang, Li, Shaoying, and Liu, Xiaoping
- Subjects
Computer Science - Computers and Society - Abstract
The rise of dockless bike-sharing systems has led to increased interest in using bike-sharing data for urban transportation and travel behavior research. However, few studies have focused on the individual daily mobility patterns, hindering their alignment with the increasingly refined needs of urban active transportation planning. To bridge this gap, this study presents a two-layer framework, integrating improved flow clustering methods and multiple rule-based decision trees, to mine individual cyclists' daily home-work commuting patterns from vast dockless bike-sharing trip data with users' IDs. The effectiveness and applicability of the framework is demonstrated by over 200 million dockless bike-sharing trip records in Shenzhen. Ultimately, based on the mining results, we obtain two categories of bike-sharing commuters (i.e., 74.38% of Only-biking commuters and 25.62% of Biking-with-transit commuters) and some interesting findings about their daily commuting patterns. For instance, lots of bike-sharing commuters live near urban villages and old communities with lower costs of living, especially in the central city. Only-biking commuters have a higher proportion of overtime than Biking-with-transit commuters, and the Longhua Industrial Park, a manufacturing-oriented area, having the longest average working hours (over 10 hours per day). Massive commuters utilize bike-sharing for commuting to work more frequently than for returning home, which is closely related to the over-demand for bike-sharing around workplaces during commuting peak. Overall, this framework offers a cost-effective way to understand residents' non-motorized mobility patterns. Moreover, it paves the way for subsequent research on fine-scale cycling behaviors that consider demographic disparities in socio-economic attributes.
- Published
- 2024
15. Offshore application of landslide susceptibility mapping using gradient-boosted decision trees: a Gulf of Mexico case study
- Author
-
Dyer, Alec S., Mark-Moser, MacKenzie, Duran, Rodrigo, and Bauer, Jennifer R.
- Published
- 2024
- Full Text
- View/download PDF
16. Minimising changes to audit when updating decision trees
- Author
-
Simmons, Anj, Barnett, Scott, Chaudhuri, Anupam, Singh, Sankhya, and Sivasothy, Shangeetha
- Subjects
Computer Science - Machine Learning - Abstract
Interpretable models are important, but what happens when the model is updated on new training data? We propose an algorithm for updating a decision tree while minimising the number of changes to the tree that a human would need to audit. We achieve this via a greedy approach that incorporates the number of changes to the tree as part of the objective function. We compare our algorithm to existing methods and show that it sits in a sweet spot between final accuracy and number of changes to audit., Comment: 12 pages
- Published
- 2024
17. Efficient Decision Trees for Tensor Regressions
- Author
-
Luo, Hengrui, Horiguchi, Akira, and Ma, Li
- Subjects
Computer Science - Machine Learning ,Statistics - Methodology ,Statistics - Machine Learning ,62G08, 15A69 ,G.3 - Abstract
We proposed the tensor-input tree (TT) method for scalar-on-tensor and tensor-on-tensor regression problems. We first address scalar-on-tensor problem by proposing scalar-output regression tree models whose input variable are tensors (i.e., multi-way arrays). We devised and implemented fast randomized and deterministic algorithms for efficient fitting of scalar-on-tensor trees, making TT competitive against tensor-input GP models. Based on scalar-on-tensor tree models, we extend our method to tensor-on-tensor problems using additive tree ensemble approaches. Theoretical justification and extensive experiments on real and synthetic datasets are provided to illustrate the performance of TT., Comment: 36 pages, 9 Figures
- Published
- 2024
18. Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation
- Author
-
Liang, Kaier, Cardona, Gustavo A., Kamale, Disha, and Vasile, Cristian-Ioan
- Subjects
Computer Science - Machine Learning - Abstract
This paper presents a novel framework for inferring timed temporal logic properties from data. The dataset comprises pairs of finite-time system traces and corresponding labels, denoting whether the traces demonstrate specific desired behaviors, e.g. whether the ship follows a safe route or not. Our proposed approach leverages decision-tree-based methods to infer Signal Temporal Logic classifiers using primitive formulae. We formulate the inference process as a mixed integer linear programming optimization problem, recursively generating constraints to determine both data classification and tree structure. Applying a max-flow algorithm on the resultant tree transforms the problem into a global optimization challenge, leading to improved classification rates compared to prior methodologies. Moreover, we introduce a technique to reduce the number of constraints by exploiting the symmetry inherent in STL primitives, which enhances the algorithm's time performance and interpretability. To assess our algorithm's effectiveness and classification performance, we conduct three case studies involving two-class, multi-class, and complex formula classification scenarios.
- Published
- 2024
19. Statistical Advantages of Oblique Randomized Decision Trees and Forests
- Author
-
O'Reilly, Eliza
- Subjects
Mathematics - Statistics Theory ,Statistics - Machine Learning ,Primary 62G05, secondary 60D05 - Abstract
This work studies the statistical advantages of using features comprised of general linear combinations of covariates to partition the data in randomized decision tree and forest regression algorithms. Using random tessellation theory in stochastic geometry, we provide a theoretical analysis of a class of efficiently generated random tree and forest estimators that allow for oblique splits along such features. We call these estimators oblique Mondrian trees and forests, as the trees are generated by first selecting a set of features from linear combinations of the covariates and then running a Mondrian process that hierarchically partitions the data along these features. Generalization error bounds and convergence rates are obtained for the flexible dimension reduction model class of ridge functions (also known as multi-index models), where the output is assumed to depend on a low dimensional relevant feature subspace of the input domain. The results highlight how the risk of these estimators depends on the choice of features and quantify how robust the risk is with respect to error in the estimation of relevant features. The asymptotic analysis also provides conditions on the selected features along which the data is split for these estimators to obtain minimax optimal rates of convergence with respect to the dimension of the relevant feature subspace. Additionally, a lower bound on the risk of axis-aligned Mondrian trees (where features are restricted to the set of covariates) is obtained proving that these estimators are suboptimal for these linear dimension reduction models in general, no matter how the distribution over the covariates used to divide the data at each tree node is weighted., Comment: 43 pages, 2 figures
- Published
- 2024
20. [Real-time Detection Method for Motion Artifact of Photoplethysmography Signals Based on Decision Trees].
- Author
-
Hu L, Zhang Y, Chou Y, Yang H, and He X
- Subjects
- Humans, Motion, Photoplethysmography methods, Artifacts, Algorithms, Signal Processing, Computer-Assisted, Decision Trees
- Abstract
PPG (photoplethysmography) holds significant application value in wearable and intelligent health devices. However, during the acquisition process, PPG signals can generate motion artifacts due to inevitable coupling motion, which diminishes signal quality. In response to the challenge of real-time detection of motion artifacts in PPG signals, this study analyzed the generation and significant features of PPG signal interference. Seven features were extracted from the pulse interval data, and those exhibiting notable changes were filtered using the dual-sample Kolmogorov-Smirnov test. The real-time detection of motion artifacts in PPG signals was ultimately based on decision trees. In the experimental phase, PPG signal data from 20 college students were collected to formulate the experimental dataset. The experimental results demonstrate that the proposed method achieves an average accuracy of (94.07±1.14)%, outperforming commonly used motion artifact detection algorithms in terms of accuracy and real-time performance.
- Published
- 2024
- Full Text
- View/download PDF
21. Gradient boosted decision trees reveal nuances of auditory discrimination behavior.
- Author
-
Griffiths CS, Lebert JM, Sollini J, and Bizley JK
- Subjects
- Animals, Computational Biology, Acoustic Stimulation, Auditory Perception physiology, Behavior, Animal physiology, Reaction Time physiology, Male, Machine Learning, Female, Decision Making physiology, Speech Perception physiology, Ferrets, Decision Trees
- Abstract
Animal psychophysics can generate rich behavioral datasets, often comprised of many 1000s of trials for an individual subject. Gradient-boosted models are a promising machine learning approach for analyzing such data, partly due to the tools that allow users to gain insight into how the model makes predictions. We trained ferrets to report a target word's presence, timing, and lateralization within a stream of consecutively presented non-target words. To assess the animals' ability to generalize across pitch, we manipulated the fundamental frequency (F0) of the speech stimuli across trials, and to assess the contribution of pitch to streaming, we roved the F0 from word token to token. We then implemented gradient-boosted regression and decision trees on the trial outcome and reaction time data to understand the behavioral factors behind the ferrets' decision-making. We visualized model contributions by implementing SHAPs feature importance and partial dependency plots. While ferrets could accurately perform the task across all pitch-shifted conditions, our models reveal subtle effects of shifting F0 on performance, with within-trial pitch shifting elevating false alarms and extending reaction times. Our models identified a subset of non-target words that animals commonly false alarmed to. Follow-up analysis demonstrated that the spectrotemporal similarity of target and non-target words rather than similarity in duration or amplitude waveform was the strongest predictor of the likelihood of false alarming. Finally, we compared the results with those obtained with traditional mixed effects models, revealing equivalent or better performance for the gradient-boosted models over these approaches., Competing Interests: The authors have declared that no competing interests exist., (Copyright: © 2024 Griffiths et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.)
- Published
- 2024
- Full Text
- View/download PDF
22. Impact on clinical guideline adherence of Orient-COVID, a CDSS based on dynamic medical decision trees for COVID19 management: a randomized simulation trial
- Author
-
Jammal, Mouin, Saab, Antoine, Khalil, Cynthia Abi, Mourad, Charbel, Tsopra, Rosy, Saikali, Melody, and Lamy, Jean-Baptiste
- Subjects
Computer Science - Human-Computer Interaction ,Computer Science - Artificial Intelligence ,Computer Science - Computers and Society ,92C50 (Primary), 68U35 (Secondary) - Abstract
Background: The adherence of clinicians to clinical practice guidelines is known to be low, including for the management of COVID-19, due to their difficult use at the point of care and their complexity. Clinical decision support systems have been proposed to implement guidelines and improve adherence. One approach is to permit the navigation inside the recommendations, presented as a decision tree, but the size of the tree often limits this approach and may cause erroneous navigation, especially when it does not fit in a single screen. Methods: We proposed an innovative visual interface to allow clinicians easily navigating inside decision trees for the management of COVID-19 patients. It associates a multi-path tree model with the use of the fisheye visual technique, allowing the visualization of large decision trees in a single screen. To evaluate the impact of this tool on guideline adherence, we conducted a randomized controlled trial in a near-real simulation setting, comparing the decisions taken by medical students using Orient-COVID with those taken with paper guidelines or without guidance, when performing on six realistic clinical cases. Results: The results show that paper guidelines had no impact (p=0.97), while Orient-COVID significantly improved the guideline adherence compared to both other groups (p<0.0003). A significant impact of Orient-COVID was identified on several key points during the management of COVID-19: ordering troponin lab tests, prescribing anticoagulant and oxygen therapy. A multifactor analysis showed no difference between male and female participants. Conclusions: The use of an interactive decision tree for the management of COVID-19 significantly improved the clinician adherence to guidelines. Future works will focus on the integration of the system to electronic health records and on the adaptation of the system to other clinical conditions., Comment: 8 pages, 5 figures
- Published
- 2024
23. Ents: An Efficient Three-party Training Framework for Decision Trees by Communication Optimization
- Author
-
Lin, Guopeng, Han, Weili, Ruan, Wenqiang, Zhou, Ruisheng, Song, Lushan, Li, Bingshuai, and Shao, Yunfeng
- Subjects
Computer Science - Cryptography and Security ,Computer Science - Artificial Intelligence - Abstract
Multi-party training frameworks for decision trees based on secure multi-party computation enable multiple parties to train high-performance models on distributed private data with privacy preservation. The training process essentially involves frequent dataset splitting according to the splitting criterion (e.g. Gini impurity). However, existing multi-party training frameworks for decision trees demonstrate communication inefficiency due to the following issues: (1) They suffer from huge communication overhead in securely splitting a dataset with continuous attributes. (2) They suffer from huge communication overhead due to performing almost all the computations on a large ring to accommodate the secure computations for the splitting criterion. In this paper, we are motivated to present an efficient three-party training framework, namely Ents, for decision trees by communication optimization. For the first issue, we present a series of training protocols based on the secure radix sort protocols to efficiently and securely split a dataset with continuous attributes. For the second issue, we propose an efficient share conversion protocol to convert shares between a small ring and a large ring to reduce the communication overhead incurred by performing almost all the computations on a large ring. Experimental results from eight widely used datasets show that Ents outperforms state-of-the-art frameworks by $5.5\times \sim 9.3\times$ in communication sizes and $3.9\times \sim 5.3\times$ in communication rounds. In terms of training time, Ents yields an improvement of $3.5\times \sim 6.7\times$. To demonstrate its practicality, Ents requires less than three hours to securely train a decision tree on a widely used real-world dataset (Skin Segmentation) with more than 245,000 samples in the WAN setting., Comment: This paper is the full version of a paper to appear in ACM CCS 2024
- Published
- 2024
- Full Text
- View/download PDF
24. Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
- Author
-
Chaouki, Ayman, Read, Jesse, and Bifet, Albert
- Subjects
Computer Science - Machine Learning - Abstract
Decision Tree Learning is a fundamental problem for Interpretable Machine Learning, yet it poses a formidable optimization challenge. Despite numerous efforts dating back to the early 1990's, practical algorithms have only recently emerged, primarily leveraging Dynamic Programming (DP) and Branch & Bound (B&B) techniques. These breakthroughs led to the development of two distinct approaches. Algorithms like DL8.5 and MurTree operate on the space of nodes (or branches), they are very fast, but do not penalise complex Decision Trees, i.e. they do not solve for sparsity. On the other hand, algorithms like OSDT and GOSDT operate on the space of Decision Trees, they solve for sparsity but at the detriment of speed. In this work, we introduce Branches, a novel algorithm that integrates the strengths of both paradigms. Leveraging DP and B&B, Branches achieves exceptional speed while also solving for sparsity. Central to its efficiency is a novel analytical bound enabling substantial pruning of the search space. Furthermore, Branches does not necessitate binary features. Theoretical analysis demonstrates that Branches has a lower complexity bound compared to state-of-the-art methods, a claim validated through extensive empirical evaluation. Our results illustrate that Branches outperforms the state of the art in terms of speed and number of iterations while consistently yielding optimal Decision Trees., Comment: This preprint is currently under review
- Published
- 2024
25. Learning accurate and interpretable decision trees
- Author
-
Balcan, Maria-Florina and Sharma, Dravyansh
- Subjects
Computer Science - Machine Learning - Abstract
Decision trees are a popular tool in machine learning and yield easy-to-understand models. Several techniques have been proposed in the literature for learning a decision tree classifier, with different techniques working well for data from different domains. In this work, we develop approaches to design decision tree learning algorithms given repeated access to data from the same domain. We propose novel parameterized classes of node splitting criteria in top-down algorithms, which interpolate between popularly used entropy and Gini impurity based criteria, and provide theoretical bounds on the number of samples needed to learn the splitting function appropriate for the data at hand. We also study the sample complexity of tuning prior parameters in Bayesian decision tree learning, and extend our results to decision tree regression. We further consider the problem of tuning hyperparameters in pruning the decision tree for classical pruning algorithms including min-cost complexity pruning. We also study the interpretability of the learned decision trees and introduce a data-driven approach for optimizing the explainability versus accuracy trade-off using decision trees. Finally, we demonstrate the significance of our approach on real world datasets by learning data-specific decision trees which are simultaneously more accurate and interpretable., Comment: 26 pages, UAI 2024
- Published
- 2024
26. Output-Constrained Decision Trees
- Author
-
Birbil, Ş. İlker, Özese, Doğanay, and Baydoğan, Mustafa
- Subjects
Computer Science - Machine Learning - Abstract
When there is a correlation between any pair of targets, one needs a prediction method that can handle vector-valued output. In this setting, multi-target learning is particularly important as it is widely used in various applications. This paper introduces new variants of decision trees that can handle not only multi-target output but also the constraints among the targets. We focus on the customization of conventional decision trees by adjusting the splitting criteria to handle the constraints and obtain feasible predictions. We present both an optimization-based exact approach and several heuristics, complete with a discussion on their respective advantages and disadvantages. To support our findings, we conduct a computational study to demonstrate and compare the results of the proposed approaches., Comment: 12 pages, 6 figures
- Published
- 2024
27. Decision Trees for Intuitive Intraday Trading Strategies
- Author
-
Naga, Prajwal, Balivada, Dinesh, Nirmala, Sharath Chandra, and Tiruveedi, Poornoday
- Subjects
Quantitative Finance - Statistical Finance - Abstract
This research paper aims to investigate the efficacy of decision trees in constructing intraday trading strategies using existing technical indicators for individual equities in the NIFTY50 index. Unlike conventional methods that rely on a fixed set of rules based on combinations of technical indicators developed by a human trader through their analysis, the proposed approach leverages decision trees to create unique trading rules for each stock, potentially enhancing trading performance and saving time. By extensively backtesting the strategy for each stock, a trader can determine whether to employ the rules generated by the decision tree for that specific stock. While this method does not guarantee success for every stock, decision treebased strategies outperform the simple buy-and-hold strategy for many stocks. The results highlight the proficiency of decision trees as a valuable tool for enhancing intraday trading performance on a stock-by-stock basis and could be of interest to traders seeking to improve their trading strategies., Comment: 6 pages, 5 figures, 1 table
- Published
- 2024
28. Vectorization of Gradient Boosting of Decision Trees Prediction in the CatBoost Library for RISC-V Processors
- Author
-
Kozinov, Evgeny, Vasiliev, Evgeny, Gorshkov, Andrey, Kustikova, Valentina, Maklaev, Artem, Volokitin, Valentin, and Meyerov, Iosif
- Subjects
Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Performance - Abstract
The emergence and rapid development of the open RISC-V instruction set architecture opens up new horizons on the way to efficient devices, ranging from existing low-power IoT boards to future high-performance servers. The effective use of RISC-V CPUs requires software optimization for the target platform. In this paper, we focus on the RISC-V-specific optimization of the CatBoost library, one of the widely used implementations of gradient boosting for decision trees. The CatBoost library is deeply optimized for commodity CPUs and GPUs. However, vectorization is required to effectively utilize the resources of RISC-V CPUs with the RVV 0.7.1 vector extension, which cannot be done automatically with a C++ compiler yet. The paper reports on our experience in benchmarking CatBoost on the Lichee Pi 4a, RISC-V-based board, and shows how manual vectorization of computationally intensive loops with intrinsics can speed up the use of decision trees several times, depending on the specific workload. The developed codes are publicly available on GitHub.
- Published
- 2024
29. Application of the representative measure approach to assess the reliability of decision trees in dealing with unseen vehicle collision data
- Author
-
Perera-Lago, Javier, Toscano-Durán, Víctor, Paluzo-Hidalgo, Eduardo, Narteni, Sara, and Rucco, Matteo
- Subjects
Computer Science - Machine Learning - Abstract
Machine learning algorithms are fundamental components of novel data-informed Artificial Intelligence architecture. In this domain, the imperative role of representative datasets is a cornerstone in shaping the trajectory of artificial intelligence (AI) development. Representative datasets are needed to train machine learning components properly. Proper training has multiple impacts: it reduces the final model's complexity, power, and uncertainties. In this paper, we investigate the reliability of the $\varepsilon$-representativeness method to assess the dataset similarity from a theoretical perspective for decision trees. We decided to focus on the family of decision trees because it includes a wide variety of models known to be explainable. Thus, in this paper, we provide a result guaranteeing that if two datasets are related by $\varepsilon$-representativeness, i.e., both of them have points closer than $\varepsilon$, then the predictions by the classic decision tree are similar. Experimentally, we have also tested that $\varepsilon$-representativeness presents a significant correlation with the ordering of the feature importance. Moreover, we extend the results experimentally in the context of unseen vehicle collision data for XGboost, a machine-learning component widely adopted for dealing with tabular data.
- Published
- 2024
30. Comparison of decision trees with Local Interpretable Model-Agnostic Explanations (LIME) technique and multi-linear regression for explaining support vector regression model in terms of root mean square error (RMSE) values
- Author
-
Thombre, Amit
- Subjects
Computer Science - Machine Learning ,Computer Science - Artificial Intelligence - Abstract
In this work the decision trees are used for explanation of support vector regression model. The decision trees act as a global technique as well as a local technique. They are compared against the popular technique of LIME which is a local explanatory technique and with multi linear regression. It is observed that decision trees give a lower RMSE value when fitted to support vector regression as compared to LIME in 87% of the runs over 5 datasets. The comparison of results is statistically significant. Multi linear regression also gives a lower RMSE value when fitted to support vector regression model as compared to LIME in 73% of the runs over 5 datasets but the comparison of results is not statistically significant. Also, when used as a local explanatory technique, decision trees give better performance than LIME and the comparison of results is statistically significant.
- Published
- 2024
31. Online Learning of Decision Trees with Thompson Sampling
- Author
-
Chaouki, Ayman, Read, Jesse, and Bifet, Albert
- Subjects
Computer Science - Machine Learning - Abstract
Decision Trees are prominent prediction models for interpretable Machine Learning. They have been thoroughly researched, mostly in the batch setting with a fixed labelled dataset, leading to popular algorithms such as C4.5, ID3 and CART. Unfortunately, these methods are of heuristic nature, they rely on greedy splits offering no guarantees of global optimality and often leading to unnecessarily complex and hard-to-interpret Decision Trees. Recent breakthroughs addressed this suboptimality issue in the batch setting, but no such work has considered the online setting with data arriving in a stream. To this end, we devise a new Monte Carlo Tree Search algorithm, Thompson Sampling Decision Trees (TSDT), able to produce optimal Decision Trees in an online setting. We analyse our algorithm and prove its almost sure convergence to the optimal tree. Furthermore, we conduct extensive experiments to validate our findings empirically. The proposed TSDT outperforms existing algorithms on several benchmarks, all while presenting the practical advantage of being tailored to the online setting., Comment: To be published in the Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS) 2024, Valencia, Spain. PMLR: Volume 238
- Published
- 2024
32. Smart Data Driven Decision Trees Ensemble Methodology for Imbalanced Big Data
- Author
-
García-Gil, Diego, García, Salvador, Xiong, Ning, and Herrera, Francisco
- Published
- 2024
- Full Text
- View/download PDF
33. Challenging Gradient Boosted Decision Trees with Tabular Transformers for Fraud Detection at Booking.com
- Author
-
Krutikov, Sergei, Khaertdinov, Bulat, Kiriukhin, Rodion, Agrawal, Shubham, and De Vries, Kees Jan
- Subjects
Computer Science - Machine Learning - Abstract
Transformer-based neural networks, empowered by Self-Supervised Learning (SSL), have demonstrated unprecedented performance across various domains. However, related literature suggests that tabular Transformers may struggle to outperform classical Machine Learning algorithms, such as Gradient Boosted Decision Trees (GBDT). In this paper, we aim to challenge GBDTs with tabular Transformers on a typical task faced in e-commerce, namely fraud detection. Our study is additionally motivated by the problem of selection bias, often occurring in real-life fraud detection systems. It is caused by the production system affecting which subset of traffic becomes labeled. This issue is typically addressed by sampling randomly a small part of the whole production data, referred to as a Control Group. This subset follows a target distribution of production data and therefore is usually preferred for training classification models with standard ML algorithms. Our methodology leverages the capabilities of Transformers to learn transferable representations using all available data by means of SSL, giving it an advantage over classical methods. Furthermore, we conduct large-scale experiments, pre-training tabular Transformers on vast amounts of data instances and fine-tuning them on smaller target datasets. The proposed approach outperforms heavily tuned GBDTs by a considerable margin of the Average Precision (AP) score. Pre-trained models show more consistent performance than the ones trained from scratch when fine-tuning data is limited. Moreover, they require noticeably less labeled data for reaching performance comparable to their GBDT competitor that utilizes the whole dataset., Comment: Submitted to CIKM'24, Applied Research track
- Published
- 2024
34. Teaching and Learning to Construct Data-Based Decision Trees Using Data Cards as the First Introduction to Machine Learning in Middle School
- Author
-
Yannik Fleischer, Susanne Podworny, and Rolf Biehler
- Abstract
This study investigates how 11- to 12-year-old students construct data-based decision trees using data cards for classification purposes. We examine the students' heuristics and reasoning during this process. The research is based on an eight-week teaching unit during which students labeled data, built decision trees, and assessed them using test data. They learned to manually construct decision trees to classify food items as recommendable or not. They utilized data cards with a heuristic that is a simplified form of a machine learning algorithm. We report on evidence that this topic is teachable to middle school students, along with insights for refining our teaching approach and broader implications for teaching machine learning at the school level.
- Published
- 2024
- Full Text
- View/download PDF
35. Using Decision Trees to Predict Insolvency in Spanish SMEs: Is Early Warning Possible?
- Author
-
Navarro-Galera, Andrés, Lara-Rubio, Juan, Novoa-Hernández, Pavel, and Cruz Corona, Carlos A.
- Published
- 2024
- Full Text
- View/download PDF
36. Time analysis of online consumer behavior by decision trees, GUHA association rules, and formal concept analysis
- Author
-
Pitka, Tomáš, Bucko, Jozef, Krajči, Stanislav, Krídlo, Ondrej, Guniš, Ján, Šnajder, Ľubomír, Antoni, Ľubomír, and Eliaš, Peter
- Published
- 2024
- Full Text
- View/download PDF
37. Variability of Winter Frosts in Central South America: Quantifying Mechanisms with Decision Trees
- Author
-
Collazo, Soledad and García-Herrera, Ricardo
- Published
- 2024
- Full Text
- View/download PDF
38. Predicting landslide and debris flow susceptibility using Logitboost alternating decision trees and ensemble techniques
- Author
-
Nguyen, Cong Quan, Nguyen, Duc Anh, Tran, Hieu Trung, Nguyen, Thanh Trung, Thao, Bui Thi Phuong, Cong, Nguyen Tien, Van Phong, Tran, Van Le, Hiep, Prakash, Indra, and Pham, Binh Thai
- Published
- 2024
- Full Text
- View/download PDF
39. Insights into Dark Matter Direct Detection Experiments: Decision Trees versus Deep Learning
- Author
-
Lopez-Fogliani, Daniel E., Perez, Andres D., and de Austri, Roberto Ruiz
- Subjects
Astrophysics - Instrumentation and Methods for Astrophysics ,Astrophysics - High Energy Astrophysical Phenomena ,High Energy Physics - Experiment ,High Energy Physics - Phenomenology ,Physics - Data Analysis, Statistics and Probability - Abstract
The detection of Dark Matter (DM) remains a significant challenge in particle physics. This study exploits advanced machine learning models to improve detection capabilities of liquid xenon time projection chamber experiments, utilizing state-of-the-art transformers alongside traditional methods like Multilayer Perceptrons and Convolutional Neural Networks. We evaluate various data representations and find that simplified feature representations, particularly corrected S1 and S2 signals, retain critical information for classification. Our results show that while transformers offer promising performance, simpler models like XGBoost can achieve comparable results with optimal data representations. We also derive exclusion limits in the cross-section versus DM mass parameter space, showing minimal differences between XGBoost and the best performing deep learning models. The comparative analysis of different machine learning approaches provides a valuable reference for future experiments by guiding the choice of models and data representations to maximize detection capabilities., Comment: 26 pages, 7 figures, 2 tables
- Published
- 2024
40. Mixed-Curvature Decision Trees and Random Forests
- Author
-
Chlenski, Philippe, Chu, Quentin, and Pe'er, Itsik
- Subjects
Computer Science - Machine Learning - Abstract
We extend decision tree and random forest algorithms to product space manifolds: Cartesian products of Euclidean, hyperspherical, and hyperbolic manifolds. Such spaces have extremely expressive geometries capable of representing many arrangements of distances with low metric distortion. To date, all classifiers for product spaces fit a single linear decision boundary, and no regressor has been described. Our method enables a simple, expressive method for classification and regression in product manifolds. We demonstrate the superior accuracy of our tool compared to Euclidean methods operating in the ambient space or the tangent plane of the manifold across a range of constant-curvature and product manifolds. Code for our implementation and experiments is available at https://github.com/pchlenski/embedders.
- Published
- 2024
41. Learning Decision Trees and Forests with Algorithmic Recourse
- Author
-
Kanamori, Kentaro, Takagi, Takuya, Kobayashi, Ken, and Ike, Yuichi
- Subjects
Computer Science - Machine Learning ,Statistics - Machine Learning - Abstract
This paper proposes a new algorithm for learning accurate tree-based models while ensuring the existence of recourse actions. Algorithmic Recourse (AR) aims to provide a recourse action for altering the undesired prediction result given by a model. Typical AR methods provide a reasonable action by solving an optimization task of minimizing the required effort among executable actions. In practice, however, such actions do not always exist for models optimized only for predictive performance. To alleviate this issue, we formulate the task of learning an accurate classification tree under the constraint of ensuring the existence of reasonable actions for as many instances as possible. Then, we propose an efficient top-down greedy algorithm by leveraging the adversarial training techniques. We also show that our proposed algorithm can be applied to the random forest, which is known as a popular framework for learning tree ensembles. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency., Comment: 27 pages, 10 figures, to appear in the 41st International Conference on Machine Learning (ICML 2024)
- Published
- 2024
42. Estimating optimal decision trees for treatment assignment: The case of K > 2 treatment alternatives
- Author
-
Sies, Aniek, Doove, Lisa, Meers, Kristof, Dusseldorp, Elise, and Van Mechelen, Iven
- Published
- 2024
- Full Text
- View/download PDF
43. Detecting malicious pilot contamination in multiuser massive MIMO using decision trees
- Author
-
da Cruz, Pedro Ivo, Leandro, Dimitri, Spadini, Tito, Suyama, Ricardo, and Loiola, Murilo Bellezoni
- Published
- 2024
- Full Text
- View/download PDF
44. Flood Susceptibility Mapping Using Information Fusion Paradigm Integrated with Decision Trees
- Author
-
Akay, Hüseyin
- Published
- 2024
- Full Text
- View/download PDF
45. Hellinger distance decision trees for PU learning in imbalanced data sets
- Author
-
Ortega Vázquez, Carlos, vanden Broucke, Seppe, and De Weerdt, Jochen
- Published
- 2024
- Full Text
- View/download PDF
46. Explainable Reinforcement Learning-based Home Energy Management Systems using Differentiable Decision Trees
- Author
-
Gokhale, Gargya, Claessens, Bert, and Develder, Chris
- Subjects
Electrical Engineering and Systems Science - Systems and Control ,Computer Science - Machine Learning - Abstract
With the ongoing energy transition, demand-side flexibility has become an important aspect of the modern power grid for providing grid support and allowing further integration of sustainable energy sources. Besides traditional sources, the residential sector is another major and largely untapped source of flexibility, driven by the increased adoption of solar PV, home batteries, and EVs. However, unlocking this residential flexibility is challenging as it requires a control framework that can effectively manage household energy consumption, and maintain user comfort while being readily scalable across different, diverse houses. We aim to address this challenging problem and introduce a reinforcement learning-based approach using differentiable decision trees. This approach integrates the scalability of data-driven reinforcement learning with the explainability of (differentiable) decision trees. This leads to a controller that can be easily adapted across different houses and provides a simple control policy that can be explained to end-users, further improving user acceptance. As a proof-of-concept, we analyze our method using a home energy management problem, comparing its performance with commercially available rule-based baseline and standard neural network-based RL controllers. Through this preliminary study, we show that the performance of our proposed method is comparable to standard RL-based controllers, outperforming baseline controllers by ~20% in terms of daily cost savings while being straightforward to explain., Comment: 9 pages, 5 figures
- Published
- 2024
47. Distill2Explain: Differentiable decision trees for explainable reinforcement learning in energy application controllers
- Author
-
Gokhale, Gargya, Madahi, Seyed Soroush Karimi, Claessens, Bert, and Develder, Chris
- Subjects
Electrical Engineering and Systems Science - Systems and Control ,Computer Science - Machine Learning - Abstract
Demand-side flexibility is gaining importance as a crucial element in the energy transition process. Accounting for about 25% of final energy consumption globally, the residential sector is an important (potential) source of energy flexibility. However, unlocking this flexibility requires developing a control framework that (1) easily scales across different houses, (2) is easy to maintain, and (3) is simple to understand for end-users. A potential control framework for such a task is data-driven control, specifically model-free reinforcement learning (RL). Such RL-based controllers learn a good control policy by interacting with their environment, learning purely based on data and with minimal human intervention. Yet, they lack explainability, which hampers user acceptance. Moreover, limited hardware capabilities of residential assets forms a hurdle (e.g., using deep neural networks). To overcome both those challenges, we propose a novel method to obtain explainable RL policies by using differentiable decision trees. Using a policy distillation approach, we train these differentiable decision trees to mimic standard RL-based controllers, leading to a decision tree-based control policy that is data-driven and easy to explain. As a proof-of-concept, we examine the performance and explainability of our proposed approach in a battery-based home energy management system to reduce energy costs. For this use case, we show that our proposed approach can outperform baseline rule-based policies by about 20-25%, while providing simple, explainable control policies. We further compare these explainable policies with standard RL policies and examine the performance trade-offs associated with this increased explainability., Comment: 14 pages, 6 figures, to be published in e-Energy 2024
- Published
- 2024
48. Explaining Kernel Clustering via Decision Trees
- Author
-
Fleissner, Maximilian, Vankadara, Leena Chennuru, and Ghoshdastidar, Debarghya
- Subjects
Computer Science - Machine Learning - Abstract
Despite the growing popularity of explainable and interpretable machine learning, there is still surprisingly limited work on inherently interpretable clustering methods. Recently, there has been a surge of interest in explaining the classic k-means algorithm, leading to efficient algorithms that approximate k-means clusters using axis-aligned decision trees. However, interpretable variants of k-means have limited applicability in practice, where more flexible clustering methods are often needed to obtain useful partitions of the data. In this work, we investigate interpretable kernel clustering, and propose algorithms that construct decision trees to approximate the partitions induced by kernel k-means, a nonlinear extension of k-means. We further build on previous work on explainable k-means and demonstrate how a suitable choice of features allows preserving interpretability without sacrificing approximation guarantees on the interpretable model.
- Published
- 2024
49. An Algorithmic Framework for Constructing Multiple Decision Trees by Evaluating Their Combination Performance Throughout the Construction Process
- Author
-
Tajima, Keito, Ichijo, Naoki, Nakahara, Yuta, and Matsushima, Toshiyasu
- Subjects
Computer Science - Machine Learning - Abstract
Predictions using a combination of decision trees are known to be effective in machine learning. Typical ideas for constructing a combination of decision trees for prediction are bagging and boosting. Bagging independently constructs decision trees without evaluating their combination performance and averages them afterward. Boosting constructs decision trees sequentially, only evaluating a combination performance of a new decision tree and the fixed past decision trees at each step. Therefore, neither method directly constructs nor evaluates a combination of decision trees for the final prediction. When the final prediction is based on a combination of decision trees, it is natural to evaluate the appropriateness of the combination when constructing them. In this study, we propose a new algorithmic framework that constructs decision trees simultaneously and evaluates their combination performance throughout the construction process. Our framework repeats two procedures. In the first procedure, we construct new candidates of combinations of decision trees to find a proper combination of decision trees. In the second procedure, we evaluate each combination performance of decision trees under some criteria and select a better combination. To confirm the performance of the proposed framework, we perform experiments on synthetic and benchmark data.
- Published
- 2024
50. Boosting-Based Sequential Meta-Tree Ensemble Construction for Improved Decision Trees
- Author
-
Maniwa, Ryota, Ichijo, Naoki, Nakahara, Yuta, and Matsushima, Toshiyasu
- Subjects
Statistics - Machine Learning ,Computer Science - Machine Learning - Abstract
A decision tree is one of the most popular approaches in machine learning fields. However, it suffers from the problem of overfitting caused by overly deepened trees. Then, a meta-tree is recently proposed. It solves the problem of overfitting caused by overly deepened trees. Moreover, the meta-tree guarantees statistical optimality based on Bayes decision theory. Therefore, the meta-tree is expected to perform better than the decision tree. In contrast to a single decision tree, it is known that ensembles of decision trees, which are typically constructed boosting algorithms, are more effective in improving predictive performance. Thus, it is expected that ensembles of meta-trees are more effective in improving predictive performance than a single meta-tree, and there are no previous studies that construct multiple meta-trees in boosting. Therefore, in this study, we propose a method to construct multiple meta-trees using a boosting approach. Through experiments with synthetic and benchmark datasets, we conduct a performance comparison between the proposed methods and the conventional methods using ensembles of decision trees. Furthermore, while ensembles of decision trees can cause overfitting as well as a single decision tree, experiments confirmed that ensembles of meta-trees can prevent overfitting due to the tree depth.
- Published
- 2024
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.