陳 功,羅森林,陳開江,馮 揚,潘麗敏
(北京理工大學(xué) 信息與電子學(xué)院信息安全與對抗技術(shù)實驗室,北京 100081)
將自然語言的句法分析進(jìn)行可計算化處理,需要兩個重要元素:語法模型和搜索算法[1]。無論是早期單純的理性主義和經(jīng)驗主義還是如今的兩者結(jié)合,都需要建立一種語法模型,并且在分析過程中采取一種搜索算法得到分析結(jié)果。最早的語法模型就是簡單的上下文無關(guān)語法模型。概率上下文無關(guān)語法(PCFG)是把概率引入到上下文無關(guān)語法規(guī)則而形成的語法規(guī)則模型。但是,經(jīng)典的PCFG實際上是建立在一些非常理想化的獨立性假設(shè)的基礎(chǔ)之上的,而這些假設(shè)并不符合實際,于是造成了PCFG的實際效果不理想。目前的概率上下文無關(guān)語法研究,主要集中在如何突破這些獨立性假設(shè)上。
中國科學(xué)院的張浩和劉群嘗試了祖先節(jié)點相關(guān),父節(jié)點使用的規(guī)則相關(guān)等幾種結(jié)構(gòu)上下文相關(guān)的策略,效果良好[2]。北京大學(xué)計算語言研究所的冀鐵亮等嘗試使用了動詞子語類框架[3],利用了動詞的子語類框架的信息。北京大學(xué)的張耀中嘗試了融合語義和句型信息[4]。這些方法都對突破上下文無關(guān)語法研究中的獨立性假設(shè)的進(jìn)行了嘗試。利用了結(jié)構(gòu)上文,動詞詞匯及語義、句型等信息,對于PCFG模型的改進(jìn)及分析很有參考價值,但是這些方法沒有嘗試與結(jié)構(gòu)下文相關(guān),本文的工作正是通過在概率上下文無關(guān)語法模型中加入結(jié)構(gòu)下文,構(gòu)成了結(jié)構(gòu)下文相關(guān)的概率語法模型。
詞匯化的句法分析是目前自然語言處理研究的趨勢和熱點。概率上下文無關(guān)語法由于其獨立性的假設(shè),脫離詞匯本身,這也是PCFG的一個重要缺陷?;诖?,本文在PCFG中引入了詞匯信息,構(gòu)成了詞匯化的PCFG,彌補(bǔ)了詞匯信息的缺乏。同時,對于模型的分析算法,使用了基于左角分析的Earley改進(jìn)算法,并引入分層的分析策略,進(jìn)一步提高了分析效果。
經(jīng)典的PCFG基于獨立性的假設(shè),對上下文信息利用不足,且沒有用到詞匯信息?;诖吮疚奶岢隽私Y(jié)構(gòu)下文相關(guān)的概率模型(S-PCFG)以及結(jié)合詞匯信息的概率模型(L-PCFG),并在這兩個模型基礎(chǔ)上,提出了結(jié)構(gòu)下文相關(guān)以及結(jié)合詞匯信息的概率模型(SL-PCFG)。
一個 PCFG 的符號系統(tǒng)包括以下成分:
? 一個終結(jié)符的集合,{Wk},k=1,…,V
? 一個非終結(jié)符的集合,{Ni},i=1,…,n
? 一個開始符號,N1
? 一個規(guī)則的集合,{Ni→ζj},(其中ζj是一個終結(jié)符和非終結(jié)符的序列)
概率方面,PCFG給出了由一個非終結(jié)符節(jié)點可能派生出的各種符號序列的概率分布(式(1))。
計算一棵分析樹t的概率P(t),需要進(jìn)行必要的獨立性假設(shè)。經(jīng)典的 PCFG認(rèn)為,施用每一條規(guī)則的概率獨立于上下文和祖先節(jié)點[5]。這樣,假設(shè)t當(dāng)中的所有規(guī)則構(gòu)成了一個規(guī)則的多重集R,那么[2]:
(2)
所得句法分析樹的概率P(t)是建立在PCFG的獨立性假設(shè)基礎(chǔ)上的,主要是以下三條假設(shè):
(1)位置無關(guān)性假設(shè):子節(jié)點概率與子節(jié)點管轄的字符串在句子中的位置無關(guān);
(2)上下文無關(guān)性假設(shè):子節(jié)點概率與不受子節(jié)點管轄的其他字符串無關(guān);
(3)祖先結(jié)點無關(guān)性假設(shè):子節(jié)點概率與導(dǎo)出該節(jié)點的所有祖先節(jié)點無關(guān)。
然而,實際生活中自然語言有著很強(qiáng)的上下文相關(guān)性,子節(jié)點的概率不僅與其祖先節(jié)點有關(guān),還與它的兄弟節(jié)點,它所導(dǎo)出的子節(jié)點相關(guān),面對這樣的歧義,PCFG模型便無法解決。此外,PCFG模型并沒有考慮詞匯的信息,對于詞匯相關(guān)的歧義,它也是無法解決。
由此可見,概率上下文無關(guān)語法在遇到結(jié)構(gòu)依存和詞匯依存問題的時候就顯得無能為力了,因此有必要探索其他的途徑來進(jìn)一步提升概率上下文無關(guān)語法的功能[6]。
PCFG對于上下文信息的利用是不足的,子樹的概率與子樹以外的節(jié)點無關(guān)。針對PCFG的這一點假設(shè),模型認(rèn)為,一個非終結(jié)符重寫出來的節(jié)點受其子規(guī)則約束,符合真實語料中二次重寫(子規(guī)則)統(tǒng)計規(guī)律的非終結(jié)符才能在一次重寫中應(yīng)用。例如,dj=np+vp的重寫過程中(一次重寫)需要考察其中np和vp將會重寫成什么符號(二次重寫),然后再考慮一次重寫是否能成立,這相當(dāng)于在分析中借助了下文的信息來提前驗證上文的預(yù)測。這個模型的規(guī)則表示成非終結(jié)符Ni重寫為幾個一層子規(guī)則r式(2)的形式,而不是重寫為兩個非終結(jié)符(或終結(jié)符),如式(3)所示。
Ni=rj+rk+…+rl
(3)
相應(yīng)地,模型中包含了式(4)所示的概率分布。
(4)
采用這種改進(jìn)的PCFG模型,增加了重寫規(guī)則的分辨率。在自底向上分析或者左角分析的過程中可以快速幫助分析器抉擇,減少不必要的子樹生成。每一個S-PCFG的規(guī)則概率可以理解為一個條件概率,類似于PCFG的規(guī)則概率,S-PCFG的規(guī)則概率計算式如式(5)所示。
需要說明的是,在重寫部分中若出現(xiàn)終結(jié)符(詞性標(biāo)記)則不用二次重寫。
假設(shè)句法樹t當(dāng)中的所有非終結(jié)符構(gòu)成了一個非終結(jié)符的集合N,分析樹的概率計算公式如式(6)所示。
(6)
模型的規(guī)則中所有非終結(jié)符均采用節(jié)點附著子節(jié)點的形式表示,例如字符串形式表示為dj-np-vp=np-nr+vp-v-np(規(guī)則左邊為節(jié)點“dj”附著子節(jié)點“np”“vp”),在葉子節(jié)點上依然是原來標(biāo)記作為節(jié)點類型,一般是詞性標(biāo)記,若結(jié)合下文L-PCFG的話可能是“詞匯/詞性”的形式。
圖1所示為由S-PCFG模型分析出的句法樹。
圖1 S-PCFG的分析樹表示方法
L-PCFG模型是將一些小集合詞性的詞匯關(guān)聯(lián)到規(guī)則中去,是一種部分詞匯化的PCFG,雖然將如名詞、動詞等詞匯考慮到句法分析中后勢必會造成數(shù)據(jù)稀疏,但是對于集合較小,在自然語言使用中更新較慢的詞匯則可以考慮到句法分析中去。經(jīng)對《人民日報》1998年1月的語料進(jìn)行統(tǒng)計之后,可以確定將詞性如表 1所示的詞匯作為預(yù)終結(jié)符(即介于非終結(jié)符和終結(jié)符之間的詞性符號),直接考慮到句法分析中。
表1 詞語集有限的詞性標(biāo)記統(tǒng)計
這些詞性的集合隨著語料增加的分布規(guī)律如圖2 所示(統(tǒng)計語料來源:《人民日報》1998年1月)。從圖 2中可以看出,表 1中所列的詞性對應(yīng)的詞匯是一個收斂的集合,將這些詞性的具體詞匯關(guān)聯(lián)到語法規(guī)則中引起的數(shù)據(jù)稀疏問題并不是很嚴(yán)重,相反,會帶來良好的消歧能力。綜合考慮數(shù)據(jù)稀疏及消歧能力,將相應(yīng)的詞匯信息關(guān)聯(lián)到語法規(guī)則中還是有利的。
圖2 部分詞性集合詞匯分布規(guī)律
為了使規(guī)則表示為“非終結(jié)符重寫為若干預(yù)終結(jié)符”的形式,以方便和其他概率語法模型使用相同的分析算法以及相同的訓(xùn)練算法,設(shè)計L-PCFG將關(guān)聯(lián)詞匯的規(guī)則表示為在需要關(guān)聯(lián)到詞匯時的地方都將詞匯和詞性連在一起作為一個符號,這相當(dāng)于擴(kuò)展了詞性標(biāo)記,示例如圖 3所示,規(guī)則表示為vbar=v+了/u。
圖3 與詞匯關(guān)聯(lián)的規(guī)則實例
經(jīng)過上述方式擴(kuò)展了規(guī)則集之后,可以繼續(xù)使用原來的分析算法進(jìn)行分析,只是在輸入句子后首先要檢查句子中是否存在表 1中所列的詞性,若有則需進(jìn)行預(yù)處理以方便使用該模型進(jìn)行分析。
為實現(xiàn)對句子信息的充分利用來進(jìn)行句法分析,SL-PCFG.對S-PCFG及L-PCFG模型進(jìn)行了結(jié)合見圖4。模型的結(jié)合實質(zhì)上是將各種限制條件疊加使用,疊加的限制條件越多,分析越精確,但是在樹庫資源有限的情況下,開集測試時召回率會有所下降。
圖4 S-PCFG的分析樹表示方法
利用以上四種模型對句法分析的效果參見第四節(jié)的實驗部分。
句法分析算法原理如圖 5所示。對于不同的概率模型,采用同樣的分析算法,只需在規(guī)則提取時采用不同的規(guī)則即可,即分別采用PCFG、S-PCFG、L-PCFG或是SL-PCFG的規(guī)則。
圖5 句法分析算法原理
規(guī)則施用概率的提取采用最大似然估計,不同的概率模型(PCFG、S-PCFG、L-PCFG、SL-PCFG)有著各自的語法規(guī)則,但對于規(guī)則施用概率提取本質(zhì)上都是一樣的。
隨著基于統(tǒng)計的方法在句法分析中逐漸成為主流,語料庫的建設(shè)對于句法分析的研究來說是不可或缺的,從樹庫自動抽取語法規(guī)則并進(jìn)行統(tǒng)計以用于模型的分析是有效易行的。對于以上各模型的語法規(guī)則及概率獲取是比較簡單的,一般做法是:首先統(tǒng)計訓(xùn)練語料中出現(xiàn)的規(guī)則及其次數(shù),然后利用最大似然估計從規(guī)則出現(xiàn)頻率估計出規(guī)則施用概率[7]如式(7)。
加入結(jié)構(gòu)下文信息或小集合詞匯信息模型的規(guī)則施用概率的計算公式跟式(7)本質(zhì)上是一樣的,只是將重寫規(guī)則Ni→ζj改寫為Ni→rj+rk…rl的形式,如式(5)所示;或?qū)⒉糠忠?guī)則中需要關(guān)聯(lián)到詞匯時的地方都將詞匯和詞性連在一起作為一個符號。相應(yīng)的分析樹中的節(jié)點標(biāo)記或部分詞性標(biāo)記也進(jìn)行變換。
具體的標(biāo)記變換如圖 6所示。
圖6 標(biāo)記變換示例
這樣,四個模型的分析算法都是PCFG的分析算法,只要替換不同的規(guī)則集,就構(gòu)造出了結(jié)構(gòu)下文相關(guān)、結(jié)合詞匯信息、結(jié)構(gòu)下文相關(guān)以及結(jié)合詞匯信息的分析器。
根據(jù)獲得的概率規(guī)則庫,我們采用分層分析的算法對待分析的句子進(jìn)行句法結(jié)構(gòu)的自動分析。
分析算法對原有的Earley算法進(jìn)行了改進(jìn),并引入了分層的分析策略。原有的Earley算法是一種典型的自頂向下、自左向右的分析算法。通過對Earley算法進(jìn)行改進(jìn),使用自底向上的分析算法,有效地減少了自頂向下的預(yù)測過程。使用分層的分析算法,有效地解決了消歧性與魯棒性間的矛盾。
1)分層分析算法原理
句法分析的難點是歧義消解,歧義存在的原因在于當(dāng)前模型下無法獲取更多的信息來供分析器判定,因此消歧能力越強(qiáng)的模型其語法規(guī)則的限制條件越多,進(jìn)而造成數(shù)據(jù)的稀疏,使得精確性(準(zhǔn)確率)提高的同時,分析的覆蓋面(召回率)有所下降。分層構(gòu)建句法樹實質(zhì)上是用不同的概率語法模型分析,并且不同層之間共享子樹,為了在魯棒性較好的模型中使用到消歧性較好的模型分析出的子樹,來達(dá)到魯棒性和消歧雙贏的目的。在不同層(使用不同模型)分析過程中,即使某一層未分析成功整個句法樹,但是在下一層分析時仍可共享這一層得到的子樹片段。
分層分析一共四層,四層模型的特點如圖 7所示。只要有一層分析成功,分層分析不再進(jìn)行下去。分層分析的流程圖如圖 8所示。
圖7 四層模型特點
圖8 分層分析流程圖
2)分層分析沖突處理策略
由于分層分析時是將不同語言模型下產(chǎn)生的結(jié)果放在一起,因此在構(gòu)建句法樹過程中遇到?jīng)_突時,采用PCFG模型的概率參數(shù)對沖突進(jìn)行取舍。
采取如下方式:當(dāng)同層分析時,遇到范圍相同、根節(jié)點相同的片段樹時,采用PCFG模型的參數(shù)計算每個片段樹的概率,保留較大概率的片段樹。當(dāng)不同層分析得到相同范圍、根節(jié)點相同的片段樹時,先計算各自在PCFG模型下的概率,較低一層得到的句法樹概率大于較高一層分析得到的句法樹時選擇較低一層得到的樹,否則,優(yōu)先選擇較高一層得到的子樹。
例如,在第四層未分析成功但是產(chǎn)生了部分片段樹的情況下,第三層分析結(jié)束后構(gòu)建出一個片段樹T3,并檢查到已在上一層構(gòu)建出相同根節(jié)點的片段樹T4,則在PCFG下分別計算P(T3)和P(T4),若P(T3)> P(T4)則用T3替代T4,否則選擇T4。
為了驗證各語法模型的分析效果及分層分析結(jié)果,進(jìn)行了各語法模型的分析對比實驗及分層分析的實驗。
本文的算法研究采用BFS-CTC語料庫(Beijing Forest Studio-Chinese Tag Corpus)。其原始語料來源于新聞?wù)Z料中的句子(如Sohu、Sina、人民日報等),句法標(biāo)注集采用北京大學(xué)計算語言學(xué)研究所規(guī)范[8]。目前語料庫中的句子以單句為主,其中的句子基本涵蓋了各種句型及常見語法現(xiàn)象。
實驗的訓(xùn)練數(shù)據(jù)來自于BFS-CTC語料庫中的詞法、句法標(biāo)注集,表 2所示為訓(xùn)練集,共5 488句。閉集測試集是從訓(xùn)練集中抽樣的句子,共549句,平均每句13詞;開集測試為對以上5 488句數(shù)據(jù)源的十字交叉驗證。
表2 訓(xùn)練用句子句式分布表
句法分析模型的評測算法采用的是PARSEVAL句法分析評價體系[9]。主要由準(zhǔn)確率(Precision,體現(xiàn)準(zhǔn)確性)、召回率(Recall,體現(xiàn)全面性)兩部分組成。F1值(Precision與Recall的調(diào)和均值)是用來綜合評價準(zhǔn)確性和全面性的指標(biāo)。
實驗中,首先分別利用PCFG、L-PCFG、S-PCFG、SL-PCFG進(jìn)行單模型的句法分析實驗,其結(jié)果如表 3所示;結(jié)合得到的PCFG、L-PCFG、S-PCFG、SL-PCFG四種模型的概率規(guī)則庫,采用分層分析算法針對相同數(shù)據(jù)進(jìn)行實驗,其結(jié)果如表 4所示。
表3 各個語法模型對比實驗結(jié)果
表4 分層分析實驗結(jié)果
表3的結(jié)果表明:集合了S-PCFG和L-PCFG兩個模型的SL-PCFG的消歧能力最強(qiáng),因此在閉集測試時能夠得到最好的效果。但是, 與此同時帶來了數(shù)據(jù)稀疏的問題;在開集測試時雖然準(zhǔn)確率仍然很高,但是召回率已經(jīng)銳減到0.272了,說明已經(jīng)出現(xiàn)了大量分析不成功的句子。S-PCFG模型與PCFG模型相比,準(zhǔn)確率與召回率在閉集測試時均有較大程度的提高,但是召回率在開集測試時也有所下降。L-PCFG模型與PCFG模型相比,準(zhǔn)確率有了一定程度的提高,說明加入部分詞匯信息對于結(jié)構(gòu)歧義的消除有一定效果,但對于句子分析成功與否的作用并不明顯。
表5列出了相關(guān)中文句法分析器在賓州中文樹庫測試集上的結(jié)果。其中分析效果比較顯著的有Jiang作業(yè)論文[15]將Collins模型移植成中文句法分析器,F(xiàn)1值達(dá)到了81.1%;中國科學(xué)院的米海濤[16]等(2008)利用多子模型句法分析系統(tǒng)將中心詞驅(qū)動模型和結(jié)構(gòu)上下文模型按照對數(shù)線性模型融合在一起,形成多子模型句法分析器,F(xiàn)1值達(dá)到了82.5%的較高水準(zhǔn);Petrov & Klein[17](Berkeley Parser)在PCFG模型基礎(chǔ)上利用隱含特征(PCFG-LA),同時并行的采用EM算法進(jìn)行訓(xùn)練,得到了一個不依賴于特定語言的句法分析器,Mary P.Harper & Zhongqiang Huang[19]用此句法分析器在CTB上對漢語進(jìn)行了句法分析,得到了82.7%的準(zhǔn)確率及83.1%的召回率,一定程度上減小了中、英文在句法分析結(jié)果上的差距;哈爾濱工業(yè)大學(xué)的曹海龍等[18]以著名的中心驅(qū)動模型為基礎(chǔ),結(jié)合中心成分決策表和基本名詞短語,采用CYK分析算法,在CTB公共測試集上得到了85.89%的準(zhǔn)確率和85.61%的召回率,這是目前已知的中文句法分析的最好分析結(jié)果。
表5 漢語相關(guān)句法分析性能比較
表4所示為論文中所述漢語句法分析的分析結(jié)果。與表5所示各漢語句法分析器實驗結(jié)果相比,雖然結(jié)果較好,但由于采用的是實驗室自己的語料,可比性存在著一定的問題。因此,暫時只能跟傳統(tǒng)的PCFG模型進(jìn)行比較,以體現(xiàn)結(jié)合結(jié)構(gòu)下文信息,結(jié)合部分詞匯信息對PCFG模型描述能力的提高。同時,有力地說明了結(jié)合結(jié)構(gòu)下文及部分詞匯信息的分層分析方法的有效性。
結(jié)合表 3、表 4可以看出,分層分析在開集和閉集測試都能得到良好的效果。分層分析中依靠消歧能力較強(qiáng)的SL-PCFG和S-PCFG提高分析的準(zhǔn)確率,依靠魯棒性較好的L-PCFG和PCFG來提高分析的全面性,從而得到準(zhǔn)確率與全面性的共同提高。開集測試的結(jié)果尤為明顯。
PCFG模型上下文無關(guān)的假設(shè)是必須要進(jìn)行突破的,同時詞匯信息的引入也是必不可少的[2]。本文基于以上的兩點考慮,首先在PCFG結(jié)構(gòu)獨立性假設(shè)基礎(chǔ)上引入了結(jié)構(gòu)下文信息;然后在PCFG中引入了詞匯化。實驗結(jié)果表明,基于以上兩點所做的改進(jìn)很大程度上增強(qiáng)了句法分析的消歧能力。同時,針對由于S-PCFG及SL-PCFG引入了較多的規(guī)則條件,而出現(xiàn)數(shù)據(jù)稀疏的問題,本文采用了分層分析算法。利用SL-PCFG和S-PCFG消歧能力較強(qiáng)的特點,利用L-PCFG和PCFG魯棒性較好的特點,結(jié)合不同模型的優(yōu)點,兼顧了句法分析的準(zhǔn)確性以及全面性。
[1]苗奪謙,衛(wèi)志華.中文文本信息處理的原理與應(yīng)用[M].北京:清華大學(xué)出版社,2007.
[2]張浩,劉群,白碩.結(jié)構(gòu)上下文相關(guān)的概率句法分析[C]//第一屆學(xué)生計算語言學(xué)研討會.北京,2002,46-51.
[3]冀鐵亮,穗志方.詞匯化句法分析與子語類框架獲取的互動方法[J].中文信息學(xué)報.2007(01):120-126.
[4]張耀中.融合語義和句型信息的中文句法分析方法研究與實現(xiàn)[D].北京大學(xué),2009.
[5]Manning,C.,Schütze,H.Foundations of Statistical Natural Language Processing[M].Massachusetts:MIT Press,1999.
[6]馮志偉,自然語言處理中的概率語法[J].當(dāng)代語言學(xué).2005(2).
[7]Charniak,E.Treebank Grammars[R].Providence:Department of Computer Science,Brown University,1996.
[8]周強(qiáng).漢語語料庫的短語自動劃分和標(biāo)注研究[D].北京:北京大學(xué),2002.
[9]Charniak,E.1997.Statistical Parsing with a Context-free Grammar and Word Statistics[C]//Proceedings of National Conference on Artificial Intelligence(NCAI)-1997,598-603.
[10]Daniel M.Bikel,David Chiang.Two statistical parsing models applied to the Chinese Treebank[C]//Proceedings of ACL 2nd Chinese Language Processing Workshop,2000.1.
[11]Roger Levy,Christopher D.Manning.Is it harder to parse Chinese,or the Chinese Treebank[C]//Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics,2003.439.
[12]Deyi Xiong,Shuanglong Li,QunLiu,Shouxun Lin,and Yueliang Qian.Parsing the Penn Chinese Treebank with semantic knowledge[C]//Proceedings of IJCNLP’05,2005.
[13]Daniel M.Bikel On the Parameter Space of Generative Lexicalized Statistical Parsing Models[D].Pennsylvania:Thesis of University of Pennsylvania,2004.
[14]David Chiang,Daniel M.Bikel.Recovering latent information in treebanks[C]//COLING ’02 Proceedings of the 19th international conference on Computational linguistics-Volume 1,2002.
[15]Zhengping Jiang Statistical Chinese parsing[D].Singapore:National University of Singapore,2004.
[16]米海濤,熊德意,劉群.中文詞法分析與句法分析融合策略研究[J].中文信息學(xué)報.2008,22(2):10-17.
[16]Slav Petrov,Dan Klein.Improved inference for unlexicalized parsing[C]//Human Language Technologies 2007:The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference.Rochester,New York,2007:404-411.
[18]曹海龍,趙鐵軍,李生.基于中心驅(qū)動模型的賓州中文樹庫(CTB)句法分析[J].高技術(shù)通訊.2007,17(1):15-20.
[19]MaryP.Harper,Zhongqiang Huang.Chinese Statistical Parsing[C]//Joseph Olive,John McCary,and Caitlin Christianson (eds).Handbook of Natural Language Processing and Machine Translation.Defense Advanced Research Projects Agency,Reston Virginia,2011:90-102.