WMD算法详解

发表于 | 更新于: | 分类于 | | 阅读量: 次

论文:From Word Embeddings To Document Distances

WMD为衡量文本相似度的方法。使用WMD来计算两个文本D1,D2之间的相似度，计算流程如下：

  1. 首先对两个文本去除停用词
  2. 使用归一化BOW(词袋模型)方法来分别表示D1,D2
  3. 使用word2vec embedding来表示D1,D2中的每个词
  4. 在D1中所有词travel到D2中所有词，对于每一个D1中的词，它与D2中的词语义比较相近的，那么可以全部移动或移动距离多一些(权重值)；对于语义差异较大，则移动距离少一点或者不移动。用词向量距离乘以移动距离就是两个词的转移代价。
  5. 求全局的转移代价累加和最小值(D1中所有词全部转移到D2,D2中的所有词也全部转移到D1中)。
  6. 这个全局转移代价累加和的最小值就是D1,D2的相似度。

如下图所示，4个词对之间的词向量欧式距离的累加值就是document1和document2的相似度：

wmd-1

算法的数学描述

假设有一个预训练好的word2vec词向量矩阵，表示词典大小为n，词向量维度为d。

如果词i在文本中出现的次数为 ，那么我们定义词i的归一化词频为:

另外词语距离的定义：词i与词j的欧式距离为：

令和表示分别表示要D1,D2两个文本的归一化词袋表示，中的每个词i都可以全部或者部分转移到的每个词。因此，定义一个稀疏的转移矩阵， 表示d中的词i到中的词j的转移距离。。

那么，从d到的全局转移代价累加和表示为：。

这里需要求出最小的全局转移代价累加和，所以把求最小化问题建模成线性规划问题：

s.t.

WMD的计算过程可视化如下图所示：

wmd-2

以上问题的线性规划问题是EMD算法中的一种特殊情况，具体求解过程可参考EMD算法。

本论文采用了Fast-EMD论文中提出的求解方法：Fast and Robust Earth Mover’s Distances

时间复杂度为，其中p为两个文本移除停用词和去重后词表的大小。

算法改进

如果字典非常大，那么上述的求解方法的计算复杂度太高，我们可以通过使用low bound来减少问题的求解空间。从而提升计算效率。

WCD low bound(词心距离)

根据三角不等式可得 ：

WCD对应的式子为:，，因此对应的时间复杂度为O(dp)，d为词向量的维度。

RWMD low bound(松弛WMD距离)

尽管WCD的时间复杂度很低，但是边界过于宽松，无法很好的近似WMD。因此，这里使用更加tight的下界RWMD。RWMD需要计算两次，基于WMD目标函数，分别去掉两个约束条件中的一个，然后求解最小值，使用两个最小值中的最大值作为WMD的近似值。

比如，去掉约束条件(3-3)，可得:

s.t.

这个问题的最优解是，对于文本D1中的一个词，找到另一文本D2中与之最相近的一个词，全部转移到这个词。即：

使用和分别表示，去掉不同约束条件所计算得到的最小值，RWMD最终的最小值为:

这个的时间复杂度为。

剪枝

接下来讨论如何使用上面的两种下界对WMD进行剪枝。

  • 利用WCD计算出所有的距离，取topK
  • 计算topK文本的WMD值
  • 对于剩下的文本，计算RWMD值，如果RWMD比topK中的WMD最大的小，则替换topK中的WMD最大的文本，并计算它的WMD值，否则，剪枝。

由于RWMD值与WMD值非常接近，因此对于剩下文本，几乎95%都是可以被剪枝的。

在twitter/amazon这两个数据集上，随机抽取一些文本组成句对，将这些句对按WMD值进行升序排列，横坐标为句对编号，纵坐标为WCD,RWMD,WMD的值。从图中可以看出，WCD是非常宽松的下界，而RWMD则与WMD非常接近：

wmd-3

优缺点及改进

优点

  • 不需要设置超参数
  • 无监督，不依赖标注数据，没有冷启动问题
  • 有全局最优解
  • 可人为干预词的重要性

缺点

  • 词袋模型，没有保留语序信息(ngram)
  • 不能处理OOV问题(因为word2vec导致的，这里可以使用fasttext)
  • 处理否定词能力差(加入情感极性信息)
  • 处理领域同义词互斥词的能力偏差(一词多义,elmo?)

代码实现

参考资料：http://www.acme.byu.edu/wp-content/uploads/2014/09/Vol2Lab14.pdf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#WMD的一种简单实现
from gensim.scripts.glove2word2vec import glove2word2vec
from gensim.models import KeyedVectors
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.preprocessing import normalize
import numpy as np
from sklearn.metrics import euclidean_distances
from cvxopt import matrix, solvers

glove_file = "glove.6B.100d.txt"
word2vec_file = "word2vec.6B.100d.txt"
_,_ = glove2word2vec(glove_file, word2vec_file)
glove_model = KeyedVectors.load_word2vec_format(word2vec_file, binary=False) #加载glove词向量

def sent_vectorize(sent1, sent2):
    vectorizer = CountVectorizer(stop_words="english")
    vect = vectorizer.fit_transform([sent1, sent2])
    norm_vect = normalize(vect.toarray(), axis=1, norm='l1')
    vocab = np.array(vectorizer.get_feature_names())
    return vocab, norm_vect

def WMD (sent1, sent2):
    """
		http://cvxopt.org/examples/tutorial/lp.html
    https://scaron.info/blog/linear-programming-in-python-with-cvxopt.html
    """
    #获取词典，以及句子的归一化词集模型向量
    vocab,norm_vect = sent_vectorize(sent1, sent2)
    #分别去掉句子中的停用词
    sent1_words = vocab[np.nonzero(norm_vect[0])]
    sent2_words = vocab[np.nonzero(norm_vect[1])]
    #获取句子中每个单词的词向量
    sent1_word2vec = []
    sent2_word2vec = []
    for word in sent1_words:
        sent1_word2vec.append(glove_model[word]) 
    for word in sent2_words:
        sent2_word2vec.append(glove_model[word])

    #计算sent1中的各个词向量与sent2中的各个词向量俩俩之间的欧式距离
    C_tmp = euclidean_distances(np.array(sent1_word2vec),np.array(sent2_word2vec))
    C = C_tmp.flatten().astype(np.double) #相当于运输单价
    
    n = len(C) #n个变量
    #根据归一化的词集模型向量得到对应的约束条件常数项的向量,分别对应供给量和需求量
    sent1_vec = norm_vect[0][norm_vect[0]!=0]
    sent2_vec = norm_vect[1][norm_vect[1]!=0]

    b_2 = np.zeros(n)
    b_1 = np.concatenate((sent1_vec, sent2_vec)) #相当于lp中的b
    b = []
    for pos,neg in zip(b_1, -b_1):
        b.append(pos)
        b.append(neg)
    b = np.concatenate((np.array(b),b_2)) #供给量和需求量约束条件以及变量均大或等于0的约束条件
    
    #生成约束条件的系数矩阵A
    m1 = len(sent1_vec)
    m2 = len(sent2_vec)
    m = m1+m2 #2m个约束条件，因为这里的等式约束拆分成了两个不等式约束
    A = np.zeros((2*(m1+m2),m1*m2),dtype=np.double)
    for i in range(m1):
        for j in range(m2):
            A[2*i][j+i*m2]=1
            A[2*i+1][j+i*m2]=-1
        
    for i in range(m2):
        for j in range(m1):
            #A[m1+i][i+j*m2]=1
            A[2*m1+2*i][i+j*m2]=1
            A[2*m1+2*i+1][i+j*m2]=-1

    G_1 = np.diag([-1]*n)
    G = np.concatenate((A,G_1))
    
    #转换成cvxopt的矩阵形式
    c = matrix(C)
    G = matrix(G)
    b = matrix(b)

    #lp 问题求解
    solvers.options['show_progress'] = False
    sol = solvers.lp(c,G,b)
    wmd_dist = sol['primal objective'] #最优目标值
    
    return wmd_dist
1
2
3
4
5
6
7
8
9
10
#测试例子
print(WMD("Obama speaks to the media in Illinois","The President addresses the press in Chicago"))
print(WMD("I enjoy working in a bank.","I enjoy working near a river bank."))
print (WMD("people like this car", "those guys enjoy driving that"))
print(WMD("Under US GAAP, gains and losses from AFS assets are included in net income.",
          "Under IFRS, gains and losses from AFS assets are included in comprehensive income."))
print(WMD("people like this car","those guys enjoy driving that"))
print (WMD("Obama speaks to the media in Illinois", "The President greets the press in Chicago"))
print (WMD("the capital of China is Beijing", "the capital of China is Beijing"))
print (WMD("i am studying the course of math ", "you are learning English lesson"))

参考资料