基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法详解
字数 2563 2025-12-02 20:12:37

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

题目描述
词移距离（Word Mover's Distance, WMD）是一种用于衡量两个文本文档之间语义相似度的算法。其核心思想是将文档相似度计算问题转化为一个经典的运输问题：将一个文档中的词“移动”到另一个文档中的词，所需的最小“工作量”。这里的“工作量”由词在预训练词向量空间中的欧氏距离来定义。WMD 的优势在于它能够利用词向量的语义信息，即使两个文档没有共同的词汇，只要它们的词在语义上接近，WMD 也能给出较高的相似度。

解题过程

第一步：问题形式化与直观理解

假设我们有两个文档：

  • 文档 A：“Obama speaks to the media in Illinois”
  • 文档 B：“The President greets the press in Chicago”

我们的目标是量化文档 A 和文档 B 的语义相似度。

  1. 文档表示：首先，我们将每个文档表示为一组加权的词向量。这通常通过以下步骤完成：

    • 分词：将文档分割成单词（或子词单元）。
    • 去除停用词（可选）：如“to", "the", "in”等，以减少噪声。
    • 词向量化：为每个剩余的词查找其预训练好的词向量（例如，Word2Vec 或 GloVe 词向量）。词向量将每个词映射到一个高维空间中的点，语义相近的词在空间中的位置也相近。
    • 权重分配：为每个词分配一个权重，通常使用词袋模型下的归一化词频（如 nBOW）。例如，如果一个词在文档中出现多次，它的权重就更高。权重之和为1。

    经过处理后：

    • 文档 A 可表示为：{ (Obama, 权重_a1), (speaks, 权重_a2), (media, 权重_a3), (Illinois, 权重_a4) }
    • 文档 B 可表示为：{ (President, 权重_b1), (greets, 权重_b2), (press, 权重_b3), (Chicago, 权重_b4) }

  2. “移动”的直观理解：现在，想象文档 A 中的每个词都是一堆“土”，土的量等于该词的权重。文档 B 中的每个词是一个“坑”，需要填入的土量等于该词的权重。WMD 要解决的问题是：如何以最少的“总运输成本”将文档 A 所有的“土”恰好填满文档 B 所有的“坑”。将一单位土从文档 A 的一个词（如 Obama）移动到文档 B 的一个词（如 President）的成本，就是这两个词向量之间的欧氏距离。由于 Obama 和 President 的语义非常接近，它们的词向量在空间中的距离很小，因此移动成本很低。同样，media 到 press，Illinois 到 Chicago 的成本也都较低。

第二步：将问题建模为最优化问题（地球移动器距离 EMD）

WMD 将上述直观问题形式化为一个线性规划问题，这实际上是计算机视觉中地球移动器距离在文本上的应用。

  1. 定义变量：
    令 T 是一个非负矩阵，其元素 T_ij >= 0 表示从文档 A 的第 i 个词移动到文档 B 的第 j 个词的“土”的量。

  2. 定义目标函数（总成本）：
    总成本是所有运输量的加权和。目标是使总成本最小化。
    最小化： Sum_over_i Sum_over_j ( T_ij * Distance(词向量_i^A, 词向量_j^B) )
    其中 Distance 通常是欧氏距离。

  3. 定义约束条件：
    为了确保“土”被完全且合理地运输，需要施加约束：

    • 流出约束：对于文档 A 中的每一个词 i，从它运出的总土量必须等于它自身的权重。
      Sum_over_j T_ij = 文档A中词i的权重 （对所有 i 成立）
    • 流入约束：对于文档 B 中的每一个词 j，运入它的总土量必须等于它自身的权重。
      Sum_over_i T_ij = 文档B中词j的权重 （对所有 j 成立）

    这两个约束保证了文档 A 的所有权重都被运出，文档 B 的所有权重需求都被满足。

第三步：求解与解释

  1. 求解线性规划：上述问题（目标函数 + 约束条件）是一个标准的线性规划问题。可以使用现成的优化库（如 SciPy 中的 linprog 或专用的 EMD 求解器）来高效地求解出最优的流矩阵 T 和对应的最小总成本。

  2. 得到 WMD 距离：这个求得的最小总成本，就是词移距离 WMD。
    WMD(文档A, 文档B) = 最小化后的总运输成本

  3. 解释结果：

    • WMD 值越小，说明将文档 A 的语义“移动”到文档 B 所需的工作量越小，意味着两个文档的语义越相似。
    • WMD 值越大，说明两个文档的语义差异越大。

    在我们的例子中，由于 Obama/President, speaks/greets, media/press, Illinois/Chicago 都是近义词对，最优的运输方案 T 会倾向于将土在这些近义词对之间运输，从而得到一个很小的 WMD 值，准确反映了语义相似性。

第四步：算法特性与优化

  1. 优点：

    • 无需监督数据：WMD 是无监督的，直接利用预训练词向量。
    • 语义感知强：能有效处理词汇不匹配但语义相近的情况。
    • 理论优雅：有坚实的数学基础（最优传输理论）。

  2. 缺点与优化：

    • 计算复杂度高：求解线性规划的时间复杂度相对较高，对于词汇量大的文档或大规模文档集，计算可能很慢。
    • 优化方法：为了加速，提出了诸如 Word Centroid Distance（一个粗糙但快速的近似）以及使用剪枝技术来预先排除不可能的词对（基于词向量距离的下界），从而减少需要计算的变量数。

总结
词移距离通过将文档相似度计算建模为一个最优传输问题，巧妙地利用了词向量的几何特性。它计算的是将一个文档的语义内容（由加权的词向量集表示）“转换”为另一个文档的语义内容所需的最小代价。这个过程循序渐进，从直观的“运土”比喻，到严谨的线性规划建模，最后通过求解得到相似度度量。尽管计算成本较高，但 WMD 在需要高精度语义匹配的任务中依然是一个非常有价值的算法。

基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法详解 题目描述 词移距离（Word Mover's Distance, WMD）是一种用于衡量两个文本文档之间语义相似度的算法。其核心思想是将文档相似度计算问题转化为一个经典的运输问题：将一个文档中的词“移动”到另一个文档中的词，所需的最小“工作量”。这里的“工作量”由词在预训练词向量空间中的欧氏距离来定义。WMD 的优势在于它能够利用词向量的语义信息，即使两个文档没有共同的词汇，只要它们的词在语义上接近，WMD 也能给出较高的相似度。 解题过程 第一步：问题形式化与直观理解 假设我们有两个文档： 文档 A：“Obama speaks to the media in Illinois” 文档 B：“The President greets the press in Chicago” 我们的目标是量化文档 A 和文档 B 的语义相似度。 文档表示 ：首先，我们将每个文档表示为一组加权的词向量。这通常通过以下步骤完成： 分词 ：将文档分割成单词（或子词单元）。 去除停用词 （可选）：如“to", "the", "in”等，以减少噪声。 词向量化 ：为每个剩余的词查找其预训练好的词向量（例如，Word2Vec 或 GloVe 词向量）。词向量将每个词映射到一个高维空间中的点，语义相近的词在空间中的位置也相近。 权重分配 ：为每个词分配一个权重，通常使用 词袋模型 下的归一化词频（如 nBOW）。例如，如果一个词在文档中出现多次，它的权重就更高。权重之和为1。 经过处理后： 文档 A 可表示为： { (Obama, 权重_a1), (speaks, 权重_a2), (media, 权重_a3), (Illinois, 权重_a4) } 文档 B 可表示为： { (President, 权重_b1), (greets, 权重_b2), (press, 权重_b3), (Chicago, 权重_b4) } “移动”的直观理解 ：现在，想象文档 A 中的每个词都是一堆“土”，土的量等于该词的权重。文档 B 中的每个词是一个“坑”，需要填入的土量等于该词的权重。WMD 要解决的问题是：如何以最少的“总运输成本”将文档 A 所有的“土”恰好填满文档 B 所有的“坑”。将一单位土从文档 A 的一个词（如 Obama ）移动到文档 B 的一个词（如 President ）的成本，就是这两个词向量之间的欧氏距离。由于 Obama 和 President 的语义非常接近，它们的词向量在空间中的距离很小，因此移动成本很低。同样， media 到 press ， Illinois 到 Chicago 的成本也都较低。 第二步：将问题建模为最优化问题（地球移动器距离 EMD） WMD 将上述直观问题形式化为一个线性规划问题，这实际上是计算机视觉中 地球移动器距离 在文本上的应用。 定义变量 ： 令 T 是一个非负矩阵，其元素 T_ij >= 0 表示从文档 A 的第 i 个词移动到文档 B 的第 j 个词的“土”的量。 定义目标函数（总成本） ： 总成本是所有运输量的加权和。目标是使总成本最小化。 最小化： Sum_over_i Sum_over_j ( T_ij * Distance(词向量_i^A, 词向量_j^B) ) 其中 Distance 通常是欧氏距离。 定义约束条件 ： 为了确保“土”被完全且合理地运输，需要施加约束： 流出约束 ：对于文档 A 中的每一个词 i ，从它运出的总土量必须等于它自身的权重。 Sum_over_j T_ij = 文档A中词i的权重 （对所有 i 成立） 流入约束 ：对于文档 B 中的每一个词 j ，运入它的总土量必须等于它自身的权重。 Sum_over_i T_ij = 文档B中词j的权重 （对所有 j 成立） 这两个约束保证了文档 A 的所有权重都被运出，文档 B 的所有权重需求都被满足。 第三步：求解与解释 求解线性规划 ：上述问题（目标函数 + 约束条件）是一个标准的线性规划问题。可以使用现成的优化库（如 SciPy 中的 linprog 或专用的 EMD 求解器）来高效地求解出最优的流矩阵 T 和对应的 最小总成本 。 得到 WMD 距离 ：这个求得的最小总成本，就是词移距离 WMD。 WMD(文档A, 文档B) = 最小化后的总运输成本 解释结果 ： WMD 值越小 ，说明将文档 A 的语义“移动”到文档 B 所需的工作量越小，意味着两个文档的语义越相似。 WMD 值越大 ，说明两个文档的语义差异越大。 在我们的例子中，由于 Obama / President , speaks / greets , media / press , Illinois / Chicago 都是近义词对，最优的运输方案 T 会倾向于将土在这些近义词对之间运输，从而得到一个很小的 WMD 值，准确反映了语义相似性。 第四步：算法特性与优化 优点 ： 无需监督数据 ：WMD 是无监督的，直接利用预训练词向量。 语义感知强 ：能有效处理词汇不匹配但语义相近的情况。 理论优雅 ：有坚实的数学基础（最优传输理论）。 缺点与优化 ： 计算复杂度高 ：求解线性规划的时间复杂度相对较高，对于词汇量大的文档或大规模文档集，计算可能很慢。 优化方法 ：为了加速，提出了诸如 Word Centroid Distance（一个粗糙但快速的近似）以及使用剪枝技术来预先排除不可能的词对（基于词向量距离的下界），从而减少需要计算的变量数。 总结 词移距离通过将文档相似度计算建模为一个最优传输问题，巧妙地利用了词向量的几何特性。它计算的是将一个文档的语义内容（由加权的词向量集表示）“转换”为另一个文档的语义内容所需的最小代价。这个过程循序渐进，从直观的“运土”比喻，到严谨的线性规划建模，最后通过求解得到相似度度量。尽管计算成本较高，但 WMD 在需要高精度语义匹配的任务中依然是一个非常有价值的算法。