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

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

(廣東工業大學 計算機學院，廣東 廣州 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>∷=|<λ-team><λ-team>|λ.<λ-team>|(<λ-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演算來進行處理?，F有的方法是加入模態詞(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的數據結構為一個三元組，其中name表示λL-team的含義，function表示λL-team的lambda函數，type表示句法類型。

表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