論文の概要: Sublinear Time Approximation of Text Similarity Matrices
- arxiv url: http://arxiv.org/abs/2112.09631v1
- Date: Fri, 17 Dec 2021 17:04:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-20 14:05:54.792998
- Title: Sublinear Time Approximation of Text Similarity Matrices
- Title(参考訳): テキスト類似度行列の線形時間近似
- Authors: Archan Ray, Nicholas Monath, Andrew McCallum, Cameron Musco
- Abstract要約: 一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
- 参考スコア(独自算出の注目度): 50.73398637380375
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study algorithms for approximating pairwise similarity matrices that arise
in natural language processing. Generally, computing a similarity matrix for
$n$ data points requires $\Omega(n^2)$ similarity computations. This quadratic
scaling is a significant bottleneck, especially when similarities are computed
via expensive functions, e.g., via transformer models. Approximation methods
reduce this quadratic complexity, often by using a small subset of exactly
computed similarities to approximate the remainder of the complete pairwise
similarity matrix.
Significant work focuses on the efficient approximation of positive
semidefinite (PSD) similarity matrices, which arise e.g., in kernel methods.
However, much less is understood about indefinite (non-PSD) similarity
matrices, which often arise in NLP. Motivated by the observation that many of
these matrices are still somewhat close to PSD, we introduce a generalization
of the popular Nystr\"{o}m method to the indefinite setting. Our algorithm can
be applied to any similarity matrix and runs in sublinear time in the size of
the matrix, producing a rank-$s$ approximation with just $O(ns)$ similarity
computations.
We show that our method, along with a simple variant of CUR decomposition,
performs very well in approximating a variety of similarity matrices arising in
NLP tasks. We demonstrate high accuracy of the approximated similarity matrices
in the downstream tasks of document classification, sentence similarity, and
cross-document coreference.
- Abstract(参考訳): 自然言語処理において生じるペアワイズ類似度行列を近似するアルゴリズムについて検討する。
一般に、$n$のデータポイントに対する類似性行列の計算には$\Omega(n^2)$類似性計算が必要である。
この二次スケーリングは重要なボトルネックであり、特に変換器モデルのような高価な関数によって類似性が計算される場合である。
近似法は、しばしば完全対類似行列の残りを近似するために、正確に計算された類似性の小さな部分集合を使用することによって、この二次複雑性を減少させる。
重要な研究は、例えばカーネル法で生じる正半定値類似度行列(PSD)の効率的な近似に焦点を当てている。
しかしながら、NLPでしばしば生じる不定(非PSD)類似性行列については、はるかに理解されていない。
これらの行列の多くがまだpsdに近いという観測に動機づけられ、人気のある nystr\"{o}m 法を不定値設定に一般化した。
我々のアルゴリズムは任意の類似度行列に適用でき、行列のサイズでサブ線形時間で動作し、わずか$O(ns)$類似度計算でランク=$s$近似を生成する。
提案手法は,単純なCUR分解の変形とともに,NLPタスクに生じる類似度行列の近似に非常に有効であることを示す。
文書分類, 文類似性, 文書間照合の下流タスクにおいて, 近似類似度行列の精度が高いことを示す。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳(メタデータ) (2023-03-30T15:48:26Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳(メタデータ) (2022-02-25T16:35:26Z) - 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) - Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity [15.023842222803058]
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。
本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。
合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
論文 参考訳(メタデータ) (2021-12-03T14:39:10Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳(メタデータ) (2021-06-16T04:07:48Z) - Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on
Gaussian and Random Orthogonal Ensembles [12.005731086591139]
Householder Dice (HD) は、高密度ランダム行列アンサンブルのダイナミクスを翻訳不変特性でシミュレートするアルゴリズムである。
HDアルゴリズムのメモリとコストはそれぞれ$mathcalO(nT)$と$mathcalO(nT2)$である。
数値結果は、高次元ランダムシステムの研究における新しい計算ツールとしてのHDアルゴリズムの約束を示しています。
論文 参考訳(メタデータ) (2021-01-19T04:50:53Z) - Estimating Multiple Precision Matrices with Cluster Fusion
Regularization [0.90238471756546]
異なるクラスから複数の精度行列を推定するペナライズされた可能性を提案する。
既存の手法の多くは、精度行列間の関係に関する情報を含まないか、あるいはこの情報を先入観として要求する。
論文 参考訳(メタデータ) (2020-03-01T01:03:22Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳(メタデータ) (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。