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

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

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

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

為了實現哈薩克語的句法分析，研究概率上下無關文法，結合哈薩克語自身的語法特征得到哈薩克語的概率上下無關文法，獲取哈薩克語PCFG參數，結合自底向下的Viterbi算法進行句法分析的歧義消除，進而實現一種有自學習能力的哈薩克語句法分析器，哈薩克語句子分析達到不錯的效果。實驗結果顯示，PCFG模型可以適用于到哈薩克語的句法分析研究。

概率上下無關文法；哈薩克語；句法分析；句法樹；Viterbi算法

現代哈薩克語短語識別及其語塊庫構建技術研究（No.61063025）、現代哈薩克語句法分析與樹庫構建關鍵技術研究（No.61063062）

0　引言

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

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

1　PCFG模型

1.1PCFG的原理

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

1.2PCFG的三個問題

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

（2）句子S有多個分析結果，最優樹的概率為P（s），使用公式（2）選擇概率最大的分析樹為最優樹。

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

（3）一個已知的句子，語法規則的概率設定可以使用EM算法在未標注的句子上訓練PCFG參數，也可以從樹庫中進行PCFG估計。

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

從未標注句子中訓練PCFG參數[5]依賴于初始設定的參數，本文使用從樹庫中進行PCFG估計。通過從標注好的樹庫中獲取上下無關文法，得到一個符合哈薩克語句法的概率上下無關文法規則集[6]，將規則在樹庫中出現的次數進行統計獲取PCFG參數。將獲取的參數與哈薩克語上下無關文法規則集相結合，形成初始的哈薩克語PCFG文法。

2.1PCFG概率參數的估計

模型的訓練[7]是語法學習的過程，即從樹庫中進行PCFG參數獲取。PCFG中概率的獲取：如產生式A→BC的概率獲取如公式（6）所示。

其中count（A→BC）是指產生式A→BC在樹庫中出現的次數。

count（A→*）是指A非終結符推出任何組合的次數。

具體的偽代碼描述為：

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規則集的自動獲取

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

For tree in treebank，parsed_sents（）:

Perform optional tree transformation

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

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

圖1　哈薩克語PCFG

2.3哈薩克語PCFG句法分析器

根據哈薩克語的句法特點和標注好的樹庫信息，結合PCFG模型的特點，形成了一個自動學習的哈薩克語概率句法分析器。它可以根據給定的標注樹庫，對樹庫進行學習，得到一個正確的哈薩克語的概率上下無關文法，并以此作為此分析器的知識，然后利用算法對生語料進行分析，得到了較好的分析結果。其對應的結構圖如圖2所示。

即當訓練樹庫如圖1（a）所示。句子進行訓練可以得到PCFG文法如圖1（c）所示。

圖2　哈薩克語句法分析器結構

3　實驗結果

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

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

表1　哈薩克語測試結果

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

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

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

（3）某些句子比較長

4　結語

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

[1]吳偉成，周俊生，曲維光.基于統計學習模型的句法分析方法綜述[J].中文信息學報2013，27（3）：9～19

[2]馮志偉.基于短語結構語法的自動句法分析.當代語言學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]張瑞嶺.一個上下文無關文法獲取過程的設計和實現[J].軟件學報，1998，9（8）:601～605

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

[7]周強.漢語句法知識的自動獲取研究.中國中文信息學會二十周年學術會議，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-），女，河北衡水人，研究生碩士，研究方向為自然語言信息處理

古麗拉·阿東別克（1962-），女，新疆烏魯木齊人，博士，博士生導師，研究方向為自然語言信息處理

牛娜（1989-），女，新疆伊犁人，研究生碩士，研究方向為自然語言信息處理

于智娟（1988-），女，新疆沙灣人，研究生碩士，研究方向為自然語言信息處理

2015-04-08

2015-05-13