最大熵模型概念VS名著中的最大熵模型应用

2020年11月22日09:37:50 发表评论 85 views

0x01 背景概念

1. 什么是熵?

熵这个概念可以从多个角度来理解。

1.1 从物理学角度理解熵

熵最早来原于物理学。德国物理学家鲁道夫·克劳修斯首次提出熵的概念,用来表示任何一种能量在空间中分布的均匀程度,能量分布得越均匀,熵就越大。即,熵是表示物质系统状态的一种度量,用它来表征系统的无序程度。

  • 熵越大,系统越无序,意味着系统结构和运动的不确定和无规则;
  • 熵越小,系统越有序,意味着系统具有确定和有规则的运动状态。

1.2 从系统复杂度理解熵

信息熵还可以作为一个系统复杂程度的度量,即物质系统有序化,组织化,复杂化状态的一种度量。

  • 如果系统越复杂,出现不同情况的种类越多,那么他的信息熵是比较大的。
  • 如果一个系统越简单,出现情况种类很少(极端情况为1种情况,那么对应概率为1,对应的信息熵为0),此时的信息熵较小。

熵越大则该系统不确定性就越大,该系统未来发展就存在越多的可能性。

1.3 熵的推导&定义

熵的定义是:𝐇(𝐱) = −𝒔𝒖𝒎(𝒑(𝒙)𝒍𝒐𝒈𝟐𝒑(𝒙))

其中,𝑝(𝑥)代表随机事件𝑥的概率,H(X) 就被称为随机变量 x 的熵,它是表示随机变量不确定的度量,是对所有可能发生的事件产生的信息量的期望。负号是用来保证信息量是正数或者零。

为什么底数为 2 ? 这是因为,我们只需要信息量满足低概率事件 x 对应于高的信息量。那么对数的选择是任意的。只是遵循信息论的普遍传统,使用 2 作为对数的底!

从公式可得,随机变量的取值个数越多,状态数也就越多,信息熵就越大,混乱程度就越大。

当随机分布为均匀分布时,熵最大。关于均匀分布熵最大,这里有一个非常好的例子:

以全班的考试成绩为例,通常我们知道整个班成绩是符合高斯分布的,通过一次考试,发现每个人成绩都是相同的,则在学校看来这是一个爆炸性新闻,因为这是一个极低的事件,但是却发生了,不符合常规,下一步应该就是调查了吧。

1.4 熵在系统复杂度应用的实际例子

下面就让我们从名著中寻找例子:

李自成系统的熵

比如历史上的李自成闯军,麾下主要分成陕西帮和河南帮。假设陕西帮占据 2/3, 河南帮占据 1/3

所以具体熵值是:

- [1/3 * log(1/3) + 2/3 * log(2/3)] = 0.63
复制代码

梁山的熵

这次按照山头分。比如:

  • 宋江派系(花荣,雷横,李逵,清风山,欧鹏,吕方,关胜,呼延灼.....)
  • 三山派系(鲁智深,武松,杨志,张青,曹正.....)
  • 晁盖派系(林冲,刘唐,三阮,白胜...)
  • 卢俊义大名府派系(燕青,蔡氏兄弟...)
  • 登州派系(孙立,顾大嫂.....)
  • 揭阳江派系(李俊,童威,童猛.....)
  • 无党派人士(萧让,金大坚, 安道全...)

假设宋江派系占据1/3, 其他派系都是 1/9,所以具体的熵值是:

- [1/3 * log(1/3) + 6 * 1/9 * log(1/9)] = 1.83
复制代码

这样看来,梁山更不稳定,所以受招安是个好的选择,而闯军相对稳定,所以可以历经坎坷干掉崇祯。

2. 最大熵原理

最大熵原理就是说明世界将趋向无序,无论是商业、生命、钢铁、政治,万事万物,都必是腐朽消亡!

他描述的是这样一个自然事实,即基于当前已知前提下,也就是约束下,未知事件的概率尽可能的接近最符合事物的自然规律。

整个宇宙发展就是一个熵增的过程。如果不施加外力影响,事物永远向着更混乱的状态发展,如果施加外力影响,系统会在外力约束下达到其可能的最混乱状态。

比如,在你面对一个系统时候,你就应该认为这个系统应该自然而然的趋向最无序状态。有人可能会说,我对这个系统施加外力,施加约束,让它有序。但是事实上,系统会趋向 在你给的这些外力或者约束下 所能达到的最大无序状态。比如大家整理耳机,无论你把耳机线整理得如何整齐,你放起一段时间后再拿出来会发现,耳机还是会有一定状态的乱。

最大熵原理指出,对一个随机事件的概率分布进行预测时,

  • 对未知的情况不要做任何主观假设。
  • 如果你对这个分布一无所知,那就猜熵最大的均匀分布。
  • 如果你对这个分布知道一些情况,那么,就猜满足这些情况(即预测应当满足全部已知的约束)的熵最大的分布。

从预测风险的角度讲,就是 熵越大越好,就是要保留全部的不确定性,将风险降到最小。鸡蛋不能放在同一个篮子里。当概率分布最均匀时候,预测的风险最小,此时得到的概率分布的熵是最大。

3. 判别模型 vs 生成模型

分类问题,就是给定一个数据 x,要判断它对应的标签 y。分类模型有判别模型和生成模型两种。

3.1 生成模型 (Generative)

生成模型之所以叫生成模型,是因为,它背后的思想是 x是特征,y是标签,什么样的标签就会生成什么样的特征。好比说,标签是大象,那么可能的特征就有大耳朵,长鼻子等等。模型表示了给定输入X产生输出Y的生成关系

生成模型就是要学习观测数据 x 和隐藏类别 y 的联合概率分布P(x,y),然后根据贝叶斯公式来求得条件概率P(y|x),预测条件概率最大的y。也就是说,在训练阶段是只对P(X,Y)建模,需要确定这个联合概率分布的所有的信息参数。具体流程是:

  • 先从训练样本数据中,将所有的数据的分布情况摸透,然后最终确定一个分布,来作为所有的输入数据的分布,并且他是一个联合分布 P(X,Y) (注意 X 包含所有的特征 Xi, Y 包含所有的label Yi, 要对每个label Yi 都需要建模)。
  • 然后来了新的样本数据再对新的样本计算P(Y|X) ,导出Y , 最终选择最优概率的label为结果,所以没有什么判别边界。

再过一遍生成式模型的工作流程。

学习阶段,建模:

P(X,Y)=P(X∣Y)P(Y)P(X,Y)=P(X|Y)P(Y)

然后 根据新的X,导出 Y:

P(Y∣X)=P(X,Y)P(X)P(Y|X) = \frac{P(X,Y)}{P(X)}

生成式模型的优点在于,所包含的信息非常齐全,我称之为“上帝信息”,所以不仅可以用来输入label,还可以干其他的事情。生成式模型关注结果是如何产生的。但是生成式模型需要非常充足的数据量以保证采样到了数据本来的面目,所以速度相比会慢。或者说生成模型是在模拟数据真实分布。

生成模型的例子:HMM / 朴素贝叶斯。Naive Bayes 需要同时对输入X和输出Y进行建模,得到联合分布P(X,Y),因此是生成模型。由于X是个比较复杂的东西,建模起来很痛苦,于是 Naive Bayes 不得不做了很强的假设,从此一辈子戴上了 “Naive” 的帽子。

3.2 判别模型(Discriminative)

判别模型是直接对 条件概率 P(Y|X) 建模,就是说,直接根据X特征来对Y建模训练。通俗的解释为在给定特征数值后预测结果出现的概率。

判别模型直接将数据的 Y(或者label),根据所提供的 X (features)来学习。训练过程是确定构建 P(Y|X) 模型里面 “复杂映射关系” 中的参数。

判别模型对所有的样本只构建一个模型,确认总体判别边界。观测到输入什么特征,就预测最可能的label,最后画出了一个明显或者比较明显的边界(具体可以通过复杂的函数映射,或者决策叠加等等mechanism做到)。

或者说,判别模型之所以是判别模型,是因为由于去掉了独立性假设,所以不能给出联合概率分布,只能求后验概率,所以是判别模型

判别模型的例子是: 逻辑回归 / SVM / CRF。

判别模型的优点是:对数据量要求没生成式的严格,速度也会快,小数据量下准确率也会好些。

3.3 对比

从概率图角度看,有向图的表达的是一种推演关系,也就是在A的前提下出现了B,这种模型又叫做生成式模型。

无向图表达的是一种“这样就对了”的关系,也就是A和B同时存在就对了,这种模型又叫做判别式模型。

生成式模型一般用联合概率计算 (因为我们知道A的前提了,可以算联合概率)。

判别式模型一般用条件概率计算 (因为我们不知道前提,所以只能"假设"A条件下B的概率)。

生成模型的目标是求联合概率分布P(X,Y),然后由条件公式求取条件概率分布P(Y|X)。即 P(Y|X) = P(X,Y) / P(X)。因为学习联合分布,所以就可以从统计的角度表示数据的分布情况,能够反映同类数据本身的相似度。但它不关心到底划分各类的那个分类边界在哪。

判别模型是由训练数据直接求取决策函数Y=f(x)或者条件概率分布P(Y|X)。它并不需要关心X与Y之间的生成关系,它关心的是对于给定输入X应该得到怎么样的输出Y,不需要先学习出来联合分布P(X,Y) 。不能反映训练数据本身的特性。但它寻找不同类别之间的最优分类面,反映的是异类数据之间的差异。由于直接学习P(Y|X)或f(X),可以对数据进行各种程度上的抽象、定义特征并使用特征,因此可以简化学习问题

3.4 用网上经典例子来解释:

例子1: 比如说要确定一只羊是山羊还是绵羊

判别模型的方法是:

先从历史数据中学习到一个统一的模型,然后通过提取这只羊的特征来预测出这只羊是山羊的概率,是绵羊的概率。我只要学会绵羊和山羊某个特殊差别就好。

比如山羊更擅长攀岩,按照岩壁坡度进行判别,能在45度以上山坡行走的就是山羊,以下是绵羊。

而眼前这个羊走85度山坡如履平地,所以它是山羊。

生成模型的方法:

根据山羊的特征首先学习出一个山羊模型(躯体瘦,角三菱型,呈镰刀状弯曲,一般毛粗而短,毛色多为白色,也有黑色、青色、褐色或杂色的,尾巴往上翘,胆子大,采食灌木嫩枝条)。

根据绵羊的特征学习出一个绵羊模型(躯体丰满,头短,公羊有螺旋状大角,母羊无角或只有细而小的角。毛细蜜、多为白色。 绵羊的嘴唇薄而灵活,适于啃食很短的牧草,性情温顺,胆小,主要吃草)。

然后从这只羊中提取各种特征,放到山羊模型中看概率是多少,再放到绵羊模型中看概率是多少,哪个大就是哪个。

在这个问题中,第一个判别模型方法中你只记住了山羊和绵羊之间的不同之处。第二个生成模型的思路中,你实际上学习了什么是绵羊,什么是山羊。

例子2: 识别一个语音属于哪种语言

例如对面一个人走过来,和你说了一句话,你需要识别出她说的到底是汉语、英语还是法语等。那么你可以有两种方法达到这个目的:

  • 学习每一种语言,你花了大量精力把汉语、英语和法语等都学会了,我指的学会是你知道什么样的语音对应什么样的语言。然后再有人过来对你说话,你就可以知道他说的是什么语音。这就是GM。
  • 不去学习每一种语言,你只学习这些语言模型之间的差别,然后再分类。意思是指我学会了汉语和英语等语言的发音是有差别的,我学会这种差别就好了。这就是DM。

例子3:跟踪算法

  • 生成模型: 一般是学习一个代表目标的模型,然后通过它去搜索图像区域,然后最小化重构误差。类似于生成模型描述一个目标,然后就是模式匹配了,在图像中找到和这个模型最匹配的区域,就是目标了。
  • 判别模型: 将跟踪问题看成一个二分类问题,然后找到目标和背景的决策边界。它不管目标是怎么描述的,那只要知道目标和背景的差别在哪,然后你给一个图像,它看它处于边界的那一边,就归为哪一类。

3.5 如何选择模型?

一般来说,生成式模型需要非常充足的数据量以保证采样到了数据本来的面目。判别模型对数据量要求没生成式的严格。但是也要具体情况具体分析。

比如根据贝叶斯公式,我们知道P(X,Y)=P(X|Y)P(Y)=P(Y|X)P(X), 所以生成模型也可以表示成:P(Y|X)=P(X|Y)P(Y)/P(X)

而我们现在用P(Y|X)=P(X|Y)P(Y)/P(X)这个公式,首先求解的是P(X|Y),所以有些地方也说对P(X|Y)建模为GM(当然也要求P(Y)和P(X)),对P(Y|X)直接建模为DM;意思其实是一样的,以为GM中先对P(X|Y)建模后,可以求出联合分布P(X,Y)=P(X|Y)P(Y),仍可以说是求联合分布为GM。

例如:X=吸烟的人,Y=得肺癌的几率,对P(Y|X)建模可能非常复杂。而对P(X|Y)建模就比较容易,因为对P(X|Y)建模就好像在得肺癌的人里面看吸烟人的情况。我们都知道吸烟的人数亿计,但得肺癌的人毕竟是少数,建模从得肺癌的人出发,更加容易,比如10万个得肺癌的,抽样1000个就差不多了。

4. 最大熵模型概念

最大熵模型是分类器中的 判别模型,它直接计算条件熵。

假定 X为输入特征,Y为类标,有了一定的经验知识,给定一个数据集。判别模型就是要学习一个条件概率分布模型 P(y|x)。这样的分布有无数种,那么在这无数种概率分布中,哪一个才是好的呢?这就是应用最大熵来得到模型。

我们对已知的知识建模,对未知的不过任何假设。换句话说,在给定一组事实(features+output)的条件下,选择符合所有事实,且在其他方面近可能均匀的模型。

  • 基于最大熵原理的最大熵模型就是最符合自然状态下概率分布的模型,所以模型是最可能真实发生的。
  • 最大熵原理通过熵的最大化来表示等可能性(尽可能均匀分布)。“等可能”不容易操作,而熵则是一个可优化的数值指标。
  • 当没有任何约束条件则只需找到熵最大的模型。
  • 若概率模型需要满足一些约束,则最大熵原理就是在满足已知约束的条件集合中,对未知的情况不做任何的主观假设。
  • 此时最好的分布就是符合这个经验知识的前提下,熵最大的分布。即最大熵统计模型获得的是所有满足约束条件的模型中信息熵最大的模型。
  • 我们根据【无知信息最大化熵】的假设来分别对分类现象进行【等可能处理】,进一步得到所有现象出现的概率,从而能够用于预测分类。
  • 对于一个输入X,我们将X导入最大熵模型,得出了一个Y类,这个Y类就是X在这个最符合自然规律分布 (各种可能性均匀分布) 模型下应该归属的类目。

5. 构建最大熵模型

5.1 目的

我们的任务是构造一个统计模型,该模型能够准确表示随机过程的行为。该模型任务是预测在给定上下文 x 的情况下,输出y的概率:p(y|x).

一个分类模型的生成一般分成两步骤:

  • 是从样本中抽取一组决策过程的事实(规则)
  • 是基于这些事实构建这一分类过程的模型。

经验知识就是约束条件,它是靠特征函数来引入的。特征函数f(x,y)描述x与y之间的某一事实(经验知识)。

5.2 推导过程

优化推导的过程:在给定训练集下,即给定约束(经验知识)下,能够得到符合约束的条件概率模型集合{P(y|X)}。

这里我们要将P(y|x)看做是无数个概率分布的集合,即每一个x,都对应一个特定的概率分布P(y|x),每一个概率分布都会有一个熵,此时,所谓的最大熵,就是最大化这些所有的概率分布的熵的和,由于每个x都有一个经验概率P~(x),我们还需要对所有这些熵进行加权求和,以此表示哪一个概率分布的熵的最大化更加重要。

然后使用特征函数的形式,将训练数据融入到条件概率中,最后基于最大熵原理,在所有可能的概率模型(概率分布)中,选择条件熵最大的模型为最终分类模型。故而最大熵模型的学习就是求解约束最优化问题。

最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代算法。GIS 的原理并不复杂,就是用第N次迭代的模型来估算每个特征在训练数据中的分布。大致可以概括为以下几个步骤:

  1. 假定第零次迭代的初始模型为等概率的均匀分布。
  2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则,将它们便大。
  3. 重复步骤 2 直到收敛。即当训练样本的特征分布和模型的特征分布相同时,就求得了最优参数。

5.3 应用

得到了模型的参数数值之后,我们就得到了最大熵模型。

模型得到的结果是 P(y|x) 概率大小, 即给定一个输入x,分别得到不同的y对应的条件概率,根据概率的大小可以将x划分到不同的y中。这样就可以进行分类判断。

注意这里的 P(y|x) 不是跟朴素贝叶斯一样从样本数据中获得先验概率然后计算,而是通过条件熵最大而求得。

0x03 名著中的最大熵模型应用

让我们从规避风险的角度来看。

1. 应用最大熵

水浒传中,宋江去江州充军路过梁山,吴用派人在各个路口等候。

因为吴学究不知道宋江能从哪条路过,所以他在四条路上都排兵了( 今番打听得断配江州,只怕路上错了路头,教大小头领分付去四路等候,迎接哥哥),这样预测的风险最小。所以等到了宋江。

三个人上路行了一日,到晚投客店安歇了,打火做些饭,又买些酒肉请两个公人。宋江对他说道:“实不瞒你两个说:我们今日此去正从梁山泊边过。山寨上有几个好汉闻我的名字, 怕他下山来夺我,枉惊了你们。我和你两个明日早起些,只拣小路里过去,宁可多走几里不肪。”两个公人道:“押司,你不说,俺们如何得知。我等自认得小路过去,定不得撞着他们。”当夜计议定了,次日,起个五更来打火。 两个公人和宋江离了客店。只从小路里走。约莫也走了三十里路,只见前面山坡背后转出一夥人来。宋江看了,只叫得苦。来的王是别人,为头的好汉正是赤发鬼刘唐,将领着三五十人,便来杀那两个公人。这张千,李万,做一堆儿跪在地下。宋江叫道:“兄弟!你要杀谁?”刘唐道:“哥哥,不杀了这两个男女,等甚么!”宋江道:“不要你污了手,把刀来我杀便了。”两个人只叫得苦。刘唐把刀递与宋江。宋江接过,问刘唐道:“你杀公人何意?” 刘唐说道:“奉山上哥哥将令,特使人打听得哥哥官司,直要来郓城县劫牢,却知哥哥不曾在牢里,不曾受苦。今番打听得断配江州,只怕路上错了路头,教大小头领分付去四路等候,迎接哥哥,便请上山。这两个公人不杀了如何?”

2. 不应用 最大熵

这就是三国演义中,华容道例子。

因为诸葛先生手中没有足够兵马,没办法应用最大熵模型。所以为了规避风险,他只能根据曹操特点做了相关谋划最后选定了华容道。

曹操是中国历史巅峰人物,而诸葛亮这种"多智而近妖"的人物在中国历史上是独占鳌头。一个能比普通人多算两步,一个能比普通人多算三步。

但是这种谋划不是我们普通人能作的。我们普通人只能老实的选择最大熵模型。

孔明先生的谋划

时云长在侧,孔明全然不睬。云长忍耐不住,乃高声曰:“关某自随兄长征战,许多年来,未尝落后。今日逢大敌,军师却不委用,此是何意?”孔明笑曰:“云长勿怪!某本欲烦足下把一个最紧要的隘口,怎奈有些违碍,不敢教去。”云长曰:“有何违碍?愿即见谕。”孔明曰:“昔日曹操待足下甚厚,足下当有以报之。今日操兵败,必走华容道;若令足下去时,必然放他过去。因此不敢教去。”云长曰:“军师好心多!当日曹操果是重待某,某已斩颜良,诛文丑,解白马之围,报过他了。今日撞见,岂肯放过!”孔明曰:“倘若放了时,却如何?”云长曰:“愿依军法!”孔明曰:“如此,立下文书。”云长便与了军令状。”云长曰:“若曹操不从那条路上来,如何?”孔明曰:“我亦与你军令状。云长大喜。孔明曰:“云长可于华容小路高山之处,堆积柴草,放起一把火烟,引曹操来。”云长曰:“曹操望见烟,知有埋伏,如何肯来?”孔明笑曰:“岂不闻兵法虚虚实实之论?操虽能用兵,只此可以瞒过他也。他见烟起,将谓虚张声势,必然投这条路来。将军休得容情。”云长领了将令,引关平、周仓并五百校刀手,投华容道埋伏去了。玄德曰:“吾弟义气深重,若曹操果然投华容道去时,只恐端的放了。”孔明曰:“亮夜观乾象,操贼未合身亡。留这人情,教云长做了,亦是美事。”玄德曰:“先生神算,世所罕及!”

曹操的算计

正行时,军士禀曰:“前面有两条路,请问丞相从那条路去?”操问:“那条路近?”军士曰:“大路稍平,却远五十余里。小路投华容道,却近五十余里;只是地窄路险,坑坎难行。”操令人上山观望,回报:“小路山边有数处烟起;大路并无动静。”操教前军便走华容道小路。诸将曰:“烽烟起处,必有军马,何故反走这条路?”操曰:“岂不闻兵书有云:虚则实之,实则虚之。诸葛亮多谋,故使人于山僻烧烟,使我军不敢从这条山路走,他却伏兵于大路等着。吾料已定,偏不教中他计!”诸将皆曰:“丞相妙算,人不可及。”遂勒兵走华容道。此时人皆饥倒,马尽困乏。焦头烂额者扶策而行,中箭着枪者勉强而走。衣甲湿透,个个不全;军器旗幡,纷纷不整:大半皆是彝陵道上被赶得慌,只骑得秃马,鞍辔衣服,尽皆抛弃。正值隆冬严寒之时,其苦何可胜言。

作者:罗西的思考
来源:掘金

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: