PaperWeekly从EMD、WMD到WRD:文本向量序列的相似度计算


北京联盟_本文原题:从EMD、WMD到WRD:文本向量序列的相似度计算
?PaperWeekly 原创 · 作者|苏剑林
单位|追一科技
研究方向|NLP、神经网络
在 NLP 中 , 我们经常要去比较两个句子的相似度 , 其标准方法是想办法将句子编码为固定大小的向量 , 然后用某种几何距离(欧氏距离、cos 距离等)作为相似度 。 这种方案相对来说比较简单 , 而且检索起来比较快速 , 一定程度上能满足工程需求 。
此外 , 还可以直接比较两个变长序列的差异性 , 比如编辑距离 , 它通过动态规划找出两个字符串之间的最优映射 , 然后算不匹配程度;现在我们还有 Word2Vec、BERT 等工具 , 可以将文本序列转换为对应的向量序列 , 所以也可以 直接比较这两个向量序列的差异 , 而不是先将向量序列弄成单个向量 。
后一种方案速度相对慢一点 , 但可以比较得更精细一些 , 并且理论比较优雅 , 所以也有一定的应用场景 。 本文就来简单介绍一下属于后者的两个相似度指标 , 分别简称为 WMD、WRD 。
Earth Mover's Distance
本文要介绍的两个指标都是以 Wasserstein 距离为基础 , 这里会先对它做一个简单的介绍 , 相关内容也可以阅读笔者旧作从 Wasserstein 距离、对偶理论到WGAN。
Wasserstein 距离也被形象地称之为 “推土机距离”(Earth Mover's Distance , EMD) , 因为它可以用一个“推土”的例子来通俗地表达它的含义 。
1.1 最优传输
假设在位置 处我们分布有 那么多的土 , 简单起见我们设土的总数量为 1 , 即, 现在要将土推到位置 上 , 每处的量为, 而从 i 推到 j 的成本为, 求成本最低的方案以及对应的最低成本 。
这其实就是一个经典的最优传输问题 。 我们将最优方案表示为, 表示这个方案中要从 i 中把 数量的土推到 j 处 , 很明显我们有约束:
PaperWeekly从EMD、WMD到WRD:文本向量序列的相似度计算
本文插图

所以我们的优化问题是:
PaperWeekly从EMD、WMD到WRD:文本向量序列的相似度计算
本文插图

1.2 参考实现
看上去复杂 , 但认真观察下就能发现上式其实就是一个 线性规划问题——在线性约束下求线性函数的极值 。 而 scipy就自带了线性规划求解函数linprog , 因此我们可以利用它实现求 Wasserstein 距离的函数:
importnumpy asnp
fromscipy.optimize importlinprog
defwasserstein_distance(p, q, D):
"""通过线性规划求Wasserstein距离
p.shape=[m], q.shape=[n], D.shape=[m, n]
p.sum=1, q.sum=1, p∈[0,1], q∈[0,1]
"""
A_eq = []
fori inrange(len(p)):
A = np.zeros_like(D)
A[i, :] = 1
A_eq.append(A.reshape( -1))
fori inrange(len(q)):
A = np.zeros_like(D)
A[:, i] = 1
A_eq.append(A.reshape( -1))
A_eq = np.array(A_eq)
b_eq = np.concatenate([p, q])
D = D.reshape( -1)
result = linprog(D, A_eq=A_eq[: -1], b_eq=b_eq[: -1])
returnresult.fun
读者可以留意到 , 在传入约束的时候用的是A_eq=A_eq[:-1], b_eq=b_eq[:-1] , 也就是去掉了最后一个约束 。
这是因为, 所以(1)中的等式约束本身存在冗余 , 而实际计算中有时候可能存在浮点误差 , 导致冗余的约束之间相互矛盾 , 从而使得线性规划的求解失败 , 所以干脆去掉最后一个冗余的约束 , 减少出错的可能性 。
Word Mover's Distance
很明显 , Wasserstein 距离适合于用来计算两个不同长度的序列的差异性 , 而我们要做语义相似度的时候 , 两个句子通常也是不同长度的 , 刚好对应这个特性 , 因此很自然地就会联想到 Wasserstein 距离也许可以用来比较句子相似度 , 而首次进行这个尝试的是论文 From Word Embeddings To Document Distances[1] 。


推荐阅读