グループテスト
↑ Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, p. 574, Section 46: Pooling Designs, ISBN 978-1-58488-506-1, https://archive.org/details/handbookofcombin0000unse/page/
1 2 3 Dorfman, Robert (December 1943), “The Detection of Defective Members of Large Populations”, The Annals of Mathematical Statistics 14 (4): 436–440, doi:10.1214/aoms/1177731363, JSTOR 2235930, https://jstor.org/stable/2235930
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. ISBN 978-9810212933
In the simplest noisy case, where there is a constant probability, q {\displaystyle q} , that a group test will have an erroneous result, one considers a random binary vector, v {\displaystyle \mathbf {v} } , where each entry has a probability q {\displaystyle q} of being 1 {\displaystyle 1} , and is 0 {\displaystyle 0} otherwise. The vector that is returned is then y ^ = y + v {\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} } , with the usual addition on ( Z / 2 Z ) n {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} (equivalently this is the element-wise XOR operation). A noisy algorithm must estimate x {\displaystyle \mathbf {x} } using y ^ {\displaystyle {\hat {\mathbf {y} }}} (that is, without direct knowledge of y {\displaystyle \mathbf {y} } ).
Non-adaptive group-testing algorithms tend to assume that the number of defectives, or at least a good upper bound on them, is known. This quantity is denoted d {\displaystyle d} in this section. If no bounds are known, there are non-adaptive algorithms with low query complexity that can help estimate d {\displaystyle d} .
Dorfman tabulated the optimum group sizes for this strategy against the prevalence rate of defectiveness in the population.
After 1943, group testing remained largely untouched for a number of years. Then in 1957, Sterrett produced an improvement on Dorfman's procedure. This newer process starts by again performing individual testing on the positive groups, but stopping as soon as a defective is identified. Then, the remaining items in the group are tested together, since it is very likely that none of them are defective.
Next the algorithm looks at all the positive tests. If an item appears as the only "possible defective" in a test, then it must be defective, so the algorithm declares it to be defective.
All other items are assumed to be non-defective. The justification for this last step comes from the assumption that the number of defectives is much smaller than the total number of items.
Note that steps 1 and 2 never make a mistake, so the algorithm can only make a mistake if it declares a defective item to be non-defective. Thus the DD algorithm can only create false negatives.
Template:Db-a10
統計学や組み合わせ数学において, 何らかの検体を特定する作業を, 検体を個別に調べるのではなく, グループにまとめて調べるという作業に分割するようなやりかたをグループテストとよぶ。1943年にRobert Dorfmanによって最初に研究されて以来, グループテストは比較的新しい応用数学の分野であり、幅広い分野で実用化されており, 現在も活発に研究されている。
グループテストのよく知られている例は、直列に接続されたいくつかの電球の中で, いずれか1つだけが壊れている場合である。目的は、できる限り少ない検査(いくつかの電球を電源に接続すること)で、壊れた電球を見つけることである。単純な方法は、各電球を個別に検査することである。しかし、電球の数が多い場合は、電球をグループにまとめる方がはるかに効率的である。たとえば、電球を2つのグループに分けて, 片方のグループの電球を一度にまとめて接続することにより、壊れた電球がどちらのグループに入っているかを判断でき、たった1回の検査で半数の電球を除外できる。
The generalised binary-splitting algorithm is an essentially-optimal adaptive group-testing algorithm that finds d {\displaystyle d} or fewer defectives among n {\displaystyle n} items as follows:
If n ≤ 2 d − 2 {\displaystyle n\leq 2d-2} , test the n {\displaystyle n} items individually. Otherwise, set l = n − d + 1 {\displaystyle l=n-d+1} and α = ⌊ log 2  l / d ⌋ {\displaystyle \alpha =\lfloor \log _{2}{l/d}\rfloor } .
Test a group of size 2 α {\displaystyle 2^{\alpha }} . If the outcome is negative, every item in the group is declared to be non-defective; set n := n − 2 α {\displaystyle n:=n-2^{\alpha }} and go to step 1.
In this form, the theorem gives us an upper bound on the probability of success based on the number of tests. For any group-testing algorithm that performs t {\displaystyle t} tests, the probability of success, P ( success ) {\displaystyle \mathbb {P} ({\textrm {success}})} , satisfies P ( success ) ≤ t / log 2  ( n d ) {\displaystyle \mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}} . This can be strengthened to: P ( success ) ≤ 2 t ( n d ) {\displaystyle \mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}} .
Biometrika 62 (1): 181–193. doi:10.1093/biomet/62.1.181. hdl:11299/199154.
↑ Bar-Noy, A.; Hwang, F. K.; Kessler, I.; Kutten, S. (1 May 1992). A new competitive algorithm for group testing. 2. 786–793. doi:10.1109/INFCOM.1992.263516. ISBN 978-0-7803-0602-8
↑ Damaschke, Peter (2000). “Adaptive versus nonadaptive attribute-efficient learning”. Machine Learning 41 (2): 197–215. doi:10.1023/A:1007616604496.
↑ Stinson, D. R.; van Trung, Tran; Wei, R (May 2000). “Secure frameproof codes, key distribution patterns, group testing algorithms and related structures”. Journal of Statistical Planning and Inference 86 (2): 595–617. doi:10.1016/S0378-3758(99)00131-7.
↑ Colbourn, C. J.; Dinitz, J. H.; Stinson, D.
Combinatorial Orthogonal Matching Pursuit, or COMP, is a simple non-adaptive group-testing algorithm that forms the basis for the more complicated algorithms that follow in this section.
First, each entry of the testing matrix is chosen i.i.d. to be 1 {\displaystyle 1} with probability 1 / d {\displaystyle 1/d} and 0 {\displaystyle 0} otherwise.
The decoding step proceeds column-wise (i.e. by item). If every test in which an item appears is positive, then the item is declared defective; otherwise the item is assumed to be non-defective. Or equivalently, if an item appears in any test whose outcome is negative, the item is declared non-defective; otherwise the item is assumed to be defective.
This is called the information lower bound. This bound is derived from the fact that after each test, S {\displaystyle {\mathcal {S}}} is split into two disjoint subsets, each corresponding to one of the two possible outcomes of the test.
However, the information lower bound itself is usually unachievable, even for small problems. This is because the splitting of S {\displaystyle {\mathcal {S}}} is not arbitrary, since it must be realisable by some test.
In fact, the information lower bound can be generalised to the case where there is a non-zero probability that the algorithm makes an error.