NLP 最大熵模型 张林 2017.12.15.

Presentation on theme: "NLP 最大熵模型 张林 2017.12.15."— Presentation transcript:

1 NLP 最大熵模型 张林

2 目 录 2 特征和约束 1 3 最大熵模型原理 引例 4 公式，算法及实现

3 一 引例

4 一.引例 最大熵模型的目的： 获取模型中所有满足约束条件的信息熵极大的标签 特点： 1.可以使用任意的复杂相关特征
2.可灵活设置约束条件，通过约束条件的多少调节模型对未知数据的适应度和对已知数据的拟合度 3.能自然解决统计模型中的平滑问题 1.是对随机变量不确定性的度量 2.本质是信息量的期望 3.平均分布是“最不确定”的分布

5 一.引例 简单模拟一个汉语中词性标注的过程：“把”有5个词性标签
在没有任何语料支持情况下，只能使用熵最大的均匀分布，即5种词性出现的概率均为1/5 开始引入一定数量的语料样本，假定样本中有30%的比例被标注为“介词”和“量词”，则可更新约束条件： p(介词)+P(量词)=3/10 p(数词)+p(名词)+p(介词)+P(量词)+p(动词)=1 简单将这5种词性写成集合的形式： {数词，名词，介词，量词，动词} 为“把”的每一个词性分配一个估计值p，即选择模型p作为某一词性出现的概率。 为得到模型，需收集大量语料样本，目标有两个： 1.从样本中抽取一组决策过程的事实（规则） 2.基于规则构建词性标注模型 A：数词---个把月 B：名词---车把，门把 C：介词---把门关上 D：量词---一把伞 E：动词---把门，把住 约束条件：p(词性)总和必须为1 p(数词)+p(名词)+p(介词)+P(量词)+p(动词)=1 继续引入语料，发现量词和名词显著增加，更新约束 如何确定剩下几个词性的概率？？ p(介词)+P(量词)=3/10 p(数词)+p(名词)+p(介词)+P(量词)+p(动词)=1 p(名词)+P(量词)=1/2 已知的约束条件 P(介词)=3/20 P(量词)=3/20 未知的均匀分布（最大熵原则） p(动词)=7/30 p(名词)=7/30 p(数词)=7/30

6 一.引例 随着问题复杂度的增大，出现了两个问题： 1.如何度量模型的均匀度 2.如何找到满足一组约束且最均匀的模型 最大熵方法：
根据已知的只是进行建模，对未知的不做任何假设，简单来说，就是在给定的事实条件下，选择符合所有事实，并使用熵最大的均匀模型

7 二 特征和约束

8 二.特征和约束 根据上例，构造一个概率图模型，产生一个输出y，y属于一个有穷集合Y，输出“把”的词性，输出值y是集合{数词，名词，介词，量词，动词}中的任意一个标签，这个过程会受到上下文信息的影响，将语境因素定义为x，属于有穷集合X。我们的任务在于构造一个统计模型，预测在给定上下文x的情况下，输出y的概率，即p(y|x). 为了得到模型，进行语料样本的收集： (x1,y1),(x2,y2),(x3,y3)…..(xn,yn). 不论收集多少样本，都不会是语言文本的总体，用一个经验分布函数来表达训练样本：

9 f(x,y)= 1 0 二.特征和约束 上下文独立的统计模式 p(介词)+P(量词)=3/10 p(名词)+P(量词)=1/2
若在语料样本中，“一”出现在“把”之前，那么“把”属于“量词”的概率为9/10 引入一个指示函数： f(x,y)= 1 0 X，y满足某一事实 特征 X，y不满足某一事实

10 EP(f𝑖)= 𝑥,𝑦 𝑃 𝑥 𝑃(𝑦|𝑥)𝑓𝑖(𝑥,𝑦)
二.特征和约束 任何样本的统计量都可以表示为特征函数关于经验分布 P (X,Y) 的期望值 ： 语料样本中x的经验分布 EP(f𝑖)= 𝑥,𝑦 𝑃 𝑥,𝑦 𝑓𝑖(𝑥,𝑦) ~ ~ 特征f关于模型的P(y|x)的期望值： ~ EP(f𝑖)= 𝑥,𝑦 𝑃 𝑥 𝑃(𝑦|𝑥)𝑓𝑖(𝑥,𝑦) ~ 样本足够大的情况下，有大数定理，样本与总体同分布，即EP(f𝑖)=EP(f𝑖) 𝑥,𝑦 𝑃 𝑥,𝑦 𝑓(𝑥,𝑦) = 𝑥,𝑦 𝑃(𝑥)𝑃 𝑥|𝑦 𝑓(𝑥,𝑦) ~ ~ 约束等式 ~ ~

11 三 最大熵的原理

12 C= 𝑝∈ 𝑃|𝐸𝑝 𝑓𝑖 =𝐸𝑝 𝑓𝑖 ,(i=1,2,3,…n)
从满足约束的模型集合 CC 中找到使得 P(Y|X)P(Y|X) 的熵最大的即为 MaxEnt 模型了 从满足约束的模型集合 CC 中找到使得 P(Y|X)P(Y|X) 的熵最大的即为 MaxEnt 模型了 三.最大熵原理 假设从训练集中抽出n个特征，相应的有n个特征函数f𝑖(x,y)(i=1,2,3,…n),以及n个约束条件, C 表示满足约束的模型集合, C= 𝑝∈ 𝑃|𝐸𝑝 𝑓𝑖 =𝐸𝑝 𝑓𝑖 ,(i=1,2,3,…n) ~ 最大熵模型就是从满足约束的模型集合 C中找到使得 P(Y|X) 的熵最大的模型 P 约束的几何解释 c1 c2 c3

13 H(p)=- 𝑥,𝑦 𝑃 𝑥 𝑃 𝑦 𝑥 𝑙𝑜𝑔𝑃(𝑦|𝑥)
三.最大熵原理 属于集合C的所有模型P中，最大熵的理念决定我们选择最均匀的分布 条件分布P(y|x)的均匀度定义为条件熵： ~ H(p)=- 𝑥,𝑦 𝑃 𝑥 𝑃 𝑦 𝑥 𝑙𝑜𝑔𝑃(𝑦|𝑥) 熵的基本性质：（|X|为X变量的取值个数） （1）H(X)≥0 （2）H(X)≤log|𝑋|，当且仅当P(X=x)=1/|X| 熵的下界是0，此时的模型没有任何不确定性，熵的上界是log|Y|，即在所有可能的y上均匀分布。

14 P*=arg maxH(P) Find P* = arg maxH(P) =arg max(
三.最大熵原理 当从允许的概率分布模型C中选择模型时，模型p*∈𝐶,使得条件熵𝐻 𝑝 最大 P*=arg maxH(P) P ∈𝐶 该约束问题的完整形式： 目标函数的约束条件： Find P* = arg maxH(P) （1）P(y|x) ≥0 （2） 𝑦 𝑃 𝑦|𝑥 =1 =arg max( P ∈𝐶 ~ - 𝑥,𝑦 𝑃 𝑥 𝑃 𝑦 𝑥 𝑙𝑜𝑔𝑃 𝑦 𝑥 ) 𝑥,𝑦 𝑃 𝑥,𝑦 𝑓(𝑥,𝑦) ~ P ∈𝐶 （3） = 𝑥,𝑦 𝑃(𝑥)𝑃 𝑦|𝑥 𝑓(𝑥,𝑦) ~

15 四 公式，算法及实现

16 Find P* = arg maxH(P) =arg max(
目标函数 四.公式，算法，及实现 =arg max( ~ - 𝑥,𝑦 𝑃 𝑥 𝑃 𝑦 𝑥 𝑙𝑜𝑔𝑃 𝑦 𝑥 ) P ∈𝐶 为解决最优化问题，引入拉格朗日乘子，构造朗格朗日函数 目标函数 目标函数的约束条件： （1）P(y|x) ≥0 （2） 𝑦 𝑃 𝑦|𝑥 =1 𝑥,𝑦 𝑃 𝑥,𝑦 𝑓(𝑥,𝑦) ~ （3） = 𝑥,𝑦 𝑃(𝑥)𝑃 𝑦|𝑥 𝑓(𝑥,𝑦) ~

17 λi (t+1)= λi (t) + 1 𝑀 log E p(f i) Ep(t)(f i)
四.公式，算法，及实现 GIS算法： step1：初始化参数，设置λi(0)等于任意值，如等于0 step2：计算Ep(f i),i=1,2,3…n step3：执行迭代，更新参数 计算Ep(t)(f i), i=1,2,3…n For i=1,2,3…n Do λi (t+1)= λi (t) + 1 𝑀 log E p(f i) Ep(t)(f i) step4：检查收敛条件，若收敛算法结束，否则转到step3 ~ GIS算法用第N次迭代的模型来估算每个特征在训练数据中的分布。 ~ 当训练样本的特征分布和模型的特征分布想通知，就求得了最优化参数。

18 四.公式，算法，及实现 主函数 def load_data(self, file): for line in open(file): fields = line.strip().split() if len(fields) < 2: continue label = fields[0] #第一列为标签 self.labels.add(label) # (label,f) tuple is feature for f in set(fields[1:]): self.feats[(label, f)] += 1 self.trainset.append(fields) #print(self.feats) if __name__ == "__main__": maxent = MaxEnt() maxent . load_data("data.txt") maxent . train() print(maxent.predict("Rainy Happy Dry")) class MaxEnt(object): def __init__(self): self.feats = defaultdict(int) self.trainset = [] self.labels = set()

19 def train(self, max_iter=1000): self._initparams()
四.公式，算法，及实现 主函数 def train(self, max_iter=1000): self._initparams() for i in range(max_iter): print ('iter %d ...' % (i + 1)) self.ep = self.Ep() self.lastw = self.w[:] for i,win in enumerate(self.w): delta = 1.0 / self.M * math.log(self.ep_[i] / self.ep[i]) self.w[i] += delta print(self.w,self.feats) if self._convergence(self.lastw, self.w): break if __name__ == "__main__": maxent = MaxEnt() maxent . load_data("data.txt") maxent . train() print(maxent.predict("Rainy Happy Dry"))

20 def train(self, max_iter=1000): self._initparams()
四.公式，算法，及实现 def train(self, max_iter=1000): self._initparams() for i in range(max_iter): print ('iter %d ...' % (i + 1)) self.ep = self.Ep() self.lastw = self.w[:] for i,win in enumerate(self.w): delta = 1.0 / self.M * math.log(self.ep_[i] / self.ep[i]) self.w[i] += delta print(self.w,self.feats) if self._convergence(self.lastw, self.w): break def _initparams(self): self.size = len(self.trainset) self.M = max([len(record) - 1 for record in self.trainset]) self.ep_ = [0.0] * len(self.feats) for i, f in enumerate(self.feats): #计算经验分布的特征期望 self.ep_[i] = float(self.feats[f])/float(self.size) self.feats[f] = i # 为每一特征函数分配id self.w = [0.0] * len(self.feats) # 初始化权重 self.lastw = self.w

21 eps = [0.0] * len(self.feats)
四.公式，算法，及实现 def Ep(self): eps = [0.0] * len(self.feats) for record in self.trainset: #从训练集中迭代输出特征 features = record[1:] probs = self.calprob(features) # 条件概率 p(y|x) for f in features: for prob, label in probs: if (label, f) in self.feats: # 来自训练数据的特征. idx = self.feats[(label, f)] #获取特征的id # 计算期望 sum(P(x) * P(y|x) * f(x,y))。 其中P(x) = 1 / N eps[idx] += prob * (1.0 / self.size) return eps def train(self, max_iter=1000): self._initparams() for i in range(max_iter): print ('iter %d ...' % (i + 1)) self.ep = self.Ep() self.lastw = self.w[:] for i,win in enumerate(self.w): delta = 1.0 / self.M * math.log(self.ep_[i] / self.ep[i]) self.w[i] += delta print(self.w,self.feats) if self._convergence(self.lastw, self.w): break def calprob(self, features): wgts = [(self.probwgt(features, label), label) for label in self.labels] Z = sum([ w for w, label in wgts]) #归一化参数 prob = [ (w / Z, label) for w, label in wgts] return prob def def probwgt(self, features, label): wgt = 0.0 for f in features: if (label, f)in self.feats: wgt += self.w[self.feats[(label, f)]] return math.exp(wgt)

22 def train(self, max_iter=1000): self._initparams()
四.公式，算法，及实现 def train(self, max_iter=1000): self._initparams() for i in range(max_iter): print ('iter %d ...' % (i + 1)) self.ep = self.Ep() self.lastw = self.w[:] for i,win in enumerate(self.w): delta = 1.0 / self.M * math.log(self.ep_[i] / self.ep[i]) self.w[i] += delta print(self.w,self.feats) if self._convergence(self.lastw, self.w): break def _convergence(self, lastw, w): for w1, w2 in zip(lastw, w): if abs(w1 - w2) >= 0.01: #收敛--终止条件 return False return True

23 四.公式，算法，及实现 主函数 def predict(self, input): #预测函数 features = input.strip().split() prob = self.calprob(features) prob.sort(reverse=True) return prob if __name__ == "__main__": maxent = MaxEnt() maxent . load_data("data.txt") maxent . train() print(maxent.predict("Rainy Happy Dry"))

24 四.公式，算法，及实现 主函数 if __name__ == "__main__": maxent = MaxEnt() maxent . load_data("data.txt") maxent . train() print(maxent.predict("Rainy Happy Dry"))

25 优缺点 优点： 1.可以使用任意的负责相关特征，特征可随意选取，易于更换
2.可灵活设置约束条件，通过约束条件的多少调节模型对未知数据的适应度和对已知数据的拟合度 3.能自然解决统计模型中的平滑问题 4.一般无需独立性假设，每一特征fi对概率分布的贡献由参数λi决定，该参数通过一定的算法迭代训练得到。 缺点： （1） 由于约束函数数量和样本数目有关系，时空开销大 （2）数据稀疏问题严重 （3）对语料库的依赖性较强

26 THANK YOU