WMD

文章出处

本文为WMD_tutorial的翻译。

使用W2V和WMD发现文档的相似性

WMD(Word Mover’s Distance)是机器学习中一个有前途的新工具,它允许我们提交查询并返回最相似的文档。例如,在博客OpenTable中,使用了WMD分析了餐厅评论。通过使用这种方法,他们能够从评论中挖掘出不同的方面。这本教程的第二部分,我们展示了如何使用gensim的WmdSimilarity去做类似与opentable所做的事情。在第一部分,我们说明了如何使用wmdistance去计算两个文档的WMD距离。如果你的目的是想使用WmdSimilarity,第一部分可以选读,但它是有意义的。

不管怎样,首先,我们浏览下关于wmd是什么的基础知识。

WMD基础

wmd允许我们用一种有意义的方式去评估两个文档之间的距离,即使他们之间没有共同词汇。他使用w2v进行词向量嵌入。它的表现优于很多最先进的k近邻分类方法。

wmd被下面两个非常相似的句子所阐明(图例来源于Vlad Niculae’s blog)。两个句子之间没有共同词汇,但是通过匹配相关词,wmd能够精确度量两个句子之间的相似性。这个方法也使用了文档的词袋表征(简单的说,文档的词频),在下面的图中被标记为d。该方法的直观理解是我们发现文档之间最小的”traveling distance”,换句话说将文档1的分布移向文档2的最有效方式。

这个方法已经在文章“From Word Embeddings To Document Distances” by Matt Kusner et al.中被介绍。它被”Earth Mover’s Distance”激发灵感,并且利用了 “transportation problem”的一个解法。

在本教程中,我们将学习如何使用gensim的wmd函数。它由进行距离计算的wmdistance方法和基于相似查询的corpus计算的WmdSimilarity类构成。

注意:
如果你使用这个软件,请留意引用[1],[2]和[3]。

运行notebook

你可以下载这个iPython Notebook,并在你自己电脑上运行它,如果你已经安装了gensim,pyemd,nltk,并下载了必要的数据。

这个notebook被运行在i7-4770cpu 3.40GHz (8 cores) 和 32 GB memory的ubuntu机器上。在这台机器上运行整个notebook需要话费3分钟。

第一部分:计算词移距离(Word Mover’s Distance)

为了使用wmd,我们首先需要一些词嵌入。你需要在一些corpus上训练一个w2v模型(教程),但是我们将通过下载一些预训练的w2v嵌入模型来开始。下载 GoogleNews-vectors-negative300.bin.gz(警告:1.5GB,第二部分并不需要这些文件)。训练你自己的嵌入模型是有益处的,但为了简化本教程,我们将首先使用预训练的嵌入。

让我们拿一些句子来计算它们之间的相似度。

1
2
3
4
5
6
7
8
9
10
11
from time import time
start_nb = time()

# Initialize logging.
import logging
logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s')

sentence_obama = 'Obama speaks to the media in Illinois'
sentence_president = 'The president greets the press in Chicago'
sentence_obama = sentence_obama.lower().split()
sentence_president = sentence_president.lower().split()

这些句子有很相似的内容,因此wmd应该低。在我们计算wmd之前,我们想要移除停用词(”the”, “to”, etc.),因为它们对句子信息并没有很多贡献。

1
2
3
4
5
6
7
8
9
# Import and download stopwords from NLTK.
from nltk.corpus import stopwords
from nltk import download
download('stopwords') # Download stopwords list.

# Remove stopwords.
stop_words = stopwords.words('english')
sentence_obama = [w for w in sentence_obama if w not in stop_words]
sentence_president = [w for w in sentence_president if w not in stop_words]

现在,正如先前提到的,我们将使用一些下载的预训练嵌入。我们加载这些进入gensim的w2v模型类中。注意我们这里选择的嵌入需要很多内存。

1
2
3
4
5
6
7
8
9
10
start = time()
import os

from gensim.models import KeyedVectors
if not os.path.exists('/data/w2v_googlenews/GoogleNews-vectors-negative300.bin.gz'):
raise ValueError("SKIP: You need to download the google news model")

model = KeyedVectors.load_word2vec_format('/data/w2v_googlenews/GoogleNews-vectors-negative300.bin.gz', binary=True)

print('Cell took %.2f seconds to run.' % (time() - start))

因此让我们使用wmdistance方法计算wmd。

1
2
distance = model.wmdistance(sentence_obama, sentence_president)
print 'distance = %.4f' % distance

让我们对完全不相关的句子做相同的操作。注意距离变大了。

1
2
3
4
5
6
sentence_orange = 'Oranges are my favorite fruit'
sentence_orange = sentence_orange.lower().split()
sentence_orange = [w for w in sentence_orange if w not in stop_words]

distance = model.wmdistance(sentence_obama, sentence_orange)
print 'distance = %.4f' % distance

正则化w2v向量

当使用wmdistance方法时,首先正则化w2v向量是有益的,因此它们都有相同的长度。为了实现正则化,简单的调用model.init_sims(replace=True),gensim会为你实现它。

通常,使用余弦距离度量两个w2v向量之间的距离。余弦距离度量的是两个向量之间的夹角。另一方面,wmd使用欧式距离。两个向量之间的欧式距离可能会因为她们之间的长度区别而变得很大,但是因为它们之间的夹角很小因此余弦距离很小。我们可以通过正则化向量减轻这个问题。

注意正则化向量会花费一些时间,特别是你有一个大的词汇表 和/或 大的向量集。

用法在下面的例子中被阐明。碰巧我们下载的向量已经被正则化了。因此,在这个例子中我们不会作出什么差别。

1
2
3
4
5
6
7
8
# Normalizing word2vec vectors.
start = time()

model.init_sims(replace=True) # Normalizes the vectors in the word2vec class.

distance = model.wmdistance(sentence_obama, sentence_president) # Compute WMD as normal.

print 'Cell took %.2f seconds to run.' %(time() - start)

第二部分:使用WmdSimilarity进行相似度查询

你可以通过WmdSimilarity类,使用wmd得到一个查询对应的最相似的文档。它的交互过程相似于在gensim教程Similarity Queries中所描绘的。

重要注意
wmd是一种距离度量。WmdSimilarity中的相似度是简单的负距离。注意不要混淆距离和相似度。两个相似文档将有一个高相似得分和一个小距离;两个差异文档将有低的相似得分和一个大距离。

Yelp data

让我们使用一些真实世界数据来尝试下相似度查询。为此我们使用yelp评论。特别的,我们将使用单一餐馆也就是Mon Ami Gabi的评论。

为了得到yelp数据,你需要使用名字和邮箱进行注册。数据是775MB。

这一次,我们将用我们自己的数据去训练W2V嵌入。一个餐馆的数据并不足以合适的训练出w2v,因此我们使用了6个餐馆的数据进行训练。但是仅仅在他们中的一个进行相似度查询试验。除了上面提到的Mon Ami Gabi,我们还将使用:

  • Earl of Sandwich.
  • Wicked Spoon.
  • Serendipity 3.
  • Bacchanal Buffet.
  • The Buffet.

我们选择的餐馆是yelp数据集中那些具有最高数量评论的餐馆。顺带一提,它们都在Las Vegas Boulevard中。我们用于训练w2v的corpus具有18957条文档(评论),而用于WmdSimilarity的corpus具有4137条文档。

下面代码是一个yelp评论的json文件被按行读取,文本被抽取,分词,停用词和标点符号被移除。

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
# Pre-processing a document.

from nltk import word_tokenize
download('punkt') # Download data for tokenizer.

def preprocess(doc):
doc = doc.lower() # Lower the text.
doc = word_tokenize(doc) # Split into words.
doc = [w for w in doc if not w in stop_words] # Remove stopwords.
doc = [w for w in doc if w.isalpha()] # Remove numbers and punctuation.
return doc

start = time()

import json

# Business IDs of the restaurants.
ids = ['4bEjOyTaDG24SY5TxsaUNQ', '2e2e7WgqU1BnpxmQL5jbfw', 'zt1TpTuJ6y9n551sw9TaEg',
'Xhg93cMdemu5pAMkDoEdtQ', 'sIyHTizqAiGu12XMLX3N3g', 'YNQgak-ZLtYJQxlDwN-qIg']

w2v_corpus = [] # Documents to train word2vec on (all 6 restaurants).
wmd_corpus = [] # Documents to run queries against (only one restaurant).
documents = [] # wmd_corpus, with no pre-processing (so we can see the original documents).
with open('/data/yelp_academic_dataset_review.json') as data_file:
for line in data_file:
json_line = json.loads(line)

if json_line['business_id'] not in ids:
# Not one of the 6 restaurants.
continue

# Pre-process document.
text = json_line['text'] # Extract text from JSON object.
text = preprocess(text)

# Add to corpus for training Word2Vec.
w2v_corpus.append(text)

if json_line['business_id'] == ids[0]:
# Add to corpus for similarity queries.
wmd_corpus.append(text)
documents.append(json_line['text'])

print 'Cell took %.2f seconds to run.' %(time() - start)

下面是一个文档长度的直方图,该图中也包含了平均文档长度。注意这些是经过预处理的文档,也就是说停用词已经被移除,标点符号已经被移除,等等。文档长度对wmd的运行时间有很大的影响,因此当和本次实验比较运行时间时,查询corpus的文档数量(大约4000)和文档长度(大约平均62个词)应该被考虑在内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from matplotlib import pyplot as plt
%matplotlib inline

# Document lengths.
lens = [len(doc) for doc in wmd_corpus]

# Plot.
plt.rc('figure', figsize=(8,6))
plt.rc('font', size=14)
plt.rc('lines', linewidth=2)
plt.rc('axes', color_cycle=('#377eb8','#e41a1c','#4daf4a',
'#984ea3','#ff7f00','#ffff33'))
# Histogram.
plt.hist(lens, bins=20)
plt.hold(True)
# Average length.
avg_len = sum(lens) / float(len(lens))
plt.axvline(avg_len, color='#e41a1c')
plt.hold(False)
plt.title('Histogram of document lengths.')
plt.xlabel('Length')
plt.text(100, 800, 'mean = %.2f' % avg_len)
plt.show()

现在,我们想要用corpus和w2v初始化相似类(提供了嵌入和wmdistance方法)。

1
2
3
4
5
6
7
# Train Word2Vec on all the restaurants.
model = Word2Vec(w2v_corpus, workers=3, size=100)

# Initialize WmdSimilarity.
from gensim.similarities import WmdSimilarity
num_best = 10
instance = WmdSimilarity(wmd_corpus, model, num_best=10)

num_best参数决定了查询返回的结果数量。现在让我们来做个查询。输出是corpus中文档相似度和索引的一个列表,按照相似度排序。

注意当num_best为None(也就是没有指定参数)时输出形式有些不同。在这种情况下,你得到一个涵盖corpus中每个文档的相似度数组。

下面的查询直接取自corpus中的一条评论。让我们看看是否有其他的评论相似于这一条。

1
2
3
4
5
6
7
8
start = time()

sent = 'Very good, you should seat outdoor.'
query = preprocess(sent)

sims = instance[query] # A query is simply a "look-up" in the similarity class.

print 'Cell took %.2f seconds to run.' %(time() - start)

查询和最相似的文档,以及它们的相似度,在下面被打印出来。我们看到被检索到的文档讨论着和查询一样的事情,尽管使用了不同的单词。查询谈论的是得到一个户外的座位,而结果谈论的是坐在外面,结果中的一个说的是餐馆有一个好的景观。

1
2
3
4
5
6
7
8

# Print the query and the retrieved documents, together with their similarities.
print 'Query:'
print sent
for i in range(num_best):
print
print 'sim = %.4f' % sims[i][1]
print documents[sims[i][0]]

让我们尝试一个不同的查询,同样直接取自corpus评论中的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
start = time()

sent = 'I felt that the prices were extremely reasonable for the Strip'
query = preprocess(sent)

sims = instance[query] # A query is simply a "look-up" in the similarity class.

print 'Query:'
print sent
for i in range(num_best):
print
print 'sim = %.4f' % sims[i][1]
print documents[sims[i][0]]

print '\nCell took %.2f seconds to run.' %(time() - start)

这次,结果更加直接。检索到的文档基本包含了与查询相同的词。

WmdSimilarity默认正则化了词嵌入(使用init_sims(),正如前面解释的),但你可以改变这个行为通过调用WmdSimilarity,并设置normalize_w2v_and_replace=False。

1
print 'Notebook took %.2f seconds to run.' %(time() - start_nb)

References

  1. Ofir Pele and Michael Werman, A linear time histogram metric for improved SIFT matching, 2008.
  2. Ofir Pele and Michael Werman, Fast and robust earth mover’s distances, 2009.
  3. Matt Kusner et al. From Embeddings To Document Distances, 2015.
  4. Thomas Mikolov et al. Efficient Estimation of Word Representations in Vector Space, 2013.