基于改进句子相似度算法的释义识别研究

陈俊月,郝文宁,张紫萱,唐新德,康睿智,莫 斐

(陆军工程大学 指挥信息系统学院,南京 210000)

0 概述

随着计算机技术的飞速发展和互联网的全面普及,全球数字化信息的存储量爆发式增长。丰富的信息资源既为人们的生活和生产带来了便利,但同时也导致了信息重复冗余的问题。因此,文本语义相似度研究应运而生,其可作为承载语义信息的一种重要方式[1]。文本语义相似度计算具有广阔的实际应用背景,例如论文查重、搜索引擎去重等,受到研究者的广泛关注[2-4]。

释义识别[5-6]用于判断任意两个句子或短语其语义是否相同,可看作是文本语义相似度计算的子任务。目前针对句子级别的文本语义相似度即句子相似度有许多较为成熟的计算方法,例如编辑距离(Levenshtein Distance,LD)算法[7]、Jaccard系数[8]和词频-逆文档频率(Term Frequency-Inverse Document Frequency,TF-IDF)算法等,但是这些方法都有着明显的不容忽视的局限性和缺点:编辑距离算法仅考虑两个句子相互转换的操作次数,忽视了操作本身引起的语义差异;基于句子间共现词计算句子相似度的Jaccard系数只考虑句子的字面量,忽视了词语的语义信息[9];TF-IDF算法需要一个大规模语料支撑统计运算[6],而对于某些领域(如军事领域),这样的大规模语料是难以获得的。近年来,随着深度学习技术的兴起,许多基于深度学习的文本相似度算法也随之涌现。但这些算法往往需要大量的语料作为支撑,同时由于深度神经网络本身的特点,因此其对计算时间和计算资源的要求都很高,而深度学习本身的黑箱性质也导致模型难以解释。

词向量技术在自然语言处理(Natural Language Processing,NLP)领域被广泛应用,其通过无监督学习从大规模语料中获取词的高维向量表示,能够很好地捕捉词语的语法和语义信息[9]并准确计算词语间的语义相似度。本文基于词向量对Levenshtein相似度算法和Jaccard系数进行改进,提出一种新的句子相似度算法。通过分析对比多种句子相似度算法的优缺点和应用场景,设计多相似度特征的组合应用模式,并使用改进后的句子相似度算法在MRPC[10]释义识别数据集上进行释义识别实验。

1 相关工作

句子相似度计算可分为基于字重叠的方法、基于语言学的方法和基于语料库的方法3类[6]。

基于字重叠的方法主要通过两个句子共有的词汇量来计算句子间的相似度,典型代表为Jaccard系数,其以两个句子中词汇交集与词汇并集的比值作为句子相似度。基于字重叠方法的基本思想是两个句子的构成短语或词汇的重叠个数越多,其相似度就越大,但这类方法都是字面层次的文本比较,未考虑词语本身含义,因而使用范围受到一定限制(如无法解决同义词问题)。

基于语言学的方法通过计算构成两个句子的词之间的语义关系和语法成分来确定句子间的相似度(如基于句法分析找到句子中各部分的依存关系或语义关系,在计算相似度的同时考虑词语相似度和关系相似度),该方法支持较为丰富的语义,但是句子本身的复杂性为框架分析带来较大的难度和工作量。

基于语料库的方法将文本表示为一系列词语的组合,把基于语料库统计的向量的余弦相似度作为句子对的相似度,而不考虑词语的语序和含义,典型代表为TF-IDF算法。TF-IDF的基本思想是字词的重要性随其在文档中出现的次数正比增加,但同时会随其在语料库中出现的频率反比下降。这类方法需要一个大的文本语料库做统计运算,而这类语料库在某些具体领域是难以获得的,例如军事领域。

随着词向量在自然语言学习领域的广泛使用,出现了大量基于词向量的句子表示学习方法,主要可分为无监督学习和有监督学习两类。

无监督学习方法包括TF-IDF加权句向量[11]、SIF加权句向量[12]、Paragraph Vector DM/DBOM[13]、FastSent[14]、Skip-Thought Vector[15]和SDAE[14]等。TF-IDF加权句向量和SIF加权句向量是基于词袋(Bag of Words,BOW)模型的改进方法,这类方法通过对句子中词向量的加权组合得到句子的向量表示,忽略了词序信息,但简单高效,在一些任务中取得了较好的结果。Paragraph Vector DM/DBOM分别基于word2vec中的CBOW模型和skip-gram模型[16]。Skip-Thought Vector模型利用word2vec中的skip-gram模型进行从词级别到句子级别的推广,即对当前句子进行编码后再对其周围的句子进行预测。该模型采用Encoder-Decoder架构,由于使用了GRU网络,因此模型训练速度慢。SDAE(Sequential Denoising AutoEncoder)采用基于LSTM的Encoder-Decoder模型,包括编码器和解码器两部分,输入信息通过编码器产生编码信息,再通过解码器得到输出信息,模型的目标是使输出信息和输入信息越来越接近,相较于Skip-Thought Vector的优点是只需要输入单个句子,不要求句子所在的文本是有序的,而Skip-Thought的输入必须是3个有序的句子。FastSent利用Skip-Thought Vector的设计思想以及BOW形式的编码方式,使得模型训练速度得到大幅提高。此外,研究者还提出一种FastSent的变体模型FastSent+AE,其不仅预测前后两个句子中的词,同时还预测本身句子中的词。

有监督学习方法包括InferSent[17]和GenSen[18]等。InferSent采用了迁移学习的方法,其从SNIL数据集[19]训练得到Encoder,然后使用预训练的Encoder生成句向量用于其他任务。该模型能够获得较优的结果,但其采用BiLSTM网络,训练速度较慢,而且对于数据集规模的要求较高。GenSen则是一种基于多任务学习的模型,其同时在多个任务和多个数据源上进行训练但共享相同的Sentence Embedding,这与Skip-Thought Vector 基本一致,主要区别在于Encoder 部分使用的是Bi-GRU,因此,该模型训练速度同样较慢。

2 句子相似度算法

2.1 全匹配相似度

文献[20]提出了用于机器阅读理解的文档-问题(QE)全匹配特征。对于文档中的某个词,假设该词在问题中出现,则其QE全匹配特征为1,否则为0。该特征从词的共现出发,一般而言,文档中包括问题词的部分更可能含有答案。本文基于这一思路,提出句子间的全匹配相似度指标,定义如下:

定义1给定句子T、S以及预训练的词向量文件emb,对于句子T中的某个词t,其与句子T的全匹配特征为:

(1)

其中,s为句子S中的某个词,下标emb表示取该词的词向量。对于句子T,该句与S的全匹配相似度如式(2)所示:

(2)

其中,‖·‖表示句子包含的词数。

全匹配特征能够反映句子间词是否共现。一般而言,若句子T中的词在句子S中出现,那么这两个句子更可能相似。考虑到自然语言中存在大量的多词一义现象,因此,本文不直接考察文本词是否在查询中出现,而是通过词向量之间的相似度度量某个文本词的词义是否在查询中出现。

2.2 Jaccard系数及其改进

2.2.1 Jaccard系数

Jaccard系数又称为Jaccard相似系数,可用于比较有限样本集之间的相似度与差异性,系数值越大,样本相似度越高[9]。直观上而言,两个句子的相同部分越大,共现词汇数目越多,它们的相似度应该越高。因此,可以使用Jaccard系数计算两个句子间的相似度,如式(3)所示:

(3)

其中,Inter(S,T)表示句子S和句子T之间的词汇交集,Union(S,T)表示句子S和句子T之间的词汇并集。

2.2.2 改进的Jaccard系数

传统的Jaccard系数未考虑词的语义,只是单纯地基于共现词计算句子的相似度,无法处理多词一义的情况,如“I hava a computer.”和“I have a PC.”,显然两句在语义上是相等的,而传统Jaccard系数在计算过程中却无法识别“computer”和“PC”为语义一致,所得到的Jaccard系数仅为0.6。

词向量是每个词语在语义层面的高维向量表示,本文结合词向量对传统的Jaccard系数进行改进。改进后的Jaccard系数定义如下:

定义2给定句子T、S、预训练词向量文件emb以及词向量相似度阈值α(α≥0)。T和S间的改进Jaccard系数如式(4)所示:

(4)

其中,下标emb代表取该词的词向量,‖T‖·‖S‖表示句子T和S的长度乘积。

在改进的Jaccard系数定义式中,分子部分代表句子T和S中词向量的相似度之和,相较于传统的Jaccard系数方法,改进后的Jaccard词向量匹配特征由于引入了词向量,不仅能够反映句子间词的共现情况,而且还能反映词向量的共现值。分母部分实际上包括了分子部分以及句子T和S中词向量的不共现度,因此,0≤Jaccard(T,S)≤1。

2.3 Levenshtein相似度算法

2.3.1 Levenshtein距离及相似度算法

Levenshtein距离是指两个字符串之间由原字符串S转换为新字符串T所需要的最少编辑次数,允许的编辑操作包括插入、替换、删除[21]。

基于Levenshtein距离能够计算字符串间的相似度,如式(5)所示:

(5)

其中,l为字符串S与T间的Levenshtein距离。Lsim值越大,表示两个字符串相似度越高;Lsim值越小,表示两个字符串相似度越低。同样,对于句子而言,以词为单位进行插入、删除和替换操作即可得到句子级别的Levenshtein相似度。

2.3.2 基于编辑操作排序的路径回溯算法

目前对于Levenshtein相似度的求解一般使用动态规划算法。假设有两个字符串S和T,S={s1,s2,…,sN},T={t1,t2,…,tM},建立S与T的(N+1)(M+1)阶LD矩阵,如式(6)所示:

(6)

在LD矩阵中,第1列代表字符串S,第1行代表字符串T,dij表示从字符串{s1,s2,…,si}到字符串{t1,t2,…,tj}所需的最少编辑次数。矩阵填充公式如下:

其中,i=1,2,…,N,j=1,2,…,M,矩阵右下角元素dNM为字符串S和T之间的Levenshtein距离,记为ld。

在LD矩阵基础上,可以回溯得到编辑路径。需要注意的是,在编辑路径回溯时可能产生多条编辑路径[16],而通过实验可以发现,不同编辑路径计算得到的Levenshtein词向量距离是不同的。为避免回溯路径对相似度造成影响,本文设计基于LD矩阵的编辑路径回溯算法,通过对编辑操作的优先级排序得到唯一的回溯路径。算法描述如下:

算法基于编辑操作排序的编辑路径回溯

1.Input S,T,operation_rank

//输入源字符串、目标字符串和编辑操作排序

2.Initialize LD matrix,i=len(S),j=len(T),list_operation=[]

//初始化LD矩阵、回溯指针及回溯路径

3.While i>= 0 and j>=0://编辑路径回溯

{

coordinate=[i,j]//记录当前编辑操作发生的位置

If i==0:operation=“insert”;

elif j==0:operation = “delete”;

Else://根据编辑距离和编辑操作排序选择编辑操作

{

candidate_operation={“replace”:LD(i-1,j-1),“insert”:

LD(i,j-1),“delete”:LD(i-1,j)}

sorted_operation=sort(candidate_operation,by={value,operation_rank},descending=False)

operation=sorted_operation[0]

}//更新回溯指针

If operation==“delete”:j=j-1;

elif operation==“insert”:i=i-1;

else:i=i-1,j=j-1;

list_operation.append([operation,coordinate])//更新回//溯路径

}

4.Output list_operation//输出回溯路径

由于算法指定了编辑操作的优先级排序,因此在进行LD矩阵回溯时,每一步的回溯操作都是唯一的,即能够得到唯一的回溯路径。根据分析可知,该算法的空间复杂度和时间复杂度仅与2个字符串的长度有关,其中空间开销即LD矩阵的存储开销为O(MN),时间开销即回溯的次数,若M>N,则时间复杂度为O(M),否则为O(N)。需要注意的是,“replace”本质上并不是Levenshtein算法规定的替换操作,而是指在进行字符串转换时直接从原字符串复制字符到目标字符串中,但是为了统一符号,本文将其看作一种特殊的待替换字符与替换字符执行相同的替换操作。

2.3.3 改进的Levenshtein相似度算法

传统的Levenshtein相似度算法从字符串互相转换的角度出发计算需要的最少编辑操作次数,能够从一定层面上反映句子间的相似性。但是仅考虑所需编辑操作次数而不考虑编辑操作本身引起的语义差异是不够的。假设有句子S、T和Q,分别为“I have a computer.”“I have a PC.”和“I have a TV.”,根据传统的Levenshtein相似度算法,3个句子两两之间都只需要一次替换操作即可完成转换。实际上句子S与T的语义一致,而S与Q、T与Q的语义差异更大,这是因为不同的编辑操作对句子语义的改变是不同的,将“computer”替换为“PC”并未对语义造成影响,因为“computer”与“PC”是等价的,而将其替换为“TV”则会引起较大的语义改变。

针对上述问题,本文通过引入词向量对Levenshtein距离算法进行改进。改进算法的具体步骤如下:

步骤1给定句子T和S,l=max(‖T‖,‖S‖),计算两者间的LD矩阵。

步骤2通过LD矩阵回溯编辑路径并记录路径。

步骤3对于编辑路径中的删除和插入操作,将其转换为特殊的替换操作,即删除操作等价于将待删除字符替换为空字符,插入操作等价于将空字符替换为待插入字符。

步骤4对于编辑路径中的所有操作,通过词向量计算替换操作两个字符的相似度并累加,将得到结果记为Lemb,即Levenshtein词向量距离。

步骤5输出改进的Levenshtein相似度1-Lemb/l,记为Lsim′。

根据改进的Levenshtein相似度算法对例句S、T和Q计算,从S转换到T和从S转换到Q都只需要一次替换操作,但由于“computer”与“PC”的语义相近,“computer”与“TV”的语义相差较大,因此有:Lemb(S,T)Lsim′(S,Q)。

可以看出,改进后的Levenshtein相似度算法相较于传统Levenshtein相似度算法能够更准确地刻画句子之间的语义相关性。

2.4 多相似度特征组合分析

Jaccard系数和Levenshtein相似度是目前常用的句子相似度计算方法,两者从不同的角度刻画了句子间的相似度。Jaccard系数从集合论的思想出发,利用句子间共现词占全部词的比例反映句子的相似度,但忽视了句子语序的影响,而Levenshtein相似度则通过句子间相互转换所需操作次数来衡量句子相似度,一定程度上考虑了句子间的语序。两种方法本质上都是基于字面量的匹配方法,虽然取得了一定的效果,但都无法解决多词一义问题。因此,本文引入词向量这一词语语义的高维表示方法对上述算法进行改进,提出一种新的相似度算法。改进后的Jaccard系数和Levenshtein相似度不仅能够反映句子间字面量的相似性,而且能够应对多词一义的情况。然而需要指出的是,改进后的Jaccard系数和Levenshtein相似度由于使用了词向量作为支撑,因此词向量的质量对于算法性能有较大影响,而对于一些专有名词如人名、地名或专业领域(如医学、生物、建筑等)词汇,这些词汇往往不可替代且出现次数较少。因此,词向量无法完全反映其语义信息甚至难以获得这类词的词向量,而传统Jaccard系数和Levenshtein相似度在面对此类句子时则较为有效。

多种句子相似度指标的组合能够有效结合各类指标的优点。传统的Jaccard系数和Levenshtein相似度对于专有名词表现更好,而改进的Jaccard系数和Levenshtein相似度则对通用词汇间的多词一义现象更具优势。全匹配特征类似于Jaccard系数,其直接通过词的共现判断句子相似度,但没有采用集合论方法,因此能够反映词频信息。本文将句子对的Jaccard系数、Levenshtein相似度、全匹配相似度、改进后的Jaccard系数与Levenshtein相似度共5种相似度指标相结合作为特征向量,共同描述句子对间的相似度关系,然后根据这一特征向量判断句子间的语义等价关系,从而避免信息的遗漏和丢失,增强算法的健壮性。

3 实验

3.1 数据集与评价指标

本文选用微软发布的通用语料集MRPC进行实验。MRPC数据集是一个用于释义识别任务的数据集,包含取自互联网新闻文章的4 076对训练句子和1 725对测试句子,每个句子对由两位评估人员判断其语义是否等价,该数据集样本分布如表1所示。

表1 MRPC数据集样本分布

给出如下数据集示例,其中,“#1 String”和“#2 String”是被测试的句子对,Quality表示句子对是否语义等价,取值为{0,1}。

Quality#1 ID#2 ID#1 String#2 String

1702876702977Amrozi accused his brother,whom he called "the witness",of deliberately distorting his evidence.Referring to him as only "the witness",Amrozi accused his brother of deliberately distorting his evidence.

021087052108831Yucaipa owned Dominick′s before selling the chain to Safeway in 1998 for $2.5 billion.Yucaipa bought Dominick′s in 1995 for $693 million and sold it to Safeway for $1.8 billion in 1998.

MRPC数据集以准确率(accuracy)和F1值作为评价指标,其定义如下:

其中:TP为预测为等价并且实际上等价的样本数量;TN为预测为不等价并且实际上不等价的样本数量;FP为预测为等价但实际上不等价的样本数量;FN为预测为不等价但实际上等价的样本数量[6]。

3.2 相似度计算与模型训练

首先对句子进行预处理,然后计算句子对的Jaccard系数、Levenshtein相似度、全匹配相似度、改进后的Jaccard系数与Levenshtein相似度5种相似度指标。其中,分词方法选用python的spacy包,词向量选用300维的谷歌预训练词向量[22](下载地址为nlp.stanford.edu/data/glove.840B.300d.zip),改进Jaccard系数算法的参数,并将Levenshtein距离计算中路径回溯算法的编辑操作优先级排序为[replace,delete,insert]。

由于各类相似度取值都较为接近,简单的特征加权算法会丢失大量信息,因此在完成各类相似度计算后,采用分类模型进行释义识别。以5种相似度指标值为样本特征,以句子对是否语义等价为类别标签,选用多种常用机器学习分类算法对训练数据进行训练,包括梯度提升树(Gradient Boosting Decision Tree,GBDT)、支持向量机(Support Vector Machine,SVM)、朴素贝叶斯(Naïve Bayes,NB)、K近邻分类(K-Nearest Neighbor algorithm,KNN)、决策树(Decision Tree,DT)、随机森林(Random Forest,RF)和逻辑回归分类(Logistic Regression,LR)。

3.3 实验结果与分析

3.3.1 分类算法对比实验

表2记录了基于多相似度特征不同分类算法在MRPC数据集上的表现,其中黑体表示最优结果。可以看出,表现最好的是SVM算法和LR算法。SVM算法的F1值达到83.69%,准确率为73.62%。LR算法虽然在F1值上略逊色于SVM算法,为82.12%,但准确率的表现更好,达到了74.14%。KNN算法、DT算法和RF算法整体表现较差,笔者认为这与数据中类别不平衡和特征相关性有关。由表1可见:MRPC数据存在一定的类别不平衡现象,其语义等价样本数和语义不等价样本数的比值约为2∶1,同时作为样本特征的5类相似度指标存在一定的相关性;KNN算法容易受到类别不平衡影响,决策树算法不仅受类别不平衡影响较大,而且还容易过拟合,因此,两者表现较差,而基于决策树的随机森林算法同样无法避免这个问题;SVM算法基于结构风险最小化原则,能够避免过拟合问题,泛化能力强,并且SVM是一个凸优化问题,其局部最优解必定为全局最优解,而LR算法不容易受到特征间相关性的影响,因此,这两种算法取得了较好的实验结果。

表2 不同分类算法在MRPC数据集上的准确率和F1值

由于表2所示的实验结果是在未做进一步模型调参下获得的,即使是表现最差的决策树算法也依然取得了准确率63.48%和F1值72.30%的结果,表明输入特征能够有效区分句子间的语义相似度。

3.3.2 本文算法与其他算法的对比实验

根据表2不同分类算法的表现结果,本文选择SVM算法训练分类模型,同时应用超参数搜索和交叉检验等方法提升模型表现,其与现有其他模型的准确率和F1值比较如表3所示,其中黑体表示最优结果,†表示在文献[20]基础上通过迁移学习得到的新模型。可以看出,本文模型准确率为74.4%,F1值为82.6%,位居第三,并且与前两名实验结果差距较小。

表3 使用不同句子相似度算法的释义识别模型性能对比Table 3 Performance comparison of paraphrase recognition models using different sentence similarity algorithms %

表3中的模型都需要大规模语料库或深度学习模型进行支撑。如第1组和第2组中的Unigram-TFIDF、Paragraph Vec和SDAE、FastSent、Skip Thought等无监督表示学习方法都是在Toronto book corpus (该语料库大小约70 MB,由来自7 000多本书的有序句子组成)上训练得到,并且这两组模型最好的实验结果分别为准确率73.9%、F1值82.0%和准确率73.0%、F1值82.0%,相较本文模型的实验结果仍有一定差距。第3组中的方法通过有监督训练学习得到句子表示,然后基于句子的表示进行释义识别,仅有InferSent和GenSen两种模型比本文模型表现得更好。但是InferSent模型的结果是基于SNLI和MultiGenre NLI(该数据集是SNLI的增强版本,包括433k个句子对)两个数据集[23]训练得到的,而当InferSent模型在SST数据集[24](该数据集仅包括12k个样本)上进行训练时仅能得到准确率72.7%和F1值80.9%的实验结果,相较于本文模型的实验结果低了2个百分点,说明该模型的表现受到语料数量的限制。此外,InferSent模型使用了BiLSTM-Maxpooling作为编码器,这导致其训练时长和计算资源需求都十分巨大,根据官方代码,该模型的参数量约为47 MB。GenSen模型基于GRU的Encoder-Decoder架构,同时使用了多任务学习,这种方法同样对于计算资源和语料的要求都十分巨大,而在不进行多任务学习的情况下其表现为准确率72.4%、F1值81.6%,与本文模型相比仍略有差距。

相比上述模型,本文基于改进文本相似度的释义识别模型仅使用了通用的预训练词向量,计算过程也只包括相似度指标计算和简单的机器学习分类模型训练两部分,因而实验结果较优,证明了本文对文本相似度算法的改进是有效的,并且可将该算法作为一种简单但优秀的基线模型用于后续的释义识别任务研究。

4 结束语

本文针对现有句子相似度算法存在的不足,结合词向量技术对传统的Levenshtein相似度算法和Jaccard系数进行改进,提出一种新的句子相似度算法。在通用MRPC数据集上的实验结果表明,该算法能够提高准确率和F1值,可作为一种简单有效的基线模型用于后续的释义识别任务。下一步将拓展更多的句子相似度度量指标,同时加快算法的计算速度。