1943年吉尔伯特和马绍尔群岛战役期间，美国海军SBD-5侦察机在华盛顿号和列克星敦号上空巡逻。介绍：贝叶斯统计和日本海军密码JN25。二战期间，美国和英国的密码分析师们都在竭力破译轴心国军队之间通信的密码。在这众多努力当中，位于布莱切利庄园的英国解码中心由于诞生了解码机“不列颠炸弹”(British Bombe)、破解了德国臭名昭著的恩尼格码密码机(ENIGMA)而闻名。
在不列颠炸弹和后续的模型机如此瞩目的同时，我们不能忽略统计方法的支持。这篇文章就将要介绍其中之一——贝叶斯方法、以及它是如何破解轴心国密码的。
布莱切利庄园的1号小屋。摄影：Toby Oxborrow，来源：Flickr。这篇文章主要基于曾经在布莱切利庄园进行解码工作的爱德华·辛普森所写的文章，笔者会用更易懂和正式的表述以及一些数学公式对其进行转述，主要对贝叶斯方法如何破译了日本海军JN25密码进行了介绍。
贝叶斯定理。贝叶斯定理像其他出名的理论一样，惊人的简单：这个公式本身很容易推导，而且在贝叶斯统计之外还有许多应用。然而，由于定理的大部分含义取决于对概率P涉及的概念的阐释，它并没有看起来那么简单。对于贝叶斯定理持续了几个世纪的争论，源于这个定理的用法挑战了更传统的频率论方法。当时所谓的频率学派将事件发生的概率定义为“多次试验下相关频率的极限”，而贝叶斯学派将概率阐释为个人主观信念衡量的结果。
提出这样质疑的大有人在：在数学理论当中怎么敢包含如此主观的内容？许多像费希尔、皮尔森这样德高望重的统计学家，都因为类似质疑而拒绝接受贝叶斯的概率阐释。为了理解两种方法之间的区别并做出合理的判断，我们来考虑下面这个例子：假如一个朋友邀请你玩个抛硬币的游戏，并主动提供了一枚用在游戏中的硬币。在答应之前，出于怀疑的本能，你应该会质疑他递出硬币的公正性——比如两面落地的机会不同。
频率学方法。
频率学派会将这个问题构造成一个假设检验，其中零假设代表硬币是公平的（两面落地机会相同），备择假设代表硬币不公平，再确定检验次数（比如100次）和置信度1-α（比如95%），记录抛出硬币100次每次的结果。
如果用k代表硬币正面朝上的次数，p代表正面朝上的概率，按照二项分布可以获得一个这样的概率结果：用置信度1-α可以算出对应的拒绝域，意思是可以放心推翻零假设（也就是p=0.5）对应的k的区间，可以通过下式求解出k*。
贝叶斯方法。但如果是贝叶斯学派，便会认为以上都是在“浪费时间”，问题本可以通过减少多次检验实现。在操作前，我们先回顾一下贝叶斯定理：其中将变量A、B替换成了有明确含义的标记θ和D。θ代表模型参数，在我们的例子中就是正面落地的概率p，它是硬币的固有特征，也是我们想求解的未知量；D代表观测数据，也就是硬币正面或反面落地的次数。
P(θ|D)是在给定证据或数据D的基础上发生θ的概率；也就是说这枚硬币的概率p，在给定正面落地次数后具有的特定值，称为后验概率(posterior)。P(D|θ)则是如果给定θ那么观测到D的可能性，也是频率学派计算的内容，称之为似然(likelihood)。P(θ)是统计者在观测数据前相信的θ对应的不同可能性值，通常被认为是先验概率(prior)模型。
P(D)通常被称为边缘概率(marginal)，描述观测到数据D的可能性，与模型参数无关，来保证后验分布是归一化的，但我们一般有方法避免直接计算。
首先需要设计一个抛硬币的实验模型。按照之前的内容我们选用二项分布函数描述“似然”：数据D同时包含投掷次数n和正面出现次数k。确定了似然后，需要选择一个先验概率，描述的是统计者在观测到任何数据前对θ的主观意念。
所以，如果对方是个非常值得信任的朋友（给出了一枚公平的硬币），那么作为贝叶斯学派，就会挑选几乎在θ=0.5附近的先验概率，如下图中尖锐的橘色曲线所展示的那样；而如果这个朋友早有捉弄别人的历史，那么就更可能会选择蓝色的曲线作为先验，这条曲线由于对任何θ可能的值都存在相信所以很宽。
你可能注意到了，我们还没有给出先验概率的等式。
事实上，包含贝叶斯方法的数学相当棘手，通常的积分不能被解析计算，只能求助于蒙特卡洛等数值工具。于是为了直观理解贝叶斯统计，我们只能依赖图像。假设投掷6次硬币，其中四次正面落地。选择信任度低的那个先验概率，那么后验分布P(θ|D)则会表现为这样：可以看到，因为正面出现的次数是背面的两倍，分布向更大值的θ偏移。我们可以将“似然”理解为对先验分布的过滤器，只筛选出比较符合数据D的θ值。
这个分布仍然很宽泛，为了获得更可靠的参考，需要更多样本。进行20次投掷后，观察到15次正面的后验概率大概如此：在比频率学派要求的投掷次数少80次时，我们便可以颇为肯定硬币被动了手脚。大大提高了资源利用效率！所以这个游戏应该玩下去么？取决于选择正面还是反面——当然是要选择正面！
如果这位朋友坚持自己选择正面，那是时候该绝交了……我们甚至还可以计算出这个游戏的期望收益，如果用1元给正面下注，那回报分布是：￥由于不知道θ的确切值，期望回报需要对概率分布积分：￥￥观察最后一个式子发现，实际上不需要计算积分，通过粗略近似例子中后验分布θ的期望值（均值）可以发现E(θ)≈0.7（实际上是0.708），那么：￥￥也就是说，每次抛掷硬币的预期回报率是40%，大概可以试试，不过在赌上全部身家之前，请先了解一下赌徒破产问题。
珍珠港遭受日本袭击后燃烧的亚利桑那号航空母舰。日本海军密码——JN25。二战期间日本海军对信息的编码方式相当直接：发件人用密码本(I)将消息中的每个单词转换成一个五位数。为保证安全，这些五位数都必须能被3整除。这样虽然可以保证日本在传输信息无误，但也帮助了同盟国解码这些信息。
对文本进行编码之后，发件人会查询一个叫做附加码(II)的密码表，将这五位数与密码求和（不进位），得到最终的加密信息(III)。接收者在收到信息后直接利用相同的密码本和附加码就可以对其进行解码。
同盟国方面。同盟国的密码分析师在截获一组消息后，需要找出正确的附加码；同时，所谓的破译员需要尝试通过语言和组合技术来重制日本的密码本。密码分析师获得的证据其实十分有限，可能只是一组截获的信息，最好的结果便是对信息背后最可能的附加码进行概率陈述。这时，（贝叶斯）统计便尤其有用。
解码的过程会从一系列已知具有相同附加码的截获信息(IV)开始。
记录下几个五位密码两两的差值，两个加密信息相减，可以将含有的附加码抵消。同盟国已经有一部分日本密码本的内容，知道了许多组编码，这些密码组被称为“好密码组”，和它们的不进位差值(V)一起制成表格。如果已知50组密码，那么可以计算出1225个差值。密码学家将会对比截获信息的差值和好密码组的差值。如果两者可以匹配（比如图中标红的22571），就会计算出一个假设的附加码（绿色数字）。
最终也是最重要的任务在于检验附加码的有效性。首先用每条加密码减去对应的附加码(VI)，如果获得的结果（图中蓝色数字）不能被3整除，那么就立即弃用这个附加码，可以节约大量时间。一般大量的备选附加码都可以通过这条检验，于是统计分析方法就会被用来确定其相对强度。
密码分析师会用已知的其他好密码组作为真附加码的证据，数学过程大致是这样的：如果用A代表“附加码为真”这个事件、A¯意思相反，我们需要确定数据加上附加码后符合好密码组的后验概率P(A|D)。
如果只关注真假概率的比例，那么分母上的边缘概率P(D)就会被消掉：如果对A的概率没有任何先验知识，通常会假设两个事件发生的概率相等，即将先验概率设置为P(A)=0.5，上面等式的最后一项就会被消掉。
如果有任何证据或好密码组支持这个附加码为真，那么就可以修改反映这种信念的先验概率。举个例子，考虑从信息2中恢复的密码32151属于好密码组的情况。如果98213并非真的附加码，那么32151只是一个随机五位数，这件事发生的概率是1/10?，如果再算上之前“整除3”条件的检验，可以得到的概率为P(32151|A¯)=3/10?。
如果98213是一个附加码，那么32151（“舰队”）出现的相对频率可以得出似然P(32151|A)。在统计分析中需要考虑，像“船”、“天气”这样的单词出现的次数显然多于“袭击”，使用频率高的词组对这个假设会增加更高的证据率。
比如在截获的词语中，每八十个单词会出现一个“船”，而“舰队”每250个词出现一次，那么98213是一个附加码的总证据率就可以计算：严格来说，不属于好密码组的密码也会增加到上面的乘式当中，只不过为了节约时间，这个略小于1的值也可以不算。
最后一个化简技巧是，似然还可以转化成对数值，来将复杂的乘法转换为简单的加法。提前将每个好密码组的似然对数值制成表格，方便员工查找和测试各个数字，降低对劳动力的数学要求。
结论。希望我对贝叶斯方法以及其如何应用在布莱切利庄园破解JN25上有了一些介绍，如果你感兴趣，可以看看爱德华·辛普森本人撰写的文章。