Popular decision tree algorithms are provably noise tolerant
Authors: Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4.5, and CART, are highly noise tolerant. Our guarantees hold under the strongest noise model of nasty noise, and we provide near-matching upper and lower bounds on the allowable noise rate. We further show that these algorithms, which are simple and have long been central to everyday machine learning, enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the theoretical literature on decision tree learning. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Stanford University 2Department of Computer Science, Massachusetts Institute of Technology. |
| Pseudocode | Yes | Figure 1: The decision tree boosting algorithm for hypothesis class H and impurity function G over distribution D. For simplicity, we assume that Dℓ(h), w D(ℓ), and µ(Dℓ) can be computed exactly. In practice, these quantities can be replaced with empirical estimates from a random sample of D (see Appendix D for details). |
| Open Source Code | No | The paper makes no explicit statement about releasing source code for the methodology described, nor does it provide a link to a code repository. |
| Open Datasets | No | This is a theoretical paper; it uses the concept of 'samples' for theoretical analysis and proofs (e.g., 'i.i.d. samples (x, y) D') but does not involve empirical training on a publicly available dataset. |
| Dataset Splits | No | This is a theoretical paper that presents proofs and theoretical guarantees, not empirical experiments. Therefore, there are no validation dataset splits. |
| Hardware Specification | No | This is a theoretical paper focused on mathematical proofs and algorithm analysis. It does not involve running experiments on specific hardware, and thus no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper that proves properties of algorithms. While it mentions existing implementations like 'scikitlearn', it does not list specific software dependencies with version numbers required to replicate its theoretical work or proofs. |
| Experiment Setup | No | This is a theoretical paper presenting proofs and algorithms. It does not describe an empirical experimental setup with hyperparameters or training configurations. |