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

罗维的博客

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

 
 
 
 
 

日志

 
 

IBM模型学习总结  

2011-03-30 22:31:06|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

作者:罗维

2010-8-16

读书不寻思,如迅风飞鸟之过前,响绝影灭,亦不知圣贤所言为何事,要作何用。惟精心寻思,体贴向身心事物上来,反覆考验其理,则知圣贤之书,一字一句皆有用矣。

------薛宣

1. 讲什么与不讲什么

做学问,一定要严谨。研究问题,一定要弄限定个范畴。这篇文章主要讲述IBM 5个模型中的Model 1和2。由于Model 3、4和5,还不是很熟悉,所以暂时就不详细讲了。以后我会在理解它们后,补充这篇学习总结。

2. IBM模型概述

IBM模型是份经典的研究工作,这5个模型既是当初基于词的统计机器翻译模型的基础,也是现在统计机器翻译中主流技术中的重要一步。作为一个生成模型,IBM模型有着自身"严密"的模型演绎。总的来说,Model 1和2是在一个展开公式下的建模,而Model 3、4和5则是在另一个展开公式下的建模。当然,从模型的复杂程度上讲,这5个模型之间的关系是1<2<3<4<5,从模型参数的包含关系上讲,则是,从模型的计算顺序来讲,是1->2 -> 3 -> 4 -> 5。

以法语(f)和英语(e)为例,如何对法语翻译为英语这项活动建模?从噪声信道模型的角度来讲(其实这最早是Weaver的独特见解),即从贝叶斯主义的角度来讲,我们可以有如下一个基本公式:

(1)

说明:公式(1)中E和F分别表示英文端和法语端的句子。

那么问题求解就变为

(2)

到这里,大家都会,但是IBM的那几位研究员很厉害,他们体会到了更多的信息:

1) Pr(E)和Pr(F|E)均有很好的物理解释。Pr(E),通俗来讲,是表示句子是合法的英语句子的可能性,学术点讲,叫做语言模型;Pr(F|E),通俗来讲,是表示该翻译出的英文句子表达的意思与原来法语句子所表达的意思有多大的相似,或者说表达出多少法语句子中的意思,学术点讲,叫做翻译模型。公式(2)就这样形式化地描述了整个翻译过程中的3个问题——语言模型、翻译模型以及解搜索。

2) 更重要地,他们还看到了翻译模型中的一个隐藏变量——句子间的词语对齐信息。如果词语对齐用符号A表示(原论文中用印刷体a表示),则有:

(3)

这样,他们开始考虑如何对Pr(F,A|E)建模。

在模型1和2中,他们这样描述Pr(F,A|E):

(4)

在模型3、4和5中,他们这样描述Pr(F,A|E):

(5)

好吧,公式(4)和(5)太复杂了,但其实不是的。它们当然是有各自的物理解释和严密的数学推导。对公式(4)的推导将放在第3节中,在此先简要介绍下(4)的物理解释。

公式(4)描述的是一个目标为当给定英文句子E,生成其对应的法语句子F和词语对齐关系A的生成故事(generative story)。为了达到这个目的,我们可以这样做:先根据英语句子E的信息来选择法语句子的长度,而后再根据英语句子的信息和法语句子的长度,确定第一个法语词对应着英语句子中的哪个位置(在一定程度上,表示想翻译英文句子中的个位置上的词),然后再根据英语句子的信息、法语句子的长度以及第一个法语词对应着英语句子中的哪个位置这些信息,来确定法语中选哪个词(在一定程度上,表示该怎么翻译英文句子中的个位置上的词)。不断往后做,就可以完成对英文句子的翻译。换句话说,依照这样的思路,完成了在给定英文句子的情况下,生成出最后的法语句子的工作(体会下,这就是生成模型的一种反映)。很漂亮的想法!

然而这还不够,IBM公司的那几位觉得Model 1和2不够好,就重新换了一个出发点,即推出公式(5),继而推出了Model 3、4和5这些越来越复杂的产物。值得注意的是,Model 1和2中的参数计算并没有浪费,而是依旧被3、4和5用着。

3. 公式(4)的推导

(4)式公式右边是对左边的展开。不用怕它的外表复杂,我们首先看下连乘那一项中的内容到底可以化简为什么。

公式展开可以得到如此多项的乘积,结果已经比较清楚了,因为在这里可以出现很多分子项与分母项的化简,最后可以将该连乘化简为:

(*1)

回到公式(4)的右边,我们依靠(*1)式,可以得到,

(*2)

咋一看,怎么比公式(4)的左边多出一个m,其实没有问题。因为我们注意到,m这个自变量是完全受影响的,可以直接去掉(回顾下,m表示法语端句子的长度,而表示长度为m的句子中每个位置上法语词)。所以有

(*3)

以上完成了公式的证明。因为这,所以我曾经在一次讨论说公式(4))不是一个近似,而是精确地推导展开。

总的来说,公式不去证明也行,但是一定要了解公式所表达的物理意义才行,因为这样才能大概跟上IBM那几位仁兄的思路。

4. Model 1

有了公式(4),我们对其进行化简,可以拿到Model 1和2,换句话说,Model 1和2是在公式(4)的框架下的。当然由于Model 2比1考虑的因素更全面,所以Model 2比1更复杂。好,现在来谈下Model 1。

也许是考虑到隐变量——词语对齐量A的存在,IBM的那几位前辈就想到往EM算法上靠,就是要想办法找到一种期望值及其能在其上完成所谓的E步和M步,所以在应用Lagrange乘数法得到辅助函数关于t(f|e)变量的偏导后,即

(9)

令其等于0,经过若干步我们得到:

(11)

把t(f|e)写在左边,构成公式(11),纯粹是为了给应用EM算法打铺垫。

好,再构造(或说成定义)E步所需要的期望值:

(12)

对比(11),可以看出(12)是其中的一部分,而剩下的那一部分当做归一化系数,当然在归一化的同时,也完成了EM算法的M步。另外,公式(12)的右边也是有物理解释的,我们分两步来认识它:

1) 表示在某一个句对中,法语词f对齐到英语词e的个数(注意,在一个句对中,f或者e出现的次数是任意的,不一定是1次!)。有物理解释才说的过去

2) 公式(12)右边表示,是在概率分布下的统计期望值

综上所述,公式(12)确实描述的是一个具有物理意义的期望,满足了EM算法的E步的要求。

这样,带入(12),(11)就变为:

(13)

当考虑有(S)组句对,我们其实可以写成:

(14)

这时,我们就可以靠着(12)和(14)来做EM,这样理论上是可以求解出t(f|e)这个Model1中仅有的参数。可惜,认真看下公式(12),为了求c(f | e; F, E)这个期望,我们需要计算出所有对齐情况下的,这个时间复杂度至少是,指数级的,难以接受。我们要么找到等价的简化计算公式,要么退而求其次,求解其近似解。幸运的是,我们能够找到等价的简化计算公式。论文中公式(15)到(17)谈的正是这方面的内容,它能将计算复杂度直接降低到O(l+m),一个很可观的级别上了!

5. Model 2

引入新的概念——对齐概率,其实就是在Model 1的基础上,不认为是均匀分布,恒等于。而认为依赖于,形式化表示为

有关的公式推导,除了由于多出了项带来的影响,其余与Model 1是一样的。

6. 模型后话

(1) Model 1和2中由于存在公式来简化计算复杂度,所以可以用EM在完整的词语对齐空间计算出参数解;然而Model 3、4和5则不幸,由于没有公式简化,所以只能选择用EM在一个较优的词语对齐空间的子集中近似地求解参数。

(2) Model 1到5这5个模型,只有Model 1是关于变量的凸函数,存在唯一的极值点,即存在最大值,所以Model 1上用EM算法可以拿到精确解,而Model 2到5由于存在多个极值点,所以用EM算法无论如何,也只能拿到近似解。

(3) 最后讲讲目前我对生成模型与判别模型的差异的认识。

1) 生成模型,乃是精确模型,即所拿到建模的公式中,其参数(我们需要训练的那部分变量)骨子里就已经是描述问题的某一面,有清楚的物理解释。例如这个公式(4)和(5),以及HMM模型等等。如果需要考虑模型的计算可行性,那么可以给模型以合理的简化,正如从公式(4)中拿到Model 1和2,从公式(5)中拿到Model 3、4和5等。

适用于没有类别标注的无监督训练。

2) 判别模型,骨子里就是对问题的近似建模,我们无法从所拿到的公式中看到其中的每一项表达的实际意义。例如,对数线性模型、感知机模型、神经网络模型、SVM等等,我们都没法说出那些参数(我们需要训练的那部分变量)表示什么具体含义。

适用于含有类别标注的有监督训练。


转载请注明出处:http://luowei828.blog.163.com/

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

历史上的今天

评论

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

页脚

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