Bloom Origami Assays: Practical Group Testing

• URL: http://arxiv.org/abs/2008.02641v1
• Date: Tue, 21 Jul 2020 19:31:41 GMT
• Title: Bloom Origami Assays: Practical Group Testing
• Authors: Louis Abraham, Gary Becigneul, Benjamin Coleman, Bernhard Scholkopf, Anshumali Shrivastava, Alexander Smola
• Abstract summary: 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.
• Score: 90.2899558237778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem usually referred to as group testing in the context of COVID-19. Given n samples collected from patients, how should we select and test mixtures of samples to maximize information and minimize the number of tests? Group testing is a well-studied problem with several appealing solutions, but recent biological studies impose practical constraints for COVID-19 that are incompatible with traditional methods. Furthermore, existing methods use unnecessarily restrictive solutions, which were devised for settings with more memory and compute constraints than the problem at hand. This results in poor utility. In the new setting, we obtain strong solutions for small values of n using evolutionary strategies. We then develop a new method combining Bloom filters with belief propagation to scale to larger values of n (more than 100) with good empirical results. We also present a more accurate decoding algorithm that is tailored for specific COVID-19 settings. This work demonstrates the practical gap between dedicated algorithms and well-known generic solutions. Our efforts results in a new and practical multiplex method yielding strong empirical performance without mixing more than a chosen number of patients into the same probe. Finally, we briefly discuss adaptive methods, casting them into the framework of adaptive sub-modularity.

Related papers

• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Nested Elimination: A Simple Algorithm for Best-Item Identification from Choice-Based Feedback [8.043586007062858]
  We study the problem of best-item identification from choice-based feedback. In this problem, a company sequentially and adaptively shows display sets to a population of customers and collects their choices. We propose an elimination-based algorithm, namely Nested Elimination (NE), which is inspired by the nested structure implied by the information-theoretic lower bound.
  arXiv  Detail & Related papers  (2023-07-13T05:05:30Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  We study sequential decision-making with known rewards and unknown constraints. As an application, we consider learning constraints to represent human preferences in a driving simulation.
  arXiv  Detail & Related papers  (2022-06-10T17:52:58Z)
• 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)
• Does My Representation Capture X? Probe-Ably [2.624902795082451]
  Probing (or diagnostic classification) has become a popular strategy for investigating whether a given set of intermediate features is present in representations of neural models. We introduce Probe-Ably: an extendable probing framework which supports and automates the application of probing methods to the user's inputs.
  arXiv  Detail & Related papers  (2021-04-12T20:43:10Z)
• 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)
• 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)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.