劉麗佳，郭劍毅，周蘭江，余正濤，邵 發(fā)，張金鵬

(1. 昆明理工大學 信息工程與自動化學院，云南 昆明 650500；2. 昆明理工大學 智能信息處理重點實驗室，云南 昆明 650500)

1 引言

領域概念實體屬性關系(包括實例與屬性、實例與屬性值、屬性與屬性值之間的對應關系)是信息檢索、社會關系構建、領域本體及知識圖譜構建的重要基礎。目前國內(nèi)外的研究主要集中在實例及屬性的提取，或?qū)傩院蛯傩灾祵Φ奶崛?。例如，David Sánchez[1]提出一種以Web為檢索語料庫的自動的、無監(jiān)督和領域無關的方法對Web文本中的領域?qū)嵗蛯傩宰隽颂崛?，解決了數(shù)據(jù)稀疏的問題，在準確率和召回率方面均有所提高；S.Ravi[2]利用弱指導的方法從Web文檔中提取屬性，不僅提高了屬性提取的精度，還可以自動對提取的屬性子集進行標識；李文杰[3]利用實例和屬性并列結構模式去網(wǎng)頁集合中提取同類詞語集合，然后再用基于種子的弱指導方法去學習實例和屬性共現(xiàn)的上下文模式，最后再通過模式去提取候選實例或候選屬性，在進行提取時融入了并列結構這樣一種特征，能大大提高系統(tǒng)的召回率；唐偉[4]提出了一種基于網(wǎng)頁標題和網(wǎng)頁結構信息的關系模版自動構建方法，從而實現(xiàn)商品的“屬性—值”關系的自動提取，該方法在結構化網(wǎng)頁的信息抽取中取得了不錯的效果。但是，領域概念的實例、屬性和屬性值間對應關系不止包括屬性—屬性值關系，還包括實例—屬性關系，實例—屬性值關系等等，從完備性角度，只有將這些關系都抽取出來，才能真正滿足信息檢索、知識圖譜構建的實際應用需求。目前關于實例、屬性和屬性值間的關系抽取主要是在結構化或半結構化文本中進行的，例如，程顯毅[5]利用半監(jiān)督機器學習框架對<實體，屬性，值>之間的關系進行抽取，提取過程中利用了Wikipedia的結構化特征和凝聚型層次聚類算法，動態(tài)的確定關系類別，完成關系聚類，提高了關系識別系統(tǒng)的性能；楊宇飛[6]提出基于弱監(jiān)督的屬性(實例，屬性名稱和屬性值)關系三元組自動抽取方法，利用中文百科條目信息模版中的半結構化屬性關系回標條目文本自動獲取訓練語料，然后利用句子分類器對語料進行訓練優(yōu)化，并在關系抽取過程中加入了觸發(fā)詞詞典的特征，提高了關系抽取的召回率，但是只將條目信息作為屬性具有一定的局限性。

與Wikipedia、百科條目信息模版中已有的結構化、半結構化文本相比，自由文本的句法表達具有多樣性，其中的實例—屬性、屬性—屬性值、實例—屬性值等各類關系的模式更復雜，抽取難度更大。目前常用的方法是用支持向量機(SVM)先對實例、屬性和屬性值等命名實體進行關系判別，把有關系的實體對抽取出來，再制定相應的推理規(guī)則，對實體對的具體關系類別進行判別，由于推理規(guī)則是人為定義的，不能涵蓋所有關系類別的模式，在準確率方面不能有所保證。

為了解決上述問題，提高關系抽取的性能，本文先對自由文本中的實例、屬性和屬性值進行命名實體識別，然后嘗試利用BP神經(jīng)網(wǎng)絡的方法進行實例—屬性、屬性—屬性值和實例—屬性值關系的識別與抽取。BP神經(jīng)網(wǎng)絡是一種前饋反向型網(wǎng)絡，其傳統(tǒng)算法具有實現(xiàn)復雜的非線性映射的能力、自主學習能力強和可反饋訓練等特點，在模式識別、文本分類、圖像分類等方面具有廣泛應用。但是，傳統(tǒng)的BP神經(jīng)網(wǎng)絡算法存在容易陷入局部極小值、收斂速度慢等缺點，為此人們提出了多種改進方案，主要有啟發(fā)式算法和數(shù)值優(yōu)化算法[7]。本文選擇優(yōu)化算法中的LM算法(Levenberg-Marquardt)對各類關系進行識別和抽取。該方法的主要思想是： 先對語料進行預處理(分詞、詞性標注、句子劃分、人工標注、命名實體識別等)，然后根據(jù)預處理的結果枚舉找出所有的關系實例(實例—屬性關系、屬性—屬性值關系、實例—屬性值關系)，并根據(jù)領域特點選取實體上下文、類別、位置等體現(xiàn)各類關系的特征構成關系特征集。各類關系的特征作為神經(jīng)網(wǎng)絡的輸入樣本集，利用LM算法對神經(jīng)網(wǎng)絡的權值和閾值進行調(diào)整，然后用實體關系的類別作為分類結果，構造關系分類器。通過多組實驗證明，本文提出的方法對自由文本中的實例—屬性關系、屬性—屬性值關系、實例—屬性值關系等的識別與抽取具有良好的性能。

2 LM算法介紹

LM算法[8-10](Levenberg-Marquardt)是梯度下降法和高斯-牛頓法相結合的一種算法，因此，它既有梯度下降法的全局特性，又有高斯-牛頓法的局部收斂特性，在局部搜索能力上高于傳統(tǒng)的BP神經(jīng)網(wǎng)絡算法。并且，LM算法利用了近似的二階導數(shù)信息，比梯度下降法的收斂速度快，比較穩(wěn)定，其性能優(yōu)于傳統(tǒng)BP神經(jīng)網(wǎng)絡算法，目前在模式識別、信號處理和圖像分類等領域的應用均取得較好效果。LM算法簡要描述如下。

設xk代表第k次迭代的神經(jīng)網(wǎng)絡權值和閾值的輸出向量，xk+1代表新的權值和閾值的輸出向量為式(1)。

對于牛頓法則如式(2)所示。

設誤差指標函數(shù)E(x)為式(3)。

其中，ei(x)為輸出層的誤差，i=1,2,…,N,yi為輸出層的實際輸出，oi為輸出層的期望輸出。

則如式(4)～(5)所示。

其中，J(x)為Jacobian矩陣，具體表達式為式(6)～(7)。

高斯-牛頓法的權值改變公式為式(8)。

LM算法的權值改變公式為式(9)。

其中，μ>0為常數(shù)，是自適應調(diào)整參數(shù)，I為單位矩陣。

由上述公式可得，LM算法的權值調(diào)整公式為式(10)。

3 關系抽取過程

LM算法對給定的各類關系進行識別與抽取的流程如圖1所示。

圖1 LM算法訓練關系分類器流程圖

下面以旅游領域自由文本中的實例—屬性值關系抽取流程為例，介紹利用BP神經(jīng)網(wǎng)絡的LM算法進行關系識別與抽取的原理。

3.1 預處理

對語料的預處理包括分詞、詞性標注、對經(jīng)過詞性標注的語料進行人工標注、命名實體識別、句子切分和提取候選關系實例等。

首先，利用中科院的ICTCLAS工具對文本進行分詞及詞性標注。其次，人工對已經(jīng)完成分詞及詞性標注的語料進行命名實體標注，使用最常用的BMEO標注方法，并利用條件隨機場(CRFs)對人工標注好的語料進行命名實體識別，并對實體識別結果進行合并。其中，實體的類別是預先定義的，即in表示實例，sx表示屬性，pv表示屬性值，根據(jù)旅游領域的特點，屬性值不僅僅包括地點名詞、數(shù)字等，很多都是由數(shù)字+數(shù)量單位組成的，例如，長、寬、高、海拔等是數(shù)字+米/千米，面積是數(shù)字+平方千米/平方公里，酒店是數(shù)字+星級，門票價格是數(shù)字+元/人，人口數(shù)是數(shù)字+萬人等等，因此在進行命名實體標注的時候，不僅要把數(shù)字標注為屬性值，數(shù)字后面的單位也要標注為屬性值，命名實體合并時將它們合并到一起，形成一個完整的屬性值。然后，根據(jù)文本中的標點符號和上下文等特點，將語料進行切分，分成獨立的句子。最后，找出每句話中的所有可能的實體關系對，組成候選關系實例，并對它們的關系類別進行人工標注。其中，預定義的關系包括四類： 實例—屬性關系、屬性—屬性值關系、實例—屬性值關系和其他關系。至此，語料的預處理完成。例如，對于句子“薩馬貢自然保護區(qū)位于維西塔城，面積243平方千米，是金沙江上游西岸的重要水源林和野生動物棲息地?！边M行預處理之后的結果為： “[薩馬貢自然保護區(qū)]inB [位于]sxB [維西塔城]pvB，[面積]sxB [243平方千米]pvB，是金沙江上游西岸的重要水源林和野生動物棲息地?！?，其中，實例-屬性值關系的實體有[薩馬貢自然保護區(qū)]inB、[維西塔城]pvB、[243平方千米]pvB，它們組成的關系候選實例為：

關系候選實例1： 實體1—[薩馬貢自然保護區(qū)]inB、實體2—[維西塔城]pvB

關系候選實例2： 實體1—[薩馬貢自然保護區(qū)]inB、實體2—[243平方千米]pvB

關系候選實例3： 實體1—[維西塔城]pvB、實體2—[243平方千米]pvB

3.2 構造輸入樣本集

根據(jù)旅游領域自由文本中實例-屬性值關系的特點，結合中文領域?qū)嶓w關系抽取中的比較成熟的特征[11-12]，本文選取了實體的類別、實體上下文詞匯、兩個實體的順序、兩個實體的距離、兩個實體之間其他實體的個數(shù)等特征進行特征集的構造，如上文中得到的候選關系實例“薩馬貢自然保護區(qū)—243平方千米”實體對的特征分別如表1所示。

表1 實例-屬性值關系的特征選取實例

其他類別的候選關系實例根據(jù)各類關系的特點，選取合適的特征進行特征集的構造，過程和上文相同，為了方便構造BP神經(jīng)網(wǎng)絡分類模型，各類關系均選擇13類特征。

由于特征集樣本即為BP神經(jīng)網(wǎng)絡的輸入樣本，因此，特征集樣本構造完之后，要轉換為向量形式。如對3.1中的例子中的關系候選實例：

關系候選實例1： 實體1—[薩馬貢自然保護區(qū)]inB、實體2—[維西塔城]pvB

關系候選實例2： 實體1—[薩馬貢自然保護區(qū)]inB、實體2—[243平方千米]pvB

關系候選實例3： 實體1—[維西塔城]pvB、實體2—[243平方千米]pvB

轉換為向量形式如表2所示。

表2 輸入樣本集和期望輸出的數(shù)值化表達

3.3 構造BP神經(jīng)網(wǎng)絡模型

圖2 BP神經(jīng)網(wǎng)絡拓撲結構圖

3.4 利用LM算法進行關系識別與抽取

LM算法對自由文本中的實例-屬性關系、屬性-屬性值關系、實例—屬性值關系進行識別與抽取的過程為：

(1) 對輸入樣本集數(shù)據(jù)進行歸一化處理，初始化BP神經(jīng)網(wǎng)絡的權值和閾值及相關參數(shù)，迭代次數(shù)q設為0，設定誤差最大允許值?，最大迭代次數(shù)qmax，令自適應調(diào)整參數(shù)μ為μ0，k為0等；

(2) 根據(jù)輸入的樣本數(shù)據(jù)計算BP神經(jīng)網(wǎng)絡各層的輸出結果，并按照公式(3)計算E(xk)；

(3) 利用公式(6)計算Jacobian矩陣J(x)；

(4) 利用公式(9)計算△x，并利用公式(10)調(diào)整BP神經(jīng)網(wǎng)絡的連接權值和閾值；

(5) 判斷訓練樣本是否全部輸入，如果已經(jīng)全部輸入，則執(zhí)行步驟(6)，反之，返回(1)；

(6) 判斷網(wǎng)絡誤差E(xk)是否小于?，或迭代次數(shù)q是否達到qmax，如果滿足其中一個條件，則執(zhí)行步驟(8)；如果兩個條件都不滿足，則執(zhí)行步驟(7)；

(7) 判斷網(wǎng)絡誤差E(xk)是否增大，如果增大，則令自適應調(diào)整參數(shù)μ=μ0β,并且返回步驟(4)；反之，則令μ=μ0/β，k=k+1,并且迭代次數(shù)q加1，返回步驟(2)；

(8) 訓練結束，得到最優(yōu)分類模型。

對于上文中的例子，利用上述步驟進行關系識別與抽取的結果如表3所示。

表3 實例、屬性和屬性值的關系抽取結果

4 實驗設計和結果分析

4.1 實驗語料

本文的實驗語料是旅游領域的自由文本，是實驗室已有語料和在旅游網(wǎng)站上爬取的，共有2 000多篇，共有88 541個實體，9 563個關系實例。采用交叉驗證的方法，隨機選取1/10的語料作為測試語料，9/10的語料為訓練語料，將語料進行預處理，轉化成數(shù)值形式的數(shù)據(jù)，便于進行BP神經(jīng)網(wǎng)絡分類模型的訓練和測試。BP神經(jīng)網(wǎng)絡的相關參數(shù)設為： ?=0.000 1，qmax=1 000，學習率η=0.01,LM算法的參數(shù)設為： μ0=0.001，β=10

4.2 評測標準

本文采用最常用的評測標準，即準確率P、召回率R和F值作為最終的實驗評價指標。其定義為：

P = 正確抽取的實體關系數(shù)/抽取出的實體關系總數(shù)*100%

R = 正確抽取的實體關系數(shù)/標準結果中的實體關系總數(shù)*100%

F = 2*P*R/(P+R)

4.3 實驗設計

(1) 實驗一： 為了驗證基于LM算法的BP神經(jīng)網(wǎng)絡分類模型在不同特征集和不同大小的訓練語料集下對實例-屬性關系、屬性-屬性值關系和實例-屬性值關系等對應關系的提取結果，逐漸增加特征集和訓練語料集并分別進行對比。實驗一結果如表4、表5所示。

表4 本文的方法在不同特征集下的實驗抽取結果

續(xù)表

表5 本文方法在不同語料集下的實驗抽取結果

由表4實驗結果可以看出，隨著特征的不斷增加，實驗的抽取效果越來越好，說明了擴大特征集會提高關系提取的效果；由表5實驗結果可以看出，隨著訓練語料集的增加，實驗的抽取效果也在提高，不過，當訓練語料集達到一定的規(guī)模時，實驗的抽取效果的提高速度會變慢。所以，當語料集達到一定規(guī)模后，應該集中到特征的選取和特征集的擴展上。

(2) 實驗二： 利用BP神經(jīng)網(wǎng)絡的傳統(tǒng)算法(梯度下降算法)和LM算法進行實例-屬性、屬性-屬性值、實例-屬性值的關系抽取，和SVM與規(guī)則相結合的方法的抽取結果進行對比。SVM方法在實體語義關系抽取方面的應用已經(jīng)比較成熟，是一種比較好的方法，BP神經(jīng)網(wǎng)絡作為一種新興的實體關系抽取的方法，應用還不是很廣泛，在實體關系抽取方面結果如何，通過和SVM與規(guī)則相結合的抽取結果進行對比，確定BP神經(jīng)網(wǎng)絡在實體關系抽取方面是否具有可行性。實驗二結果如表6所示。

表6 實例、屬性和屬性值二元關系實驗抽取結果

由表6實驗結果可以看出，在實例、屬性和屬性值之間的關系抽取方面，傳統(tǒng)的BP神經(jīng)網(wǎng)絡算法的分類效果很差，這是因為傳統(tǒng)的BP算法即梯度下降法具有易陷入局部最小化和收斂速度慢等缺點，實驗過程中，迭代次數(shù)達到最大值1000時網(wǎng)絡誤差仍沒達到要求，訓練時間為549s?；贚M算法的BP神經(jīng)網(wǎng)絡的分類效果優(yōu)于SVM分類器與規(guī)則相結合的方法的效果，這是由于實例、屬性和屬性值之間的所有特征組合屬于非線性特征組合，而BP神經(jīng)網(wǎng)絡具有復雜的非線性映射能力，LM算法收斂速度比傳統(tǒng)的BP神經(jīng)網(wǎng)絡算法快得多，當?shù)螖?shù)為27時就滿足誤差指標訓練時間只有82s，因此，基于LM算法的BP神經(jīng)網(wǎng)絡更適合解決多分類問題。

5 結論

本文提出了利用BP神經(jīng)網(wǎng)絡的優(yōu)化算法LM算法對非結構化自由文本進行實例、屬性和屬性值之間的關系進行抽取的方法，該方法利用BP神經(jīng)網(wǎng)絡非線性映射能力強，自主學習和反饋訓練的特點，提高了關系提取的準確率，取得了良好的抽取效果，并且通過實驗驗證了該方法的可行性。下一步工作將在不斷收集數(shù)據(jù)、增加實驗語料的基礎上，嘗試利用半監(jiān)督的深度學習算法實現(xiàn)對領域?qū)嵗龑傩躁P系的抽取學習，以期進一步提高關系抽取的性能。

[1] David Sánchez. A methodology to learn ontological attributes from the Web[J].Data & Knowledge Engineering, 2010，69(6)： 573-597.

[2] S Ravi,M Pasca. Using structured text for large-scale attribute extraction[C]//Proceedings of the 17th CIKM(CIKM 2008),Napa Valley, California,2008: 1183-1192.

[3] 李文杰,穗志方.基于并列結構的實例和屬性的同步提取方法[J].中文信息學報，2012，26(2): 82-87.

[4] 唐偉,洪宇，馮艷卉，等.網(wǎng)頁中商品“屬性-值”關系的自動抽取方法研究[J].中文信息學報，2013，27(1): 21-29.

[5] 程顯毅,朱倩.未定義類型的關系抽取的半監(jiān)督學習框架研究[J].南京大學學報： 自然科學版，2012，48(4):466-474.

[6] 楊宇飛，戴齊，賈真，等.基于弱監(jiān)督的屬性關系抽取方法[J].計算機應用，2014，34(1):64-68.

[7] 王建梅,覃文忠. 基于L-M算法的BP神經(jīng)網(wǎng)絡分類器[J]. 武漢大學學報(信息科學版),2005，10:928-931.

[8] Manolis I A Lourakis. A Brief Description of theLevenberg-Marquardt Algorithm Implemened by levmar. Institute of Computer Science Foundation for Research and Technology - Hellas (FORTH). Vassilika Vouton, P.O. Box 1385, GR 711 10 Heraklion, Crete, GREECE. February 11, 2005.

[9] 張長勝,歐陽丹彤,岳娜,等. 一種基于遺傳算法和LM算法的混合學習算法[J].吉林大學學報(理學版),2008，04:675-680.

[10] Janti Shawash，David R Selviah. Real-Time Nonlinear Parameter Estimation Usingthe Levenberg-Marquardt Algorithm on Field Programmable Gate Arrays[J]. IEEE Transactions on Industrial Electronics， 2013,60(1)： 170-176.

[11] 董靜,孫樂,馮元勇.中文實體關系抽取中的特征選擇研究[J].中文信息學報, 2007，21(4): 80-85.

[12] 車萬翔,劉挺,李生.實體關系自動抽取[J].中文信息學報，2005,19(2):1-6.

[13] Pengyi Gao,Chuanbo Chen,Sheng Qin. An optimization method of hidden nodes for neural network[J].2nd International Workshop on Education Technology and Computer Science, ETCS 2010, 2: 53-56.