論文の概要: Streaming Coresets for Symmetric Tensor Factorization
- arxiv url: http://arxiv.org/abs/2006.01225v2
- Date: Mon, 13 Jul 2020 17:49:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 06:50:19.588983
- Title: Streaming Coresets for Symmetric Tensor Factorization
- Title(参考訳): 対称テンソル分解のためのストリーミングコアセット
- Authors: Rachit Chhaya, Jayesh Choudhari, Anirban Dasgupta, Supratim Shit
- Abstract要約: ストリーミング環境でテンソルを効率的に分解する方法を示す。
本稿では,オンラインフィルタリングとカーネル化という2つの新しいアルゴリズム手法を紹介する。
単一トピックモデリング学習におけるアルゴリズムの適用例を示す。
- 参考スコア(独自算出の注目度): 9.181791777532608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Factorizing tensors has recently become an important optimization module in a
number of machine learning pipelines, especially in latent variable models. We
show how to do this efficiently in the streaming setting. Given a set of $n$
vectors, each in $\mathbb{R}^d$, we present algorithms to select a sublinear
number of these vectors as coreset, while guaranteeing that the CP
decomposition of the $p$-moment tensor of the coreset approximates the
corresponding decomposition of the $p$-moment tensor computed from the full
data. We introduce two novel algorithmic techniques: online filtering and
kernelization. Using these two, we present six algorithms that achieve
different tradeoffs of coreset size, update time and working space, beating or
matching various state of the art algorithms. In the case of matrices
($2$-ordered tensor), our online row sampling algorithm guarantees $(1 \pm
\epsilon)$ relative error spectral approximation. We show applications of our
algorithms in learning single topic modeling.
- Abstract(参考訳): 最近、ファクタリングテンソルは、多くの機械学習パイプライン、特に潜在変数モデルにおいて重要な最適化モジュールになっている。
ストリーミング環境でこれを効率的に行う方法を示します。
1組の$n$ベクターが与えられ、それぞれ$\mathbb{r}^d$が与えられると、これらのベクターの部分線型数をcoresetとして選択するアルゴリズムが与えられ、一方で、コアセットの$p$-momentテンソルのcp分解は、全データから計算された$p$-momentテンソルの分解を近似する。
オンラインフィルタリングとカーネル化という2つの新しいアルゴリズム手法を提案する。
これら2つのアルゴリズムを用いて,コアセットサイズ,更新時間,作業スペースの異なるトレードオフを実現する6つのアルゴリズムを提案する。
行列(2$-ordered tensor)の場合、オンライン行サンプリングアルゴリズムは$(1 \pm \epsilon)$相対誤差スペクトル近似を保証する。
単一トピックモデリング学習におけるアルゴリズムの適用例を示す。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳(メタデータ) (2024-11-23T23:13:24Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳(メタデータ) (2022-10-21T15:56:13Z) - Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳(メタデータ) (2022-07-15T11:55:09Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳(メタデータ) (2022-07-09T09:14:12Z) - Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured
Inputs [2.737640280995564]
我々はネットワーク埋め込みを用いてテンソルネットワーク構造入力の次元的低減を行う。
このような埋め込みを用いて、入力データを効率的にスケッチするアルゴリズムを提供する。
列車のラウンドリングのための既存のアルゴリズムの最適性を示す。
論文 参考訳(メタデータ) (2022-05-26T05:27:31Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳(メタデータ) (2022-02-09T15:26:03Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear
Circuits [4.129484350382891]
深さ$3$の算術回路のクラスに対して、新しい効率的なブラックボックス再構成アルゴリズムを提供する。
我々のアルゴリズムは、すべてのフィールド特性 0 以上の大きな特性に作用する。
論文 参考訳(メタデータ) (2021-05-04T20:45:07Z) - Fast Tensor Disentangling Algorithm [0.0]
本稿では, 互いに絡み合うユニタリテンソルを最適化する近似的, 高速, 簡易なアルゴリズムを提案する。
我々のアルゴリズムは以前の反復アルゴリズムよりも高速であり、しばしば最小の10から40%以内の残絡エントロピーをもたらす。
論文 参考訳(メタデータ) (2021-04-16T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。