劉冬寧，鄧春國，滕少華，張巍，梁路

(廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006)

基于輕語義λ-演算的漢語陳述句靈活語序研究

劉冬寧，鄧春國，滕少華，張巍，梁路

(廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006)

目前，自然語言處理已經(jīng)從句法、語法層面走向輕語義層面。對于漢語陳述句的處理，傳統(tǒng)的方法是采用Lambek演算來進(jìn)行處理。但是傳統(tǒng)的Lambek演算無法處理漢語中的靈活語序問題，而現(xiàn)有的方法，如加入模態(tài)詞、新連接詞等，又因為其進(jìn)一步使得本已是NP-hard的Lambek演算時間復(fù)雜度變大，并不適合當(dāng)前的計算機處理?；诖耍撐奶岢隽甩?Lambek演算，即采用Lambek演算來對漢語陳述句進(jìn)行句法演算，并通過Curry-Howard對應(yīng)理論與λ-演算來對漢語陳述句進(jìn)行輕語義模型的構(gòu)建。λ-Lambek演算不僅能夠?qū)h語陳述句進(jìn)行輕語義演算，而且還能對漢語陳述句靈活語序進(jìn)行處理。

Lambek演算；λ-演算；中文陳述句；靈活語序；語義

1 引言

自然語言處理在日常生活當(dāng)中扮演著重要角色[1-3]。隨著大數(shù)據(jù)時代的到來，半結(jié)構(gòu)化的自然語言在計算機處理中有著更高的要求[4]，如機器翻譯、語義搜索等需要更加快速、準(zhǔn)確地處理大量自然語言數(shù)據(jù)，并且需要涉及自然語言中語義或輕量級語義的處理。傳統(tǒng)的方法已難以滿足大數(shù)據(jù)時代的要求，例如，基于概率模型的統(tǒng)計方法難以準(zhǔn)確地進(jìn)行語義分析，而一些過于強調(diào)語義邏輯的方法又會使計算機進(jìn)行處理的時間復(fù)雜度更高。與此同時，基于Lambek演算的自然語言處理有著許多優(yōu)點，它是上下文無關(guān)的[5-6](context-free)、具有代數(shù)語義(Algebra)、關(guān)系語義(Relation)的模型，并能通過Curry-Howard對應(yīng)理論與-演算引入輕量級語義[7]處理。而且由于Lambek演算沒有收縮(contraction)、弱化(weakening)和交換律(exchange)這三條結(jié)構(gòu)規(guī)則的特點[8]，使得Lambek演算在自然語言處理中是可判定的。但同時也因為其缺少了交換律(exchange)規(guī)則，使得不能處理靈活語序。在前人研究中，為了處理漢語陳述句中的靈活語序，分別在Lambek演算中加入了新模態(tài)詞和新連接詞。雖然這些方法在邏輯、數(shù)學(xué)和語言學(xué)范疇內(nèi)形式完美，但其使原本已是NP—Hard的Lambek演算變得更為復(fù)雜，在程序處理中運行效率極低，因此并不可行?；诖?，本文提出了λ-Lambek演算，通過Curry-Howard 對應(yīng)理論將Lambek演算和λ-演算結(jié)合起來，以解決漢語陳述句靈活語序處理的問題，并且有較高的執(zhí)行效率。

2 相關(guān)技術(shù)

2.1 Lambek演算

Lambek演算是由著名的加拿大學(xué)者Joachim Lambek在1958年提出，用于自然語言處理中的句法分析。Lambek演算是基于句法類型的演算，即句子片段中每一個詞語都用一個類型表示，形成類型序列，然后通過類型序列來進(jìn)行演算，從而判定句子的合法性。Lambek演算是上下文無關(guān)的(context-free)，而且具有代數(shù)語義(Algebra)、關(guān)系語義(Relation)的模型，它的連接詞只有三個，即積運算(product)“”、左余運算(left residuation)“”和右余運算(right residuation)“/”。Lambek演算擁有四條規(guī)則(表1)，并具有切割可消除性(cut-free)，這些優(yōu)點使得Lambek演算在形式完美的同時運算簡單，因此適合計算機的處理。

其中，規(guī)則Ⅰ描述了類型消去演算，規(guī)則Ⅱ描述了Lambek演算的結(jié)合性，規(guī)則Ⅲ描述了Lambek演算的傳遞性，規(guī)則Ⅳ描述了演算中的類型是可以提升的，即從簡單類型提升到復(fù)雜類型。

表1 Lambek演算規(guī)則

設(shè)類型序列S={t1,t2,…,tn}，其中tk為類型數(shù)組(k=1,2,…,n)。根據(jù)表1中的規(guī)則，Lambek演算的過程可歸納成以下五步。

Step1 列出句子或句子片段中每一個詞語所有可能的類型，記于數(shù)組tk中；

Step2 對類型序列中每一組類型進(jìn)行組合，得到類型序列數(shù)組arrayS；

Step3 選取類型序列數(shù)組中一個類型序列arrayS[i]={t1[a],t2[b],…,tn[c]}，其中a、b、c分別為類型數(shù)組t1、t2、t3的一個取值；

Step4 對每個類型序列組合arrayS[i]進(jìn)行類型演算；

Step5 if演算結(jié)果為s，then結(jié)束計算，并輸出句子合法，else 跳到step3直到所有類型序列組合都計算完。

2.2 λ-演算

λ-演算[9-11]是一套用于數(shù)學(xué)定義、函數(shù)應(yīng)用和遞歸的形式系統(tǒng)，它是由Alonzo Church 和 Stephen Cole Kleene 在 20 世紀(jì)30年代提出的，在1936年，Alonzo Church運用其證明了判定性問題(Entscheidungsproblem)的一個否定的答案。λ-演算在自然語言處理中可以對語義模型進(jìn)行描述。

定義1 設(shè)λ-term為λ-演算中的一個表達(dá)式，則其BNF定義為<λ-team>∷=|<λ-team><λ-team>|λ.<λ-team>|(<λ-team>)。

在λ-演算中，有三種運算: α-變換，β-歸約和η-變換。α-變換意味著λ表達(dá)式中的變元是可以替換的，但不改變原來含義；β-歸約表達(dá)了函數(shù)代入的語義；η-變換表達(dá)了函數(shù)的等價性，即如果對于任意的x，如果有f(x)=g(x)，則f和g具有函數(shù)等價性。

3 λ-演算及其漢語陳述句靈活語序的處理

(1)

(2)

(3)

因為這種足夠弱，使得Lambek演算無法處理漢語陳述句的靈活語序。對于陳述句“劉強愛看言情片[13]”，我們通過Lambek演算，如式(4)所示。

(4)

其中(I)表示使用表1中的規(guī)則I，由此可見句子“劉強愛看言情片”是合法的，但是對于其話題句靈活語序“言情片劉強愛看”，我們無法使得該句子通過Lambek演算式

(5)

(5)因此，Lambek演算對于漢語陳述句靈活語序的處理是不可行的。因此，我們必須通過某種方式使得句子的演算順序變得能夠使用Lambek演算來進(jìn)行處理。現(xiàn)有的方法是加入模態(tài)詞(Modality)，如鄒崇理[14]提出的方法Moortgat[15]提出的方法和劉冬寧[16]提出的方法，但是這些加入了模態(tài)詞的方法，會使得原已是NP-hard的Lambek演算變得更復(fù)雜，從而不適合計算機的計算，而且不能進(jìn)行輕量級語義處理。針對這個問題，我們通過Curry-Howard對應(yīng)理論，將Lambek演算和λ-演算對應(yīng)起來，從而實現(xiàn)漢語陳述句靈活語序的處理。對應(yīng)后的Lambek演算如式(6)～式(12)所示。

(6)

(7)

(8)

(9)

(10)

(11)

(12)

根據(jù)Curry-Howard對應(yīng)理論及定義1，我們對λ-Lambek演算進(jìn)行定義。

定義2 設(shè)λ-Lambek表達(dá)式(簡寫為“λL-team”)為一個二元組，λL-team={λ-team，TYPE }，其中TYPE為單詞類型。

定義3 設(shè)λ-Lambek演算的句子序列為LS，則LS=(λL-team)*，即句子由若干個λ-team組成。

對應(yīng)的λ-Lambek演算過程如式(13)所示。λyx.Verb(x,y) Noun

(13)

由此可見句子“劉強愛看言情片”是合法句子。對于其靈活語序“言情片劉強愛看”，其演算模型是無法通過演算得到合法句子類型s，其演算過程如式(14)所示。Noun λyx.Verb(x,y)

(14)

因此，無論是傳統(tǒng)的Lambek演算，還是Lambek演算與λ-演算結(jié)合起來的方法都無法對漢語陳述句中的靈活語序進(jìn)行處理。傳統(tǒng)的方法是在Lambek演算中加入了模態(tài)詞，但是其使得本已是NP-hard的Lambek演算變得更復(fù)雜，不適合在計算機中進(jìn)行計算。為此，我們對λ-Lambek演算中的λL-team進(jìn)行預(yù)處理，即修改部分λL-team，從而將靈活語序變成常規(guī)語序，以便于進(jìn)行λ-Lambek演算。整體的演算流程如圖1所示。

圖1 λ-Lambek演算流程圖

(15)

由此可見，句子“言情片劉強愛看”是合法的。

(16)

除此之外，如果陳述句不是簡單句，而是用了形容詞等修飾，則該句子也能通過λ-Lambek演算，例如句子“愛看動人的言情片劉強”，其中形容詞“動人

(17)

由此可見，對于各種靈活語序的λ-Lambek演算， 我們需要對其詞語的λL-team根據(jù)其靈活語序

的結(jié)構(gòu)進(jìn)行修改，然后再對其進(jìn)行演算。

4 λ-演算及其漢語陳述句靈活語序的處理與應(yīng)用

傳統(tǒng)的Lambek演算只能對句子進(jìn)行句法判定，即判定句子句法的合法性，但是不能進(jìn)行輕語義的演算。而λ-演算不僅對Lambek進(jìn)行了補充，使之能夠處理漢語言中靈活語序的問題，而且還能進(jìn)行輕語義的演算。

定義4 設(shè)w為輕語義模型中詞語語義的λL-team，函數(shù)w=sem(parameters[])為語義函數(shù)，其中函數(shù)名sem為詞語的語義，parameters[]為詞語集{w1,w2,…}，表示單詞w的語義作用在詞語集parameters[]之上。

根據(jù)定義4，令“劉強”的λL-team為λx.LIUx，“言情片”的λL-team為λx.xYAN，“愛看”的λL-team為λyx.LIKE(x,y)，則句子“劉強愛看言情片”的語義演算如式(18)所示。

(18)

演算最終得到語義單詞LIKE(LIU,YAN)，其表示動詞“愛看”的主語是“劉強”，謂語是“言情片”。

定義5 設(shè)λ-Lambek演算的樹模型為T，則T的BNF定義為T=(T,T) | leaf，其中l(wèi)eft為詞語的語義。

因此，我們可以通過λ-Lambek演算得到一棵語義二叉樹模型T。λ-Lambek演算過程中，每一個詞語是葉子節(jié)點，在每一次的E或/E演算都得到父節(jié)點，最終生成一棵二叉樹。

二叉樹模型T有兩個性質(zhì): 樹的根節(jié)點對應(yīng)的句法類型必為s；語義相同但語序不同的二叉樹模型T形狀不一致，但其根節(jié)點一致，即表示含有相同語義。

(19)

對于句子“愛看動人的言情片劉強”，其演算流程如式(20)所示。

(20)

對應(yīng)的二叉樹模型如圖2(b)所示。

圖2 句子“動人的言情片劉強愛看”和“愛看動人的言情片劉強”的二叉樹模型

5 實驗驗證

Lambda是一個函數(shù)式表達(dá)式，因此λ-Lambek演算能夠方便地通過計算機程序來實現(xiàn)。

定義6 設(shè)λL-team的數(shù)據(jù)結(jié)構(gòu)為一個三元組，其中name表示λL-team的含義，function表示λL-team的lambda函數(shù)，type表示句法類型。

表2 λ-Lambek演算詞匯表

為了通過程序?qū)嶒瀸崿F(xiàn)λ-Lambek演算，首先需要采集一定的實現(xiàn)數(shù)據(jù)，即詞匯表，本實驗采用已經(jīng)經(jīng)過預(yù)處理的詞匯表，選出的部分?jǐn)?shù)據(jù)如表2所示。實驗分別對句子“劉強愛看言情片”、“愛看動人的言情片劉強”和“言情片愛看劉強”進(jìn)行了程序驗證，結(jié)果如圖3～圖5所示。

圖3 句子“劉強愛看言情片”的程序判定結(jié)果

圖4 句子“愛看動人的言情片劉強”的程序判定結(jié)果

圖5 句子“愛看劉強言情片”的程序判定結(jié)果

由圖3可以看出，對于簡單句子“劉強愛看言情片”，在演算中只需要進(jìn)行兩次函數(shù)代入操作(/E和E)既可得到合法句子的判定結(jié)果。由圖4可以看出，對于復(fù)雜靈活語序，如“愛看動人的言情片劉強”，在演算中需要進(jìn)行三次函數(shù)代入操作以及一次β操作。由圖5可以看出，對于語義上錯誤的句子“愛看劉強言情片”，由于“劉強”的lambda函數(shù)代入“愛看”中無法消去，從而在程序判定中得到“句子非法”，因此該λ-Lambek演算同樣能夠判定非法句子。通過實驗可以證明lambda演算不僅在形式上能夠?qū)h語陳述句靈活語序進(jìn)行判定，還能通過程序進(jìn)行判定，并且有較高的執(zhí)行效率。

6 結(jié)束語

對于自然語言處理，基于Lambek的演算有著許多優(yōu)點，它是上下文無關(guān)的，具有代數(shù)語義(Algebra)、關(guān)系語義(Relation)的模型，并能通過Curry-Howard對應(yīng)理論與λ-演算引入輕量級語義處理。但是由于Lambek演算也存在一些限制，例如由于缺少了Exchange規(guī)則，導(dǎo)致不能處理漢語陳述句中的靈活語序?；诖?，本文采用了λ-Lambek演算，即通過Curry-Howard對應(yīng)理論將λ-演算和Lambek演算結(jié)合起來，對漢語陳述句靈活語序進(jìn)行處理。λ-Lambek演算并不改變Lambek演算的時間復(fù)雜度，因此能很好地適應(yīng)計算機的計算。除此之外，λ-Lambek演算還能進(jìn)行輕量級語義演算，而且通過演算能得到輕語義的二叉樹模型，從而實現(xiàn)句子的輕量級語義分析，并且能夠通過程序進(jìn)行判定。在后續(xù)的工作中，我們將對漢語陳述句進(jìn)行語義分析，從而為語義搜索和機器翻譯提供有力的工具。

[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].中文信息學(xué)報,2014,28(1): 1-7.

[4] 彭煒明，宋繼華，王寧，等. 漢語傳統(tǒng)語法及其在中文信息處理中的應(yīng)用展望[J].中文信息學(xué)報,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]. 中文信息學(xué)報,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] 劉冬寧，湯庸，滕少華，等. 基于時態(tài)數(shù)據(jù)庫的極小子結(jié)構(gòu)邏輯系統(tǒng)[J]. 計算機學(xué)報,2013(8): 1592-1561.

[13] 鄒崇理.多模態(tài)范疇邏輯研究[J].哲學(xué)研究,2006,09: 115-121.

[14] Bernardi,Moortgat.Continuation semantics for the Lambek-Grishin calculus[J].Information & Computation,2010,208(5): 397-416.

[15] 劉冬寧，湯庸，黃昌勤，等. 基于時態(tài)查詢語言的并發(fā)Lambek演算及范疇語法[J].智能系統(tǒng)學(xué)報，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-)，博士，副教授，主要研究領(lǐng)域為人工智能邏輯、數(shù)據(jù)庫與協(xié)同計算。E?mail：liudn@gdut．edu．cn鄧春國(1988-)，碩士研究生，主要研究領(lǐng)域為自然語言處理、數(shù)據(jù)挖掘。E?mail：cidgee@outlook．com滕少華(1952-)，博士，教授，主要研究領(lǐng)域為數(shù)據(jù)庫與協(xié)同計算。E?mail：shteng@gdut．edu．cn

2014-02-24 定稿日期： 2014-06-18

國家自然科學(xué)基金(61402118，61272067，61104156，61370229)；國家科技支撐計劃課題 (2013BAH72B01)

1003-0077(2016)03-0023-07

TP391

A