快速收斂截?cái)嗪朔稊?shù)矩陣填充方法的遠(yuǎn)監(jiān)督關(guān)系抽取

王燁 張百強(qiáng)

（中國科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所 吉林省長(zhǎng)春市 130000）

1 引言

關(guān)系抽取技術(shù)能夠從海量數(shù)據(jù)中挖掘出反映實(shí)體之間關(guān)系的結(jié)構(gòu)化數(shù)據(jù)。為了應(yīng)對(duì)當(dāng)今大數(shù)據(jù)時(shí)代的海量異構(gòu)數(shù)據(jù)[1]，遠(yuǎn)監(jiān)督關(guān)系抽取方法被提出，該方法通過將一個(gè)已有的知識(shí)庫和文本集進(jìn)行啟發(fā)式匹配生成訓(xùn)練數(shù)據(jù)。這些訓(xùn)練數(shù)據(jù)的產(chǎn)生是基于這一假設(shè)條件——“任何包含已知知識(shí)庫中關(guān)系的實(shí)體對(duì)的句子，都是在用某種方式潛在的表達(dá)了這種關(guān)系”[2]。實(shí)際上存在提到某實(shí)體對(duì)的句子并未表達(dá)該實(shí)體對(duì)在知識(shí)庫中對(duì)應(yīng)的關(guān)系的情況，對(duì)這樣的句子進(jìn)行特征提取，就導(dǎo)致了噪聲特征的產(chǎn)生。

Fan[3]等人提出了基于低秩矩陣填充方法的遠(yuǎn)監(jiān)督關(guān)系抽取，來應(yīng)對(duì)遠(yuǎn)監(jiān)督關(guān)系抽取存在較多噪聲特征的問題。該方法將低秩矩陣填充技術(shù)應(yīng)用在遠(yuǎn)監(jiān)督關(guān)系抽取當(dāng)中，準(zhǔn)確率比通過訓(xùn)練分類器進(jìn)行遠(yuǎn)監(jiān)督關(guān)系抽取的方法有了顯著的提高。然而這種基于核范數(shù)的低秩矩陣填充技術(shù)本身也存在一定局限：核范數(shù)的大小與秩的大小無法完全等價(jià)，因此對(duì)于秩函數(shù)不能取得很好的逼近效果，導(dǎo)致了優(yōu)化目標(biāo)不夠明確的問題。

本文使用截?cái)嗪朔稊?shù)代替核范數(shù)[4]進(jìn)行遠(yuǎn)監(jiān)督關(guān)系抽取，選取奇異值開始快速衰減的位置進(jìn)行截?cái)啵桓淖兦皉 個(gè)最大的奇異值的大小，通過最小化奇異值序列中剩余的min(m,n)-r 個(gè)奇異值得和——即截?cái)嗪朔稊?shù)，來進(jìn)行最小化秩函數(shù)的求解，從而進(jìn)行基于低秩矩陣填充的遠(yuǎn)監(jiān)督關(guān)系抽取。

2 相關(guān)工作

遠(yuǎn)監(jiān)督學(xué)習(xí)是弱監(jiān)督學(xué)習(xí)的一種，Craven[5]等人通過將酵母蛋白質(zhì)數(shù)據(jù)于PubMed 目錄進(jìn)行匹配，得到的訓(xùn)練數(shù)據(jù)用來訓(xùn)練樸素貝葉斯分類器，這是遠(yuǎn)監(jiān)督學(xué)習(xí)的思想第一次被提出。Snow[6]等人使用WorldNet 知識(shí)庫作為監(jiān)督來提取文本中實(shí)體之間的上下位關(guān)系。Hoffman[7]等人提出了使用多標(biāo)簽的框架來適應(yīng)一個(gè)實(shí)體對(duì)對(duì)應(yīng)多個(gè)關(guān)系的情況。噪聲特征的存在影響了遠(yuǎn)監(jiān)督關(guān)系抽取的準(zhǔn)確率，F(xiàn)an[3]等人提出了將低秩矩陣填充技術(shù)應(yīng)用于遠(yuǎn)監(jiān)督關(guān)系抽取當(dāng)中，過濾噪音數(shù)據(jù)，恢復(fù)潛在的低秩矩陣，準(zhǔn)確率和召回率都較之前的方法有了明顯的提高，但是在進(jìn)行最小化矩陣的秩的過程中，矩陣的有效信息和噪音數(shù)據(jù)一同被減小。

本文提出的能夠快速收斂的基于截?cái)嗪朔稊?shù)矩陣填充技術(shù)的遠(yuǎn)監(jiān)督關(guān)系抽取，利用TNNR-ADMMAP 算法進(jìn)行凸優(yōu)化子問題的求解，能夠較好地保留矩陣中對(duì)遠(yuǎn)監(jiān)督關(guān)系抽取有效的成分，同時(shí)降低噪聲數(shù)據(jù)對(duì)結(jié)果的影響。

3 基于TNNR低秩矩陣填充的遠(yuǎn)監(jiān)督關(guān)系抽取過程

本文將基于截?cái)嗪朔稊?shù)快速收斂的低秩矩陣填充技術(shù)，應(yīng)用于遠(yuǎn)監(jiān)督關(guān)系抽取當(dāng)中。TNNR（Truncated Nuclear Norm Regularization）方法是通過針對(duì)截?cái)嗪朔稊?shù)（奇異值序列中最小的k 個(gè)奇異值的和）進(jìn)行最小化求解，來代替最小化矩陣的秩的問題的求解，不改變前r 個(gè)最大的奇異值的大小，其中k=min(m,n)-r。

3.1 將遠(yuǎn)監(jiān)督關(guān)系抽取轉(zhuǎn)化為矩陣填充問題

將遠(yuǎn)監(jiān)督關(guān)系抽取問題轉(zhuǎn)化為矩陣填充問題，通過對(duì)矩陣中未知部分的填充，實(shí)現(xiàn)關(guān)系抽取的目的。根據(jù)訓(xùn)練數(shù)據(jù)集，構(gòu)建一個(gè)包含n 個(gè)實(shí)體對(duì)、t 個(gè)標(biāo)簽和d 維特征向量的基于遠(yuǎn)監(jiān)督關(guān)系抽取規(guī)則的待填充矩陣。

可以表示為以下形式：

Ftrain∈Rn×d代表訓(xùn)練數(shù)據(jù)的特征矩陣，Ltrain∈Rn×t代表訓(xùn)練數(shù)據(jù)的標(biāo)簽矩陣，F(xiàn)test∈Rm×d代表測(cè)試數(shù)據(jù)的特征矩陣，Ltest∈Rm×t代表測(cè)試數(shù)據(jù)的標(biāo)簽矩陣。利用已觀測(cè)到的Ftrain，Ltrain和Ftest將線性分類問題轉(zhuǎn)化為填充Ltest中未知部分的問題。可以將低秩矩陣填充過程表示為對(duì)最小化矩陣秩函數(shù)的問題的求解。

3.2 截?cái)嚅L(zhǎng)度的選取

本文通過截?cái)嗟暮朔稊?shù)代替核范數(shù)來近似表示矩陣的秩。矩陣經(jīng)過奇異值分解，得到呈快速衰減趨勢(shì)的奇異值序列。矩陣秩的大小等于奇異值的個(gè)數(shù)，因此對(duì)于矩陣秩的大小來說，奇異值無論大小，重要性是相同的。核范數(shù)的大小等于所有奇異值的和。因此，與核范數(shù)相比，從奇異值快速衰減處進(jìn)行截?cái)啵瑑H保留最小的r 個(gè)奇異值的截?cái)嗪朔稊?shù)可以更好地逼近矩陣的秩。本文使用ISD[8]方法尋找奇異志序列的截?cái)辔恢谩云娈愔档淖詈箫@著跳躍點(diǎn)作為截?cái)辔恢茫磖 的取值。

3.3 最小化截?cái)嗪朔稊?shù)的問題求解

本文通過最小化截?cái)嗪朔稊?shù)代替核范數(shù)，來求解最小化矩陣的秩的問題。以下是截?cái)嗪朔稊?shù)的定義：

定義3.1([4]).對(duì)于給定矩陣X∈Rm×n，截?cái)嗟暮朔稊?shù)‖X‖r為奇異值序列中最小的k 個(gè)奇異值的和，其中k=min(m,n)-r。矩陣的截?cái)嗪朔稊?shù)可表示為如下形式：

σi為X 的第i 個(gè)大的奇異值。r 值即核范數(shù)的截?cái)辔恢谩＝財(cái)嗪朔稊?shù)是非凸函數(shù)，我們將最小化截?cái)嗪朔稊?shù)問題轉(zhuǎn)化為如下形式：

采用兩步迭代機(jī)制求解式（3），在第l 次迭代中：

（1）固定Xl，通過對(duì)矩陣進(jìn)行奇異值分解得到Al和Bl。

（2）固定Al和Bl，然后通過求解凸優(yōu)化子問題得到Xl+1，該凸優(yōu)化子問題描述如下：

3.4 TNNR-ADMMAP優(yōu)化方法

雖然TNNR-ADMM (alternating direction method of multipliers)可以用來求解兩步迭代算法中的凸優(yōu)化子問題，但由于遠(yuǎn)監(jiān)督關(guān)系抽取問題計(jì)算規(guī)模較大，TNNR-ADMM 難以求得使其收斂的最優(yōu)解。本文利用ADMMAP(alternating direction method of multipliers with adaptive penalty)求該解凸優(yōu)化子問題，以達(dá)到加速收斂的目的。

TNNR-ADMMAP 算法通過對(duì)凸優(yōu)化字問題的約束條件進(jìn)行放松，使用自適應(yīng)懲罰算法加速收斂。

首先，將式（7）的兩個(gè)線性約束條件：X=W 和PΩ(W)=PΩ(M)，寫成如下形式：

其中，A 和B∈Rm×n→R2m×2n，A 和B 是線性映射。

因此，對(duì)應(yīng)的增廣拉格朗日函數(shù)為：

其中，βmax為β 的上界，ρ 的定義如下：

其中，ρ0是常數(shù)，且ρ0＞1，ε 為近端參數(shù)。

通過線性ADMM，求解式（6）：

定義A*，B*：R2m×2n→Rm×n為A，B 的伴隨矩陣。

TNNR-ADMMAP 具體算法如下：

表1

4 實(shí)驗(yàn)設(shè)計(jì)

將本文中的TNNR-ADMMAP 算法與ADMM、APGL 優(yōu)化算法以及Miao Fan 等人提出的使用低秩矩陣填充方法進(jìn)行遠(yuǎn)監(jiān)督關(guān)系抽取的方法——DRMC-1 和DRMC-b 進(jìn)行比較。

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文中使用NYT’13 數(shù)據(jù)庫需要將該數(shù)據(jù)庫的內(nèi)容以矩陣的形式表示出來。根據(jù)NYT’13 數(shù)據(jù)庫構(gòu)造出來的矩陣為稀疏矩陣，共包含10591 個(gè)實(shí)體對(duì)，該數(shù)據(jù)庫中的特征為實(shí)體對(duì)之間的依存路徑。

4.2 參數(shù)選取

在實(shí)驗(yàn)中，我們?cè)O(shè)定β=1，?=10-4。對(duì)數(shù)據(jù)進(jìn)行五組交叉驗(yàn)證，減少因數(shù)據(jù)劃分對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生的影響。

4.3 實(shí)驗(yàn)結(jié)果

表1 在 前100、500、1000 個(gè)關(guān)系實(shí)例預(yù)測(cè)中DRMC-1、DRMC-b、TNNR-ADMM 和TNNR-ADMMAP 方法的準(zhǔn)確率。

使用同一組數(shù)據(jù)（NYT’13）進(jìn)行實(shí)驗(yàn)，針對(duì)置信度前100、500、1000 個(gè)關(guān)系實(shí)例的預(yù)測(cè)準(zhǔn)確率進(jìn)行統(tǒng)計(jì)，使用TNNR-ADMM算法進(jìn)行關(guān)系抽取的準(zhǔn)確率未能比DRMC-b 和DRMC-1 有明顯提高，這是由于ADMM 不易收斂，難以得到使其收斂的最優(yōu)解，對(duì)于計(jì)算規(guī)模較大的遠(yuǎn)監(jiān)督關(guān)系抽取問題的求解沒有明顯優(yōu)勢(shì)。TNNR-ADMMAP 具有較快的收斂速度，截?cái)嗪朔稊?shù)能夠更好地逼近秩函數(shù)并且能夠更好的保留矩陣的主要成分信息，因此基于截?cái)嗪朔稊?shù)的TNNR-ADMMAP 方法準(zhǔn)確率較高，平均準(zhǔn)確率能夠達(dá)到84.20%。

5 展望

本文對(duì)于遠(yuǎn)監(jiān)督關(guān)系抽取存在噪聲特征這一特點(diǎn)進(jìn)行了有針對(duì)性的改進(jìn)，降低噪聲數(shù)據(jù)對(duì)結(jié)果的影響。在以后的工作中，可以針對(duì)以下兩方面開展研究：

（1）研究特征稀疏對(duì)關(guān)系抽取效果的影響。

（2）研究應(yīng)對(duì)標(biāo)簽不完整性的方法，進(jìn)一步提高遠(yuǎn)監(jiān)督關(guān)系抽取的準(zhǔn)確率。