UA MATH ECE636 信息論10 Group Testing簡介

• Group Testing
• • AGT
  • • Dworfman算法
    • Binary Search
    • Generalized Binary Search
  • Lower Bound

Group testing在工程、醫(yī)學(xué)、統(tǒng)計等領(lǐng)域都有廣泛的應(yīng)用。一個group testing的比較直觀的例子：假設(shè)有$N$個串聯(lián)的燈泡，其中有$d$個燒掉了，所以整串燈泡都不亮了。現(xiàn)在想把這$d$個燈泡檢測出來，如果每個燈泡都檢查的話就需要檢測$N$個，而group testing想要回答的問題是最少需要檢測幾個燈泡才能把這$d$個燒掉的檢測出來？

Group Testing

假設(shè)$X_1,?,X_N$是一組隨機(jī)樣本，$X_1,?,X_N{～}_{iid}Ber(p),p<<1$。記
$$d=\sum _{i=1}^N{X}_i$$
$d$表示所有取值為1的樣本數(shù)（假設(shè)$d$已知），記$T$表示需要做的檢測的數(shù)量。對應(yīng)上面的例子，這$N$個樣本就是$N$個串聯(lián)的燈泡，$d$就是燒掉的燈泡的數(shù)量，一次檢測可以就是用電壓表測一下每個燈泡兩端的電壓，$T$就是需要檢測的燈泡的數(shù)量，顯然$T\le N$。考慮到$p<<1$，也就是燒掉的燈泡數(shù)量很少，我們比較容易想到的是pooling的思想，也就是檢測多個燈泡兩端的電壓，如果是220V就說明其中有燒掉的，如果明顯小于220V說明沒問題。

用pooling的思想做Group testing的方法分為兩大類，adaptive group testing和non-adaptive group testing。Adaptive group testing（AGT）的做法是序貫地對樣本的子集做檢測。。因為AGT的序貫性，它的速度是比較慢的，所以樣本數(shù)目比較大的時候一般不用這個。Non-adaptive group testing（NAGT）的做法是并行地對樣本的子集做檢測，所以速度較快，大樣本時一般用這種操作。但相比AGT，NAGT需要的檢測的數(shù)量更多。

AGT

Dworfman算法

這個算法是1943年就提出來了的，比較古老的一種算法。它的思想是把$N$個樣本分成$\sqrt{Nd}$組，每一組有$\sqrt{N/d}$個樣本，對每一組做一次檢測，一共需要做$\sqrt{Nd}$次檢測。假設(shè)檢測到$k$組取值為1的樣本，則$1\le k\le d$，接下來對這$k$組中的每一個樣本做檢測，找出所有取值為1的樣本，一共需要做$k\sqrt{N/d}$次檢測。從而這個算法需要做的檢測次數(shù)為
$$T=\sqrt{Nd}+k\sqrt{\frac{N}{d}}$$
顯然
$$\sqrt{Nd}+\sqrt{\frac{N}{d}}\le T\le 2\sqrt{Nd}$$

Binary Search

如果$d=1$：首先對$N$個樣本做檢測，如果結(jié)果是0，說明$d=0$，如果結(jié)果是1，將樣本均分為兩個group，每個group有$N/2$個元素，然后對每個group做檢測，如果結(jié)果是0，說明這個group沒有取值為1的樣本，如果結(jié)果是0，再將樣本均分為兩個group。。。重復(fù)這個操作，最終找到取值為1的那個樣本。根據(jù)這個算法，我們需要
$$2^T=N?T=ceil({\log }_{2}N)$$
其中$ceil()$表示不超過括號內(nèi)的數(shù)的最小整數(shù)。因此Binary滿足
$$T=ceil({\log }_{2}N)$$

如果$d>1$：檢測到第一個取值為1的樣本，將它移走，對剩下的$N?1$個樣本做Binary Search，重復(fù)這個過程，直到找到$d$個取值為1的樣本。因此
$$T=ceil({\log }_{2}N)+?ceil({\log }_{2}N?d)\le d\times ceil({\log }_{2}N)=O(d{\log }_{2}N)$$
因為$d<<N$，所以通常Binary Search需要的檢測數(shù)目比Dworfman算法更少。

Generalized Binary Search

將$N$個樣本分為$d$個group，則每個group中有$N/d$個樣本，在每個group中做binary search，假設(shè)第$j$個group中有$k_j$個樣本取值為1，則
$$T=k_1{\log }_2\frac{N}{d}+?+k_d{\log }_2\frac{N}{d}=d{\log }_2\frac{N}{d}$$
顯然這個比Binary Search更優(yōu)秀。

Lower Bound

下面的定理給出了GT最優(yōu)的可能性，由此可以看出generalized binary search是AGT中一種最優(yōu)的算法。

定理
$$T\ge d{\log }_2\frac{N}{d}$$

證明

我們嘗試用信息論的語言來描述這個問題。假設(shè)我們用了$T$個檢測，則每個檢測返回的結(jié)果是0或者1，相當(dāng)于就是收到了一個字長為$T$的binary code，則這個binary code能表示的信息的總數(shù)為$2^T$。而$d$個取值為1的樣本在所有樣本中的分布情況可以理解為字長為$N$的binary信號中有$d$個字是1，這種編碼方式可以表示$C_N^d$種信號。為了保證binary code能夠表示所有的信號：
$$2^T\ge C_N^d?T\ge {\log }_2{C}_N^d\ge T\ge {\log }_2(N/d{)}^d=d{\log }_2\frac{N}{d}$$

這里面用到了不等式
$$C_N^d=(N/d{)}^d$$
它其實非常直觀
$$C_N^d=\frac{N}{d}\frac{N?1}{d?1}\frac{N?2}{d?2}?\frac{N?(d?1)}{d?(d?1)}$$
根據(jù)小學(xué)數(shù)學(xué)分式的性質(zhì)
$$\frac{N?n}{d?n}\ge \frac{N}{d},n<d$$
用到的那個不等式成立。

總結(jié)

以上是生活随笔為你收集整理的UA MATH ECE636 信息论10 Group Testing简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。