論文の概要: Dynamic Maintenance of Kernel Density Estimation Data Structure: From
Practice to Theory
- arxiv url: http://arxiv.org/abs/2208.03915v1
- Date: Mon, 8 Aug 2022 04:40:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-09 12:40:57.902109
- Title: Dynamic Maintenance of Kernel Density Estimation Data Structure: From
Practice to Theory
- Title(参考訳): カーネル密度推定データ構造の動的保守:実践から理論へ
- Authors: Jiehao Liang, Zhao Song, Zhaozhuo Xu, Danyang Zhuo
- Abstract要約: カーネル密度推定(KDE)は機械学習において難しい課題である。
近年,効率的なKDEにデータ構造を用いる傾向が高まっている。
そこで本研究では,KDEデータ構造を動的に維持し,逆クエリに対する堅牢性に着目した。
- 参考スコア(独自算出の注目度): 19.454469229356697
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Kernel density estimation (KDE) stands out as a challenging task in machine
learning. The problem is defined in the following way: given a kernel function
$f(x,y)$ and a set of points $\{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$,
we would like to compute $\frac{1}{n}\sum_{i=1}^{n} f(x_i,y)$ for any query
point $y \in \mathbb{R}^d$. Recently, there has been a growing trend of using
data structures for efficient KDE. However, the proposed KDE data structures
focus on static settings. The robustness of KDE data structures over dynamic
changing data distributions is not addressed. In this work, we focus on the
dynamic maintenance of KDE data structures with robustness to adversarial
queries. Especially, we provide a theoretical framework of KDE data structures.
In our framework, the KDE data structures only require subquadratic spaces.
Moreover, our data structure supports the dynamic update of the dataset in
sublinear time. Furthermore, we can perform adaptive queries with the potential
adversary in sublinear time.
- Abstract(参考訳): カーネル密度推定(kde)は、機械学習において難しいタスクである。
カーネル関数 $f(x,y)$ と点の集合 $\{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$ が与えられたとき、任意のクエリポイント $y \in \mathbb{R}^d$ に対して $\frac{1}{n}\sum_{i=1}^{n} f(x_i,y)$ を計算したい。
近年,効率的なKDEにデータ構造を用いる傾向が高まっている。
しかし,提案するkdeデータ構造は静的設定に焦点を当てている。
動的に変化するデータ分布に対するKDEデータ構造の堅牢性には対処できない。
本研究では,KDEデータ構造を動的に維持し,逆クエリに対して頑健性を示す。
特に,KDEデータ構造の理論的枠組みについて述べる。
我々のフレームワークでは、KDEデータ構造は4次空間のみを必要とする。
さらに,データ構造は,データセットの動的更新をサブリニア時間でサポートする。
さらに,準線形時間で潜在的な敵と適応的なクエリを実行できる。
関連論文リスト
- Deep Equilibrium Based Neural Operators for Steady-State PDEs [100.88355782126098]
定常PDEに対する重み付けニューラルネットワークアーキテクチャの利点について検討する。
定常PDEの解を直接解くFNOアーキテクチャの深い平衡変種であるFNO-DEQを提案する。
論文 参考訳(メタデータ) (2023-11-30T22:34:57Z) - Fast Private Kernel Density Estimation via Locality Sensitive
Quantization [10.227538355037554]
差分プライベートカーネル密度推定(DP-KDE)の効率的なメカニズムについて検討する。
カーネルを$d$の時間線形でプライベートに近似する方法を示し、高次元データに対して実現可能である。
論文 参考訳(メタデータ) (2023-07-04T18:48:04Z) - KDEformer: Accelerating Transformers via Kernel Density Estimation [30.860357184928407]
本稿では,Dot-product attention mechanismの正確な計算方法を提案する。
提案手法は, 精度, メモリ, 実行時間において, 他の注目度よりも優れていることを示す。
T2T-ViTを用いた画像分類では,精度低下が0.5%以下であるのに対して,18時間以上のスピードアップを示す。
論文 参考訳(メタデータ) (2023-02-05T18:23:49Z) - Differentiable and Transportable Structure Learning [73.84540901950616]
本稿では,新しいアーキテクチャと損失関数により,発見された構造物の輸送性を回復するD-Structを紹介する。
D-Structは依然として微分可能であるため、既存の微分可能アーキテクチャでは容易に適用できる。
論文 参考訳(メタデータ) (2022-06-13T17:50:53Z) - ISDE : Independence Structure Density Estimation [0.0]
多次元密度推定は次元性の呪いに苦しむ。
本稿では,ISDE (Independence Structure Density Estimation) を提案する。
実世界のデータセット上で定量的かつ質的にどのように機能するかを示す。
論文 参考訳(メタデータ) (2022-03-18T08:01:04Z) - Generative Adversarial Learning via Kernel Density Discrimination [32.91091065436645]
本稿では,KDD GAN(Kernel Density Discrimination GAN)について紹介する。
我々は,カーネル密度推定を特徴空間内で直接定義し,カーネル特徴写像の可逆性の必要性を排除した。
その結果,FIDの基準値に比べてFIDが10%から40%に向上することが示唆された。
論文 参考訳(メタデータ) (2021-07-13T15:52:10Z) - DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest
Neighbor Search [8.25574589820305]
近似近傍近傍近傍(DEANN)からの密度推定アルゴリズムを提案する。
我々は、非バイアス密度推定(KDE)を計算するために、ANNアルゴリズムをブラックボックスサブルーチンとして適用する。
我々の実装は、検討したすべての高次元データセットにおいて、技術実装の状況よりも優れていることを示す。
論文 参考訳(メタデータ) (2021-07-06T17:11:28Z) - iDARTS: Differentiable Architecture Search with Stochastic Implicit
Gradients [75.41173109807735]
微分可能なArchiTecture Search(DARTS)は先日,ニューラルアーキテクチャサーチ(NAS)の主流になった。
暗黙の関数定理に基づいてDARTSの過次計算に取り組む。
提案手法であるiDARTSのアーキテクチャ最適化は,定常点に収束することが期待される。
論文 参考訳(メタデータ) (2021-06-21T00:44:11Z) - Deep Parametric Continuous Convolutional Neural Networks [92.87547731907176]
Parametric Continuous Convolutionは、非グリッド構造化データ上で動作する、新たな学習可能な演算子である。
室内および屋外シーンの点雲セグメンテーションにおける最先端技術よりも顕著な改善が見られた。
論文 参考訳(メタデータ) (2021-01-17T18:28:23Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
カーネル重み付けの観点からノード集約を再解釈する。
本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。
特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
論文 参考訳(メタデータ) (2020-05-16T04:44:29Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳(メタデータ) (2020-02-21T00:43:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。