論文の概要: An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute
the Word Mover's Distance
- arxiv url: http://arxiv.org/abs/2005.06727v3
- Date: Mon, 22 Mar 2021 20:35:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 04:49:06.989790
- Title: An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute
the Word Mover's Distance
- Title（参考訳）: ワードムーバー距離計算のための効率的な共有メモリ並列spinhorn-knoppアルゴリズム
- Authors: Jesmin Jahan Tithi and Fabrizio Petrini
- Abstract要約: Word Mover's Distance (WMD) は、2つの文書間の意味的相違を測定するメトリクスである。
我々は、他の多くの文書に対して、ある文書のWMDを計算するための共有メモリ並列アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.18275108630751835
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Word Mover's Distance (WMD) is a metric that measures the semantic
dissimilarity between two text documents by computing the cost of moving all
words of a source/query document to the most similar words of a target document
optimally. Computing WMD between two documents is costly because it requires
solving an optimization problem that costs \(O(V^3log(V))\) where \(V\) is the
number of unique words in the document. Fortunately, the WMD can be framed as
the Earth Mover's Distance (EMD) (also known as the Optimal Transportation
Distance) for which it has been shown that the algorithmic complexity can be
reduced to \(O(V^2)\) by adding an entropy penalty to the optimization problem
and a similar idea can be adapted to compute WMD efficiently. Additionally, the
computation can be made highly parallel by computing WMD of a single query
document against multiple target documents at once (e.g., finding whether a
given tweet is similar to any other tweets happened in a day). In this paper,
we present a shared-memory parallel Sinkhorn-Knopp Algorithm to compute the WMD
of one document against many other documents by adopting the \(O(V^2)\) EMD
algorithm. We used algorithmic transformations to change the original dense
compute-heavy kernel to a sparse compute kernel and obtained \(67\times\)
speedup using \(96\) cores on the state-of-the-art of Intel\textregistered{}
4-sockets Cascade Lake machine w.r.t. its sequential run. Our parallel
algorithm is over \(700\times\) faster than the naive parallel python code that
internally uses optimized matrix library calls.
- Abstract（参考訳）: Word Mover's Distance (WMD) は、ソース/クエリ文書の全ての単語をターゲット文書の最も類似した単語に最適に移動させるコストを計算することで、2つのテキスト文書間の意味的相違を測定するメトリクスである。
2つの文書間の WMD の計算には、文書内の一意な単語の数である \(O(V^3log(V))\) のコストがかかる最適化問題を解く必要があるため、コストがかかる。
幸いなことに、WMDは、最適化問題にエントロピーペナルティを加えてアルゴリズムの複雑さを(O(V^2)\)に減らすことができ、類似のアイデアをWMDの計算に効率的に適用できることが示されている、Earth Mover's Distance (EMD) (Optimal Transportation Distance) としてフレーム化することができる。
さらに、単一のクエリドキュメントのwmdを複数のターゲットドキュメントに対して一度に計算することで、計算を高度に並列化することができる(例えば、あるツイートが1日で他のツイートと類似しているかどうかを判断する)。
本稿では、共有メモリ並列Sinkhorn-Knoppアルゴリズムを用いて、他の多くの文書に対して1つの文書の WMD を計算し、 \(O(V^2)\) EMD アルゴリズムを採用する。
アルゴリズム変換を用いて計算量の多いオリジナルのカーネルをスパース計算カーネルに変更し、intel\textregistered{} 4-socketsカスケードレイクマシン w.r.t. の最先端で \(96\) コアを使った \(67\times\) speedup を得た。
我々の並列アルゴリズムは、最適化された行列ライブラリ呼び出しを内部的に使用する単純並列ピソンコードよりも高速である。
関連論文リスト
- Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。
実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。
本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-13T02:44:05Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文 参考訳（メタデータ） (2021-12-17T17:04:34Z) - A New Parallel Algorithm for Sinkhorn Word-Movers Distance and Its
Performance on PIUMA and Xeon CPU [0.3655021726150367]
Word Movers Distance (WMD)は、2つの文書間の意味的相違を測定する。
我々は、他の多くの文書に対して1つの文書のWMDを計算するために、共有メモリ並列Sinkhorn-Knoppアルゴリズムを提案する。
並列実装は、Intel Cascade Lakeシステムの4つのNUMAソケットにまたがる96コアでの67倍の高速化を実現している。
論文 参考訳（メタデータ） (2021-07-14T00:29:18Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Accelerating Text Mining Using Domain-Specific Stop Word Lists [57.76576681191192]
本稿では,超平面的アプローチと呼ばれるドメイン固有語の自動抽出手法を提案する。
ハイパープレーンベースのアプローチは、無関係な特徴を排除することによって、テキストの寸法を著しく削減することができる。
その結果,超平面型アプローチはコーパスの寸法を90%削減し,相互情報より優れることがわかった。
論文 参考訳（メタデータ） (2020-11-18T17:42:32Z) - Exact, Parallelizable Dynamic Time Warping Alignment with Linear Memory [0.0]
我々は,O(M+N)メモリを用いて,正確な大域的最適DTWアライメントを計算する分割・征服アルゴリズムを提案する。
我々のアルゴリズムは、同じメモリ制約でmin(M, N)の係数まで並列化できるので、十分なGPUで教科書版よりも効率的に実行できる。
論文 参考訳（メタデータ） (2020-08-04T15:00:33Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。