論文の概要: Do you know what q-means?
- arxiv url: http://arxiv.org/abs/2308.09701v2
- Date: Thu, 20 Mar 2025 17:47:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-21 16:32:01.598388
- Title: Do you know what q-means?
- Title(参考訳): q-meansを知っていますか。
- Authors: Joao F. Doriguello, Alessandro Luongo, Ewin Tang,
- Abstract要約: Kerenidis, Landman, Luongo, Prakash (NeurIPS')によって提案された量子アルゴリズムの改良版を提案する。
我々のアルゴリズムは、先行研究の量子線型代数プリミティブに頼るのではなく、QRAMを用いて単純な状態を作成する。
また、$varepsilon$-$k$-meansに対して、$Obigで実行される"dequantized"アルゴリズムも提示する。
- 参考スコア(独自算出の注目度): 45.810803542748495
- License:
- Abstract: Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's iteration for $k$-means. This iteration takes $n$ vectors $V=[v_1,\dots,v_n]\in\mathbb{R}^{n\times d}$ and outputs $k$ centroids $c_1,\dots,c_k\in\mathbb{R}^d$; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present an overall improved version of the "$q$-means" algorithm, the quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS'19) which performs $\varepsilon$-$k$-means, an approximate version of $k$-means clustering. Our algorithm does not rely on quantum linear algebra primitives of prior work, but instead only uses QRAM to prepare simple states based on the current iteration's clusters and multivariate quantum amplitude estimation. The time complexity is $\widetilde{O}\big(\frac{\|V\|_F}{\sqrt{n}}\frac{k^{5/2}d}{\varepsilon}(\sqrt{k} + \log{n})\big)$ and maintains the logarithmic dependence on $n$ while improving the dependence on most of the other parameters. We also present a "dequantized" algorithm for $\varepsilon$-$k$-means which runs in $O\big(\frac{\|V\|_F^2}{n}\frac{k^{2}}{\varepsilon^2}(kd + \log{n})\big)$ time. Notably, this classical algorithm matches the logarithmic dependence on $n$ attained by the quantum algorithm.
- Abstract(参考訳): クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つであり、おそらく最も人気のあるクラスタリングアルゴリズムは、$k$-meansのロイドの反復である。
この反復は$n$のベクトルを$V=[v_1,\dots,v_n]\in\mathbb{R}^{n\times d}$で取り、$k$ centroids $c_1,\dots,c_k\in\mathbb{R}^d$で出力する。
我々は、Kerenidis, Landman, Luongo, Prakash (NeurIPS'19)によって提案された量子アルゴリズムである"$q$-means"アルゴリズムの全体的な改良版を紹介し、$k$-meansクラスタリングの近似バージョンである$\varepsilon$-$k$-meansを実行する。
我々のアルゴリズムは、先行研究の量子線型代数プリミティブに頼るのではなく、QRAMを使用して現在の反復のクラスタと多変量量子振幅推定に基づく単純な状態を作成する。
時間複雑性は$\widetilde{O}\big(\frac{\|V\|_F}{\sqrt{n}}\frac{k^{5/2}d}{\varepsilon}(\sqrt{k} + \log{n})\big)$であり、他のパラメータのほとんどへの依存を改善しながら$n$への対数依存を維持する。
また、$O\big(\frac{\|V\|_F^2}{n}\frac{k^{2}}{\varepsilon^2}(kd + \log{n})\big)$時間で走る$\varepsilon$-$k$-meansに対して「定式化」アルゴリズムを提案する。
特に、この古典的アルゴリズムは量子アルゴリズムによって達成された$n$の対数依存と一致する。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳(メタデータ) (2024-11-23T23:13:24Z) - Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳(メタデータ) (2024-07-15T20:04:06Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳(メタデータ) (2024-02-09T19:01:48Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳(メタデータ) (2023-10-29T16:46:26Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳(メタデータ) (2023-10-25T16:37:45Z) - 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) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳(メタデータ) (2023-06-05T12:22:46Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-06-30T15:49:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。