從教堂語料庫中有效構造餘弦相似矩陣

我有一個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

從教堂語料庫中有效構造餘弦相似矩陣

回答

相關問題