注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

最大熵模型与最大似然概率  

2010-03-25 00:26:15|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     对于自然语言处理中的各种模型来说,最大熵模型是一种在形式上最简单,但是在实现上却最复杂的模型。最大熵模型就是在满足已知条件的情况下,求得使熵最大的概率模型。说起来很简单,实际上要求得这个熵最大的概率模型,计算量十分巨大,因此需要仔细设计细节。

      最大熵模型最大的难点来源于特征的选取和参数估计。其中特征选取的需要很多次迭代,在迭代的过程中逐步对参数进行估计。在最大熵模型参数的计算中,因为将特征视为已知,因此需要对已知情况进行计算,而这种计算就是最大似然概率估计算法的特长。    

     最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂,大致可以概括为以下几个步骤:

  1. 假定第零次迭代的初始模型为等概率的均匀分布。
  2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则,将它们便大。
  3. 重复步骤 2 直到收敛。
   上次的文章中讲到最大熵模型最难的部分是训练,因为训练中的数据量巨大,导致计算量巨大。Darroch & Raticliff在1972年提出了GIS算 法来求解。GIS算法是一种通用的求解线性等式约束对数线性规划问题的算法,其核心思想是利用拉格朗日算子,将线性等式约束对数线性规划问题转化为对数线 性规划问题,然后使用求偏导数法将对数线性规划问题转化为迭代求解问题,最后使用梯度递减法求得最优解。GIS算法的效率不高,收敛速度慢,而且不稳定, 容易越界。

    鉴于这些缺陷,最大熵模型并未被广泛使用,但Adwait Ratnaparkhi在1994年的A Maximum Entropy Model for Parsing 论文中成功的使用了最大熵模型进行句法分析。1997年Della Pietra & Lafferty提出了IIS算 法,对GIS进行了改进。IIS算法的前两步与GIS相同,再将线性等式约束对数线性规划问题转化为迭代求解问题后,使用最大似然概率法将问题再次转化为 求最大下界问题,然后使用求偏导数法求得迭代步长,循环迭代得到最优解。Adam Berger对IIS算法进行了十分清晰的解释

    虽然经过了两次改进,最大熵模型的计算量仍然十分巨大,在2001年吴军对最大熵模型进行了进一步改进,提出了层次训练算法。下一篇将详细介绍这一算法。

 上次的文章中讲到吴军在IIS的基础上进一步提出了层次训练算法,其核心思想是利用特征的层次化关系,避免了重复计算,从而把最大熵模型的训练效率提高了几百上千倍。

    最大熵模型的训练的计算量主要来自三个部分:模型参数、特征期望值和归一化因子。模型参数的个数等于特征的个数,可以用IIS中的办法计算 出来,计算量相比特征期望值和归一化因子算是少的,因此主要的计算量集中在后两者。层次训练算法中计算模型参数的方法与GIS和IIS是一样的,主要改进 特征期望值和归一化因子的计算方法。

    最大熵模型中的特征有很多,有些特征具有层次化关系,例如在3-gram模型中,符合一个三元特征的元组通常会符合一个二元特征,因此符合 二元特征的元组集合包含三元特征的元组集合,两者具有层次关系,以此类推,二元特征又跟一元特征具有层次关系。因此,在计算归一化因子的时候,能够将式子 划分成对一元特征、二元特征和三元特征的累加值的和,这样具有同样前向条件的二元元组和三元元组只需计算一次,以后就都能使用二元特征和三元特征的累加 值,只需计算一元特征的累加值,计算量大为下降。同样,在计算特征期望值的时候,由于符合一元特征的元组集合包含二元和三元特征的,可以将求一元特征期望 值的式子划分成一元、二元、三元三个部分,其中二元和三元的部分,只需计算一次,以后具有同样的前向条件的三元元组就不需要计算了,以此类推,二元特征期 望值和三元特征期望值,也可以简化。

    但是,有些模型的特征并不具有层次关系,吴军提出一个通用的层次化特征的办法,这样对于一些诸如主题特征、句法特征、符号特征等无层次的特征的计算也能够进行简化。在此基础上,吴军还进一步简化了归一化因子的计算,将最大熵模型转化ARPA格式,同时对常用的归一化因子和特征期望值进行缓存,计算时间进一步减少。

    以上三篇文章对最大熵模型的训练算法,做了基本介绍,下一篇将讲讲最大熵模型与最大似然概率的关系。

  评论这张
 
阅读(4144)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017