基于單字提示特征的中文命名實體識別快速算法

1、基于單字提示特征的中文命名實體識別快速算法    摘要：近年來條件隨機場(CRF)模型在自然語言處理中的應(yīng)用越來越廣泛。標(biāo)準的線性鏈(Linear-chain)模型一般采用L-BFGS參數(shù)估計方法，收斂速度慢。本文在分析模型復(fù)雜度的基礎(chǔ)上提出了一種改進的快速CRP算法。該算法通過引入小規(guī)模單字特征降低特征的規(guī)模，并通過在推理過程中引入任務(wù)相關(guān)的人工知識壓縮Viterbi和Baum-Welch格搜索空間，提高了訓(xùn)練的速度。在中文863命名實體識別評測語料和SIGHAN06語料集上進行的實驗表明，該算法在不影響中文命名實體識別精度的同時，有效地降低了模型的訓(xùn)

2、練代價。關(guān)鍵詞：計算機應(yīng)用；中文信息處理；中文命名實體識別；條件隨機場；自然語言處理；機器學(xué)習(xí)1引言命名實體識別是確定文檔中的人名、地名和機構(gòu)名等名詞短語的過程。它是信息抽取、問答系統(tǒng)、機器翻譯、文檔摘要、跨語言檢索等自然語言處理應(yīng)用的關(guān)鍵技術(shù)之一。與其他語言相比，中文缺乏詞間分隔與大小寫等語法特征，其他語言中常用的表層局部環(huán)境信息往往不足以完成中文命名實體識別的任務(wù)。因而中文命名實體識別更為困難。在早期基于規(guī)則的中文命名實體識別系統(tǒng)中，特征融合自由，各種方面的信息以規(guī)則的形式引入。眾所周知，規(guī)則系統(tǒng)的缺點是工程量大，移植困難，因此當(dāng)前基于大規(guī)模語料的機器學(xué)習(xí)已成為主流方法。在中文命名實體識別

3、中，常見的學(xué)習(xí)模型有最大熵模型、隱馬爾科夫模型以及條件隨機場模型。條件隨機場(Conditional Random Fields，CRF)模型實質(zhì)上是基于馬爾科夫依賴假設(shè)的最大熵模型，可以引入多種靈活的允許交疊的特征，沒有搜索空間過大或標(biāo)注不一致的問題。對于NER這樣的序列文本標(biāo)注任務(wù)，諸多研究工作表明CRF模型綜合了最大熵和HMM模型各自的優(yōu)點，因而近年在詞類標(biāo)注、中文分詞、淺層分析、命名實體識別中廣為應(yīng)用。在這些工作中，大多采用了標(biāo)準線性鏈(Lin-earchain)結(jié)構(gòu)的CRF實現(xiàn)。其常規(guī)的解碼與單輪訓(xùn)練算法時間復(fù)雜度與特征空間的規(guī)模成正比。特別地，在幾十萬到幾百萬字的語料上，基于多特征

4、的CRF系統(tǒng)特征規(guī)?？蛇_百萬到千萬，時收斂速度緩慢。當(dāng)引入更多更豐富的特征會引起規(guī)模的劇烈上升，甚至不可運行。因此，如何降低訓(xùn)練的代價，提高訓(xùn)練的速度，是基于標(biāo)準線性鏈結(jié)構(gòu)的CRF模型命名實體識別實現(xiàn)中的技術(shù)難點。當(dāng)前主要的解決思路是壓縮模型的特征規(guī)模。有三個思路：單字多特征、詞語簡單特征與組合模型標(biāo)注器。單字模型一般以字元組為模型特征，其局限是字特征過于細致，容易形成過擬合，泛化不足。而在基于詞的模型中，一般采用較簡單的提示詞列表、名稱列表等特征。由于稀疏問題，較少使用二元以上的詞元組。當(dāng)前兩者結(jié)合，使用大量的字、詞特征時，CRF模型的特征規(guī)模和訓(xùn)練代價迅速增長。第三種思路是設(shè)計多個較小特征

5、規(guī)模的標(biāo)注器，然后通過投票或錯誤編碼的方式進行綜合。這種思路的缺點是系統(tǒng)結(jié)構(gòu)復(fù)雜，需要大量精細的工作。本文以單字為基本模型符號，通過引入精心設(shè)計的小規(guī)模單字提示特征，特別是機構(gòu)名和地名尾字特征，僅使用少量的字元組和詞性特征，在不影響系統(tǒng)精度的情形下，有效地降低復(fù)雜特征所需的訓(xùn)練代價，縮短了訓(xùn)練時間。然后，通過引入任務(wù)相關(guān)的人工知識，壓縮CRF模型動態(tài)規(guī)劃解碼過程中的搜索空間，降低節(jié)點勢函數(shù)計算量的格生成算法，提高估計和訓(xùn)練的速度。全文布局如下：第二節(jié)介紹基于條件隨機場模型的命名實體識別基本原理。第三節(jié)引入小規(guī)模單字提示特征和啟發(fā)式規(guī)則控制搜索路徑生成策略的CRF快速訓(xùn)練算法。第四節(jié)給出了實驗數(shù)

6、據(jù)，并進行結(jié)果對比和分析。最后為全文總結(jié)，指出將來的研究方向。2基于條件隨機場的命名實體識別下面我們具體分析條件隨機場模型進行序列概率估計、解碼和學(xué)習(xí)算法的時間復(fù)雜度。阿拉伯?dāng)?shù)字和中英文字母，以及100個常見單字姓氏，100個地名尾字和40個機構(gòu)名尾字。每種類型的字組成一個列表，所有列表中的字總量不到400。這些列表形成一個單字提示特征，詳見表1。與大規(guī)模的詞提示列表和名稱列表相比，小規(guī)模單字提示特征規(guī)模小，模型的計算資源需求不高，有利于提高系統(tǒng)的速度。同時單字列表查詢簡單，不存在跨越詞邊界匹配形成錯誤切分的問題。此外，小規(guī)模的列表收集容易。這些單字列表主要來自于對863語料上和少量名稱列表的

7、統(tǒng)計，并經(jīng)過補充相關(guān)形式的數(shù)字和字母得到。3.1.2狀態(tài)表示命名實體識別的任務(wù)是對命名實體識別的邊界確定和類型確定。在CRF模型下，這兩個問題可以綜合考慮。我們的系統(tǒng)中，模型節(jié)點的狀態(tài)對應(yīng)著符號的標(biāo)簽，由兩部分組成，分別為符號所在命名實體的類型標(biāo)簽和符號在命名實體中的位置標(biāo)簽。863任務(wù)有6類命名實體，分別是人名(PER)、地名(LOC)、機構(gòu)名(ORG)、日期表達式(DAT)、時間表達式(TIM)、數(shù)量表達式(NUM)，各對應(yīng)一種類型標(biāo)簽，加上非命名實體標(biāo)簽(OTH)，共7種類型標(biāo)簽。SIGHAN MSRA任務(wù)只識別前三類命名實體(專名)。位置標(biāo)簽則有起始(B)、接續(xù)(I)和非命名實體(O)

8、三種。外部位置標(biāo)簽0與OTH類對應(yīng)，故863任務(wù)共有6×2+1=13種狀態(tài)標(biāo)簽，MSRA任務(wù)共有7種狀態(tài)標(biāo)簽。搜索格(圖1)在符號序列頭部和尾部附加的節(jié)點start和stop可理解為標(biāo)簽OTHER。3.2搜索格生成算法標(biāo)準線性鏈結(jié)構(gòu)CRF中Baum-Welch和Vit-erbi呈格(Trellises)狀展開，如圖1所示。各狀態(tài)變量為一列，列上各節(jié)點為相應(yīng)的狀態(tài)取值，前后相鄰兩列的節(jié)點間有邊相連接。在完全的格中，任意相鄰列問的節(jié)點均有邊相連。在命名實體識別中，格某些鄰接邊是沒有意義的。NER的狀態(tài)值包含兩個方面的信息：實體類型和實體邊界。其潛在的約束為：如果兩狀態(tài)對應(yīng)的實體類型不相同

9、，那么后一狀態(tài)對應(yīng)的邊界類型必須為B(新實體的起始)，而不能為I(原實體的接續(xù))。例如，不能在B-LOC后接I-PER，或者I-PER后接I-LOC，或者OTHER后接I-ORG。但可以在I-PER后接B-LOC，或者在B-LOC后接I-LOC或OTHER。這里，標(biāo)簽OTHER可理解為B-OTH，即每個符號為非命名實體。我們將這一知識施加到格生成過程中，剪除不合理的邊，見圖3中的虛線，形成快速的搜索格。間相比，小規(guī)模特征集減小的訓(xùn)練代價是相當(dāng)可觀的。并且，與POS+TXT+aLIST相比較，其性能不但沒有下降，反而較POS+TXT+aLIST有所上升，增幅達2.5個百分點。 

10、0;  4.3改進的搜索格生成對訓(xùn)練時間的影響我們在SIGHAN命名實體識別語料集上也進行了搜索格生成控制策略前后的對比。前100輪L-BFGS迭代所需時間示于圖6?？梢钥闯?，由于剪除了無效鄰接狀態(tài)組合，壓縮了搜索路徑的空間，格生成改進算法是有效的，可以平均節(jié)約訓(xùn)練時間15.12的時間。未能接近50的原因在于算法中解碼沒有引入復(fù)雜的鄰接狀態(tài)特征，計算量主要集中在狀態(tài)一觀察關(guān)聯(lián)上，這部分的改進由上小節(jié)引入小規(guī)模單字提示特征來完成(我們沒有在SIGHAN上再次進行對比實驗)。4.4基于快速CRF算法的命名實體識別系統(tǒng)最后，我們給出在特征集POS+TXT+sLIST上最終系統(tǒng)的評測結(jié)果以及當(dāng)次評測系統(tǒng)中單項最佳的指標(biāo)，見表2。需要注意的是，2004年度的863中文命名實體識別評測沒有提供訓(xùn)練語料，我們直接將評測語料分割為訓(xùn)練語料和測試語料，兩部分類型相似，因此評測指標(biāo)偏高，難以與當(dāng)次評測報告給出的最佳指標(biāo)做出公正的對比，僅供參考。5結(jié)論與將來的工作本文在條件隨機場框架下進行了兩個方面的工作：(1)我們首次將單字提示特征用于地名和機構(gòu)名中文命名實體識別。通過人工對從訓(xùn)練語料中用字統(tǒng)計結(jié)果的分析，選取了總規(guī)模不到400條的幾類常見用字列表，主要包括地名和機構(gòu)名尾字，顯著改善了大規(guī)模列表收集困難、特征空間大、CRF訓(xùn)練資源消耗大、運行時間長的困