文本匹配的经典方法

一文梳理文本匹配中经典的非机器学习方法，这些方法不用设计深度模型甚至不需要训练。

文本匹配（语义相似、文本相似）的经典方法有些需要配合向量表征使用，常见的向量表征方法有：

• word2vec
• tf-idf
• VSM向量空间模型

这里不展开说了。像word2vec直接获得的是词向量序列，获得句子的表征还需要一步操作，如直接求和、求平均，或者使用词的idf权重加权求和。VSM、tf-idf方法直接在句子空间中计算句子的向量表征。如果是深度模型，常见的方法有MaxPooling、AveragePooling、BERT的[CLS]等等。

从表征的角度看，匹配方法可以分为三类：

• 基于文本字符的直接匹配
• 基于词向量序列的匹配
• 基于词向量序列所构造的句向量的匹配

相似度度量

通过句子的向量序列，获取句向量，如加权平均或直接平均。

Minkowski距离、Mahalanobis距离、Wasserstein距离中的相似方法，例如余弦相似，

距离度量DD定义：

1. D(a,b)≥0D(a,b)≥0 当a=ba=b取等式（非负性和正定性）
2. D(a,b)=D(b,a)D(a,b)=D(b,a)（对称a性）
3. D(a,b)≤D(a,z)+D(b,z)D(a,b)≤D(a,z)+D(b,z) （三角不等式）。

cos相似

假设句子对的词向量分别为A、B，那么有cos相似，

cos(θ)=A⋅B∥A∥∥B∥=n∑i=1AiBi√n∑i=1A2i√n∑i=1B2icos⁡(θ)=A⋅B‖A‖‖B‖=∑i=1nAiBi∑i=1nAi2∑i=1nBi2

取值区间为[−1,1][−1,1]。转换成[0,2][0,2]正区间的相似度度量，

s(θ)=1−cos(θ)s(θ)=1−cos⁡(θ)

对于文本匹配任务来说，要求AA和BB​​表示为句向量的形式，可以使用tfidf或word2vec等等。还有一种方法就是直接对词向量序列进行加权平均，

average(x)=n∑i=1wixin∑i=1wiaverage⁡(x)=∑i=1nwixi∑i=1nwi

然后权重可以是等全，即直接相加平均，或者取值为词xixi的idf值。

需要注意，从距离度量上看，cos(θ)cos⁡(θ)不满足三角不等式。

欧几里得距离

假设两个随机向量分别为X=(x1,x2,…,xn)∈RnX=(x1,x2,…,xn)∈Rn和Y=(y1,y2,…,yn)∈RnY=(y1,y2,…,yn)∈Rn，那么他们之间的闵可夫斯基距离为，

d(X,Y)=(n∑i=1|xi−yi|p)1pd(X,Y)=(∑i=1n|xi−yi|p)1p

其中p≥1p≥1。欧几里得距离是Minkowski（闵可夫斯基）距离p=2p=2的情况，即

d(X,Y)=(n∑i=1|xi−yi|2)12d(X,Y)=(∑i=1n|xi−yi|2)12

汉明距离是Minkowski（闵可夫斯基）距离p=0p=0​的情况。在文本处理中，其含义是，两个等长字符串的汉明距离是指两者对应位置的不同字符的个数。比如“funny”和“denny”的汉明距离是2。在文本相似中，可以作为特征使用，单独使用效果并不好。

Python实现如下，

def hamming_distance(text1, text2):
    d = 0
    for n in range(len(text1)):
        if text1[n] != text2[n]:
            d += 1
    return d

雅可比相似

雅可比（Jaccard）相似系数，

J(A,B)=|A∩B||A∪B|=|A∩B||A|+|B|−|A∩B|J(A,B)=|A∩B||A∪B|=|A∩B||A|+|B|−|A∩B|

可以作为文本的重合度的度量。Python实现如下，

def jaccard_similar(text1, text2):
    words1 = jieba.lcut(text1)
    words2 = jieba.lcut(text2)
    s1 = set(words1)
    s2 = set(words2)
    return len(s1.intersection(s2)) / len(s1.union(s2))

考虑到不同词汇的重要性不同，如果直接按照集合大小不加以区分，效果会不准确，因此可以引入词汇权重信息，加权句子间的区分，详细可参看本文扩展和衍生部分。

cqr & ctr

考虑query和title的匹配，query和title两者交集占query的比例，

simcqr(Q,T)=|Q∩T||Q|simcqr⁡(Q,T)=|Q∩T||Q|

query和title两者交集占title的比例，

simctr(Q,T)=|Q∩T||T|simctr⁡(Q,T)=|Q∩T||T|

两者相乘可以获得对称的相似计算公式，

sim(Q,T)=simcqr(Q,T)×simctr(Q,T)=|Q∩T|2|Q||T|sim⁡(Q,T)=simcqr⁡(Q,T)×simctr⁡(Q,T)=|Q∩T|2|Q||T|

所谓的对称就是sim(Q,T)=sim(T,Q)sim⁡(Q,T)=sim⁡(T,Q)​。

编辑距离（Levenshitein distance）是给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可以将两个字符串变成相同。编辑距离计算将字符串转换成另一个字符串的操作步骤数量来独立字符串的距离，它的值越高，表示两个字符串越不相似，反之则反。

La,b(i,j)La,b⁡(i,j)表示字符a<ia<i和字符b<jb<j的编辑距离

编辑距离可以看做是汉明距离的一般形式，支持不等长字符串，其递归表达如下，

Lda,b(i,j)=⎧⎪ ⎪ ⎪⎨⎪ ⎪ ⎪⎩max(i,j) if min(i,j)=0min⎧⎪⎨⎪⎩Lda,b(i−1,j)+1Lda,b(i,j−1)+1Lda,b(i−1,j−1)+I[ai≠bj] otherwise.Lda,b⁡(i,j)={max(i,j) if min(i,j)=0min{Lda,b⁡(i−1,j)+1Lda,b⁡(i,j−1)+1Lda,b⁡(i−1,j−1)+I[ai≠bj] otherwise.

其中I[ai≠bj]I[ai≠bj]值指示函数。

对于不存在空字符串的情况

La,b(i,j)=min⎧⎪⎨⎪⎩La,b(i−1,j)+1La,b(i,j−1)+1La,b(i−1,j−1)+I[ai≠bj]La,b⁡(i,j)=min{La,b⁡(i−1,j)+1La,b⁡(i,j−1)+1La,b⁡(i−1,j−1)+I[ai≠bj]

最后获得的编辑距离归一化后可以作为文本相似性的度量。使用Python表示为，

def min_editdistance_similar(text1, text2):
    """根据编辑距离的归一化值作为相似性度量"""
    distance = min_edit_distance(text1, text2)
    return 1 - distance / max(len(text1), len(text2))

更详细的实现可参看我的Github：https://github.com/allenwind/text-similarity-classical-methods。

最长公共子字符串

最长公共子串问题（Longest common substring problem）类似最长公共子序列，其中要求子串在原序列中占用连续的位置。

l(i,j)=l(i−1,j−1)+1 if ai=bjl(i,j)=l(i−1,j−1)+1 if ai=bj

最长公共子串列长度与两个序列中最长的长度的比值作为这两个序列的相似性度量，即，

def lcsubstring_similar(text1, text2):
    """根据最长公共子串的归一化值作为相似性度量"""
    *_, distance = longest_common_substring(text1, text2)
    return distance / max(len(text1), len(text2))

最长公共子序列

最长公共子序列（LCS）问题是找到两个或多个序列中共有的最长子序列，其中子序列不要求在原序列中占用连续的位置。

l(i,j)l(i,j)表示序列a<ia<i和序列b<jb<j的最长公共子序列长度

l(i,j)={l(i−1,j−1)+1 if ai=bjmax(l(i,j−1),l(i−1,j)) if ai≠bjl(i,j)={l(i−1,j−1)+1 if ai=bjmax(l(i,j−1),l(i−1,j)) if ai≠bj

最长公共子序列长度与两个序列中最长的长度的比值作为这两个序列的相似性度量，即，

def lcs_similar(text1, text2):
    """根据最长公共子序列的归一化值作为相似性度量"""
    *_, distance = longest_common_subsequence(text1, text2)
    return distance / max(len(text1), len(text2))

文本匹配中代表性模型有 BM25，对于句子Q=[q1,…,qn]Q=[q1,…,qn]，每个要比较的句子D，其匹配度为，

score(Q,D)=n∑i=1IDF(qi)⋅f(qi,D)⋅(k1+1)f(qi,D)+k1⋅(1−b+b⋅|D|avgdl)score(Q,D)=∑i=1nIDF(qi)⋅f(qi,D)⋅(k1+1)f(qi,D)+k1⋅(1−b+b⋅|D|avgdl) IDF(qi)=logN−n(qi)+0.5n(qi)+0.5IDF(qi)=log⁡N−n(qi)+0.5n(qi)+0.5

当然，比较方便的做法是词qiqi的IDF值直接在idf词典中获取。

avgdlavgdl表示文本的平均常见，bb和k1k1是超参数，根据经验调节。f(qi,D)f(qi,D)为句子Q中的词qiqi​与句子D的匹配度，这里使用词qiqi在句子D中出现的频率来表示。

事实上，结合jieba分词，BM25的Python实现比上式清晰多了，

def bm25_similar(text1, text2, s_avg=10, k1=2.0, b=0.75):
    """s_avg是句子的平均长度，根据语料统计。k1,b是调节因子，根据经验调整。"""
    bm25 = 0.0
    sl = len(text2)
    for w in jieba.lcut(text1):
        w_idf = idf_dict.get(w, 1)
        bm25_ra = text2.count(w) * (k1 + 1)
        bm25_rb = text2.count(w) + k1 * (1 - b + b * sl / s_avg)
        bm25 += w_idf * bm25_ra / bm25_rb
    return bm25

注意到，这里的实现需要事先准备好idf词典。在实践中，需要注意idf词典与句子对集的match程度。

基于Wasserstein距离的向量序列比较

Wasserstein距离在文章Minkowski距离、Mahalanobis距离、Wasserstein距离中以及有简明的介绍。

句子的向量序列容易获得，如gensim加载word2vec模型，甚至BERT等模型。现有句子1的向量序列，

s1=[ϕ1,…,ϕm]s1=[ϕ1,…,ϕm]

类似地，句子2的向量序列，

s2=[ψ1,…,ψn]s2=[ψ1,…,ψn]

注意到一般情况下m≠nm≠n

我们使用di,jdi,j表示ϕiϕi与ψjψj的某种度量下的差异，如范数。ci,j≥0ci,j≥0表示把内容从ii处移动到jj出的量。注意到，从ii处移动到j=1,…,nj=1,…,n处的总量为pipi，因此有，

∑jci,j=pi∑jci,j=pi ∑ici,j=qj∑ici,j=qj

因此有最优化问题，

min∑i,jci,jdi,js.t.∑jci,j=pi∑ici,j=qjci,j≥0min∑i,jci,jdi,js.t.∑jci,j=pi∑ici,j=qjci,j≥0

在运用到句子相似度计算时上时，可以取pi=1npi=1n以及qi=1mqi=1m，相当于不引入任何先验假设，称为字移动距离（WMD）。实现的Python代码如下，

def word_mover_similar(x, y):
    """Word Mover's Distance计算方法, 
    x.shape=(m,d)
    y.shape=(n,d)
    """
    x = np.array(x)
    y = np.array(y)
    p = np.ones(x.shape[0]) / x.shape[0]
    q = np.ones(y.shape[0]) / y.shape[0]
    C = np.sqrt(np.mean(np.square(x[:,None] - y[None,:]), axis=2))
    return 1 - wasserstein_distance(p, q, C)

这一部分可以参考历史文章Minkowski距离、Mahalanobis距离、Wasserstein距离。

字移动距离（WMD）尽管不涉及模型的训练，但是在计算上开销还是比较大，但是其建模上的优雅，不失作为一个baseline或优化因子。

扩展和衍生

事实上，以上基本方法可以组合起来衍生更有效的方法。例如词汇的IDF权重和雅可比相似组合起来，使用词汇的集权平均代替词汇集合的大小。

具体Python实现为，

def weighted_jaccard_similar(text1, text2):
    """使用idf进行词汇加权的jaccard_similar"""
    words1 = jieba.lcut(text1)
    words2 = jieba.lcut(text2)
    s1 = set(words1)
    s2 = set(words2)
    a = s1.intersection(s2)
    b = s1.union(s2)
    al = np.array([idf_dict.get(w, 1) for w in a]).sum(axis=0)
    bl = np.array([idf_dict.get(w, 1) for w in b]).sum(axis=0)
    return al / bl

实现表明，这种方式比原始的雅可比相好很多，而且并没有引入诸如word2vec这类词向量。

类似地，cqr & ctr也可以引入这种权重。

后期整理补充了上述相关实现，可参看我的Github：https://github.com/allenwind/text-similarity-classical-methods 。

这是后期的实现更新，包括了上述的方法的实现，以及使用PR曲线、ROC曲线对比这些方法的差异。

可能会根据个人需要不断更新~

以上总结了很多文本匹配的经典方法，这些方法不用设计深度学习模型，甚至不用进行模型训练，在测试中取得不错的效果。在不要求高性能，追求效率的情况下，这些经典方法不失为一种尝试。

此外，还有句子向量表征召回方法，就是把句子向量化，通过一定的技术对其进行索引，召回时，搜索其进邻向量即可。还有就是深度模型，如DSSM及其各自扩展。这些后期有机会在深入展开。

[1] From Word Embeddings To Document Distances

[2] 《统计自然语言处理》

转载请包括本文地址：https://allenwind.github.io/blog/11001
更多文章请参考：https://allenwind.github.io/blog/archives/