快速收敛截断核范数矩阵填充方法的远监督关系抽取

王烨 张百强

（中国科学院长春光学精密机械与物理研究所 吉林省长春市 130000）

1 引言

关系抽取技术能够从海量数据中挖掘出反映实体之间关系的结构化数据。为了应对当今大数据时代的海量异构数据[1]，远监督关系抽取方法被提出，该方法通过将一个已有的知识库和文本集进行启发式匹配生成训练数据。这些训练数据的产生是基于这一假设条件——“任何包含已知知识库中关系的实体对的句子，都是在用某种方式潜在的表达了这种关系”[2]。实际上存在提到某实体对的句子并未表达该实体对在知识库中对应的关系的情况，对这样的句子进行特征提取，就导致了噪声特征的产生。

Fan[3]等人提出了基于低秩矩阵填充方法的远监督关系抽取，来应对远监督关系抽取存在较多噪声特征的问题。该方法将低秩矩阵填充技术应用在远监督关系抽取当中，准确率比通过训练分类器进行远监督关系抽取的方法有了显著的提高。然而这种基于核范数的低秩矩阵填充技术本身也存在一定局限：核范数的大小与秩的大小无法完全等价，因此对于秩函数不能取得很好的逼近效果，导致了优化目标不够明确的问题。

本文使用截断核范数代替核范数[4]进行远监督关系抽取，选取奇异值开始快速衰减的位置进行截断，不改变前r 个最大的奇异值的大小，通过最小化奇异值序列中剩余的min(m,n)-r 个奇异值得和——即截断核范数，来进行最小化秩函数的求解，从而进行基于低秩矩阵填充的远监督关系抽取。

2 相关工作

远监督学习是弱监督学习的一种，Craven[5]等人通过将酵母蛋白质数据于PubMed 目录进行匹配，得到的训练数据用来训练朴素贝叶斯分类器，这是远监督学习的思想第一次被提出。Snow[6]等人使用WorldNet 知识库作为监督来提取文本中实体之间的上下位关系。Hoffman[7]等人提出了使用多标签的框架来适应一个实体对对应多个关系的情况。噪声特征的存在影响了远监督关系抽取的准确率，Fan[3]等人提出了将低秩矩阵填充技术应用于远监督关系抽取当中，过滤噪音数据，恢复潜在的低秩矩阵，准确率和召回率都较之前的方法有了明显的提高，但是在进行最小化矩阵的秩的过程中，矩阵的有效信息和噪音数据一同被减小。

本文提出的能够快速收敛的基于截断核范数矩阵填充技术的远监督关系抽取，利用TNNR-ADMMAP 算法进行凸优化子问题的求解，能够较好地保留矩阵中对远监督关系抽取有效的成分，同时降低噪声数据对结果的影响。

3 基于TNNR低秩矩阵填充的远监督关系抽取过程

本文将基于截断核范数快速收敛的低秩矩阵填充技术，应用于远监督关系抽取当中。TNNR（Truncated Nuclear Norm Regularization）方法是通过针对截断核范数（奇异值序列中最小的k 个奇异值的和）进行最小化求解，来代替最小化矩阵的秩的问题的求解，不改变前r 个最大的奇异值的大小，其中k=min(m,n)-r。

3.1 将远监督关系抽取转化为矩阵填充问题

将远监督关系抽取问题转化为矩阵填充问题，通过对矩阵中未知部分的填充，实现关系抽取的目的。根据训练数据集，构建一个包含n 个实体对、t 个标签和d 维特征向量的基于远监督关系抽取规则的待填充矩阵。

可以表示为以下形式：

Ftrain∈Rn×d代表训练数据的特征矩阵，Ltrain∈Rn×t代表训练数据的标签矩阵，Ftest∈Rm×d代表测试数据的特征矩阵，Ltest∈Rm×t代表测试数据的标签矩阵。利用已观测到的Ftrain，Ltrain和Ftest将线性分类问题转化为填充Ltest中未知部分的问题。可以将低秩矩阵填充过程表示为对最小化矩阵秩函数的问题的求解。

3.2 截断长度的选取

本文通过截断的核范数代替核范数来近似表示矩阵的秩。矩阵经过奇异值分解，得到呈快速衰减趋势的奇异值序列。矩阵秩的大小等于奇异值的个数，因此对于矩阵秩的大小来说，奇异值无论大小，重要性是相同的。核范数的大小等于所有奇异值的和。因此，与核范数相比，从奇异值快速衰减处进行截断，仅保留最小的r 个奇异值的截断核范数可以更好地逼近矩阵的秩。本文使用ISD[8]方法寻找奇异志序列的截断位置——以奇异值的最后显著跳跃点作为截断位置，即r 的取值。

3.3 最小化截断核范数的问题求解

本文通过最小化截断核范数代替核范数，来求解最小化矩阵的秩的问题。以下是截断核范数的定义：

定义3.1([4]).对于给定矩阵X∈Rm×n，截断的核范数‖X‖r为奇异值序列中最小的k 个奇异值的和，其中k=min(m,n)-r。矩阵的截断核范数可表示为如下形式：

σi为X 的第i 个大的奇异值。r 值即核范数的截断位置。截断核范数是非凸函数，我们将最小化截断核范数问题转化为如下形式：

采用两步迭代机制求解式（3），在第l 次迭代中：

（1）固定Xl，通过对矩阵进行奇异值分解得到Al和Bl。

（2）固定Al和Bl，然后通过求解凸优化子问题得到Xl+1，该凸优化子问题描述如下：

3.4 TNNR-ADMMAP优化方法

虽然TNNR-ADMM (alternating direction method of multipliers)可以用来求解两步迭代算法中的凸优化子问题，但由于远监督关系抽取问题计算规模较大，TNNR-ADMM 难以求得使其收敛的最优解。本文利用ADMMAP(alternating direction method of multipliers with adaptive penalty)求该解凸优化子问题，以达到加速收敛的目的。

TNNR-ADMMAP 算法通过对凸优化字问题的约束条件进行放松，使用自适应惩罚算法加速收敛。

首先，将式（7）的两个线性约束条件：X=W 和PΩ(W)=PΩ(M)，写成如下形式：

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

因此，对应的增广拉格朗日函数为：

其中，βmax为β 的上界，ρ 的定义如下：

其中，ρ0是常数，且ρ0＞1，ε 为近端参数。

通过线性ADMM，求解式（6）：

定义A*，B*：R2m×2n→Rm×n为A，B 的伴随矩阵。

TNNR-ADMMAP 具体算法如下：

表1

4 实验设计

将本文中的TNNR-ADMMAP 算法与ADMM、APGL 优化算法以及Miao Fan 等人提出的使用低秩矩阵填充方法进行远监督关系抽取的方法——DRMC-1 和DRMC-b 进行比较。

4.1 实验数据

本文中使用NYT’13 数据库需要将该数据库的内容以矩阵的形式表示出来。根据NYT’13 数据库构造出来的矩阵为稀疏矩阵，共包含10591 个实体对，该数据库中的特征为实体对之间的依存路径。

4.2 参数选取

在实验中，我们设定β=1，ϵ=10-4。对数据进行五组交叉验证，减少因数据划分对实验结果产生的影响。

4.3 实验结果

表1 在 前100、500、1000 个关系实例预测中DRMC-1、DRMC-b、TNNR-ADMM 和TNNR-ADMMAP 方法的准确率。

使用同一组数据（NYT’13）进行实验，针对置信度前100、500、1000 个关系实例的预测准确率进行统计，使用TNNR-ADMM算法进行关系抽取的准确率未能比DRMC-b 和DRMC-1 有明显提高，这是由于ADMM 不易收敛，难以得到使其收敛的最优解，对于计算规模较大的远监督关系抽取问题的求解没有明显优势。TNNR-ADMMAP 具有较快的收敛速度，截断核范数能够更好地逼近秩函数并且能够更好的保留矩阵的主要成分信息，因此基于截断核范数的TNNR-ADMMAP 方法准确率较高，平均准确率能够达到84.20%。

5 展望

本文对于远监督关系抽取存在噪声特征这一特点进行了有针对性的改进，降低噪声数据对结果的影响。在以后的工作中，可以针对以下两方面开展研究：

（1）研究特征稀疏对关系抽取效果的影响。

（2）研究应对标签不完整性的方法，进一步提高远监督关系抽取的准确率。