从Jaccard到BERT：语义检索的度量手段

原文标题&＃xff1a;Semantic Search: Measuring Meaning From Jaccard to Bert
作者&＃xff1a;James Briggs
原文地址&＃xff1a;https://towardsdatascience.com/semantic-search-measuring-meaning-from-jaccard-to-bert-a5aca61fc325

注&＃xff1a;只挑选了干货部分进行翻译

相似性搜索&＃xff08;Similarity search&＃xff09;是人工智能和机器学习中发展最快的领域之一。其核心是将相关信息片段匹配在一起的过程。

相似性搜索是一个复杂的主题&＃xff0c;有无数的技术来构建有效的搜索引擎。在本文中&＃xff0c;我们将介绍这些技术中最有趣、最强大的&＃xff0c;特别关注语义检索&＃xff08;semantic search&＃xff09;。我们将学习它们如何工作&＃xff0c;它们的优势&＃xff0c;以及如何自己实现它们。

• Jaccard Similarity
• w-shingling
• Pearson Similarity
• Levenshtein距离
• 标准化谷歌距离&＃xff08;Normalized Google Distance&＃xff09;

所有这些都是用于相似性搜索的优秀指标&＃xff0c;其中我们将介绍三个最流行的指标&＃xff1a;Jaccard相似性、w-shingling和Levenshtein距离。

1.1 Jaccard Similarity

Jaccard相似性是一个简单&＃xff0c;但有些时候很有用的相似性度量手段。
给定两个序列&＃xff0c;A和B&＃xff0c;我们求出两者之间共有的元素的数量&＃xff0c;然后除以两个序列中的元素总数。

Jaccard相似度度量两个序列在两个序列的并集上的交集&＃xff1a;

下面是一段示例代码&＃xff1a;

a &＃61; [0, 1, 2, 3, 3, 3, 4]
b &＃61; [7, 6, 5, 4, 4, 3]
# convert to sets
a &＃61; set(a)
b &＃61; set(b)
# find the number of shared values between sets
shared &＃61; a.intersection(b)
# find the total number of values in both sets
total &＃61; a.union(b)
# and calculate Jaccard similarity
len(shared) / len(total)


在这里&＃xff0c;我们确定了两个序列之间的两个共享唯一整数&＃xff0c;3和4&＃xff0c;这两个序列中总共有10个整数&＃xff0c;其中8个是唯一值
由$2/8$ 得到Jaccard相似性得分为0.25。

我们也可以对文本数据执行相同的操作&＃xff0c;我们所做的就是用单词替换整数。
计算两个句子a和b之间的Jaccard相似度&＃xff1a;

a &＃61; "his thought process was on so many levels that he gave himself a phobia of heights".split()
b &＃61; "there is an art to getting your way and throwing bananas on to the street is not it".split()
c &＃61; "it is not often you find soggy bananas on the street".split()
a &＃61; set(a)
b &＃61; set(b)
c &＃61; set(c)
def jac(x: set, y: set):
shared &＃61; x.intersection(y) # selects shared tokens only
return len(shared) / len(x.union(y)) # union adds both sets together
jac(a, b) # 0.03225806451612903
jac(b, c) # 0.35


我们发现句子b和c的得分要高得多&＃xff0c;正如我们预期的那样。现在&＃xff0c;它并不是完美的——两个除了“the”、“a”、“is”等词之外什么都没有的句子可能会返回很高的Jaccard分数&＃xff0c;尽管语义不同。

这些缺点可以通过预处理技术部分解决&＃xff0c;如使用停用词表&＃xff0c;词干/词形还原等。然而&＃xff0c;我们很快就会看到&＃xff0c;有些方法完全避免了这些问题。

1.2 w-Shingling

另一种类似的技术是w-Shingling。
w-Shingling使用完全相同的取交集&＃xff0c;并集逻辑&＃xff0c;但使用“shingles”。
个人理解就是n-grams

The w denotes the number of tokens in each shingle in the set.

句子A的2-shingle看起来像&＃xff1a;a &＃61; ‘his thought’, ‘thought process’, ‘process is’, …
就是取了句子的2-gram。

# 句子分词
a &＃61; "his thought process was on so many levels that he gave himself a phobia of heights".split()
b &＃61; "there is an art to getting your way and throwing bananas on to the street is not it".split()
c &＃61; "it is not often you find soggy bananas on the street".split()
a_shingle &＃61; set([&＃39; &＃39;.join([a[i], a[i&＃43;1]]) for i in range(len(a)) if i !&＃61; len(a)-1])
b_shingle &＃61; set([&＃39; &＃39;.join([b[i], b[i&＃43;1]]) for i in range(len(b)) if i !&＃61; len(b)-1])
c_shingle &＃61; set([&＃39; &＃39;.join([c[i], c[i&＃43;1]]) for i in range(len(c)) if i !&＃61; len(c)-1])
# 仍然可用杰卡德距离的公式计算&＃xff0c;只不过每个元素由单词变为了2-gram
jac(a_shingle, b_shingle) # 0.0
jac(b_shingle, c_shingle) # 0.125
# 展示两句中匹配的shingles
b_shingle.intersection(c_shingle)
# &＃39;bananas on&＃39;, &＃39;is not&＃39;, &＃39;the street&＃39;


1.3 Levenshtein Distance

莱文斯坦距离&＃xff0c;又称Levenshtein距离&＃xff0c;是编辑距离的一种。指两个字串之间&＃xff0c;由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符&＃xff0c;插入一个字符&＃xff0c;删除一个字符。

这是一道经典的动态规划算法题&＃xff0c;可前往力扣自行练习。
题目链接&＃xff1a;https://leetcode-cn.com/problems/edit-distance/。

Levenshtein距离公式&＃xff1a;

变量a和b代表两个字符串&＃xff0c;i和j分别代表a和b中的字符位置。

下标从1开始&＃xff0c;索引0将代表空字符串

使用Wagner-Fischer matrix来计算两个字符串的莱温斯坦距离。

a &＃61; &＃39; Levenshtein&＃39;
b &＃61; &＃39; Livinshten&＃39; # we include empty space at start of each word
import numpy as np
# initialize empty zero array
lev &＃61; np.zeros((len(a), len(b)))


lev[i][j] 表示a[0:i]变换到b[0:j]的最小操作次数。

首先处理dp表的边界。很容易理解&＃xff0c;一个空的字符串要变成另一个字符串&＃xff0c;操作数必然是非空字符串的长度。

for i in range(len(a)):
for j in range(len(b)):
# if i or j are 0
if min([i, j]) &＃61;&＃61; 0:
# we assign matrix value at position i, j &＃61; max(i, j)
lev[i, j] &＃61; max([i, j])


内部元素的计算&＃xff1a;

for i in range(len(a)):
for j in range(len(b)):
# we did this before (for when i or j are 0)
if min([i, j]) &＃61;&＃61; 0:
lev[i, j] &＃61; max([i, j])
else:
# calculate our three possible operations
x &＃61; lev[i-1, j] # 删除
y &＃61; lev[i, j-1] # 插入
z &＃61; lev[i-1, j-1] # 替换
# take the minimum (eg best path/operation)
lev[i, j] &＃61; min([x, y, z])
# and if our two current characters don&＃39;t match, add 1
if a[i] !&＃61; b[j]:
# if we have a match, don&＃39;t add 1
lev[i, j] &＃43;&＃61; 1


这篇博客没有讲清楚算法的原理&＃xff0c;只是用画图展示了计算过程。提供的代码&＃xff0c;耗时和内存也很糟糕。

下面讲一讲基本的动态规划思路&＃xff1a;
指针$i$指向word1, 指针$j$指向word2

• $dp[0][0]$表示word1和word2都是空的字符串
• $dp[i][j]$表示word1的前i个字符转换成word2的前j个字符所需要的最少操作步数

注意只看操作的word1的字符范围&＃xff0c;不看操作后的word1的长度&＃xff01;并且我们始终操作word1。

确定递推公式
当word1[i-1] &＃61;&＃61; word2[j-1]时&＃xff0c;什么也不做&＃xff0c;dp[i][j] &＃61; dp[i-1][j-1]
当word1[i-1] !&＃61; word2[j-1]时&＃xff0c; 有三种情况&＃xff1a;
1. 什么时候插入&＃xff1f;
已经将word1的前i个字符转换为word2的前j-1个字符了&＃xff08;最小操作数为dp[i][j-1]&＃xff09;
只需在word1的第i个字符后面插入word2[j]
2. 什么时候删除&＃xff1f;
已经将word1前i-1个字符转换为word2的前j个字符&＃xff08;最小操作数为dp[i-1][j]&＃xff09;
只需要删除word1[i-1], 相当于dp[i-1][j]加上一次删除操作
3. 什么时候替换?
已经将word1的前i-1个字符转换成word2的前j-1个字符&＃xff08;最小操作数为dp[i-1][j-1]&＃xff09;
只需要将word1的第i个字符替换成word2的第j个字符

• TF-IDF
• BM25
• word2vec/doc2vec
• BERT
• USE

这些基于向量的方法是相似度搜索领域的最优方法。
我们将介绍基于TF-IDF、BM25和BERT的方法&＃xff0c;因为它们是最常见的方法&＃xff0c;并且涵盖稀疏和密集向量表示。

2.1 TF-IDF

信息检索领域的经典方法&＃xff0c;诞生于1970s。
关于TF-IDF这部分&＃xff0c;也可以参考我的博客&＃xff1a;
IR&IE笔记&＃xff1a;倒排索引表与布尔模型
IR&IE笔记&＃xff1a;向量空间模型与扩展的向量空间模型

TF(term frequency)部分计算一个词语在一个文档中出现的次数&＃xff0c;并将其除以该文档中的词语总数。






T


F


&＃61;




f


(


q


,


D


)




f


(


t


,


D


)






\\Large TF &＃61; \\fracf(q, D)f(t, D)


TF&＃61;f(t,D)f(q,D)​

• $f(q,D)$: q在文档D中出现的次数
• $f(t,D)$: 文档d的词数

“bananas"是一个比较有信息含量的查询词&＃xff0c;计算所有文档的TF(&＃39;bananas&＃39;, D)&＃xff0c;可以找出"bananas"出现频率较高的文档。但是如果query中还包含了一些常用词呢&＃xff1f;如"the”、“is"或"it"这样的词。假如我们搜索"is bananas”&＃xff0c;可能含有更多"is"的文档"is is is is is"就会排在更前面。但显然不是我们想要的。

某个单词出现次数越小&＃xff0c;那文档中出现此单词的概率越小&＃xff0c;则信息量越高。理想情况下&＃xff0c;我们希望稀有词&＃xff0c;即带有更多信息的词的匹配得分更高。因此我们需要第二个指标IDF&＃xff0c;逆向文档频率。

IDF(The Inverse Document Frequency)衡量了一个单词在所有文档中的非常见程度。







I


D


F


&＃61;


l


o


g



N



N


(


q


)







\\displaystyle \\Large IDF &＃61; log \\fracNN(q)


IDF&＃61;logN(q)N​
$N(q)$: 包含词项$q$的文档的数量

如下图所示&＃xff0c;假如我们同时搜索"is"和"forest"这两个词&＃xff0c;首先计算一次两个词的IDF值&＃xff0c;再计算每个文档的TF(&＃39;is&＃39;, D)and TF(&＃39;forest&＃39;, D)&＃xff0c;将TF与IDF相乘得到每篇文档的TF-IDF值。

可以发现&＃xff0c;尽管"is"在每篇文档的TF值较大&＃xff0c;但IDF值为0&＃xff0c;TF-IDF值还是帮助我们找到了信息量更大的&＃xff0c;包含"forest"的文档。

原博客提供的代码有误&＃xff0c;修正后的代码如下&＃xff1a;

a &＃61; "purple is the best city in the forest".split()
b &＃61; "there is an art to getting your way and throwing bananas on to the street is not it".split()
c &＃61; "it is not often you find soggy bananas on the street".split()
import numpy as np
def tfidf(word):
tf &＃61; []
count_n &＃61; 0
for sentence in [a, b, c]:
t_count &＃61; 0
# calculate TF
for x in sentence:
if word &＃61;&＃61; x:
t_count &＃43;&＃61; 1
tf.append(t_count/len(sentence))
# count number of docs for IDF
count_n &＃43;&＃61; 1 if word in sentence else 0
idf &＃61; np.log10(len([a, b, c]) / count_n)
return [round(_tf*idf, 2) for _tf in tf]
tfidf_a, tfidf_b, tfidf_c &＃61; tfidf(&＃39;forest&＃39;)
print(f"TF-IDF a: tfidf_a\\nTF-IDF b: tfidf_b\\nTF-IDF c: tfidf_c")


看起来TF-IDF本身就是一个检索算法了&＃xff0c;那么&＃xff0c;向量相似性检索从哪里来的呢&＃xff1f;
根据所有的文档&＃xff0c;维护一个词汇表。
一个文档&＃xff0c;就可以用其所有单词的TF-IDF值表示成为一个向量&＃xff0c;向量的长度为词表大小。

示例代码如下&＃xff1a;

vocab &＃61; set(a&＃43;b&＃43;c)
# initialize vectors
vec_a &＃61; []
vec_b &＃61; []
vec_c &＃61; []
for word in vocab:
tfidf_a, tfidf_b, tfidf_c &＃61; tfidf(word)
vec_a.append(tfidf_a)
vec_b.append(tfidf_b)
vec_c.append(tfidf_c)
print(vec_a)
# [0.0, 0.0, 0.0, 0.0, 0.0, 0.48, 0.0, 0.0, 0.48, 0.0, 0.48, 0.48, 0.0, 0.0, 0.0, 0.0, 0.48, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]


值得注意的是&＃xff0c;vocab的大小很容易在20K&＃43;范围内&＃xff0c;因此使用这种方法生成的向量非常稀疏&＃xff0c;这意味着我们无法编码任何语义。

2.2 BM25

Okapi BM25是TF-IDF的改进算法&＃xff0c;基于文档长度对结果进行标准化。
假设我们有两篇500词的文章&＃xff0c;发现A提到“丘吉尔”六次&＃xff0c;B提到“丘吉尔”十二次——我们是否应该认为A有一半B的相关性&＃xff1f;
大概不会。
BM25通过改进TF-IDF的公式解决了这个问题。

先来看TF部分

再来看IDF部分

随着查询词在句子中的频率提升&＃xff0c;两个算法分数的直观对比如下所示。
TF-IDF分数随着相关单词的数量线性增加。因此&＃xff0c;如果频率加倍&＃xff0c;TF-IDF分数也会加倍。
而BM25的分数&＃xff0c;不会在词频较高时线性增加。

计算BM25的分数并构建词向量的示例代码如下&＃xff1a;

a &＃61; "purple is the best city in the forest".split()
b &＃61; "there is an art to getting your way and throwing bananas on to the street is not it".split()
c &＃61; "it is not often you find soggy bananas on the street".split()
d &＃61; "green should have smelled more tranquil but somehow it just tasted rotten".split()
e &＃61; "joyce enjoyed eating pancakes with ketchup".split()
f &＃61; "as the asteroid hurtled toward earth becky was upset her dentist appointment had been canceled".split()
docs &＃61; [a, b, c, d, e, f]
import numpy as np
avgdl &＃61; sum(len(sentence) for sentence in [a,b,c,d,e,f]) / len(docs)
N &＃61; len(docs)
def bm25(word, sentence, k&＃61;1.2, b&＃61;0.75):
freq &＃61; sentence.count(word) # or f(q,D) - freq of query in Doc
tf &＃61; (freq * (k &＃43; 1)) / (freq &＃43; k * (1 - b &＃43; b * (len(sentence) / avgdl)))
N_q &＃61; sum([doc.count(word) for doc in docs]) # number of docs that contain the word
idf &＃61; np.log(((N - N_q &＃43; 0.5) / (N_q &＃43; 0.5)) &＃43; 1)
return round(tf*idf, 4)
vocab &＃61; set(a&＃43;b&＃43;c&＃43;d&＃43;e&＃43;f)
vec &＃61; []
# we will create the BM25 vector for sentence &＃39;a&＃39;
for word in vocab:
vec.append(bm25(word, a))
print(vec)


同样&＃xff0c;BM25能算出的也是稀疏向量。我们将无法对语义进行编码&＃xff0c;而是将重点放在语法上。

2.3 BERT

这部分作者主要使用了SBERT&＃xff0c;SBERT可见我的这篇博客&＃xff1a;Sentence-BERT论文阅读笔记