尚文清，古麗拉·阿東別克，?！∧龋谥蔷辏?.新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊830046；2.國家語言資源監(jiān)測與研究中心少數(shù)民族語言中心哈薩克和柯爾克孜語言基地，烏魯木齊830046）

基于PCFG模型的哈薩克語句法分析

尚文清1，2，古麗拉·阿東別克1，2，牛娜1，2，于智娟1，2
（1.新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊830046；2.國家語言資源監(jiān)測與研究中心少數(shù)民族語言中心哈薩克和柯爾克孜語言基地，烏魯木齊830046）

為了實(shí)現(xiàn)哈薩克語的句法分析，研究概率上下無關(guān)文法，結(jié)合哈薩克語自身的語法特征得到哈薩克語的概率上下無關(guān)文法，獲取哈薩克語PCFG參數(shù)，結(jié)合自底向下的Viterbi算法進(jìn)行句法分析的歧義消除，進(jìn)而實(shí)現(xiàn)一種有自學(xué)習(xí)能力的哈薩克語句法分析器，哈薩克語句子分析達(dá)到不錯(cuò)的效果。實(shí)驗(yàn)結(jié)果顯示，PCFG模型可以適用于到哈薩克語的句法分析研究。

概率上下無關(guān)文法；哈薩克語；句法分析；句法樹；Viterbi算法

現(xiàn)代哈薩克語短語識(shí)別及其語塊庫構(gòu)建技術(shù)研究（No.61063025）、現(xiàn)代哈薩克語句法分析與樹庫構(gòu)建關(guān)鍵技術(shù)研究（No.61063062）

0　引言

句法分析是將句子描述成分析樹的一個(gè)過程，它是自然語言處理中的一個(gè)基本問題[1]，如機(jī)器翻譯、信息獲取、自動(dòng)文摘等都要依賴句法分析。從上世紀(jì)50年代開始人們對自然語言處理至今，語言的研究層次主要分為詞法分析、短語分析、句法分析語義分析和語用分析,句法分析一直是自然語言研究中的阻礙。目前各種語言（如英語、漢語等）在句法分析方面都取得了很好的研究成果，句法分析的方法主要為基于規(guī)則和統(tǒng)計(jì)的方法。近些年，基于統(tǒng)計(jì)學(xué)習(xí)模型的句法分析已經(jīng)是研究者們的熱點(diǎn)[1]。

哈薩克語語言處理方面，目前已經(jīng)完成了對哈薩克語的詞法分析的研究、哈薩克語基本名詞短語自動(dòng)識(shí)別和動(dòng)詞短語自動(dòng)識(shí)別等相關(guān)工作并且已經(jīng)取得了很好的效果。哈薩克語在句法方面的工作才剛剛起步。本文首先簡要介紹了PCFG（Probabilistic Context Free Grammar）模型,對模型中的三個(gè)問題進(jìn)行了相應(yīng)的解決；重點(diǎn)描述了哈薩克語的PCFG文法的獲取方法、過程及對Viterbi算法過程的描述；然后通過對哈薩克語的分析結(jié)果進(jìn)行分析；最后，對哈薩克語的句法分析下一步的研究方向提出了一些想法。

1　PCFG模型

1.1PCFG的原理

CFG（Context Free Grammar）是獲取語言中句法規(guī)則的一種方式[2]。它包括了終結(jié)符（如）、非終結(jié)符（如NP）、開始字符（如S）、規(guī)則的產(chǎn)生式集合（如S→NP）。使用CFG對句子進(jìn)行分析可以得到不同的分析結(jié)果。PCFG把概率引入上下文無關(guān)文法，將統(tǒng)計(jì)方法和規(guī)則方法進(jìn)行了有效的融合，具有十分重要的意義，概率上下無關(guān)文法通過為每條產(chǎn)生式規(guī)則指派一個(gè)概率值，擴(kuò)展了一個(gè)上下無關(guān)文法的描述體系，即A→姿，p（A→姿）并且滿足ΣA→姿P（A→姿）=1。它是最簡單最常用的概率語法模型[3]，通過判定概率只返回一個(gè)分析結(jié)果。

1.2PCFG的三個(gè)問題

（1）對于一個(gè)語法G，句子S的分析概率為P（S，G）。P（t，G）是分析的句子S中的句法分析樹t的概率，它為所有施用規(guī)則概率之積，其中t∈S。句子S的分析概率如公式（1）所示。

（2）句子S有多個(gè)分析結(jié)果，最優(yōu)樹的概率為P（s），使用公式（2）選擇概率最大的分析樹為最優(yōu)樹。

Viterbi算法[4]是使用動(dòng)態(tài)規(guī)則算法找到句子中最可能的句法分析樹，不管它找到多少子樹，它只選擇概率最大的一個(gè)。如：韋特比變量γij（A）為非終結(jié)符Α經(jīng)由某一推導(dǎo)而產(chǎn)生wiwi+1…wj的最大概率，Ψ（A）為最佳推導(dǎo)。其中動(dòng)態(tài)規(guī)則公式為：

（3）一個(gè)已知的句子，語法規(guī)則的概率設(shè)定可以使用EM算法在未標(biāo)注的句子上訓(xùn)練PCFG參數(shù)，也可以從樹庫中進(jìn)行PCFG估計(jì)。

2　哈薩克語概率上下無關(guān)文法的獲取和分析算法

從未標(biāo)注句子中訓(xùn)練PCFG參數(shù)[5]依賴于初始設(shè)定的參數(shù)，本文使用從樹庫中進(jìn)行PCFG估計(jì)。通過從標(biāo)注好的樹庫中獲取上下無關(guān)文法，得到一個(gè)符合哈薩克語句法的概率上下無關(guān)文法規(guī)則集[6]，將規(guī)則在樹庫中出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)獲取PCFG參數(shù)。將獲取的參數(shù)與哈薩克語上下無關(guān)文法規(guī)則集相結(jié)合，形成初始的哈薩克語PCFG文法。

2.1PCFG概率參數(shù)的估計(jì)

模型的訓(xùn)練[7]是語法學(xué)習(xí)的過程，即從樹庫中進(jìn)行PCFG參數(shù)獲取。PCFG中概率的獲?。喝绠a(chǎn)生式A→BC的概率獲取如公式（6）所示。

其中count（A→BC）是指產(chǎn)生式A→BC在樹庫中出現(xiàn)的次數(shù)。

count（A→*）是指A非終結(jié)符推出任何組合的次數(shù)。

具體的偽代碼描述為：

For each tree in the Treebank

Get the context-free rules from the tree

For each（L-＞R）context-free of rule

Update the count of L

Update the count of（L-＞R）

For each（L-＞R）context-free of rule in the Treebank

Count（L）=the count of L!Count（L-＞R）=the count of（L-＞R）P

rob（L-＞R）=Count（L-＞R）/Count（L）

2.2規(guī)則集的自動(dòng)獲取

從樹庫中獲取規(guī)則集的過程為：首先，將樹庫如圖1（a）轉(zhuǎn)換為樹的形式如圖1（b），然后將樹的形式轉(zhuǎn)為CFG規(guī)則。則訓(xùn)練樹庫中獲取PCFG文法的過程的偽代碼為：

For tree in treebank，parsed_sents（）:

Perform optional tree transformation

Correspond to the non-terminal nodes of the tree generate the productions

哈薩克語規(guī)則集的獲取，首先，先將哈薩克語熟語料用相應(yīng)的方法進(jìn)行處理，將處理過的熟語料按照上述的方式可以直接獲取文法規(guī)則；然后，將獲取的文法規(guī)則用哈薩克語的反相應(yīng)方法進(jìn)行處理得到正確的哈薩克語的規(guī)則集；根據(jù)PCFG概率參數(shù)獲取方法得到適合哈薩克語句法的PCFG文法如圖1（b）。

圖1　哈薩克語PCFG

2.3哈薩克語PCFG句法分析器

根據(jù)哈薩克語的句法特點(diǎn)和標(biāo)注好的樹庫信息，結(jié)合PCFG模型的特點(diǎn)，形成了一個(gè)自動(dòng)學(xué)習(xí)的哈薩克語概率句法分析器。它可以根據(jù)給定的標(biāo)注樹庫，對樹庫進(jìn)行學(xué)習(xí)，得到一個(gè)正確的哈薩克語的概率上下無關(guān)文法，并以此作為此分析器的知識(shí)，然后利用算法對生語料進(jìn)行分析，得到了較好的分析結(jié)果。其對應(yīng)的結(jié)構(gòu)圖如圖2所示。

即當(dāng)訓(xùn)練樹庫如圖1（a）所示。句子進(jìn)行訓(xùn)練可以得到PCFG文法如圖1（c）所示。

圖2　哈薩克語句法分析器結(jié)構(gòu)

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

本文在Windows 7環(huán)境下使用Python語言[8]和NLTK自然語言[8]處理工具編寫的哈薩克語分析器界面如圖3所示。其中訓(xùn)練語料為如圖1（a）所示的樹庫存放在txt文本中，測試語料如圖3原始文件所示，存放在txt文本中，一句占用一行。

圖3　哈薩克語句法分析界面

表1　哈薩克語測試結(jié)果

通過對300個(gè)哈薩克語句子進(jìn)行封閉性測試，測試結(jié)果如圖3輸出結(jié)果所示。測試數(shù)據(jù)結(jié)果如表1所示。結(jié)果顯示基于PCFG模型的哈薩克語句法分析效果很好，但也有些句子沒有正確地分析成功，原因主要有：

（1）一些句子沒有匹配正確的規(guī)則

（2）某些句子的順序比較難

（3）某些句子比較長

4　結(jié)語

本文描述了基于概率上下無關(guān)文法適用于哈薩克語和NLTK自底向上的Viterbi算法分析技術(shù)。NLTK是自然語言處理工具。由于哈薩克語的句法分析剛剛起步，很多方面還不成熟，例如語料規(guī)模比較小、語料題材的選取等使得哈薩克語的句法分析器不夠完善?？傊?，本文的哈薩克語概率分析器對一些相對簡單的句子分析效果比較好，下一步，我們對基于短語結(jié)構(gòu)的哈薩克語句法分析從以下幾個(gè)方面改進(jìn)：①訓(xùn)練語料的不斷擴(kuò)充和修改；②參數(shù)的訓(xùn)練；③自動(dòng)獲取哈薩克語的相關(guān)的結(jié)構(gòu)信息，盡量提高系統(tǒng)的運(yùn)行效率；④改進(jìn)算法等方面進(jìn)行探索研究。

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

[2]馮志偉.基于短語結(jié)構(gòu)語法的自動(dòng)句法分析.當(dāng)代語言學(xué)2000，2（2）：84～98

[3]Booth T L，Thompson R A.Applying Probabihty Measures to Abstract Languages.IEEE Tmnsactiom on Computers，1973，C-22（5）：442～450

[4]D.Mckee，K.Krebsbach.A learning Natural Language Parser[J]，2004.https://www2.lawrence.edu/fast/krebsbak/Research/Publications/ pdf/mics08-mckee.pdf

[5]張瑞嶺.一個(gè)上下文無關(guān)文法獲取過程的設(shè)計(jì)和實(shí)現(xiàn)[J].軟件學(xué)報(bào)，1998，9（8）:601～605

[6]王鵬，戴新宇，陳家俊，王啟祥.基于規(guī)則的漢語句法分析方法研究.計(jì)算機(jī)工程與應(yīng)用[J]，2003：29

[7]周強(qiáng).漢語句法知識(shí)的自動(dòng)獲取研究.中國中文信息學(xué)會(huì)二十周年學(xué)術(shù)會(huì)議，2001[c]

[8]Stenven Bird，Ewan Klein Edward Loper[M].Natural Language Processing with Python.O’Reilly Media，Inc.2009:291～322

Probabilistic Context Free Grammars;Kazakh;Syntactic Parser;Syntactic Tree;Viterbi Algorithm

Syntactic Analysis of Kazakh Language Based on PCFG Model

SHANG Wen-qing1，2，Gulila·Altenbek1，2，NIU Na1，2，YU Zhi-juan1，2
（1.Department of Information Science and Engineering，Xinjiang University，Urumqi830046）（2.National Language Resource Monitoring and Research Center，Minority Language Center，Hazakh and Kirgiz Language Base，Urumqi 830046）

Introduces the work of Kazakh language in language processing,does the technology research on the construction of corpus annotation of syntax,analyzes the method to study the Kazakh syntax,and combined with the existing parsing model,it can learn that Kazakh probabilistic context free grammars from the annoted syntactic corpus,and then puts forward a self-learning Kazakh syntax parser.Experimental results show that it perform well.

1007-1423（2015）14-0007-04

10.3969/j.issn.1007-1423.2015.14.002

尚文清（1988-），女，河北衡水人，研究生碩士，研究方向?yàn)樽匀徽Z言信息處理

古麗拉·阿東別克（1962-），女，新疆烏魯木齊人，博士，博士生導(dǎo)師，研究方向?yàn)樽匀徽Z言信息處理

牛娜（1989-），女，新疆伊犁人，研究生碩士，研究方向?yàn)樽匀徽Z言信息處理

于智娟（1988-），女，新疆沙灣人，研究生碩士，研究方向?yàn)樽匀徽Z言信息處理

2015-04-08

2015-05-13