从教堂语料库中有效构造余弦相似矩阵

我有一个TF/IDF向量的语料库V，所以它们很稀疏。
这是一个数组大约2,500到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下面

来源

2017-09-05 Brian Dolan

给定一个数学任务（函数最大化），标准函数是什么？对此没有明确的说明。 *（cit。）*是“计算最有效的方法**（在此计算中使用Chapel）”的定量度量是什么？感谢Brian添加了这样一个清晰明了的声明，以使这种优化工作不会在移动的沙子上运行。 – user3666197

@ brian-dolan：上面的代码中有一些错误，我试图编辑，但它被拒绝，说我需要将编辑信息传达给你。问题在于ndocs和nftrs被声明为域，但随后用于声明一个数组（需要范围）以及内部for循环（需要一个整数）的绑定。这里是我提出的修正：使用Norm，LinearAlgebra; VAR ndocs = 2500， nftrs = 150000，文档= 1..ndocs， FTRS = 1..nftrs，五：[文档，FTRS]真实， X：[文档，文档]真实; 我在文档{ – Brad

@布拉德请不要觉得被拒绝！好吧，我会看看，并可能要求更多的帮助。啊，很久以前，当我对编程一无所知时...... –

下面的建议有一些改进，可以到原执行进行：

预先计算和所有i缓存dot(V[i, ..], V[i, ..])到一个数组，以减少重复计算。
使用1..V.size或V.domain代替1..V.shape[1]
- V.shape从域尺寸计算，而不是作为一个字段存储。
利用该尴尬的并行性质这个程序的，通过计算X并联

详情看到，探讨了这些变化及其对的定时影响GitHub issue。

来源

2017-11-26 17:57:08 bencray

[元：这个问题一直在考虑我，因为它没有得到答复这么久。由于使用了“计算效率最高”这个短语，我个人避而远之。在实践中，由于从一台目标机器或数据集到下一台目标机器或数据集可能会发生变化，因此很难保证任何解决方案都符合该描述。但是，因为没有其他人已经加强了，我希望他们可能会使用提出一些意见]

脱颖而出，我在你的代码有几件事情：

1）除非我错过了一些东西，在计算过程中，你会多次重复计算norm(V[r, ..])。渐近地说，这表明你正在做二次工作，只需要线性工作。我建议计算每一行的范曾并将其存储在阵列，以避免这种冗余计算：

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

然后，内环内，你可以参考normVrow[i]或normVrow[j]。2）由于这是Chapel，并且您的循环似乎没有交叉循环依赖性，而不是使用串行for循环，所以您应该使用并行的forall循环进行此计算。有一个关于是否的问题：

（a）您外环更改为forall（这会导致负载不平衡，因为整体迭代空间是三角形），

（二）改变这两个循环，以forall （这将通过过度分解来帮助负载不平衡问题，但可能还会增加开销），或者（c）使外环成为动态调度的循环以解决负载不平衡。

我的本能会做的选择c。使用教堂的dynamic迭代器：

use DynamicIters; 

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

3）考虑是避免三角迭代空间，只是冗余计算X[i,j]和X[j,i]即使他们” A最后一件事会有相同的价值。这对于共享内存运行可能没有意义，但是如果您在分布式阵列X上进行计算，则可能会减少通信，因为这些矩阵值将由不同的处理器存储。在这种方法中，您可以在X.domain之上迭代单个forall循环，并且默认情况下结果将良好地负载均衡，而不需要动态迭代器。

来源

2017-12-09 01:04:14 Brad

糟糕，我在浏览器中有一个这个问题的缓存副本，并没有注意到@bencray几周前已经回答了它。我的错。 – Brad

从教堂语料库中有效构造余弦相似矩阵

回答

相关问题