論文の概要: Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle
- arxiv url: http://arxiv.org/abs/2106.10374v1
- Date: Fri, 18 Jun 2021 22:20:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-22 15:43:30.610424
- Title: Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle
- Title（参考訳）: Oracleの故障によるクラスタリングのためのクエリ最適化と時間効率アルゴリズム
- Authors: Pan Peng, Jiapeng Zhang
- Abstract要約: 本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 7.449644976563424
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by applications in crowdsourced entity resolution in database,
signed edge prediction in social networks and correlation clustering, Mazumdar
and Saha [NIPS 2017] proposed an elegant theoretical model for studying
clustering with a faulty oracle. In this model, given a set of $n$ items which
belong to $k$ unknown groups (or clusters), our goal is to recover the clusters
by asking pairwise queries to an oracle. This oracle can answer the query that
``do items $u$ and $v$ belong to the same cluster?''. However, the answer to
each pairwise query errs with probability $\varepsilon$, for some
$\varepsilon\in(0,\frac12)$. Mazumdar and Saha provided two algorithms under
this model: one algorithm is query-optimal while time-inefficient (i.e.,
running in quasi-polynomial time), the other is time efficient (i.e., in
polynomial time) while query-suboptimal. Larsen, Mitzenmacher and Tsourakakis
[WWW 2020] then gave a new time-efficient algorithm for the special case of $2$
clusters, which is query-optimal if the bias $\delta:=1-2\varepsilon$ of the
model is large. It was left as an open question whether one can obtain a
query-optimal, time-efficient algorithm for the general case of $k$ clusters
and other regimes of $\delta$.
In this paper, we make progress on the above question and provide a
time-efficient algorithm with nearly-optimal query complexity (up to a factor
of $O(\log^2 n)$) for all constant $k$ and any $\delta$ in the regime when
information-theoretic recovery is possible. Our algorithm is built on a
connection to the stochastic block model.
- Abstract（参考訳）: データベースにおけるクラウドソーシングエンティティの解決,ソーシャルネットワークにおけるエッジ予測の署名,相関クラスタリングなどの応用に触発されて,MazumdarとSaha(NIPS 2017)は,クラスタリングを障害オラクルで研究するためのエレガントな理論的モデルを提案した。
このモデルでは、未知のグループ(またはクラスタ)に属する$n$アイテムのセットが与えられた場合、私たちのゴールは、オラクルにペアワイズクエリを要求することでクラスタを回復することです。
このオラクルは ``do items $u$ と $v$ が同じクラスタに属している'' というクエリに答えることができる。
しかし、各ペアワイズクエリerrに対する答えは$\varepsilon$であり、$\varepsilon\in(0,\frac12)$である。
mazumdarとsahaは、このモデルの下で2つのアルゴリズムを提供した: 1つのアルゴリズムはクエリ最適化であり、時間非効率である(すなわち、準多項時間で実行される)。
Larsen, Mitzenmacher and Tsourakakis [WWW 2020] はその後、2ドルクラスタの特別な場合に対して新しい時間効率のアルゴリズムを与え、バイアス $\delta:=1-2\varepsilon$ が大きければクエリ最適化となる。
一般に$k$クラスタや他の$\delta$のレギュレーションに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかという未解決の問題として残された。
本稿では,上記の問題に対して,情報理論的なリカバリが可能であれば,すべての定数$k$ に対して,ほぼ最適に近いクエリ複雑性(最大$o(\log^2 n)$) と,レジーム内の$\delta$ の時間効率アルゴリズムを提案する。
我々のアルゴリズムは確率ブロックモデルとの接続に基づいている。
関連論文リスト
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - 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) - 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z) - Query-Efficient Correlation Clustering [13.085439249887713]
相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。
相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。
我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
論文 参考訳（メタデータ） (2020-02-26T15:18:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。