論文の概要: Empirical complexity of comparator-based nearest neighbor descent
- arxiv url: http://arxiv.org/abs/2202.00517v1
- Date: Sun, 30 Jan 2022 21:37:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-02 13:56:49.357304
- Title: Empirical complexity of comparator-based nearest neighbor descent
- Title（参考訳）: コンパレータに基づく近親系の経験的複雑性
- Authors: Jacob D. Baron and R. W. R. Darling
- Abstract要約: K$-nearest 隣り合うアルゴリズムの Java 並列ストリームの実装を示す。
Kullback-Leiblerの発散比較器による実験は、$K$-nearest近くの更新ラウンドの数が直径の2倍を超えないという予測を支持している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A Java parallel streams implementation of the $K$-nearest neighbor descent
algorithm is presented using a natural statistical termination criterion. Input
data consist of a set $S$ of $n$ objects of type V, and a Function<V,
Comparator<V>>, which enables any $x \in S$ to decide which of $y, z \in
S\setminus\{x\}$ is more similar to $x$. Experiments with the Kullback-Leibler
divergence Comparator support the prediction that the number of rounds of
$K$-nearest neighbor updates need not exceed twice the diameter of the
undirected version of a random regular out-degree $K$ digraph on $n$ vertices.
Overall complexity was $O(n K^2 \log_K(n))$ in the class of examples studied.
When objects are sampled uniformly from a $d$-dimensional simplex, accuracy of
the $K$-nearest neighbor approximation is high up to $d = 20$, but declines in
higher dimensions, as theory would predict.
- Abstract（参考訳）: k$-nearest近傍降下アルゴリズムのjava並列ストリーム実装は、自然統計終了基準を用いて提示される。
入力データは、タイプVの$n$オブジェクトのセット$S$と、任意の$x \in S$が$y、z \in S\setminus\{x\}$のどちらが$x$に近いかを判断できるFunction<V, Comparator<V>>で構成される。
Kullback-Leibler 分岐比較器による実験は、$K$-nearest 隣の更新ラウンドの数が$n$ vertices上のランダムな正則外度$K$ digraphの2倍の直径を超えないという予測を支持している。
全体の複雑性は、研究された例のクラスで$o(n k^2 \log_k(n))$であった。
オブジェクトが$d$-dimensional simplex から一様にサンプリングされると、$k$-nearest の隣の近似の精度は $d = 20$ となるが、理論が予測するより高次元では低下する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Robust testing of low-dimensional functions [8.927163098772589]
著者たちの最近の研究は、線型$k$-juntasがテスト可能であることを示した。
耐雑音性試験への関心が高まった後, 本論文では, 耐雑音性(あるいは頑健性)バージョンを実証する。
クエリ複雑性が$kO(mathsfpoly(log k/epsilon))$,$k$-halfspacesの交叉のクラスに対して完全耐雑音試験器を得る。
論文 参考訳（メタデータ） (2020-04-24T10:23:12Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - Efficient Distance Approximation for Structured High-Dimensional
Distributions via Learning [31.552581550603005]
構成された高次元分布のいくつかのクラスに対する効率的な距離近似アルゴリズムを設計する。
我々の結果は、これらのよく研究された問題に対する最初の効率的な距離近似アルゴリズムである。
論文 参考訳（メタデータ） (2020-02-13T07:42:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。