論文の概要: Sketching Transformed Matrices with Applications to Natural Language Processing

• arxiv url: http://arxiv.org/abs/2002.09812v1
• Date: Sun, 23 Feb 2020 03:07:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 09:28:57.790098
• Title: Sketching Transformed Matrices with Applications to Natural Language Processing
• Title（参考訳）: スケッチ変換行列と自然言語処理への応用
• Authors: Yingyu Liang, Zhao Song, Mengdi Wang, Lin F. Yang, Xin Yang
• Abstract要約: 本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
• 参考スコア（独自算出の注目度）: 76.6222695417524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose we are given a large matrix $A=(a_{i,j})$ that cannot be stored in memory but is in a disk or is presented in a data stream. However, we need to compute a matrix decomposition of the entry-wisely transformed matrix, $f(A):=(f(a_{i,j}))$ for some function $f$. Is it possible to do it in a space efficient way? Many machine learning applications indeed need to deal with such large transformed matrices, for example word embedding method in NLP needs to work with the pointwise mutual information (PMI) matrix, while the entrywise transformation makes it difficult to apply known linear algebraic tools. Existing approaches for this problem either need to store the whole matrix and perform the entry-wise transformation afterwards, which is space consuming or infeasible, or need to redesign the learning method, which is application specific and requires substantial remodeling. In this paper, we first propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. It works for a general family of transformations with provable small error bounds and thus can be used as a primitive in downstream learning tasks. We then apply this primitive to a concrete application: low-rank approximation. We show that our approach obtains small error and is efficient in both space and time. We complement our theoretical results with experiments on synthetic and real data.
• Abstract（参考訳）: 例えば、大きな行列$A=(a_{i,j})$はメモリに格納できないがディスクにあるか、データストリームに表示されていると仮定する。 しかし、ある関数 $f$ に対して、エントリーワイズ変換された行列 $f(A):=(f(a_{i,j}))$ の行列分解を計算する必要がある。 空間的に効率的に行うことは可能か? 多くの機械学習アプリケーションはそのような大きな変換行列を扱う必要があり、例えばNLPのワード埋め込み法はポイントワイド相互情報(PMI)行列を扱う必要があるが、エントリーワイド変換は既知の線形代数ツールの適用を困難にしている。 この問題に対する既存のアプローチでは、マトリックス全体を格納し、その後、空間消費や実現不可能であるエントリ・アズ・トランスフォーメーションを実行するか、アプリケーション固有の学習方法を再設計する必要がある。 本稿ではまず,与えられた小さな行列の積を変換行列で計算するための空間効率の高いスケッチアルゴリズムを提案する。 証明可能な小さなエラー境界を持つ変換の一般的なファミリーで機能するため、下流学習タスクにおいてプリミティブとして使用できる。 次に、このプリミティブを具体的応用であるローランク近似に適用する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。 我々は、理論結果を合成および実データの実験で補完する。

関連論文リスト

• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Kissing to Find a Match: Efficient Low-Rank Permutation Representation [33.880247068298374]
  そこで本稿では,低ランク行列係数化を用いて近似し,次いで非線形性を用いて,大きな置換行列の次元性の呪いに取り組むことを提案する。 提案手法の適用性とメリットを,様々な問題に対する一連の実験を通じて実証する。
  論文  参考訳（メタデータ） (2023-08-25T08:59:03Z)
• Multiresolution kernel matrix algebra [0.0]
  本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。 カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。 行列代数は擬微分計算によって数学的に正当化される。
  論文  参考訳（メタデータ） (2022-11-21T17:50:22Z)
• 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 Differentiable Matrix Square Root [65.67315418971688]
  微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。 前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。 もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
  論文  参考訳（メタデータ） (2022-01-21T12:18:06Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-09-16T18:42:21Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  テンソル分解は行列法で欠落する潜伏効果を拾うことができることを示す。 また,効率的なテンソル分解法を設計するための計算手法についても概説する。
  論文  参考訳（メタデータ） (2020-04-16T22:53:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。