Learning Optimal Classification Trees Robust to Distribution Shifts

• URL: http://arxiv.org/abs/2310.17772v1
• Date: Thu, 26 Oct 2023 20:37:29 GMT
• Title: Learning Optimal Classification Trees Robust to Distribution Shifts
• Abstract summary: We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. We propose a method for learning optimal robust classification trees based on mixed-integer robust optimization technology.
• Score: 3.244976698646146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time when and place where the survey is conducted, and the level of comfort the interviewee has in sharing information with the interviewer. We propose a method for learning optimal robust classification trees based on mixed-integer robust optimization technology. In particular, we demonstrate that the problem of learning an optimal robust tree can be cast as a single-stage mixed-integer robust optimization problem with a highly nonlinear and discontinuous objective. We reformulate this problem equivalently as a two-stage linear robust optimization problem for which we devise a tailored solution procedure based on constraint generation. We evaluate the performance of our approach on numerous publicly available datasets, and compare the performance to a regularized, non-robust optimal tree. We show an increase of up to 12.48% in worst-case accuracy and of up to 4.85% in average-case accuracy across several datasets and distribution shifts from using our robust solution in comparison to the non-robust one.

Related papers

• Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective [5.848643785361479]
  We introduce the exponential decay rate of the policy-selection error probability as a principled efficiency metric.<n>We formalize two complementary notions of optimality in terms of the optimal solution of the nested problem.<n>We prove that the resulting reinforcement learning algorithm is near-robustly optimal under our optimality criterion, up to a constant factor.
  arXiv  Detail & Related papers  (2026-05-27T16:08:56Z)
• Interpretable clustering via optimal multiway-split decision trees [1.8224668251608893]
  We propose an interpretable clustering method based on optimal multiway-split decision trees.<n>A key feature of our method is the integration of a one-dimensional K-means algorithm for the discretization of continuous variables.<n>Our method yields multiway-split decision trees with concise decision rules while maintaining competitive performance across various evaluation metrics.
  arXiv  Detail & Related papers  (2026-02-14T04:08:52Z)
• Geometric Median Matching for Robust k-Subset Selection from Noisy Data [75.86423267723728]
  We propose a novel k-subset selection strategy that leverages Geometric Median -- a robust estimator with an optimal breakdown point of 1/2. Our method iteratively selects a k-subset such that the mean of the subset approximates the GM of the (potentially) noisy dataset, ensuring robustness even under arbitrary corruption.
  arXiv  Detail & Related papers  (2025-04-01T09:22:05Z)
• Forecasting Outside the Box: Application-Driven Optimal Pointwise Forecasts for Stochastic Optimization [0.0]
  We present an integrated learning and optimization procedure that yields the best approximation of an unknown situation. Numerical results conducted with inventory problems from the literature as well as a bike-sharing problem with real data demonstrate that the proposed approach performs well.
  arXiv  Detail & Related papers  (2024-11-05T21:54:50Z)
• Optimal and Efficient Binary Questioning for Human-in-the-Loop Annotation [11.4375764457726]
  This paper studies the neglected complementary problem of getting annotated data given a predictor. For the simple binary classification setting, we present the spectrum ranging from optimal general solutions to practical efficient methods.
  arXiv  Detail & Related papers  (2023-07-04T09:11:33Z)
• Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker [57.49330031751386]
  We find achievable information-theoretic lower bounds on loss in the presence of a test-time attacker for multi-class classifiers on any discrete dataset. We provide a general framework for finding the optimal 0-1 loss that revolves around the construction of a conflict hypergraph from the data and adversarial constraints.
  arXiv  Detail & Related papers  (2023-02-21T15:17:13Z)
• Pareto Optimization for Active Learning under Out-of-Distribution Data Scenarios [79.02009938011447]
  We propose a sampling scheme, which selects optimal subsets of unlabeled samples with fixed batch size from the unlabeled data pool. Experimental results show its effectiveness on both classical Machine Learning (ML) and Deep Learning (DL) tasks.
  arXiv  Detail & Related papers  (2022-07-04T04:11:44Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  We present a new discrete optimization method based on branch-and-bound (BnB) to obtain optimal decision trees. Our proposed algorithm Quant-BnB shows significant speedups compared to existing approaches for shallow optimal trees on various real datasets.
  arXiv  Detail & Related papers  (2022-06-23T17:19:29Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
  Federated learning (FL) is a promising privacy-preserving machine learning paradigm over distributed located data. We propose a learning-based reweighting approach to mitigate the effect of noisy labels in FL. Our approach has shown superior performance on several real-world datasets compared to various baselines.
  arXiv  Detail & Related papers  (2022-06-11T16:21:17Z)
• Sample Selection for Fair and Robust Training [28.94276265328868]
  We propose a sample selection-based algorithm for fair and robust training. We show that our algorithm obtains fairness and robustness better than or comparable to the state-of-the-art technique.
  arXiv  Detail & Related papers  (2021-10-27T07:17:29Z)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.