Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design

• URL: http://arxiv.org/abs/2004.12508v6
• Date: Wed, 22 Jul 2020 08:19:33 GMT
• Title: Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design
• Authors: Marco Cuturi, Olivier Teboul, Quentin Berthet, Arnaud Doucet, Jean-Philippe Vert
• Abstract summary: When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually. Our goal in this paper is to propose new group testing algorithms that can operate in a noisy setting.
• Score: 63.48989885374238
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually. Our goal in this paper is to propose new group testing algorithms that can operate in a noisy setting (tests can be mistaken) to decide adaptively (looking at past results) which groups to test next, with the goal to converge to a good detection, as quickly, and with as few tests as possible. We cast this problem as a Bayesian sequential experimental design problem. Using the posterior distribution of infection status vectors for $n$ patients, given observed tests carried out so far, we seek to form groups that have a maximal utility. We consider utilities such as mutual information, but also quantities that have a more direct relevance to testing, such as the AUC of the ROC curve of the test. Practically, the posterior distributions on $\{0,1\}^n$ are approximated by sequential Monte Carlo (SMC) samplers and the utility maximized by a greedy optimizer. Our procedures show in simulations significant improvements over both adaptive and non-adaptive baselines, and are far more efficient than individual tests when disease prevalence is low. Additionally, we show empirically that loopy belief propagation (LBP), widely regarded as the SoTA decoder to decide whether an individual is infected or not given previous tests, can be unreliable and exhibit oscillatory behavior. Our SMC decoder is more reliable, and can improve the performance of other group testing algorithms.

Related papers

• Is this model reliable for everyone? Testing for strong calibration [4.893345190925178]
  In a well-calibrated risk prediction model, the average predicted probability is close to the true event rate for any given subgroup. The task of auditing a model for strong calibration is well-known to be difficult due to the sheer number of potential subgroups. Recent developments in goodness-of-fit testing offer potential solutions but are not designed for settings with weak signal.
  arXiv  Detail & Related papers  (2023-07-28T00:59:14Z)
• Sequential Kernelized Independence Testing [101.22966794822084]
  We design sequential kernelized independence tests inspired by kernelized dependence measures. We demonstrate the power of our approaches on both simulated and real data.
  arXiv  Detail & Related papers  (2022-12-14T18:08:42Z)
• Cost-aware Generalized $\alpha$-investing for Multiple Hypothesis Testing [5.521213530218833]
  We consider the problem of sequential multiple hypothesis testing with nontrivial data collection costs. This problem appears when conducting biological experiments to identify differentially expressed genes of a disease process. We make a theoretical analysis of the long term behavior of $alpha$-wealth which motivates a consideration of sample size in the $alpha$-investing decision rule.
  arXiv  Detail & Related papers  (2022-10-31T17:39:32Z)
• Statistical and Computational Phase Transitions in Group Testing [73.55361918807883]
  We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease. We consider two different simple random procedures for assigning individuals tests.
  arXiv  Detail & Related papers  (2022-06-15T16:38:50Z)
• Efficient Test-Time Model Adaptation without Forgetting [60.36499845014649]
  Test-time adaptation seeks to tackle potential distribution shifts between training and testing data. We propose an active sample selection criterion to identify reliable and non-redundant samples. We also introduce a Fisher regularizer to constrain important model parameters from drastic changes.
  arXiv  Detail & Related papers  (2022-04-06T06:39:40Z)
• Group Testing with Non-identical Infection Probabilities [59.96266198512243]
  We develop an adaptive group testing algorithm using the set formation method. We show that our algorithm outperforms the state of the art, and performs close to the entropy lower bound.
  arXiv  Detail & Related papers  (2021-08-27T17:53:25Z)
• Efficient and accurate group testing via Belief Propagation: an empirical study [5.706360286474043]
  Group testing problem asks for efficient pooling schemes and algorithms. The goal is to accurately identify the infected samples while conducting the least possible number of tests. We suggest a new test design that significantly increases the accuracy of the results.
  arXiv  Detail & Related papers  (2021-05-13T10:52:46Z)
• Efficient Detection Of Infected Individuals using Two Stage Testing [0.0]
  Group testing is an efficient method for testing a large population to detect infected individuals. We characterize the efficiency of several two stage group testing algorithms. In the optimal setting, our testing scheme is robust to errors in the input parameters.
  arXiv  Detail & Related papers  (2020-08-24T23:05:10Z)
• 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)
• Crackovid: Optimizing Group Testing [7.895866278697778]
  Given $n$ samples taken from patients, how should we select mixtures of samples to be tested? We consider both adaptive and non-adaptive strategies, and take a Bayesian approach with a prior both for infection of patients and test errors.
  arXiv  Detail & Related papers  (2020-05-13T16:40:09Z)

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.