論文の概要: Clustering with Non-adaptive Subset Queries
- arxiv url: http://arxiv.org/abs/2409.10908v1
- Date: Tue, 17 Sep 2024 05:56:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-18 17:48:51.777012
- Title: Clustering with Non-adaptive Subset Queries
- Title（参考訳）: 非適応サブセットクエリによるクラスタリング
- Authors: Hadley Black, Euiwoong Lee, Arya Mazumdar, Barna Saha,
- Abstract要約: クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
- 参考スコア（独自算出の注目度）: 16.662507957069813
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recovering the underlying clustering of a set $U$ of $n$ points by asking pair-wise same-cluster queries has garnered significant interest in the last decade. Given a query $S \subset U$, $|S|=2$, the oracle returns yes if the points are in the same cluster and no otherwise. For adaptive algorithms with pair-wise queries, the number of required queries is known to be $\Theta(nk)$, where $k$ is the number of clusters. However, non-adaptive schemes require $\Omega(n^2)$ queries, which matches the trivial $O(n^2)$ upper bound attained by querying every pair of points. To break the quadratic barrier for non-adaptive queries, we study a generalization of this problem to subset queries for $|S|>2$, where the oracle returns the number of clusters intersecting $S$. Allowing for subset queries of unbounded size, $O(n)$ queries is possible with an adaptive scheme (Chakrabarty-Liao, 2024). However, the realm of non-adaptive algorithms is completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making $O(n \log k \cdot (\log k + \log\log n)^2)$ queries, which improves to $O(n \log \log n)$ when $k$ is a constant. We also consider algorithms with a restricted query size of at most $s$. In this setting we prove that $\Omega(\max(n^2/s^2,n))$ queries are necessary and obtain algorithms making $\tilde{O}(n^2k/s^2)$ queries for any $s \leq \sqrt{n}$ and $\tilde{O}(n^2/s)$ queries for any $s \leq n$. We also consider the natural special case when the clusters are balanced, obtaining non-adaptive algorithms which make $O(n \log k) + \tilde{O}(k)$ and $O(n\log^2 k)$ queries. Finally, allowing two rounds of adaptivity, we give an algorithm making $O(n \log k)$ queries in the general case and $O(n \log \log k)$ queries when the clusters are balanced.
- Abstract（参考訳）: ペアワイズな同クラスタクエリを問うことで、セットの基盤となるクラスタリングを$U$$n$ポイントで回収することは、この10年で大きな関心を集めてきた。
クエリ $S \subset U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$\Theta(nk)$で、$k$はクラスタの数である。
しかし、適応的でないスキームは$\Omega(n^2)$クエリを必要とし、これは全ての点を問うことで得られる自明な$O(n^2)$上限と一致する。
非適応クエリの二次障壁を断ち切るために、この問題を$|S|>2$のサブセットクエリに一般化し、オラクルは$S$と交差するクラスタの数を返す。
非有界サイズのサブセットクエリを許せば、適応的なスキームで$O(n)$クエリが可能である(Chakrabarty-Liao, 2024)。
しかし、非適応アルゴリズムの領域は全く不明である。
本稿では,サブセットクエリを用いたクラスタリングのための非適応アルゴリズムを提案する。
我々の主な結果は、$O(n \log k \cdot (\log k + \log\log n)^2)$クエリを作成する非適応アルゴリズムであり、$k$が定数であるときに$O(n \log \log n)$に改善される。
クエリサイズが制限されたアルゴリズムも検討しています。
この設定では、$\Omega(\max(n^2/s^2,n))$クエリが必要であることを証明し、$\tilde{O}(n^2k/s^2)$クエリを任意の$s \leq \sqrt{n}$および$\tilde{O}(n^2/s)$クエリを$s \leq n$とするアルゴリズムを得る。
また、クラスタのバランスが取れた場合には、$O(n \log k) + \tilde{O}(k)$および$O(n\log^2 k)$クエリを生成する非適応アルゴリズムを得る。
最後に,2ラウンドの適応性を実現するため,一般の場合で$O(n \log k)$クエリと,クラスタのバランスが取れた場合には$O(n \log \log k)$クエリを生成するアルゴリズムを提案する。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Active Learning of Classifiers with Label and Seed Queries [18.34182076906661]
ラベルクエリのみを許可する標準的なアクティブラーニング設定では、強い凸境界を持つ分類器を$gamma$で学習するには、最悪の場合は$Omegabig(k m log frac1gammabig)$ seedクエリが必要である。
2種類のクエリを慎重に組み合わせることで、$O(m2 log n)$ラベルクエリと$Obig(m log fracmgamma)を使って、$operatornamepoly(n+m)$でバイナリ分類器を時間内に学習できることが示されている。
論文 参考訳（メタデータ） (2022-09-08T18:46:23Z) - Optimal Clustering with Noisy Queries via Multi-Armed Bandit [19.052525950282234]
多くのアプリケーションによって動機づけられた私たちは、欠陥のあるオラクルでクラスタリングを研究します。
我々は,$O(fracn)delta2 + textpoly(k,frac1delta, log n)$クエリを用いた新しい時間アルゴリズムを提案する。
我々の主な要素は、我々の問題と多腕バンディットの興味深い関係である。
論文 参考訳（メタデータ） (2022-07-12T08:17:29Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-18T22:20:12Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Deterministic Algorithms for the Hidden Subgroup Problem [3.2590610391507444]
隠れ部分群問題に対する決定論的アルゴリズムを提案する。
アーベル群の場合、第1のアルゴリズムは最適なランダム化アルゴリズムと同じ最悪のクエリ複雑性を達成する。
非アーベル群に対する類似アルゴリズムは、最適ランダム化クエリの複雑さの$sqrt log n$ factorの範囲内にある。
論文 参考訳（メタデータ） (2021-04-29T15:55:15Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。