基于序列標(biāo)注模型的分層式依存句法分析方法

鑒 萍，宗成慶

(中國(guó)科學(xué)院 自動(dòng)化研究所 模式識(shí)別國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

1 引言

目前，基于圖的分析模型[1-2]和基于轉(zhuǎn)換的(也稱為基于分析動(dòng)作的)分析模型[3-4]是主流的數(shù)據(jù)驅(qū)動(dòng)依存句法分析方法。McDonald和Nivre[5]詳細(xì)比較了這兩類模型并給出了二者因算法上的本質(zhì)差別而導(dǎo)致的分析性能上的差異。簡(jiǎn)單來(lái)說(shuō)，以最大生成樹方法為代表的基于圖的依存分析將一棵依存樹的打分看作是所有依存關(guān)系分值的總和，把依存分析問(wèn)題轉(zhuǎn)化為如何尋找得分最高的依存樹。此方法在全句范圍內(nèi)窮盡搜索，算法的時(shí)間復(fù)雜度在投射性條件下是O(n3)(n是輸入句子所含詞的個(gè)數(shù))；基于轉(zhuǎn)換的方法使用分類器選擇當(dāng)前分析狀態(tài)下最可能的分析動(dòng)作來(lái)實(shí)現(xiàn)狀態(tài)的確定性轉(zhuǎn)移，以得到輸入句子的最優(yōu)依存樹，每一步?jīng)Q策只作用于當(dāng)前格局(configuration)的焦點(diǎn)詞對(duì)上。由此看來(lái)，基于圖的方法和基于轉(zhuǎn)換的方法分別以整個(gè)句子和一個(gè)詞對(duì)為搜索最優(yōu)結(jié)構(gòu)的基本單位，是依存分析的兩個(gè)極端。本文中，我們將引入一個(gè)處于中間位置的結(jié)構(gòu)單元——依存層，來(lái)建立句法分析模型。

這里所指的依存層由在依存樹中依存關(guān)系深度不大于1的詞組成。輸入句子的依存結(jié)構(gòu)用依存層分割開來(lái)，便有可能采用不同的處理方式。在層內(nèi)，我們窮盡搜索這些詞之間的最優(yōu)依存關(guān)系組合；在層與層之間，已得到的依存結(jié)構(gòu)可以被確定性地傳遞。這種做法一方面可以降低搜索整棵樹所帶來(lái)的計(jì)算代價(jià)，另一方面則能減輕決策的完全確定性所導(dǎo)致的錯(cuò)誤傳遞。因?yàn)槭菍浣Y(jié)構(gòu)分解為層結(jié)構(gòu)，本方法適用于分析滿足投射性條件的語(yǔ)言。

我們知道，語(yǔ)塊分析可以作為完全句法分析一個(gè)有效的前處理單元，而序列標(biāo)注技術(shù)已能很好地處理這類任務(wù)[6-7]。受此啟發(fā)，我們嘗試用序列標(biāo)注模型來(lái)構(gòu)建依存層最優(yōu)子結(jié)構(gòu)，將依存句法分析問(wèn)題轉(zhuǎn)化為一系列典型序列標(biāo)注問(wèn)題進(jìn)行求解，從而考查序列標(biāo)注模型求解層次結(jié)構(gòu)問(wèn)題的能力。

為方便起見，我們將這種基于序列標(biāo)注模型的分層式方法稱作基于層的依存分析方法。在英漢標(biāo)準(zhǔn)樹庫(kù)上的實(shí)驗(yàn)表明，基于層的分析方法能夠獲得與主流方法可比的分析精度，但在分析效率上有很大優(yōu)勢(shì)。在相同系統(tǒng)環(huán)境下，分析速度可達(dá)其他方法現(xiàn)有實(shí)現(xiàn)的十幾到上百倍。

文章組織如下：在第2節(jié)中詳細(xì)闡述基于層的依存分析方法及相關(guān)問(wèn)題；第3節(jié)給出實(shí)驗(yàn)結(jié)果和相應(yīng)的分析；與現(xiàn)有方法的比較在第4節(jié)中給出；第5節(jié)是結(jié)論和未來(lái)工作。

2 基于層的依存分析方法

2.1 算法描述

Wu等[8]設(shè)計(jì)了一種相鄰依存關(guān)系分析器(Neighbor parser)來(lái)識(shí)別句子中相鄰兩個(gè)詞之間的依存關(guān)系。我們依照類似的方式將詞之間的依存關(guān)系表示成序列形式，如圖1所示。

圖1中，第一列和第二列分別是句子的詞和POS(part of speech)標(biāo)注，第三列表示該位置的詞是否依存于它相鄰的詞：如果依存于它左邊相鄰的詞，則用“LH”(left-headed，即“父節(jié)點(diǎn)在左邊”)表示；如果依存于右邊的詞，則是“RH”(right-headed)；否則，標(biāo)記為“O”。下劃線“_”后面的字串是依存關(guān)系成立時(shí)相應(yīng)的依存關(guān)系類型。

圖1 相鄰依存關(guān)系分析器

Wu等使用可以得到全局最優(yōu)解的條件隨機(jī)場(chǎng)(conditional random fields, CRFs)模型來(lái)標(biāo)注相鄰詞間依存關(guān)系，以避免采用序列分類器進(jìn)行標(biāo)注[9]所帶來(lái)的決策的貪婪性。另外，考慮到直接輸送相鄰關(guān)系分析結(jié)果中的父節(jié)點(diǎn)到后續(xù)過(guò)程可能造成錯(cuò)誤傳遞，Wu在他們的模型中僅把該結(jié)果看作特征加入后續(xù)的分析器。實(shí)際上，這種做法沒(méi)有充分發(fā)揮相鄰關(guān)系分析對(duì)句法結(jié)構(gòu)預(yù)測(cè)的能力。在我們的方法中，所有依存關(guān)系都由這種相鄰關(guān)系分析來(lái)建立。

首先，從構(gòu)建樹結(jié)構(gòu)的角度出發(fā)，我們簡(jiǎn)單地為詞序列中每一個(gè)與其父節(jié)點(diǎn)相鄰并且已是完整子樹的節(jié)點(diǎn)標(biāo)注依存關(guān)系，如圖2所示。

圖2 相鄰依存關(guān)系標(biāo)注方式Ⅰ

這些詞(如圖2例中的“部”、“國(guó)際”和“知名”)被歸約到其父節(jié)點(diǎn)上，而未建立依存關(guān)系的詞則進(jìn)入下一層繼續(xù)分析，直到形成一棵樹。對(duì)輸入句子的依存分析被分解到自底向上排列的若干個(gè)分析層，每一層都有部分依存結(jié)構(gòu)被建立。因?yàn)楸粯?biāo)注了父節(jié)點(diǎn)的詞都在當(dāng)前層被歸約，建立的依存結(jié)構(gòu)在后續(xù)的分析中將不再改變。這也使得后續(xù)的分析可以利用已生成的依存結(jié)構(gòu)。我們同樣使用CRF標(biāo)注器來(lái)保證層依存結(jié)構(gòu)的最優(yōu)性。

序列標(biāo)注模型特別是計(jì)算因子之間具有不確定性的CRF模型，不能很好地捕捉序列中的長(zhǎng)距離依存關(guān)系。使用高階模型可以起到一定的緩和作用，但又帶來(lái)極大的計(jì)算代價(jià)。因此，我們認(rèn)為只有在前一步的依存層分析中就已找到自己所有孩子的詞是可歸約的，在當(dāng)前層依存關(guān)系分析后其子樹才完整的節(jié)點(diǎn)將不予歸約。這在相鄰依存分析中表現(xiàn)為：連續(xù)同方向的依存關(guān)系中，只歸約最低層的孩子節(jié)點(diǎn)。采取這種策略可以使得由于依存距離較長(zhǎng)而標(biāo)注錯(cuò)誤的詞在后續(xù)的分析中有修正的機(jī)會(huì)。如圖3(a)所示，名詞“影星”和其父親“由”相隔較遠(yuǎn)，在相鄰依存關(guān)系分析中，它有可能錯(cuò)誤依存到它右邊的動(dòng)詞“主演”上。如果我們訓(xùn)練標(biāo)注器歸約所有找到父親并且是完整子樹的節(jié)點(diǎn)，那么詞“國(guó)際”、“知名”和“影星”都將被歸約掉，“影星”失去了與“由”發(fā)生關(guān)系的機(jī)會(huì)；如果標(biāo)注器每次只歸約該層分析之前就已是完整子樹的節(jié)點(diǎn)，則只有詞“國(guó)際”的依存關(guān)系被確立(“知名”和“影星”都是在本層分析中才找到其所有孩子的)，“影星”便有機(jī)會(huì)與“由”毗鄰并得到正確的依存結(jié)果，如圖3(b)。

圖3 相鄰依存關(guān)系分析中的長(zhǎng)距離關(guān)系依存錯(cuò)誤

因?yàn)橐来骊P(guān)系只發(fā)生在相鄰詞之間，連續(xù)同方向依存關(guān)系發(fā)生時(shí)只建立最低層關(guān)系，所以每個(gè)層內(nèi)的依存深度不大于1。圖4是以此設(shè)計(jì)的新的依存標(biāo)注方式。

圖4 相鄰依存關(guān)系標(biāo)注方式Ⅱ

比較圖4和圖1，可以看出圖4中的標(biāo)記“O”存在一定的歧義。它可以表示當(dāng)前詞與相鄰的詞沒(méi)有依存關(guān)系，也可以表示當(dāng)前詞與相鄰的詞有依存關(guān)系但是暫時(shí)無(wú)法被歸約而只能標(biāo)記為“O”。原因可能是未找齊它的所有子節(jié)點(diǎn)(如詞“主演”和“的”)或受連續(xù)同方向依存關(guān)系只歸約最低層策略的約束(如詞“知名”)。為消除這種歧義，我們回歸到圖1的形式，只要相鄰的詞之間存在依存關(guān)系，就進(jìn)行標(biāo)注。樹結(jié)構(gòu)的形成，則依靠額外的歸約決策標(biāo)注器來(lái)標(biāo)記可以被歸約的詞。如圖5(a)所示，最后一列的“r”表示當(dāng)前詞可以被歸約，其依存結(jié)構(gòu)在該層被建立。

圖5 相鄰依存關(guān)系標(biāo)注方式Ⅲ

為了保證解的全局最優(yōu)性，歸約決策標(biāo)注器也使用CRF模型。實(shí)際上，這種依次標(biāo)注并不是真正的全局最優(yōu)。因此我們把依存關(guān)系和歸約決策整合成一組標(biāo)記，用“_”連接，如圖5(b)所示，使用一個(gè)標(biāo)注器來(lái)建立當(dāng)前序列的依存結(jié)構(gòu)。這樣做的另一個(gè)原因，是避免所做的歸約決策過(guò)于依賴依存關(guān)系標(biāo)注結(jié)果(歸約決策要以依存關(guān)系為特征才能達(dá)到較好的效果)。

從另一個(gè)角度看，上述標(biāo)注方式更符合對(duì)“相鄰”依存關(guān)系分析的直觀理解，而且將歸約決策獨(dú)立出來(lái)，也使加入的歸約約束表達(dá)地更加清晰。整個(gè)句法分析過(guò)程可以用一個(gè)流程圖來(lái)表示，如圖6。

圖6 分析算法流程圖

輸入句子經(jīng)相鄰關(guān)系和歸約決策標(biāo)注后，部分詞被歸約為其相鄰詞的孩子，余下的詞重新組合進(jìn)入下一步分析，直到只剩下一個(gè)詞或沒(méi)有被標(biāo)記為可歸約的詞。

根據(jù)此流程，圖5例句的部分后續(xù)分析過(guò)程簡(jiǎn)單表示如圖7所示。

圖7 圖5例句的后續(xù)分析過(guò)程

加上圖5中刻畫的第一層分析，輸入例句共需要7步即7個(gè)依存層得到最后的分析結(jié)果。圖7中第二列和第三列給出的是前一層分析歸約掉的孩子節(jié)點(diǎn)，因?yàn)橐来骊P(guān)系只發(fā)生在相鄰詞之間，它們分別是到目前為止當(dāng)前詞最左邊和最右邊的孩子節(jié)點(diǎn)。本文的實(shí)驗(yàn)只使用這一部分孩子節(jié)點(diǎn)作特征，這與一些使用基于轉(zhuǎn)換方法的相關(guān)工作[4,10]的做法相同。

2.2 終止策略——n-best標(biāo)注結(jié)果的使用

上述算法在無(wú)可歸約節(jié)點(diǎn)(沒(méi)有節(jié)點(diǎn)標(biāo)記為“r”)時(shí)便退出分析過(guò)程，但是由于訓(xùn)練語(yǔ)料包含每一個(gè)分析層，標(biāo)記為“O”或“_o”的實(shí)例遠(yuǎn)多于標(biāo)記為“_r”的實(shí)例，算法更傾向于將節(jié)點(diǎn)標(biāo)記為“不具有依存關(guān)系”或“不歸約”。我們使用標(biāo)注器的多輸出(n-best)結(jié)果來(lái)處理這個(gè)問(wèn)題。

以圖5(b)所示聯(lián)合標(biāo)注為例，我們規(guī)定：如果當(dāng)前序列長(zhǎng)度大于1但是沒(méi)有詞被標(biāo)記為可歸約，分析過(guò)程仍繼續(xù)，我們選取次優(yōu)標(biāo)注結(jié)果；如果該次優(yōu)結(jié)果顯示仍然沒(méi)有詞可歸約，則退回到原最優(yōu)標(biāo)注序列，依據(jù)最優(yōu)序列是否有詞被標(biāo)記為具有依存關(guān)系來(lái)決定是否強(qiáng)制歸約。目前，我們主要使用CRFs提供的2-best輸出，實(shí)驗(yàn)結(jié)果顯示可以達(dá)到預(yù)期的效果。

2.3 特征集合

作為典型的序列標(biāo)注問(wèn)題，分析器使用與文獻(xiàn)[6]中淺層句法分析類似的特征， 列于表1。包括詞特征、子節(jié)點(diǎn)特征和關(guān)系特征。中括號(hào)內(nèi)的數(shù)字標(biāo)志該特征所取自的詞與焦點(diǎn)詞的相對(duì)位置，“·”表示兩個(gè)原子特征的組合；w和p分別是詞形(word)和POS標(biāo)注。lc和rc分別表示在當(dāng)前分析狀態(tài)節(jié)點(diǎn)詞最左邊和最右邊的孩子節(jié)點(diǎn)，其依存關(guān)系類型用typ表示。rel表示該層依存關(guān)系標(biāo)注的結(jié)果，只在依次標(biāo)注模型中使用。為保證算法的高效性，這里只使用一階CRFs。

表1 標(biāo)注器特征集合

Cheng等[9]認(rèn)為在自底向上的確定性句法分析系統(tǒng)中，低層所使用的分析策略和特征要與高層區(qū)分開，因?yàn)閷?duì)高層來(lái)說(shuō)，分析的對(duì)象更像是一個(gè)“短語(yǔ)”而不是詞。在我們的系統(tǒng)中，也將第一層和其他層區(qū)別對(duì)待，采用分離模型：訓(xùn)練語(yǔ)料中，句子第一層的實(shí)例被單獨(dú)取出來(lái)訓(xùn)練針對(duì)第一層的分析模型，所有層的實(shí)例用來(lái)訓(xùn)練針對(duì)其他層的分析模型。針對(duì)第一層分析的標(biāo)注器不訓(xùn)練子節(jié)點(diǎn)特征。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)分別在英語(yǔ)和漢語(yǔ)標(biāo)準(zhǔn)樹庫(kù)上進(jìn)行。

英語(yǔ)數(shù)據(jù)取自賓州樹庫(kù)(Penn Treebank)[11]的《華爾街日?qǐng)?bào)》語(yǔ)料，采用標(biāo)準(zhǔn)劃分：02～21節(jié)做訓(xùn)練，22節(jié)作為開發(fā)集，23節(jié)測(cè)試(共56 684詞)。使用和文獻(xiàn)[12]相同的中心詞提取規(guī)則和依存關(guān)系類型集合，均由Penn2Malt[13]工具提供，得到的依存結(jié)構(gòu)共含有12種依存關(guān)系類型。開發(fā)集和測(cè)試集中的POS標(biāo)注由軟件MXPOST[14]自動(dòng)獲得，并在測(cè)試集上達(dá)到97.05%的標(biāo)注正確率。

漢語(yǔ)數(shù)據(jù)取自賓州中文樹庫(kù)5.0(Penn Chinese Treebank 5.0)[15]，樹庫(kù)的劃分參照文獻(xiàn)[16]，以平衡各種語(yǔ)料來(lái)源。劃分后的訓(xùn)練集共16 079句，開發(fā)集803句，測(cè)試集1 905句(共50 319詞)。樹庫(kù)的轉(zhuǎn)化同樣參照文獻(xiàn)[12]，使用Penn2Malt提供的針對(duì)漢語(yǔ)的中心詞提取規(guī)則和依存關(guān)系類型集合。開發(fā)集和測(cè)試集采用樹庫(kù)中的標(biāo)準(zhǔn)分詞和POS標(biāo)注。

以下是實(shí)驗(yàn)中用于比較的五個(gè)基線系統(tǒng)：

1. MaltParser[17]：文獻(xiàn)[18]中描述的基于轉(zhuǎn)換的依存分析方法的典型實(shí)現(xiàn)，它采用“移進(jìn)-歸約”的一次分析方法，具有線性的分析時(shí)間O(n)，這里使用的是MaltParser的1.1版本；

2. Yamada03：我們實(shí)現(xiàn)的另一種基于轉(zhuǎn)換的依存分析方法[3]，同樣采用“移進(jìn)-歸約”算法，對(duì)輸入句子自底向上多次分析得到句法樹，時(shí)間復(fù)雜度為O(n2)；

3. MSTParser1：MSTParser[19]是基于圖的方法[1,2]的典型實(shí)現(xiàn)，這里使用的是0.2版本，MSTParser1指的是其一階模型；

4. MSTParser2：MSTParser的二階模型；

5. Duan07：Duan等[16]提出的概率動(dòng)作模型。該方法在Yamada和Matsumoto[3]提出的基于轉(zhuǎn)換的模型之上全局搜索最優(yōu)分析動(dòng)作序列，使用束搜索算法和支持向量機(jī)(SVMs)學(xué)習(xí)算法。時(shí)間復(fù)雜度為O(BKn2)，B是束搜索的寬度，K是其動(dòng)作短語(yǔ)模型轉(zhuǎn)移性動(dòng)作的步數(shù)。

對(duì)于本文提出的基于層的分析方法(LDParser)，這里共比較以下五種：

1. LDP2：圖5(a)所示依次標(biāo)注法；

2. LDP：圖5(b)所示聯(lián)合標(biāo)注法；

3. LDPdiv：圖5(b)所示聯(lián)合標(biāo)注法，第一層和其他層采用分離模型；

4. LDPnrAll：圖2所示不歸約則不標(biāo)注依存關(guān)系的簡(jiǎn)單標(biāo)注方法，在當(dāng)前層成為完整子樹的節(jié)點(diǎn)也被歸約。與LDPdiv一樣采用分離模型；

5. LDPnr：圖4所示不歸約則不標(biāo)注依存關(guān)系，但只歸約當(dāng)前層之前就已是完整子樹的節(jié)點(diǎn)。與LDPdiv一樣采用分離模型。

實(shí)驗(yàn)結(jié)果的評(píng)價(jià)指標(biāo)我們采用常用的無(wú)標(biāo)記依存正確率(UAS)、帶標(biāo)記依存正確率(LAS)、根正確率(RA)和完全匹配率(CM)。其中根正確率指的是所有根節(jié)點(diǎn)識(shí)別正確的句子所占比例。除完全匹配率以外，所有指標(biāo)均不將標(biāo)點(diǎn)符號(hào)統(tǒng)計(jì)在內(nèi)。此外，我們還給出了各種方法的時(shí)間復(fù)雜度(Comp.)和其實(shí)現(xiàn)工具的分析時(shí)間(Testing time)(CPU時(shí)間)。所有實(shí)驗(yàn)在同一計(jì)算機(jī)環(huán)境(64位Xeon處理器，2.5GHz，64G內(nèi)存)下進(jìn)行。

3.2 主要結(jié)果

在英語(yǔ)數(shù)據(jù)集上我們比較了除Duan07以外的所有系統(tǒng)。對(duì)于MaltParser，arc-eager算法[18]被選為句法分析算法，特征集合與在Hall等[12]實(shí)驗(yàn)中取得最好結(jié)果的Ψ5組合一致。Hall等還指出在該特征集上SVM算法在句法分析精度和速度上都要比基于記憶的學(xué)習(xí)算法(MBL)優(yōu)越，對(duì)于漢語(yǔ)也是如此。所以本文實(shí)驗(yàn)均使用SVMs作為學(xué)習(xí)算法。另外，我們還將分類器分割策略用于MaltParser以求獲得更快的分析速度，按照下一個(gè)輸入詞的POS標(biāo)注將原SVM分類器分割成多個(gè)小分類器，每個(gè)分類器訓(xùn)練實(shí)例數(shù)量的下限是1 000。對(duì)于Yamada03，特征選取的窗口寬度為6，特征集同時(shí)還加入了孩子節(jié)點(diǎn)的依存關(guān)系類型，其SVM分類器是按左焦點(diǎn)詞的POS標(biāo)注劃分后分別訓(xùn)練的。對(duì)于MSTParser，我們重復(fù)了文獻(xiàn)[1]和[2]的實(shí)驗(yàn)。

考慮到訓(xùn)練代價(jià)，實(shí)驗(yàn)中五種基于層的句法分析模型除了依次標(biāo)注模型以外都只使用出現(xiàn)了兩次以上的特征，而且表1中的聯(lián)合子節(jié)點(diǎn)特征和詞形與POS標(biāo)注的聯(lián)合特征也被忽略了。

表2和表3是五個(gè)基線系統(tǒng)以及各種基于層的分析模型在英語(yǔ)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。時(shí)間復(fù)雜度項(xiàng)中的R表示基于層的模型中所有在訓(xùn)練實(shí)例中出現(xiàn)的依存關(guān)系標(biāo)記的個(gè)數(shù)?；赩iterbi算法的標(biāo)準(zhǔn)CRF序列模型復(fù)雜度為O(R2n)。在基于層的方法中，對(duì)一個(gè)輸入句子的分析最多需要n層，因此算法復(fù)雜度為O(R2n2)。

表2 各模型英語(yǔ)分析結(jié)果

表3 各基于層的模型英語(yǔ)分析結(jié)果

在相比較的模型中，基于層的方法和基于轉(zhuǎn)換的方法在依存正確率和完全匹配率上相似，但根識(shí)別正確率要高于基于轉(zhuǎn)換的方法。需要指出的是，MaltParser提供了多種可選參數(shù)項(xiàng)，我們實(shí)驗(yàn)得到的結(jié)果并不代表它的最好性能。文獻(xiàn)[12]的英語(yǔ)實(shí)驗(yàn)使用的數(shù)據(jù)集和我們的相同，其公布的該方法的最好結(jié)果是89.4%(UAS)。雖然得到該結(jié)果的自動(dòng)POS標(biāo)注正確率是96.5%，要低于我們的97.05%，但其分析器的參數(shù)經(jīng)過(guò)了優(yōu)化。

依賴于全句范圍內(nèi)的搜索，MSTParser實(shí)現(xiàn)的基于圖的方法在英語(yǔ)分析中得到最好的結(jié)果。但是考慮到分析效率，基于層的方法有很大優(yōu)勢(shì)。將搜索范圍縮小到一個(gè)依存層，復(fù)雜度比基于圖的方法低(在投射性條件下)，相應(yīng)的有更快的分析速度：在五種基于層的分析模型中具有最高精度的LDPdiv每秒鐘可以分析700個(gè)詞以上；不歸約則不標(biāo)注依存關(guān)系的LDPnr甚至可以達(dá)到每秒2 500個(gè)詞?；谵D(zhuǎn)換的方法雖然可以有線性的復(fù)雜度，但是被認(rèn)為是分析效果最好的SVMs并不是一種非常高效的分類算法[20-21]，特別是當(dāng)類別個(gè)數(shù)非常多的時(shí)候。采用分類器分割或其他加速方法[22]，或換用另外的分類器可以改善這一問(wèn)題。但是，即使考慮到這些因素，基于層的方法其分析速度仍十分可觀。況且很多提升分類器速度的策略往往是以犧牲分析精度和消耗更多內(nèi)存為代價(jià)的。比較表2中兩個(gè)MaltParser系統(tǒng)的分析結(jié)果也可以看出這一點(diǎn)。

分析表3中的數(shù)據(jù)，可以看出依次標(biāo)注法(LDP2)因?yàn)椴痪哂薪Y(jié)構(gòu)搜索的全局最優(yōu)性，分析精度較差；采用分離模型能很好地適應(yīng)不同層的特點(diǎn)，從而得到較好的性能；LDPnrAll歸約包括在當(dāng)前層形成完整子樹的節(jié)點(diǎn)，相當(dāng)于層內(nèi)可能有深度大于1的依存結(jié)構(gòu)，高估了線性序列標(biāo)注的分析能力，因此性能最差；而LDPdiv與LDPnr相比，因?yàn)橄藰?biāo)記“O”的歧義，分析精度有一定提高。這五種模型分析效率的差異分屬三種情況：聯(lián)合標(biāo)注模型和依次標(biāo)注模型的差別是復(fù)雜度的一部分因子由乘積變?yōu)榧雍?，?fù)雜度降低；使用額外歸約決策標(biāo)注器的LDP和LDPdiv與只使用關(guān)系標(biāo)注器的LDPnr和LDPnrAll，差別在于標(biāo)注集縮小，效率也就提高了；另外，LDPnrAll每次歸約的詞要比LDPnr多，一個(gè)句子需要的分析層數(shù)相應(yīng)減少，所以LDPnrAll更快。實(shí)際上，建立在序列標(biāo)注模型之上的基于層的依存分析方法有很強(qiáng)的適應(yīng)性，當(dāng)語(yǔ)料標(biāo)注集較大(通常是樹庫(kù)依存關(guān)系類型較多)或?qū)π室筝^高時(shí)，可以通過(guò)標(biāo)注拆分或縮減標(biāo)注集來(lái)滿足要求；另外，因?yàn)樽匀徽Z(yǔ)言詞語(yǔ)的聚集性(即大部分是短距離依存)，分析進(jìn)入高層，序列的平均長(zhǎng)度會(huì)急劇減小，即使輸入句子本身很長(zhǎng)，也不會(huì)出現(xiàn)難以接受的時(shí)間消耗。

在漢語(yǔ)實(shí)驗(yàn)中，我們又加入了與Duan07的比較。這里MaltParser選擇使用arc-standard算法[18]，因?yàn)橥ㄟ^(guò)對(duì)開發(fā)集的測(cè)試我們發(fā)現(xiàn)，對(duì)漢語(yǔ)的分析arc-standard算法要優(yōu)于arc-eager算法，CoNLL2007共享任務(wù)中的MaltParser[23]處理漢語(yǔ)時(shí)同樣選擇了arc-standard算法。特征集依然是參考Hall等[12]的實(shí)驗(yàn)，選用Φ5組合。包括Yamada03在內(nèi)，分類器設(shè)置和英語(yǔ)實(shí)驗(yàn)一致。對(duì)于MSTParser，漢語(yǔ)的分析模型訓(xùn)練設(shè)置為只使用1-best句法樹。

LDParser模型只考慮出現(xiàn)了一次以上的特征。實(shí)驗(yàn)結(jié)果列于表4。

表4 各模型漢語(yǔ)分析結(jié)果

在漢語(yǔ)實(shí)驗(yàn)中，基于層的方法與一階MSTParser準(zhǔn)確率相當(dāng)，比基于轉(zhuǎn)換的方法稍差一些。原因是基于轉(zhuǎn)換的方法有較強(qiáng)的特征表達(dá)能力，更適合形態(tài)變化少的漢語(yǔ)的分析。這也是為什么基于層的方法在漢語(yǔ)分析中能與一階MSTParser相比：基于層的方法也可以使用已生成的句法結(jié)構(gòu)，雖不及基于轉(zhuǎn)換的方法有效，但比MSTParser在特征表達(dá)上有一定優(yōu)勢(shì)。Duan07在Yamada03之上全局搜索最優(yōu)分析動(dòng)作序列，得到了比Yamada03等更好的分析結(jié)果*這里公布的Duan07分析結(jié)果與文獻(xiàn)[16]不一致，是因?yàn)槲覀兪褂昧瞬煌囊来鏄滢D(zhuǎn)換規(guī)范。。

和在英語(yǔ)數(shù)據(jù)集上的實(shí)驗(yàn)一樣，基于層的方法使用了最少的時(shí)間。LDPdiv模型在當(dāng)前系統(tǒng)環(huán)境下每秒鐘分析多于600個(gè)詞，而且與其他方法的差距比英語(yǔ)實(shí)驗(yàn)中要大。比如，在漢語(yǔ)數(shù)據(jù)集上LDP-div的分析速度是MaltParser的27倍和MST-Parser2 的約12倍，而在英語(yǔ)數(shù)據(jù)集上這兩個(gè)值分別是11和不到7。原因可能是漢語(yǔ)測(cè)試集的平均句長(zhǎng)(每句26.4個(gè)詞)大于英語(yǔ)的平均句長(zhǎng)(每句23.5個(gè)詞)。分層結(jié)構(gòu)和相鄰依存關(guān)系分析模式使基于層的句法分析能更高效地處理長(zhǎng)句。在原本就低效的基于SVM分類的動(dòng)作序列上加入全局搜索，Duan07是所有參與比較的分析器中最慢的一個(gè)。

總之，基于層的依存分析方法在分析精度上與現(xiàn)有主流方法有可比性，其準(zhǔn)確率處于基于圖的方法和基于轉(zhuǎn)換的方法之間，但在分析速度上有極大優(yōu)勢(shì)。特別是用于處理大規(guī)模語(yǔ)料時(shí)，這一優(yōu)勢(shì)將非常突出。

3.3 其他結(jié)果和分析

為進(jìn)一步分析LDParser的特性，我們?cè)谟⒄Z(yǔ)數(shù)據(jù)集上分別測(cè)試了各方法對(duì)不同長(zhǎng)度依存關(guān)系的分析能力， 列于表5。項(xiàng)“=1”表示相鄰依存關(guān)系，“≤3”和“>3”分別指依存距離不大于和大于3個(gè)詞的依存關(guān)系。這里以“3”作為分界點(diǎn)是考慮到實(shí)驗(yàn)使用的英語(yǔ)樹庫(kù)平均依存距離是3.28。

表5 各長(zhǎng)度依存關(guān)系精度比較(UAS/%)(英語(yǔ))

LDParser的相鄰關(guān)系分析精度與其他兩個(gè)模型不相上下，說(shuō)明全局搜索的序列標(biāo)注模型可以像層次分析模型一樣，很好地判斷相鄰詞間的依存關(guān)系，甚至有比基于轉(zhuǎn)換的方法更高的精度。對(duì)于長(zhǎng)距離的依存關(guān)系，LDParser性能也比MaltParser稍好，這說(shuō)明基于層的方法能一定程度上緩解基于轉(zhuǎn)換的方法中確定性過(guò)程的貪婪性。

通過(guò)將計(jì)算因子擴(kuò)展到兩個(gè)相鄰的依存邊以保存更多的上下文信息，二階MSTParser無(wú)論在短依存還是長(zhǎng)依存關(guān)系上都有較好表現(xiàn)。因?yàn)槭褂昧艘焉山Y(jié)構(gòu)信息，LDParser對(duì)短距離依存關(guān)系的判斷能力與MSTParser相近，但隨著依存關(guān)系距離的增大，LDParser的精度下降嚴(yán)重。原因是基于層的方法仍然是一種確定性的分析方法，無(wú)法擺脫錯(cuò)誤傳遞對(duì)長(zhǎng)距離依存關(guān)系分析的影響。另一個(gè)原因是目前的LDParser版本對(duì)所有高層實(shí)例使用同一個(gè)模型，沒(méi)有各自建模，削弱了高層分析模型的排歧能力。

我們還考查了各模型對(duì)長(zhǎng)句的分析能力。英語(yǔ)測(cè)試集中長(zhǎng)度大于40個(gè)詞的共171個(gè)句子(8 019詞)作為測(cè)試數(shù)據(jù)，結(jié)果列于表6。測(cè)試時(shí)間項(xiàng)中同時(shí)列出了分析器分析長(zhǎng)句時(shí)速度下降的百分比。

表6 長(zhǎng)句分析結(jié)果比較(英語(yǔ))

LDParser的精度與MaltParser相當(dāng)。因?yàn)槭褂萌渌阉?，MSTParser雖然是準(zhǔn)確率最高的一個(gè)，但也是句子變長(zhǎng)時(shí)效率下降最嚴(yán)重的一個(gè)(減慢了約56%)。平均句長(zhǎng)由原來(lái)的23.5增加到46.9，LDParser的分析速度只降低了15%，進(jìn)一步說(shuō)明了基于層的方法雖然引入了最優(yōu)結(jié)構(gòu)搜索，對(duì)長(zhǎng)句仍有較好的魯棒性，可以高效地進(jìn)行長(zhǎng)句分析。

4 與相關(guān)工作的比較

作為一種自底向上的層次分析方法，本文提出的基于層的句法分析與基于轉(zhuǎn)換的Yamada和Matsumoto[3]的方法在依存樹歸約形式上有些相似。但是他們的模型每一次由左至右分析詞序列，針對(duì)每一個(gè)分析狀態(tài)做決策，算法是完全確定性的和貪婪的。為了克服此類方法決策的貪婪性，Duan等[16]保留部分或所有可能的分析動(dòng)作序列，搜索概率最大者來(lái)分析輸入句子。同樣，基于層的方法也通過(guò)加入全局搜索來(lái)尋找依存關(guān)系的最優(yōu)組合，但是搜索空間只限制在一個(gè)依存層內(nèi)，而Duan的方法則和基于圖的模型一樣為整個(gè)圖空間打分。另外，他們繼承了基于轉(zhuǎn)換的方法所采用的層次結(jié)構(gòu)分析機(jī)制(即使用分析動(dòng)作建立依存關(guān)系)，基于層的方法則引入了序列標(biāo)注技術(shù)。

目前有很多工作致力于兩種主流方法的融合算法研究。Sagae和Lavie[24]建立圖模型重新分析一個(gè)“組合”起來(lái)的依存圖，圖中邊的分值(即依存關(guān)系打分)來(lái)自另外三個(gè)基于轉(zhuǎn)換的分析器。Hall等[10]采用相似的方法融合六個(gè)基于轉(zhuǎn)換的分析模型。這類方法可以看作是對(duì)基于圖和基于轉(zhuǎn)換方法的結(jié)構(gòu)投票。Nivre和McDonald[25]提出了一種更有效的融合算法，將其中一種模型的輸出看作是另一模型的特征。但是，所有這些融合系統(tǒng)都只是使用了子系統(tǒng)的輸出結(jié)果，并沒(méi)有改變它們的結(jié)構(gòu)或算法。而基于層的分析方法對(duì)二者的繼承，不僅引入了全新的結(jié)構(gòu)而且采用了不同的分析算法。

Cheng等[9]和Wu等[8]使用相鄰依存關(guān)系分析器來(lái)提高確定性句法分析系統(tǒng)的性能。在Cheng的方法中，相鄰關(guān)系由SVM序列分類器標(biāo)注，父節(jié)點(diǎn)直接輸送到后續(xù)的分析。Wu使用CRFs進(jìn)行關(guān)系分析，并用分析結(jié)果擴(kuò)充特征集。這些方法中的相鄰關(guān)系分析實(shí)際上只是充當(dāng)完全句法分析的一個(gè)前處理單元，而我們的方法自始至終都是使用這種分析形式，并且證明它完全可以勝任層次結(jié)構(gòu)預(yù)測(cè)任務(wù)。

5 結(jié)論

我們提出了一種全新的分層式依存句法分析方法。它以依存層為分析單位，在層內(nèi)，像一個(gè)基于圖的模型搜索最優(yōu)子結(jié)構(gòu)；在層之間，又像一個(gè)基于轉(zhuǎn)換的模型確定性地傳遞已建立的依存結(jié)構(gòu)。自底向上的分層結(jié)構(gòu)、相鄰關(guān)系分析模式和一階CRF序列標(biāo)注技術(shù)的應(yīng)用使分析器在保證與主流方法可比的分析精度前提下，具有非常高的分析效率。

對(duì)分析器進(jìn)行改進(jìn)的首要工作是提高其分析精度。像Duan[16]的方法那樣保留多個(gè)依存標(biāo)注結(jié)果并加入層間搜索，是目前來(lái)看最有潛力的途徑。此外，優(yōu)化高層分析模型可能是另一種有效的手段。

[1] R. McDonald, K. Crammer and F. Pereira. Online large-margin training of dependency parsers[C]//Proc. of ACL. Ann Arbor, USA：2005, 91-98.

[2] R. McDonald and F. Pereira. Online learning of approximate dependency parsing algorithms[C]//Proc. of EACL. Trento, Italy：2006, 81-88.

[3] H. Yamada and Y. Matsumoto. Statistical dependency analysis with support vector machines[C]//Proc. of IWPT. Nancy, France：2003, 195-206.

[4] J. Nivre and M. Scholz. Deterministic dependency parsing of English text[C]//Proc. of COLING. Switzerland：2004, 64-70.

[5] R. McDonald and J. Nivre. Characterizing the errors of data-driven dependency parsing models[C]//Proc. of EMNLP-CoNLL. Prague, Czech：2007, 122-131.

[6] F. Sha and F. Pereira. Shallow parsing with conditional random fields[C]//Proc. of NAACL. Edmonton, Canada：2003, 213-220.

[7] 李珩, 朱靖波, 姚天順. 基于SVM的中文組塊分析[J]. 中文信息學(xué)報(bào), 2004, 18(2)：1-7.

[8] Y. Wu, J. Yang and Y. Lee. Multilingual deterministic dependency parsing framework using modified finite Newton method support vector machines[C]//Proc. of EMNLP-CoNLL. Prague, Czech：2007, 1175-1181.

[9] Y. Cheng, M. Asahara and Y Matsumoto. Multi-lingual dependency parsing at NAIST[C]//Proc. of CoNLL. New York City, USA：2006, 191-195.

[10] J. Hall, J. Nilsson, J. Nivre, et. al. Single Malt or blended? A study in multilingual parser optimization[C]//Proc. of EMNLP-CoNLL. Prague, Czech：2007, 933-939.

[11] M. P. Marcus, B. Santorini and M. A. Marcinkiewicz. Building a large annotated corpus of English：the Penn Treebank[J]. Computational Linguistics, 1993, 19(2)：313-330.

[12] J. Hall, J. Nivre and J. Nilsson. Discriminative classifiers for deterministic dependency parsing[C]//

Proc. of COLING-ACL. Sydney, Australia：2006, 316-323.

[13] http://w3.msi.vxu.se/～nivre/research/Penn2Malt.html[CP/OL].

[14] A. Ratnaparkhi. MXPOST[CP/OL]. http://www.inf.ed.ac.uk/resources/nlp/local_doc/MXPOST.html.

[15] N. Xue, F. Xia, F. Chiou et, al. The Penn Chinese Treebank：phrase structure annotation of a large corpus[J]. Natural Language Engineering, 2005,11(2)：207-238.

[16] X. Duan, J. Zhao and B. Xu. Probabilistic models for action-based Chinese dependency parsing[C]//Proc.of ECML-PKDD. Warsaw, Poland：2007, 559-566.

[17] J. Nivre, J. Hall and J. Nilsson. MaltParser：a data-driven parser-generator for dependency parsing[C]//Proc. of LREC. Genoa, Italy：2006, 2216-2219.

[18] J. Nivre. Incrementality in deterministic dependency parsing[C]//Proc. of ACL. Barcelona, Spain：2004, 50-57.

[19] R. McDonald. MSTParser[CP/OL]. http://www.seas.upenn.edu/～strctlrn/MSTParser/MSTParser.html.

[20] Y. Cheng, M. Asahara and Y. Matsumoto. Machine learning-based dependency analyzer for Chinese[C]//Proc. of ICCC. Mauritius：2005, 66-73.

[21] M. Wang, K. Sagae and T. Mitamura. A fast, accurate deterministic parser for Chinese[C]//Proc. of COLING-ACL. Sydney, Australia：2006, 425-432.

[22] Y. Goldberg and M. Elhadad. SplitSVM：fast, space-efficient, non-heuristic, polynomial kernel computation for NLP applications[C]//Proc. of ACL. Columbus USA：2008, 237-240.

[23] J. Hall, J. Nilsson and J. Nivre. MaltParser in the CoNLL shared task 2007-Multilingual track[EB/OL]. http://maltparser.org/conll/conll07/.

[24] K. Sagae and A. Lavie. Parser combination by reparsing[C]//Proc. of NAACL. New York City, USA：2006, 129-132.

[25] J. Nivre and R. McDonald. Integrating graph-based and transition-based dependency parsers[C]//Proc. of ACL. Columbus, USA：2008, 950-958.