論文の概要: Greedy k-Center from Noisy Distance Samples

• arxiv url: http://arxiv.org/abs/2011.01973v3
• Date: Mon, 4 Apr 2022 08:03:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 04:36:12.983928
• Title: Greedy k-Center from Noisy Distance Samples
• Title（参考訳）: ノイズ距離サンプルからのGreedy k-Center
• Authors: Neharika Jali, Nikhil Karamchandani, and Sharayu Moharir
• Abstract要約: 距離空間における頂点の集合上の標準的k中心問題の変種について検討する。 1次元の点間の距離を返す次元サンプリング(dimension Smpling)と、1次元の点間の距離を返す雑音距離サンプリング(noisy Distance Smpling)である。 UCB,Thompson Smpling,Track-and-Stopなどのアイデアをベースとしたアクティブアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.363116234985515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a variant of the canonical k-center problem over a set of vertices in a metric space, where the underlying distances are apriori unknown. Instead, we can query an oracle which provides noisy/incomplete estimates of the distance between any pair of vertices. We consider two oracle models: Dimension Sampling where each query to the oracle returns the distance between a pair of points in one dimension; and Noisy Distance Sampling where the oracle returns the true distance corrupted by noise. We propose active algorithms, based on ideas such as UCB, Thompson Sampling and Track-and-Stop developed in the closely related Multi-Armed Bandit problem, which adaptively decide which queries to send to the oracle and are able to solve the k-center problem within an approximation ratio of two with high probability. We analytically characterize instance-dependent query complexity of our algorithms and also demonstrate significant improvements over naive implementations via numerical evaluations on two real-world datasets (Tiny ImageNet and UT Zappos50K).
• Abstract（参考訳）: 我々は距離空間内の頂点の集合上の正準 k-中心問題(英語版)の変種について検討する。 その代わりに、任意の頂点間の距離をノイズ/不完全推定するオラクルをクエリできる。 私たちは2つのoracleモデルを検討しています: oracleに対する各クエリが1次元のポイント間の距離を返すディメンションサンプリングと、oracleがノイズによって腐敗した真の距離を返すノイズ距離サンプリングです。 我々は,オラクルに送信するクエリを適応的に決定し,高い確率で2の近似比でk中心問題を解くことができるマルチアームドバンディット問題において,ucb,トンプソンサンプリング,トラックアンドストップといったアイデアに基づくアクティブアルゴリズムを提案する。 実世界の2つのデータセット(Tiny ImageNet と UT Zappos50K)の数値評価により,本アルゴリズムのインスタンス依存クエリ複雑性を解析的に特徴付けるとともに,ネイティブ実装よりも大幅に改善したことを示す。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
  共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。 我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。 本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
  論文  参考訳（メタデータ） (2024-02-02T13:31:24Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• How to Design Robust Algorithms using Noisy Comparison Oracle [12.353002222958605]
  メトリクスに基づく比較操作は、様々なクラスタリング技術の研究に基本的である。 本稿では,最接近探索,最接近探索,最接近探索など様々な問題について検討する。 k中心クラスタリングと凝集階層クラスタリングのためのロバストなアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-05-12T16:58:09Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• ThetA -- fast and robust clustering via a distance parameter [3.0020405188885815]
  クラスタリングは機械学習の根本的な問題であり、遠隔ベースのアプローチが数十年にわたってこの分野を支配してきた。 Theta-based Algorithms (ThetA) と呼ばれる新しい距離しきい値法を提案する。
  論文  参考訳（メタデータ） (2021-02-13T23:16:33Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Cross-Domain Generalization Through Memorization: A Study of Nearest Neighbors in Neural Duplicate Question Detection [72.01292864036087]
  重複質問検出(DQD)は,コミュニティの効率向上と自動質問応答システムの実現に重要である。 我々は、DQDのクロスドメイン一般化のために、ニューラル表現を活用し、近接する隣人を研究する。 StackExchange、Spring、Quoraの各データセットの異なるクロスドメインシナリオにおいて、このメソッドの堅牢なパフォーマンスを観察します。
  論文  参考訳（メタデータ） (2020-11-22T19:19:33Z)
• Query Complexity of k-NN based Mode Estimation [4.821253146561989]
  与えられた n 個の点のデータセットに対して、その点を最小の k 番目の近傍距離で同定する問題について検討する。 本研究では,信頼区間のアイデアに基づく逐次学習アルゴリズムを設計し,どのクエリをオラクルに送信するかを適応的に決定し,高い確率で問題を正しく解けるようにした。
  論文  参考訳（メタデータ） (2020-10-26T11:32:08Z)

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

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