Efficient and accurate group testing via Belief Propagation: an empirical study
This work addresses efficient and accurate screening for rare infections, such as in medical testing, but appears incremental as it builds on existing Belief Propagation techniques.
The paper tackled the group testing problem for screening rare infections by proposing a new test design using Belief Propagation, which significantly increased accuracy while minimizing the number of tests, with experimental results on practical problem sizes.
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.