海量法律文書中基于CNN的實體關系抽取技術

高 丹,彭敦陸,劉 叢

(上海理工大學 光電信息與計算機工程學院,上海 200093)

1 引 言

隨著計算機技術和人工智能科學發展,使得自然語言的計算機處理成為現實.近年來,自然語言處理被廣泛地應用到信息檢索、文本分類、自動文摘、語音自動識別與合成、機器翻譯及人機對話等領域.作為自然語言理解技術中不可缺少的重要環節——文本實體關系抽取技術,更是成為近年來的研究熱點.文本實體關系抽取是指根據自由文本的上下文,自動抽取兩個實體之間的關聯.譬如,法律文書中句子“李良挑釁斗毆,致韓寒休克死亡”表明兩個人物實體“李良”與“韓寒”之間構成了“犯罪”關系.

自1998年MUC*MUC[EB/OL].http://www.itl.nist.gov,2008.會議首次正式提出關系抽取任務以來,實體關系抽取已經被應用到不同的領域.在問答系統或推薦系統中,實體關系抽取會自動將問題、答案以及相關實體進行關聯.譬如,當用戶搜索“姚明”時,系統會快速且準確地返回、推薦“葉莉”(夫婦關系)、“NBA”(雇傭關系).在案由分析系統中,實體關系自動抽取提升了審判人員案由分析的速度,不僅直接關系到當事人的法律關系認定,還有利于法官對適用法律的正確選擇,形成恰當的判決結果.

迄今,眾多國內外研究學者們已經提出了一系列實體關系抽取方法.Zhou JF等人構建抽取中文實體命名及其關系的信息抽取系統,利用MBL算法獲取規則以達到實體關系抽取的目的[5].Zhang Z等人基于SVM分類器以及bootstr- apping思想,提出一種新的提升算法-BootProject,實現對實體關系的半監督抽取[6].Sun L和Han X利用特征向量提煉語法樹,基于核函數提出一種名為FTK(Feature-Enriched Tree Kernel)的實體關系抽取方法[8].針對法律文書的半結構化、實體類型、實體之間關系單一的語言特點,本文利用語法結構相似性構建短語有效子樹,同時采用余弦相似度計算方法來改進核函數,求得短語有效子樹之間的相似性矩陣,然后結合CNN提出一種實現對多對實體之間的關系進行自動抽取的技術——KMCNN.

論文其余部分的組織如下:第2部分介紹實體關系抽取方法相關的前人研究成果;第3部分給出本文用到的術語描述及準備工作;第4部分給出基于KMCNN的實體關系抽取過程;第5部分采用實驗對所提方法進行有效性驗證;第6部分是全文的結論.

2 相關工作

過去幾十年,對實體關系抽取的研究得到了人們的重視,許多實體關系抽取方法已得到廣泛應用.不同模式抽取方法,如基于模式匹配[10]的關系抽取、基于詞典驅動[11]的關系抽取、基于機器學習[5]的關系抽取、基于Ontology[12]的關系抽取方法,在不同程度上推動了實體關系抽取的發展.這些方法的共同之處是將實體關系抽取任務視為分類問題.Hendrickx I等人利用MaxEnt、SVM等分類器,采用特征向量完成SemEval-2010數據集上的實體關系自動抽取任務[13].Liu KB等人開發的中文關系自動抽取系統運用改進的語義序列核函數,結合KNN算法構造分類器對關系類型進行分類標注[14].Banko M等人通過深層解析一個相對較小的語料集,利用貝葉斯分類器進行訓練以實現實體關系的抽取[7].

近幾年來,越來越多的研究者們則將深度學習方法與NLP的分類任務相結合,通過深度學習的自動學習能力,對自然語言進行處理.Liu CY等人利用同義詞字典對輸入詞匯進行編碼,將詞法特征、語義知識集成到神經網絡中,提出一種新的卷積神經網絡挖掘實體關系[2].Liu K等人利用脈沖耦合神經網絡(Pulse Coupled Neural Network,PCNN)的最大池自動學習相關特性,提出一個PCNN與多實例學習相結合的模型[3].Nguyen TH等人利用卷積神經網絡的自動學習能力,通過改變滑動窗的數目,減少對外部工具、資源的依賴,實現實體關系的抽取[4].

無論是傳統的基于特征量及核函數的實體關系抽取方法,還是近年來興起的基于深度學習的實體關系抽取方法,均基于僅包含單對目標實體對語句的特定數據集,提高了對原始數據進行預處理的難度.本文試圖在包含多對實體的語句中完成實體關系抽取的任務,并以大規模法律文書數據中進行實體關系抽取為例進行說明.具體的算法思想如下:利用中文語法結構的局部相似性,構建短語有效子樹挖掘模型,并采用基于改進的核函數來計算子樹之間的相似度.基于此,提出基于CNN算法的多實體關系抽取方法——KMCNN,最后通過實驗來驗證所提算法的有效性.

3 準備工作

本節主要介紹如何對原始文本進行預處理,以適合所提算法的計算要求.在給出下文所需相關術語的基礎上,提出詳細的短語有效子樹挖掘過程,然后采用改進的核函數來計算短語有效子樹相似度.

3.1 術語解釋

實體(Entity):自由文本中具有特殊含義的概念,記為e.

實體關系(Relation):一對實體間具有的聯系,記為R(ei,ej,ri,j),其中(ei,ej)為實體對,ri,j為實體對(ei,ej)之間的關系.

例如,在法律文書的案情描述中:人物實體為施害人、被害人;實體之間的關系則為死亡或重傷等犯罪事實.

表1中給出了下文將要用到的符號及其所表示的含義.

表1 算法中所用到的符號說明Table 1 Explanation of words used in paper

3.2 短語有效子樹挖掘

從中文語法結構出發,短語是句子的主要成分.短語結構樹被視為句子語法結構的可視化,可用于挖掘句子中的隱藏信息.

定義1.短語:由若干個連續的詞序列wi～wi+ns搭配成的獨立語言單位,記為Pi.對于一個給定的詞序列W,將其分割成若干短語集合的過程,記為P={Pi|1in,n為句子的詞組個數}.

例如,對詞序列“李良挑釁斗毆,致韓寒休克死亡”進行短語切割,得到短語集合P={李良,挑釁斗毆,致,韓寒,休克死亡},其中,“挑釁斗毆”等詞即為短語.

定義2.短語有效子樹:給定一棵有序的語法樹T=(V,E,R),其中,V表示節點集合,E表示所有的路徑集合,R是根節點.當T′=(V′,E′,R′)滿足:

圖1 短語有效子樹Fig.1 Effective subtree of phrases

1)V′?V,E′?E;

2)V′包含樹T中R′的所有子孫結點

3)T′中的節點序列由若干Pi構成,且有且僅有兩個NR節點.則T′稱為T的短語有效子樹.如圖1所示,樹b、c為語法樹a的兩棵短語有效子樹.在短語有效子樹的挖掘算法中應用以下規則:

規則1.子樹根節點挖掘規則

語法樹中的每個節點符號均有可能在每一個實例中出現,如圖1中的節點S.若對其進行特征選擇,則多數子樹都會是無效的,以致產生錯誤的結果,因此挖掘子樹根節點(即單項集)時,所有非葉節點的單項均是有效的.

短語庫H為所有短語類型的集合,Type為短語類型,Num為該短語中詞匯的數目.因此,子樹根節點集Trie={ti∈H∩T′.V|1≤i≤n,n為有效子樹個數}

規則2.投影序列片段產生規則

自左至右,先序遍歷語法樹,則節點內容、節點序號信息加入樹序列.以圖1為例,以S為根節點,則該子樹的序列為S1-NR2-VP3-V4-S5-NR6-V7(李某致韓某死亡).

挖掘短語有效子樹的具體過程如下:依次遍歷子樹中的序列,并判斷該序列的節點類型,若節點類型存在于短語庫中,則該節點是一棵短語有效子樹的根節點,獲得以該節點為根節點的所有短語有效子樹全序列.算法1 (圖2)詳細描述了該過程.算法前4行完成數據的初始化,第1行初始化短語有效子樹為空集.第2行利用transfer()函數將語法樹轉換成二叉樹,便于之后的遍歷操作,第3行preOrder()函數前序遍歷該二叉樹,并轉換成投影序列S,第4行length()函數取得序列的長度.5-15行依次遍歷序列,挖掘短語有效子樹.第6行isContain()函數判斷序列節點是否存在于短語庫中,若存在,則跳入7-12行,其中7-9行利用preAppend()函數在該子樹前端節點依次插入序列節點,10-12表示將該子樹的最后節點替換成相對應的子樹.最后,15行根據定義3移除無效短語子樹,并返回.

3.3 基于核函數的相似度計算

目前,通過核函數計算相同子樹的個數是計算兩棵樹的相似度的經典方法.但該方法忽略了子樹結構,隱藏了文本隱含信息,不利于實體關系抽取的準確度.基于此,論文提出改進的核函數,計算兩棵短語有效子樹的相似度.

兩棵短語有效子樹的相似度計算是對節點類型、短語語法結構相似程度的度量,其求解過程的主要步驟就是構建相似矩陣.去掉短語有效子樹的葉子節點,應用余弦相似度計算有效子樹對應節點的相似度:

(1)

其中,向量Ai∈Rd×nw,Bj∈Rd×nw是兩棵子樹的所有節點構成的向量.基于上述計算,當相似度大于某個閾值時,兩個節點近似相同.這樣,就可以得到核函數:

(2)

其中,

(3)

算法2(圖3)詳細的描述了如何求解相似矩陣.算法第1行size()函數計算有效子樹集合的子樹個數.第2行通過zero()函數初始化相似矩陣A為0矩陣,表示子樹兩兩均不相似.3-13行完成相似矩陣的求解,其中第6行根據公式2求解兩棵子樹之間的相似度,若大于ε,則7-9行設置對應的相似矩陣元素為1.最后,13行返回相似矩陣.

圖2 短語有效子樹挖掘算法PSTMiningFig.2 Algorithm of PSTMining

圖3 求解相似矩陣算法SimMatrixFig.3 Algorithm of SimMatrix

4 實體關系抽取技術—KMCNN

通過卷積神經網絡(CNN)的自動學習能力,可以減少構建大規模語料庫的人力耗費,實現多實體關系的自動抽取.在前文文本數據預處理的基礎上,本節將重點討論KMCNN模型.

4.1 相關概念

自然語言處理過程中的主要任務是如何對詞、句子、篇章進行編碼,以便將其作為數值類型的數據輸入到模型中進行計算.

定義4.詞向量(Word Vector):詞序列中的每個“詞”均可表示成一個d維實數向量ei∈Rd,i=1,2,…,n.

定義5.距離向量(Distant Vector):詞ei與兩個實體之間的距離向量,記為disti={(disti1,disti2),i=1,2,…,n}.即為短語有效子樹節點之間的邊數.

定義6.向量全矩陣(The Full Embedding Matrix):Matrix=[m1,m2,..mn]∈R(d+2)×n,其中,n是詞序列的長度.對于一個給定的詞序列W={w1,w2,…,wn},詞向量vi是第i個詞wi對應的一個由詞向量ei與距離向量disti組成的d+2維實數向量,即mi=[ei,disti].

4.2 基于相似性矩陣求解向量全矩陣集合

傳統的基于CNN的實體關系抽取算法多數是針對單對實體的,而法律文書中包含實體的句子通常包含多對實體,并且語義結構具有相似性.針對這一發現,利用短語有效子樹的相似性矩陣對句子進行切分,并假設:同一短語中出現多個實體、當兩棵短語有效子樹的相似性值大于閾值時兩個短語中的所有實體均為并列關系,即同時成為施害人或被害人.

基于相似矩陣,算法3 (圖4)詳細描述了如何求解KMCNN中的向量全矩陣參數:有效子樹集合與向量全矩陣集合.第1-2行對數據進行初始化,向量全矩陣集合Matrix為空集,其中len參數記錄該集合的長度.核心代碼為3-13行:第4行初始化len為0,表示當前集合中全矩陣數目為0;第6行判斷相似矩陣元素的值,若值為1則跳至第7行,應用Word2Vec[15]將短語有效子樹的序列化數據轉換成詞向量;然后,第8行dist()函數求解相對應的距離矩陣;第10行更新向量全矩陣集合,即append()函數將向量權矩陣在添加至集合中,同時設置集合長度加1.最后,14行返回結果.

4.3 KMCNN

前文介紹了如何挖掘短語有效子樹,并基于改進的核函數對相似性矩陣進行計算,求得向量全矩陣.下面介紹基于KMCNN來實現實體關系抽取的過程.圖5給出了KMCNN的偽代碼:代碼第1行將實體關系集初始化為空集,并設索引值為0.第2-11行遍歷向量全矩陣集合,依次抽取實體對之間的關系.其中,3-10行完成指定集合的實體關系抽取:首先,第4行基于分詞、詞性標注等知識,應用reconge()函數對實體進行識別;然后,判斷實例是否為集合中的第一個元素,若是,則跳至第6行,基于CNN算法對實體關系進行抽取;最后,第12行返回實體關系集合.

圖5 KMCNN方法Fig.5 Approach of KMCNN

圖6 CNN算法結構圖Fig.6 Structure of convolutional neural network

如圖6所示,CNN算法包含四個主要部分:全向量映射、卷積層、池化層以及全鏈接層.其中,全向量映射是根據定義7求解全向量矩陣的過程.在卷積層,若滑動窗口數目為win,則卷積核的權重集合是:

f={f1,f2,…,fwin|fi∈R(d+2)×n}

(4)

基于公式(4),給出卷積值的計算公式:

(5)

其中,b為偏置值,g是一個非線性函數.然后,在池化層運用最大池化原理提取最大卷積值,即pmax=max(C).最后,在全連接層采用sigmod函數實現實體關系的抽取.

5 實驗分析

5.1 數據來源

實驗部分的數據采集于2016年某省刑事案件的法律文書2*China Judgements Online.http://wenshu.court.gov.cn,2016.,共25,463份文本數據.裁定書的內容主要包含以下五部分:被告人信息;以時間為序,開庭判決過程;復核事實;證據陳述;判決結果.因此,可將裁判文書視為有模板的半結構化數據,利用正則表達式匹配全文信息來提取關鍵段落(即被告人信息、復核事實等),并進行數據預處理過程(去除噪聲數據、重復數據、提取包含實體對的句子).

5.2 算法有效性分析

準確率(Precision)、召回率(Recall)和F1-measure是評估算法有效性的基本標準.因此,實驗采用三個指標對所提算法進行綜合性評估.下面,給出三個指標的數學定義:

(6)

(7)

(8)

Nc是某類別中被正確分類的實例數目,Nic是某類別中被錯誤分類的實例數目,Nsum是某類別中的實例總數.

圖7 不同相似度閾值下的實體關系抽取結果Fig.7 Relation extraction in KMCNN vs.similarity

圖8 不同滑動窗口數目下的實體關系抽取結果Fig.8 Relation extraction in KMCNN vs.slide window number

第1組.在真實數據集上實現實體關系的抽取

實驗1考察了在不同相似度閾值下,KMCNN的實體關系的抽取效果.KMCNN需要提供相似度閾值ε確定短語有效子樹之間的相似性矩陣.實驗中發現不同的ε取值,對于最終的實體關系抽取結果有很大的影響.圖7是實驗結果,橫軸表示相似度閾值,縱軸表示三個指標的值.從圖中可以看出,當ε從0.75到0.87變化時,三個指標值上升很快,表明實體關系抽取效果越來越好.而當ε大于0.87后,三個指標值趨于平穩,即實體關系抽取效果趨于穩定.

實驗2考察不同滑動窗口數目下,KMCNN的實體關系的抽取效果.實驗中滑動窗口的數目包含兩種:固定滑動窗口大小,取值分別是2、3、4、5;組合滑動窗口大小,組合取值分別是(2,3,4,5)、(3,4,5)、(4,5).圖8中顯示了滑動窗口數目對實體關系抽取結果的影響:(1)滑動窗口數目固定時,KMCNN的抽取效果不穩定.滑動窗口大小為3時,準確率較高;滑動窗口大小為2、5時,召回效果較好.(2)組合滑動窗口大小的取值時,KMCNN的抽取效果穩定并呈現較好的趨勢.特別地,滑動窗口組合大小(4,5)時,抽取結果具有很高的準確率,且召回效果良好.

第2組.考查KMCNN計算性能

在確定了相似度閾值和滑動窗口數目的基礎上,本組實驗將驗證相似性取值為0.87、滑動窗口數目為(4,5)時,使用所提算法進行實體關系抽取的計算效果.本文從兩個方面對KMCNN與O-CNN[1]、W-ONN[4]、MVRNN[8]等現有算法的實體關系抽取結果進行考察:

實驗3考察KMCNN的運行效率.圖9中顯示了四種算法在不同數據集規模的情況下,抽取實體關系所需要的運行時間.在數據集規模小于10,000時,相對于其余三種算法,KMCNN在較短的時間內完成實體關系的抽取.隨著數據規模的增加,四個算法的運行時間的差距增大.這是因為隨著數據集規模的增加,挖掘短語有效子樹的時間明顯減少,意味著KMCNN算法的計算規模也明顯減少.

圖9 不同數據集規模下算法的運行時間比較Fig.9 Different algorithms runtime vs.data set

實驗4驗證KMCNN的實體關系抽取結果的準確性.圖10中顯示了4個算法在不同的數據集規模(分別選取5000,10000,15000,20000篇法律文書)下得到的實體關系抽取結果的三個指標值.文獻[1,4,8]顯示,O-CNN、W-ONN、MVRNN三種算法都能夠較好地抽取實體之間的關系,而KMCNN的實體關系抽取結果與W-CNN的實體抽取結果近乎相同,且明顯優于O-CNN、MVRNN的實體關系抽取結果.由此可見KMCNN能夠較好地抽取實體之間的關系.

6 結 論

實體關系抽取是自然語言處理的重要任務.快速而準確地抽取實體間的關系,對自由文本信息挖掘、主題挖掘、問答系統、推薦系統均具有重要意義.本文提出一種基于改進核函數和CNN的多實體關系抽取技術—KMCNN.算法利用語法結構相似性挖掘短語有效子樹,通過余弦相似度計算來改進核函數,并利用該核函數計算關系實例間的相似度,結合CNN算法對實體關系進行抽取.算法合理運用了語法結構,結合CNN算法的自動訓練能力,不需要大規模語料庫為基礎,較大地減少了中間特征向量的計算量同時挖掘了句、篇中隱含的有效信息.實驗結果表明,KMCNN具有較好的實體關系抽取效果,在效率方面也有較大提高.下一步工作將圍繞如何進一步提高算法效率、構建實體關系圖譜及采用MapReduce進行分布式計算等問題展開研究.

圖10 不同數據集規模下的實體關系抽取結果比較Fig.10 Relation extraction in different algorithms vs.data set

：

[1] Zeng D,Liu K,Lai S,et al.Relation classification via convolutional deep neural network [J].In Proceedings of COLING,the 25th International Conference on Computational Linguistics,2014:2335-2344.

[2] Liu C Y,Sun W B,Chao W H,et al.Convolutionneural network for relation extraction [M].Advanced Data Mining and Applications,2013:231-242.

[3] Zeng D,Liu K,Chen Y,et al.Distant supervision for relation extraction via piecewise convolutional neural net works [C].Conference on Empirical Methods in Natural Language Processing,2015:1753-1762.

[4] Nguyen T H,Grishman R.Relation extraction:perspective from convolutional neural networks [C].The Workshop on Vector Space Modeling for Natural Language Processing,2015:39-48.

[5] Zhang Y,Zhou J F.A trainable method for extracting Chinese entity names and their relations [C].The Workshop on Chinese Language Processing:Held in Conjunction with the,Meeting of the Association for Computational Linguistics,Association for Computational Linguistics,2000:66-72.

[6] Zhang Z.Weakly-supervised relation classification for information extraction [C].ACM CIKM International Conference on Information and Knowledge Management,Washington,Dc,Usa,November,DBLP,2004:581-588.

[7] Banko M,Cafarella M J,Soderland S,et al.Open information extraction from the web [C].International Joint Conference on Artifical Intelligence,Morgan Kaufmann Publishers Inc,2007:2670-2676.

[8] Sun L,Han X.A feature-enriched tree kernel for relation extraction [C].Meeting of the Association for Computational Linguistics,2014:61-67.

[9] Socher R,Huval B,Manning C D,et al.Semantic compositionality through recursive matrix-vector spaces [C].Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning,2012:1201-1211.

[10] Appelt D E,Hobbs Jr,Bear J,et al.SRI international FASTUS system:MUC-6 test results and analysis [C].In Proceedings of the 6th Message Understanding Conference(MUC-6),1995:237-248.

[11] Aone C, Ramos Santacruz M.REES: a large-scale relation and event extraction systems[C].In Proceedings of the 6th Applied Natural Language Processing Conference, New York,2000:76-83.

[12] Iria J.T-Rex:a flexible relation extraction framework [C].In Proceedings of the 8th Annual Colloquium for the UK Special Interest Group for Computational Linguistics,2005.

[13] Hendrickx I,Kim S N,Kozareva Z,et al.SemEval-2010 task 8:multi-way classification of semantic relations between pairs of nominals [C].The Workshop on Semantic Evaluations:Recent Achievements and Future Directions，Association for Computational Linguistics,2009:94-99.

[14] Liu Ke-bin,Li Fang,Liu Lei,et al.Implementation of a kernel-based Chinese relation extraction system [J].Journal of Computer Research and Development,2007,44(8):1406-1411.

[15] Mikolov T,Chen K,Corrado G,et al.Efficient estimation of word representations in vector space [J].Computer Science,2013.

附中文參考文獻：

[14] 劉克彬,李 芳,劉 磊,等.基于核函數中文關系自動抽取系統的實現 [J].計算機研究與發展,2007,44(8):1406-1411.