马尔可夫链和香农信息论

马尔可夫的原始研究属于纯粹抽象的概率论练习。那么，它有哪些应用呢？马尔可夫在一封信中写道：“我只关心纯粹的分析性问题，而不关心概率论的应用性问题。”马尔可夫称，著名统计学家和生物统计学家卡尔·皮尔逊“没有做过任何值得注意的事情”。几年后，听说巴舍利耶在他之前做过随机游走和股市研究后，马尔可夫回应道：“我当然看过巴舍利耶的文章，但我非常不喜欢它。我不会试图判断它对统计学的重要性，不过从数学角度看，我认为它一点儿也不重要。”

但是，在把俄罗斯的无神论者和东正教信徒团结起来的那股激情——亚历山大·普希金的诗歌——的感召下，马尔可夫做出了让步，并应用了巴舍利耶的理论。概率论当然无法捕捉普希金诗歌的意义和艺术性，于是，马尔可夫自娱自乐地把普希金的诗体小说《叶甫盖尼·奥涅金》的前20000个字母看作由元音字母和辅音字母组成的序列，准确地说，其中元音字母占43.2%，辅音字母占56.8%。人们可能会天真地以为这些字母之间是相互独立的，也就是说，一个辅音字母后面的那个字母也是辅音字母的可能性与该文本中其他任意一个字母是辅音字母的可能性一样大，都是56.8%。

但马尔可夫发现事实并非如此。他费力地把每对连续的字母分成了4类，即辅音-辅音、辅音-元音、元音-辅音、元音-元音，并绘制了示意图（见图4-4）。

这是一个马尔可夫链，与控制蚊子在两个沼泽间飞行的那个马尔可夫链类似，只是概率发生了变化。如果当前字母是辅音字母，那么下一个字母是元音字母的概率为66.3%，是辅音字母的概率为33.7%。双元音字母的概率更小，一个元音字母后面跟着另一个元音字母的概率只有12.8%。这些数字在整个文本中都具有统计稳定性，你可以把它们视为普希金作品的统计学特征。后来，马尔可夫还分析了谢尔盖·阿克萨科夫的小说《孙子巴格罗夫的童年》中的10万个字母。阿克萨科夫作品中的元音字母的占比与普希金作品的差别不太大，为44.9%。但是，阿克萨科夫作品的马尔可夫链（见图4-5）看起来与普希金的作品完全不同。

如果出于某种原因，你需要确定一份俄语文本的作者是阿克萨科夫还是普希金，有一个好办法（尤其是在你不懂俄语的情况下）是，数一数有多少对连续的元音字母——阿克萨科夫似乎乐于此道，普希金则没有这样的爱好。

你不能责怪马尔可夫把文学作品简化为由辅音字母和元音字母组成的二元序列，因为他只能靠纸笔完成研究工作。电子计算机的问世，将很多不可能都变成了可能。你可以研究蚊子在26个沼泽（每个沼泽对应英语字母表中的一个字母）间飞行的情况，而不再局限于两个沼泽。只要给定一份大小合适的文本，人们就可以估算出定义其马尔可夫链所需的全部概率。谷歌公司的研究总监彼得·诺维格使用了一个约有3.5万亿个字母的文本语料库来计算这些概率。这些字母中包含4450亿个最常用的英语字母E，占比为12.5%。但一个E后面紧跟着另一个E的情况只出现了106亿次，概率略大于2%。更常见的情况是E后面紧跟着R，共出现了578亿次。所以，在紧跟着E的字母中，R的占比接近13%，是R在所有字母中占比的两倍多。事实上，在英语的所有双字母组合中，ER的出现概率排名第四。（猜一猜，排在前三名的是哪几个组合？ ）

我喜欢把字母想象成地图上的地点，把概率想象成穿行难易程度不等的人行道。从E到R有一条宽阔平坦的马路，而从E到B只有一条荆棘丛生的小道。哦，所有路都是单行道。从H到T的难度要比从T到H大20多倍。（因为讲英语的人常会说“the”、“there”、“this”和“that”，而不怎么说“light”和“ashtray”。）马尔可夫链可以告诉我们，一份英语文本可能会在地图上转化成何等蜿蜒曲折的路径。

既然你已经走到这里了，为什么不继续走下去呢？我们可以把英语文本看成是双字母组合序列，而不是单字母序列。例如，“Once you're here, why not go deeper?”这个英语句子可以变成如下双字母组合序列：

ON, NC, CE, EY, YO, OU…

现在，我们给道路设置一些限制性条件：紧跟着ON的不能是任意一个双字母组合，而必须是以N开头的双字母组合（诺维格的表格告诉我们，紧跟着ON的最常见的双字母组合是NS，占比为14.7%，接下来是NT，占比为11.3%）。这种做法会让英语文本的结构更加清晰。

工程师、数学家克劳德·香农最先意识到，马尔可夫链不仅可用于分析文本，还可以生成文本。假设你想以ON作为开头，生成一段与书面英语有相同统计性质的文本。那么，你可以用随机数生成器选择下一个字母，它是S的概率为14.7%，是T的概率为11.3%，以此类推。一旦选定了下一个字母（比如T），你就有了下一个双字母组合（NT）。如果你愿意，可以一直这样进行下去。香农的论文《通信的数学理论》（它开创了整个信息论领域）写于1948年，所以他无法从现代磁存储系统中读取包含3.5万亿个字母的英语文本，而只能用另一种方法估算马尔可夫链。如果出现在他眼前的双字母组合是ON，他就会从书架上取下一本书并快速翻阅，直到发现第一对相连的O和N。如果紧跟在双字母组合ON后面的是字母D，下一个双字母组合就是ND。然后，香农会打开另一本书，查找后面紧跟着D的N，以此类推。（如果紧跟在双字母组合ON后面的是空格，你也可以追踪它，它能帮你实现单词内换行。）把这个双字母组合序列写下来，你可以得到香农的一句名言：

IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.

这个简单的马尔可夫过程生成的并不是英语文本，但它看起来很像英语文本。这就是马尔可夫链的鬼魅般的可怕力量。

当然，马尔可夫链取决于你用来学习概率的文本，在机器学习领域它们被称为“训练数据”。诺维格使用的文本是谷歌搜索引擎从网站上获取的大量信息，香农使用的文本是他书架上的书，马尔可夫使用的文本是普希金的作品。我以1971年在美国出生的婴儿名单作为训练数据，利用从中习得的马尔可夫链生成了如下文本：

Teandola, Amberylon, Madrihadria, Kaseniane, Quille, Abenellett, …

以上是双字母组合的马尔可夫链的应用情况。我们还可以更进一步，问一个问题：对于一个三字母组合，每个字母紧随其后出现的频率是多少？这需要追踪更多的数据，因为三字母组合的数量远多于双字母组合，但得出的结果看上去更像人名了：

Kendi, Jeane, Abby, Fleureemaira, Jean, Starlo, Caming, Bettilia, …

如果我们把字符串的长度增加到5个字母，结果的忠实度就会变得非常高，以至于我们常常可以从数据库中复制全名。与此同时，有些“名字”也不乏新意。

Adam, Dalila, Melicia, Kelsey, Bevan, Chrisann, Contrina, Susan, …

如果我们将三字母组合的马尔可夫链应用于2017年出生的婴儿，就会得到：

Anaki, Emalee, Chan, Jalee, Elif, Branshi, Naaviel, Corby, Luxton, Naftalene, Rayerson, Alahna, …

毫无疑问，这个序列给人一种更加现代的感觉。（事实上，其中约有50%都是当今婴孩的真实名字。）如果我们将三字母组合的马尔可夫链应用于1917年出生的婴儿，则会得到：

Vensie, Adelle, Allwood, Walter, Wandeliottlie, Kathryn, Fran, Earnet, Calus, Hazellia, Oberta, …

马尔可夫链虽然简单，却能在一定程度上捕捉到不同时代取名字的风格，还能给人一种耳目一新的感觉。有些名字还不错，例如，“Jalee”会让你联想到一个上小学的孩子，“Vensie”会给你一种复古的感觉。但“Naftalene”可能不是一个好名字。

马尔可夫链生成语言的能力让人半信半疑。语言就是马尔可夫链吗？说话时，我们会根据自己说过的最后几句话，以及我们从听过的所有其他话语中习得的某种概率分布，生成新的语句，是这样吗？

事情没那么简单。毕竟，在用语言介绍我们周围的世界时，我们确实会字斟句酌，而不只是重复自己说过的话。

然而，现代的马尔可夫链可以生成非常像人类语言的文本。Open AI（一个人工智能方面的非营利性组织）推出的GPT-3等语言生成算法是香农的文本机器的精神继承者，只不过前者的训练数据要大得多，输入的也不是三字母组合，而是数百个单词长度的文本块。但是，两者的原理相同：输入一段摘自本书英文版的文本，马尔可夫链生成的下一个单词是“the”、“geometry”或“graupel”的概率有多大？

You might think that this would be easy. You could take the first five sentences from your book and run them through GPT-3, and you’d get back a list of probabilities for every possible combination of words in those sentences.（ 你也许会认为这很容易。你可以摘出本书开头的5句话，并用GPT-3算法来处理它们，就会得到这些句子中所有可能的词语组合的概率。 ）

等一下，你为什么会觉得这很容易？实际上，你不会产生这种感觉，因为上面这段英语文本是在其前面三段文本的基础上由GPT-3算法续写的。我从大约10次的尝试中选择了这个最合理的结果，而GPT-3算法生成的其他结果看上去与你正在读的这本书的英文版也没有多大的违和感。坦白地说，这让身为本书作者的我多少有些不安，尽管这些英语句子从字面意义上是说不通的，就像GPT-3算法生成的如下结果一样。

If you're familiar with the concept of Bayes' theorem, then this should be easy for you. If there's a 50% chance that the next word will be“the” and a 50% chance that it'll be “geometry,” then the probability that the next word is either “the geometry” or “graupel” is (50/50) ² =0.[ 如果你熟悉贝叶斯定理的概念，那么这对你来说应该很容易。如果下一个单词有50%的概率是 “the”， 有50%的概率是 “geometry”， 那么下一个单词是 “the geometry” 或 “graupel” 的概率是 (50/50) ² =0。]

GPT-3算法和香农的文本机器之间存在很大的区别。想象一下，克劳德·香农拥有一座更大的图书馆。他准备从你刚刚读过的这7段英语文本（共计500个单词左右）入手，用他的文本机器生成英语句子。香农开始查阅他图书馆里的藏书，直到找到一本包含这500个英语单词且单词的排列顺序一模一样的书，以便记录紧随其后出现的那个单词。但他肯定找不到这样一本书，不会有其他人（我希望如此！）一字不差地在其他书中写过这7段文本。所以，香农的方法在第一步就失败了。这就好像他要猜下一个字母，但摆在他面前的两个字母是XZ一样。在他的书架上，很可能没有一本书中会接连出现这两个字母。那么，他会耸耸肩然后放弃吗？让我们赋予想象中的香农坚忍不拔的品格吧！有人可能会说：既然我们以前从未遇见XZ，那么我们见过哪些类似于XZ的双字母组合呢？紧跟在这些双字母组合后面的又是哪些字母呢？一旦我们开始这样想，我们就是在判断哪些字母串彼此“贴近”（close to），或者说我们正在思考字母串的几何图形。我们应该如何理解并记住“贴近度”（closeness）的概念呢？这不是一个答案显而易见的问题。如果我们讨论的是一份包含500个单词的英语文本，问题就难上加难了。两段文本彼此贴近意味着什么？有语言几何学吗？有文体几何学吗？计算机应该如何弄清楚这个问题？我们后面还会回到这些问题上，但在此之前我们先来说说世界上最伟大的国际跳棋选手。 NBv1pRyjHOWaZwnVb6BfUEa6FHg9VxFZrKfg18bKw9m0Z9fmjrfdgU06SZzLXFhJ