論文の概要: How to Design Robust Algorithms using Noisy Comparison Oracle

• arxiv url: http://arxiv.org/abs/2105.05782v1
• Date: Wed, 12 May 2021 16:58:09 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-13 14:58:48.061621
• Title: How to Design Robust Algorithms using Noisy Comparison Oracle
• Title（参考訳）: ノイズ比較によるロバストアルゴリズムの設計方法 oracle
• Authors: Raghavendra Addanki, Sainyam Galhotra, Barna Saha
• Abstract要約: メトリクスに基づく比較操作は、様々なクラスタリング技術の研究に基本的である。 本稿では,最接近探索,最接近探索,最接近探索など様々な問題について検討する。 k中心クラスタリングと凝集階層クラスタリングのためのロバストなアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 12.353002222958605
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Metric based comparison operations such as finding maximum, nearest and farthest neighbor are fundamental to studying various clustering techniques such as $k$-center clustering and agglomerative hierarchical clustering. These techniques crucially rely on accurate estimation of pairwise distance between records. However, computing exact features of the records, and their pairwise distances is often challenging, and sometimes not possible. We circumvent this challenge by leveraging weak supervision in the form of a comparison oracle that compares the relative distance between the queried points such as `Is point u closer to v or w closer to x?'. However, it is possible that some queries are easier to answer than others using a comparison oracle. We capture this by introducing two different noise models called adversarial and probabilistic noise. In this paper, we study various problems that include finding maximum, nearest/farthest neighbor search under these noise models. Building upon the techniques we develop for these comparison operations, we give robust algorithms for k-center clustering and agglomerative hierarchical clustering. We prove that our algorithms achieve good approximation guarantees with a high probability and analyze their query complexity. We evaluate the effectiveness and efficiency of our techniques empirically on various real-world datasets.
• Abstract（参考訳）: 最大値,最近値,最遠値などのメトリックベースの比較操作は,$k$-centerクラスタリングや集約階層クラスタリングなど,さまざまなクラスタリング技術を研究する上での基礎となる。 これらの手法はレコード間のペアワイズ距離の正確な推定に依存する。 しかし、レコードの正確な特徴と対距離を計算することはしばしば困難であり、時には不可能である。 我々は「点 u は v に近いか、w は x に近いか?」のようなクエリされた点間の相対距離を比較する比較オラクルの形で弱い監督を利用することで、この課題を回避する。 しかし、いくつかのクエリは、比較oracleを使用して、他のクエリよりも答えやすい可能性がある。 これを2つの異なるノイズモデル(adversarial and probabilistic noise)を導入することで捉える。 本稿では,これらのノイズモデルに基づく最接近探索,最接近探索,最遠探索など様々な問題について検討する。 これらの比較操作のために開発した手法に基づき、k中心クラスタリングと凝集階層クラスタリングのためのロバストアルゴリズムを与える。 提案アルゴリズムは高い確率で良好な近似保証を実現し,クエリの複雑さを解析する。 本手法の有効性と効率を実世界の様々なデータセットで実証的に評価する。

関連論文リスト

• Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
  共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。 我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。 本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
  論文  参考訳（メタデータ） (2024-02-02T13:31:24Z)
• Linear time Evidence Accumulation Clustering with KMeans [0.0]
  この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。 分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。 k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
  論文  参考訳（メタデータ） (2023-11-15T14:12:59Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• A sampling-based approach for efficient clustering in large datasets [0.8952229340927184]
  本稿では,多数のクラスタを持つ高次元データに対して,簡便かつ効率的なクラスタリング手法を提案する。 私たちのコントリビューションは、データポイントとクラスタの完全な比較を必要としないため、k-meansよりもはるかに効率的です。
  論文  参考訳（メタデータ） (2021-12-29T19:15:20Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Learning with Group Noise [106.56780716961732]
  グループノイズを用いた学習のための新しいマックスマッチング手法を提案する。 いくつかの学習パラダイムの領域における実世界のデータセットのレンジのパフォーマンスは、Max-Matchingの有効性を示している。
  論文  参考訳（メタデータ） (2021-03-17T06:57:10Z)
• ThetA -- fast and robust clustering via a distance parameter [3.0020405188885815]
  クラスタリングは機械学習の根本的な問題であり、遠隔ベースのアプローチが数十年にわたってこの分野を支配してきた。 Theta-based Algorithms (ThetA) と呼ばれる新しい距離しきい値法を提案する。
  論文  参考訳（メタデータ） (2021-02-13T23:16:33Z)
• Query Complexity of k-NN based Mode Estimation [4.821253146561989]
  与えられた n 個の点のデータセットに対して、その点を最小の k 番目の近傍距離で同定する問題について検討する。 本研究では,信頼区間のアイデアに基づく逐次学習アルゴリズムを設計し,どのクエリをオラクルに送信するかを適応的に決定し,高い確率で問題を正しく解けるようにした。
  論文  参考訳（メタデータ） (2020-10-26T11:32:08Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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