論文の概要: Convergence of Graph Laplacian with kNN Self-tuned Kernels
- arxiv url: http://arxiv.org/abs/2011.01479v2
- Date: Wed, 10 Feb 2021 02:17:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 04:26:43.437431
- Title: Convergence of Graph Laplacian with kNN Self-tuned Kernels
- Title（参考訳）: kNN自己調整カーネルを用いたグラフラプラシアンの収束
- Authors: Xiuyuan Cheng, Hau-Tieng Wu
- Abstract要約: 自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。
本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
- 参考スコア（独自算出の注目度）: 14.645468999921961
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Kernelized Gram matrix $W$ constructed from data points $\{x_i\}_{i=1}^N$ as
$W_{ij}= k_0( \frac{ \| x_i - x_j \|^2} {\sigma^2} )$ is widely used in
graph-based geometric data analysis and unsupervised learning. An important
question is how to choose the kernel bandwidth $\sigma$, and a common practice
called self-tuned kernel adaptively sets a $\sigma_i$ at each point $x_i$ by
the $k$-nearest neighbor (kNN) distance. When $x_i$'s are sampled from a
$d$-dimensional manifold embedded in a possibly high-dimensional space, unlike
with fixed-bandwidth kernels, theoretical results of graph Laplacian
convergence with self-tuned kernels have been incomplete. This paper proves the
convergence of graph Laplacian operator $L_N$ to manifold (weighted-)Laplacian
for a new family of kNN self-tuned kernels $W^{(\alpha)}_{ij} = k_0( \frac{ \|
x_i - x_j \|^2}{ \epsilon \hat{\rho}(x_i)
\hat{\rho}(x_j)})/\hat{\rho}(x_i)^\alpha \hat{\rho}(x_j)^\alpha$, where
$\hat{\rho}$ is the estimated bandwidth function {by kNN}, and the limiting
operator is also parametrized by $\alpha$. When $\alpha = 1$, the limiting
operator is the weighted manifold Laplacian $\Delta_p$. Specifically, we prove
the point-wise convergence of $L_N f $ and convergence of the graph Dirichlet
form with rates. Our analysis is based on first establishing a $C^0$
consistency for $\hat{\rho}$ which bounds the relative estimation error
$|\hat{\rho} - \bar{\rho}|/\bar{\rho}$ uniformly with high probability, where
$\bar{\rho} = p^{-1/d}$, and $p$ is the data density function. Our theoretical
results reveal the advantage of self-tuned kernel over fixed-bandwidth kernel
via smaller variance error in low-density regions. In the algorithm, no prior
knowledge of $d$ or data density is needed. The theoretical results are
supported by numerical experiments on simulated data and hand-written digit
image data.
- Abstract（参考訳）: データポイント$\{x_i\}_{i=1}^N$ as $W_{ij}= k_0( \frac{ \| x_i - x_j \|^2} {\sigma^2} )$はグラフベースの幾何学的データ解析や教師なし学習で広く使われている。
重要な疑問は、どのようにカーネル帯域幅を$\sigma$を選択するかであり、セルフチューニングカーネルと呼ばれる一般的なプラクティスは、k$-nearest neighbor (kNN) 距離によって各ポイントに$\sigma_i$を適応的に設定する。
固定帯域幅のカーネルとは異なり、$x_i$'sが高次元空間に埋め込まれた$d$次元多様体からサンプリングされると、自己チューニングされたカーネルを持つグラフラプラシア収束の理論結果は不完全である。
グラフラプラシアン作用素 $L_N$ を多様体 (重み付き) Laplacian for a new family of kNN self-tuned kernels $W^{(\alpha)}_{ij} = k_0( \frac{ \| x_i - x_j \|^2}{ \epsilon \hat{\rho}(x_i) \hat{\rho}(x_j)})/\hat{\rho}(x_i)^\alpha \hat{\rho}(x_j)^\alpha$, ここで$\hat{\rho}$は推定帯域幅関数 {by kNN} であり、極限作用素も$\alpha$でパラメタ化される。
$\alpha = 1$ のとき、極限作用素は加重多様体 Laplacian $\Delta_p$ である。
具体的には、$L_N f $ の点収束とグラフディリクレ形式の点収束をレートで証明する。
我々の分析は、まず、相対的な推定誤差である$|\hat{\rho} - \bar{\rho}|/\bar{\rho}$に対して$C^0$の一貫性を確立することに基づいており、$\bar{\rho} = p^{-1/d}$であり、$p$はデータ密度関数である。
低密度領域での分散誤差を小さくすることで、固定帯域カーネルに対する自己調整カーネルの利点を明らかにする。
アルゴリズムでは、$d$やデータ密度に関する事前の知識は必要ない。
理論的結果はシミュレーションデータと手書き桁画像データに関する数値実験によって支持される。
関連論文リスト
- Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。
制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文 参考訳（メタデータ） (2024-10-30T17:01:00Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。
点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
論文 参考訳（メタデータ） (2021-05-11T02:29:33Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳（メタデータ） (2021-01-11T17:23:24Z) - Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。
我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文 参考訳（メタデータ） (2020-07-15T22:58:50Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。