最大熵模型

2023-02-26 11:10:02Python022

最大熵模型,第1张

信息增益在决策树中介绍，最大熵模型之后再来更。

为了解释熵，首先要引入“信息量”这个词。直观上理解，信息量可以度量一个事件包含的信息。先给出公式，然后结合例子来理解。

信息量的定义：

例子：比如有两个事件，狗咬了人与人咬了狗，那很明显狗咬人这件事情概率大，人咬了狗这件事情概率小，所以可以通过公式来分析。log是一个单调递增的凹函数，因此公式中越大则信息量越小；越小则信息量越大。例子中，狗咬人的信息量就很小，人咬狗的信息量就很大。总而言之信息量与概率成反比，概率越低则信息量越大，概率越大信息量则越小。

有了信息量的基础，就可以用来解释熵是什么东西。简单的一句话来解释就是 “熵是信息量的期望”，先给出公式：

熵的定义：

可以看到，事件的概率乘上这个时间的信息量再求和，那就是期望的定义。熵能够反映事件的不确定性，不确定性与熵成正比关系。

联合熵实际上是表示两个变量或者多个变量熵的并集。给出公式：

多变量联合熵的定义：

条件熵可以从引言部分中给出的Venn图中可以直观地理解，由于个人能力有限，无法用通俗的语言来解释。还是用公式来描述其含义比较准确。

条件熵的定义：

推导一波：

条件熵的两种含义：

第一种含义是说从联合熵中减去熵第二中含义是说熵减去互信息 . 其中，互信息就是指两个熵的交集，接下来马上介绍互信息。

互信息的含义可以通过引言部分的Venn图理解一下，实际上就是两个熵的交集。给出公式：

互信息的定义：

特点： 互信息常用于机器学习中的特征选择和特征关联性分析。互信息刻画了两个变量之间的非线性相关性，而概率论中的相关性用来刻画线性相关性

KL散度用来刻画两个分布之间的差异性，可参考MLPR一书中对贝叶斯的描述。有很多类似的度量两个分布P和Q的方法，如 ,这里只是mark一下，目前我还没有逐一去研究过，这里仅讨论KL散度。

为什么需要用KL散度来比较两个分布之间的差异性呢？在这个问题之前还有问题，什么是两个分布？怎么就来了两个分布？答案是实际的应用问题引出的。机器学习中有时候需要比较两个样本集的差异，按照经验比较差异那就可以用一些范数距离来求解，如用一阶范数或者二阶范数直接来计算不久OK了吗？当然，用范数来做有一定的道理，也是可以的，但是有一个先决条件——“两个数据集中的样本能够逐一对应”。如果不满足这个先决条件，那么用范数来度量差异性就是不合理的。实际的应用中，很难保证两个样本集中的样本能够一一对应，因此用范数距离比较差异的方法就不可行了。那么就换一种思路，我用两个样本集的分布来比较差异性，这样就回答了“两个分布怎么来的”这个问题。

再回答标题中的问题，为什么需要用KL散度来比较两个分布之间的差异性呢？答案就很简单了，KL散度只是很多种比较分布差异性的一种，我们这里讨论熵的时候就用到了相对熵，那就是KL散度。条条大路通罗马，KL散度只是其中一种方法。

假设有两个分布P和Q，我们需要求他们的相对熵，那么用公式可以表示为

相对熵的定义：

性质1：

性质2：随着的增大，P和Q两个分布的差异会非常明显

推导一波： 为了方便进一步的推导，我们令 , 则令则有

由于log函数是一个凹函数，因此根据凹函数的詹森不等式，可以对进一步推导:

其中。通过推导可以发现

证毕！

交叉熵可以用来计算学习模型分布与训练分布之间的差异，交叉熵广泛用于逻辑回归的Sigmoid和Softmax函数中作为损失函数使用。（这句话引自 https://www.cnblogs.com/kyrieng/p/8694705.html ，感谢大佬的解读）给出公式：

交叉熵的定义

实际上交叉熵还可以这样理解：

因此，交叉熵可以看做是熵加上KL散度.

决策树中介绍（还未更）

在介绍最大熵之前，首先来明确一下事件概率的经验值和理论值

经验值：

假设有这样一个数据集，我们用来表示从包含n个样本的数据集中样本所占的比例。这个就是我们的经验值，实际上也就是我们从数据中训练得到的值。

理论值： 理论上这个事件的概率应该如何表示呢？实际上这个问题在很早以前就学过了。就是抛硬币的例子，例如抛100次出现30次正面，抛1000次出现400次正面，抛10000次出现4800次正面....抛次的时候出现次正面。因此，最后逼近极限的就是抛硬币例子中概率的理论值。在考虑我们的数据集，在这个例子中事件的理论概率值就是数据集中的样本无穷多的时候 .用公式来描述就是：

通过前面几节对熵的介绍，可以知道熵表示事件的不确定性，熵越大则不确定性越大。如果有A,B,C三件事情，通过已有数据测量发现他们发生的概率都是三分之一。那么问题来了，现在又发生了一个事件，请问到底是是A，B，C其中的哪件事情？要回答这个问题就先来看看最大熵原则是怎么说的

最大熵原则是这样一句话：承认已知数据，对未知数据无偏见。

通过这句话，我们在例子中所承认的就是“A,B,C三件事情，通过已有数据测量发现他们发生的概率都是三分之一”，对未知数据无偏见意思就是，再来一个事件我们主观地认为它可能会是哪个事件。

通过上面的例子可能会有两个问题，最大熵到底有什么用？如何应用最大熵？那么下面的例子来解释这两个问题。

插播一条李航《统计学习方法》中对最大熵原理是这样讲的“最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型”

先回忆条件熵：最大熵怎么用呢？我们可以用最大熵来确定事件的概率，然后通过概率来确定事件的归属类别。通俗地将就是可以通过对数据进行分析后进行参数估计。

用上面的条件熵可以有：

这个式子的意思就是：求解，使得熵最大。实际上，这个式子就引出了最大熵模型的目标。再定义一个特征函数就构成了最大熵问题的清单。特征函数是什么呢？可以理解为数据的特征对估计结果的映射关系。接下来给出最大熵问题的清单：

接下来，有目标函数，有约束，那就可以用拉格朗日朗日乘子法求解。可以看到，这里又引入了一个经验值，它和理想值相等是一个约束条件。用公式来描述：

开始构造拉格朗日函数：

对求偏导：

令则可以推导得到：

令则有：

这样，我们就得到了最终所要估计的概率 .

中文分词，即 Chinese Word Segmentation，即将一个汉字序列进行切分，得到一个个单独的词。表面上看，分词其实就是那么回事，但分词效果好不好对信息检索、实验结果还是有很大影响的，同时分词的背后其实是涉及各种各样的算法的。

中文分词与英文分词有很大的不同，对英文而言，一个单词就是一个词，而汉语是以字为基本的书写单位，词语之间没有明显的区分标记，需要人为切分。根据其特点，可以把分词算法分为四大类：

基于规则的分词方法

基于统计的分词方法

基于语义的分词方法

基于理解的分词方法

下面我们对这几种方法分别进行总结。

基于规则的分词方法

这种方法又叫作机械分词方法、基于字典的分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配。若在词典中找到某个字符串，则匹配成功。该方法有三个要素，即分词词典、文本扫描顺序和匹配原则。文本的扫描顺序有正向扫描、逆向扫描和双向扫描。匹配原则主要有最大匹配、最小匹配、逐词匹配和最佳匹配。

最大匹配法（MM）。基本思想是：假设自动分词词典中的最长词条所含汉字的个数为 i，则取被处理材料当前字符串序列中的前 i 个字符作为匹配字段，查找分词词典，若词典中有这样一个 i 字词，则匹配成功，匹配字段作为一个词被切分出来；若词典中找不到这样的一个 i 字词，则匹配失败，匹配字段去掉最后一个汉字，剩下的字符作为新的匹配字段，再进行匹配，如此进行下去，直到匹配成功为止。统计结果表明，该方法的错误率为 1/169。

逆向最大匹配法（RMM）。该方法的分词过程与 MM 法相同，不同的是从句子（或文章）末尾开始处理，每次匹配不成功时去掉的是前面的一个汉字。统计结果表明，该方法的错误率为 1/245。

逐词遍历法。把词典中的词按照由长到短递减的顺序逐字搜索整个待处理的材料，一直到把全部的词切分出来为止。不论分词词典多大，被处理的材料多么小，都得把这个分词词典匹配一遍。

设立切分标志法。切分标志有自然和非自然之分。自然切分标志是指文章中出现的非文字符号，如标点符号等；非自然标志是利用词缀和不构成词的词（包括单音词、复音节词以及象声词等）。设立切分标志法首先收集众多的切分标志，分词时先找出切分标志，把句子切分为一些较短的字段，再用 MM、RMM 或其它的方法进行细加工。这种方法并非真正意义上的分词方法，只是自动分词的一种前处理方式而已，它要额外消耗时间扫描切分标志，增加存储空间存放那些非自然切分标志。

最佳匹配法（OM）。此法分为正向的最佳匹配法和逆向的最佳匹配法，其出发点是：在词典中按词频的大小顺序排列词条，以求缩短对分词词典的检索时间，达到最佳效果，从而降低分词的时间复杂度，加快分词速度。实质上，这种方法也不是一种纯粹意义上的分词方法，它只是一种对分词词典的组织方式。OM 法的分词词典每条词的前面必须有指明长度的数据项，所以其空间复杂度有所增加，对提高分词精度没有影响，分词处理的时间复杂度有所降低。

此种方法优点是简单，易于实现。但缺点有很多：匹配速度慢；存在交集型和组合型歧义切分问题；词本身没有一个标准的定义，没有统一标准的词集；不同词典产生的歧义也不同；缺乏自学习的智能性。

基于统计的分词方法

该方法的主要思想：词是稳定的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好地反映成词的可信度。可以对训练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可以认为此字组可能构成了一个词。该方法又称为无字典分词。

该方法所应用的主要的统计模型有：N 元文法模型（N-gram）、隐马尔可夫模型（Hiden Markov Model，HMM）、最大熵模型（ME）、条件随机场模型（Conditional Random Fields，CRF）等。

在实际应用中此类分词算法一般是将其与基于词典的分词方法结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。

基于语义的分词方法

语义分词法引入了语义分析，对自然语言自身的语言信息进行更多的处理，如扩充转移网络法、知识分词语义分析法、邻接约束法、综合匹配法、后缀分词法、特征词库法、矩阵约束法、语法分析法等。

扩充转移网络法

该方法以有限状态机概念为基础。有限状态机只能识别正则语言，对有限状态机作的第一次扩充使其具有递归能力，形成递归转移网络（RTN）。在RTN 中，弧线上的标志不仅可以是终极符（语言中的单词）或非终极符（词类），还可以调用另外的子网络名字分非终极符（如字或字串的成词条件）。这样，计算机在运行某个子网络时，就可以调用另外的子网络，还可以递归调用。词法扩充转移网络的使用，使分词处理和语言理解的句法处理阶段交互成为可能，并且有效地解决了汉语分词的歧义。

矩阵约束法

其基本思想是：先建立一个语法约束矩阵和一个语义约束矩阵，其中元素分别表明具有某词性的词和具有另一词性的词相邻是否符合语法规则，属于某语义类的词和属于另一词义类的词相邻是否符合逻辑，机器在切分时以之约束分词结果。

基于理解的分词方法

基于理解的分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。目前基于理解的分词方法主要有专家系统分词法和神经网络分词法等。

专家系统分词法

从专家系统角度把分词的知识（包括常识性分词知识与消除歧义切分的启发性知识即歧义切分规则）从实现分词过程的推理机中独立出来，使知识库的维护与推理机的实现互不干扰，从而使知识库易于维护和管理。它还具有发现交集歧义字段和多义组合歧义字段的能力和一定的自学习功能。

神经网络分词法

该方法是模拟人脑并行，分布处理和建立数值计算模型工作的。它将分词知识所分散隐式的方法存入神经网络内部，通过自学习和训练修改内部权值，以达到正确的分词结果，最后给出神经网络自动分词结果，如使用 LSTM、GRU 等神经网络模型等。

神经网络专家系统集成式分词法

该方法首先启动神经网络进行分词，当神经网络对新出现的词不能给出准确切分时，激活专家系统进行分析判断，依据知识库进行推理，得出初步分析，并启动学习机制对神经网络进行训练。该方法可以较充分发挥神经网络与专家系统二者优势，进一步提高分词效率。

以上便是对分词算法的基本介绍。

现在我们回到序列标注任务，描述一下直接使用对数线性模型的最大熵马尔科夫模型。最大熵马尔科夫模型是隐马尔可夫模型的一个有用替代。

我们的目标是为以下条件概率建立模型。

这里是第个输入符号（比如一句话里的第个词），是第个状态。这里使用表示所有状态的集合，这里假设是有限的。

例如，在英语词性标注里，是所有英语词性的集合（名词、动词、介词等）。给定包含单词的一句话，将有种可能的词性序列，这里是所有词性的数量。我们想要在这种可能序列中估算出一个分布。

第一步，最大熵马尔科夫模型使用下面的概率分解：