論文の概要: A PAC-Bayesian Analysis of Distance-Based Classifiers: Why
Nearest-Neighbour works!
- arxiv url: http://arxiv.org/abs/2109.13889v1
- Date: Tue, 28 Sep 2021 17:35:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-29 14:56:05.222009
- Title: A PAC-Bayesian Analysis of Distance-Based Classifiers: Why
Nearest-Neighbour works!
- Title(参考訳): PAC-Bayesian Analysis of Distance-based Classifications: Why Nearest-Neighbour Works!
- Authors: Thore Graepel and Ralf Herbrich
- Abstract要約: K-nearest-neighbour分類器(K-NN)の一般化誤差に対するPAC-Bayesian境界
我々は、カーネル展開における係数に関する事前測度と、カーネル空間における重みベクトルに関する誘導測度との関係を確立する。
- 参考スコア(独自算出の注目度): 12.317405551932195
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Abstract We present PAC-Bayesian bounds for the generalisation error of the
K-nearest-neighbour classifier (K-NN). This is achieved by casting the K-NN
classifier into a kernel space framework in the limit of vanishing kernel
bandwidth. We establish a relation between prior measures over the coefficients
in the kernel expansion and the induced measure on the weight vectors in kernel
space. Defining a sparse prior over the coefficients allows the application of
a PAC-Bayesian folk theorem that leads to a generalisation bound that is a
function of the number of redundant training examples: those that can be left
out without changing the solution. The presented bound requires to quantify a
prior belief in the sparseness of the solution and is evaluated after learning
when the actual redundancy level is known. Even for small sample size (m ~ 100)
the bound gives non-trivial results when both the expected sparseness and the
actual redundancy are high.
- Abstract(参考訳): 要約 K-nearest-neighbour classifier (K-NN) の一般化誤差に対するPAC-Bayesian boundsを提案する。
これはK-NN分類器をカーネル帯域幅の消滅の限界においてカーネル空間フレームワークにキャストすることで達成される。
核展開における係数上の事前測度と、核空間における重みベクトル上の誘導測度との関係を定式化する。
係数の上のスパース事前を定義することで、余剰な訓練例の数の関数である一般化境界(英語版)(generalization bound)に繋がるpac-ベイズフォーク定理(pac-bayesian folk theorem)の応用が可能になる。
提示された境界は、ソリューションのスパース性に対する事前の信念を定量化することを必要とし、実際の冗長性レベルが分かっている場合の学習後に評価される。
小さいサンプルサイズ (m ~ 100) であっても、期待されるスパースネスと実際の冗長性の両方が高い場合、バウンドは非自明な結果を与える。
関連論文リスト
- Exploiting Structure for Optimal Multi-Agent Bayesian Decentralized
Estimation [4.320393382724066]
ベイジアン分権データ融合の鍵となる課題は、噂の伝播(double counting)現象である。
マルチエージェント分散核融合問題における確率的独立構造を利用して、より厳密な境界を求めることができることを示す。
次に、大規模目標追跡シミュレーションを用いて、新しいモノリシックCIアルゴリズムを試験し、より厳密な境界とより正確な推定値が得られることを示す。
論文 参考訳(メタデータ) (2023-07-20T05:16:33Z) - Understanding the Generalization Ability of Deep Learning Algorithms: A
Kernelized Renyi's Entropy Perspective [11.255943520955764]
本稿では,Renyiのエントロピーをカーネル化した新しい情報理論尺度を提案する。
我々は,Renyiエントロピーのカーネル化の下で,勾配/ランジュバン降下(SGD/SGLD)学習アルゴリズムの一般化誤差境界を確立する。
我々の情報理論的境界は勾配の統計に依存しており、現在のSOTA(State-of-the-art)結果よりも厳密であることを示す。
論文 参考訳(メタデータ) (2023-05-02T01:17:15Z) - Regret Bounds for Noise-Free Cascaded Kernelized Bandits [51.45291566743071]
RKHS関数クラスを用いたノイズフリーグレーボックス設定において,関数ネットワークの最適化を検討する。
本研究では,(1)チェーン:スカラー値関数のカスケード,(2)マルチアウトプットチェーン:ベクトル値関数のカスケード,(3)フィードフォワードネットワーク:完全に接続されたスカラー値関数のフィードフォワードネットワークの3種類の構造について検討する。
論文 参考訳(メタデータ) (2022-11-10T09:12:55Z) - A New Family of Generalization Bounds Using Samplewise Evaluated CMI [14.147617330278662]
本稿では,学習損失と人口損失を連接凸関数を用いて比較する情報理論の一般化境界系を提案する。
これまでに知られていた情報理論境界を拡張することで,この枠組みの汎用性を実証する。
いくつかのシナリオでは、この新しい境界は、以前の境界よりも深いニューラルネットワークの人口減少を厳しく評価する。
論文 参考訳(メタデータ) (2022-10-12T17:15:44Z) - Robust Estimation for Nonparametric Families via Generative Adversarial
Networks [92.64483100338724]
我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。
我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。
技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
論文 参考訳(メタデータ) (2022-02-02T20:11:33Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Oversampling Divide-and-conquer for Response-skewed Kernel Ridge
Regression [20.00435452480056]
本研究では,分割・分散手法の限界を克服するために,新しい応答適応分割戦略を開発する。
提案手法は, 従来のダックKRR推定値よりも小さい平均二乗誤差(AMSE)を有することを示す。
論文 参考訳(メタデータ) (2021-07-13T04:01:04Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z) - Robust subgaussian estimation with VC-dimension [0.0]
この研究は、MOM推定器の余剰リスクを束縛する新しい一般的な方法を提案する。
中心となる技術は、統計複雑性を測定するためにVC次元(ラデマッハの複雑さの代わりに)を用いることである。
論文 参考訳(メタデータ) (2020-04-24T13:21:09Z) - Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
モデルに基づく楽観的アルゴリズムであるKernel-UCBVIを導入する。
スパース報酬を伴う連続MDPにおける我々のアプローチを実証的に検証する。
論文 参考訳(メタデータ) (2020-04-12T12:23:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。