面向移進(jìn)—?dú)w約句法分析器的單模型系統(tǒng)整合算法

馬 驥，朱慕華，肖 桐，朱靖波

(東北大學(xué) 自然語(yǔ)言處理實(shí)驗(yàn)室，遼寧 沈陽(yáng) 110004)

1 引言

系統(tǒng)整合的主要目的在于通過(guò)整合多套不同的系統(tǒng)來(lái)得到更好的整體性能。基于系統(tǒng)整合的方法在近年來(lái)已經(jīng)受到廣泛的關(guān)注，這類(lèi)方法已經(jīng)廣泛應(yīng)用于與自然語(yǔ)言處理領(lǐng)域相關(guān)的任務(wù)中，例如，文本分類(lèi)[1]、命名實(shí)體識(shí)別[2]、機(jī)器翻譯[3-4]和句法分析[5-6]等。一般而言，基于系統(tǒng)整合的方法要解決的兩個(gè)核心問(wèn)題為：如何構(gòu)建多套用于整合的子系統(tǒng)*為描述方便,本文稱(chēng)參與整合的各系統(tǒng)為子系統(tǒng)。；如何將各子系統(tǒng)的輸出進(jìn)行整合從而得到最終結(jié)果。對(duì)于第一個(gè)問(wèn)題，一種方法是用不同的模型來(lái)構(gòu)建各個(gè)子系統(tǒng)，即參與整合的子系統(tǒng)是由不同的模型通過(guò)訓(xùn)練得到的。本文稱(chēng)這種方法為基于多模型的系統(tǒng)整合。另一種方法是用同一個(gè)模型來(lái)構(gòu)建不同的子系統(tǒng)。本文稱(chēng)這種方法為基于單模型的系統(tǒng)整合。多模型系統(tǒng)整合的缺點(diǎn)在于開(kāi)發(fā)不同模型需要付出較高的時(shí)間與人力。而單模型系統(tǒng)相對(duì)來(lái)說(shuō)開(kāi)發(fā)代價(jià)較低。因此，本文主要研究面向移進(jìn)—?dú)w約句法分析器的單模型系統(tǒng)整合技術(shù)。在訓(xùn)練階段，本文使用基于AdaBoost[7]的子系統(tǒng)生成算法，該方法通過(guò)改變訓(xùn)練數(shù)據(jù)的分布來(lái)生成多個(gè)移進(jìn)—?dú)w約句法分析器。在解碼階段，本文主要考慮兩類(lèi)特征——子系統(tǒng)置信度和擴(kuò)展動(dòng)作序列置信度(第4部分將詳細(xì)介紹)——并使用這兩類(lèi)特征的線(xiàn)性組合對(duì)各子系統(tǒng)的輸出進(jìn)行整合。作者在賓夕法尼亞大學(xué)提供的英文樹(shù)庫(kù)(Penn English Treebank)上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文中的方法能夠顯著提高移進(jìn)—?dú)w約句法分析器的性能。

Henderson和Brill[8]對(duì)面向Collins Parser[9]的單模型系統(tǒng)整合方法進(jìn)行過(guò)研究，然而關(guān)于移進(jìn)—?dú)w約句法分析器，尚沒(méi)有此類(lèi)研究。移進(jìn)—?dú)w約句法分析器的特點(diǎn)是在于其速度快。因此通過(guò)系統(tǒng)整合來(lái)提高移進(jìn)—?dú)w約句法分析器的性能是一件有意義的工作。

2 移進(jìn)—?dú)w約句法分析法

移進(jìn)—?dú)w約句法分析法涉及的兩個(gè)主要數(shù)據(jù)結(jié)構(gòu)為：輸入隊(duì)列Q和分析棧S。隊(duì)列Q中的元素是輸入句子中尚未被處理的 <詞,詞性>對(duì)序列。分析棧S中保存著輸入串中已經(jīng)被處理的部分所對(duì)應(yīng)的句法樹(shù)片段。移進(jìn)—?dú)w約句法分析法自左向右地掃描待分析的句子，并在掃描過(guò)程中執(zhí)行下列動(dòng)作之一。

? 移進(jìn)：將Q的隊(duì)首元素壓入棧S，并從Q中刪除該元素。

? 一元/二元—XX—?dú)w約：生成一個(gè)新的元素，該元素的非終結(jié)符類(lèi)型為XX，彈出棧頂?shù)囊粋€(gè)/兩個(gè)元素，并將彈出的元素作為新生成的元素的子樹(shù)。最后，將新生成的元素插入到棧頂。

當(dāng)Q為空時(shí)，如果S中只有一個(gè)元素，則將S中的元素作為輸入句子的分析結(jié)果，并結(jié)束整個(gè)分析過(guò)程。如果S中包含多于一個(gè)元素，則報(bào)告對(duì)輸入句子分析失敗。

圖1中展示了移進(jìn)—?dú)w約句法分析法的分析過(guò)程。初始情況下(圖1(a))，S為空，Q中包含待分析句子的<詞,詞性>對(duì)序列。算法第一步執(zhí)行移進(jìn)動(dòng)作，將隊(duì)首元素從Q中彈出，并壓入S。移進(jìn)后，Q和S的狀態(tài)如圖1(b)所示。算法第二步執(zhí)行的動(dòng)作仍為移進(jìn)，執(zhí)行過(guò)程與第一步類(lèi)似，該動(dòng)作執(zhí)行后，Q和S的狀態(tài)如圖1(c)所示。第三步執(zhí)行的動(dòng)作為二元—ADJP—?dú)w約，該動(dòng)作首先生成一個(gè)根節(jié)點(diǎn)為ADJP的子樹(shù)，然后將S的棧頂?shù)膬蓚€(gè)元素彈出作為新元素的子樹(shù)。最后，該新生成的子樹(shù)被壓入S中。該動(dòng)作執(zhí)行后Q和S的狀態(tài)如圖1(d)所示。算法第四步執(zhí)行的動(dòng)作為移進(jìn)，執(zhí)行后的結(jié)果如圖1(e)所示。算法第5步執(zhí)行的動(dòng)作為二元—NP—?dú)w約，該動(dòng)作執(zhí)行以后，Q和S的狀態(tài)如圖1(f)所示。此時(shí)Q為空，S中僅有一個(gè)元素，分析過(guò)程結(jié)束，S中的元素就是對(duì)整個(gè)輸入句子的分析結(jié)果。

圖1 移進(jìn)—?dú)w約句法分析法的分析過(guò)程舉例

基于移進(jìn)—?dú)w約句法分析法的首個(gè)句法分析器是由Sagae和Lavie[10]實(shí)現(xiàn)的，其基本思想是從S和Q的狀態(tài)中抽取特征，然后使用一個(gè)分類(lèi)器根據(jù)這些特征來(lái)選擇要執(zhí)行的動(dòng)作。因此，整個(gè)句法分析過(guò)程可以看成是使用分類(lèi)器進(jìn)行一系列移進(jìn)—?dú)w約動(dòng)作的決策過(guò)程，而訓(xùn)練移進(jìn)—?dú)w約句法分析器主要是訓(xùn)練該分類(lèi)器。用于訓(xùn)練分類(lèi)器的訓(xùn)練數(shù)據(jù)是一組<特征向量,動(dòng)作>對(duì)，稱(chēng)為分類(lèi)樣本。例如，與圖1所對(duì)應(yīng)的那組分類(lèi)樣本為：

，，，，

其中，v(a)表示從圖1(a)所描述的S和Q的狀態(tài)中抽取的特征向量。

Sagae和Lavie在文獻(xiàn)[10] 中實(shí)現(xiàn)的移進(jìn)—?dú)w約句法分析器每一步只選擇一個(gè)動(dòng)作來(lái)執(zhí)行，因此一個(gè)輸入句子僅對(duì)應(yīng)唯一一組動(dòng)作序列，這種貪婪的策略限制了移進(jìn)—?dú)w約分析法的搜索空間，并且如果某一步選擇了錯(cuò)誤的動(dòng)作，則該錯(cuò)誤將影響對(duì)后續(xù)動(dòng)作的選擇。為了克服該缺點(diǎn)，Sagae和Lavie[11]使用了最優(yōu)優(yōu)先(best-first search)搜索算法對(duì)他們前期的工作進(jìn)行改進(jìn)。在分析過(guò)程中，分析器每次可以選擇盡可能多的動(dòng)作來(lái)對(duì)當(dāng)前的S和Q的狀態(tài)進(jìn)行擴(kuò)展，并將動(dòng)作執(zhí)行之后的結(jié)果狀態(tài)存入到一個(gè)全局優(yōu)先級(jí)隊(duì)列中。分析器使用基于最大熵模型的分類(lèi)器對(duì)每個(gè)動(dòng)作進(jìn)行評(píng)分，優(yōu)先級(jí)隊(duì)列中的每個(gè)狀態(tài)的得分是從初始狀態(tài)到該狀態(tài)所執(zhí)行的動(dòng)作序列的得分的乘積。該方法擴(kuò)大了分析器的搜索范圍，從而提高了分析器的性能。本文所研究的系統(tǒng)整合方法也是基于Sagae 和 Lavie在文獻(xiàn) [11]中提出的移進(jìn)—?dú)w約句法分析器，具體方法將在余下的章節(jié)中進(jìn)行詳細(xì)討論，其中第三部分主要介紹了子系統(tǒng)構(gòu)建算法，第四部分主要介紹子系統(tǒng)輸出整合算法，第五部分介紹實(shí)驗(yàn)，第六部分和第七部分則分別為相關(guān)工作和對(duì)本文的總結(jié)。

3 單模型系統(tǒng)整合的子系統(tǒng)構(gòu)建

本部分介紹基于AdaBoost的子系統(tǒng)生成算法，該算法的主要思想是通過(guò)更新訓(xùn)練數(shù)據(jù)的分布，來(lái)構(gòu)建各子系統(tǒng)。在對(duì)該算法的具體細(xì)節(jié)進(jìn)行描述之前，首先介紹該算法所涉及幾個(gè)主要符號(hào)的含義。

本文用Psen表示訓(xùn)練語(yǔ)料中的句子的分布，Psmp表示從訓(xùn)練語(yǔ)料中抽取的分類(lèi)樣本的分布，SR表示移進(jìn)—?dú)w約句法分析器。SR在訓(xùn)練語(yǔ)料中的第i個(gè)句子上取得的F1-score用score(i)表示。SR在整個(gè)訓(xùn)練語(yǔ)料中取得的平均性能用r來(lái)表示。

子系統(tǒng)生成算法通過(guò)迭代的更新Psen和Psmp，來(lái)構(gòu)建各個(gè)子系統(tǒng)，其(第t輪)迭代的基本過(guò)程為：算法首先根據(jù)當(dāng)前分類(lèi)樣本的分布Psmpt來(lái)訓(xùn)練一個(gè)最大熵分類(lèi)器，從而構(gòu)建一個(gè)移進(jìn)—?dú)w約句法分析器SRt，然后使用SRt對(duì)訓(xùn)練語(yǔ)料中的句子進(jìn)行句法分析。根據(jù)SRt在訓(xùn)練語(yǔ)料中的每個(gè)句子上取得的分?jǐn)?shù)scoret(i)，以及SRt在整個(gè)訓(xùn)練語(yǔ)料上取得的平均性能rt來(lái)更新訓(xùn)練語(yǔ)料中的句子的權(quán)重*本文用p(i)表示第i個(gè)樣本的權(quán)重或概率，P表示分布。樣本的分布可以通過(guò)對(duì)每個(gè)樣本的權(quán)重進(jìn)行歸一化而得到。，從而得到訓(xùn)練語(yǔ)料的句子的新分布 Psent+1。由于訓(xùn)練一個(gè)移進(jìn)—?dú)w約句法分析器的主要目的是訓(xùn)練該分析器中用于對(duì)移進(jìn)-歸約動(dòng)作進(jìn)行決策的分類(lèi)器。因此，算法根據(jù)分布Psent+1，調(diào)整從語(yǔ)料中抽取的分類(lèi)樣本權(quán)重，從而得到新的分類(lèi)樣本的分布Psmpt+1。

圖2中給出了整個(gè)子系統(tǒng)構(gòu)建算法的偽代碼，3.1和3.2將詳細(xì)討論P(yáng)sen和Psmp的更新過(guò)程。3.3還將介紹如何修改最大熵模型的學(xué)習(xí)算法，使新的學(xué)習(xí)算法(WeightedMELearn)能夠考慮每個(gè)樣本的權(quán)重。

3.1 更新Psen

本小結(jié)主要討論如何在每一輪迭代過(guò)程中調(diào)整訓(xùn)練語(yǔ)料中句子的分布Psen(圖2中步驟(4))。其具體過(guò)程如下：假設(shè)在第t輪迭代中，算法首先使用在該輪構(gòu)建的移進(jìn)—?dú)w約句法分析器SRt對(duì)訓(xùn)練語(yǔ)料中的句子進(jìn)行句法分析，SRt會(huì)在一部分句子中取得相對(duì)較低的F1-score。為了讓下一輪構(gòu)建的句法分析器能夠更好地處理這部分句子，更新句子權(quán)重的準(zhǔn)則為：SRt在某句子中的得分越低，該句子的權(quán)重增長(zhǎng)幅度就越大。

式(3)給出了更新第i個(gè)句子的權(quán)重的計(jì)算方法，其中Zt為歸一化因子。由式(3)可知，每個(gè)句子的權(quán)重的更新幅度主要由兩部分決定：損失因子errort(i)，和步長(zhǎng)因子βt。

定義SRt在第i個(gè)句子上的性能損失errort(i) 為，

(4)

其中，scoret(i)表示SRt在訓(xùn)練語(yǔ)料中第i個(gè)句子上取得的得分(F1-score)。由式(4)可知，SRt在該句子上的得分越低，損失因子就越大，因此對(duì)該句子的權(quán)重的增大幅度就越大。

步長(zhǎng)因子βt的計(jì)算主要基于以下原則：對(duì)于性能相對(duì)較高的句法分析器仍然無(wú)法正確處理的句子應(yīng)該給予更多的重視。定義SRt在整個(gè)訓(xùn)練語(yǔ)料上取得的平均性能rt為其在訓(xùn)練語(yǔ)料的每個(gè)句子上得分的期望，如式(1)，然后根據(jù)rt的值，計(jì)算βt，如式(2)所示。由式(2)可知，SRt的平均性能越高，則步長(zhǎng)因子βt越大。

3.2 根據(jù)Psen，更新Psmp

假設(shè)sj為訓(xùn)練語(yǔ)料中第j個(gè)句子并且SRt在該句子上的性能損失大于0，即errort(j)>0。對(duì)于如何更新從sj中抽取的分類(lèi)樣本的權(quán)重(注：對(duì)從訓(xùn)練語(yǔ)料的每個(gè)句子中抽取的全部分類(lèi)樣本的權(quán)重進(jìn)行歸一化即可得到分類(lèi)樣本的分布Psmp)，本文使用了兩種不同的方案。

圖2 基于AdaBoost的子系統(tǒng)構(gòu)建算法

方案一，從sj中抽取的全部分類(lèi)樣本的權(quán)重都將被更新，方案一設(shè)置這些分類(lèi)樣本的權(quán)重與sj的權(quán)重相同。

方案二,僅更新SRt對(duì)sj進(jìn)行句法分析過(guò)程中的第一個(gè)錯(cuò)誤決策所對(duì)應(yīng)的分類(lèi)樣本的權(quán)重，并設(shè)置該分類(lèi)樣本的權(quán)重與sj的權(quán)重相同。方案二與Collins和Roark在文獻(xiàn)[12]中提出的“early update”類(lèi)似，使用這種方案主要是由于移進(jìn)—?dú)w約句法分析法的每一步的決策都會(huì)對(duì)后續(xù)動(dòng)作的決策產(chǎn)生影響，第一個(gè)錯(cuò)誤決策的出現(xiàn)往往會(huì)導(dǎo)致更多后續(xù)的錯(cuò)誤決策。因此，句法分析過(guò)程中的第一個(gè)決策錯(cuò)誤所對(duì)應(yīng)的分類(lèi)樣本應(yīng)該受到更多的重視。

3.3 加權(quán)訓(xùn)練樣本的參數(shù)估計(jì)

本小節(jié)主要介紹如何修改最大熵模型的學(xué)習(xí)算法，使得修改后的學(xué)習(xí)算法能夠根據(jù)訓(xùn)練數(shù)據(jù)的權(quán)重來(lái)調(diào)整最大熵模型的參數(shù)。令{(xi,yi)}為一組獨(dú)立同分布的訓(xùn)練樣本，其中xi表示第i個(gè)樣本的特征向量，yi為該樣本的類(lèi)別。傳統(tǒng)的最大熵模型學(xué)習(xí)算法[13]通過(guò)最大化式(5)定義的樣本集的對(duì)數(shù)—似然值來(lái)確定最大熵模型的參數(shù)。

(5)

(6)

(7)

其中w(xi,yi)表示訓(xùn)練樣本(xi,yi)的權(quán)重。則整個(gè)訓(xùn)練樣本的對(duì)數(shù)—似然值為:

(8)

通過(guò)使用如L-BFGS[14]等方法優(yōu)化目標(biāo)函數(shù)(8)即可得到最大熵模型的參數(shù)的極大似然估計(jì)值。

4 子系統(tǒng)整合

本章主要介紹將各個(gè)子系統(tǒng)的輸出進(jìn)行整合的方法。假設(shè)對(duì)m個(gè)子系統(tǒng)進(jìn)行系統(tǒng)整合，則對(duì)于測(cè)試集上的任何一個(gè)句子，首先用待整合的m個(gè)子系統(tǒng)分別對(duì)該句子進(jìn)行句法分析，生成m棵句法樹(shù)，然后用一個(gè)線(xiàn)性模型對(duì)這m棵句法樹(shù)進(jìn)行評(píng)分，并將得分最高的句法樹(shù)作為最終結(jié)果。令t表示一棵句法樹(shù)，則t的最終得分為：

(9)

αi為第i個(gè)特征的權(quán)重，權(quán)重的值可以使用最小錯(cuò)誤率訓(xùn)練方法(文獻(xiàn)[15])來(lái)確定(將MERT的錯(cuò)誤率函數(shù)定義為1-F1-score)。

式(9)中的線(xiàn)性模型主要包含兩類(lèi)特征：第一類(lèi)特征稱(chēng)為子系統(tǒng)置信度(類(lèi)似于Zhang 等在文獻(xiàn)[16]中提出的模型置信度)，用pi(t)表示，即第i個(gè)子系統(tǒng)對(duì)句法樹(shù)t的置信度。該置信度的計(jì)算方法如下：假設(shè),..., 為從t中抽取的分類(lèi)樣本，其中，vj表示第j個(gè)分類(lèi)樣本的特征向量，aj表示第j個(gè)分類(lèi)樣本對(duì)應(yīng)的動(dòng)作，qi(aj|vj)表示第i個(gè)子系統(tǒng)所使用的最大熵分類(lèi)器對(duì)分類(lèi)樣本輸出的條件概率，則

(10)

第二類(lèi)特征為擴(kuò)展動(dòng)作序列置信度pas(t)(與統(tǒng)計(jì)機(jī)器翻譯中使用的語(yǔ)言模型特征類(lèi)似)，表示由a1,...,ak組成一個(gè)擴(kuò)展動(dòng)作序列的概率。其中aj是對(duì)動(dòng)作aj的擴(kuò)展，其定義如下：

(11)

POS(aj)表示被aj移進(jìn)的元素的詞性。我們通過(guò)觀察發(fā)現(xiàn)，如果將原始的動(dòng)作序列進(jìn)行擴(kuò)展以后，擴(kuò)展的動(dòng)作之間往往存在某些模式或聯(lián)系。例如，生成由兩個(gè)名詞組成的名詞短語(yǔ)的動(dòng)作序列為：

移進(jìn)_NN, 移進(jìn)_NN, 二元—NP—?dú)w約

因此，使用pas(t)的目的就是希望通過(guò)對(duì)擴(kuò)展動(dòng)作序列的分布建模。從而對(duì)給定的一組擴(kuò)展動(dòng)作，可以從概率的角度來(lái)判斷這組擴(kuò)展動(dòng)作生成一顆句法樹(shù)的可能性。本文使用N元語(yǔ)言模型對(duì)擴(kuò)展動(dòng)作序列進(jìn)行建模，在訓(xùn)練階段，使用從訓(xùn)練集中抽取的擴(kuò)展動(dòng)作序列對(duì)語(yǔ)言模型進(jìn)行參數(shù)估計(jì)。訓(xùn)練結(jié)束以后，就可以使用該模型計(jì)算t的擴(kuò)展動(dòng)作序列置信度pas(t)，例如，當(dāng)N=2時(shí)，圖1(f)中的句法樹(shù)的擴(kuò)展動(dòng)作序列置信度為：

pas(t)=l(移近_JJ)×l(移近_JJ|移近_JJ)×

l(二元-ADJP-規(guī)約|移近_JJ)×

l(移近_NNS|二元—ADJP-規(guī)約)×

(12)

其中，l為語(yǔ)言模型定義的條件分布。

5 實(shí)驗(yàn)

5.1 基準(zhǔn)系統(tǒng)及實(shí)驗(yàn)數(shù)據(jù)

本文使用賓夕法尼亞大學(xué)英文樹(shù)庫(kù)(Penn English Treebank)作為實(shí)驗(yàn)數(shù)據(jù)，并主要使用以下三個(gè)部分：02-21節(jié)作為訓(xùn)練集，主要用于訓(xùn)練移進(jìn)—?dú)w約句法分析器和N語(yǔ)言模型。22節(jié)作為開(kāi)發(fā)集，主要用于訓(xùn)練式(9)中各個(gè)特征的權(quán)重。23節(jié)作為測(cè)試集。我們刪除了訓(xùn)練集和開(kāi)發(fā)集中所有句法樹(shù)的功能節(jié)點(diǎn)及空節(jié)點(diǎn)，并使用Collins在文獻(xiàn)[17]中介紹的方法對(duì)句法樹(shù)進(jìn)行詞匯化。

本文實(shí)現(xiàn)了文獻(xiàn)[11]中提出的移進(jìn)—?dú)w約句法分析器作為本文實(shí)驗(yàn)的基準(zhǔn)系統(tǒng)，該基準(zhǔn)系統(tǒng)的再測(cè)試集上的F1得分為 87.10。但文獻(xiàn)[11]中使用的分類(lèi)器*http://www-tsujii.is.s.u-tokyo.ac.jp/～tsuruoka/maxent/的訓(xùn)練時(shí)間大于40小時(shí)，這使得迭代的訓(xùn)練多套系統(tǒng)在時(shí)間上不可行。本文因此改用Zhang[18]開(kāi)發(fā)的最大熵工具作為對(duì)移進(jìn)—?dú)w約動(dòng)作進(jìn)行決策的分類(lèi)器，基于該分類(lèi)器的移近規(guī)約句法分析器的性能為86.13，但該分類(lèi)器的訓(xùn)練時(shí)間較短，一般在三小時(shí)以?xún)?nèi)，使得迭代的訓(xùn)練多套子系統(tǒng)變得可行。對(duì)于子系統(tǒng)生成部分，我們使用3.3節(jié)中提到的方法對(duì)最大熵模型的學(xué)習(xí)部分進(jìn)行修改，使最大熵的學(xué)習(xí)部分能夠同時(shí)考慮訓(xùn)練樣本數(shù)量及權(quán)重。對(duì)于N元語(yǔ)言模型，本文使用了基于Katz[19]的平滑方法的語(yǔ)言模型工具，利用該工具對(duì)擴(kuò)展動(dòng)作序列進(jìn)行建模。

由于移進(jìn)—?dú)w約句法分析器的輸入是帶有詞性標(biāo)注的句子，因此我們使用SVMTool[20]作為本實(shí)驗(yàn)的詞性標(biāo)注器，該工具在測(cè)試集上的準(zhǔn)確率為96.81%。本文使用EVALB作為實(shí)驗(yàn)性能的評(píng)價(jià)工具。

5.2 實(shí)驗(yàn)結(jié)果及分析

第一組實(shí)驗(yàn)使用五元語(yǔ)言模型對(duì)所有子系統(tǒng)的輸出進(jìn)行整合，實(shí)驗(yàn)結(jié)果如表1所示。其中“開(kāi)發(fā)集”和“測(cè)試集”分別表示在開(kāi)發(fā)集及測(cè)試集上取得的性能，“方案1”和“方案2”分別表示使用3.2介紹的方案1和方案2來(lái)更新分類(lèi)樣本的權(quán)重所取得的性能。'T(M)'表示取得最佳性能時(shí)，參與整合的子系統(tǒng)的個(gè)數(shù)為M。從表1中可以看出，對(duì)于開(kāi)發(fā)集，基于方案1和方案2的系統(tǒng)整合后的性能分別比基準(zhǔn)系統(tǒng)的性能提高了2.09和2.16個(gè)點(diǎn)，這說(shuō)明了本文中提出的系統(tǒng)整合方法的有效性。對(duì)于測(cè)試集，基于方案1和方案2的系統(tǒng)整合后的性能則分別比基準(zhǔn)系統(tǒng)的性能提高了1.47和1.94個(gè)點(diǎn)，這表明方案2更能有效的調(diào)整分類(lèi)樣本的權(quán)重，從而獲得更好的系統(tǒng)整合性能。

表1 系統(tǒng)整合在測(cè)試集和開(kāi)發(fā)集上的性能

圖3 系統(tǒng)整合的性能隨N的變化曲線(xiàn)

第二組實(shí)驗(yàn)主要是為了研究N元語(yǔ)言模型對(duì)系統(tǒng)整合的影響。在該組實(shí)驗(yàn)中，我們選擇不同的N值，然后記錄下整合后的系統(tǒng)在測(cè)試集上取得的性能*在該組實(shí)驗(yàn)中，我們使用3.2節(jié)的方案2來(lái)更新分類(lèi)樣本的權(quán)重，并使用12個(gè)子系統(tǒng)進(jìn)行整合，該設(shè)置是第一組實(shí)驗(yàn)中取得最高性能時(shí)的設(shè)置。，實(shí)驗(yàn)結(jié)果如圖3所示。從圖3中可以看出，當(dāng)N從1增大到5時(shí)，整合系統(tǒng)的性能隨N的增加而提高，這表明使用基于N元語(yǔ)言模型的擴(kuò)展動(dòng)作序列置信度能夠?qū)ψ罱K結(jié)果的選擇帶來(lái)幫助。當(dāng)N為5時(shí)，系統(tǒng)的性能達(dá)到最高，這表明使用5元語(yǔ)言模型對(duì)系統(tǒng)整合的幫助最大。當(dāng)N從5增大到10的時(shí)候，整合系統(tǒng)的性能隨N的增大而下降。這主要是由于隨著N逐漸增大，數(shù)據(jù)稀疏問(wèn)題越發(fā)嚴(yán)重，導(dǎo)致系統(tǒng)整合的性能逐漸下降。

為了進(jìn)一步研究擴(kuò)展動(dòng)作序列置信度對(duì)句法分析器的影響，本文將擴(kuò)展動(dòng)作置信度整合到基準(zhǔn)系統(tǒng)(單系統(tǒng))當(dāng)中，并在開(kāi)發(fā)集上利用MERT調(diào)整基準(zhǔn)系統(tǒng)以及擴(kuò)展動(dòng)作置信度的權(quán)重。整合后的系統(tǒng)在開(kāi)發(fā)集和測(cè)試集上的F1得分分別為85.55和87.36，表明擴(kuò)展動(dòng)作置信度的有效性。

6 相關(guān)工作

對(duì)于短語(yǔ)結(jié)構(gòu)句法分析的系統(tǒng)整合的研究工作，早在上個(gè)世紀(jì)就已經(jīng)開(kāi)始。Henderson 和 Brill 在文獻(xiàn)[5]中提出了兩種不同的整合方法。第一種方法是將各個(gè)子系統(tǒng)輸出的句法樹(shù)進(jìn)行相似度打分，得分最高的句法樹(shù)作為最終結(jié)果。第二種方法是將各個(gè)子系統(tǒng)輸出的句法樹(shù)拆成一序列元組(constituent)，通過(guò)統(tǒng)計(jì)每個(gè)元組出現(xiàn)的次數(shù)來(lái)判斷該元組是否可能出現(xiàn)在最終結(jié)果的句法樹(shù)中，其判斷的標(biāo)準(zhǔn)為：如果一個(gè)元組在半數(shù)以上的句法樹(shù)中出現(xiàn)，則該元組可能出現(xiàn)在最終結(jié)果中。Sagae和Lavie在文獻(xiàn)[6]中將這種方法做了進(jìn)一步擴(kuò)展，他們使用一個(gè)閾值來(lái)選擇可能出現(xiàn)在最終句法樹(shù)中的元組。Zhang等人[16]從子系統(tǒng)的輸出中選擇一棵最優(yōu)句法樹(shù)作為最終結(jié)果，并使用模型置信度作為句法樹(shù)質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)之一。以上方法與本文中方法的最主要區(qū)別在于，以上方法的系統(tǒng)整合都屬于多模型系統(tǒng)整合，而本文中的系統(tǒng)整合則是基于單個(gè)模型。

Henderson 和Brill[8]研究了基于Collins Parser的單模型系統(tǒng)整合，他們首先基于Adaboost，調(diào)整語(yǔ)料中的句子的權(quán)重，從而生成多套子系統(tǒng)，在解碼階段，他們使用文獻(xiàn)[5]中提出的元組選擇的方法對(duì)子系統(tǒng)的輸出進(jìn)行整合。然而，本文是對(duì)移進(jìn)—?dú)w約句法分析器進(jìn)行單模型系統(tǒng)整合。此外本文中提出的權(quán)重更新方法同時(shí)考慮到句子的權(quán)重和分類(lèi)樣本的權(quán)重，而且本文中的基于線(xiàn)性模型的系統(tǒng)整合方法能夠同時(shí)考慮系統(tǒng)置信度和擴(kuò)展動(dòng)作序列置信度等特征。

7 總結(jié)

本文提出了一種面向移進(jìn)—?dú)w約句法分析器的單模型系統(tǒng)整合的方法。在子系統(tǒng)生成階段，根據(jù)移進(jìn)—?dú)w約句法分析器的特點(diǎn)，本文提出了兩種不同的權(quán)重更新方法來(lái)生成多套子系統(tǒng)。在子系統(tǒng)輸出整合階段，通過(guò)使用線(xiàn)性模型對(duì)各子系統(tǒng)輸出的句法樹(shù)進(jìn)行評(píng)價(jià)，從而選出最終結(jié)果。此外，本文通過(guò)實(shí)驗(yàn)對(duì)比分析了兩種權(quán)重更新方法的有效性以及線(xiàn)性模型中使用的特征對(duì)系統(tǒng)整合的影響。

[1] Yoav Freund,Robert Schapire. BoosTexter: A Boosting-based for Text Categorization[C]Proceedings of Machine Learning. 2000. 39:135-168.

[2] Andrew Borthwick, John Sterling, Eugene Agichtein, et al. Exploiting Diverse Knowledge Sources via Maximum Entropy in Named Entity Recognition[C]//Proceedings of the Six Workshop on Very Large Corpora, 1998: 152-160.

[3] Evgeny Matusov, Nicola Ueffing, Hermann Ney. Computing consensus translation from multiple machine translation systems using enhanced hypotheses alignment[C]//Proceedings of EACL 2006: 33-40.

[4] Tong Xiao, Jingbo Zhu, Muhua Zhu,et al. AdaBoost-based System Combination for Machine Translation[C]//Proceedings of ACL 2010: 739-748.

[5] John Henderson, Eric Brill. Exploiting diversity in natural language processing: combining parsers[C]//Proceedings of EMNLP 1999: 187-194.

[6] Kenji Sagae, Alon Lavie. Parser combination by reparsing[C]//Proceedings of HLT-NAACL 2006: 129-132.

[7] Yoav Freund, Robert Schapire. A decision theoretic generalization of on-line learning and an application to boosing[J]. Journal of Computer and System Sciences, 1997, 55(1): 119-139.

[8] John Henderson, Eric Brill. Bagging and Boosting a Treebank Parser[C]//Proceedings of ANLP 2000：34-41.

[9] Michael Collins. Three generative, lexicalised models for statistical parsing[C]//Proceedings of ACL 1997：16-23.

[10] Kenji Sagae, Alon Lavie. A Classifier-based Parser with Linear Run-Time Complexity[C]//Proceedings of IWPT 2005.

[11] Kenji Sagae, Alon Lavie. A Best-First Probabilistic Shift-Reduce Parser[C]//Proceedings of ACL-COLING 2006 (poster).

[12] Michael Collins, Brain Roark. Incremental Parsing with the perceptron algorithm[C]//Proceedings of ACL 2004：111-118.

[13] A comparison of algorithms for maximum entropy parameter estimation[C]//Proceedings of CoNLL-2002：49-55.

[14] Dong C. Liu, Jorge Nocedal. On the limited memory BFGS method for large scale Optimization[C]//Proceedings of Mathematical Programming, 45:503-528.

[15] Franz J. Och. Minimum Error Rate Training in Statistical Machine Translation[C]//Proceedings of ACL 2003: 160-167.

[16] Hui Zhang, Min Zhang, Chew Lim Tan, et al. K-Best Combination of Syntactic Parsers[C]//Proceedings of EMNLP 2009: 1552-1560.

[17] Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing[D]. Phd thesis, University of Pennsylvania.

[18] Le Zhang. Maximum Entropy Modeling Toolkit for Python and C++ Reference Manual[CP/OL]. http://homepages.inf.ed.ac.uk/lzhang10/maxent_toolkit.html.

[19] Katz, S. M. Estimation of probabilities from sparse data for the language model component of a speech recogniser[J]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3): 400-401.

[20] Jesús Giménez, Lluís Márquez. SVMTool: A general POS tagger generator based on Support Vector Machines[C]//Porceedings of LREC 2004：43-46.