基于轻语义λ-演算的汉语陈述句灵活语序研究
2016-05-04刘冬宁邓春国滕少华张巍梁路
刘冬宁，邓春国，滕少华，张巍，梁路
(广东工业大学 计算机学院，广东 广州 510006)
基于轻语义λ-演算的汉语陈述句灵活语序研究
刘冬宁，邓春国，滕少华，张巍，梁路
(广东工业大学 计算机学院，广东 广州 510006)
目前，自然语言处理已经从句法、语法层面走向轻语义层面。对于汉语陈述句的处理，传统的方法是采用Lambek演算来进行处理。但是传统的Lambek演算无法处理汉语中的灵活语序问题，而现有的方法，如加入模态词、新连接词等，又因为其进一步使得本已是NP-hard的Lambek演算时间复杂度变大，并不适合当前的计算机处理。基于此，该文提出了λ-Lambek演算，即采用Lambek演算来对汉语陈述句进行句法演算，并通过Curry-Howard对应理论与λ-演算来对汉语陈述句进行轻语义模型的构建。λ-Lambek演算不仅能够对汉语陈述句进行轻语义演算，而且还能对汉语陈述句灵活语序进行处理。
Lambek演算；λ-演算；中文陈述句；灵活语序；语义
1 引言
自然语言处理在日常生活当中扮演着重要角色[1-3]。随着大数据时代的到来，半结构化的自然语言在计算机处理中有着更高的要求[4]，如机器翻译、语义搜索等需要更加快速、准确地处理大量自然语言数据，并且需要涉及自然语言中语义或轻量级语义的处理。传统的方法已难以满足大数据时代的要求，例如，基于概率模型的统计方法难以准确地进行语义分析，而一些过于强调语义逻辑的方法又会使计算机进行处理的时间复杂度更高。与此同时，基于Lambek演算的自然语言处理有着许多优点，它是上下文无关的[5-6](context-free)、具有代数语义(Algebra)、关系语义(Relation)的模型，并能通过Curry-Howard对应理论与-演算引入轻量级语义[7]处理。而且由于Lambek演算没有收缩(contraction)、弱化(weakening)和交换律(exchange)这三条结构规则的特点[8]，使得Lambek演算在自然语言处理中是可判定的。但同时也因为其缺少了交换律(exchange)规则，使得不能处理灵活语序。在前人研究中，为了处理汉语陈述句中的灵活语序，分别在Lambek演算中加入了新模态词和新连接词。虽然这些方法在逻辑、数学和语言学范畴内形式完美，但其使原本已是NP—Hard的Lambek演算变得更为复杂，在程序处理中运行效率极低，因此并不可行。基于此，本文提出了λ-Lambek演算，通过Curry-Howard 对应理论将Lambek演算和λ-演算结合起来，以解决汉语陈述句灵活语序处理的问题，并且有较高的执行效率。
2 相关技术
2.1 Lambek演算
Lambek演算是由著名的加拿大学者Joachim Lambek在1958年提出，用于自然语言处理中的句法分析。Lambek演算是基于句法类型的演算，即句子片段中每一个词语都用一个类型表示，形成类型序列，然后通过类型序列来进行演算，从而判定句子的合法性。Lambek演算是上下文无关的(context-free)，而且具有代数语义(Algebra)、关系语义(Relation)的模型，它的连接词只有三个，即积运算(product)“”、左余运算(left residuation)“”和右余运算(right residuation)“/”。Lambek演算拥有四条规则(表1)，并具有切割可消除性(cut-free)，这些优点使得Lambek演算在形式完美的同时运算简单，因此适合计算机的处理。
其中，规则Ⅰ描述了类型消去演算，规则Ⅱ描述了Lambek演算的结合性，规则Ⅲ描述了Lambek演算的传递性，规则Ⅳ描述了演算中的类型是可以提升的，即从简单类型提升到复杂类型。
表1 Lambek演算规则
设类型序列S={t1,t2,…,tn}，其中tk为类型数组(k=1,2,…,n)。根据表1中的规则，Lambek演算的过程可归纳成以下五步。
Step1 列出句子或句子片段中每一个词语所有可能的类型，记于数组tk中；
Step2 对类型序列中每一组类型进行组合，得到类型序列数组arrayS；
Step3 选取类型序列数组中一个类型序列arrayS[i]={t1[a],t2[b],…,tn[c]}，其中a、b、c分别为类型数组t1、t2、t3的一个取值；
Step4 对每个类型序列组合arrayS[i]进行类型演算；
Step5 if演算结果为s，then结束计算，并输出句子合法，else 跳到step3直到所有类型序列组合都计算完。
2.2 λ-演算
λ-演算[9-11]是一套用于数学定义、函数应用和递归的形式系统，它是由Alonzo Church 和 Stephen Cole Kleene 在 20 世纪30年代提出的，在1936年，Alonzo Church运用其证明了判定性问题(Entscheidungsproblem)的一个否定的答案。λ-演算在自然语言处理中可以对语义模型进行描述。
定义1 设λ-term为λ-演算中的一个表达式，则其BNF定义为<λ-team>∷=
在λ-演算中，有三种运算: α-变换，β-归约和η-变换。α-变换意味着λ表达式中的变元是可以替换的，但不改变原来含义；β-归约表达了函数代入的语义；η-变换表达了函数的等价性，即如果对于任意的x，如果有f(x)=g(x)，则f和g具有函数等价性。
3 λ-演算及其汉语陈述句灵活语序的处理
(1)
(2)
(3)
因为这种足够弱，使得Lambek演算无法处理汉语陈述句的灵活语序。对于陈述句“刘强爱看言情片[13]”，我们通过Lambek演算，如式(4)所示。
(4)
其中(I)表示使用表1中的规则I，由此可见句子“刘强爱看言情片”是合法的，但是对于其话题句灵活语序“言情片刘强爱看”，我们无法使得该句子通过Lambek演算式
(5)
(5)因此，Lambek演算对于汉语陈述句灵活语序的处理是不可行的。因此，我们必须通过某种方式使得句子的演算顺序变得能够使用Lambek演算来进行处理。现有的方法是加入模态词(Modality)，如邹崇理[14]提出的方法Moortgat[15]提出的方法和刘冬宁[16]提出的方法，但是这些加入了模态词的方法，会使得原已是NP-hard的Lambek演算变得更复杂，从而不适合计算机的计算，而且不能进行轻量级语义处理。针对这个问题，我们通过Curry-Howard对应理论，将Lambek演算和λ-演算对应起来，从而实现汉语陈述句灵活语序的处理。对应后的Lambek演算如式(6)～式(12)所示。
(6)
(7)
(8)
(9)
(10)
(11)
(12)
根据Curry-Howard对应理论及定义1，我们对λ-Lambek演算进行定义。
定义2 设λ-Lambek表达式(简写为“λL-team”)为一个二元组，λL-team={λ-team，TYPE }，其中TYPE为单词类型。
定义3 设λ-Lambek演算的句子序列为LS，则LS=(λL-team)*，即句子由若干个λ-team组成。
对应的λ-Lambek演算过程如式(13)所示。λyx.Verb(x,y) Noun
(13)
由此可见句子“刘强爱看言情片”是合法句子。对于其灵活语序“言情片刘强爱看”，其演算模型是无法通过演算得到合法句子类型s，其演算过程如式(14)所示。Noun λyx.Verb(x,y)
(14)
因此，无论是传统的Lambek演算，还是Lambek演算与λ-演算结合起来的方法都无法对汉语陈述句中的灵活语序进行处理。传统的方法是在Lambek演算中加入了模态词，但是其使得本已是NP-hard的Lambek演算变得更复杂，不适合在计算机中进行计算。为此，我们对λ-Lambek演算中的λL-team进行预处理，即修改部分λL-team，从而将灵活语序变成常规语序，以便于进行λ-Lambek演算。整体的演算流程如图1所示。
图1 λ-Lambek演算流程图
(15)
由此可见，句子“言情片刘强爱看”是合法的。
(16)
除此之外，如果陈述句不是简单句，而是用了形容词等修饰，则该句子也能通过λ-Lambek演算，例如句子“爱看动人的言情片刘强”，其中形容词“动人
(17)
由此可见，对于各种灵活语序的λ-Lambek演算， 我们需要对其词语的λL-team根据其灵活语序
的结构进行修改，然后再对其进行演算。
4 λ-演算及其汉语陈述句灵活语序的处理与应用
传统的Lambek演算只能对句子进行句法判定，即判定句子句法的合法性，但是不能进行轻语义的演算。而λ-演算不仅对Lambek进行了补充，使之能够处理汉语言中灵活语序的问题，而且还能进行轻语义的演算。
定义4 设w为轻语义模型中词语语义的λL-team，函数w=sem(parameters[])为语义函数，其中函数名sem为词语的语义，parameters[]为词语集{w1,w2,…}，表示单词w的语义作用在词语集parameters[]之上。
根据定义4，令“刘强”的λL-team为λx.LIUx，“言情片”的λL-team为λx.xYAN，“爱看”的λL-team为λyx.LIKE(x,y)，则句子“刘强爱看言情片”的语义演算如式(18)所示。
(18)
演算最终得到语义单词LIKE(LIU,YAN)，其表示动词“爱看”的主语是“刘强”，谓语是“言情片”。
定义5 设λ-Lambek演算的树模型为T，则T的BNF定义为T=(T,T) | leaf，其中left为词语的语义。
因此，我们可以通过λ-Lambek演算得到一棵语义二叉树模型T。λ-Lambek演算过程中，每一个词语是叶子节点，在每一次的E或/E演算都得到父节点，最终生成一棵二叉树。
二叉树模型T有两个性质: 树的根节点对应的句法类型必为s；语义相同但语序不同的二叉树模型T形状不一致，但其根节点一致，即表示含有相同语义。
(19)
对于句子“爱看动人的言情片刘强”，其演算流程如式(20)所示。
(20)
对应的二叉树模型如图2(b)所示。
图2 句子“动人的言情片刘强爱看”和“爱看动人的言情片刘强”的二叉树模型
5 实验验证
Lambda是一个函数式表达式，因此λ-Lambek演算能够方便地通过计算机程序来实现。
定义6 设λL-team的数据结构为一个三元组
表2 λ-Lambek演算词汇表
为了通过程序实验实现λ-Lambek演算，首先需要采集一定的实现数据，即词汇表，本实验采用已经经过预处理的词汇表，选出的部分数据如表2所示。实验分别对句子“刘强爱看言情片”、“爱看动人的言情片刘强”和“言情片爱看刘强”进行了程序验证，结果如图3～图5所示。
图3 句子“刘强爱看言情片”的程序判定结果
图4 句子“爱看动人的言情片刘强”的程序判定结果
图5 句子“爱看刘强言情片”的程序判定结果
由图3可以看出，对于简单句子“刘强爱看言情片”，在演算中只需要进行两次函数代入操作(/E和E)既可得到合法句子的判定结果。由图4可以看出，对于复杂灵活语序，如“爱看动人的言情片刘强”，在演算中需要进行三次函数代入操作以及一次β操作。由图5可以看出，对于语义上错误的句子“爱看刘强言情片”，由于“刘强”的lambda函数代入“爱看”中无法消去，从而在程序判定中得到“句子非法”，因此该λ-Lambek演算同样能够判定非法句子。通过实验可以证明lambda演算不仅在形式上能够对汉语陈述句灵活语序进行判定，还能通过程序进行判定，并且有较高的执行效率。
6 结束语
对于自然语言处理，基于Lambek的演算有着许多优点，它是上下文无关的，具有代数语义(Algebra)、关系语义(Relation)的模型，并能通过Curry-Howard对应理论与λ-演算引入轻量级语义处理。但是由于Lambek演算也存在一些限制，例如由于缺少了Exchange规则，导致不能处理汉语陈述句中的灵活语序。基于此，本文采用了λ-Lambek演算，即通过Curry-Howard对应理论将λ-演算和Lambek演算结合起来，对汉语陈述句灵活语序进行处理。λ-Lambek演算并不改变Lambek演算的时间复杂度，因此能很好地适应计算机的计算。除此之外，λ-Lambek演算还能进行轻量级语义演算，而且通过演算能得到轻语义的二叉树模型，从而实现句子的轻量级语义分析，并且能够通过程序进行判定。在后续的工作中，我们将对汉语陈述句进行语义分析，从而为语义搜索和机器翻译提供有力的工具。
[1] John Atkinson,Juan Matamala. Evolutionary Shallow Natural Language Parsing[J].Computational intelligence,2012,28(2): 156-175.
[2] Christian Bitter,David A. Elizondo,Yingjie Yang. Natural language processing: a prolog perspective[J].Artificial Intelligence Review,2010,33(1/2): 151-173.
[3] 孙茂松，刘挺，姬东鸿，等. 语言计算的重要国际前沿[J].中文信息学报,2014,28(1): 1-7.
[4] 彭炜明，宋继华，王宁，等. 汉语传统语法及其在中文信息处理中的应用展望[J].中文信息学报,2012,26(4): 50-60.
[5] Joachim Lambek. The Mathematics of Sentence Structure[J].The American Mathematical Monthly,1958,65(3): 153-169.
[6] Michal Kozak.Cyclic Involutive Distributive Full Lambek Calculus is Decidable[J].Journal of logic and computation,2011,21(2): 231-252.
[7] 张亮，尹存燕，陈家骏. 基于语义树的中文词语相似度计算与分析[J]. 中文信息学报,2010,24(6): 23-30.
[8] Bayu Surarso,H. Ono. Cut elimination in noncommutative substructural logics[J].Reports on Mathematical Logic,1996(30): 13-29.
[9] JL Krivine. Lambda Calculus,Types and Models[M]. Ellis Horwood,1993(98): 105-110.
[10] Hindley R.,Seldom J. Introduction to Combinators and lambda-calculus [M]. London: Cambridge University Press,1986: 87-100.
[11] Gerhard Jäger,Anaphora and Type Logical Grammar[M].Springer Netherlands,2005,24:119-125.
[12] 刘冬宁，汤庸，滕少华，等. 基于时态数据库的极小子结构逻辑系统[J]. 计算机学报,2013(8): 1592-1561.
[13] 邹崇理.多模态范畴逻辑研究[J].哲学研究,2006,09: 115-121.
[14] Bernardi,Moortgat.Continuation semantics for the Lambek-Grishin calculus[J].Information & Computation,2010,208(5): 397-416.
[15] 刘冬宁，汤庸，黄昌勤，等. 基于时态查询语言的并发Lambek演算及范畴语法[J].智能系统学报，2009,6: 245-250.
Research of Flexible Word Order in Chinese StatementsBased on Lightweight Semantic λ-calculus
LIU Dongning，DENG Chunguo，TENG Shaohua，ZHANG Wei，LIANG Lu
(School of Computer,Guangdong University of Technology,Guangzhou,Guangdong 510006,China)
Now natural language processing has shifted from syntactic/lexical level to lightweight semantic level. As for the natural language processing of Chinese narrative sentences,the traditional method is using Lambek calculus,Which to process the Chinese statements with a flexible word order. And the present methods,such as adding modal words or new conjunctions,are not suitable for computer processing because they will increase the complexity of the NP-hard Lambek calculus. In response,this paper puts forward the λ-Lambek calculus,which uses Lambek calculus for the syntactic calculus of Chinese statements,and builds the lightweight semantic model of Chinese statements by Curry-Howard theory and λ-calculus. The λ-Lambek calculus can not only process the lightweight semantic calculus for Chinese statements,but also process the statements of flexible word order in Chinese.
Lambek calculus；λ-calculus；Chinese statements；flexible word order；semantic
刘冬宁(1979-)，博士，副教授，主要研究领域为人工智能逻辑、数据库与协同计算。E⁃mail：liudn@gdut．edu．cn邓春国(1988-)，硕士研究生，主要研究领域为自然语言处理、数据挖掘。E⁃mail：cidgee@outlook．com滕少华(1952-)，博士，教授，主要研究领域为数据库与协同计算。E⁃mail：shteng@gdut．edu．cn
2014-02-24 定稿日期： 2014-06-18
国家自然科学基金(61402118，61272067，61104156，61370229)；国家科技支撑计划课题 (2013BAH72B01)
1003-0077(2016)03-0023-07
TP391
A
