A Probably Approximately Correct Analysis of Group Testing Algorithms
Sameera Bharadwaja H. and Chandra R. Murthy · 2024
Read A Probably Approximately Correct Analysis of Group Testing Algorithms by Sameera Bharadwaja H. and Chandra R. Murthy (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00466.txt.
Introduction
Bharadwaja and Chandra Murthy analyze pooled testing through the lens of learning theory, in a 2024 paper. Group testing finds the few faulty or infected items in a crowd by testing mixed batches. When tests are fixed in advance and pools are random, the question is how many batches suffice.
The authors recast the search as learning a function, then apply the probably approximately correct framework, which tolerates a few misses at a stated confidence. They derive test counts for three popular decoding methods and compare them with older exact-recovery bounds, in theory and by simulation. Maps of the testing rate across accuracy and confidence levels let designers pick a method for their tolerance. Near-perfect answers, it turns out, need far fewer tests than perfect ones.
Catalog record
| CREATOR | Sameera Bharadwaja H. and Chandra R. Murthy |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-00466
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Probably Approximately Correct Analysis of Group Testing Algorithms Sameera Bharadwaja H. and Chandra R. Murthy Abstract We consider the problem of identifying the defectives from a population of items via a non-adaptive group testing framework with a random pooling-matrix design. We analyze the sufficient number of tests needed for approximate set identification , i.e., for identifying almost all the defective and non-defective items with high confidence . To this end, we view the group testing problem as a function learning problem and develop our analysis using the probably approximately correct (PAC) framework. Using this formulation, we derive sufficiency bounds on the number of tests for three popular binary group testing algorithms: column matching, combinatorial basis pursuit, and definite defectives. We compare the derived bounds with the existing ones in the literature for exact recovery theoretically and using simulations. Finally, we contrast the three group testing algorithms under consideration in terms of the sufficient testing rate surface and the sufficient number of tests contours across the range of the approximation and confidence levels. I Introduction Identifying a set of k defectives from a population of n items is an interesting problem. A näive solution is to test the items individually, which requires n tests. This approach is inefficient if n is very large or there are constraints on time-to-test, cost budget, or testing hardware and resource constraints. An alternative is to pool items together and run m<n tests in parallel, with each test pooling random subsets of the items together. These are collectively called group testing algorithms (or pool testing algorithms) and work as follows. The outcome of a group test is negative if and only if none of the defective items participate in that group test; it is positive otherwise. When k\ll n , which holds in many applications like identifying a rare disease from a set of blood samples, testing a population for an infection in the early stage of an epidemic, identifying defective industrial products in a high-yield production line, etc., this approach can help significantly reduce the sufficient number of tests needed. Group testing was first introduced by Dorfman in 1943 during world war II to test the prospective entrants into the US military for Syphilis [ 2 ] . Owing to its success, group testing has been adopted in diverse applications ranging from (other) infectious disease detection [ 3 , 4 ] to multiple access control protocols [ 5 ] , cognitive radios [ 6 ] , drug and DNA library scanning [ 7 , 8 , 9 , 10 ] , product testing [ 11 ] , etc. Group testing has gained renewed interest recently due to global developments related to COVID-19 [ 12 , 13 ] . For example, it is possibly applicable to monkeypox detection [ 14 ] and to scale-up testing to detect Khosta 2, a type of sarbecovirus [ 15 ] . Group testing methods can be categorized into adaptive and non-adaptive types [ 16 ] . In adaptive group testing, the tests are performed in multiple stages wherein the group design in the current stage depends on the test outcomes from the previous stage. Dorfman-style testing falls under this category. In contrast, in the non-adaptive method, all the required tests are performed in a single stage, followed by the application of a suitable decoding algorithm [ 17 , 18 , 19 ] to recover the individual item status (i.e., defective or non-defective). In this paper, we focus on random pooling-based non-adaptive group testing [ 6 ] . Here, the decision about which items will participate in which group test is predetermined and is encoded in a random binary test matrix denoted by \mathbf{A}\in\{0,1\}^{m\times n} [ 20 ] . The (i,j) -th element of \mathbf{A} , denoted by a_{ij} , takes the value 1 or 0 depending on whether the j -th item participates in the i -th group test or not, respectively. The item vector is denoted by \mathbf{x}\in\{0,1\}^{n} , whose j -th entry, denoted by x_{j} , takes the value 1 if the j -th item is defective, and 0 otherwise. In addition, the support of \mathbf{x} is denoted by the set \mathcal{K} such that |\mathcal{K}|=k , where |\cdot| denotes the cardinality of a set. Finally, the outcome of the i th group test is y_{i}=\vee_{j=1}^{n}~a_{ij}x_{j},~i\in[m] , where \vee denotes the boolean OR-ing operation. Thus, the outcome is 1 if the group test includes one or more defective items and is 0 otherwise. Once the group test outcomes ( y_{i},i\in[m] ) are collected, a decoding algorithm aims to output an item vector estimate denoted by \hat{\mathbf{x}}\in\{0,1\}^{n} . The estimate of the defective item set, \hat{\mathcal{K}} is then simply the support of \hat{\mathbf{x}} , i.e., the set of indices corresponding to the nonzero entries in \hat{\mathbf{x}} . Some of the well-known binary group testing (decoding) algorithms studied in this work include [ 17 , Chapter 2] [ 19 ] 1. Column Matching (CoMa), also called Combinatorial Orthogonal Matching Pursuit (COMP). 2. Combinatorial Basis Pursuit (CBP), also called Coupon Collector (CoCo) algorithm. 3. The Definite Defectives (DD) algorithm. Note that, under the group testing model described above, CoMa and CBP only make false positive errors, i.e., \hat{\mathcal{K}}\supseteq{\mathcal{K}} , while DD only makes false negative errors, i.e., \hat{\mathcal{K}}\subseteq{\mathcal{K}} [ 17 ] . We analyze these separately in the sequel. Now, when exact set identification is considered, the decoding algorithm succeeds when \hat{\mathcal{K}}=\mathcal{K} and fails otherwise. Let \mathbb{P}_{\mathbf{A}}\left(\hat{\mathcal{K}}\neq\mathcal{K}\right) denote the probability of error given the set of defectives, \mathcal{K} . Then, the average probability of error under a combinatorial setting can be written as [ 20 ] \mathbb{P}(\text{err})=\mathbb{P}_{\mathbf{A},\mathcal{K}}(\hat{\mathcal{K}}\neq\mathcal{K})=\frac{1}{{n\choose k}}\sum_{\mathcal{K}:|\mathcal{K}|=k}\mathbb{P}_{\mathbf{A}}(\hat{\mathcal{K}}\neq\mathcal{K}). (1) Characterizing \mathbb{P}(\text{err}) as a function of k , n , and m is helpful in using group testing for practical applications. For instance, one can ask: Given k and n along with an upper bound on \mathbb{P}(\text{err}) , what is the sufficient number of tests, m_{S} , required by a group testing algorithm? In the following subsections, we briefly discuss the existing work toward answering this question before presenting our main contributions. I-A Prior Work Under \delta^{\prime}\equiv\mathbb{P}(\text{err})=n^{-\delta},\delta>0 and k=o(n) , the authors in [ 18 , 19 ] show that an upper bound on the number of tests is ek(1+\delta)\log n and 2ek(1+\delta)\log n for CoMa and CBP algorithms, respectively. 1 1 1 \log denotes natural logarithm unless specified otherwise. Further, the linear programming (LiPo) decoder requires no more than O(k\log n) tests under the same conditions with the constant factor associated with the asymptotic expression being a function of (1\!+\!1/k) , \log k/\log n and \delta [ 19 ] . Similarly, the sufficient number of tests for DD and sequential COMP (SCOMP) algorithms is also C_{a}k\log n, with a decoder-dependent constant C_{a}>0 [ 17 ] . In addition, a lower bound on the required number of tests is (1-\delta^{\prime})k\log(n/k) (See [ 19 ] and references therein, e.g., [ 21 , 22 ] .) In the above works, the entries of the test matrix are chosen i.i.d. from the \text{Bernoulli}(p) distribution, where p\in(0,1) . Further, the author in [ 23 ] presents an improved converse bound for this Bernoulli-design group testing. Other test matrix designs have been considered and contrasted with the