論文の概要: DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest
Neighbor Search
- arxiv url: http://arxiv.org/abs/2107.02736v1
- Date: Tue, 6 Jul 2021 17:11:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-07 13:34:23.274291
- Title: DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest
Neighbor Search
- Title（参考訳）: DEANN:近似近傍探索によるカーネル密度推定の高速化
- Authors: Matti Karppa and Martin Aum\"uller and Rasmus Pagh
- Abstract要約: 近似近傍近傍近傍(DEANN)からの密度推定アルゴリズムを提案する。
我々は、非バイアス密度推定(KDE)を計算するために、ANNアルゴリズムをブラックボックスサブルーチンとして適用する。
我々の実装は、検討したすべての高次元データセットにおいて、技術実装の状況よりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 8.25574589820305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Kernel Density Estimation (KDE) is a nonparametric method for estimating the
shape of a density function, given a set of samples from the distribution.
Recently, locality-sensitive hashing, originally proposed as a tool for nearest
neighbor search, has been shown to enable fast KDE data structures. However,
these approaches do not take advantage of the many other advances that have
been made in algorithms for nearest neighbor algorithms. We present an
algorithm called Density Estimation from Approximate Nearest Neighbors (DEANN)
where we apply Approximate Nearest Neighbor (ANN) algorithms as a black box
subroutine to compute an unbiased KDE. The idea is to find points that have a
large contribution to the KDE using ANN, compute their contribution exactly,
and approximate the remainder with Random Sampling (RS). We present a
theoretical argument that supports the idea that an ANN subroutine can speed up
the evaluation. Furthermore, we provide a C++ implementation with a Python
interface that can make use of an arbitrary ANN implementation as a subroutine
for KDE evaluation. We show empirically that our implementation outperforms
state of the art implementations in all high dimensional datasets we
considered, and matches the performance of RS in cases where the ANN yield no
gains in performance.
- Abstract（参考訳）: 核密度推定 (kde) は、分布からサンプルの集合を与えられた密度関数の形状を推定するための非パラメトリックな方法である。
近年,近傍探索のためのツールとして提案された局所性感応ハッシュは,高速なKDEデータ構造を実現することが示されている。
しかし、これらの手法は、近隣のアルゴリズムのアルゴリズムでなされた他の多くの進歩を生かしていない。
非バイアスkdeを計算するために、近似近接近傍(ann)アルゴリズムをブラックボックスサブルーチンとして適用し、近似近接近傍(deann)から密度推定を行う。
この考え方は、ANNを用いてKDEに多大な貢献をした点を見つけ、その貢献を正確に計算し、残りの点をランダムサンプリング(RS)で近似する。
我々は、ANNサブルーチンが評価を高速化できるという考えを支持する理論的議論を示す。
さらに,任意のANN実装をKDE評価のサブルーチンとして利用できるPythonインターフェースを備えたC++実装を提供する。
実験により,我々の実装は,検討した高次元データセットすべてにおいて,技術実装の状況よりも優れており,ANNが性能を損なう場合のRSの性能に匹敵することを示した。
関連論文リスト
- 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) - PECANN: Parallel Efficient Clustering with Graph-Based Approximate
Nearest Neighbor Search [8.15681999722805]
本稿では, 点集合の密度に基づくクラスタリングについて検討する。
密度ピークの異なる変種を単一のフレームワークPECANNに統合する。
PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
論文 参考訳（メタデータ） (2023-12-06T22:43:50Z) - Fast Approximation of Similarity Graphs with Kernel Density Estimation [12.321755440062732]
我々は,データポイントのセットである$X$から類似性グラフを構築するための新しいアルゴリズムをmathbbRd$に提示する。
提案アルゴリズムはカーネル密度推定問題に基づいており,任意のカーネル関数に適用可能である。
論文 参考訳（メタデータ） (2023-10-21T00:32:47Z) - Fast Private Kernel Density Estimation via Locality Sensitive
Quantization [10.227538355037554]
差分プライベートカーネル密度推定(DP-KDE)の効率的なメカニズムについて検討する。
カーネルを$d$の時間線形でプライベートに近似する方法を示し、高次元データに対して実現可能である。
論文 参考訳（メタデータ） (2023-07-04T18:48:04Z) - A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near
Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。
グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。
低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文 参考訳（メタデータ） (2023-03-10T21:18:34Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳（メタデータ） (2022-10-21T15:56:13Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Random Features for the Neural Tangent Kernel [57.132634274795066]
完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。
得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
論文 参考訳（メタデータ） (2021-04-03T09:08:12Z) - 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) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。