最大熵准则背后的一连串秘密

1. 阅读本文前已全面了解统计机器学习中最大熵模型（MEM），有向图模型（DAG），无向图模型（UGM）等相关内容会获得更好阅读体验。

2. 本文不是教科书式的介绍，而是借技术分享文自由而不受限的形式，把严谨的教材（尤其中式教材）中为了主线的清晰，讲清楚“怎么办”的内容以外，却部分难以展现的关于“是什么”和“为什么”的一些思考分享出来供大家参考，这些内容考试绝不会考，但笔者认为这一定是能否拥有解决问题能力的关键。

3. 本文所有概念中文名仅出现一次，下文英文简称可与之对照。）

相信大家在做机器学习相关研究中，都或多或少遇到过以下这些概念：最大熵（ME），指数分布族（EFD），贝叶斯网络（BN），马尔可夫随机场（MRF），动态图模型（DBN），隐马尔可夫模型（HMM），条件随机场（CRF），最大熵马尔可夫模型（MEMM），加权有限状态自动机（WFST），乔姆斯基文法（Chomsky Grammar）等等，这些初次见面看起来头大，二次见面如同初识的概念可能一定程度上困扰着我们，这些方法到底如何选用？为什么要搞出这么多概念来？抛开算法执行层面的具体细节，他们产生的来龙去脉是什么？有着怎样的联系？今天，就和大家分享一下我在这部分内容上的一些思考。

1. 一个中心：最大熵准则

这是一个原则性的指导思想，实践中在其他应用指导下才能生效，而平常我们用的极大似然估计方法，是最大熵准则求解步骤中的最后一步。

先来看最大熵模型的定义（这里统一用求和代表离散随机变量的求和和连续随机变量的积分，二者公式推导没有本质区别）：

吴军老师在数学之美里对最大熵模型的通俗解释是“不要把鸡蛋放在一个篮子里”，所以我们需要找一个满足条件限制的尽可能“均匀”的分布来作为估计分布，熵最大的分布最“均匀”。我想，猜测一个硬币正反面的概率都是0.5，这是均匀，但当分布有限制的时候，平常理解的平均分配已经无法指导什么是最优分布了，而最大熵其实只是在无任何其他约束或约束够简单的时候（比如ABCDE五种可能结果，限定AB两结果之和为定值），和平常说的“均匀准则”恰好同解。那么到底为什么要求分布的最大熵来作为估计结果呢？这一准则为什么会屡试不爽，奉为经典？本质到底是什么？

跳出最大熵框架和以往知识的约束，我们来凭直觉设想一下，问题就会迎刃而解。现在要你估计一个随机变量的分布，满足若干数字特征条件后，在分布空间内还有无数可行解，那到底选哪一个呢？理论上，此时选择任何一个可行解都是没有问题的，即一个没有抛过又没见过，但知道只有两面而且每次只会从中抛出一面时候，你估计正面概率为0.99，0.5和0.01都有可能是正确答案，因为我们对硬币抛出正反面分布的先验一无所知，只能是均匀分布，以上三个猜想命中正解的似然相等！既然相等，为啥一定要猜才0.5看似更合理呢？因为我们估计分布的目的，有时不是为了得到一个完全正确概率最大的分布（反正那也接近0），而是为了得到一个任何情况下，效果都不太差的分布，即，对于最差的情况，我估计的分布和真实分布也要足够的接近；即，真实分布的样本在我估计分布上的似然要是最大的；即，交叉熵（CE）最小。写成公式就是：

继续推导一下，有惊喜：

可以证明，CE是f的凸泛函数，故只要ri(x)是仿射函数，上述推导成立。

看到了吧，所谓最大熵准则呢，既没有吴军老师解释的那么通俗，也没有那么深奥不可理解，利用最大熵准则求出来的分布，其实是在约束条件都成立的条件下，在最差情况下，表现最好的分布，我们只需要理解和承认表现最好等价于似然函数最大，那这样分布的求解实际上就是求解最大熵分布，甭论熵的物理意义，我认为在统计模型中最好理解的意义一定在此。

另外，最大熵分布的求解仍然用到优化问题的对偶性质，可以证明，一般的机器学习问题loss设定成估计分布对经验分布函数交叉熵（用极大似然求解参数），其实是最大熵模型中选定若干特征函数ri，并以样本估计值作为其真值时的最大熵模型的解。证明如下：

故综上，寻求的是最差情况下的最好解，是我们大多说机器学习问题loss设定成交叉熵（极大似然）的理想答案的性质，只有我们确实需要这样性质的解的时候，最大熵准则以及表面的损失函数，才是有效的。而我们还有一些如svm背后的hinge loss自成一派；多臂老虎机（MAB）类问题UCB追求收敛速度（若追求期望等也可写出其他策略）；而MSE loss求的是期望值（在正态分布下等价于极大似然），absolute loss求的是中位数，sign loss求的是众数等，可以看成是把分布空间限定在单点分布时候不同损失函数的求解性质。为啥我觉得最大熵模型是统计建模的中心呢？因为你看看，我们市面上见得到的联合分布和条件分布表达式基本都是其特例或者其边缘分布结果。他们都是在给定随机变量空间和特征函数的条件下的最大熵模型的解。那么多复杂的分布和参数性质居然背后有一个统一的思想来统领和指导，我不得不再次惊叹于数学之美。

到此，从最开始无脑迷恋最大熵的美丽形式，到百思不得道的思索，最后窥见其原理的简明以及局限，真理总是越辩越明。

在这套框架指导下，我们的前辈们还发明了诸多适应于不同数学结构和实际问题的经典模型，仔细研读会发现他们都是在最大熵的基础上结合具体问题延展的可行的处理策略以及建模思想，无不结合了领域知识带来的机理假设使得模型更合理可行。我们虽然通常是做基于统计的机器学习，那只不过是完全明确的机理不得而知时候采取的建模策略，但是对机理把握越明确，越能同时向模型里注入知识（定性特征后由样本表达和定量限定后划定函数空间等）和数据才能使得机器学习系统能越来越聪明，以便在一件小小的事情上达到自动驾驶，帮助人类开启新征程的探索。接下来，我们就来看看前辈们给我们留下的，在最大熵的框架下，面对实际问题的行动指南。

（关于最大熵模型的求解公式推导以及学习算法，以及与其关系密切的指数分布族函数的性质我们另外找专题再讨论，本文专注讲清楚其来龙去脉和图模型之间的关系。）

2. 两种世界观：贝叶斯网络和马尔可夫随机场

我们对客观事件发生的可能性大小计算通常转化为了在给定样本空间内求解某概率密度函数，第一个要解决也往往是被忽略的问题是，你选取的随机变量是哪个对象的哪些属性，描述的是生成过程中的哪个阶段？是否有重复和遗漏？他们之间的关系如何呢？如何对变量复杂繁多，生成过程复杂的事件进行最大熵特征的有效书写，进而完成建模呢？前辈给我们留下的有向图（DAG）和无向图模型（UGM）给了我们答案，他们用两种完全不同的思考角度完成对物理世界的数学抽象。

2.1 DAG

2.1.1BN

BN觉得，世间万物都是依序产生的，我们也可以完全观测或了解每一道工序下描述对象的全部随机变量信息，后产生的变量总是按照一定规律受前面若干变量的影响，当其依赖的变量全部产生时，它也应运而生，没错，这是个时序模型，我们暂且抛开生成速度，给定固定的变量生成顺序，也假设明确知道该系统运行的开始和终止。对于这样一个生成系统，描述变量和生成过程完全固定，我们应该怎样去描述和建模呢？其数学结构即DAG，对应有BN的联合概率密度写为：

第二个式子是指数族分布表达式，由此得到了最终的联合概率密度表达式。能这么写其实是源于我们已经对此局部做了最大熵建模，并把其转化为最后一步参数求解了。这里，theta为固定参数，可能是要从数据中学习估计的，或者待求后验分布/期望的中间参数（MAP、PME），hi函数对应那些已知固定的参数对分布函数的影响，为外部给定先验，不参与优化（常常设为常数1），Ai仅为参数的函数和随机变量无关。且可喜的是，这一看似复杂的形式下有着良好的性质，且对于已知的观测变量集，对应的CE loss，即最大熵解是有解析解的，简单的可以直接写出表达式，或者GD，IIS等求解即可，这里与本文核心思想无关，暂不更多展开。

由此看到，DAG模型的建模思路是，以生成的角度搞清楚研究对象每个事件的生成依赖关系，得到表达依赖的DAG结构以及结构所含的具体特征表达形式（有序的每个随机变量的依赖变量集（注意要无环）以及具体方式是其根本数学结构），至此，用条件概率公式即可写出整个事件的联合分布，这样的写法也一定满足图上任意两个变量集是否相互独立的结论在公式上的结论，这些都源于因果关系的初始设定。对于任何完全或不完全的观测可以利用此数据进行参数估计，于是关于此系统的任何条件，边缘或者联合概率均可由此得到，建模完成。

举两个例子简单说明一下，用类别分布抽出一个某颜色的小球，并选择按下一个颜色的开关，最后球所显示的颜色分布；01分布决定是否打雷，打雷作为条件01分布是否下雨，打雷和下雨发生与否决定01分布是否降温，等等。这些生成机理多由外部知识和大量的人类观察决定，其好坏决定了模型利用数据的能力和模型上限。但话说回来，这里的父节点随机变量集和孩子随机变量之间的因果关系不必真的存在，我们可以任意给定一族变量的依赖关系并如上建模，只不过，我们相信，利用人脑思维得到的“因果关系”，对应到DAG图中的关系以后，能够尽最大可能传授给机器这一贴近真实的机理，这样，再用观测变量集合来消除variance就会有着更好的效果。这个因果关系到DAG有向关系是人机配合的核心接口之一：我负责定性观察因果关系，你负责把定性算成定量结果。所以BN向我们提供了一种使用最大熵模型建模的策略：分解成若干有序的条件分布，在每个条件分布上用最大熵模型，各部分可独立处理，合并后即为所求。

另外，考虑生成时长的经典模型是Poisson Process和CTMC，和本文主线无关，这里暂不展开了。

2.1.2 DBN

很遗憾，能够用指定个数并含义固定不变的变量来描述的系统是极其简单而不符合实际的，要么中间有严重的环节缺失，使得因果关系并不牢靠。一个常见的情况是，研究对象是天然的变长序列，即一阶张量（高阶同理）。比如待检测变异的基因测序序列，待进行某种标注的给定文本序列。其位置属性并不重要而一旦对位置建模则处理序列的长度有限且参数数量随着序列长度线性增长是不可接受的。故综合数据量和模型复杂度的匹配，假设满足的一个基本规律是，序列满足时齐性（homogeneous），其在每一个单元内服从近似相同形式和参数的分布，这样，在损失很小bias的情况下（可能并不严格时齐），把模型参数数量从与序列长度成正比降为与序列长度无关，而仅从基本单元的阶数去作为超参调整模型与数据的匹配，以达到最好的学习效果，这就是DBN模型的思路和策略，在暂不要求对开始和结束状态建模的条件下，为已知序列到序列的映射标注问题提供了通用思路，其基本表达式为：

注意m是每个样本所特有固定的序列长度，f函数为所有i所共用，不是i的函数，其地位相当于DAG中的一个完整的生成过程。注意添加的S和E，是为了对开头结尾处可能服从的特殊规律建模，哪怕不对结尾开头建模，这个符号也使得于是我们在表达式书写上能够用统一的形式。

这样我们对于无须对序列长度建模（往往是给定已知序列的标注）问题，在动态变化的定长序列空间内给出了概率建模思路，即，其生成是基本单元的延展，自然的根据这个动态DAG图，分布函数是每个共享单元内条件概率的乘积。

后面我们会看到，这里的BN和DBN实际上都是WFST模型的一个特例，更一般的形式我们在后面马上介绍，另外这里的共享参数延展特性在后面的CRF模型中同样应用到，可对照着来理解。

2.1.3 WFST

无论是静态图还是作为其周期延拓的动态图，绕不开的一点是，在有序产生变量的过程中，对可能的分支状态的描述无能为力，对所有变长序列统一空间的概率分布函数无法估计。（或言，DAG只是WFST模型中仅有一条没有任何分支的从开始到结束的状态链的特例，DBN又比BN多的地方在于此链构成一个圈）比如，以篮球比赛为例，实际情况可能是，某人以01分布决定传球还是出手，如果出手则以category 分布决定谁拿到篮板球或者出界，如果有人拿到篮板球决定他要干嘛，如果出界则决定谁发边线球；如果传球，则以01分布决定是否有人抢断以及如果没有抢断谁拿到球后准备干嘛，如果抢断，抢断后准备干嘛。。。。。。可以看出，每一个随机行为的结果不仅影响到后续行为的分布参数，还会以分类变量选择的方式影响到其分布类型，包括变量空间。所以，那种固定的DAG对应固定的变量有序生成的模型已经不适用了，整个系统的状态连接不能仅仅限定于单链的线性，对系统的建模方式应该是状态空间及在该空间下输入信号空间作为条件，决定当下输出及可能的新状态的分布，这样能够描述清楚所有可能行为变量以及其对应可行条件。一次离散随机过程相当于在从开始到结束的状态空间内的游走，每一步都依概率选择路径和输出不影响下一步行为的信号，我们直接观测的，便是这个信号了。这便是WFST的存在理由，对一个稳定的时序系统，不考虑时长，系统的运行可以看作状态X输入=输出X新状态的循环，这样可以完美解决上面的建模问题。表达式如下：

篇幅有限，关于其求解的详细算法我们另外介绍，这里阐述的思想是，通过这一建模框架，我们可以得到任意输入输出为序列或可以表达为序列的任务建模，我们定义好输入空间A，状态空间Q，以及给定Q，A时发射的B，结果Q，以及发生概率，这可以描述任一稳定系统接收外界信息后的随机反应方式，概率建模中往往也转化为求概率最大的那个解的问题。这为我们构建客观模型提供了更加灵活的框架，不必再受限于线性的状态转移结构而是可以任意设置以接近真实情况，也可由此更灵活地设定变量空间，而在这个框架下的每一个局部的状态转移分布，即K(Q2，B|Q1，A)=K1(Q2|Q1，A)*K2(B|Q2，Q1，A)，其看作条件概率密度函数时仍是用最大熵模型建模和使用DAG基本单元看待，其中若K2(B|Q2，Q1，A)=K2(B|Q1，A)，称之为Moore Machine（HMM就是最简单的例子），否则称为Mealy Machine。

2.2 UGM=MRF

到此为止，我们介绍完了DAG框架下的条件概率建模思路以及由之产生的诸多拓展方案。UGM的拓展方式同前面完全相同，DBN对应过来就是CRF，WFST每个转移单元的建模本就可以选择DAG或UGM两种方式，这里就模型堆叠拓展部分不再重述，但对单元内建模思路的获取的不同予以分析和比较。

在DAG的世界里，一切变量是有因果的而顺序产生的，但UGM的世界观把一个建模单元看作一个整体对象，其随机变量与属性函数作用在一个对象上的映射对应，故UGM中的变量都是无序的对象属性，其相互关联的原因在于共属于同一个对象（可以看作是由同一对象产生的，在未知对象时候，理论上应该两两相关），那如何构建相互连接的边呢？我们这样来想象一下，一个对象的全局描述可能有很多维度，他们稠密地互相连接，相互影响，有些维度是天然已知有固定值，有些未知且不可观测，有的可以观测，那这些可以观测的变量之间有边相连就等价于，建模者认为在当前已知条件下，二者独立，互不干扰，或其相关性在当前数据量条件下忽略更有优势。比如认为一个人的性别和他生的孩子的性别是独立的，没有边相连，而性别和职业却相关，有边相连，这里的连接方式即代表我们人注入计算机的知识结构框架，作为能量帮助计算机理解客观世界。

当图构建好以后，就完成了物理规律向数学结构的抽象，那任意两个变量集是否独立的结论也由图结构定下来（Markov Property），和前面一样，DAG通过因果关系得到了依赖关系进而确定独立关系，这里通过两两相关关系确定图结构进而确定独立关系，这两个方案都给人类提供了足够友好而可行的接口，这便是图模型的价值。接下来，Hamilton Clifford Theory告诉我们概率分布可以写成如下形式：

Ci是图中所有的max clique，可以证明，这样的形式是满足Markov Property的，且是不损失bias条件下形式最简的。其实这里应该能理解，我们通过人为给定两两变量是否直接相关来获得UGM结构，而这个结构会自带对所有两个变量集是否独立的判断（前面DAG则是给定所有变量有序的因果联系，而得到这个独立与否的判断），让人去思考最简单直接的问题，而把这些信号组合起来构成一个模型系统进行复杂计算是计算机的工作。由此我们在每个单元内应用最大熵模型得到的指数族分布解即为第二行的表达结果，故Hamilton Clifford Theory其实就是在由UGM限定变量独立关系的条件下最大熵模型的具体形式。

这里提一个小点，我们在PRML一书中看到过关于DAG和UGM表达模型能力的表述，举例了immorality结构UGM无法表达而四边形结构DAG无法表达的例子，最后说明二者为有交集但互不包含关系且在模型空间中还存在着二者都无法表达的部分（如下图所示）：

其实，这些例子背后的本质是，变量间的独立与否关系是个变量集上的二元关系，DAG和UGM均只能表达其上有限的一部分（后文还介绍的因子图可以看作UGM的变种，直接给出互不包含的max clique得到解而省略了找寻步骤，只不过对人脑信息分析提高了难度），另外，在独立条件满足时，我们往往也仅把分布搜索空间限定在指数分布族，这也使得我们图模型可以表达的分布和全体分布的差距，科学研究总是把起点设置得很高使得理论退稿看起来很美，好在这里的理论基础对应的本质还是很漂亮和简单：这些分布形式假设加极大似然估计的结果，一定在最不利的情况下有最好的效果。

以上便是DAG和UGM概率建模的全部思想，它期望打通人脑定性知识和结构化数据的联系，为最大熵全局模型提供建模变量集合分割的方案，使得分割能简化每一个子问题的参数空间且由于人脑知识的保证也不至于偏离于真实情况（或在数据有限情况下的折中）。在每个子图内，我们应用最大熵模型的求解结论，去划定真实应用的特征函数（或根据特征模板以及数据自动选择），进而求得在人类知识指导下，这样的样本条件下，在最差情况下最好的解来。那接下来，我们进一步比较两种图模型建模的细节异同，以及在线性链上的神奇结论。

3. 三条等价链：隐马尔可夫模型，条件随机场，最大熵马尔可夫模型

在正式探讨三类线性链图模型和他们的异同之前，我们先继续推导一下用DAG和UGM的接口进行建模变量集划分以后，分布函数极其参数空间的形式：

可以惊喜地发现，无论DAG还是UGM，甚至factor graph都是提供一种变量集合划分方式，DAG的每个条件概率表达式涉及的条件和目标变量集合正好对应于UGM所得的max clique！而且他们建模的结果中只要每个子图是最大熵模型得到的指数族分布，那联合概率也是最大熵模型的指数分布族函数！由上面的公式对照可知，二者模型等价当且仅当：

可以看到，DAG在同等变量集合划分后的建模中，DAG予实质的特征函数更多的限定（h函数在一般的建模中往往设置为1，不予考虑），包括条件分布条件变量必须以线性函数得到特征函数（充分统计量样本函数）对应参数，此时归一化函数A也应是变量条件和参数条件和分离的，剩余不分离部分也是各自特征函数向量点乘函数得到结果，当UGM的设定函数形式没有超出这些限定，或可尤其表达的时候，二者建模完全等价。否则，在二者变量划分方式不同或者DAG函数形式不能表达为UGM对应条件概率表达的时候，二者不可混同，PRML一书中举的二者不可混同的例子也对应上述表述的情况。当然，我们整个讨论问题的范围都在指数分布族内，其含有分布指数形式以及内部特征参数点乘得到概率密度值的限定，超出这些限定的分布函数也自然不可表达，而好在，我们的指数分布族函数源于最大熵，最大熵的分布就一定有那个性质，让我们再来说一遍：充分统计量值测量准确时候，估计出来的分布一定是最差情况下最佳的。

好了，有了上面的基础再看HMM，CRF，MEMM就有一种会当凌绝顶，一览众山小的快感了。HMM和MEMM是DAG，区别在于HMM的隐藏链Yi生成Xi，MEMM的Yi则由Xi和原有的历史Yi-1，共同生成，且此关键条件分布用UGM建模联合分布后用条件概率公式得到，而CRF则是彻头彻尾的UGM（他们的高阶形式也类似）。他们三者对应的由图结构决定的变量集合划分方式完全相同，从表达能力上看，CRF是最佳最灵活的，而HMM，MEMM分别有所限定，可以看到，在X序列观测已知推测Y序列的问题上，在我们平常的建模策略里，他们是基本等价的。详细公式推导如下所示：

可以看到，他们都是指数分布族分布里的函数，只要特征函数（充分统计量样本函数）相同，他们都是等价的（其中CRF的第一个单元建模了后两个模型中前(k-1)个单元，与他们对应后相应的基本单元也可以相互对应了），且表达能力上CRF>HMM and MEMM，后二者则各有千秋。当然他们的共用适用范围都是不对时长间隔和开始结束建模的序列上元素一一映射问题，共同假设是序列上的时齐性，反映在公式里即是：序列上各位置单元共享函数形式与参数值，其任意长度序列的特征函数可写作单元特征函数和的形式，这样使得不同长度序列，不同位置之间能够通过共享参数，互相学习达到从样本信息中中估计分布的效果，这便是线性链模型的终极精髓了。

但是，这样的线性链拓展显然还不能建模像自然语言这样有着更复杂生成机理的对象，于是状态机模型，文法理论和因变量的引入，再一次使我们的模型系统贴近真实世界。

4. 四阶文法：状态机模型与隐变量建模

在上文2.1中，提到DAG模型的几个变种，可依线性链扩展处理变长序列，但对变量空间变长以及生成过程存在分类状态分支的情况无能为力，另外，虽然我们假设对象联合分布是指数分布族分布是合理的，但是往往观察的缺失使得我们常常算的是边缘分布，而这并不再保证指数分布族性质，因此，我们需要引入WFST模型以及由此带来的对隐变量的考虑和相应处理。这里的经典理论是Chomsky Grammar，关于它和WFST建模理论，以及和基本图模型甚至神经网络之间的关系，还有在含有隐变量条件下的EM类算法的内容较多，这里暂时点到为止，我们在其他文章中再单独成文予以详细阐述。

好了，读罢此文，不希望大家又多会背了一些公式，也不希望连公式也不曾浏览，而是对我们教科书上知识产生的来龙去脉形成自己的理解：

我们希望求解一个最坏情况下似然性期望最高的分布，于是我们又对偶理论推导出了最大熵目标函数；又由对偶理论得到其函数形式为指数函数，并简化设定为指数分布族函数；又依据实际问题中可能从变量生成和属性测量两个角度指导模型变量关系并化简模型得到DAG和UGM两类模型；然后对线性链结构予以时齐性假设来拓展基本单元解决得到DBN和CRF两类模型；最后引出还可能遇到分支的生成过程以及不可观测变量存在时候需要更加完善的WFST数学结构来解决的情况。

这是我理解的统计建模在最大熵的根基下的的全部脉络，且本文并不涉及算法操作层面的严谨叙述，相关内容可自行查阅教材。这里我把我基于是什么和为什么理解分享出来，让大家看到教材里写的怎么办时能够更加有的放矢，顿觉知识财富之美妙和价值，就足够了。内容不一定完善，供大家参考，希望真理越辩越明。

本人自幼热爱数学建模，后专攻统计建模，近年在生物序列，文本序列等序列建模领域深耕。学习和工作中无数次碰到ME，EFD，BN，MRF，DBN，HMM，CRF，MEMM，WFST，Chomsky Grammar等等，对其中来龙去脉，相互关系颇为疑惑和着迷。遂翻阅资料无数，夜以继日思考，终得此文，以兹纪念。