基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法

字数 2302 2025-11-05 08:30:59

基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法

题目描述

词移距离是一种基于词嵌入的文本相似度度量方法，旨在解决传统方法（如TF-IDF、编辑距离）忽略语义信息的问题。其核心思想是将文本相似度计算转化为运输问题：将一篇文档中的每个词视为一定质量的“货物”，需要通过最小“移动成本”将文档A的词“搬运”到文档B的词上，移动成本由词嵌入空间中的距离（如余弦距离）定义。WMD直接利用预训练词向量（如Word2Vec、GloVe），捕获词汇间的语义关系，从而更准确地衡量文本语义相似度。

解题过程详解

步骤1：问题形式化

假设有两篇文档 \(D_A\) 和 \(D_B\)：

\(D_A\) 由词序列 \(\{w_1^A, w_2^A, ..., w_m^A\}\) 组成，每个词 \(w_i^A\) 的权重为 \(d_i^A\)（如通过TF-IDF或归一化词频得到）。
\(D_B\) 由词序列 \(\{w_1^B, w_2^B, ..., w_n^B\}\) 组成，权重为 \(d_j^B\)。

目标：找到一种“搬运方案” \(T \in \mathbb{R}^{m \times n}\)，其中 \(T_{ij}\) 表示将 \(w_i^A\) 的权重分配到 \(w_j^B\) 的比例，使得总移动成本最小：

\[\text{WMD}(D_A, D_B) = \min_{T \geq 0} \sum_{i=1}^m \sum_{j=1}^n T_{ij} \cdot c(w_i^A, w_j^B) \]

约束条件：

权重守恒：从 \(w_i^A\) 搬出的总重量等于其原始权重，即 \(\sum_j T_{ij} = d_i^A\)。
需求满足：搬运到 \(w_j^B\) 的总重量等于其目标权重，即 \(\sum_i T_{ij} = d_j^B\)。
其中 \(c(w_i^A, w_j^B)\) 是词嵌入空间中的距离（如欧氏距离）。

步骤2：词权重计算

通常采用归一化词频（或TF-IDF）作为权重：

对文档中的每个词频 \(\text{tf}(w)\) 进行归一化：

\[d(w) = \frac{\text{tf}(w)}{\sum_{w' \in D} \text{tf}(w')} \]

例如，文档 \(D_A\)：“猫追老鼠” → 词频均为1，归一化后权重各为 \(1/3\)。

步骤3：词间距离定义

使用预训练词向量（如GloVe）计算词对之间的欧氏距离：

\[c(w_i, w_j) = \| \mathbf{v}_{w_i} - \mathbf{v}_{w_j} \|_2 \]

例如，“猫”和“狗”的向量距离较小，而“猫”和“飞机”的距离较大。

步骤4：转化为最优运输问题

WMD的优化目标等价于地球 mover 距离（Earth Mover's Distance），可通过线性规划求解：

变量：\(T_{ij}\)（非负）。
目标函数：最小化 \(\sum_{i,j} T_{ij} c_{ij}\)。
约束：

\[ \begin{cases} \sum_j T_{ij} = d_i^A, & \forall i \in [1, m] \\ \sum_i T_{ij} = d_j^B, & \forall j \in [1, n] \end{cases} \]

该问题可用单纯形法或专用传输算法（如Sinkhorn-Knopp近似）求解。

步骤5：计算示例

假设文档 \(D_A\) ：{猫，追，老鼠}，权重各为 \(1/3\)；
文档 \(D_B\) ：{狗，追，仓鼠}，权重各为 \(1/3\)。
词向量距离矩阵 \(c_{ij}\) 如下（简化示例）：

	狗	追	仓鼠
猫	0.2	1.0	0.8
追	1.0	0.0	1.2
老鼠	0.9	1.2	0.3

最优传输方案 \(T\) 可能为：

将“猫”的权重全部分配给“狗”（成本 \(0.2 \times 1/3\)）。
将“追”的权重分配给“追”（成本 \(0\)）。
将“老鼠”的权重分配给“仓鼠”（成本 \(0.3 \times 1/3\)）。
总成本：\((0.2 + 0 + 0.3)/3 = 0.167\)。

步骤6：优化与近似

WMD的精确求解复杂度为 \(O(p^3 \log p)\)（\(p\) 为文档长度），难以处理长文本。常用优化方法：

Word Centroid Distance（WCD）下界：快速计算文档向量质心的距离，作为WMD的下界，用于剪枝。
Relaxed WMD：通过限制运输范围（如仅允许最近邻词配对）降低复杂度。

总结

WMD通过结合词嵌入与最优运输理论，实现了语义敏感的文本相似度计算。其优势在于直接建模词汇语义关系，但计算成本较高，通常需借助近似算法加速。后续改进如S-WMD（对齐句法结构）、FastWMD（基于树搜索的剪枝）进一步提升了实用性与效率。

基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法题目描述词移距离是一种基于词嵌入的文本相似度度量方法，旨在解决传统方法（如TF-IDF、编辑距离）忽略语义信息的问题。其核心思想是将文本相似度计算转化为运输问题：将一篇文档中的每个词视为一定质量的“货物”，需要通过最小“移动成本”将文档A的词“搬运”到文档B的词上，移动成本由词嵌入空间中的距离（如余弦距离）定义。WMD直接利用预训练词向量（如Word2Vec、GloVe），捕获词汇间的语义关系，从而更准确地衡量文本语义相似度。解题过程详解步骤1：问题形式化假设有两篇文档 \( D_ A \) 和 \( D_ B \)： \( D_ A \) 由词序列 \( \{w_ 1^A, w_ 2^A, ..., w_ m^A\} \) 组成，每个词 \( w_ i^A \) 的权重为 \( d_ i^A \)（如通过TF-IDF或归一化词频得到）。 \( D_ B \) 由词序列 \( \{w_ 1^B, w_ 2^B, ..., w_ n^B\} \) 组成，权重为 \( d_ j^B \)。目标：找到一种“搬运方案” \( T \in \mathbb{R}^{m \times n} \)，其中 \( T_ {ij} \) 表示将 \( w_ i^A \) 的权重分配到 \( w_ j^B \) 的比例，使得总移动成本最小： \[ \text{WMD}(D_ A, D_ B) = \min_ {T \geq 0} \sum_ {i=1}^m \sum_ {j=1}^n T_ {ij} \cdot c(w_ i^A, w_ j^B) \] 约束条件：权重守恒：从 \( w_ i^A \) 搬出的总重量等于其原始权重，即 \( \sum_ j T_ {ij} = d_ i^A \)。需求满足：搬运到 \( w_ j^B \) 的总重量等于其目标权重，即 \( \sum_ i T_ {ij} = d_ j^B \)。其中 \( c(w_ i^A, w_ j^B) \) 是词嵌入空间中的距离（如欧氏距离）。步骤2：词权重计算通常采用归一化词频（或TF-IDF）作为权重：对文档中的每个词频 \( \text{tf}(w) \) 进行归一化： \[ d(w) = \frac{\text{tf}(w)}{\sum_ {w' \in D} \text{tf}(w')} \] 例如，文档 \( D_ A \)：“猫追老鼠” → 词频均为1，归一化后权重各为 \( 1/3 \)。步骤3：词间距离定义使用预训练词向量（如GloVe）计算词对之间的欧氏距离： \[ c(w_ i, w_ j) = \| \mathbf{v} {w_ i} - \mathbf{v} {w_ j} \|_ 2 \] 例如，“猫”和“狗”的向量距离较小，而“猫”和“飞机”的距离较大。步骤4：转化为最优运输问题 WMD的优化目标等价于地球 mover 距离（Earth Mover's Distance），可通过线性规划求解：变量：\( T_ {ij} \)（非负）。目标函数：最小化 \( \sum_ {i,j} T_ {ij} c_ {ij} \)。约束： \[ \begin{cases} \sum_ j T_ {ij} = d_ i^A, & \forall i \in [ 1, m ] \\ \sum_ i T_ {ij} = d_ j^B, & \forall j \in [ 1, n ] \end{cases} \] 该问题可用单纯形法或专用传输算法（如Sinkhorn-Knopp近似）求解。步骤5：计算示例假设文档 \( D_ A \) ：{猫，追，老鼠}，权重各为 \( 1/3 \)；文档 \( D_ B \) ：{狗，追，仓鼠}，权重各为 \( 1/3 \)。词向量距离矩阵 \( c_ {ij} \) 如下（简化示例）： | | 狗 | 追 | 仓鼠 | |--------|-----|-----|------| | 猫 | 0.2 | 1.0 | 0.8 | | 追 | 1.0 | 0.0 | 1.2 | | 老鼠 | 0.9 | 1.2 | 0.3 | 最优传输方案 \( T \) 可能为：将“猫”的权重全部分配给“狗”（成本 \( 0.2 \times 1/3 \)）。将“追”的权重分配给“追”（成本 \( 0 \)）。将“老鼠”的权重分配给“仓鼠”（成本 \( 0.3 \times 1/3 \)）。总成本：\( (0.2 + 0 + 0.3)/3 = 0.167 \)。步骤6：优化与近似 WMD的精确求解复杂度为 \( O(p^3 \log p) \)（\( p \) 为文档长度），难以处理长文本。常用优化方法： Word Centroid Distance（WCD）下界：快速计算文档向量质心的距离，作为WMD的下界，用于剪枝。 Relaxed WMD ：通过限制运输范围（如仅允许最近邻词配对）降低复杂度。总结 WMD通过结合词嵌入与最优运输理论，实现了语义敏感的文本相似度计算。其优势在于直接建模词汇语义关系，但计算成本较高，通常需借助近似算法加速。后续改进如S-WMD（对齐句法结构）、FastWMD（基于树搜索的剪枝）进一步提升了实用性与效率。