|贝叶斯定理如何帮助赢得第二次世界大战破解日本海军密码JN25
1943年 ， 第二次世界大战期间 ， 美国和英国的加密分析师都在疯狂地试图破译轴心国军事分支发送的加密通信 。
本文插图
在这些努力中 ， 位于布莱奇利公园（Bletchley Park）的英国密码破解中心可能以Bombe的发源地而闻名 ， 该机器最终破解了臭名昭著的德国密码Enigma 。 尽管孟买及其后继模型受到了大多数公众的关注 ， 但如果没有统计方法的支持 ， 他们的努力往往是徒劳的 。 本文的目的是首先介绍一种方法 ， 即贝叶斯推理 ， 首先介绍其背后的理论 ， 然后概述其如何用于破解Axis密码 。
本文插图
第一部分将致力于打破日本海军密码JN 25 ， 而第二部分将概述贝叶斯推理在破解《谜》中的作用 。 该报告的大部分内容基于爱德华·辛普森（Edward Simpson）撰写的一篇文章 ， 该文章是在Bletchley Park工作的代码破坏者之一 。 本文试图通过回顾贝叶斯形式主义并执行仅在Simpson文章中隐含的大部分数学运算 ， 来使该主题更易于访问 。
定理
像许多其他著名理论一样 ， 贝叶斯定理非常简单：
本文插图
该公式本身易于导出 ， 并且在贝叶斯统计之外具有许多应用 。 但是 ， 它的简单性可能是骗人的 ， 因为大多数定理的能力在于对涉及的概率P的解释 。 几个世纪以来一直存在于贝叶斯定理的真正争议在于它的用法挑战了更传统的常客主义方法 。 所谓的常客将事件的可能性定义为''在许多试验中其相对频率的极限'' 。 贝叶斯主义者将概率解释为个人信念的量度 。
有人可能会问 ， 他们怎么敢在数学理论中包含主观信念 。 说出这种批评 ， 肯定会有好伙伴 。 许多统计重量级人物 ， 包括Fisher和Pearson ， 都基于相似的论点放弃了对概率的贝叶斯解释 。
要真正理解两种方法之间的区别并能够通过公正的判断 ， 让我们考虑以下示例：
想象一个朋友向你挑战掷硬币游戏 ， 并立即产生她想使用的硬币 。 在同意此游戏之前 ， 你本性相当可疑 ， 所以想确定她递给您的硬币是公平的 ， 即它落在头和尾上的机会是相等的 。
惯常做法
一个常客将这个问题作为假设检验 ， 用零假设H?进行解释：硬币是公平的 ， 而替代假设H?不是 。 然后 ， 她将决定进行多次试验（例如= 100）和置信度（例如 = 0.05） 。 翻转硬币次后 ， 将记录结果 。 如果我们让表示观察到正面的次数 ， 并且硬币落在正面上的概率 ， 则按照二项式分布 ， 得出特定结果的概率为：
本文插图
给定置信度之后 ， 她可以计算拒绝区域 ， 这意味着可以安全拒绝否定假设H?：= 0.5的间隔 。 可以通过求解获得该区域
本文插图
* 。 值得庆幸的是 ， 过去人们已经解决了这类问题 ， 因此与其直接自己解决方程式 ， 不如直接在表中查找其解决方案或使用任何统计软件为她提供答案 。 事实证明 ， 对于此问题 ， * = 10 ， 因此如果| ?50 |> 10 ， 或者等效地如果40 <40或> 60 ， 则H?可以被拒绝 。
让我们假设在100次硬币翻转中 ， （=）73成为正面 。 现在 ， 常客可以得出结论：该硬币已被操纵 ， 并且得出错误结论的可能性小于5％（置信度） 。
贝叶斯方法
支持贝叶斯统计的公司您进入了现场 。 您对''时间浪费''感到震惊 ， 并建议所有这些工作都可以通过更少的试验来完成 。 要了解您如何进行 ， 请首先回顾一下贝叶斯定理：
本文插图
注意 ， 我们已经用更有意义的符号和replaced替换了变量A ， B 。 表示模型的参数 ， 在本例中只是is的概率 ， 这是所用硬币固有的特性以及我们试图推断的未知值 。 代表观察到的数据 ， 即硬币落在正面和反面的次数 。
· （ |）是给定证据或数据 的概率 。 换句话说 ， 我们的硬币落在头部上一定次数后具有特定值的概率 。 这称为后验 。
· （| ）回答以下问题：观察给定的数据what的可能性是多少？这也是常客计算的东西 ， 称为可能性 。
· （）是统计学家对any在观察任何数据之前 different的不同值具有多大可能性的信念 。 通常称为先验模型
· （）通常称为边际函数 ， 它描述观测数据的概率 ， 而与模型参数无关 。 它可以确保后验分布是规范化的 ， 但是我们经常可以找到避免对其进行直接计算的方法 。
我们需要做的第一件事是确定一个描述投币实验的模型 。 和以前一样 ， 二项分布是我们选择的功能：
本文插图
数据D包括抛掷数和头部数 。 确定了可能性之后 ， 我们现在必须选择一个先验 。 请记住 ， 先验特征是统计学家在看到任何数据之前对参数belief的信念 。 因此 ， 如果我们要与一个值得信赖的朋友打交道 ， 我们作为贝叶斯人可以选择一个先验先验 ， 先验先验在 = 0.5（公平硬币的价值）附近有一个尖峰 ， 如橙色曲线所示 。 如果我们的朋友过去曾试图欺骗我们 ， 我们可能会更倾向于选择蓝色曲线 。 它更宽 ， 因此对any的任何特定值的信任程度降低 。
本文插图
正如您可能已经注意到的那样 ， 我们没有写下任何先前的方程式 。 不幸的是 ， 贝叶斯推理中涉及的数学可能非常棘手 。 通常 ， 积分无法通过分析来计算 ， 因此必须求助于诸如蒙特卡洛采样之类的数值工具 。 因此 ， 我们将依靠图来发展对贝叶斯统计的直观理解 。
比方说 ， 在6次抛掷中 ， 硬币正面落了4次 。 使用''低信任度''先验 ， 后验分布（ |）将如下所示：
本文插图
如您所见 ， 由于头部出现的频率是尾部的两倍 ， 因此分布已转移到更大的值 。 我们可以将似然项解释为作用于先验分布的过滤器 ， 仅让的值或多或少地与数据less一致 。
分布仍然相当广泛 ， 因此我们得出结论 ， 为了做出可靠的推断 ， 我们需要更多的样本 。 经过20次抛掷并观察了15次头部之后 ， 后部看起来像这样：
本文插图
我们可以高度肯定地得出该硬币被操纵的结论 ， 而且我们能够比普通人少投掷80枚硬币 。 谈谈有效利用资源！
现在您应该同意和我们的朋友一起玩吗？要看 。 如果她允许您选择正面还是反面 ， 请押头！但是 ， 如果她坚持要自己挑头 ， 也许是时候找到一个新朋友了……
实际上 ， 可以计算出该游戏的有利版本的预期收益：如果我们押一美元 ， 我们的预期收益为
本文插图
由于我们不知道的确切值 ， 因此需要对它的概率分布进行积分：
本文插图
对于最后一个表达式 ， 我们实际上不需要计算任何积分 。 为了在后验分布下获得the的期望值（均值）的粗略近似值 ， 只需查看所述分布就可以找到??≈0.7（精确值约为0.708） 。 所以
本文插图
每次抛硬币的预期投资回报率约为40％ ， 我会说''去吧'' 。 但是在押注所有资金之前 ， 请确保您已意识到赌徒的破产 。
本文插图
日本海军密码— JN 25
日本视角
本文插图
日本海军在第二次世界大战期间编码信息的方式非常简单 。 发件人将使用密码簿（I）将其消息的每个单词转换为五位数的数字 。 作为安全措施 ， 这五个数字的总和总是可以被3整除 。 虽然给日本人提供了一种确保他们的消息已经无误传输的方法 ， 但是这种措施将极大地帮助盟军解码被拦截的消息 。 但是稍后会更多 。
对纯文本进行编码之后 ， 发送者将查阅加密表以获取所谓的添加剂（II） 。 这些五位数字将被添加（非携带）到代码中以产生最终的加密消息（III） 。 接收者可以访问相同的代码簿和附加信息 ， 并且可以通过颠倒上述过程来简单地解码消息 。
联盟观点
收到一组截获的消息后 ， 联盟的密码分析师的任务是找出正确的添加剂 。 同时 ， 所谓的书籍制作者将尝试依靠语言和组合技巧的结合来复制日语代码书 。
由于加密分析师只能获得有限的证据 ， 即给定数量的被拦截消息 ， 因此他们所希望的最好是对消息背后最可能的添加剂做出概率陈述 。 因此 ， （贝叶斯）统计数据特别适合解决此问题 。
本文插图
解密过程将从一组已知具有相同添加剂的侦听消息（IV）开始 。 据说这些消息是''深度''的 ， 人们会说这是消息的''深度'' 。
五位数密码彼此不同 ， 并记录结果（始终选择5555以下的数字） 。 该过程背后的逻辑是 ， 利用编码消息之间的差异 ， 潜在的添加剂将被抵消 。 盟军已经了解了日本法典的一部分 ， 并且许多法典集团都是众所周知的 。 这些被称为''好群体'' ， 并与它们的（非携带）差异（V）一起制成表格 。 如果已知50组 ， 则必须计算和记录1225个差异 。
密码分析人员将比较从截获的消息计算得出的差异与从好的组得出的差异 。 如果找到匹配项（在我们的案例中为22571 ， 以红色显示） ， 则计算出假设的添加剂（以绿色显示） 。
最后也是最重要的任务是测试这种假想添加剂的有效性 。 第一步 ， 从每个消息（VI）中对应的编码词中减去添加剂 。 如果生成的代码（以蓝色显示）违反了''被3整除''的规则 ， 则可以迅速丢弃添加剂 ， 从而为盟军节省了大量时间 。 通常 ， 多种潜在的添加剂会通过该测试 ， 因此使用统计分析来确定其相对强度 。 作为真实添加剂的证据 ， 密码分析人员将在上述测试中使用任何其他良好基团的存在 。 数学计算如下：
让我们将note表示为发现的添加剂为真 ， 而则为不表示 。 我们想根据添加了（|）的良好组的数据来确定后验概率 。
本文插图
如果我们只对优势比感兴趣（真与假） ， 则分母中的边际（）抵消：
本文插图
没有关于A的概率的任何先验知识 ， 总是可以使用为两个事件分配相等概率的先验 ， 即（）= 0.5 。 等式中的最后一项 。 从而抵消 ， 剩下的就是确定似然比 ， 这很容易获得 。 （请注意 ， 如果我们有任何理由相信我们是根据正确的添加剂进行处理的 ， 则除了存在良好群体以外的证据以外 ， 我们总是可以修改先验知识以反映这一信念 。 ）
例如 ， 让我们考虑可以在消息2中恢复的良好组32151 。 如果98213不是真正的加法器 ， 则32151只是一个随机的五位数 。 该数字出现的可能性为1 /10? ， 但是 ， 由于该数字需要检查'' 3分频''规则 ， 因此我们获得（32151 |?）= 3 /10? 。
如果98213是真正的加法器 ， 则似然（32151 |）由32151的相对出现频率给出（''车队''） 。 当然 ， 诸如'' Ship''或'' Weather''之类的词比诸如'' Attack''之类的词出现得更多 。 在正确的统计处理中需要考虑到这一点 ， 因为更频繁的用语为该假设增加了更多的证据 。 就本示例而言 ， 让我们假设每个第80个截获单词是'' Ship'' ， 每250个捕获单词是'' Fleet'' ， 那么加法运算符98213的总证据将计算为：
本文插图
从技术上讲 ， 商品组列表中未包含的代码也会为上述产品添加因素 。 但是 ， 由于这些因素仅略小于一个 ， 因此可以节省时间 ， 可以安全地忽略它们 。
作为最后的简化技巧 ， 可能性将被转换为对数值 ， 将复杂的乘法交易为简单的加法 。 每个好组的对数似然率将预先制成表格 ， 以便员工可以简单地查找值 ， 并简化添加剂的测试过程 。 此程序的主要优点之一是 ， 测试添加剂的工作量较大且重复性很高 ， 可以将其外包给只有有限数学知识的人员 。 对于边缘案例或非常重要的消息 ， 只需征询专家意见 。
结论
【|贝叶斯定理如何帮助赢得第二次世界大战破解日本海军密码JN25】我希望我能对贝叶斯推断有所启发 ， 并说明如何在布莱奇利公园使用该推断解密JN25 。
推荐阅读
- 米歇尔·戴斯玛克特|海奥华预言的真相，地球人被带到九级文明，揭开神话背后的秘密
- 茶香四溢的慕斯蛋糕
- 埃隆·马斯克|马斯克薛其坤对谈：火星地球各有生存之道
- 尼尔·戴维斯|什么？地球曾经没有泥土？！直到这种生物的出现，旧貌换新颜
- 俄罗斯|上月一艘破冰船驶往江苏，预示俄罗斯将成气候变暖最大赢家？
- 尼斯湖水怪|今年尼斯湖水怪第四次官方目击，出现1分41秒，有两个黑色驼峰
- 猎鹰9号|马斯克的猎鹰9号火箭刷新全球回收复用纪录，中国实现突破还要多久
- 詹姆斯·贝德福德|53年前被冷冻，等待2017年被复活的美国富豪，他的现状如何？
- 波力斯卡|“火星男孩”今年已经25岁了，他的预言，到底是不是真的？
- 阿斯利康疫苗|阿斯利康疫苗要“凉”？欧洲18国紧急叫停，是否致死尚无定论