理论计算机科学电子笔记5(2001)随机Lambek范畴文法Guillaume Bonfante 1Philippe de Groote2LORIA BP 239Campus Scienti queVand uvre-l es-Nancy,法国摘要我们在这里提出了一个随机点的Lambek范畴语法,已显示出其效用在自然语言处理的价值。关键点来自于这样一个事实,即Lambek演算中的解析是基于一个本质上不确定的算法。我们认为随机治疗可能是解决这个问题的好方法。1引言统计方法在自然语言处理中已经被证明是非常成功的。近年来,已经提出了几种随机文法模型,包括基于词汇化上下文无关文法[3]、树邻接文法[16]、依赖文法[2,5]或范畴AB文法[13]的模型。在这篇探索性的论文中,我们提出了一个新的随机语法模型,其独创性来自于基于Lambek范畴语法[8]。该模型具有有趣的特性:概率与句法依赖性有关,而与派生规则无关。此外,它们是在词汇层面上表达的。因此,我们的模型是完全词汇化的。提 供了词汇歧义的处理。 这种处理基于未解决的依赖性。因此,考虑了长距离依赖性。附加在词条上的概率并不是用来用高概率句法分析来近似正确句法分析,而只是作为指导1 电子邮件地址:bonfante@loria.fr2 电子邮件地址:degroote@loria.frc 2001年Elsevier Science B。诉 在CC BY-NC-ND许可下开放访问。2+的+的+的++Guillaume Bonfante和Philippe de Groote在categorial deduction中。因此,范畴类型逻辑的严格纪律并没有丧失。2Lambek演算与证明网我们假定读者熟悉Lambek范畴文法,例如在[1,9,10,11]中所提出的,并着重于Lambek演算[8]和Girard线性逻辑[6]之间存在的关系。请记住,兰贝克演算的公式(或类型)是通过连接词n(直接蕴涵或左除法),=(逆蕴涵或右除法),(合取或乘积)建立在一组原子类型A上的,并且演绎关系是由直觉主义的代数演算指定的,没有任何结构规则。可以将Lambek演算的公式转换为乘法线性逻辑的公式,使得Lambek演算的一个有效的公式当且仅当它的转换是Girard-Yetter循环线性逻辑的一个有效的公式[17]。乘法线性逻辑的公式遵循以下文法:F::=Aj A? j FFjF一元连接词在哪里 表示线性求反,二进制连接词(张量)和析取。(par)对应于乘法连词循环线性逻辑的演绎关系是通过一个经典的单边代数演算来规定的,并且Lambek代数到这样一个经典代数的转换[[ ]]被定义如下:[[A0; : :;An A]]=[[A0]]; : :;[[An]];[[A]]其中:(i) [[a]]=a?对于原子类型,(ii)[[A B]]=[[A]][[B]](iii)[[An B]]= [[A]][[B]]㈣ [[A=B]]= [[A]][[B]](v)[[a]]+=a,对于a,原子type(vi)[[AB]]+=[[B]]+[[A]]+(vii)[[A n B]]=[[B]]㈧[[A=B]]+=[[B]][[A]][[A]]+上述翻译允许定义Lambek演算的证明网[7,14,15]。设A0; :;An一个是拉马克微积分的一个序列。前框架30n.Guillaume Bonfante和Philippe de Groote[[A]]; : :;[[A]];[[A]]+的序列。给定证明框架,公理链接是证明框架的两个叶之间的边,使得装饰这些叶的文字彼此是对偶的(即, A和A?). 由这样一个公理环连接起来的两个结论称为公理环的结论。一个证明框架是一个树序列(而不是一个多集),人们区分公理链的左结论和右结论。证明结构由证明框架和一组公理链接组成,使得:(i) 证明框架的每一叶都是一个公理链的结论;(ii) 公理链接不交叉;更确切地说,对于任何两个公理链接A和B,分别具有左和右结论Al,Ar和Bl,Br,情况不是Al