Fugu-MT 論文翻訳(概要): Learning a Latent Simplex in Input-Sparsity Time

論文の概要: Learning a Latent Simplex in Input-Sparsity Time

arxiv url: http://arxiv.org/abs/2105.08005v1
Date: Mon, 17 May 2021 16:40:48 GMT
ステータス: 処理完了
システム内更新日: 2021-05-18 18:07:40.194241
Title: Learning a Latent Simplex in Input-Sparsity Time
Title（参考訳）: 入力分離時間における潜在単純性学習
Authors: Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff and Samson Zhou
Abstract要約: 我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
参考スコア（独自算出の注目度）: 58.30321592603066
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider the problem of learning a latent $k$-vertex simplex $K\subset\mathbb{R}^d$, given access to $A\in\mathbb{R}^{d\times n}$, which can be viewed as a data matrix with $n$ points that are obtained by randomly perturbing latent points in the simplex $K$ (potentially beyond $K$). A large class of latent variable models, such as adversarial clustering, mixed membership stochastic block models, and topic models can be cast as learning a latent simplex. Bhattacharyya and Kannan (SODA, 2020) give an algorithm for learning such a latent simplex in time roughly $O(k\cdot\textrm{nnz}(A))$, where $\textrm{nnz}(A)$ is the number of non-zeros in $A$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$, which holds in many of these applications. Further, we show this assumption is necessary, as otherwise an algorithm for learning a latent simplex would imply an algorithmic breakthrough for spectral low rank approximation. At a high level, Bhattacharyya and Kannan provide an adaptive algorithm that makes $k$ matrix-vector product queries to $A$ and each query is a function of all queries preceding it. Since each matrix-vector product requires $\textrm{nnz}(A)$ time, their overall running time appears unavoidable. Instead, we obtain a low-rank approximation to $A$ in input-sparsity time and show that the column space thus obtained has small $\sin\Theta$ (angular) distance to the right top-$k$ singular space of $A$. Our algorithm then selects $k$ points in the low-rank subspace with the largest inner product with $k$ carefully chosen random vectors. By working in the low-rank subspace, we avoid reading the entire matrix in each iteration and thus circumvent the $\Theta(k\cdot\textrm{nnz}(A))$ running time.
Abstract（参考訳）: k$-vertex simplex $K\subset\mathbb{R}^d$, given access to $A\in\mathbb{R}^{d\times n}$, which can seen as a data matrix with $n$ points that are obtained by randomly perturbing latent points in the simplex $K$ (potentially beyond $K$)。逆クラスタリング、混合メンバシップ確率ブロックモデル、トピックモデルなど、潜在変数モデルの大きなクラスは、潜在単純性の学習としてキャストできる。 Bhattacharyya and Kannan (SODA, 2020) は、およそ$O(k\cdot\textrm{nnz}(A))$、$\textrm{nnz}(A)$は$A$の非ゼロの数である。実行時間における$k$への依存は、これらの多くのアプリケーションで成り立つ$a$の最上位の$k$特異値の質量に関する自然な仮定を考えると不要であることを示している。さらに, 潜在単純性を学ぶアルゴリズムは, スペクトル低ランク近似のアルゴリズム的ブレークスルーを意味するため, この仮定は必要であることを示す。高いレベルでは、bhattacharyyaとkannanは、$k$ matrix-vector製品クエリを$a$とし、各クエリは、それ以前のすべてのクエリの関数である適応アルゴリズムを提供する。各行列ベクトル積は $\textrm{nnz}(A)$ time を必要とするので、全体の実行時間は避けられない。代わりに、入力スパース時間にa$に低いランクの近似を求め、それによって得られる列空間が、右トップ-k$特異空間にわずかに$\sin\theta$(三角形)距離を持つことを示す。アルゴリズムは次に、最も大きい内部積を持つ低ランク部分空間の$k$ポイントを、慎重に選択されたランダムベクトルで選択する。低ランクな部分空間で作業することで、各イテレーションで行列全体の読み込みを回避し、$\Theta(k\cdot\textrm{nnz}(A))$ run timeを回避します。

論文の概要: Learning a Latent Simplex in Input-Sparsity Time

関連論文リスト