群组测试：毒药谜题

问题背景

这个问题在统计学和组合数学领域被称为群组测试问题 (Group testing),问题源于二战时期，美国需要通过血样检测美军是否携带梅毒，但是血液检测耗时耗钱，将每个士兵的血液都检查一遍效率很低。考虑到携带梅毒的总归是少数，Rosenblatt 和 Dorfman 提出将全部待检测士兵的血样分组混合后再检测，如果混合后的血样没有病毒，可以推定整个组都没有病毒，如此便能够减少不必要的检测。

将以上问题标准化描述如下：

• 给定集合N，其中有n个个体，每个个体要么是正例 (Positive) 要么是负例 (Negative)，记其中正例个数为d。
• 目标：通过尽量少的测试次数，找出所有的负例。
• 群组测试 (Group testing)：在N 的一个子集上测试（与在每个个体上测试相对）。

这样做有一个前提：$d << n$；可以设想，如果一个集合 N 当中大多数都是正例，那你随便找个子集，大概率都是含有正例的，那么就不能达到排除一个子集的效果，这个方法就失去意义了。

Katona 在 1976 年介绍了一种矩阵表示法，只需要 $\log_2{n}$ 次测试即可检测出 n 个样本中的一个正例，并且证明的其最优性。这个方法就是被各个互联网公司面试题疯狂引用的 1000 瓶药中有一瓶有毒，要求用最少的小白鼠检测出这一瓶毒药的题目。我也刷过，但是不得不吐槽，起码对我来讲，倘若没见过这个题目的解法，要想自己独立思考出来，可以说是难如登天，即使有些人能够写下解法，但是这个“最优”一词，可能很少有人能说上来其中的原因。反正大加面试题抄来抄去，也没有认真想过为什么要出这么个面试题，可能面试官觉得自己已经背过了，不出给别人觉得浪费。

吐槽完了还是简单说说这个题目的解法，就免得部分同学再点到其他网页游览一圈了。将 1000 只老鼠用二进制的 $(1) _{10}$ 到 $(1000) _{10}$编上序号，需要 10 位二进制码，然后把序号第 1 位为 1 的药混合在一起喂给老鼠 1，....然后把序号第 10 位为 1 的药混合在一起喂给老鼠 10。假设老鼠 i 死掉了，那么可以推定毒药的编号的第 i 位是 1，把每只老鼠的实验结果综合起来，就能得到毒药编号的每一位，毒药就找出来了。另外，前述的此法所需测试次数 $\log_2{n}$ 实际上就是所需二进制编码的位数。

一般，对上述从 n 个样本中寻找一个正例的问题，很容易能想到的就是采用二分法去寻找，把样本分成两份，分别进行群组测试，那么只有一个能包含正例，所以，排除一半，对另一半进行检测····使用此法也能在 $\log_2{n}$ 次检测结束后找到解。不过此法与 Katona 的方法区别在于，此法是多阶段的决策 (adaptive Algorithm)，比如第二次对哪一拨进行测试，要根据第一次的测试结果来确定。但是 Katona 方法则不同，其在测试开始前即可确定全部的测试群组的划分 (non-adaptive Algorithm)。

---

以上的只是一些老生常谈的问题，可能大家都看过无数遍了，我为甚么又要提起这个问题，还要谁个博文呢？主要是我昨天参加了 IGG 的线上笔试题，这个公司不走寻常路，出了一个这个问题的加强版，也就是在 n 个样本中寻找 d 个正例。这种题一下子就触及到我这样的刷题党的知识盲区了，因为之前没见过，要现场想出个解法太难了。

但是当时我还是大致写了个方法，不过不严密，当时也想的比较混乱。大致思想如下，既然已知其中有 d 个正例，我直接把样本随机分为 d 份，然后分别进行群组测试，按照鸽笼原理和统计学常识，这些正例恰好每组一个的概率是不太大的，所以能够淘汰掉一些群组。一直重复这个过程就能够排除掉很多负例。但是达到一定程度 (在剩余样本里正例占比很大的时候)，就不能再采用分组测试了，应该采用单独测试。后来我去查阅文献，发现这个思想和文章[1]类似。

信息论下界

从信息论讲，这个问题 (仅有一个正例) 一定有一个下界。因为每次测试只有两个输出信息---正例 or 负例，因此进行 k 次测试最多表示 $2^k$ 种信息状态，因此，至少要 $\log_2{n}$ 次测试才能获得足够的信息，因此，下界为 $\log_2{n}$。 同理，对于 d 个正例的情况，下界为 $\log_2{n \choose d}$。当然，下界一般而言是难以达到的。

解法 1：可以简单地想到一种解法，利用二分法去解决，首先把 n 个样本分成两份进行检测，有毒（正例）的群组继续检测，没毒的部分排除，一直重复这个过程直到剩下的样本总数等于 d，就找到所有的正例了。这个方法实际上就是算法中常用的剪枝的思想，剪枝越早，效率越高，假设你运气好，没走几步就只剩下 d 个可疑样本了，那就直接求出结果了。再来看看它的复杂度，由于其中只有 d 个样本是正例，那么在二叉搜索树的某一个层上最多只有 d 个节点能被检测出正例，而二叉树的深度是$\log_2{n}$，所以复杂度为 $O(d \log_2{n} )$。而哪个 IGG 笔试的题目实际上就是要求这个复杂度，只能说考试总是这样，交卷了思维才会清晰起来，呵呵。

但是这个方法也不是没有问题，因为它是 adaptive 的，需要的时间复杂度是 $\log_2{n}$ ，也就是要进行至多 $\log_2{n}$ 次的试验。如果题目要求一次就测出来，那么就还需要一个提前决定测试分组的编码方案，并且在测试结果出来之后能够解码得出到底哪些是正例。由于我对类问题兴趣不大，所以暂时不想深究，有兴趣的可以去文献[3]尝试寻找答案。

最近比较忙，倘若日后有空再去看这个问题，如果你有了自己的见解欢迎分享给我，万分感谢。

//TODO

[1]: Li, Chou Hsiung (June 1962). "A sequential method for screening experimental variables". Journal of the American Statistical Association. 57 (298): 455–477. doi:10.1080/01621459.1962.10480672

[2]: Group_testing: https://en.wikipedia.org/wiki/Group_testing

[3]:Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. ISBN 978-9810212933.