在完成第二篇论《From Word Embeddings To Document Distances》文阅读之后，需要完成相应论文词数据的测试计算，另外这个文章中涉及线性规划的一部分内容，所以就趁着算法细节没有忘记，完成了相关算法的实现。由于年底很忙，这个简单的文档也拖了很久还没有写完，趁没有遗忙的时候赶紧记录下来，尽管很简单。
假设有三个句子，需要通过WMD来判断句子之间的相似度，具体三个句子分别为：
(1)sentence1: “Boys like eating apples”
(2)sentence2: “He wants some fruits”
(3)sentence3: “A boy speaks French”
为完成上述目标，具体的算法实现流程如图1所示。
图1 利用WMD计算不同语句相似度的算法流程
1、获取词embedding向量文件
为了完成每个单词的词向量特征提取，需要利用公共数据进行预训练，形成了embedding向量文件。目前英文文档中较常用的是斯坦福大学提供的Glove(Golobal Vectors for word Representation）词embedding文件，便于映射形成各个单词的多维度词向量，该文件包括了50维、100维、200维、300维等四种词向量维度。一般而言，维度越多，越能够表现出每个词之间的差异。上述embeeding向量文件，一般是读取之后用dictionary的方式进行存储。
常规英文对应embedding向量文件下载链接为：Global Vectors for Word Representation常规英文对应embedding向量文件下载链接为：
Global Vectors for Word Representationnlp.stanford.edu
2、 句子单词分析与nBow构建
由于英文单词跟中文单词有典型的差异，因此直接利用空格对单词进行分割，然后利用nBow进行统计，并计算每一个单词在该句子中的占比概率。
这个概率后面在进行句子间的比例计算时，需要用来衡量与之对应的那个新词对应的占比，是计算WMD最短距离的重要约束。
3、句子单词embedding向量预处理
参照embedding向量文件对应的dictionary，获取每一个单词对应的词向量。本文实验部分利用的是50维的词向量特征进行评估。例如单词boys与he对应的50维词向量为：
- boys: [-0.74203 0.6797 -0.56667 -1.1968 0.3358 0.29851 -0.70912 -0.14211 -0.40529 0.097625 -0.082705 -0.21598 -0.33956 -0.63261 0.54714 -0.32945 -0.037783 0.88213 -0.36467 -0.0061634 -0.39807 1.2246 0.66922 1.3295 -0.56906 -1.0283 -0.3655 -0.18287 -0.13597 -1.1708 2.2974 0.626 -0.015633 -0.32109 0.88654 0.4967 0.45373 -0.82939 0.28069 -0.92905 -0.60766 -0.74002 0.12943 0.2404 1.0691 -0.27271 0.29008 -1.2301 -0.091389 -0.2003 ]
- he: [-0.20092 -0.060271 -0.61766 -0.8444 0.5781 0.14671 -0.86098 0.6705 -0.86556 -0.18234 0.15856 0.45814 -1.0163 -0.35874 0.73869 -0.24048 -0.33893 0.25742 -0.78192 0.083528 0.1775 0.91773 0.64531 -0.19896 0.37416 -2.7525 -0.091586 0.040349 -0.064792 -0.31466 3.3944 0.044941 -0.55038 -0.65334 0.10436 0.016394 0.24388 1.0085 0.31412 -0.33806 -0.16925 0.10228 -0.62143 0.19829 -0.36147 -0.24769 -0.38989 -0.33317 -0.041659 -0.013171]
4、求解两个句子之间最短WMD距离约束
参照《From Word Embeddings To Document Distances》文档，利用单词对应的50维的单词向量计算两个单词的距离。第
个词与第
个词之间的距离可表示为：
。其中
与
分别为两个单词在embedding空间的两个词向量，而
则表示为两个词向量之间的word travel cost。
在完成任何两个词之间的travel cost计算之后，需要计算文档
与文档
时，首先要利用nBow表示两段文本。在开始计算两个文档的距离，需要有三个假设：
- 假设1：文档中任何一个词 都可以转化为文档 中任何词 ，且每个单词都要完成转移；
- 假设2：从文档中的转移出来的词 的总和等于文档 中词的总数；
- 假设3：转移进入文档中转化为 的数量总各等于文档 中词总数。
在完成上述三个假设之后，定义一个转移矩阵
，其中每个元素
表示有多少词
从
转移成了
中的词
。最终本文定义两个文档之间的距离为即为两个文档中词的积累Total travel cost，具体表达式为
。因此在求解Documnet distance的过程即转化为一个
典型的整数规划求解问题
，具体表达示可写为：
5、调用求解器进行求解
参照第4阶段中涉及整数规划求解原理，完成两个句子距离计算的算法逻辑。本文在完成最小移动距离的计算时，涉及的软件包为pulp，最终具体的实现代码如下：
import numpy as np
from pulp import *
记录词向量字典
w2v = {}
word2id = {}
id2word = {}
word_list = []
读取原始词向量文件
with open("raw_data/glove.6B.50d.txt", "r", encoding="utf-8") as glovefile:
for i, each_line in enumerate(glovefile):
each_wc = each_line.strip().split(' ')
w2v[each_wc[0]] = np.array([float(i) for i in each_wc[1:]])
word_list.append(each_wc[0])
id2word[i] = each_wc[0]
word2id[each_wc[0]] = i
将一句英文单词拆分为单词
def cleanup_line(sent):
splitted_list = []
for each in sent.strip().split():
if word2id.get(each.strip()):
splitted_list.append(each.strip())
return splitted_list
利用词向量字典提取每个句子中单词的词向量
def encode_line(sent_splitted, w2v, word2id):
encoded = {}
for each in sent_splitted:
encoded[word2id[each]] = w2v[each]
return encoded
针对每一个句子计算相应的nBow的词占比概率
def calculated_d_stat(sent_splitted, word2id):
d = np.zeros(len(word2id))
for each_w in sent_splitted:
d[word2id[each_w]] += 1
return d/(d.sum())
计算两个词的词向量距离
def cost(v1, v2):
dist = np.linalg.norm(v1 - v2)
return dist
基于两个句子中各单词的词向量，求解最小的wmd组合
def solve_lp(sent_splitted_1, sent_splitted_2, d1, d2, encod1, encod2):
sent_id1 = [word2id[e] for e in set(sent_splitted_1)]
sent_id2 = [word2id[e] for e in set(sent_splitted_2)]
problem = LpProblem("wmp_lp", LpMinimize)
T = LpVariable.dicts('T', (sent_id1, sent_id2), lowBound=0, upBound=1)
problem += lpSum([(T[i][j] * cost(encod1[i], encod2[j])) for i in sent_id1 for j in sent_id2])
for i in sent_id1:
problem += lpSum(T[i][j] for j in sent_id2) == d1[i]
for j in sent_id2:
problem += lpSum(T[i][j] for i in sent_id1) == d2[j]
problem.solve()
return problem.objective.value()
def WMD(sent1, sent2):
"""
这是主要的函数模块。参数sent1是第一个句子， 参数sent2是第二个句子，可以认为没有经过分词。
step1: 对句子做分词： 调用 .split() 函数即可
step2: 获取每个单词的词向量。这需要读取文件之后构建embedding matrix.
step3: 构建lp问题，并用solver解决
可以自行定义其他的函数，但务必不要改写WMD函数名。测试时保证WMD函数能够正确运行。
"""
splitted_line_1 = cleanup_line(sent1)
splitted_line_2 = cleanup_line(sent2)
d1 = calculated_d_stat(splitted_line_1, word2id)
d2 = calculated_d_stat(splitted_line_2, word2id)
encoded_1 = encode_line(splitted_line_1, w2v, word2id)
encoded_2 = encode_line(splitted_line_2, w2v, word2id)
return solve_lp(splitted_line_1, splitted_line_2, d1, d2, encoded_1, encoded_2)
6、句子之间相似度度量验证
完成了上述代码的撰写与实践，具体计算sentence1至sentence3之间的距离，通过WMD函数的计算，具体的距离即为：
(1)sentence1: “Boys like eating apples”
(2)sentence2: “He wants some fruits”
(3)sentence3: “A boy speaks French”
具体而言，sentenc1与sentence2的WMD值为4.37，而sentence1与sentence3的WMD值为5.43。因此，sentence1与sentence2的相似性更高。
Original: https://blog.csdn.net/weixin_36164538/article/details/113366836
Author: 化学小辣鸡toto
Title: 判断两个颜色相似度_计算两个语句相似度的WMD算法实现
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/568969/
转载文章受原作者版权保护。转载请注明原作者出处！