Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes

• URL: http://arxiv.org/abs/2312.15357v2
• Date: Wed, 31 Jul 2024 16:20:51 GMT
• Title: Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes
• Authors: Su Jia, Fatemeh Navidi, Viswanath Nagarajan, R. Ravi,
• Abstract summary: In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (i.e., decision tree) that identifies the true hypothesis. In this work, we study a fundamental variant of the ODT problem in which some test outcomes are noisy, even in the more general
• Score: 9.321976218862542
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (i.e., decision tree) that identifies the true hypothesis. This optimization problem has been extensively studied under the assumption that each test generates a deterministic outcome. However, in numerous applications, for example, clinical trials, the outcomes may be uncertain, which renders the ideas from the deterministic setting invalid. In this work, we study a fundamental variant of the ODT problem in which some test outcomes are noisy, even in the more general case where the noise is persistent, i.e., repeating a test gives the same noisy output. Our approximation algorithms provide guarantees that are nearly best possible and hold for the general case of a large number of noisy outcomes per test or per hypothesis where the performance degrades continuously with this number. We numerically evaluated our algorithms for identifying toxic chemicals and learning linear classifiers, and observed that our algorithms have costs very close to the information-theoretic minimum.

Related papers

• Submodular Information Selection for Hypothesis Testing with Misclassification Penalties [3.3444620077119436]
  We study the problem of selecting an optimal subset of information sources for a hypothesis testing/classification task. We propose a misclassification penalty framework, which enables nonuniform treatment of different misclassification errors. We prove that this metric is submodular and establish near-optimal guarantees for the greedy algorithms for both the information set selection problems.
  arXiv  Detail & Related papers  (2024-05-17T17:31:02Z)
• Globally-Optimal Greedy Experiment Selection for Active Sequential Estimation [1.1530723302736279]
  We study the problem of active sequential estimation, which involves adaptively selecting experiments for sequentially collected data. The goal is to design experiment selection rules for more accurate model estimation. We propose a class of greedy experiment selection methods and provide statistical analysis for the maximum likelihood.
  arXiv  Detail & Related papers  (2024-02-13T17:09:29Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity. An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation [80.07065346699005]
  It is widely assumed that the optimal noise distribution should be made equal to the data distribution, as in Generative Adversarial Networks (GANs) We turn to Noise-Contrastive Estimation which grounds this self-supervised task as an estimation problem of an energy-based model of the data. We soberly conclude that the optimal noise may be hard to sample from, and the gain in efficiency can be modest compared to choosing the noise distribution equal to the data's.
  arXiv  Detail & Related papers  (2023-01-23T19:57:58Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  We show that deviating from this assumption can actually lead to better statistical estimators. In particular, the optimal noise distribution is different from the data's and even from a different family.
  arXiv  Detail & Related papers  (2022-03-02T13:59:20Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Statistical Hypothesis Testing for Class-Conditional Label Noise [3.6895394817068357]
  This work aims to provide machine learning practitioners with tools to answer the question: is there class-conditional flipping noise in my labels? In particular, we present hypothesis tests to check whether a given dataset of instance-label pairs has been corrupted with class-conditional label noise.
  arXiv  Detail & Related papers  (2021-03-03T19:03:06Z)
• Test Score Algorithms for Budgeted Stochastic Utility Maximization [12.360522095604983]
  We extend an existing scoring mechanism, namely the replication test scores, to incorporate heterogeneous item costs as well as item values. Our algorithms and approximation guarantees assume that test scores are noisy estimates of certain expected values. We show how our algorithm can be adapted to the setting where items arrive in a fashion while maintaining the same approximation guarantee.
  arXiv  Detail & Related papers  (2020-12-30T15:28:41Z)
• Algorithms for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference [2.169755083801688]
  We propose greedy algorithms to solve the robust causal inference test instances from observational data with continuous outcomes. By leveraging the structure of the feasibility formulation, we develop greedy schemes that are efficient in solving robust test problems.
  arXiv  Detail & Related papers  (2020-12-22T16:12:11Z)
• Cross-validation Confidence Intervals for Test Error [83.67415139421448]
  This work develops central limit theorems for crossvalidation and consistent estimators of its variance under weak stability conditions on the learning algorithm. Results are the first of their kind for the popular choice of leave-one-out cross-validation.
  arXiv  Detail & Related papers  (2020-07-24T17:40:06Z)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  Group testing is a well-studied problem with several appealing solutions. Recent biological studies impose practical constraints for COVID-19 that are incompatible with traditional methods. We develop a new method combining Bloom filters with belief propagation to scale to larger values of n (more than 100) with good empirical results.
  arXiv  Detail & Related papers  (2020-07-21T19:31:41Z)

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.