許麗丹， 劉嘉勇， 何 祥

(1.四川大學網絡空間安全學院， 成都 610065; 2.四川大學電子信息學院， 成都 610065)

1 引 言

命名實體識別是自然語言處理領域中一項重要任務，經過幾十年的研究發(fā)展已取得了顯著成果[1-5].但是目前已有的研究較少關注命名實體識別數(shù)據(jù)集數(shù)據(jù)類別標記不平衡這類數(shù)據(jù)分布問題[6].數(shù)據(jù)類別標記不平衡[7]是指一個類別的數(shù)據(jù)量與屬于另一類別的數(shù)據(jù)量差距較大,且小樣本量類呈現(xiàn)出的信息更具價值.數(shù)據(jù)類別標記不平衡會影響統(tǒng)計學習模型的效果，導致模型更關注多數(shù)類別數(shù)據(jù)，忽略少數(shù)類別數(shù)據(jù)[7-16].在分類問題中解決數(shù)據(jù)類別標記不平衡的方法主要有以下三類: (1) 采樣方法，包括欠采樣和過采樣方法[7]；(2) 改進統(tǒng)計學習算法，包括one-class學習方法[8]，修改算法的代價[9]以及集成學習[10]；(3) 特征選擇，通過收集最佳特征子集[11]以實現(xiàn)最佳性能.

針對序列數(shù)據(jù)，Tomanek等人通過主動學習，在數(shù)據(jù)標記階段盡可能平衡地標記數(shù)據(jù)[12].Douzas等人使用條件對抗生成模型為少數(shù)類別數(shù)據(jù)生成更多數(shù)據(jù)以緩解數(shù)據(jù)失衡[13]，但這種方法模型復雜、計算代價大.Gliozzo假設頻繁出現(xiàn)的單詞一般不提供文本具體信息，也不會是實體.可以過濾掉這些詞以減小非實體類單詞與實體類單詞比值[14].Maragoudakis等人使用Tomek連接法在訓練階段減少訓練集中不必要的負面樣本[15].Akkasi等人[6]提出了平衡欠采樣方法，該方法保留句子邏輯短語結構以及句子間相關性，并在四個生物醫(yī)學數(shù)據(jù)集上分別實驗比較隨機欠采樣、SWF[14]和平衡欠采樣三種欠采樣方法的效果并證明了調節(jié)數(shù)據(jù)集中實體類單詞和實體類單詞比例可以改善模型效果.然而這種方法直接剔除數(shù)據(jù)集中非實體單詞或語句，可能破壞文本的短語結構，丟失有價值的數(shù)據(jù).

針對已有方法可能造成的信息丟失問題，本文通過改造遺傳算法[17]用于序列文本合成，提出了一種基于遺傳算法的數(shù)據(jù)類別標記平衡方法，本文簡稱CBM-GA(class balance method based on genetic algorithm).該方法保留所有原始語料，利用遺傳算法基因重組、繁衍行為特點，充分挖掘類別平衡文本特征，盡可能維持語句中實體短語結構的同時，合成新文本以擴充原始數(shù)據(jù)集.實驗表明，本文提出的方法有效緩解數(shù)據(jù)集類別標記不平衡問題，提高命名實體識別任務性能.

2.1 類別平衡方法框架

本文提出的數(shù)據(jù)類別平衡方法CBM-GA框架如圖1所示，首先對原始數(shù)據(jù)集進行篩選，獲得合適的父代樣本集，通過適應度函數(shù)評估樣本并按照其適應度函數(shù)值排序獲得有序父代樣本集.從有序父代樣本集中隨機選擇樣本形成父代樣本對，經過交叉和變異操作生成新樣本，再次使用適應度函數(shù)評估新樣本，抽取適應度函數(shù)值高的新樣本集合更新下一輪文本合成操作所需的父代樣本集，如此循環(huán)N次.最后將第N輪生成新樣本數(shù)據(jù)集和原始數(shù)據(jù)集合并產生擴充數(shù)據(jù)集，用于命名實體識別.

圖1 CBM-GA框架圖Fig.1 Method framework

2.2 類別平衡方法原理

2.2.1 數(shù)據(jù)篩選 現(xiàn)有用于命名實體識別研究的公開數(shù)據(jù)集中實體單詞個數(shù)遠小于非實體單詞個數(shù)，且包含大量無實體單詞、類別嚴重失衡的語句[6].直接使用這樣的數(shù)據(jù)集進行文本合成會增加后續(xù)操作代價，降低文本合成效果.因此需要進行文本篩選，初步獲取類別分布相對平衡的文本集合作為父代樣本集.

如何評估文本類別標記平衡的程度是首先需要解決的問題，Akkasi等人[6]用非實體單詞個數(shù)和實體單詞個數(shù)比值來評估文本類別標記平衡性，如式(1)所示.

(1)

式(1)中，WO表示語句中非實體單詞個數(shù);分母WE表示語句實體單詞個數(shù).本文將R值作為文本平衡性的衡量指標，R值越大文本類別越不平衡.

統(tǒng)計分析常用數(shù)據(jù)集CoNLL2003[18]、JNLPBA[19]中語句的非實體單詞個數(shù)與實體單詞個數(shù)比值R和語句單詞總數(shù)的關系，我們可以得出以下結論：文本單詞個數(shù)越多，R值越大，文本類別越不平衡，兩者近似反比例關系，如圖2所示.

圖2 兩個常用數(shù)據(jù)集文本R值與文本單詞個數(shù)關系圖

Fig.2 Relationship between the textRvalue of two common datasets and the number of text words

圖2中橫軸表示語句的單詞總數(shù)，縱軸表示語句中非實體單詞個數(shù)與實體單詞個數(shù)的比值.實線、虛線分別表示JNLPBA、CoNLL2003數(shù)據(jù)集的文本R值與文本長度的關系，二者整體呈上升趨勢.當文本單詞個數(shù)超過60，文本的R值波動幅度變大；當文本單詞個數(shù)超過100，JNLPBA數(shù)據(jù)集的R值均處于劇烈波動狀態(tài)，CoNLL2003數(shù)據(jù)集R值快速增長，表明此時文本類別較不平衡，使用這樣的數(shù)據(jù)進行后續(xù)操作將不利于合成類別均衡的新文本.

因此，為了減少后續(xù)文本合成操作的計算代價，提高合成效率，數(shù)據(jù)篩選過程中需要剔除類別嚴重失衡的數(shù)據(jù).結合上述分析，數(shù)據(jù)篩選具體流程如下.

(1) 計算每個語句中實體單詞個數(shù)，剔除不含實體單詞的語句；

(2) 剔除單詞個數(shù)超過100的語句.

2.2.2 適應度評估 適應度函數(shù)，在遺傳算法中用以評估給定解決方案與所需問題最佳解決方案的接近程度[17].CBM-GA方法使用適應度函數(shù)作為評估指標以評估樣本的平衡性，并將類別標記平衡條件引入適應度函數(shù)中，使得算法尋優(yōu)過程中嘗試構造類別分布平衡的新樣本.定義適應度函數(shù)f如式(2)所示.

f=sigmoid(Rs-R)+λ×sigmoid(R-Rr)

(2)

式(2)中，R為式(1)定義的語句非實體單詞和實體單詞的比值；Rs是合成文本R值上限值；Rr是合成文本R值下限值；λ是Rr權重系數(shù).式(2)借助sigmoid函數(shù)控制合成樣本的R值在[Rr,Rs]范圍內.

由圖2分析可知文本單詞個數(shù)不應過長，因此向適應度函數(shù)中添加單詞個數(shù)小于100的限制，如式(3)所示.

(3)

式(3)中，L表示語句單詞個數(shù)限制函數(shù)；l表示當前樣本單詞個數(shù).relu函數(shù)限制合成文本的長度.適應度函數(shù)引入單詞個數(shù)限制，如式(4)所示.

f=sigmoid(Rs-R)+λ×sigmoid(R-Rr)+

(4)

式(4)中，μ是L的權重系數(shù)，用以控制類別平衡條件和單詞個數(shù)限制的重要性差異.

2.2.3 文本合成 CBM-GA方法文本合成過程主要是通過一系列選擇、交叉和變異操作合成數(shù)據(jù)標記平衡的數(shù)據(jù).其中，選擇操作從有序父代樣本集合中抽取父代樣本構建父代樣本對集合；交叉操作將父代樣本對進行組合以生成新樣本；變異操作調整新樣本的單詞順序，向樣本中添加更多隨機性.

CBM-GA方法將文本視為染色體，將單詞及其實體標記類型視為染色體上的基因.如圖3所示.每個框內上行表示單詞，下行表示對應實體類型標記[17]，二者共同構成一個完整的基因.基因構成染色體，又稱之為樣本.將數(shù)據(jù)集中每個文本視為樣本，數(shù)據(jù)集視為樣本群體.

為了便于后續(xù)分析，定義樣本染色體x=(x1,x2,…,xn)，其中，xi是包含單詞及其對應實體類型標記的基因，n是染色體長度.

1) 選擇操作

在選擇步驟中，遍歷有序父代樣本集并按照比例選擇方法[20]隨機選擇兩個父代樣本構成父代樣本對，從而構成父代樣本對集合.

圖3 染色體示意圖
Fig.3 Chromosome schematic diagram

圖4 交叉過程示意圖Fig.4 Crossover schematic diagram

2) 交叉操作

在交叉階段，對父代樣本對集合中每個父代樣本對采用隨機交叉策略進行單詞序列相互交換，以產生新樣本，如圖4所示.

為避免實體短語被切分而導致命名實體模糊、歧義等問題，CBM-GA方法修改基因組合規(guī)則，限制單詞交換位置僅為開始，結尾以及O標記[18]的非實體單詞位置以確保實體單詞結構完整交換.因此首先根據(jù)父樣本1的實體標記類型，構建交換位置集合l.并隨機從l中抽取交叉發(fā)生的開始、結束位置以得到單詞序列如圖中黑色框單詞序列，將其與父樣本2合并生成新樣本x′.

x′=x1[lstart:lend]+x2

(6)

式(6)中，x1表示父樣本1;x2表示父樣本2;lstart、lend分別表示從交換位置集合l隨機抽取的開始、結束位置;x′表示新樣本.

3) 變異操作

本文采用隨機交換單詞位置的方式實現(xiàn)變異.具體操作為：設定一個變異概率α，對交叉得到的新樣本x′，隨機產生一個[0,1]區(qū)間上的隨機數(shù)r，如果r<α，則隨機交換新樣本x′兩個單詞的位置.最終生成樣本如式(7)所示.

(7)

式(7)表明當r<α時，隨機選定兩個單詞位置i、k，交換x′中兩個位置的單詞從而實現(xiàn)變異操作，反之則不進行變異.

綜上分析，CBM-GA方法完整表述如算法1.

算法1 CBM-GA方法

輸入原始訓練樣本集合S;參數(shù)Rs、Rr、λ、μ、循環(huán)次數(shù)N、變異概率α、合成樣本集合大小La

輸出擴展的新樣本集合A

Begin

初始化迭代次數(shù)n:n=0

(1) 遍歷原始訓練樣本S，過濾不含實體單詞及文本單詞個數(shù)超過100的語句，獲得父代樣本集D;

(2) 遍歷父代樣本集D，根據(jù)式(4)計算每個語句的適應值并排序，得到有序父代樣本集D1;

(3) 使用比例選擇法隨機從D1中抽取兩個父代樣本組成的父代樣本對集合;

(4) 遍歷父代樣本對集合:

(a) 針對父代樣本對(p1,p2)，分別從p1、p2樣本的開始、結尾及非實體單詞的位置集合中隨機選擇位置變量以截取單詞序列;

(b) 將單詞序列合并成新樣本T;

(c) 以概率α交換T中任意兩個位置的單詞，并將T加入新樣本集合G;

(5) 遍歷G，根據(jù)式(4)計算每個新語句的適應值.抽取適應值最高的La個樣本的集合替換D1、G，迭代次數(shù)n加1;

(6) 如果n

End

為了驗證CBM-GA方法的有效性，排除單一數(shù)據(jù)集影響，實驗采用命名實體識別研究中常用數(shù)據(jù)集CoNLL2003[18]和JNLPBA[19]進行實驗.數(shù)據(jù)集基本統(tǒng)計信息如表1所示.

表1 數(shù)據(jù)集統(tǒng)計信息表

如表1所示， CoNLL 2003已分配好訓練集、驗證集和測試集；JNLPBA僅劃分了訓練集和測試集.本文從JNLPBA中隨機抽取1/3數(shù)據(jù)作為驗證集.

本文實驗平臺為ubuntu16.04系統(tǒng)服務器，GPU為GeForce GTX 1070，顯存8 G.實驗模型使用tensorflow框架構建.

3.2 實驗評價指標

Akkasi等人提出平衡欠采樣方法以緩解數(shù)據(jù)集的類別失衡問題，從而改善命名實體識別的效果，其借助命名實體識別評價指標作為最終的方法有效性衡量指標[6].本文沿用該評價指標來論證CBM-GA方法的有效性.命名實體識別一般采用精準率(prec)、召回率(recall)和F1值作為模型性能評估指標[1-5].本文使用的模型評價指標定義如下.

(8)

(9)

(10)

3.3 實驗參數(shù)設置與尋優(yōu)

根據(jù)2.2節(jié)定義，CBM-GA方法實現(xiàn)過程涉及參數(shù)：合成樣本R值上限Rs，合成樣本R值下限Rr，Rr值權重λ，L的權重系數(shù)μ，合成樣本集合大小La，變異概率α以及循環(huán)次數(shù)N.

根據(jù)Whitley等人的經驗[17]，本文實驗將α設為0.01.為給其它參數(shù)設置合理的取值，實驗基于Bi-LSTM-CRF模型[2]使用貝葉斯優(yōu)化[16]尋優(yōu)方法來設置參數(shù).具體操作如下.

1) 分別以1為步長，設置Rs,Rr的取值范圍為[0,30]；以500為步長，設置La的取值范圍為[500,2000]；以0.1為步長，設置λ取值范圍為[0,1]；以1為步長，設置循環(huán)次數(shù)N取值范圍為[1,10]，構建參數(shù)集合；

2) 基于Bi-LSTM-CRF模型使用貝葉斯優(yōu)化尋優(yōu)方法以F1值為指標，對參數(shù)集合進行尋優(yōu).選取驗證集實驗結果中F1值最大的參數(shù)作為后續(xù)實驗參數(shù).

圖5 參數(shù)Rs選擇實驗結果Fig.5 Results of Rs selection

以CoNLL 2003數(shù)據(jù)集的Rs參數(shù)選取為例，以1為步長，設置Rs取值區(qū)間為[0,30]，繪制不同Rs對應F1值分布圖，如圖5所示.

根據(jù)圖5可知，當Rs為15時，合成的數(shù)據(jù)集進行命名實體識別F1值最高，因此選定Rs=15.由此思路選擇其他參數(shù)，最終參數(shù)取值如表2所示.

表2 數(shù)據(jù)集參數(shù)表

3.4 實驗測試結果

實驗使用Bi-LSTM-CRF模型作為基準模型.為了驗證CBM-GA方法的有效性和優(yōu)異性，分別設計了2組對比實驗.且為了避免偶然因素影響，實驗結果均為5次重復實驗結果.具體如下.

為了驗證CBM-GA方法的有效性，設計基準模型和CBM-GA方法對比實驗.

1) 基準實驗：使用基準模型分別對CoNLL2003、JNLPBA建模；

2) CBM-GA方法實驗：使用基準模型分別對CBM-GA方法作用后的兩數(shù)據(jù)集建模；

針對CoNLL 2003數(shù)據(jù)集的實驗結果如表3所示，CBM-GA方法相比基準模型在保持精確率幾乎不變的情況下，召回率提升3.26%，F(xiàn)1值提高1.70%；針對JNLPBA數(shù)據(jù)集的實驗結果如表4所示，CBM-GA方法雖然造成精確率的小幅下降，但其召回率提高了2.44%,最終F1值增加了1.03%.

為了驗證CBM-GA方法表現(xiàn)優(yōu)于已有平衡欠采樣、隨機過采樣方法，設計以下對比實驗.

1) 隨機過采樣方法實驗：使用隨機過采樣方法擴充原始CoNLL 2003、JNLPBA，獲取與CBM-GA方法相同規(guī)模的擴充數(shù)據(jù)集，并使用基準模型其建模；

2) 平衡欠采樣方法實驗.使用平衡欠采樣方法處理原始兩數(shù)據(jù)集獲得新樣本集合，并隨機采樣新樣本集合擴充原始數(shù)據(jù)集以獲取與CBM-GA方法相同規(guī)模的擴充數(shù)據(jù)集，使用基準模型其建模；

優(yōu)異性驗證實驗結果如表5和表6所示，針對CoNLL 2003數(shù)據(jù)集，CBM-GA方法召回率比平衡欠采樣高2.98%，比隨機過采樣方法高3.29%，F(xiàn)1值均超出1.76%以上；針對JNLPBA，CBM-GA方法召回率比平衡欠采樣高1.78%，比隨機過采樣方法高2.25%，F(xiàn)1值均超出0.97%以上.

綜上實驗分析驗證了CBM-GA方法可以有效提高模型召回率，改善命名實體識別效果，相比已有方法表現(xiàn)更優(yōu)異.

表3 CoNLL 2003數(shù)據(jù)集上有效性驗證結果

表4 JNLPBA數(shù)據(jù)集上有效性驗證結果

表5 CoNLL 2003數(shù)據(jù)集上優(yōu)異性驗證結果

表6 JNLPBA數(shù)據(jù)集上優(yōu)異性驗證結果

3.5 結果分析

進一步分析實驗結果，以CoNLL 2003數(shù)據(jù)集為例，繪制基準、CBM-GA實驗接收者操作特征曲線(receiver operating characteristic curve，ROC)[21]如圖6所示.

圖6 ROC曲線Fig.6 ROC of baseline and CBM-GA

分別計算兩條ROC曲線對應AUC[22]值如表7所示.

表7 AUC值

圖6和表7更一步證明CBM-GA模型通過緩解實體類和非實體類單詞個數(shù)的不平衡問題，有效地改善了命名實體識別的效果.

從時間代價分析，CBM-GA算法增廣CoNLL 2003數(shù)據(jù)集需2.42 min，增廣JNLPBA數(shù)據(jù)集訓練需2.4 min，相比Bi-LSTM-CRF模型訓練每epoch需32 s，50個epoch需要26.7 min,CBM-GA算法的運行成本是可以接受的.數(shù)據(jù)類別標記失衡是普遍存在于開源數(shù)據(jù)集的問題，但目前關于命名實體識別任務上的數(shù)據(jù)標記失衡研究較少.本文針對這一現(xiàn)狀創(chuàng)新性地改造遺傳算法，提出了保持文本實體短語結構的CBM-GA方法.實驗結果表明，CBM-GA方法在文本數(shù)據(jù)預處理階段有效緩解數(shù)據(jù)集類別標記失衡問題，改善模型召回率并進一步提高命名實體識別性能.該方法可以應用在其它序列標注任務上如分詞、機器翻譯等中.