基于LM算法的領(lǐng)域概念實體屬性關(guān)系抽取

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

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

1 引言

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

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

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

2 LM算法介紹

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

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

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

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

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

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

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

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

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

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

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

3 關(guān)系抽取過程

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

圖1 LM算法訓練關(guān)系分類器流程圖

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

3.1 預處理

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

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

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

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

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

3.2 構(gòu)造輸入樣本集

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

表1 實例-屬性值關(guān)系的特征選取實例

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

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

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

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

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

轉(zhuǎn)換為向量形式如表2所示。

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

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

圖2 BP神經(jīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖

3.4 利用LM算法進行關(guān)系識別與抽取

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

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

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

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

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

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

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

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

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

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

表3 實例、屬性和屬性值的關(guān)系抽取結(jié)果

4 實驗設(shè)計和結(jié)果分析

4.1 實驗語料

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

4.2 評測標準

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

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

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

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

4.3 實驗設(shè)計

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

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

續(xù)表

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

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

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

表6 實例、屬性和屬性值二元關(guān)系實驗抽取結(jié)果

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

5 結(jié)論

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

[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] 李文杰,穗志方.基于并列結(jié)構(gòu)的實例和屬性的同步提取方法[J].中文信息學報，2012，26(2): 82-87.

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

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

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

[7] 王建梅,覃文忠. 基于L-M算法的BP神經(jīng)網(wǎng)絡(luò)分類器[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] 董靜,孫樂,馮元勇.中文實體關(guān)系抽取中的特征選擇研究[J].中文信息學報, 2007，21(4): 80-85.

[12] 車萬翔,劉挺,李生.實體關(guān)系自動抽取[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.