钮 焱 李 星 李 军 刘宇强 Jepkemei Judith

（湖北工业大学 武汉 430068）

1 引言

随着人工智能技术的日益深入，自然语言处理领域的研究变得越来越重要。句子语义相似度的计算作为自然语言处理领域基本且核心的问题，在很多人工智能领域有着广泛的应用，例如，在机器翻译、语音识别、文字情感识别、自动作文等方面，均需要用相似度模型来衡量文本中词语的可替换程度或计算问题与答案的匹配程度。相似度计算也成为备受众多自然语言处理研究者关注的研究课题。

目前，随着词向量概念的提出，很多研究学者将传统的相似度算法与词向量结合起来，在短文本相似度计算的准确率上有很大的提升。田星等［2］在解决短文本相似度的问题上，将传统的Jaccard算法与词向量相结合，以语义层面的高维向量代替原来句子的字面量，通过计算词向量间的相似度，以自设定的阈值来区分共现部分，在相似度的准确率上有明显的提升，但是该算法在中文文本相似度的计算上效果不尽人意。针对汉语句子，李茹等［10］提出结合汉语框架语义对句子进行框架语义分析，来达到刻画句子语义的目的，由此计算的相似度效果传统的方法更好，但是现有的汉语语义资源中框架的覆盖率较低，在进行语义分析时有局限。针对基于路径方法中普遍存在的密度不均匀性问题，郭承湘等［3］提出了融合路径距离与信息内容方法，通过一个平滑参数将路径和信息内容融合调整概念间的语义距离，使路径方法计算的相似度值更加合理，以此方法计算句子相似度具有较强的鲁棒性，但是一些词典的特殊性使得信息内容的方法体现不出任何效果。针对短文本数据稀疏和缺乏语义的问题，黄栋等［5］提出词向量和EMD距离相结合的方法，使用Skip-gram 模型训练得到特征词语义的词向量，使用欧式距离计算特征词相似度，使用EMD 距离计算句子相似度，与传统方法相比有很大提升，但是算法中未考虑词性和语序的影响。

针对以上研究缺点，我们提出了一种基于DTW 和改进匈牙利算法的语义句子相似度算法模型。由于中文词语具有较为丰富的语义信息，为了更好地比对词语间的相似度，先用神经网络训练语料，获得具有200 维语义信息的特征向量，再通过DTW 将分词模拟成空间中的点，将句子模拟成空间中的曲线，把两个句子相似度的计算转换为空间中两条曲线相互变换的距离和复杂度，以此解决了汉语语义的问题，通过匈牙利算法寻找两个句子相互转换的最优方案，以此解决了句子语序的问题。通过实验测试，本文使用的方法在汉语句子相似度计算上相对于传统的计算模型有较好的效果。

2 相关技术介绍

2.1 词向量

词向量指的是用低维实数向量表示一个词，词向量每一维的值代表一个具有一定语义和语法上解释的特征。由此，可通过词向量间的距离来从语义、语法上比较两个词之间的相似度。本文的词向量是依据百度新闻语料库，通过Word2vec 优化训练得到的。Word2vec 是Google 公司在2013 年开放的一款用于训练词向量的软件工具，其内部转化主要运用的是神经网络算法，因此，词向量可以称为将深度学习算法引入NLP 领域的一个核心技术。Word2vec 模型有两种：CBOW 模型（见图1）和Skip-gram 模型（见图2）。CBOW 模型利用词w（t）前后各c（c=2）个词预测当前词；而Skip-gram 模型利用词w（t）预测其前后各c 个词。本文通过Word2vec 训练得到汉语词语对应的语义特征词向量，再通过距离计算得到词语相似度。由于词向量包含语义特征，所以计算的相似度值更加可靠。

图1 CBOW模型

图2 Skip-gram模型

2.2 DTW距离

给定两个时间序列X=[x1,x2,…,xnx]∈Rd×nx和Y=[y1,y2,…,yny]∈Rd×ny，DTW 是一种使式（1）平方和成本最小化的X，Y样本最佳对齐技术：

其中m是对齐两个序列所需的索引数量，对应矩阵P 可以由一对路径向量参数化，P=[px,py]T∈R2×m，其中px∈{1:nx}m×1，py∈{1:ny}m×1表示帧中对齐的组成。例如，对于一些t，如果存在pt=，则X 中第i 帧与Y 中第j 帧对齐。P必须满足三个额外的约束：边界条件(p1≡[1,1]T和pm≡[nx,ny]T) ，连续性(0 ≤pt-pt-1≤1) ，单调性（t1≥t2⇒pt1-pt2≥0）。尽管对齐X 和Y 的可能方式的数量在nx和ny中是指数的，动态编程通过使用贝尔曼等式提供了一种有效的途径来最小化Jdtw：

成本函数值L*(pt)表示，基于最优策略π*，从第t 步开始的剩余代价。策略π:{1:nx}×{1:ny}→{[1,0]T,[0,1]T,[1,1]T}定义了连续步骤之间的确定性转换：pt+1=pt+π(pt)。确定了策略队列，就可以从起始点开始递归地构造对齐步骤pt=[1,1]T。

2.3 匈牙利算法

匈牙利算法的目的主要是为了寻求最大匹配或最小匹配值。给定一组成员X={x1,x2,x3,x4,x5}和一组任务Task={A,B,C,D,E}，每个成员完成任务的工时不同，求解所有任务完成所用的总工时最少的指派方案。指定kij表示成员i完成任务j的标记值（0或1），首先确定约束条件：

改进算法实现步骤如下：

第一步：列出成员任务的效率矩阵T，T 中每一项的值Tij表示成员i完成任务j需要的工时。查看矩阵T中每行的最小元素的个数总和r和每列的最小元素的个数总和c，比较r 和c 的大小。当r ≥c，则先从系数矩阵的每列减去该列的最小元素，再从所得系数矩阵的每行元素中减去该行的最小元素。反之如果当r ≤c，则先从系数矩阵的每行中减去该行的最小元素，再从所得系数矩阵的每行元素中减去该列的最小元素。由此，使变换后的效率矩阵T1各行各列都出现0元素。

第二步：进行试指派，在T1中找尽可能多的独立0 元素，若能找出n 个独立0 元素，就以这n 个独立0 元素对应解矩阵T2中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤：

1）从只有一个0 元素的行（列）开始，给这个0元素加圈，记作◎。然后划去◎所在列（行）的其它0 元素，记作Ø ；这表示这列所代表的任务已指派完，不必再考虑其他元素了。

2）给只有一个0 元素的列（行）中的0 元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø。

3）反复进行1）、2）两步，直到尽可能多的0 元素都被圈出和划掉为止。最后得到矩阵T3。

第三步：创建一个与矩阵T 同大小的零矩阵，将T3与中圈0 的位置相同的地方替换成1，得到0-1矩阵R。

第四步：将1的位置同原矩阵T映射的值相加，即得到最少总工时，最优指派方案即为1 对应的横纵坐标（成员与任务）的匹配。

通过上述的步骤可以看出，寻找独立零元素的位置即寻找最优匹配，这就是匈牙利算法的本质。

3 基于DTW 和匈牙利算法的语义句子相似度计算方法

3.1 词向量的计算

本文研究用到的数据为2016 年～2018 年百度新闻语料数据。通过Word2vec 结合神经网络学习的方法训练出6万条具有200维特征的词向量数据形成词向量库，经过此方法获取的词向量包含了汉字的语义信息。从语料库中选着或人工组合出长度小于30 个汉字的几个句子。通过检索词向量库得到每个句子对应的词向量数组。

3.2 DTW矩阵的计算

针对实验中两个需要计算相似度的汉语句子S1和S2，通过jieba 分词将其划分成长度分别为m和n 的词组，从词向量库中检索出对应的词向量，得到句子S1和S2对应的词向量数组Vec1和Vec2。将词向量数组Vec1和Vec2中每个分量相互求DTW 距离，最终得到一个大小为m×n 的DTW 矩阵Ddtw。本文在DTW 定义的基础上做了一定的调整，使计算的流程更加简洁，计算两个向量V 和U间DTW距离的方法如下。

第一步：确定初始向量V=｛v1,v2,v3,v4｝，U=｛u1,u2,u3,u4,u5｝，约束条件为向量V 和U 的分量维度相同。计算V 中每个分量与U 中每个分量的欧氏距离，得到矩阵M1（如图3）。

图3 矩阵M1

第二步：由于向量V 和U 的分量在矩阵中是按照一定顺序排列的，所以我们计算向量V 和U的DTW 距离即找到一条从矩阵M1左下角到右上角的最短动态规划距离。设定当从一个方格（（i-1，j-1）或者（i-1，j）或者（i，j-1））到下一个方格（i，j），如果是横着或者竖着的话其距离为d（i，j），如果是斜着对角线过来的则是2d（i，j）。其中约束条件函数如式（6）和式（7）：

式（6）中d(i,j) 表示矩阵M1第i 行第j 列的值；g(i,j)表示两个向量从起始分量开始逐次匹配，已经到达V 的i 分量，U 的j 分量的距离。每一步的计算遵循约束式（6），如：

第三步：按照第二步的计算方法计算矩阵M1中每一处的g(i,j)值，将其写入矩阵值的右上角并用红色标记，结果为矩阵M2（如图4）。

图4 矩阵M2

第四步：由第三步计算结果可得出，向量V 和U 的DTW 距离为18，即到达矩阵右上角的最短动态规划路径距离值。并且可以通过回溯得到最短规划路径，如图4中箭头标出。

通过上述步骤可以总结出动态规划的思路为

3.3 匈牙利算法求解句子相似度

将上一步求得的DTW 矩阵作为初始矩阵进行匈牙利算法计算，由于匈牙利算法要求的是一对一匹配，但是DTW 矩阵可能行列数不等。这里我们进行了填补处理。尝试以向量最大值填补时，发现在求取独立0 元素时会有很大误差，导致最终相似度结果与实际偏差过大。于是以行列中最大值为基准，缺失的部分补0。经过多次测试，行列值均为0 时，在计算的过程中不会对选取独立零元素造成太大影响。填补之后得到一个行列数相等的初始矩阵，按照匈牙利算法的步骤先比较行列最小值数目的总和进行比较，判定先从行开始处理还是先从列开始处理；处理后得到行列均有0 元素的矩阵；接着选取独立0 元素进行位置标记，选择完所有的独立0 元素之后将其位置与初始矩阵映射的值相加得到最短距离值d12（句子S1变换到S2所需的最小距离值），我们将一个词与另一个词的相似度以空间中的距离变化来衡量。由于匈牙利算法计算出独立0 元素的个数count(0)对结果均有影响，延伸出句子相似度的计算公式：

4 实验与结果分析

本文实验训练及测评的数据是从2015 年～2018 年百度新闻语料库中摘录的。使用Google 的Word2vec 模型，将语料分词后通过神经网络模型训练得到每个分词对应的200 维词向量，每一维都包含分词的某一特征语义的信息，形成一个含有6万条词向量数据的词向量库，词向量库数据见表1。

表1 百度新闻语料200维词向量部分数据

4.1 实验流程及结果

选取词向量库中部分分词组合成四条汉语句子（见表2）。

表2 实验中计算相似度的句子

通过检索词向量库，得到每条句子对应的有序词向量数组，以sentence1 作为待匹配句，sen⁃tence2，sentence3，sentence4 作为匹配句，分别计算sentence1 与sentence2，sentence3，sentence4 的DTW矩阵D1，D2，D3，D4；再将D1，D2，D3，D4作为初始矩阵通过匈牙利最优匹配算法分别求出sentence1 与sentence2，sentence3，sentence4 的最短路径值，最后通过式（9）分别计算sentence1 与sen⁃tence2，sentence3，sentence4 的相似度，实验同时使用传统的Jaccard 和TFIDF 方法计算相似度结果，用于对比，结果见表3。

4.2 实验结果分析

首先我们通过人工评判四个句子，经过专家分析观察出sentence1 与sentence2，sentence3 表达的意思几乎是一样的，与sentence4 表达的意思不一样。因此在相似度的比较上应该有：

再观察sentence2 和sentence3 表达的意思与sentence1 几乎是一致的，但是sentence3 的语序杂乱程度要比sentence2 更严重，所以sentence1 变换到sentence3 所耗费的空间距离应该比sentence1 变换到sentence2的要大，因此应该有：

所以从人工评判的结果来看，应该是：

从本文方法实验结果来看：0.9279 ＞0.8961 ＞0.6926，结果与预期相符。而使用传统的句子相似度计算方法Jaccard和TFIDF，得到的结果都为

原因在于两种传统的方法只考虑了两个句子中共有词出现的频率，而没有考虑语义信息和语序的影响，当两个句子的共有词数目相等时无法做出有效的评估。由此表明通过DTW 与匈牙利算法相结合的方法计算含有语义信息和语序结构的汉语句子相似度，具有一定的实际意义和研究价值。

5 结语

本文为了考虑汉语语义和句子语序对句子相似度计算的影响，提出了一种基于DTW 和匈牙利算法的语义句子相似度计算的方法。将原本应用于语音识别和图像识别领域的方法DTW 和解决最优分配问题的匈牙利算法结合起来应用在自然语言处理领域，并且在汉语句子相似度的计算上取得了不错的效果，为自然语言处理领域研究提供了一种全新的方向。由于实验环境的限制，我们还没有进行大量语句的测试，对于不同方法对相似度的影响程度的权值设定可能还不是特别的精准，但是相对于传统的仅从距离的方向进行相似度计算有明显的提高。