論文の概要: Nearest Neighbor Search Under Uncertainty

• arxiv url: http://arxiv.org/abs/2103.05057v1
• Date: Mon, 8 Mar 2021 20:20:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-11 04:14:50.042639
• Title: Nearest Neighbor Search Under Uncertainty
• Title（参考訳）: 不確実性下での近接探索
• Authors: Blake Mason, Ardhendu Tripathy, Robert Nowak
• Abstract要約: Nearest Neighbor Search (NNS) は知識表現、学習、推論の中心的なタスクである。 NNSを不確実性(NNSU)下で研究する。
• 参考スコア（独自算出の注目度）: 19.225091554227948
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nearest Neighbor Search (NNS) is a central task in knowledge representation, learning, and reasoning. There is vast literature on efficient algorithms for constructing data structures and performing exact and approximate NNS. This paper studies NNS under Uncertainty (NNSU). Specifically, consider the setting in which an NNS algorithm has access only to a stochastic distance oracle that provides a noisy, unbiased estimate of the distance between any pair of points, rather than the exact distance. This models many situations of practical importance, including NNS based on human similarity judgements, physical measurements, or fast, randomized approximations to exact distances. A naive approach to NNSU could employ any standard NNS algorithm and repeatedly query and average results from the stochastic oracle (to reduce noise) whenever it needs a pairwise distance. The problem is that a sufficient number of repeated queries is unknown in advance; e.g., a point maybe distant from all but one other point (crude distance estimates suffice) or it may be close to a large number of other points (accurate estimates are necessary). This paper shows how ideas from cover trees and multi-armed bandits can be leveraged to develop an NNSU algorithm that has optimal dependence on the dataset size and the (unknown)geometry of the dataset.
• Abstract（参考訳）: Nearest Neighbor Search (NNS) は知識表現、学習、推論の中心的なタスクである。 データ構造を構築し、正確なNNSを実行するための効率的なアルゴリズムに関する膨大な文献がある。 本論文ではNNSを不確実性(NNSU)下で研究する。 具体的には、nnsアルゴリズムが、正確な距離ではなく、任意の対の点間の距離のノイズ、偏りのない推定を提供する確率的距離オラクルにのみアクセスする設定を考える。 このモデルは、人間の類似性判定に基づくnn、物理的測定、正確な距離に対する高速ランダム近似など、実用上重要な多くの状況をモデル化している。 NNSUに対する単純なアプローチは、標準的なNNSアルゴリズムを使用して、対距離が必要なときに確率的オラクル(ノイズを減らすために)から繰り返しクエリし、平均的な結果を得ることができる。 問題は、十分な数の繰り返しクエリが事前に分かっていないことであり、例えば、ある点が他の1つの点以外の点(距離推定の精度)から遠ざかる場合や、他の点に近い場合(正確な推定が必要となる場合)である。 本論文では,データセットサイズとデータセットの(未知の)ジオメトリに最適に依存するNNSUアルゴリズムの開発に,カバーツリーとマルチアームバンディットのアイデアをどのように活用できるかを示す。

関連論文リスト

• Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search [14.77572360618428]
  高次元近似$K$近辺探索(AKNN)は、様々なアプリケーションの基本課題である。 我々はemphDADEと呼ばれるアンダーラインデータアンダーラインAwareアンダーラインEstimationアプローチを提案する。
  論文  参考訳（メタデータ） (2024-11-26T08:51:46Z)
• Inferring Neural Signed Distance Functions by Overfitting on Single Noisy Point Clouds through Finetuning Data-Driven based Priors [53.6277160912059]
  本稿では,データ駆動型およびオーバーフィット型手法のプロースを推進し,より一般化し,高速な推論を行い,より高精度なニューラルネットワークSDFを学習する手法を提案する。 そこで本研究では,距離管理やクリーンポイントクラウド,あるいは点正規化を伴わずに,データ駆動型プリエントを微調整できる新しい統計的推論アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-25T16:48:44Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• k-NNN: Nearest Neighbors of Neighbors for Anomaly Detection [20.204147875108976]
  異常検出は、標準から大きく逸脱した画像を特定することを目的としている。 埋め込み空間における特徴の様々な構造と重要性を考慮に入れた新しい演算子を提案する。 既存のアルゴリズムに最も近いコンポーネントをk-NNN演算子に置き換えるだけで、残りのアルゴリズムに手を加えずに、各アルゴリズムの処理結果を改善できることが示される。
  論文  参考訳（メタデータ） (2023-05-28T11:39:51Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Robust Multi-Object Tracking by Marginal Inference [92.48078680697311]
  ビデオにおける多目的追跡は、隣接するフレーム内のオブジェクト間の1対1の割り当てに関する根本的な問題を解決する必要がある。 本稿では,各オブジェクトの限界確率をリアルタイムに計算する効率的な手法を提案する。 MOT17とMOT20ベンチマークで競合する結果を得る。
  論文  参考訳（メタデータ） (2022-08-07T14:04:45Z)
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search [8.25574589820305]
  近似近傍近傍近傍(DEANN)からの密度推定アルゴリズムを提案する。 我々は、非バイアス密度推定(KDE)を計算するために、ANNアルゴリズムをブラックボックスサブルーチンとして適用する。 我々の実装は、検討したすべての高次元データセットにおいて、技術実装の状況よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-06T17:11:28Z)
• Adaptive Nearest Neighbor Machine Translation [60.97183408140499]
  kNN-MTは、事前訓練されたニューラルネットワーク翻訳とトークンレベルのk-nearest-neighbor検索を組み合わせる。 従来のkNNアルゴリズムは、ターゲットトークンごとに同じ数の近傍を検索する。 ターゲットトークン毎のk個数を動的に決定する適応的kNN-MTを提案する。
  論文  参考訳（メタデータ） (2021-05-27T09:27:42Z)
• 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)
• Query Complexity of k-NN based Mode Estimation [4.821253146561989]
  与えられた n 個の点のデータセットに対して、その点を最小の k 番目の近傍距離で同定する問題について検討する。 本研究では,信頼区間のアイデアに基づく逐次学習アルゴリズムを設計し,どのクエリをオラクルに送信するかを適応的に決定し,高い確率で問題を正しく解けるようにした。
  論文  参考訳（メタデータ） (2020-10-26T11:32:08Z)
• Non-Local Spatial Propagation Network for Depth Completion [82.60915972250706]
  本研究では,深度完了のための堅牢で効率的な非局所的空間伝搬ネットワークを提案する。 提案するネットワークは,RGBとスパース深度画像を入力とし,各画素の非局所的近傍とその親和性を推定する。 提案アルゴリズムは,混合深度問題に対する深度補完精度とロバスト性の観点から,従来のアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-07-20T12:26:51Z)

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

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