論文の概要: Query Complexity of k-NN based Mode Estimation

• arxiv url: http://arxiv.org/abs/2010.13491v1
• Date: Mon, 26 Oct 2020 11:32:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 18:41:01.371490
• Title: Query Complexity of k-NN based Mode Estimation
• Title（参考訳）: k-NNに基づくモード推定のクエリ複雑性
• Authors: Anirudh Singhal, Subham Pirojiwala and Nikhil Karamchandani
• Abstract要約: 与えられた n 個の点のデータセットに対して、その点を最小の k 番目の近傍距離で同定する問題について検討する。 本研究では,信頼区間のアイデアに基づく逐次学習アルゴリズムを設計し,どのクエリをオラクルに送信するかを適応的に決定し,高い確率で問題を正しく解けるようにした。
• 参考スコア（独自算出の注目度）: 4.821253146561989
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the mode estimation problem of an unknown multivariate probability density function, we study the problem of identifying the point with the minimum k-th nearest neighbor distance for a given dataset of n points. We study the case where the pairwise distances are apriori unknown, but we have access to an oracle which we can query to get noisy information about the distance between any pair of points. For two natural oracle models, we design a sequential learning algorithm, based on the idea of confidence intervals, which adaptively decides which queries to send to the oracle and is able to correctly solve the problem with high probability. We derive instance-dependent upper bounds on the query complexity of our proposed scheme and also demonstrate significant improvement over the performance of other baselines via extensive numerical evaluations.
• Abstract（参考訳）: 未知の多変量確率密度関数のモード推定問題に動機づけられ,与えられたn点のデータセットに対して,最小k次近傍距離の点を同定する問題について検討した。 ペア間の距離が不明な場合について検討しますが、oracleにアクセスして、任意の2つのポイント間の距離に関するノイズ情報を取得することができます。 2つの自然オラクルモデルに対して、信頼区間のアイデアに基づいて逐次学習アルゴリズムを設計し、どのクエリをオラクルに送信するかを適応的に決定し、高い確率で問題を正しく解けるようにする。 提案手法の問合せ複雑性のインスタンス依存上界を導出し,広範囲な数値評価により,他のベースラインの性能に対して有意な改善を示す。

関連論文リスト

• 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)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• How to Design Robust Algorithms using Noisy Comparison Oracle [12.353002222958605]
  メトリクスに基づく比較操作は、様々なクラスタリング技術の研究に基本的である。 本稿では,最接近探索,最接近探索,最接近探索など様々な問題について検討する。 k中心クラスタリングと凝集階層クラスタリングのためのロバストなアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-05-12T16:58:09Z)
• Nearest Neighbor Search Under Uncertainty [19.225091554227948]
  Nearest Neighbor Search (NNS) は知識表現、学習、推論の中心的なタスクである。 NNSを不確実性(NNSU)下で研究する。
  論文  参考訳（メタデータ） (2021-03-08T20:20:01Z)
• ThetA -- fast and robust clustering via a distance parameter [3.0020405188885815]
  クラスタリングは機械学習の根本的な問題であり、遠隔ベースのアプローチが数十年にわたってこの分野を支配してきた。 Theta-based Algorithms (ThetA) と呼ばれる新しい距離しきい値法を提案する。
  論文  参考訳（メタデータ） (2021-02-13T23:16:33Z)
• Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms [0.0]
  与えられたクエリポイントのデータセットでk-nearestの隣人を見つける問題は、数年前から解決されてきた。 本稿では,K-Nearest Neighbor Search(K-Nearest Neighbor Search)の手法について,計算の視点から検討する。 本論文では,KNNSアプローチの対敵点に対する堅牢性を評価するために,汎用的な強化学習ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-02-10T16:10:58Z)
• Greedy k-Center from Noisy Distance Samples [10.363116234985515]
  距離空間における頂点の集合上の標準的k中心問題の変種について検討する。 1次元の点間の距離を返す次元サンプリング(dimension Smpling)と、1次元の点間の距離を返す雑音距離サンプリング(noisy Distance Smpling)である。 UCB,Thompson Smpling,Track-and-Stopなどのアイデアをベースとしたアクティブアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-03T19:37:02Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Neural Methods for Point-wise Dependency Estimation [129.93860669802046]
  我々は,2つの結果が共起する確率を定量的に測定する点依存度(PD)の推定に焦点をあてる。 提案手法の有効性を,1)MI推定,2)自己教師付き表現学習,3)クロスモーダル検索タスクで示す。
  論文  参考訳（メタデータ） (2020-06-09T23:26:15Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。 我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
  論文  参考訳（メタデータ） (2020-05-04T10:48:04Z)

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

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