論文の概要: Clustering with Queries under Semi-Random Noise

• arxiv url: http://arxiv.org/abs/2206.04583v1
• Date: Thu, 9 Jun 2022 16:02:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-10 18:25:57.904593
• Title: Clustering with Queries under Semi-Random Noise
• Title（参考訳）: 半ランダム雑音下でのクエリによるクラスタリング
• Authors: Alberto Del Pia, Mingchen Ma, Christos Tzamos
• Abstract要約: 一般半ランダム雑音を許容する頑健な学習法を開発した。 理論的には$Oleft(fracnk log n (1-2p)2right)$ query suffice to learn any cluster of enough large size。
• 参考スコア（独自算出の注目度）: 13.817228853960655
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The seminal paper by Mazumdar and Saha \cite{MS17a} introduced an extensive line of work on clustering with noisy queries. Yet, despite significant progress on the problem, the proposed methods depend crucially on knowing the exact probabilities of errors of the underlying fully-random oracle. In this work, we develop robust learning methods that tolerate general semi-random noise obtaining qualitatively the same guarantees as the best possible methods in the fully-random model. More specifically, given a set of $n$ points with an unknown underlying partition, we are allowed to query pairs of points $u,v$ to check if they are in the same cluster, but with probability $p$, the answer may be adversarially chosen. We show that information theoretically $O\left(\frac{nk \log n} {(1-2p)^2}\right)$ queries suffice to learn any cluster of sufficiently large size. Our main result is a computationally efficient algorithm that can identify large clusters with $O\left(\frac{nk \log n} {(1-2p)^2}\right) + \text{poly}\left(\log n, k, \frac{1}{1-2p} \right)$ queries, matching the guarantees of the best known algorithms in the fully-random model. As a corollary of our approach, we develop the first parameter-free algorithm for the fully-random model, answering an open question by \cite{MS17a}.
• Abstract（参考訳）: Mazumdar と Saha \cite{MS17a} によるセミナー論文では、ノイズの多いクエリによるクラスタリングに関する広範な研究が紹介された。 しかし、この問題に対する大きな進展にもかかわらず、提案手法は基礎となる完全ランダムなオラクルのエラーの正確な確率を知ることに大きく依存している。 本研究では,一般半ランダムノイズを許容するロバストな学習手法を開発し,完全ランダムモデルにおける最善の手法と定性的に同じ保証を得る。 より具体的には、未知のパーティションを持つ$n$の点集合が与えられた場合、同じクラスタにあるかどうかを確認するために$u,v$の点対を問うことができるが、確率$p$の場合、答えは逆選択される可能性がある。 理論的には$O\left(\frac{nk \log n} {(1-2p)^2}\right)$クエリは十分な大きさのクラスタを学習するのに十分である。 我々の主な結果は、大クラスタを$O\left(\frac{nk \log n} {(1-2p)^2}\right) + \text{poly}\left(\log n, k, \frac{1}{1-2p} \right)$クエリで識別し、完全ランダムモデルの最もよく知られたアルゴリズムの保証と一致する。 提案手法の補足として,完全ランダムモデルに対するパラメータフリーな最初のアルゴリズムを考案し,公開質問に対して \cite{ms17a} で回答した。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• 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)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• 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)
• 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)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)
• Query-Efficient Correlation Clustering [13.085439249887713]
  相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。 相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。 我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-02-26T15:18:20Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。