0 引言

随着互联网媒体的兴起, 海量网络新闻文本数据仍在不断增长, 并且这些数据中存储着社会发展过程中重要的舆情事件和热门讨论话题.当前, 自然语言处理(Natural Language Processing, NLP)技术的不断成熟使得我们可以利用命名实体识别^[1] (Named Entity Recognition, NER)技术识别文本中出现的实体.然而, 当文本中存在很多实体时, 如何提取文本中的重要实体来刻画事件(或话题)的发生主体(人物或机构)与发生地点就显得尤为重要, 因为这些实体中仅有一部分是与文本主题相关的, 并且大量的实体可能会淹没或模糊文本主题, 而与文本主题无关的实体可能会偏离事件(或话题)本身并影响对文本主题的理解.

近些年来, 对于文本关键词抽取的研究吸引了越来越多学者的关注^[2-11], 它旨在对文本中的词项进行重要性排序, 从而选出top- $k$ 个词项作为文本的关键词.其算法主要考虑词项

在文本中的特征, 如词频和位置^[2]、文档结构^[3]、逆向文档频率^[4-5]、词项的主题分布^[6-7]等.尽管存在大量文本关键词抽取的研究工作, 然而对文本重要实体排序的研究却相对欠缺.文本重要实体不仅可以抽象概括文本主题^[12], 而且有助于信息检索^[13]和问答系统^[14]等方面的研究.例如, 在信息检索系统中利用实体搜索相关文档时, 在搜索匹配过程中去除文档中的无关实体可以有效地提高文档检索的准确率; 同样在问答系统中, 如何有效地识别文本中的重要实体与无关实体可以更好地求解出问题答案.因此, 对文本中的实体进行重要性排序具有现实意义.

本文针对单文档的重要实体排序问题, 提出了一种新的排序模型LA-FSAM (FSAM based on AUC Metric and Logistic Function). LA-FSAM是一种基于提升(Boosting)的前向分步算法^[15], 它充分考虑实体在文档中的重要特性, 提取4种实体文档特征, 并利用维基百科和谷歌Word2Vec引入2种实体外部特征. LA-FSAM模型运用改进的AUC准则构建损失函数, 并使用逻辑斯谛函数混合上述6种特征作为基函数, 通过标注训练数据并利用随机梯度下降法学习模型参数, 最终通过实验对比, 证明了本文所提方法的有效性.

本文后续组织如下:第1节简要总结相关研究工作; 第2节形式化定义单文档排序问题; 第3节详细介绍本文的研究方法; 第4节通过实验验证本文所提方法的有效性; 第5节总结全文.

1 相关工作

经典的实体排序问题主要应用于信息检索领域, 旨在根据实体与用户搜索的相关性, 对实体进行排序^{[14, 16-18]}.在这些实体排序任务中, 研究的关键在于理解用户搜索并从海量的、异构的数据源中返回与用户搜索最相关的实体集.文献[14]关注于如何理解用户自由无规则的搜索并返回相关的实体或事件, 该文献使用与搜索相关的文档集和知识库来提取相关特征, 分别使用RankSVM和Coordinate Ascent模型对搜索结果进行相关性排序.文献[16-17]通过使用结构化的知识库、实体关系图谱和用户数据来提取有效特征, 并运用基于GBDT的模型对搜索实体进行相关性排序.文献[18]通过收集并整合知识库、推特和搜索日志等不同资源(给予权重)的实体描述来提高搜索实体排序的性能, 该方法可实时的增加新的实体描述, 并且通过获取用户如何搜索实体的变化来优化不同资源的实体描述.学习排序(Learning to Rank, LTR)方法被广泛应用于信息检索领域并取得了较好的表现, 文献[14, 16-17]所使用的算法均为学习排序模型.学习排序方法根据模型的数据输入形式可以分为基于Pointwise、Pairwise和Listwise的排序, 这类方法提取特征, 并训练RankSVM、提升模型或神经网络等排序模型^[19].因此, 对于文档实体排序问题, 本文考虑提取文档中有关实体的重要特征并通过学习排序方法融合多种特征来实现排序模型.

然而, 本文所提的实体排序问题是指对于任意的文本文档, 根据文本描述内容与主题, 对文本中的实体进行重要性排序, 这与文本关键词抽取的研究有很强的相关性.文献[2-5]利用文本中的词项特征, 例如词性、词频、逆向文档频率、位置和词项长度等, 通过标注训练数据并应用监督学习方法来抽取文本关键词.非监督学习方法中, 文献[8]首次将随机游走算法应用于关键词提取问题, 该文使用词项在滑动窗口内的共同出现来建立词项之间的关系, 随后出现了大量的基于随机游走的关键词抽取研究工作, 他们通过不同的方法建立词项之间的语义关系:文献[9]通过WordNet建立词与词之间的语义关系; 文献[10]则利用词汇分布表示(Word Embedding)来计算词项之间的语义关系; 对于其他非监督学习方法, 文献[7, 11]运用基于图的算法或聚类方法抽取文本关键词.文本关键词抽取的目标是提取与文本内容和主题相关的词项, 主要考虑名词、动词和形容词, 而文本实体排序则是获取与文本内容和主题相关的重要实体, 他们的研究目标相似, 研究对象略有不同.

基于以上的研究, 本文考虑借助文本关键词抽取的相关研究来提取文本实体特征, 并根据学习排序方法提出LA-FSAM模型对文本实体进行排序.

2 单文档实体排序问题

为了更好地介绍LA-FSAM算法如何对文本实体进行重要性排序, 本节将详细给出算法涉及的重要概念以及LA-FSAM算法的梗概.

定义1 新闻文档 $d_i$ , 对于任意的新闻文档 $d_i$ , 它由标题 $t_i$ 、描述内容 $c_i$ 和实体列表 $E(d_i)$ 组成, 即 $d_i=\{t_i, c_i, E(d_i)\}$ , 其中, 实体列表 $E(d_i)=\{e_{i1}, e_{i2}, \cdots, e_{im}\}$ , $e_{ij}(1\leq j\leq m)$ 为文档 $d_i$ 中的第 $j$ 个实体, 本文按照实体首次出现的顺序来排序.

定义2 实体正例集合 $P_i$ 与实体负例集合 $N_i$ , 在任意新闻文档 $d_i$ 的实体列表 $E(d_i)$ 中, 重要的实体构成实体正例集合 $P_i$ , 其他剩余实体构成实体负例集合 $N_i$ .

因此, 根据定义1和定义2可以将文本重要实体排序问题定义为:对于任意给定的新闻文档 $d_i$ , 自动地对文档实体列表 $E(d_i)$ 中的实体进行排序, 使得 $E(d_i)$ 中实体正例集合 $P_i$ 中的实体排在实体负例集合 $N_i$ 中的实体的前面.

定义3 标注新闻文档 $dl_i$ , 对于任意的标注新闻文档 $dl_i$ , 它由标题 $t_i$ 、描述内容 $c_i$ 、实体正例集合 $P_i$ 与实体负例集合 $N_i$ 构成, 即 $dl_i=\{t_i, c_i, P_i, N_i\}$ .

定义4 标注文档集合DL, 标注文档集合DL由一系列标注新闻文档 $dl_i$ 构成, 即 $DL=\{dl_1, dl_2, \cdots, dl_n\}$ .

LA-FSAM是基于前向分步算法的监督学习方法, 该算法主要由以下4部分组成.

(1) 命名实体抽取.对于任意给定的新闻文档 $d_i$ , 本文利用NER技术抽取文档标题和描述内容中的所有实体, 借助文献[20]所提方法对抽取的实体集合进行归一化处理, 归一化后的实体集合组成该文档重要实体的候选集, 即定义1中的实体列表 $E(d_i)$ .

(2) 特征提取.对于任意给定的新闻文档 $d_i$ , 经过第一步命名实体抽取后, 计算实体列表 $E(d_i)$ 中各个实体在6种特征下的值来构造特征矩阵 $X_i$ , 对于特征矩阵 $X_i$ 中的每一种特征做归一化处理, 即特征矩阵 $X_i$ 中每一列的元素相加之和等于1. 6种特征的定义以及计算方法将在第3节中详细介绍.

(3) 模型学习.给定标注文档集合DL作为模型输入, LA-FSAM通过不断地叠加新的基函数优化模型, 在每次叠加新的基函数时, 通过极小化损失函数不断地更新模型当前参数, 直至模型收敛.这里, 模型学习的优化目标为对于任意的新闻文档 $d_i$ , 经过排序打分后其实体正例集合 $P_i$ 中的实体分数高于实体负例集合 $N_i$ 中的实体分数.具体的模型算法以及参数学习将在第3节中详细介绍.

(4) 实体排序.通过第(3)部分求解出模型的最优参数后, 任意给定一篇新闻文档 $d_i$ , 经过前两步实体抽取与特征提取后, 通过LA-FSAM模型可以得到该文档中实体的最终分数并对其进行排序.

3 LA-FSAM算法

本节将详细给出LA-FSAM模型算法介绍、基于特征的基函数构造、损失函数构造以及模型参数学习过程.

3.1 LA-FSAM算法

前向分步算法(FSAM)是一种基于提升(Boosting)的方法, FSAM方法旨在通过改变训练样本权重, 学习多个基函数, 然后通过将这些基函数进行线性组合提高模型性能^[21]. LA-FSAM模型借鉴FSAM算法的思想, 结合文档实体排序问题, 构造适合的基函数与损失函数.特别地, 本文基函数为排序函数, 通过叠加排序函数提高LA-FSAM模型性能.设 $b(X;\overrightarrow{\beta})$ 为排序基函数, $L(P, N, f(X))$ 为损失函数, 其中, $X$ 为实体特征矩阵, $\overrightarrow{\beta}$ 为各个特征 $(\overrightarrow{x}_1, \cdots, \overrightarrow{x}_6)$ 的权重向量, $f(X)$ 为基函数叠加后的加法模型, $P$ 为实体正例集合, $N$ 为实体负例集合, 则LA-FSAM算法见算法1.

算法1  LA-FSAM算法
输入:标注文档集合 $DL=\{dl_1, dl_2, \cdots, dl_n\}$ , 损失函数 $L(P, N, f(X))$ , 基函数集 $\{b(X;\overrightarrow{\beta})\}$ 输出:加法模型 $f(X)$
1.初始化 $f_0(X)=0$
2. For $t=1, \cdots, T$
$(\alpha_t, \overrightarrow{\beta_t})=\text {arg} \min\limits_{\alpha, {\overrightarrow{\beta}}} \sum\limits_{i=1}^nL(P_i, N_i, f_{t-1}(X_i)+\alpha b(X_i;\overrightarrow{\beta}))$
$f_t(X)=f_{t-1}+\alpha_tb(X;\overrightarrow{\beta_t})$
3.得到加法模型
$f(X)=\sum\limits_{t-1}^T+\alpha_tb(X;\overrightarrow{\beta_t})$

与前向分步算法思路相似, LA-FSAM算法通过每次只学习一个排序基函数及其参数来不断的优化模型, 不仅求解出高性能的加法模型排序函数 $f(X)$ , 还降低了优化问题的复杂度.

3.2 基于特征的基函数构造

基函数 $b(X;\overrightarrow{\beta})$ 为排序函数, 给定任意新闻文档 $d_i$ 可以根据实体特征矩阵 $X_i$ 求解出实体列表 $E(d_i)$ 中每个实体的分数.接下来将分别介绍6种实体特征.

(1) 标题频率.新闻标题作为新闻描述内容的高度概括与总结, 通常会提及重要实体, 例如文本描述事件(或话题)的发生主体(人名, 机构名)或发生地点(位置).因此, 实体在标题中的出现频率可以作为实体是否重要的判断依据.任意给定实体列表 $E(d_i)$ , 则标题频率特征 $\overrightarrow{x}_1$ 可以表示为

$ \begin{align} \overrightarrow{x}_1=\Big(\frac{T\text {count} (e_{i1})}{Z_{i1}}, \frac{T\text {count} (e_{i2})}{Z_{i1}}, \cdots, \frac{T\text {count} (e_{im})}{Z_{i1}}\Big)^\text T, \end{align} $

(1)

其中, $T\text {count} (e_{ij})$ 为文档 $d_i$ 中第 $j$ 个实体 $e_{ij}$ 在标题中出现的次数, $Z_{i1}$ 为文档 $d_i$ 在标题频率特征下的归一化因子.

(2) 描述内容频率.文本描述内容作为新闻文档的主体内容, 多数实体都来自于这里, 并且通常重要的实体会在描述文本中出现多次.因此, 特征 $\overrightarrow{x}_2$ 定义为实体在文本描述内容中的频率.任意给定实体列表 $E(d_i)$ , 则描述内容频率特征 $\overrightarrow{x}_2$ 可以表示为

$ \begin{align} \overrightarrow{x}_2=\Big(\frac{C\text {count}(e_{i1})}{Z_{i2}}, \frac{C\text {count} (e_{i2})}{Z_{i2}}, \cdots, \frac{C\text {count} (e_{im})}{Z_{i2}}\Big)^\text T, \end{align} $

(2)

其中, $C\text {count} (e_{ij})$ 为文档 $d_i$ 中第 $j$ 个实体 $e_{ij}$ 在描述内容中出现的次数, $Z_{i2}$ 为文档 $d_i$ 在描述内容频率特征下的归一化因子.

(3) 实体位置.描述内容文本通常会在文本开头概述新闻事件或话题的主要内容.因此, 实体在整个文档中首次出现的位置可以作为实体是否重要的判断标准.任意给定实体列表 $E(d_i)$ , 则标题频率特征 $\overrightarrow{x}_2$ 可以表示为

$ \begin{align} \overrightarrow{x}_3=\frac{1}{Z_{i3}}\Big(\frac{m}{\text {total}_\text {pos}}, \frac{m-1}{\text {total}_\text {pos}}, \cdots, \frac{1}{\text {total}_\text {pos}}\Big)^\text T, \end{align} $

(3)

其中, $\text {total}_\text {pos}=\sum\limits_{j=1 }^mj$ , $Z_{i3}$ 为文档 $d_i$ 在实体位置特征下的归一化因子.

以上3个特征为基于实体个体的特征, 而接下来将要介绍的特征为基于实体关系的特征, 通过特定的实体关系构造实体关系矩阵 $M_{m\times m}$ ( $m$ 为实体个数), 经过基于PageRank的随机游走方法, 并将最终的稳定向量作为实体的特征.

在PageRank^[22]算法中, 设转移矩阵为上文所提实体关系矩阵 $M_{m\times m}$ , 随机跳转向量 $\overrightarrow{t}=(\frac{1}{m}, \frac{1}{m}, \cdots, \frac{1}{m})^\text T$ , 初始概率分布向量 $\overrightarrow{v}_0=(\frac{1}{m}, \frac{1}{m}, \cdots, \frac{1}{m})^\text T$ , $\gamma$ 为随机跳转概率, 则可以通过

$ \begin{align} \overrightarrow{v}_t=(1-\gamma)M\overrightarrow{v}_{t-1}+\gamma \overrightarrow{t} \end{align} $

(4)

计算得到任意新闻文本 $d_i$ 中各个实体基于某种关系的稳定排序分数值, $t=1, 2, \cdots$ , 直至 $\overrightarrow{v}_t$ 收敛.

(4) 基于实体共现的特征. TextRank^[8]首次将基于PageRank的随机游走应用于关键词抽取中并取得较好的实验效果, 随后出现了大量基于此方法的关键词提取的研究. TextRank通过两个实体在滑动窗口内的共同出现建立实体间关系.本文将滑动窗口定义为每一句话(包括标题).任意给定实体列表 $E(d_i)$ , 对于转移矩阵 $M_i$ 中的任意元素 $m_{ijk}$ , 有

$ \begin{align} m_{ijk}=S\text {count} (e_{ij}, e_{ik}), \end{align} $

(5)

其中, $S\text {count} (e_{ij}, e_{ik})$ 为文档 $d_i$ 中实体 $e_{ij}$ 和 $e_{ik}$ 同时出现的句子的个数.得到转移矩阵 $M_i$ 后对 $M_i$ 做归一化处理.

(5) 基于维基百科的特征.维基百科页面中的入链接(inlink)和出链接(outlink)提供了实体间丰富的语义关系, 通过这些语义关系可以建立有效的实体关系矩阵 $M_i$ .本文主要使用维基百科页面中的出链接.任意给定实体列表 $E(d_i)$ , 对于实体关系矩阵 $M_i$ 中的任意元素 $m_{ijk}$ ,

$ \begin{align} m_{ijk}= \frac{\text {OutLinkCount}_{e_{ij}}(e_{ik})+\text {OutLinkCount}_{e_{ik}}(e_{ij})}{2}, \end{align} $

(6)

其中, OutLinkCount $_{e_{ij}}(e_{ik})$ 表示在实体 $e_{ij}$ 的维基百科页面中出链接为实体 $e_{ik}$ 的个数, 同理, OutLinkCount $_{e_{ik}}(e_{ij})$ 表示在实体 $e_{ik}$ 的维基百科页面中出链接为实体 $e_{ij}$ 的个数.得到转移矩阵 $M_i$ 后对 $M_i$ 做归一化处理.

(6) 基于词汇分布表示的特征.词汇分布表示通过训练海量语料库来得到隐含词汇信息的数值型词向量, 对这些词向量进行计算操作可以得到词汇之间的语义关系, 由于训练词汇分布表示需要海量的语料库并且耗时较长, 本文直接使用谷歌Word2Vec作为词汇分布表示并使用余弦相似度来建立任意两个实体之间的语义关系.任意给定实体列表 $E(d_i)$ , 对于该实体关系矩阵 $M_i$ 中的任意元素 $m_{ijk}$ , 有

$ \begin{align} m_{ijk}=\frac{\overrightarrow{V}_{eij}\cdot \overrightarrow{V}_{eik}}{|\overrightarrow{V}_{eij}|| \overrightarrow{V}_{eik}|}, \end{align} $

(7)

其中, $\overrightarrow{V}_{eij}$ 和 $\overrightarrow{V}_{eik}$ 分别表示实体 $e_{ij}$ 和实体 $e_{ik}$ 在词汇分布表示中的词向量.得到转移矩阵 $M_i$ 后对 $M_i$ 做归一化处理.

对于任意给定新闻文档, 根据上述方法计算出特征矩阵 $X$ 后, 应用逻辑斯谛函数来结合这6种特征, 即

$ \begin{align} b(X;\overrightarrow{\beta})=\frac{1}{1+\text e^{-X\overrightarrow{\beta}}}\;, \end{align} $

(8)

其中, $\overrightarrow{\beta}$ 为各个特征的权重向量.

3.3 损失函数构造

文献[23]提出将AUC准则作为排序问题的损失函数, 并且文献[2]将AUC准则作为关键词排序的损失函数.因为排序函数旨在通过排序后使实体正例集合中实体的分数尽可能地高于实体负例集合中实体的分数, 这个优化目标和AUC准则很相似.因此, 本文使用AUC准则构造损失函数. AUC的计算定义为

$ \begin{align} \text {AUC}=\frac{\Sigma_{j\in P}\Sigma_{k\in N}\mbox {II}(f^j(X)-f^k(X))}{|P||N|}\;, \end{align} $

(9)

其中, $f^j(X)$ 和 $f^k(X)$ 分别表示经函数 $f(X)$ 排序后第 $j$ 个实体和第 $k$ 个实体的分数, $P$ 为实体正例集合, $N$ 为实体负例集合, Ⅱ $(x)$ 为指示函数, 有

$ {\text{II}}\left( x \right) = \left\{ \begin{array}{l} 1,\;\;x > 0,\\ 0,\;\;x \le 0. \end{array} \right. $

(10)

根据排序函数的优化目标, 定义损失函数 $L(P, N, f(X))$ 为

$ \begin{align} L(P, N, f(X))=\frac{\Sigma_{j\in P}\Sigma_{k\in N}\mbox{II}\big(f^k(X)-f^j(X)\big)}{|P||N|}, \end{align} $

(11)

但是, 由于本文使用随机梯度下降法极小化损失函数, 根据AUC定义的损失函数 $L(P, N, f(X))$ 含有指示函数Ⅱ $(x)$ , 而指示函数不可导, 因此本文使用Sigmoid函数 $S(x)$ 替换指示函数Ⅱ $(x)$ ,

$ \begin{align} S(x)=\frac{1}{1+\text e^{-x}}. \end{align} $

(12)

则公式(11)损失函数 $L(P, N, f(X))$ 可以重新定义为

$ \begin{align} L(P, N, f(X))=\frac{\Sigma_{j\in P}\Sigma_{k\in N}S(f^k(X)-f^j(X))}{|P||N|}\;. \end{align} $

(13)

3.4 参数学习

由第3.2节和第3.3节可以得到LA-FSAM算法中基函数和损失函数, 综合第3.1节中LA-FSAM算法的介绍, LA-FSAM算法的最终目标优化函数计算是

$ \begin{align} \min\limits_{\alpha_t, \overrightarrow{\beta_t }}\sum\limits_{i=1}^n L\Big(P_i, N_i, \sum\limits_{t=1}^T \alpha_t b(X_i;\overrightarrow{\beta }_t) \Big). \end{align} $

(14)

根据LA-FSAM算法, 对于 $t=1, 2, {\cdots}, T$ , 通过第 $t$ 次叠加仅学习当前基函数 $b(X; \overrightarrow{\beta }_t)$ 及其系数 $\alpha_t$ , 从而不断逼近目标优化函数(14), 因此, 第 $t$ 次仅需优化损失函数

$ \begin{align} \min\limits_{\alpha_t, \overrightarrow{\beta }}J(\alpha, \overrightarrow{\beta })=\frac{1}{n}\sum\limits_{i=1}^n\frac{\sum\nolimits_{j\in P_i\wedge k\in N_i}S(f^k(X_i)-f^j(X_i))}{|P_i||N_i|}, \end{align} $

(15)

其中,

$ \left\{ \begin{align} &{{f}^{k}}\left( {{X}_{i}} \right)=f_{t-1}^{k}\left( {{X}_{i}} \right)+\alpha {{b}^{k}}\left( {{X}_{i}};\vec{\beta } \right), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (16\text{a}) \\ &{{f}^{j}}\left( {{X}_{i}} \right)=f_{t-1}^{j}\left( {{X}_{i}} \right)+\alpha {{b}^{j}}\left( {{X}_{i}};\vec{\beta } \right), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 16\text{b} \right) \\ \end{align} \right. $

$b^k(X_i; \overrightarrow{\beta})$ 和 $b^j(X_i; \overrightarrow{\beta})$ 分别表示经基函数 $b(X_i; \overrightarrow{\beta})$ 排序后第 $k$ 个和第 $j$ 个实体的分数.

本文使用梯度下降法极小化损失函数(15).梯度下降法主要有批处理梯度下降法和随机梯度下降法.考虑到批处理梯度下降法时间复杂度较高, 本文采用随机梯度下降法.在LA-FSAM中, 每次叠加新的基函数时使用随机梯度下降法求解最优参数 $\alpha$ 和 $\overrightarrow{\beta}$ . LA-FSAM模型学习算法见算法2:

算法2  LA-FSAM模型学习算法
输入:标注文档集合 $DL=\{dl_1, dl_2, \cdots, dl_n\}$ , 学习速度 $lr$ 输出: $\alpha$ 和 $\overrightarrow{\beta}$
1. $j=0$ 2.初始化 $\alpha^{(0)}$ , $\overrightarrow{\beta}^{(0)}$ 3.若 $J(\alpha, \overrightarrow{\beta})$ 未收敛, 则循环做       对于训练数据集中的每一篇文档 $dl_i$            $\alpha^{(j+1)}=\alpha ^{(j)}-lr\frac{\partial Ji(\alpha ^{(j)}, \overrightarrow{\beta}^{(j)})}{\partial \alpha}$            $\overrightarrow{\beta}^{(j+1)}=\overrightarrow{\beta}^{(j)}-lr \frac{\partial Ji(\alpha ^{(j)}, \overrightarrow{\beta}^{(j)})}{\alpha\overrightarrow{\beta}}$        $j=j+1$

算法2中 $J_i(\alpha, \overrightarrow{\beta})$ 为基于文档 $dl_i$ 的损失函数

$ \begin{align} J_i(\alpha, \overrightarrow{\beta})=\frac{\sum\nolimits_{j\in P_i\wedge k\in N_i}S(f^k(X_i)-f^j(X_i))}{|P_i||N_i|}. \end{align} $

(16)

下面给出算法2中 $\frac{\partial J_i(\alpha, \overrightarrow{\beta})}{\partial \alpha}$ 和 $\frac{\partial J_i(\alpha, \overrightarrow{\beta})}{\alpha\overrightarrow{\beta}}$ 的计算方法.

$ \begin{align} &\frac{\partial J_i(\alpha, \overrightarrow{\beta})}{\partial \alpha}=\frac{\sum\nolimits_{j\in P_i\wedge k\in N_i}\frac{\partial S(\Delta f^{kj})}{\partial \Delta f^{kj}}\Big(\frac{\partial f^k(X_i)}{\partial\alpha}-\frac{\partial f^j(X_i)}{\partial\alpha}\Big)}{|P_i||N_i|}, \end{align} $

(17)

$ \begin{align} &\frac{\partial J_i(\alpha, \overrightarrow{\beta})}{\alpha\overrightarrow{\beta}}= \frac{\sum\nolimits_{j\in P_i\wedge k\in N_i}\frac{\partial S(\Delta f^{kj})}{\partial \Delta f^{kj}}\Big(\frac{\partial f^k(X_i)}{\partial\overrightarrow{\beta}}-\frac{\partial f^j(X_i)}{\partial\overrightarrow{\beta}}\Big)}{|P_i||N_i|}, \end{align} $

(18)

其中,

$ \left\{ \begin{array}{l} \Delta {f^{kj}} = {f^k}({X_i})-{f^j}({X_i}), \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(20{\text{a}})\\ \frac{{\partial S(\Delta {f^{kj}})}}{{\partial \Delta {f^{kj}}}} = S(\Delta {f^{kj}}) \cdot (1-S(\Delta {f^{kj}})).\;\;\;\;\;\;\;\;(20{\text{b}}) \end{array} \right. $

可以根据公式(16)可以得到

$ \begin{array}{l} \left\{ \begin{array}{l} \frac{{\partial {f^k}({X_i})}}{{\partial \alpha }} = {b^k}({X_i};\vec \beta ), \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(21{\text{a}})\\ \frac{{\partial {f^j}({X_i})}}{{\partial \alpha }} = {b^j}({X_i};\vec \beta ), \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(21{\text{b}}) \end{array} \right.\\ \left\{ \begin{array}{l} \frac{{\partial {f^k}({X_i})}}{{\partial \vec \beta }} = \alpha \cdot {b^k}({X_i};\vec \beta ) \cdot (1-{b^k}({X_i};\vec \beta )){(X_i^k)^{\text{T}}}, \;\;\;\;\;(22{\text{a}})\\ \frac{{\partial {f^j}({X_i})}}{{\partial \vec \beta }} = \alpha \cdot {b^j}({X_i};\vec \beta ) \cdot (1-{b^j}({X_i};\vec \beta )){(X_i^j)^{\text{T}}}, \;\;\;\;\;\;(22{\text{b}}) \end{array} \right. \end{array} $

其中, $X_i^k$ 和 $X_i^j$ 分别表示矩阵 $X_i$ 的第 $k$ 行和第 $j$ 行.

将公式(20)、(21)、(22)分别代入到公式(18)、(19)可以求出算法2中的 $\frac{\partial J_i(\alpha, \overrightarrow{\beta})}{\partial \alpha}$ 和 $\frac{\partial J_i(\alpha, \overrightarrow{\beta})}{\alpha\overrightarrow{\beta}}$ .

4 实验

本节将通过系统的实验来评测LA-FSAM模型的表现.下文将分别对数据集、相关参数设置、基函数叠加数量对LA-FSAM模型的影响、基线方法与LA-FSAM的对比以及案例进行详细说明.

4.1 数据集介绍

目前没有有关文本实体排序相关的公开测试数据集, 本文使用来自于文献[24]的公开新闻报道数据集, 并对其进行人工标注当作评测数据.该数据集中的文本主要来着谷歌搜索中中东地区冲突事件及话题报道, 这里仅使用每篇报道的标题与描述内容.本文从数据集中随机选取500条新闻报道, 使用Standford-NLP^[1]工具抽取文本实体并人工对其每篇文章进行重要实体标注, 最后将80%的标注数据当作训练数据, 剩余20%的标注数据用做测试数据.数据集中重要实体数量统计如表 1所示.

4.2 相关参数设置

参数 $lr$ :参数 $lr$ 为学习速度, 较大的学习速率可以加快算法 $2$ 中优化速度, 但是过大可能会出现震荡无法收敛, 经过实验本文选取 $lr=0.01$ .

参数 $\gamma $ :参数 $\gamma $ 为随机跳转概率, 在0.1 $\le \gamma \le $ 0.9的范围内, 本文以平均损失函数值与平均AUC值为标准, 通过对照实验来分析 $\gamma $ 对LA-FSAM模型的影响.由图 1可以看出当 $\gamma \ge $ 0.3时平均损失函数值较小、平均AUC值较大, 综合考虑平均损失函数值与平均AUC值随 $\gamma $ 的变化, 当0.7 $\le \gamma \le $ 0.9时平均损失函数值与平均AUC值趋于平稳, 因此本文选取 $\gamma=0.8 $ .

4.3 基函数叠加数量对LA-FSAM模型的影响

由第3.1节算法1可以知道LA-FSAM算法通过不断累加新的排序基函数来优化模型.对于模型基函数数量 $t$ , 根据图 2(横坐标为基函数累加数量, 纵坐标为平均损失函数值与平均AUC值)可知, 随着基函数数量的增加平均损失函数值不断减小, 平均AUC值不断增大, 并且当 $t\le 10$ 时随着t的增加平均损失函数值与平均AUC值变化明显, 当 $t>30$ 时平均损失函数与平均AUC值逐渐趋于平稳.因此, 基于前向分步算法的LA-FSAM模型对实体排序有效.

4.4 不同特征LA-FSAM模型的影响

为了衡量不同特征对于LA-FSAM模型的影响, 对于第3.2节介绍的每一个特征, 本实验环节通过分别移除该特征, 使用剩余特征训练模型, 分析在缺少该特征情况下LA-FSAM的排序性能.同样地, 以平均损失函数值与平均AUC值作为评价指标, 由图 3可以看出, 特征3实体位置和特征1标题频率对LA-FSAM排序模型影响最大.

4.5 基线方法介绍

为了证明LA-FSAM模型对文本实体排序的有效性, 本文选取6种方法作为基线方法, 它们分别如下.

基于频率的统计(Frequency):此方法仅考虑实体在文档中的出现频率.

基于位置的统计(Position):此方法仅考虑实体在文档中首次出现的位置, 并且随着首次出现位置的不断靠后重要程度依次降低.

基于共同出现的随机游走(TextRank):此方法主要基于文献[8]所提, 通过实体在滑动窗口内的共同出现建立实体间语义关系, 最后通过随机游走对实体节点进行排序, 这里滑动窗口设置为文本中的每个句子.

基于维基的随机游走(WikiRank):这个方法与TextRank类似, 但是WikiRank通过维基百科链接(inlinks and outlinks)建立实体语义关系.

基于词汇分布表示的随机游走(WordEmbeddingRank):此方法主要基于文献[10]所提, 通过借助词汇分布表示获得蕴含语义的词汇向量, 并通过向量间的相似度建立实体间语义关系, 该算法同样使用随机游走对实体结点进行排序.

RankSVM: RankSVM^[25]是基于Pairwise的学习排序算法, 并且RankSVM也是目前最先进的排序算法之一, 被广泛应用于排序问题中.

4.6 实验结果

根据表 1可以看出少于20%的文档集含有超过5个的重要实体.因此, 本文使用LA-FSAM以及第4.5节所述6种基线方法, 对测试数据进行实体排序, 并分别对排序后的结果做top-1, top-2, top-3, top-4和平均AUC值的实验对比, 实验对比结果如表 2所示.在上述基线方法中, 基于位置的统计方法和RankSVM取得了较好的实验结果; 但是, 与6种基线方法对比, 本文LA-FSAM模型取得最优的表现.

4.7 案例分析

本节从测试集中随机抽取一篇文章做案例分析.文章标题和文章内容如下所示(由于篇幅较长, 文中较多内容用" ${\cdots}{\cdots}$ "替代).

U.N. says Syria death toll has likely surpassed 100, 000

An image provided by opposition activists in April shows a mass grave said...... (Aleppo Media Center/Associated......) BEIRUT -The ever-escalating death toll in Syria's two-year civil war has likely surpassed 100, 000, the United Nations said Thursday, ...... carried out for the U.N. human rights office....... according to the U.N. analysis....... over the past year, " U.N. High Commissioner for Human Rights Navi Pillay said......, including babies, being massacred, " Pillay said. The death count — which likely underestimates the total, Pillay said —......, the U.N.noted, ......more deaths. But Pillay noted that......the strategic city of Qusair, ......the northern city of Aleppo, which...... for almost a year. Any battle to retake Aleppo would likely be protracted and bloody. The U.N. has repeatedly......have failed. A joint U.S.-Russian initiative...... Syrian President Bashar Assad agree to step down, ......Russian brokered peace talks.

该报道文主要针对"联合国(U.N.)高级人权专家皮莱(Navi Pillay)发表的叙利亚(Syria)内战所引发的人员伤亡分析声明"做报道.报道中抽取的实体已在文本中用加粗斜体标记; 人工标注重要实体有: U.N., Syria, Navi Pillay; 经LA-FSAM排序后实体分数从高到低依次为: U.N., Syria, Navi Pillay, Aleppo Media, BEIRUT, Qusair, Aleppo, U. S., Bashar Assad.

5 总结

文本重要实体不仅可以抽象概括文本描述事件或话题的发生主体与发生位置, 还有助于信息检索和问答系统等方面的研究, 因此, 对文本实体进行排序具有现实价值.本文针对该问题提出了一种基于前向分步算法的排序模型LA-FSAM, 该模型使用逻辑斯谛函数混合六种有效特征, 运用改进的AUC准则构建损失函数, 通过标注训练数据并利用随机梯度下降法学习模型参数.最终通过与其他基线方法的实验对比证明了LA-FSAM方法的有效性.