Efficient and accurate group testing via Belief Propagation: an empirical study

• URL: http://arxiv.org/abs/2105.07882v1
• Date: Thu, 13 May 2021 10:52:46 GMT
• Title: Efficient and accurate group testing via Belief Propagation: an empirical study
• Authors: AminCoja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Manuel Penschuck
• Abstract summary: 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.
• Score: 5.706360286474043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The group testing problem asks for efficient pooling schemes and algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately identify the infected samples while conducting the least possible number of tests. Exploring the use of techniques centred around the Belief Propagation message passing algorithm, we suggest a new test design that significantly increases the accuracy of the results. The new design comes with Belief Propagation as an efficient inference algorithm. Aiming for results on practical rather than asymptotic problem sizes, we conduct an experimental study.

Related papers

• Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes [9.321976218862542]
  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
  arXiv  Detail & Related papers  (2023-12-23T21:47:50Z)
• 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)
• Statistical Performance Guarantee for Subgroup Identification with Generic Machine Learning [1.0878040851638]
  We develop uniform confidence bands for estimation of the group average treatment effect sorted by generic ML algorithm (GATES) We analyze a clinical trial of late-stage prostate cancer and find a relatively large proportion of exceptional responders.
  arXiv  Detail & Related papers  (2023-10-12T01:41:47Z)
• 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)
• Group Testing with a Graph Infection Spread Model [61.48558770435175]
  Infection spreads via connections between individuals and this results in a probabilistic cluster formation structure as well as a non-i.i.d. infection status for individuals. We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model. Our results imply that, by exploiting information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when infection rate is high.
  arXiv  Detail & Related papers  (2021-01-14T18:51:32Z)
• 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)
• Application-oriented mathematical algorithms for group testing [0.0]
  Group testing is particularly efficient if the infection rate is low. The goal of this article is to summarize and extend the mathematical knowledge about the most efficient group testing algorithms.
  arXiv  Detail & Related papers  (2020-05-05T14:40:46Z)
• Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design [63.48989885374238]
  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.
  arXiv  Detail & Related papers  (2020-04-26T23:41:33Z)

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.