word order and functional word_s盒算法[通俗易懂]

         在做NLP项目的时候，要计算两个文本的相似度——字面上语义的相似，一般而言在文本比较短的情况下，采用bert模型学习到文本向量然后使用cos函数计算余弦相似性。当文本较长的时候，目前没有一个很好的解决方案——最近谷歌提出了一个基于文档级别的transformer模型，可以学习到长度为2048的文本向量，代码还没有放出来，我几乎是实现不了的——我们这边就会采取提取关键词来做相似性的计算。来度量这一批关键词的相似性，就可以使用WMD算法，也就是词移距离；现在又出来了WRD算法，它是基于WMD算法的基础上提出的一种新的算法，克服了WMD算法的一些局限性。很值得被用到工程实践中。苏剑林大佬写一篇博客，详细的介绍了EM、WMD和WRD算法，文章地址——从EMD、WMD到WRD：文本向量序列的相似度计算

一、WRD算法概览和参考实现

这部分的内容，直接是转载苏剑林大佬的文章的。内容如下：

WMD其实已经挺不错了，但非要鸡蛋里挑骨头的话，还是能挑出一些缺点来：

1、它使用的是欧氏距离作为语义差距度量，但从Word2Vec的经验我们就知道要算词向量的相似度的话，用coscos往往比欧氏距离要好；

2、WMD理论上是一个无上界的量，这意味着我们不大好直观感知相似程度，从而不能很好调整相似与否的阈值。

为了解决这两个问题，一个比较朴素的想法是将所有向量除以各自的模长来归一化后再算WMD，但这样就完全失去了模长信息了。最近的论文《Word Rotator’s Distance: Decomposing Vectors Gives Better Representations》则巧妙地提出，在归一化的同时可以把模长融入到约束条件p,qp,q里边去，这就形成了WRD。

基本形式 #

首先，WRD提出了“词向量的模长正相关于这个词的重要程度”的观点，并通过一些实验结果验证了这个观点。事实上，这个观点跟笔者之前提出的simpler glove模型的观点一致，参考《更别致的词向量模型(五)：有趣的结果》。而在WMD中，pi,qjpi,qj某种意义上也代表着对应句子中某个词的重要程度，所以我们可以设

代码实现参考

def wasserstein_distance(p, q, D):
    """
    通过线性规划求Wasserstein距离——EMD距离——推土机距离
    p.shape=[m], q.shape=[n], D.shape=[m, n]
    p.sum()=1, q.sum()=1, p∈[0,1], q∈[0,1]
    :param p:关键词向量序列或者字向量序列
    :param q:关键词向量序列或者字向量序列
    :param D:
    :return:
    """
    A_eq = []
    for i in range(len(p)):
        A = np.zeros_like(D)
        A[i, :] = 1
        A_eq.append(A.reshape(-1))
    for i in range(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])
    return result.fun

def word_rotator_distance(x, y):
    """WRD（Word Rotator's Distance）
    x.shape=[m,d], y.shape=[n,d]
    """
    x_norm = (x**2).sum(axis=1, keepdims=True)**0.5
    y_norm = (y**2).sum(axis=1, keepdims=True)**0.5
    p = x_norm[:, 0] / x_norm.sum()
    q = y_norm[:, 0] / y_norm.sum()
    D = 1 - np.dot(x / x_norm, (y / y_norm).T)
    return wasserstein_distance(p, q, D)

def word_rotator_similarity(x, y):
    """1 - WRD
        x.shape=[m,d], y.shape=[n,d]
        """
    return 1 - word_rotator_distance(x, y)

给定一个向量对X和Y，以上代码就可以实现WRD距离的计算，得出想要的文本距离。

二、WRD算法的应用

背景如下：现有query 文本100条，待匹配的match数据有400W条。可以使用word2vec把文本数据转化我词向量，然后根据文本对的所有词向量来计算两个文本之间的WRD距离，把每个query最相似的10条推荐出来！

先看看WRD计算一次的消耗时间：

    kw_vecotr = np.random.randn(10,100)
    ele = np.random.randn(7,100)
    t1 = time.time()
    word_rotator_similarity(kw_vecotr, ele)  # 0.02s
    t2 = time.time()
    print('word_rotator_similarity time is %.4f'%(t2-t1))

python WRD_recomm.py 
wasserstein_distance linprog time 0.0227
word_rotator_similarity time is 0.0230

计算一次的时间就是0.023秒，其实耗费的时间全部在如下函数中的线性规划求解中：

def wasserstein_distance(p, q, D):
    ...
    result = linprog(D, A_eq=A_eq[:-1], b_eq=b_eq[:-1])#线性规划求解
    ...

一般的逻辑流程这里需要进行100*400W次计算，然后排序得到结果。最少的时间是4亿*0.023s =106天，采用多进程10个进程也需要10天，一条结果需要十分之一天，大约2.4个小时！所以需要进行优化。在从EMD、WMD到WRD：文本向量序列的相似度计算文章中作者提到了一个下界公式，在计算WRD之前，用一种高效的、不精确的算法把待匹配样本过滤一些，从而减少计算成本。我们这里的场景下，就是减小400W，给缩减到几十几百几千，就能极大的提高每条query得到结果的速度！

下界公式

公式来自文章

我尝试的给出代码实现如下：

def dis_lower_boundary(x,y):
    """
    wrd的一个下界距离
    """
    x_norm = (x ** 2).sum(axis=1, keepdims=True) ** 0.5
    y_norm = (y ** 2).sum(axis=1, keepdims=True) ** 0.5
    z_x = x.sum(axis=0)/x_norm.sum()
    z_y = y.sum(axis=0)/y_norm.sum()
    dis = ((z_x-z_y) ** 2).sum()**0.5 * 0.5
    return dis

可以看看计算400W次dis_lower_boundary需要的时间是多少：

    kw_vecotr = np.random.randn(10, 100)
    ele = np.random.randn(7, 100)
    t1 = time.time()
    dis_lower_boundary(kw_vecotr, ele)  # 0.02s
    t2 = time.time()
    print('dis_lower_boundary 1  time is %.6f' % (t2 - t1))
    t1 = time.time()
    for i in tqdm(range(4000000)):
        dis_lower_boundary(kw_vecotr, ele)  # 0.02s
    t2 = time.time()
    print('dis_lower_boundary 4000W time is %.6f'%(t2-t1))

结果显示：

可以看到只需要126秒。设置合适的过滤值，可以把400W缩减到5K级别。一条query得出的结果为0.023*5000+126=241s！相比之前没有采用下界公式过滤的2.4个小时10000S，提升了很多！把多进程也考虑进来241s还可以进一步优化到10s以内。如果能把线性规划的求解时间再缩小10倍，那么提升的将会更大！

这里主要的是大数据量的情况下，时间效率问题的解决方案的一个探索！

总结

本文就WRD算法在具体业务场景下进行简单的应用，并初步解决一定的效率问题。首先从苏剑林大佬的文章出发，简单介绍了WRD算法的原理和代码实现，其次就具体的业务场景下，如何使用WRD算法以及碰到了效率问题的时候，如何使用WRD算法下界公式来优化提升效率，做了详细的说明。这里并没有涉及到算法最后推荐效果的分析，这个又是另外一个层面的问题了，不做介绍！

参考文章

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

今天的文章word order and functional word_s盒算法[通俗易懂]分享到此就结束了，感谢您的阅读。