グループテスト
Machine learning is a field of computer science that has many software applications such as DNA classification, fraud detection and targeted advertising. One of the main subfields of machine learning is the 'learning by examples' problem, where the task is to approximate some unknown function when given its value at a number of specific points. As outlined in this section, this function learning problem can be tackled with a group-testing approach.
In a simple version of the problem, there is some unknown function, f : { 0 , 1 } N → { 0 , 1 } {\displaystyle f:\{0,1\}^{N}\to \{0,1\}} where f ( x ) = a ⋅ x {\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}} , and a ∈ { 0 , 1 } N {\displaystyle {\textbf {a}}\in \{0,1\}^{N}} (using logical arithmetic: addition is logical OR and multiplication is logical AND).
An unfortunate property of this method is that, although it is easy to tell if the data has been modified, there is no way of determining how: that is, it is impossible to recover which part of the data has changed.
One way to get around this limitation is to store more hashes – now of subsets of the data structure – to narrow down where the attack has occurred. However, to find the exact location of the attack with a naive approach, a hash would need to be stored for every datum in the structure, which would defeat the point of the hashes in the first place. (One may as well store a regular copy of the data.
An important property of this algorithm is that it never creates false negatives, though a false positive occurs when all locations with ones in the j-th column of M {\displaystyle M} (corresponding to a non-defective item j) are "hidden" by the ones of other columns corresponding to defective items.
The COMP algorithm requires no more than e d ( 1 + δ ) ln  ( n ) {\displaystyle ed(1+\delta )\ln(n)} tests to have an error probability less than or equal to n − δ {\displaystyle n^{-\delta }} . This is within a constant factor of the lower bound for the average probability of error above.
doi:10.1111/j.0006-341X.1999.00231.x. PMID 11318160.
↑ Chen, Hong-Bin; Fu, Hung-Lin (April 2009). “Nonadaptive algorithms for threshold group testing”. Discrete Applied Mathematics 157 (7): 1581–1585. doi:10.1016/j.dam.2008.06.003.
↑ De Bonis, Annalisa (20 July 2007). “New combinatorial structures with applications to efficient group testing with inhibitors”. Journal of Combinatorial Optimization 15 (1): 77–94. doi:10.1007/s10878-007-9085-1.
↑ Hayes, J. (August 1978). “An adaptive technique for local distribution”. IEEE Transactions on Communications 26 (8): 1178–1186. doi:10.1109/TCOM.1978.1094204.
↑ Sterrett, Andrew (December 1957). “On the detection of defective members of large populations”.
Carry out steps 1 and 2 of the DD algorithm to obtain K {\displaystyle K} , an initial estimate for the set of defectives.
If K {\displaystyle K} explains every positive test, terminate the algorithm: K {\displaystyle K} is the final estimate for the set of defectives.
If there are any unexplained tests, find the "possible defective" that appears in the largest number of unexplained tests, and declare it to be defective (that is, add it to the set K {\displaystyle K} ). Go to step 2.
In simulations, SCOMP has been shown to perform close to optimally.
Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. ISBN 978-9810212933
Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2007), Lectures 7.
Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2010), Lectures 10, 11, 28, 29
Du, D., & Hwang, F. (2006). Pooling Designs and Nonadaptive Group Testing. Boston: Twayne Publishers.
Aldridge, M., Johnson, O.
During a pandemic such as the COVID-19 outbreak in 2020, virus detection assays are sometimes run using nonadaptive group testing designs. One example was provided by the Origami Assays project which released open source group testing designs to run on a laboratory standard 96 well plate.
In a laboratory setting, one challenge of group testing is the construction of the mixtures can be time-consuming and difficult to do accurately by hand.