論文の概要: Do you know what q-means?
- arxiv url: http://arxiv.org/abs/2308.09701v1
- Date: Fri, 18 Aug 2023 17:52:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-21 12:18:29.533632
- Title: Do you know what q-means?
- Title（参考訳）: q-meansを知っていますか。
- Authors: Jo\~ao F. Doriguello, Alessandro Luongo, Ewin Tang
- Abstract要約: クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
- 参考スコア（独自算出の注目度）: 50.045011844765185
- License: http://creativecommons.org/publicdomain/zero/1.0/
- 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_1,\dots,v_N\in\mathbb{R}^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 (2019) which performs $\varepsilon$-$k$-means, an approximate version
of $k$-means clustering. This algorithm does not rely on the quantum linear
algebra primitives of prior work, instead only using its QRAM to prepare and
measure simple states based on the current iteration's clusters. The time
complexity is $O\big(\frac{k^{2}}{\varepsilon^2}(\sqrt{k}d + \log(Nd))\big)$
and maintains the polylogarithmic 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{k^{2}}{\varepsilon^2}(kd + \log(Nd))\big)$ time. Notably, this
classical algorithm matches the polylogarithmic dependence on $N$ attained by
the quantum algorithms.
- Abstract（参考訳）: クラスタリングは大規模なデータセットを分析する上で最も重要なツールの1つであり、おそらく最も人気のあるクラスタリングアルゴリズムは$k$-meansのロイドの反復である。
この反復では、$n$ベクター$v_1,\dots,v_n\in\mathbb{r}^d$を、$k$ centroids $c_1,\dots,c_k\in\mathbb{r}^d$を出力します。
我々は、Kerenidis, Landman, Luongo, Prakash (2019)によって提案された量子アルゴリズムである"$q$-means"アルゴリズムの全体的な改良版を紹介し、$k$-meansクラスタリングの近似バージョンである$\varepsilon$-$k$-meansを実行する。
このアルゴリズムは、以前の作業の量子線型代数プリミティブに頼るのではなく、現在の反復のクラスタに基づいて単純な状態の準備と測定にQRAMを使用する。
時間複雑性は$O\big(\frac{k^{2}}{\varepsilon^2}(\sqrt{k}d + \log(Nd))\big)$であり、他のほとんどのパラメータへの依存を改善しながら、$N$に対する多対数依存を維持する。
また、$O\big(\frac{k^{2}}{\varepsilon^2}(kd + \log(Nd))\big)$time で実行される $\varepsilon$-$k$-means に対して "dequantized" アルゴリズムを提案する。
特に、この古典的アルゴリズムは量子アルゴリズムによって達成された$N$の多対数依存と一致する。
関連論文リスト
- 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) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。