由粗到精的哈薩克語(yǔ)短語(yǔ)結(jié)構(gòu)句法分析研究

梁金蓮,古麗拉·阿東別克

(1. 新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046； 2. 新疆多語(yǔ)種信息技術(shù)實(shí)驗(yàn)室，新疆大學(xué)，新疆 烏魯木齊 830046；3. 國(guó)家語(yǔ)言資源監(jiān)測(cè)與研究少數(shù)民族語(yǔ)言中心哈薩克和柯爾克孜語(yǔ)文基地，新疆大學(xué)，新疆 烏魯木齊 830046)

0　引言

自然語(yǔ)言處理過(guò)程一般包含詞性分析、句法分析和語(yǔ)義分析。句法分析是自然語(yǔ)言處理的核心技術(shù)之一[1]。目前句法分析的主要方法包括基于規(guī)則的方法和基于統(tǒng)計(jì)的方法?；诮y(tǒng)計(jì)的句法分析方法在處理歧義等方面有較好的效果，相對(duì)也比較靈活。基于統(tǒng)計(jì)的方法在自然語(yǔ)言處理領(lǐng)域已逐漸成為主流[2]方法。

目前，哈薩克語(yǔ)的研究已經(jīng)完成了詞法分析[3]的研究，進(jìn)行到句法分析階段。其中，文獻(xiàn)[4]中提出一種規(guī)則與最大熵結(jié)合的方法對(duì)哈薩克語(yǔ)基本動(dòng)詞短語(yǔ)進(jìn)行識(shí)別；文獻(xiàn)[5]提出了一種基于條件隨機(jī)場(chǎng)模型的哈薩克語(yǔ)的基本短語(yǔ)自動(dòng)識(shí)別方法；文獻(xiàn)[6]采用基于規(guī)則自動(dòng)識(shí)別及人工標(biāo)注的方法建立基本名詞短語(yǔ)標(biāo)注語(yǔ)料庫(kù)，在句法分析階段也進(jìn)行了相關(guān)的研究。文獻(xiàn)[3]中采用PCFG方法，結(jié)合自底向下的Vitrtbi算法實(shí)現(xiàn)一種有自學(xué)能力的哈薩克語(yǔ)句法分析器： 文獻(xiàn)[7]中根據(jù)概率上下文無(wú)關(guān)文法模型和Chart算法特點(diǎn)，將概率引入Chart算法，提出一種PChart算法，實(shí)現(xiàn)一種基于PChart算法的哈薩克語(yǔ)句法分析器。在句法分析研究中，無(wú)論是基于統(tǒng)計(jì)的方法還是基于規(guī)則的方法，都不能完全解決句法分析的問題，只有將兩者結(jié)合起來(lái)，才有可能最大限度地解決句法分析中存在的問題。概率上下文無(wú)關(guān)文法(probabilistic context free grammars,PCFG)，是統(tǒng)計(jì)與規(guī)則相結(jié)合的方法。PCFG只能捕捉到句子的結(jié)構(gòu)和規(guī)則，不能捕捉到上下文的信息，因此對(duì)語(yǔ)言的描述是粗粒度的。本文提出一種PCFG[8]與感知機(jī)相結(jié)合的方法進(jìn)行句法分析。感知機(jī)在進(jìn)行訓(xùn)練過(guò)程中，可以捕獲到句子的上下文信息。利用感知機(jī)捕獲到的信息，對(duì)PCFG產(chǎn)生的解析候選樹進(jìn)行重排序，進(jìn)一步提高哈薩克語(yǔ)句法分析的效果，進(jìn)而彌補(bǔ)PCFG的不足之處。本文提出的方法分為兩個(gè)階段，在第一階段，采用PCFG方法，對(duì)輸入的每個(gè)待解析的句子，粗略地產(chǎn)生20個(gè)概率最高的句子候選集，由于句子長(zhǎng)度的差異，有些句子的最佳候選集長(zhǎng)度小于20。在感知機(jī)訓(xùn)練過(guò)程中，將訓(xùn)練得到的參數(shù)，以及提取特征得到的特征模板，對(duì)第一階段生成的20個(gè)最佳候選集進(jìn)行重排序。將重排序的結(jié)果和PCFG得到的結(jié)果按照一定比例選取，得到解析結(jié)果，將其作為重排序的最終解析結(jié)果。實(shí)驗(yàn)表明，使用PCFG和感知機(jī)相結(jié)合的方法，可以得到比較理想的句法分析結(jié)果。

1　PCFG和感知機(jī)

由于PCFG句法分析不能捕捉到句子的上下文信息，消歧能力有限，而感知機(jī)可以通過(guò)自學(xué)習(xí)，捕捉到句子中的細(xì)粒度信息，可以彌補(bǔ)PCFG的不足。因此，本文采用PCFG和感知機(jī)相結(jié)合的方法，對(duì)哈薩克語(yǔ)進(jìn)行句法分析。

1.1　PCFG模型

PCFG模型是句法分析中研究較廣泛和充分的模型之一。它是一種統(tǒng)計(jì)和規(guī)則相結(jié)合的方法。CFG是獲取語(yǔ)言中的句法規(guī)則，由非終結(jié)符、詞匯表、開始字符及規(guī)則的產(chǎn)生式集合構(gòu)成[9]。PCFG則是在此規(guī)則中增加了概率參數(shù)，通過(guò)計(jì)算概率，預(yù)測(cè)可能性最大的句法結(jié)構(gòu)。

對(duì)于一個(gè)輸入句子S，通過(guò)統(tǒng)計(jì)的方法得到解析樹。其得到最優(yōu)解Tbest如式(1)所示。

(1)

其中T表示候選樹，P(T,S)是候選樹T中所有規(guī)則的概率的乘積，如式(2)所示。

│LHSi)

(2)

通過(guò)計(jì)算句子S中所有可能的T中的概率P(T,S),選出概率最大的值。在計(jì)算概率時(shí)，需給定三個(gè)假設(shè)： 祖先無(wú)關(guān)性假設(shè)、位置不變性假設(shè)及上下文無(wú)關(guān)性假設(shè)。

1.2　感知機(jī)算法

神經(jīng)網(wǎng)絡(luò)由一個(gè)或者多個(gè)神經(jīng)元組成。而一個(gè)神經(jīng)元包括輸入、輸出和“內(nèi)部處理器”。神經(jīng)元從輸入端接收信息，通過(guò)“內(nèi)部處理器”將這些信息進(jìn)行一定的處理，最后通過(guò)輸出端輸出。單層感知器(single layer perceptron)是最簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)。它包含輸入層和輸出層，而輸入層和輸出層是直接相連的。

康奈爾大學(xué)教授Frank Rosenblatt 1957年提出“感知機(jī)(perceptron)”，是第一個(gè)用算法來(lái)精確定義的神經(jīng)網(wǎng)絡(luò)，也是第一個(gè)具有自組織學(xué)習(xí)能力的數(shù)學(xué)模型，是目前許多新的神經(jīng)網(wǎng)絡(luò)模型的始祖。

單層感知機(jī)訓(xùn)練步驟如下：

第一步： 函數(shù)輸出數(shù)量相等的感知機(jī)會(huì)以小的初始值開始。

第二步： 選取訓(xùn)練集中的一個(gè)例子作為輸入，計(jì)算感知機(jī)的輸出。

第三步： 對(duì)于每一個(gè)感知機(jī)，如果其結(jié)果和該例子的結(jié)果不匹配，調(diào)整初始值。

第四步： 繼續(xù)采用訓(xùn)練集中的例子，重復(fù)輸入，進(jìn)行匹配，調(diào)整參數(shù)。

在本文中，重排序的訓(xùn)練過(guò)程及句法分析解碼階段都采用感知機(jī)算法。感知機(jī)算法[10-11]如表1所示：

表1　感知機(jī)算法

2　重排序

本文的句法分析主要分為兩個(gè)階段。第一階段，采用PCFG的方法，為待分析的每個(gè)句子產(chǎn)生20個(gè)概率最高的候選解析列表。第二階段，使用感知機(jī)重排序的方法，對(duì)第一階段產(chǎn)生的20個(gè)概率最高的候選解析序列進(jìn)行重排序，將兩者得分按照比例相加，選出得分最高的候選樹，作為句法分析最終的結(jié)果。本文中的句法分析流程如圖1所示。

圖1　句法分析流程圖

2.1　哈薩克語(yǔ)的20個(gè)最佳解析

在這個(gè)階段，對(duì)于每個(gè)輸入的字符串S，采用n-best解析算法[8]，返回n個(gè)最高概率的解析Y(s)={y1(s),…,yn(s)}，以及根據(jù)解析器產(chǎn)生概率模型的每個(gè)解析y的概率P(y)。本文的實(shí)驗(yàn)數(shù)量n為20。但是有些簡(jiǎn)單的句子，實(shí)際上得到的解析列表集少于20個(gè)。

目前哈薩克語(yǔ)中有10種詞性標(biāo)注和5種短語(yǔ)標(biāo)注集[7]，如表2所示。

對(duì)于給定的哈薩克語(yǔ)的句子S，通過(guò)PCFG得到20個(gè)候選集，例如，輸入句子形如：

則該句子中的一個(gè)候選樹如圖2所示。

表2　哈薩克語(yǔ)標(biāo)注集

圖2　哈薩克語(yǔ)句法樹

2.2　訓(xùn)練

在重排序階段，首先使用感知機(jī)算法對(duì)語(yǔ)料進(jìn)行訓(xùn)練，再將PCFG階段每個(gè)句子產(chǎn)生的20個(gè)候選解析樹進(jìn)行解碼，解碼的過(guò)程就是對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行重新算分，重新排序。

在用感知計(jì)算法進(jìn)行訓(xùn)練的過(guò)程，對(duì)輸入x∈χ有一個(gè)映射y∈у，在句法分析中χ是一個(gè)未處理的句子集合，у是一個(gè)χ句子中的標(biāo)準(zhǔn)句法樹的集合。下面首先給出如下四個(gè)假設(shè)：

假設(shè)一： 訓(xùn)練樣本(xi,yi),i=1,…,n

假設(shè)二： 定義函數(shù)GEN，GEN(x)是列舉了輸入x所有可能的句法樹集合

(3)

在感知機(jī)訓(xùn)練中需要特征模板，特征模板[8]如表3所示。

表3　感知機(jī)訓(xùn)練特征模板

其中，W0表示當(dāng)前節(jié)點(diǎn)的詞，Tf表示父節(jié)點(diǎn)的詞性，Wf表示父節(jié)點(diǎn)的詞，Wc表示子節(jié)點(diǎn)的詞，Tc表示子節(jié)點(diǎn)的詞性，Wb表示兄弟節(jié)點(diǎn)的詞，Tb表示兄弟節(jié)點(diǎn)的詞性。

2.3　重排序

在PCFG階段，對(duì)于給定一個(gè)句子S，可以產(chǎn)生20個(gè)最佳解析的候選集，將這20個(gè)候選樹作為感知機(jī)重排序的輸入。在重排序階段，感知機(jī)重新計(jì)算每個(gè)父節(jié)點(diǎn)的分?jǐn)?shù)，最后將每個(gè)父節(jié)點(diǎn)的分?jǐn)?shù)相乘，得到每個(gè)候選樹的得分[13]。最終的句法分析的結(jié)果，以PCFG的結(jié)果和重排序的結(jié)果按照一定比例，選出最佳的句法分析。圖3顯示了一個(gè)候選樹計(jì)算節(jié)點(diǎn)的例子。

圖3　感知機(jī)計(jì)算節(jié)點(diǎn)示意圖

計(jì)算父節(jié)點(diǎn)得分如式(4)所示。

(4)

S=∑S(p)

(5)

最終的評(píng)分參考PCFG和感知機(jī)重排序之后的兩者的得分，按照一定的比例求和，如式(6)所示。

S=SPCFG+t·SP

(6)

其中SPCFG是PCFG的得分，SP是感知機(jī)重排序之后的得分，t是權(quán)重系數(shù)。

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

本文的數(shù)據(jù)來(lái)源于新疆中小學(xué)哈薩克語(yǔ)文課文。這些原始語(yǔ)料以短語(yǔ)形式標(biāo)注過(guò)，例如名詞短語(yǔ)標(biāo)注為NP，動(dòng)詞短語(yǔ)標(biāo)注為VP等，本語(yǔ)料中哈薩克語(yǔ)的短語(yǔ)標(biāo)注分為五類，分別為名詞短語(yǔ)、動(dòng)詞短語(yǔ)、形容詞短語(yǔ)、數(shù)詞短語(yǔ)和副詞短語(yǔ)。

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

使用的原始語(yǔ)料及語(yǔ)料中的句法樹的形式，如下所示。

原始語(yǔ)料：

句法樹形式：

(S

(..))

評(píng)價(jià)指標(biāo)采用常用的PARSEVAL評(píng)價(jià)體系評(píng)測(cè)句法分析，標(biāo)記正確率(labeled precision, LP)、標(biāo)記召回率(labeled recall, LR)、F1 值作為評(píng)價(jià)標(biāo)準(zhǔn)。PARSEVAL 是應(yīng)用比較廣泛的短語(yǔ)結(jié)構(gòu)分析器性能評(píng)價(jià)方法，標(biāo)記正確率是句法分析結(jié)果中正確短語(yǔ)數(shù)占結(jié)果中短語(yǔ)總數(shù)的比例，如式(7)所示；標(biāo)記召回率是句法分析結(jié)果中正確短語(yǔ)數(shù)占標(biāo)準(zhǔn)樹中短語(yǔ)總數(shù)的比例，如式(8)所示；F1 值是綜合正確率和召回率兩者的綜合指標(biāo)，如式(9)所示。

3.2　實(shí)驗(yàn)結(jié)果

首先利用PCFG對(duì)句子進(jìn)行解析。其中以一個(gè)句子的五個(gè)候選樹為例進(jìn)行說(shuō)明，如圖4所示。

圖4　5個(gè)句法解析候選樹

文中先用PCFG句法分析器產(chǎn)生最佳候選解析樹，再用感知機(jī)對(duì)訓(xùn)練語(yǔ)料進(jìn)行訓(xùn)練，并將訓(xùn)練得到的參數(shù)用于感知機(jī)句法重排序，重新計(jì)算PCFG句法解析器生成的候選樹的總分。在感知機(jī)重排序階段，感知機(jī)不對(duì)PCFG生成的句法結(jié)構(gòu)做任何改動(dòng)，僅通過(guò)訓(xùn)練得到的特征模板和參數(shù)對(duì)PCFG生成的句法結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)重新計(jì)算得分。在表4中顯示的是由PCFG句法分析器的準(zhǔn)確率，召回率和F1值，以及感知機(jī)重排序之后，和PCFG句法分析器的結(jié)果，按照一定比例的解析最終的句法分析的準(zhǔn)確率(LP)、召回率(LR)和F1值。

表4　句法分析實(shí)驗(yàn)結(jié)果

表5顯示的是將測(cè)試語(yǔ)料根據(jù)不同的句子長(zhǎng)度進(jìn)行測(cè)試的實(shí)驗(yàn)結(jié)果。該文將句子長(zhǎng)度分為三種類型，分別是長(zhǎng)度為1～5的句子；長(zhǎng)度為6～15句子和長(zhǎng)度大于15的句子。

表5　不同句長(zhǎng)實(shí)驗(yàn)結(jié)果

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

從表4中的實(shí)驗(yàn)結(jié)果可以看出，經(jīng)過(guò)感知機(jī)重排序之后的句法分析，相比較單一的使用PCFG句法分析器，句法分析的結(jié)果有所提高，準(zhǔn)確率提高3.2%，主要原因是PCFG對(duì)句法解析的過(guò)程是粗粒度的，不能捕捉到上下文的信息，因此在句法解析的過(guò)程中，捕捉不到上下文的信息；其次，PCFG在進(jìn)行句法解析的過(guò)程中，還需要句法規(guī)則，因此對(duì)語(yǔ)料的規(guī)模要求較高，以上因素導(dǎo)致基于PCFG的句法分析結(jié)果不夠理想。從表5中的實(shí)驗(yàn)結(jié)果可以看出，句長(zhǎng)為1～5的實(shí)驗(yàn)結(jié)果顯示，重排序之后準(zhǔn)確率提高3.2%；句長(zhǎng)為6～15重排序之后準(zhǔn)確率提高3.7%；句長(zhǎng)大于15重排序之后準(zhǔn)確率提高2.6%。主要原因在于，較短的句子，句法結(jié)構(gòu)不是特別規(guī)范，較長(zhǎng)的句子結(jié)構(gòu)較復(fù)雜。因此，句子結(jié)構(gòu)較完整又較規(guī)范的句子效果最好。

由實(shí)驗(yàn)結(jié)果可以明顯地看出，重排序的句法分析結(jié)果比PCFG效果要好，但在句法解析結(jié)果中，仍有些句法解析的結(jié)果不夠理想，主要原因如下：

(1) 在PCFG解析過(guò)程中，有些句子并沒有匹配正確的規(guī)則，因此產(chǎn)生的候選樹的結(jié)果并不是特別理想。

(2) 有些句子的結(jié)構(gòu)比較難，有些句子的結(jié)構(gòu)不是嚴(yán)格的按照句法規(guī)則，PCFG在進(jìn)行句法解析的過(guò)程中存在一定的難度。

4　結(jié)束語(yǔ)

本文描述了由粗到精的哈薩克語(yǔ)短語(yǔ)結(jié)構(gòu)句法分析。主要由PCFG解析器對(duì)每個(gè)待分析的句子進(jìn)行解析，生成20個(gè)最佳候選樹，然后由感知機(jī)進(jìn)行訓(xùn)練得到參數(shù)以及特征模板，再對(duì)生成的20個(gè)最佳候選樹進(jìn)行重排序。PCFG對(duì)語(yǔ)言的描述是粗粒度的，該文的重排序的方法是細(xì)粒度的，彌補(bǔ)了其不能捕捉到上下文信息的不足。在PCFG進(jìn)行句法解析的過(guò)程當(dāng)中，需要大量的語(yǔ)料，以及需要的語(yǔ)料題材多樣性，因此，之后的工作之一是對(duì)語(yǔ)料以及語(yǔ)料題材進(jìn)一步擴(kuò)大。語(yǔ)言是復(fù)雜的，在感知機(jī)訓(xùn)練階段，重排序過(guò)程當(dāng)中，使用相同的參數(shù)，并沒有將語(yǔ)言的特性很好的表現(xiàn)出來(lái)，在后續(xù)的重排序的的過(guò)程當(dāng)中，可以考慮使用不同的參數(shù)，結(jié)合每個(gè)結(jié)點(diǎn)的信息，進(jìn)行參數(shù)訓(xùn)練，對(duì)生成的候選句法樹進(jìn)行重排序。

[1]吳偉成, 周俊生, 曲維光. 基于統(tǒng)計(jì)學(xué)習(xí)模型的句法分析方法綜述[J]. 中文信息學(xué)報(bào), 2013, 27(3): 9-19.

[2]劉挺, 馬金山. 漢語(yǔ)自動(dòng)句法分析的理論與方法[J]. 當(dāng)代語(yǔ)言學(xué), 2009(2): 100-112.

[3]尚文清, 古麗拉·阿東別克, 牛娜,等. 基于PCFG模型的哈薩克語(yǔ)句法分析[J]. 現(xiàn)代計(jì)算機(jī)(專業(yè)版), 2015(5): 7-10.

[4]古麗扎達(dá)·海沙, 古麗拉·阿東別克. 哈薩克語(yǔ)動(dòng)詞短語(yǔ)自動(dòng)識(shí)別研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(2): 218-223.

[5]汪泱, 古麗拉·阿東別克, 戶冰心,等. 基于條件隨機(jī)場(chǎng)的哈薩克語(yǔ)基本短語(yǔ)自動(dòng)識(shí)別[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2014(10): 3602-3607.

[6]孫瑞娜, 古麗拉·阿東別克. 哈薩克語(yǔ)基本名詞短語(yǔ)自動(dòng)識(shí)別研究與實(shí)現(xiàn)[J]. 中文信息學(xué)報(bào), 2010, 24(6): 114-119.

[7]尚文清, 古麗拉·阿東別克, 牛娜,等. 基于PChart算法的哈薩克語(yǔ)句法分析[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2016, 37(3): 832-836.

[8]Charniak E, Johnson M. Coarse-to-fine n -best parsing and MaxEnt discriminative reranking[C]//Proceedings of the ACL 2005, Meeting of the Association for Computational Linguistics, Proceedings of the Conference, 25-30 June 2005, University of Michigan, USA. DBLP, 2005: 173-180.

[9]Kasami T. An efficient recognition and syntax-analysis algorithm for context-free languages[J], 1966.

[10]Collins M, Roark B. Incremental parsing with the perceptron algorithm[C]//Proceedings of the Meeting on Association for Computational Linguistics. Association for Computational Linguistics, 2004: 111.

[11]Martí, Nez C, Prodinger H. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms[C]//Proceedings of the ACL-02 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2002: 1-8.

[12]Charniak E. A maximum-entropy-inspired parser[C]//Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference. Association for Computational Linguistics, 2000: 132-139.

[13]Socher R, Bauer J, Manning C D, et al. Parsing with Compositional Vector Grammars[C]//Proceedings of the ACL (1). 2013: 455-465.