从 Chapel 语料库高效构建余弦相似度矩阵

Question

我有 V 个 TF/IDF 向量的语料库，所以它们非常稀疏。
这是一个大约 2,500 x 150,000 的数组。
我想计算语料库中每个文档之间的余弦相似度。

这几乎是我能想到的最天真的方法了。我已经知道三四个优化，但我不想假设答案。我想知道在此计算中使用 Chapel 的计算效率最高的方法。目标是将 X 作为具有 diag(X) = 0

的对称矩阵

use Norm,
    LinearAlgebra;

var ndocs = 2500,
    nftrs = 150000,
    docs = 1..ndocs,
    ftrs = 1..nftrs,
    V: [docs, ftrs] real,
    X: [docs, docs] real;

for i in docs {
  var n1 = norm(V[i,..]);
  for j in (i+1)..ndocs {
    var n2 = norm(V[j,..]);
    var c = dot(V[i,..], V[j,..]) / (n1*n2);
    X[i,j] = c;
    X[j,i] = c;
  }
}

编译使用

chpl -I/usr/local/Cellar/openblas/0.2.20/include -L/usr/local/Cellar/openblas/0.2.20/lib -lblas cosim.chpl

== 已更新 ==

这实际上应该编译运行。原始代码存在以下@bradcray 建议的错误

Answer 1

以下是可以对原始实现进行的一些改进：

将所有 i 的 dot(V[i, ..], V[i, ..]) 预先计算并缓存到一个数组中，以减少重复计算。
使用1..V.size或V.domain代替1..V.shape[1]
- V.shape 是根据域大小计算的，而不是存储为字段。
利用此程序的令人尴尬的并行性质，通过并行计算X

有关详细信息，请参阅探讨这些更改及其对计时的影响的 GitHub issue。

Answer 2

[Meta：这个问题一直困扰着我，因为它已经很久没有得到解答了。由于它使用了 "most computationally efficient." 短语，我个人一直回避它。在实践中，很难保证任何解决方案都符合该描述，因为一台目标机器或数据集可能会发生变化。但由于没有其他人站出来，我将发表一些评论，希望它们可能有用。]

你的代码中有几点对我来说很突出：

1) 除非我遗漏了什么，否则您在计算过程中多次重复计算 norm(V[r, ..])。渐近地讲，这表明您在只需要线性工作的情况下进行二次工作。我建议为每一行计算一次范数并将其存储在数组中以避免这种冗余计算：

var normVrow: [docs] real = [r in docs] norm(V[r,..]);

然后，在内部循环中，您可以直接引用normVrow[i]或normVrow[j]。

2) 因为这是 Chapel 并且您的循环似乎没有交叉循环依赖性，而不是使用串行 for 循环，您应该使用并行 forall 循环进行此计算。有一个关于是否要的问题：

(a) 将您的外循环更改为 forall（这将导致负载不平衡，因为整个迭代 space 是三角形的），

(b) 将两个循环更改为 forall 循环（这将通过过度分解帮助解决负载不平衡问题，但也可能增加开销），或

(c) 将外层循环变成动态调度循环，解决负载不均衡问题

我的直觉是使用 Chapel 的 dynamic 迭代器来执行选项 c:

use DynamicIters;

forall i in dynamic(ndocs) {
  ...
}

3) 最后要考虑的事情是避免三角迭代 space 并且只是冗余计算 X[i,j] 和 X[j,i] 即使它们具有相同的值。这在共享内存运行上可能没有意义，但如果您在分布式数组 X 上计算，您可能会减少通信，因为这些矩阵值将由不同的处理器存储。在这种方法中，您可以在 X.domain 上使用单个 forall 循环进行迭代，结果默认情况下负载平衡良好，无需动态迭代器。

从 Chapel 语料库高效构建余弦相似度矩阵

Efficient construction of cosine similarity matrix from corpus in Chapel

sparse-matrix

cosine-similarity

chapel