一、引言

我们在投资的时常常讲不要把所有鸡蛋放在一个篮子里,这样可以降低风险,这其实就是最大熵原理的一个朴素说法,因为当我们遇到不确定性时,就要保留各种可能性。在信息处理中,这个原理同样适用。在数学上,这个原理被称为最大熵原理(the maximum entropy principle)。同样的,当我们在回答,扔一个色子的时候,每个面朝上的概率分别是多少?所有人都会回答说是1/6。这个回答是正确的,但是为什么是1/6而不是其他呢?这里就应用到最大熵原理。对这个“一无所知”的色子,假定每一面朝上的概率相同是最保险的做法。从信息论的角度来解释,就是保留了最大的不确定性,也就是让熵达到最大。

最大熵原理指出,当我们需要对一个随机事件的概率分布进行预测的时候,我们的预测应当满足已知的条件,而对未知的情况不做任何主观的假设。在这种情况下,概率分布最均匀,预测的风险最小。因为这时候概率分布的信息熵最大,所以人们称这种模型为“最大熵模型”。

最大熵模型是由最大熵原理推导实现。在这篇文章中,我们会首先介绍最大熵知识里涉及到的一些数学知识,为后面的数学推导做一些基本铺垫。接着叙述一般的最大熵原理,然后讲解最大熵模型的推到,接着给出最大熵模型的求解过程,即学习过程,最后介绍最大熵模型的学习算法,包括GIS、IIS和拟牛顿法。

二、预备知识

1、记号约定

本文中将大量用到概率统计中的记号,为统一起见,这里做一些约定:

  • 用大写字母表示随机变量(如 X,对于一个六面的骰子,有X∈{1,2,3,4,5,6}),用小写字母表示随机变量中某个具体的取值(如X=x)。
  • 用P(X)表示随机变量X的概率分布,用P(X,Y)表示随机变量X,Y的联合概率分布,用P(Y|X)表示已知随机变量X时随机变量Y的条件概率分布。
  • 用p(X=x)表示X具体取某个取值的概率(如p(X=1)=1/6),在不引起混淆的情况下,也将p(X=x)简记为p(x)。
  • 用P(X=x,Y=y)表示联合概率,p(Y=y|X=x)表示条件概率,两者长分别简记为p(x,y)、p(y|x)。

2、贝叶斯定理

贝叶斯定理是用来描述两个条件概率之间的关系。若记P(A)、P(B)分别表示事件A和事件B发生的概率,P(A|B)表示事件B发生的情况下事件A发生的概率,P(A,B)表示事件发生的概率,则有:

利用两个上式,进一步可得:

这就是贝叶斯公式。

3、熵

熵(entropy)原来是热力学中的概念,后由香农引入到信息论中。在信息论和概率统计中,熵用来表示随机变量不确定性的度量。

4、最大似然估计

若总体X属于离散性,其分布律P{X=x}=p(x;θ),θ∈Θ的形式为已知,θ为待估参数,Θ是θ可能取值的范围。

是来自X的样本,则的联合分布律为:

\[
\prod P(x;\theta)
\]

又设是相应于的一个样本值,则取到观察值的概率,即事件:发生的概率为:

这一概率随着θ而发生变化,它是θ的函数,L(θ)称为样本的似然函数(注意,这里是一只的样本值,它们都是常数)

固定样本值,在θ的可能取值范围内,找到使得似然函数L(θ)达到最大值的参数值,作为参数θ的估计值。即取使:

这样得到的与样本值有关,常记为,称为参数θ的最大似然估计值,而相应的统计量称为参数θ的最大似然估计量。

 

5、拉格朗日乘数

最大熵模型的数学推导中需用到拉格朗日乘子法,这里做一个简单介绍。

问题:求函数z=f(X)在条件下的可能极值点,其中

利用拉格朗日乘子法,可将上述带约束的极值问题转换为无约束极值问题来进行求解,具体步骤如下:

(1)构造函数为拉格朗日乘子。

(2)求解方程组:

求解上述方程组可得,其中就是函数f可能的极值点。

三、最大熵原理

最大熵原理是在1957 年由E.T.Jaynes 提出的,其主要思想是,在只掌握关于未知分布的部分知识时,应该选取符合这些知识但熵值最大的概率分布。因为在这种情况下,符合已知知识的概率分布可能不止一个。我们知道,熵定义的实际上是一个随机变量的不确定性,熵最大的时候,说明随机变量最不确定,换句话说,也就是随机变量最随机,对其行为做准确预测最困难。

从这个意义上讲,那么最大熵原理的实质就是,在已知部分知识的前提下,关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断,这是我们可以作出的唯一不偏不倚的选择,任何其它的选择都意味着我们增加了其它的约束和假设,这些约束和假设根据我们掌握的信息无法作出。

最大熵原理认为,学习概率模型时,在所有可能的概率模型分布中,熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合,而最大熵原理就是在满足约束条件的模型集合中选取熵最大的模型。

直观地,最大熵原理认为要选择的概率模型首先要满足已有的事实,即约束条件。在没有更多信息的情况下,那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。

还是举引言部分的色子的例子,我们知道在仍一枚色子的时,它每个面朝上的概率都是1/6。但是假设这个色子被特殊处理过,已知4朝上的概率是1/3。在这种情况下,每个面朝上的概率是多少?正确的答案是:

已知:

(1)P(x=4) = 1/3

(2)P(x=1)+P(x=2)+P(x=3)+P(x=4)+P(x=5)+P(x=6) = 1

则其他面朝上的概率为:P(x=1)=P(x=2)=P(x=3)=P(x=5)=P(x=6) = [1-P(x=4)]/5 =2/15。

也就是说,我们已知条件必须满足(即面朝上为4的概率是1/3),而对于其他面朝上的概率无法知道,这时对于未知概率分布在猜测分布的时候不能带有任何主观的假设,于是认为其他面朝上的概率是均等的是才是客观正确的,这是因为它刚好符合最大熵原理。

最大熵原理思想简单朴素,导出的数学模型非常漂亮,具有很多良好的特性,因而其应用也十分广泛,如天体物理学、医药、自然语言处理(NLP)等领域。

四、最大熵模型

最大熵原理是统计学习的一般原理,将它应用到分类得到最大熵模型。

假设分类模型是一个条件概率分布P(Y|X),X∈χ⊆代表输入,Y∈γ表示输出,χ和γ分别表示输入和输出的集合。这个模型表示的是对于给定的输入变量X,以条件概率P(Y|X)输出Y。

下面给定一个训练数据集:

学习目标是用最大熵原理选择最好的分类模型。

1、特征函数

用特征函数(feature function)f(x,y)描述输入x和输出y之间的某一个事实。其定义为:

它是一个二值函数,当x和y满足这个事实时取值为1,否则取值为0.

这里,我们假定训练数据集有n个特征函数,即:

例如:假设我们需要判断“打”字是动词还是量词,已知的训练集如下:

通过观察我们发现,“打”前面为数字时,“打”是量词,“打”后面为名词时,“打”是动词。于是,我们就从训练数据集中提取两个特征,分别用特征函数表示为:

定了了这两个特征函数后,对于训练数据,我们就有以下事实:

2、约束条件

(1)经验分布

经验分布式指在训练集T进行统计得到的分布,用表示。

这里,对于给定的训练数据集,我们可以确定联合分布p(x,y)的经验分布和边缘分布p(x)的经验分布,分别以表示,其定义为:

其中,count(x,y)表示训练数据集中(x,y)出现的次数,count(x)表示训练数据中输入x的次数,N表示训练样本集的容量。

备注:这里p(x,y)和p(x)是未知的,而是已知的常量。后面在数学公式推导过程中会经常出现,这里不要搞混淆了。

特征函数f(x,y)关于经验分布的期望值,用表示:

特征函数f(x,y)关于模型p(x,y)的期望值,用表示:

这里,p(x,y)是未知的,我们建模的目标是希望生成p(y|x),所以我们希望用p(y|x)来表示p(x,y)。根据贝叶斯定理,我们有p(x,y)=p(x)p(y|x),而p(x)也是未知,这时,我们可以通过取一个近似值,带入上一个表达式,最终得到定义如下:

如果模型能够获取训练数据中的信息,那么就可以假设这两个期望值相等,即:

或:

我们将上述公式作为模型学习的约束条件。假如有n个特征函数,那么就有n个约束条件。

 

4、最大熵模型定义

假设满足所有的约束条件的模型集合为:

定义在条件概率分布p(y|x)的条件熵为:

则模型集合C中条件熵H(p)最大的模型称为最大熵模型,式中的对数为自然对数。

五、最大熵模型求解(学习过程)

最大熵模型的学习过程就是求解最大熵模型的过程。我们在4.4中定义了最大熵模型,最大熵模型可以形式化为约束最优化的问题。

对于给定的训练数据集以及特征函数,最大熵模型的学习等价于约束最优化问题:

也可以表示为求解最小值问题:

求解上述两个最优化问题的解就可以得到最大熵模型。下面我们通过拉格朗日乘子将约束最优化问题转化为无约束最优化问题。

将原始问题转换成对偶问题,通过求解对偶问题得到原始问题的解。之所以转换为对偶问题求解是因为对偶问题往往更易于求解。

1、原始问题和对偶问题

引入拉格朗日乘子,定义拉格朗日函数为:L(p, λ)

则原始问题为:

对偶问题是:

由于H(p)是关于p的凸函数,则原始问题和对偶问题是等价的。所以要求解最大熵模型,只需要求解对偶问题即可。

首先,我们求解对偶问题内部的极小化问题,是关于λ的函数,将其记为:

Ψ(λ)称为对偶函数。同时,将期解记作:

要求极值问题,我们可以通过偏导来求解。

具体地,求L(p,λ)对p(y|x)的偏导数。

令偏导数为0,即:

情况下,得到:

又已知约束条件,带入上式得:

即:

带回上式得:

其中称为规范化因子,是特征函数,是特征的权值。就是最大熵模型,这里λ是最大熵模型中的参数向量。

 

接下来,就是求解对偶问题外部的极大化问题:

将其解即为:

所以最大熵模型的解为(学习到的最优化模型):

所以,最大熵模型的学习归结为对偶函数Ψ(λ)的极大化。

举骰子的例子。。。todo

2、极大似然估计

下面我们证明对偶函数的极大化等价于最大熵模型的极大似然估计。

在上面,我们得到下式:

将其做一个变换,得到如下公式:

将上式代入,可得:

 

已知训练数据的经验概率分布为,条件概率p(y|x)的对数似然函数为:

推到后得到:

所以,这说明对偶函数Ψ(λ)的极大化和最大似然估计是等价的。

这样,最大熵学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题。

总结:模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计。

六、最大熵模型学习算法

1、通用迭代尺度法(Generalized Iterative Scaling, GIS)

已知最大熵模型为:

GIS算法流程如下:

备注:收敛的条件可以是判断前后两次的差值是否足够小。

其中η类似于学习率,在实际应用中一般取1/C。其中C一般取所有样本数据中最大的特征数量,即

其中

其大致原理可以概括为以下几个步骤:

(1)假定第0次迭代的初始模型为等概率的均匀分布。

(2)用第N次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则将它们变大。

(3)重复步骤(2)直至收敛。

训练数据来自各种天气情况下是否打球的例子:data.txt
其中字段依次是:

play outlook temperature humidity windy

数据如下:

no	sunny	hot	high	FALSE
no	sunny	hot	high	TRUE
yes	overcast	hot	high	FALSE
yes	rainy	mild	high	FALSE
yes	rainy	cool	normal	FALSE
no	rainy	cool	normal	TRUE
yes	overcast	cool	normal	TRUE
no	sunny	mild	high	FALSE
yes	sunny	cool	normal	FALSE
yes	rainy	mild	normal	FALSE
yes	sunny	mild	normal	TRUE
yes	overcast	mild	high	TRUE
yes	overcast	hot	normal	FALSE
no	rainy	mild	high	TRUE

其关键代码如下:

def _sample_ep(self):
    self._ep_ = [0.0] * self._n
    print self._numXY
    for i, xy in enumerate(self._numXY):
        # i是idx,xy=Key是(xi,yi)对,self._numXY[xy]=Value是count(xi,yi)
        # 如:i=0 xy=('rainy', 'no') self._numXY[('rainy', 'no')]=2
        self._ep_[i] = self._numXY[xy] * 1.0 / self._N
        self._xyID[xy] = i

def _zx(self, X):
    ZX = 0.0
    for y in self._Y:
        sum = 0.0
        for x in X:
            if (x, y) in self._numXY:
                sum += self._w[self._xyID[(x, y)]]
        ZX += math.exp(sum)
    return ZX
def _pyx(self, X):
    # calculate p(y|x)
    ZX = self._zx(X)
    results = []
    for y in self._Y:
        sum = 0.0
        for x in X:
            if (x, y) in self._numXY:  # 这个判断相当于指示函数的作用
                sum += self._w[self._xyID[(x, y)]]
        pyx = 1.0 / ZX * math.exp(sum)
        results.append((y, pyx))
    return results

 

def _model_ep(self):
    self._ep = [0.0] * self._n
    for sample in self._samples:
        X = sample[1:]
        pyx = self._pyx(X)
        for y, p in pyx:
            for x in X:
                if (x, y) in self._numXY:
                    self._ep[self._xyID[(x, y)]] += p * 1.0 / self._N

def train(self, maxiter=1000):
    self._initparams()
    for i in range(0, maxiter):
        print "Iter:%d..." % i
        self._lastw = self._w[:]  # 保存上一轮权值
        self._model_ep()
        # 更新每个特征的权值
        for i, w in enumerate(self._w):
            # 参考公式(19)
            self._w[i] += 1.0 / self._C * math.log(self._ep_[i] / self._ep[i])
        print self._w
        # 检查是否收敛
        if self._convergence():
            break

完整代码如下:

# -*- coding:utf-8 -*-
import sys
import math
from collections import defaultdict


class MaxEnt:
    def __init__(self):
        self._samples = []  # 样本集, 元素是[y,x1,x2,...,xn]的元组
        self._Y = set([])  # 标签集合,相当于去重之后的y
        # Key是(xi,yi)对,Value是count(xi,yi),如:{('rainy', 'no'): 2, ('mild', 'no'): 2, ('FALSE', 'no'): 2,...}
        self._numXY = defaultdict(int)
        self._N = 0  # 样本数量
        self._n = 0  # 特征对(xi,yi)总数量
        self._xyID = {}  # 对(x,y)对做的顺序编号(ID), Key是(xi,yi)对,Value是ID
        self._C = 0  # 样本最大的特征数量,用于求参数时的迭代,见GIS原理说明
        self._ep_ = []  # 样本分布的特征期望值
        self._ep = []  # 模型分布的特征期望值
        self._w = []  # 对应n个特征的权值
        self._lastw = []  # 上一轮迭代的权值
        self._EPS = 0.01  # 判断是否收敛的阈值

    def load_data(self, filename):
        for line in open(filename, "r"):
            sample = line.strip().split("\t")
            if len(sample) < 2:  # 至少:标签+一个特征
                continue
            y = sample[0]
            X = sample[1:]
            self._samples.append(sample)  # labe + features
            self._Y.add(y)  # label
            for x in set(X):  # set给X去重
                self._numXY[(x, y)] += 1

    def _initparams(self):
        self._N = len(self._samples)
        self._n = len(self._numXY)
        self._C = max([len(sample) - 1 for sample in self._samples])
        self._w = [0.0] * self._n
        self._lastw = self._w[:]
        self._sample_ep()

    def _convergence(self):
        for w, lw in zip(self._w, self._lastw):
            if math.fabs(w - lw) >= self._EPS:
                return False
        return True

    def _sample_ep(self):
        self._ep_ = [0.0] * self._n
        print self._numXY
        for i, xy in enumerate(self._numXY):
            # i是idx,xy=Key是(xi,yi)对,self._numXY[xy]=Value是count(xi,yi)
            # 如:i=0 xy=('rainy', 'no') self._numXY[('rainy', 'no')]=2
            self._ep_[i] = self._numXY[xy] * 1.0 / self._N
            self._xyID[xy] = i

    def _zx(self, X):
        ZX = 0.0
        for y in self._Y:
            sum = 0.0
            for x in X:
                if (x, y) in self._numXY:
                    sum += self._w[self._xyID[(x, y)]]
            ZX += math.exp(sum)
        return ZX

    def _pyx(self, X):
        # calculate p(y|x)
        ZX = self._zx(X)
        results = []
        for y in self._Y:
            sum = 0.0
            for x in X:
                if (x, y) in self._numXY:  # 这个判断相当于指示函数的作用
                    sum += self._w[self._xyID[(x, y)]]
            pyx = 1.0 / ZX * math.exp(sum)
            results.append((y, pyx))
        return results

    def _model_ep(self):
        self._ep = [0.0] * self._n
        for sample in self._samples:
            X = sample[1:]
            pyx = self._pyx(X)
            for y, p in pyx:
                for x in X:
                    if (x, y) in self._numXY:
                        self._ep[self._xyID[(x, y)]] += p * 1.0 / self._N

    def train(self, maxiter=1000):
        self._initparams()
        for i in range(0, maxiter):
            print "Iter:%d..." % i
            self._lastw = self._w[:]  # 保存上一轮权值
            self._model_ep()
            # 更新每个特征的权值
            for i, w in enumerate(self._w):
                self._w[i] += 1.0 / self._C * math.log(self._ep_[i] / self._ep[i])
            print self._w
            # 检查是否收敛
            if self._convergence():
                break

    def predict(self, input):
        X = input.strip().split("\t")
        prob = self._pyx(X)
        return prob


if __name__ == "__main__":
    maxent = MaxEnt()
    maxent.load_data('data.txt')
    maxent.train()
    print maxent.predict("sunny\thot\thigh\tFALSE")
    print maxent.predict("overcast\thot\thigh\tFALSE")
    print maxent.predict("sunny\tcool\thigh\tTRUE")
    sys.exit(0)

输出结果如下:

[(‘yes’, 0.0041626518719793055), (‘no’, 0.9958373481280207)]
[(‘yes’, 0.9943682102360447), (‘no’, 0.005631789763955373)]
[(‘yes’, 1.4464465173635747e-07), (‘no’, 0.9999998553553482)]

 

2、改进的迭代尺度法(Improved Iterative Scaling, IIS)

TODO

3、拟牛顿法

TODO

七、最大熵模型小结

最大熵模型的优点有:

  •  最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型,作为经典的分类模型时准确率较高。
  •  可以灵活地设置约束条件,通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度。

最大熵模型的缺点有:

  • 由于约束函数数量和样本数目有关系,导致迭代过程计算量巨大,实际应用比较难。

 

打赏

发表评论

电子邮件地址不会被公开。