應該怎樣理解bootstrap的結果可以通過λ=1的泊松過程來模擬？

12-30

最近看到數據流的bootstrap方法，是通過對每個到達的觀測生成一個服從λ=1的泊松分布的隨機整數，來判定這個觀測是以0次、1次還是2次或更多次入樣。
相信這兩者之間一定是存在某種聯繫，但是應該怎樣理解兩者之間的這種「巧合」呢？或者說，為什麼bootstrap的結果恰好就可以被這樣實現呢？

本文先介紹Bootstrap的標準流程，再列舉標準Bootstrap和Poisson Bootstrap的異同，最後說明為何Poisson Bootstrap在數據流(streaming)中的優點。

（一）、Bootstrap的標準流程：

Bootstrap其實就是反覆地從樣本中放回抽樣(sample with replacement)，從模擬的數據中計算統計量，並推斷統計量的分布的方法。其優勢在於它的非參數性(non-parametric)，即不需要假設樣本服從某種特定的分布。但其缺點在於計算複雜：需要不停的放回抽樣。簡而言之，它是利用粗暴的計算能力來解決統計量分布問題的非參數方法。

在每次抽樣中，每一個樣本都有可能沒有被抽到，抽到一次或抽到多次，其被抽到次數分布服從二項分布, $Bin(n,frac{1}{n})$ .而總體的聯合分布服從多項分布 $MultiNomial(n, frac{1}{n}, dots, frac{1}{n})$ . 因此，bootstrap實際上就是如何生成上述的多項分布。

由於bootstrap是「暴力解法」，當數據量足夠大時，它的計算就顯得過於複雜。舉例而言，它不可以被並行計算來生成上述多項分布，且在數據流(streaming)中，我們無法事先得知數據的大小(n).

（二）、Poisson Bootstrap及其與標準Bootstrap的異同：

Poisson Bootstrap是提出來進行獨立抽樣的方法。例如我們可以對每一個樣本獨立同分布的決定其被抽到的次數為 $Bin(n,frac{1}{n})$ ，而當n足夠大時，我們又有如下近似 $lim_{n ightarrow infty} Bin(n,frac{1}{n}) = Poi(1)$ . 因此，我們可以用Poisson的隨機數來決定樣本被取用多少次。而由於每一個樣本都是獨立生成的隨機數，我們可以並行生成來決定樣本。

然而，上述論證中每個樣本獨立的假設並不成立。而且由於在標準bootstrap中的取樣總量是確定的，每一個樣本被取的數量應該與其他樣本的值呈負相關(negatively correlated).因此，Poisson Bootstrap的一個弊病在於無法控制樣本大小。但當數據量足夠大時，樣本的數量應該和數據的總量差不多。

（三）、Poisson Bootstrap在數據流(Streaming)中的優點：

在數據流(streaming)問題中，生成多項分布的隨機數不僅僅是計算複雜，而是不可行的。因為在數據流中，我們無法確定樣本的大小。然而如果我們利用Poisson Bootstrap的方法，不僅它在數學上非常簡便，而且可以被並行運算。這種Bootstrap方法解決了大數據（N很大）與數據流（N不確定）的問題。

結論：可以證明，在Poisson Bootstrap下估計量的漸進分布比利用標準Bootstrap更加接近其真實的分布。因此，利用Poisson Boostrap並沒有在估計上有損失，並且由於其能夠並行運算反而獲得計算收益。

It can be shown that the asymptotic distribution of the estimator using this Poisson bootstrap is much closer to that of the standard bootstrap is to the true distribution of the estimator. Thus there really isn"t any price to pay in estimation for using independent Poisson sampling and much to be gained computationally by way of parallelism.

Reference:

[1] An introduction to the Poisson bootstrap

[2] Chamandy, Nicholas, et al. "Estimating uncertainty for massive data streams." Internal Technical Report, Google (2012).

Bootstrap是有放回的抽樣，本身每個觀測被選入的次數應該滿足多項分布，當樣本量N比較大的時候，可以認為每個觀測被選入的次數是一組獨立同分布的二項分布隨機變數。同時，N較大時，二項分布近似於lambda為1 的泊松分布(因為N * 1/N=1)，所以可以通過泊松分布去模擬。選擇泊松分布的原因是能降低計算量。