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

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

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

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

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

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

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

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

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

9、，那么后一狀態(tài)對(duì)應(yīng)的邊界類型必須為B(新實(shí)體的起始)，而不能為I(原實(shí)體的接續(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，即每個(gè)符號(hào)為非命名實(shí)體。我們將這一知識(shí)施加到格生成過(guò)程中，剪除不合理的邊，見(jiàn)圖3中的虛線，形成快速的搜索格。間相比，小規(guī)模特征集減小的訓(xùn)練代價(jià)是相當(dāng)可觀的。并且，與POS+TXT+aLIST相比較，其性能不但沒(méi)有下降，反而較POS+TXT+aLIST有所上升，增幅達(dá)2.5個(gè)百分點(diǎn)。 

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