論文の概要: Query-Efficient Correlation Clustering with Noisy Oracle

• arxiv url: http://arxiv.org/abs/2402.01400v2
• Date: Sun, 03 Nov 2024 11:54:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:41:55.566348
• Title: Query-Efficient Correlation Clustering with Noisy Oracle
• Title（参考訳）: ノイズの多いOracleによるクエリ効率の良い相関クラスタリング
• Authors: Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, Wei Chen,
• Abstract要約: 共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。 我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。 本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
• 参考スコア（独自算出の注目度）: 17.11782578276788
• License:
• Abstract: We study a general clustering setting in which we have $n$ elements to be clustered, and we aim to perform as few queries as possible to an oracle that returns a noisy sample of the weighted similarity between two elements. Our setting encompasses many application domains in which the similarity function is costly to compute and inherently noisy. We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB): fixed confidence and fixed budget settings. For both settings, we design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation clustering and study their theoretical guarantees. Our results are the first examples of polynomial-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.
• Abstract（参考訳）: 我々は,2つの要素間の重み付けされた類似性のノイズサンプルを返すオラクルに対して,できるだけ少数のクエリを実行するために,$n$要素をクラスタ化する一般的なクラスタリング環境について検討する。 我々の設定は、類似性関数が計算にコストがかかり、本質的にノイズの多い多くのアプリケーションドメインを含んでいる。 本稿では,Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB)のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化について紹介する。 いずれの設定においても,相関クラスタリングのための古典近似アルゴリズムとサンプリング戦略を組み合わせたアルゴリズムを設計し,その理論的保証について検討する。 本研究は, PE-CMABの場合の多項式時間アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。

関連論文リスト

• Sample-Efficient Clustering and Conquer Procedures for Parallel Large-Scale Ranking and Selection [0.0]
  並列コンピューティング環境では、相関ベースのクラスタリングは$mathcalO(p)$サンプル複雑性低減率を達成することができる。 ニューラルアーキテクチャ検索のような大規模AIアプリケーションでは、スクリーニングなしバージョンの手順が、サンプル効率の点で完全に順序づけられたベンチマークを驚くほど上回っている。
  論文  参考訳（メタデータ） (2024-02-03T15:56:03Z)
• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。 制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
  論文  参考訳（メタデータ） (2024-01-23T07:16:32Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
  論文  参考訳（メタデータ） (2021-04-18T07:46:28Z)
• Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects [0.0]
  Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。 この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。 本稿では,本手法の計算的側面について考察する。
  論文  参考訳（メタデータ） (2021-02-02T10:39:27Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)

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

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