(以后尽量少用公式直接用Latex的plain文本表示简单公式，因为看到的latex在线转换服务都不能让我满意，又要照顾到各个同步blog不同的奇葩问题，十分不爽。以后的以后有空找个靠谱的或自己写一个。。)
这是一个看起来很基础很简单的经典问题：假设所有的德国坦克是从1开始按自然数递增编号的，坦克的总数为N，也就是说坦克的最大编号为N。盟军在战斗中共随机俘获/击毁了k辆坦克，且这些坦克的最大编号为m，那么应当如何对N的大小进行估计？
本问题以应用于二战时对德军产能的实际估计而得名，在这个问题的解决上，基于统计的方法取得了非常大的成功，取得了惊人的准确成果。而这个基本问题的解决方法，体现了统计理论中频率学派与贝叶斯学派的不同。
一、原始问题
这个问题在Wikipedia上有详细的介绍和解法：
频率学派和贝叶斯学派对这个问题的理解和解法是不同的，但他们求解时都用到了下面这个显而易见的结论：
已知N和k，则观测到的最大值为m的概率为C(m-1,k-1)/C(N,k)，其中C(x,y)为从x中取y的组合数。即P(m|N,k)=C(m-1,k-1)/C(N,k)。
1. 频率学派
频率学派对原问题的结论是：
N=m(1+1/k)-1
这个结论有一个很直观的解释，就是平均来说观测到的k个序号应该是均匀等间隔的分布在1~N这个范围内的，而去掉观测到的最大的m，剩下的k-1个序号应该均匀等间隔的分布在1~(m-1)这个范围内，根据这个分布的间隔可以估计m距离最大值N的距离。
在上面的wikipedia的link里，推导用了一个很奇葩的方式（虽然它是对的。。），先求给定N，k情况下观测到的最大值的期望，再令这个期望等于m。于是这种方法得到的估计是一个无偏估计（估计值的数学期望与真实值相等），再说明这个估计是最小方差的无偏估计（MVUM）。
wiki页面里的置信区间计算（Confidence intervals部分）我也觉得不太能理解，是按给定N和k之后m的置信区间反推N的置信区间的。而且似乎假设了序号在1~N中为连续的实数分布。最终的结果，概率为r的置信区间是[m/q^{1/k}, m/p^{1/k}]，其中p=(1-r)/2，q=(1+r)/2。
我觉得既然m的分布式都有了，感觉可以直接通过分布式求出置信区间啊。而且如果想求0%置信区间就会发现问题：得到的区间这时是一个点，这个点与无偏估计不同，那这个点的值是什么意思呢。。
2. 贝叶斯学派
Bayes学派的解释就清晰多了，但丫需要先对N的先验概率分布进行假设，但现在我们对N没有任何先验知识，最幸福的当然是假设一个在所有自然数上的均匀分布，但这样会导致每个点概率都是0，所以采用的方法是假设N有一个最大值\Omega，这样用Bayes公式就可以方便的进行估计，得到给定m，k的情况下，N的概率分布，式子是这个：
注意这个式子里是用的n代替本文中的N。
如果在\Omega趋于无穷时上式的分母有限，可以去掉这个讨厌的\Omega，这样就幸福了。。但没有给出什么时候这个条件可以满足。。
几个简单的结论：所有数值中，概率最大的N的值（众数）为m，只有当k>=3时，N有有限的数学期望(m-1)(k-1)/(k-2)，k>=4时N有有限的方差。
对原始问题的一些讨论：
1. 总之觉得频率学派的计算和解释不好理解，因为我对频率分析的方法不够熟悉，而在我的知识体系里面，Bayes的推导非常靠谱。但当k=1时，频率学派可以给出一个很Reasonable的解为2m-1，而Bayes方法没有\Omega的话N的期望是无穷大。。
2. 重新写一下频率学派的无偏估计：N=m-1+m/k，Bayes的数学期望：N=m-1+(m-1)/(k-2)，两个式子只差最后一项，注意m一定大于k，所以m/k>1/2，所以Bayes的结果会较大，如果观测点的数目k越来最多，m也会越来越大，两者的值就很接近了。
3. 看起来两种方法的推导都是对的啊，为啥得到的结果会不一样呢？是因为求的东西不一样。频率学派是假设给定N，求m的数学期望，“无偏估计”是指在N确定的情况下，多次进行观测实验，对结果进行估计，得到的结果的数学期望就是真实值N；Bayes学派是认为观测m确定，求N的概率分布。
4. 等一下。。。上一条的解释里为什么没有提到k？m和k都是已知的一部分，数学上是两个地位等同的变量啊？再重新看看上一条的解释，如果把上一条中的"m"替换为"m和k"，对于Bayes学派来说仍然说得通，但是频率学派就有问题了：为什么没有求k的数学期望呢？上面说的“多次进行实验”是在k和N确定的情况下进行实验的，为什么k要确定呢？Things are getting a little interesting ... 试试把频率学派推导中的m和k交换一下，第一步要求m和N确定情况下k的概率P(k|N,m)，发现求不出来。。因为没有k的先验。。那为啥P(m|N,k)就可以求呢？为啥m就不需要先验呢？因为有了N和k，m的分布就唯一确定了，但是有了N和m，k的分布却无法知道。所以在频率学派的解释里，k和N被认为是确定的模型参数而非随机变量，而m是每次观测得到的随机变量。“无偏估计”是按每次观测m来说的。
5. 事情还没完。。。那按上面的解释，从频率学派的角度来讲，数学上N和k的地位就可以交换了，于是我们的问题如果换成：已知所有坦克的数量N和观测到的最大值m，估计观测的次数k。频率学派的解法应该是类似的。尝试解了一下，按原来的方法强制代入是可以求出估计值的：k=m/(N-m+1)，但这感觉应该不是无偏估计，因为k和m的关系是非线性的。按频率学派的思想求解k的最小方差的无偏估计，直观感觉可做，但应该会比较麻烦。而反过来，如果Bayes学派来回答这个问题，需要假设k的先验，按定义域最简单的应该是[1,m]这个区间内自然数上的均匀分布（但这听起来也不合理啊）。
二、频率学派与Bayes学派
这个问题的确可以反映出两者的很多区别，翻了翻一些相关的资料总结一下我的理解：
1. 可以把所有已知的未知的数值分成两部分，一部分是模型参数，一部分是观测到的数据。频率学派认为，模型参数是客观存在的，固定的，比如“火星上是否有生命”，要么有要么没有，只是我们不知道而已，而观测到的数据是在确定的模型参数下依模型决定的分布进行采样的结果。而Bayes学派认为参数也是随机变量，所以需要参数的先验分布，也就是人们对参数的先验知识，但有时这个先验分布本身又是带参数的，这些参数就是“超参数”了，这样有可能会有多层到"超超..参数"，比如LDA的各种变种，但最上层的参数我们仍然会认为是确定的，或者说，给一个确定的分布形式。
2. 看起来，如果把Bayes中最上层的“超参数”理解成模型参数的话，两者不就一样了？不是的，世界观的不同造成了方法论上的区别（这话还是很有道理的。。。），首先通常不会有频率学派的方法引入超参数，这本来就是个Bayes理论里的概念啊。。其次，频率学派更注重“点估计”（point estimation），得到一个待求参数的数值（无偏估计或MVUE），Bayes学派则会得到一个待求参数的分布，再计算期望方差什么的。对应的，频率学派可以用置信区间描述估计的准确程度，置信区间大约意思是这个确定的真实模型参数以概率r（比如95%）落入的区间范围。
3. 似乎从前频率学派是非常流行的，但慢慢Bayes学派在有方便描述的先验的领域取得了非常好的效果，方便引入domain knowledge，逐渐占了上风（这个理解可能会有偏颇）。
4. 似乎在概率推导时采用Bayes学派思想的很多，但evaluation中经常用到频率学派的置信区间，假设检验的计算方法。
参考文献：
英文：
三、原始问题的变化
一边看一边想到的。
1. 在坦克问题里观测到的序号是不会重复的，坦克被俘了就没了，下一次不会看到同样的坦克，如果每次记下序号之后再放回去（蛋疼。。。），也就是观测到的序号可以重复，结果会是如何？
不管对什么学派，都要把P(m|N,k)改为P(m|N,k)=(p(m,k)-p(m-1,k))/p(N,k)，这里p(x,y)为x中取y的排列数，用小写p与大写P的概率区分。后面的做法应该是相似的。
2. 如果在上面1的基础上，已知k次观测中每次观测得到的序号从小到大为m_1, ..., m_k（于是m_k就是原始问题中的m），结果会是如何？
情况又有点不一样了。。对于Bayes学派，后验概率为：当N>=m_k时，P(N|.)正比于1/N^k，N取其他值时为0，于是N的众数为m_k，k<=2时数学期望无穷大，k>2时有有限的数学期望，没仔细算，但这个数学期望（形式非常简单，一个求和除以一个求和）很可能和原来不一样，因为N的分布和原来不一样。这个期望有时为超越数，参见：
对于频率学派，我不会做。。。
What If英文原版：
No comments:
Post a Comment