組合范疇語法(CCG)的計算語言學價值

陳　鵬

(1.北京語言大學 信息科學學院，北京　100083； 2.中國社會科學院 哲學所，北京　100732)

?

組合范疇語法(CCG)的計算語言學價值

陳鵬1,2

(1.北京語言大學 信息科學學院，北京100083； 2.中國社會科學院 哲學所，北京100732)

組合范疇語法(CCG)是在AB演算基礎上進行擴展而產生的范疇語法。從語法理論視角看，CCG是一種詞匯形式化的方法；從計算語言學視角看，CCG屬于一類適度上下文相關文法；從邏輯語義學視角看，CCG在句法與語義的接口方面非常融洽。無論是CCG語言的、計算的，還是邏輯的特征，都使得 CCG非常適用于自然語言信息處理，對于計算語言學具有很好的理論和實際價值。

組合范疇語法；語法理論；計算語言學；邏輯語義學；自然語言信息處理；適度上下文相關文法；句法與語義接口融洽

一、引言

肯尼斯·丘奇(Kenneth Church)于2011年在《語言技術中的語言學問題》雜志上發表了一篇題為APendulumSwungTooFar的文章[1]。文中通過整理、分析和研究自1940年以來關于自然語言處理的文章，發現了一個非常有趣的規律，即如果將自然語言處理的文獻劃分為“理性主義”和“經驗主義”兩大類的話，雙方的優勢局面出現連續振蕩的現象，而且存在一個每20年一個周期的規律。兩大類研究的巔峰期分別是：(1)20世紀50年代，以香農(Shannon)、斯金納(Skinner)、弗斯(Firth)和哈里斯(Harris)為代表的經驗主義高峰時期；(2)20世紀70年代由喬姆斯基(Chomsky)、明斯基(Minsky)所主導的理性主義全盛時期；(3)20世紀90年代由IBM語音團隊(IBM Speech Group)、AT&T貝爾實驗室(AT&T Bell Labs)所引發的新一輪經驗主義巔峰時代。

當然，對丘奇的研究，或許我們可以說，理性主義和經驗主義并沒有非常清晰的界定。此外，許多基于算法的統計方法和深度學習方法在傳統分析數學的視角上是一種經驗主義的做法，但是若將圖靈機模型本身看成是一個理性主義產物，那么很多的所謂“經驗主義”方法其實仍然不失為一種“理性主義”成果。姑且拋開對丘奇研究的一些爭議，他的文章對當前學界的一些批判和反思是完全值得我們深思的：

(1) 在實用主義的驅動下，計算語言學領域的教與學的工作向統計學極度傾斜，而邏輯、代數等基礎學科卻得不到應有的發展。

(2) 在經驗主義的誘惑下，學者傾向于采用統計學方法把唾手可得的低枝果實采摘下來，而極少人愿意去攀登更具挑戰性和科研風險的理性主義高峰，為人類的自然語言處理甚至人工智能開拓一條新的道路。

盡管已經過去近5年，然而丘奇所憂慮的問題卻日益凸顯。當今的計算技術發展日新月異，大數據技術甚至推動整個科學領域發生范式轉換，形成所謂的“數據密集型科學研究”。在這種環境下，在整個計算語言學領域，“經驗主義”更是以絕對壓倒性的優勢浩蕩前進，似乎只要在摩爾定律*摩爾定律：集成電路的復雜度(可被間接理解為芯片上可容納的晶體管數目)每兩年增加1倍，性能也將提升1倍。、吉爾德定律*吉爾德定律：主干網帶寬的增長速度至少是運算性能增長速度的3倍。的指導下，只要計算機速度不斷加快、存儲容量不斷擴充、網絡速度不斷提升，一切問題都會迎刃而解。

然而，事實并非如此。實事求是講，近些年，隨著計算和網絡速度與效率的提升，自然語言信息處理能力得到極大的改善，能夠處理的語言信息容量、處理的速度和效率也取得了較大的突破。正如丘奇所說，這些更多的是簡單地應用新技術工具而唾手可得的，那些計算語言學中的“硬核”問題，例如語義問題，并未得到解決。應該說，如果不解決計算語言學中的“硬核”問題，那么我們在語言信息處理方面的成果只能是量變，而不能夠形成質變。

反觀近些年來自然語言信息處理的“理性主義”路線，相比而言，這條研究路線冷清了許多，僅僅是少量的歐洲傳統的自然語言邏輯學派和一些擁有堅定“理性主義”信念的研究者在從事這方面的研究工作。但是，在這些研究工作中，我們發現了一條非常有趣且頗具價值的研究路徑：它源于理性主義，但又不局限于理性主義，其根基已經逐步蔓延到經驗主義的土壤中，并從中吸取養分，在諸多的大規模自然語言處理中獲得廣泛應用。同時，對于一些自然語言處理的“硬核”問題也展開了探索。這項研究就是基于組合范疇語法(CCG)的自然語言信息處理應用。

二、 組合范疇語法CCG

組合范疇語法CCG應該算作是20世紀末的理性主義產物，它在20世紀80至90年代開始出現，在AB演算基礎上進行擴展而產生，其核心的擴展在于“組合”，即基于范疇語法增添了函子范疇的組合運算，從而增強了表達與描述能力。另一方面，由于組合規則與柯里的組合算子非常接近，因此每個組合規則在分析過程中都具有一個語義解讀，這樣使得句法派生的同時，又能夠構造謂詞-論元結構作為語義解讀。

2000年以來，CCG就已經廣泛地應用在計算語言學的各個方面，可以說CCG是計算語言學中的一個全棧模型，從自然語言的分析、轉換到生成等各方面都得到普遍應用[2]。之所以如此，主要有如下兩大方面的原因。

1.在基于CCG的自然語言信息處理系統中，很好地協調了計算、規則和算法幾方面的因素

現代的自然語言信息處理系統都可以抽象為一個三元組〈 R,C,O〉中，其中，R代表規則、C代表計算、O表示Oracle，規則是整個語言信息中的內核，例如上下文無關文法(CFG)或者組合范疇文法(CCG)，計算是在計算系統中實現的算法，O表示一些經驗性的語料或者人為的干涉等。

要想系統發揮最佳作用，〈 R,C,O〉3個部件需要相互協同。例如，如果選擇了一種上下文無關文法來描述自然語言，那么在對該語言進行分析時，就需要設計一種多項式復雜性的計算算法，同時能夠有效地進行消歧。甚至，如果可能的話，需要對上下文無關文法的模型進行概率化，引入一些優選機制來對生成規則進行排序，從而提高處理效率和擴展處理的規模。

〈 R,C,O〉三元組3個部件相互協同，體現了計算語言學中理性主義與經驗主義的調和。正如我國計算語言學家馮志偉所主張的，自然語言處理應該將理性主義與經驗主義結合起來[3]。在自然語言處理中，理性主義與經驗主義各有優缺點。理性主義更貼近自然語言本身，更注重自然語言本身的規則與規律，能有效處理遠距離的主語和謂語動詞之間的一致關系(subject-verb agreement)、wh 移位(wh-movement)等遠距離依存關系(long-distance dependencies)問題；經驗主義在大規模和工程化方面具有顯著優勢，結合強大的計算和信息處理能力，可以進行語言的自動學習和統計分析[3]。

自然語言信息處理系統通常需要這3個部件之間的協同，同時也受到這3個部件之間的彼此約束。例如，如果系統采用了上下文相關文法(1型文法)，那么基于該文法，對自然語言進行分析過程的計算復雜性通常都是NP。反過來，如果你選擇一個計算復雜性較低的文法，例如正則文法(0型文法)，那么又存在該文法在描述和表達能力上不夠強的問題。詳細的關聯情況如圖1所示。

圖1　文法形式化與計算復雜性的關聯

說明：在文法描述上，存在0型文法到3型文法，其中涉及一個表達能力和計算能力的折衷；在計算復雜度方面，存在多項式可計算(P)、指數可計算(NP)、不可計算(圖靈機意義下的不可計算)3個不同的層次。

CCG在規則與計算上做了一個很好的折衷。CCG在文法的描述和表達能力上是介于上下文無關文法(2型文法)和上下文相關文法(1型文法)之間，屬于一類適度上下文相關 (mildly context sensitive) 文法[4]。所謂的適度上下文相關語言具有如下特點：

(1) 有限的交叉依賴。

(2) 連續增長，即如果存在一個界值k，只要有兩個語句之間的長度差異超過k，那么必然存在一個語句，其長度介于這兩個語句之間。

(3) 分析的時間復雜度是多項式復雜度。

除了很好地調和計算、算法和規則幾個因素之外，CCG本身具有一些非常有益于自然語言信息處理的特性。

2.CCG在文法形式化、語言與計算和邏輯語義等方面都具有非常有益于自然語言的計算機信息處理的特性

從自然語言的信息處理視角來看，CCG的優勢主要可以從以下幾個方面來闡述：

(1) 從語法理論方面來看，CCG是詞匯形式化的思路，是以詞作為單位的形式化方法。在進行大規模的自然語言信息處理過程中，CCG的詞匯形式化在處理的信息規模、計算效率和復雜性方面都有比較明顯的優勢。

(2) 從計算語言學方面來看，CCG屬于一類適度上下文相關文法。適度上下文相關文法在描述和表達能力上要明顯優于上下文無關文法，能描述一些在自然語言中經常出現的交叉依賴(Crossing dependencies)現象。分析適度上下文相關語言的時間復雜度通常是在多項式時間復雜度上，這對于計算而言是非常融洽的。

(3) 從邏輯語義學方面來看，CCG是一種組合性的文法。此外，句法與語義之間融洽的接口使得CCG在對自然語言的語義進行分析和計算時非常便捷。

三、CCG的性質：詞匯形式化以及適度上下文相關特性

首先，CCG是一種基于詞匯的形式化理論，即CCG將自然語言生成過程凝縮在詞條的范疇構造上[5]。例如：

(1) S → NP VP

VP → TV NP

TV → {喜歡,愛,…}

(2) 喜歡：= (SNP)/NP

式(1) 是一個上下文無關文法所表達的產生式規則，式(2)是對單個詞指派范疇。可以說通過式(2)中所指派的詞法范疇，捕獲了式(1)中的句法規則。

通過式(2)中的范疇指派，將及物動詞“喜歡”定義為一個函數，并說明了其論元的類型和方向以及結果的類型。例如：“喜歡”作為一個函數，其從右邊接受一個類型為NP的論元，同時計算結果的類型為SNP。

CCG體現的是一種詞本位的思想，形式化聚焦在詞條上，而規則是相對簡潔和緊致的。這種詞匯形式化特性在自然語言信息處理上具有如下優勢：

1.可以為每一種自然語言構建一個CCG范疇語料庫

CCG范疇語料庫中的內容包括覆蓋每一個詞的范疇庫(通常一個詞匯對應1個或者多個范疇)、一些典型語句的加標記CCG范疇派生樹庫。

這樣的CCG范疇語料庫可以為自然語言處理提供如下用途：

(1)作為詞法-范疇字典，可以在語料庫中檢索和查找任何一個詞所對應的范疇(當然，有可能出現多個范疇)。

(2)作為自然語言分析過程中的訓練語料和測試模型。在開發學習器和分析器的過程中，可以使用語料庫進行學習器的訓練語料，同時也作為測試分析器的精度和準確性的測試樣本。

目前，已經有許多語種都開發出相應的CCG范疇語料庫，有些是重新構建，有些是基于以往的一些語料庫進行自動轉換而來。例如：從賓州樹庫轉換而得到的英語CCGBank、漢語CCGBank、德語CCGBank，清華大學漢語樹庫轉換而來的清華CCGBank等。

2.極大地促進大規模自然語言分析工程化的可行性

在基于文法的大規模自然語言分析應用中，普遍存在著歧義性問題，通常每一個句子成分都會對應大量的分析，從而使得解析空間爆炸式增長，極大地提升了各類復雜性，使得大規模應用難以實施與開展。

基于CCG的自然語言分析過程大致可以為分成兩階段：第一階段是將句子中的詞指派詞法范疇，第二個階段便是使用CCG組合規則組合這些范疇。在第一階段中，由于有些詞對應的可能范疇多達上百個*例如，在一個我們從賓州漢語樹庫轉換而來的漢語CCGBank中，“的”一詞對應的范疇就有181個之多。，如果采取完全指派，那么大規模應用顯然是行不通的。因此，在CCG范疇語料庫基礎上，采用了一種稱為“超級標記器”(supertagging)的技術來減少范疇規模。

超級標記器是在進行自然語言分析之前，使用統計序列標記技術(statistical sequence tagging techniques)為語句中的每一個詞都擇優指派少量的詞法范疇，其擇優標準采取的是一種概率模型：

其中，fi代表一種特征，λi是其對應的權重，Z(x)是一個規范化常量。語境是圍繞目標詞的5-詞的窗口，特征通過窗口內的每個詞和每個詞的詞性來定義。

這種超級標記技術，極大地提高了分析的速度和效率。斯蒂芬·克拉克(Stephen Clark)和詹姆斯·柯倫( James R.Curran)的研究表明，采用超級標記技術的CCG分析器比同類型的分析器的速度提升了一個量級(根據他們的實驗，在他們給定的實驗環境下，采用超級標記技術的分析器比未采用超級標記技術的分析器的速度提高了77倍)[6]。

其次，CCG是一種適度上下文相關文法。關于自然語言究竟位于喬姆斯基形式文法的哪一個層級尚存在爭議。首先，喬姆斯基本人否定自然語言是正則語言，但是他也不確認自然語言是否是上下文無關語言。有許多學者根據自然語言出現的一些復雜交叉依賴的現象，認為自然語言必定是超越上下文無關語言，而接近于上下文相關語言。喬希(Joshi)在1985年對自然語言的形式化層次做了一個假設：人類的自然語言是適度上下文相關的[7]。總之，雖然對自然語言究竟屬于哪一形式語言層次尚未有定論，但大多數學者還是傾向于自然語言應該介于上下文無關語言和上下文相關語言之間，類似于適度上下文相關語言。

CCG就是一種適度上下文相關文法，其優勢是處理一些內在于語言構造的遠距離依賴現象。在使用基于CCG的分析器進行語句分析的時候，能夠直接融入遠距離依賴分析，而不需要像其他一些分析器那樣，在后處理階段中再去處理遠距離依賴。例如，在CCG中可以處理一些非常復雜的交叉依賴現象。

例1das mer d’chind em Hans es huus l?nd h?lfe aastriiche.

that we let the children help Hans paint the house

我們讓孩子們幫助漢斯粉刷房間

類似例1這種交叉依賴是不能夠由上下文無關文法來描述的。

CCG的適度上下文相關文法特性使得它在描述與表達能力和計算復雜度之間取得一個較好的折衷。我們可以基于上下文無關文法的移位-歸約(Shift-Reduce)算法，通過修改和增加操作符：{SHIFT,COMBINE,UNARY,FINISH}，便可以獲得基于CCG的移位-歸約分析算法[8]。

例2我愛真理

分析見圖2。

圖2　基于CCG的移位-歸約算法示意：“我愛真理”

四、CCG性質：組合性以及句法與語義接口的融洽性

CCG為句法提供非常直觀的組合語義，使得句法與語義的接口是透明的。CCG只需要在詞條項中增加語義標記，并解釋少量的組合規則，便能提供組合語義。基于CCG透明的句法-語義接口，分析器能夠直接或者間接地訪問謂詞-論元結構。CCG的組合性以及句法與語義接口的融洽性使得分析、處理大規模自然語言的語義成為可能。

組合原則是邏輯語義學的基本原則，是其基礎和出發點。CCG直觀地體現了意義組合原則，其規則中語法與語義嚴格對應，如表1所示。

表1　CCG中范疇與語義規則嚴格對應

CCG通常可以進行句法與語義并行推演，例如：

例3Utah borders Iaho

Utah:= NP :utah

Idaho:= NP :idaho

borders:= (SNP)/NP :λx.λy.

borders(y,x)

在計算語言學中，存在著一些“硬核”任務，或者說是最為困難的任務，其中之一就是對自然語言的語義分析，即將自然語言語句映射為表征其意義的形式化(通常是某種邏輯式)。通過語義分析，將一個自然語言句子，按照特定的句法，解析成邏輯表達式，基于這些邏輯表達式可以實現邏輯和知識操作，并構建相應的頂層應用，例如自動問答系統和知識推理系統等。

CCG在語義分析方面具有較好的優勢，除了能夠結合一些統計、學習的方法之外，CCG還能夠進行一個規則映射。一方面，CCG可以通過類似概率CCG的模型來解決歧義解析問題。另外，CCG的句法與語義接口的融洽性非常有助于語義學習，例如，盧克·澤特爾莫耶(Luke S.Zettlemoyer)等人基于CCG開發了一個語義分析框架[8]，在該框架中使用了一些規則，將邏輯式反向映射為范疇與語義，其規則為：

a.對于一個常元c，那么其輸出的范疇是：

NP:c

b.對于一個一元謂詞p，那么其輸出的范疇是：

N :λx.p(x)

或者

SNP :λx.p(x)

N/N :λg.λx.p(x)∧g(x)

c.對于一個二元謂詞p，那么其輸出的范疇是：

(SNP)/NP :λx.λy.p(y,x)

(SNP)/NP:λx.λy.p(x,y)

N/N:λg.λx.p(x,c)∧g(x)

d.對于一個二元謂詞p和一個常元c，其輸出的范疇是：

N/N:λg.λx.p(x,c)∧g(x)

e.對于一元函數f，其輸出的范疇是：

NP/N:λg.argmax/min(g(x),λx.f(x))

S/NP:λx.f(x)

例如，對于例3中對應的邏輯式：

borders(utah,idaho)

由于utah和idaho都對應兩個常元，因此有：

NP:utah

NP:idaho

此外，borders對應一個二元謂詞，那么有：

(SNP)/NP :λx.λy.borders(y,x)

CCG的反向映射不僅能夠輔助大規模的語義學習，而且使得CCG能夠作為機器翻譯中的中介語言，實現由源語言到邏輯表達式，再由邏輯表達式到“范疇和語義詞項”，再到目標語言的一個三階段機器翻譯的方法，這樣的機器翻譯將使得“意義保真”。

五、結論

以詞匯為核心，能夠描述一類適度上下文相關語言，同時句法與語義可以透明地相互轉換是組合范疇語法CCG的幾個非常顯著的特征，這些特征結合一些統計和學習方法，能夠對自然語言信息處理中一些非常復雜的“硬核”問題的解決有所幫助。

[1]CHURCH K.A Pendulum Swung Too Far[J].Linguistic Issues in Language Technology,2011,6(5):1-27.

[2]The tombinatory categorial grammar site[EB/OL].[2016-03-27].http://groups.inf.ed.ac.uk/ccg/publications.html.

[3]馮志偉.自然語言處理中的理性主義和經驗主義[C].全國民族語言文字信息學術研討會,2007.

[4]EDWARD P S.Varieties of crossing dependencies:structure dependence and mild context sensitivity[J].Cognitive Science,2004,28:699-720.

[5]鄒崇理.關于組合范疇語法CCG[J].重慶理工大學學報(社會科學),2011,25(8):1-5.

[6]CLARK S,CURRAN J R.The importance of supertagging for wide-coverage CCG parsing[C].International conference on computational linguistics.Association for computational linguistics,2004:282-288.

[7]JOSHI A K.How much context sensitivity is necessary for characterizing structural descriptions-tree adjoining grammars[C].Natural Language Processing，1983.

[8]ZHANG Y,CLARK S.Shift-Reduce CCG Parsing[C].Meeting of the association for computational linguistics:human language technologies,proceedings of the conference.Portland:[S.l.],2011:683-692.

[9]ZETTLEMOYER L S,COLLINS M.Learning to map sentences to logical form:structured classification with probabilistic categorial grammars[J/OL].[2016-01-16].Eprint Arxiv,http://arxiv.org/abs/1207.1420,2012:658-666.

(責任編輯張佑法)

Computational Linguistic Value of Combination Category Grammar

CHEN Peng1,2

(1.School of Information Sciences,Beijing Language and Culture University, Beijing 100083, China;2.Philosophy Institute, Chinese Academy of Social Sciences, Beijing 100732, China)

Combination Category Grammar (CCG) is a category grammar extended on the basis of AB calculus. From the perspective of grammar theory, CCG is a lexical formalization; from the perspective of computational linguistics, CCG belongs to a class of mildly context-sensitive grammar; from the perspective of logical semantics, CCG has a friendly interface between syntax and semantics. Either CCG’s language characteristic or logic computational characteristic, even logic characteristic makes CCG much suitable for natural language processing, which is theoretically and practically valuable to computational linguistics.

Combination Category Grammar; grammar theory ; computational linguistics; logical semantics; natural language processing; mildly context-sensitive grammar; friendly interface between syntax and semantics

10.3969/j.issn.1674-8425(s).2016.08.002

主持人語：

中國邏輯學會會長鄒崇理 研究員

B81

A

1674-8425(2016)08-0005-07

《組合范疇語法(CCG)的計算語言學價值》一文，比較深刻地刻畫了CCG的主要性質。其觀點切中了當前計算語言學界的弊端，即大部分研究者都埋頭做關于自然語言處理系統的具體工作，這些是容易收到實效的“低枝果實”，而不愿意去仰望理論的星空，做具有科學探險性質的理論探討。CCG就是計算語言學者理性主義思考的結果，值得計算語言學和邏輯學界的關注。

為了深化對社會選擇理論的認識，《基于理由的偏好防策略投票方案》一文，以丹尼爾·歐歇爾森和斯科特·溫斯坦定義的基于理由的偏好作為基本的偏好關系，研究基于理由的偏好聚合問題，并嘗試構造一個基于理由的偏好投票方案，進而對其是否具有防策略性進行了研究，具有一定的理論創新意義和現實價值。

《論邏輯真理的范圍》一文，通過考察兩大類邏輯系統——實在論邏輯系統和反實在論邏輯系統，發現Henkin的方法能夠給出這些系統的完全性證明。用這種方法可以構造出包含所有系統邏輯真理的集合，而這個集合就是邏輯真理的范圍。該文做出結論：完全性是一個劃分邏輯真理和非邏輯真理的標準。