論文の概要: For Kernel Range Spaces a Constant Number of Queries Are Sufficient
- arxiv url: http://arxiv.org/abs/2306.16516v1
- Date: Wed, 28 Jun 2023 19:19:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-30 15:57:24.142093
- Title: For Kernel Range Spaces a Constant Number of Queries Are Sufficient
- Title（参考訳）: カーネルレンジスペースの場合、定数のクエリは十分である
- Authors: Jeff M. Phillips and Hasan Pourmahmood-Aghababa
- Abstract要約: カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。
Anvarepsilon$-cover は点 $Q の部分集合 mathbbRd$ for any $p in mathbbRd$ that $frac1n |R_p - R_q|leq varepsilon$ for some $q in Q$ の部分集合である。
- 参考スコア（独自算出の注目度）: 13.200502573462712
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We introduce the notion of an $\varepsilon$-cover for a kernel range space. A
kernel range space concerns a set of points $X \subset \mathbb{R}^d$ and the
space of all queries by a fixed kernel (e.g., a Gaussian kernel $K(p,\cdot) =
\exp(-\|p-\cdot\|^2)$). For a point set $X$ of size $n$, a query returns a
vector of values $R_p \in \mathbb{R}^n$, where the $i$th coordinate $(R_p)_i =
K(p,x_i)$ for $x_i \in X$. An $\varepsilon$-cover is a subset of points $Q
\subset \mathbb{R}^d$ so for any $p \in \mathbb{R}^d$ that $\frac{1}{n} \|R_p -
R_q\|_1\leq \varepsilon$ for some $q \in Q$. This is a smooth analog of
Haussler's notion of $\varepsilon$-covers for combinatorial range spaces (e.g.,
defined by subsets of points within a ball query) where the resulting vectors
$R_p$ are in $\{0,1\}^n$ instead of $[0,1]^n$. The kernel versions of these
range spaces show up in data analysis tasks where the coordinates may be
uncertain or imprecise, and hence one wishes to add some flexibility in the
notion of inside and outside of a query range.
Our main result is that, unlike combinatorial range spaces, the size of
kernel $\varepsilon$-covers is independent of the input size $n$ and dimension
$d$. We obtain a bound of $(1/\varepsilon)^{\tilde O(1/\varepsilon^2)}$, where
$\tilde{O}(f(1/\varepsilon))$ hides log factors in $(1/\varepsilon)$ that can
depend on the kernel. This implies that by relaxing the notion of boundaries in
range queries, eventually the curse of dimensionality disappears, and may help
explain the success of machine learning in very high-dimensions. We also
complement this result with a lower bound of almost
$(1/\varepsilon)^{\Omega(1/\varepsilon)}$, showing the exponential dependence
on $1/\varepsilon$ is necessary.
- Abstract（参考訳）: 我々は、カーネル範囲空間に対する$\varepsilon$-coverの概念を導入する。
カーネル範囲空間は、点の集合 $X \subset \mathbb{R}^d$ と、固定されたカーネルによる全てのクエリの空間(例えば、ガウス核 $K(p,\cdot) = \exp(-\|p-\cdot\|^2)$)に関する。
点集合 $X$ of size $n$ に対して、クエリは値のベクトル $R_p \in \mathbb{R}^n$ を返し、$i$th 座標 $(R_p)_i = K(p,x_i)$ for $x_i \in X$ が返される。
Q \subset \mathbb{R}^d$ は任意の$p \in \mathbb{R}^d$ に対して、$\frac{1}{n} \|R_pR_q\|_1\leq \varepsilon$ の集合である。
これは、組合せ範囲空間に対するハウスラーの$\varepsilon$-covers(例えば、ボールクエリ内の点の部分集合で定義される)の概念の滑らかな類似であり、結果として得られるベクトル$R_p$は$[0,1]^n$の代わりに$\{0,1\}^n$である。
これらの範囲空間のカーネルバージョンは、座標が不確かで不正確であるかもしれないデータ解析タスクに現れ、従ってクエリ範囲内外の概念に柔軟性を加えることを望んでいる。
私たちの主な結果は、組合せ範囲空間とは異なり、カーネル $\varepsilon$-covers のサイズは入力サイズ $n$ と次元 $d$ に依存しないということです。
ここでは、$(1/\varepsilon)^{\tilde O(1/\varepsilon^2)}$, $\tilde{O}(f(1/\varepsilon))$は、カーネルに依存することができる$(1/\varepsilon)$でログ係数を隠す。
これは、範囲クエリにおける境界の概念を緩和することで、最終的には次元の呪いが消え、非常に高次元の機械学習の成功を説明するのに役立つことを意味する。
また、この結果を約$(1/\varepsilon)^{\Omega(1/\varepsilon)$で補い、$/\varepsilon$への指数的な依存が必要とされることを示す。
関連論文リスト
- Sparsifying Suprema of Gaussian Processes [6.638504164134713]
我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。
また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
論文 参考訳（メタデータ） (2024-11-22T01:43:58Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳（メタデータ） (2024-06-04T15:50:42Z) - Metricizing the Euclidean Space towards Desired Distance Relations in
Point Clouds [1.2366208723499545]
我々は教師なし学習アルゴリズム、具体的には$k$-Means and density-based clustering algorithm(DBSCAN)を攻撃している。
クラスタリングアルゴリズムの結果は、特定の距離関数を使用するための標準化された固定された処方令がなければ、一般的には信頼できない可能性がある。
論文 参考訳（メタデータ） (2022-11-07T16:37:29Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳（メタデータ） (2021-06-25T19:14:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。