論文の概要: On Convergence of Nearest Neighbor Classifiers over Feature Transformations

• arxiv url: http://arxiv.org/abs/2010.07765v1
• Date: Thu, 15 Oct 2020 14:05:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 03:16:21.969799
• Title: On Convergence of Nearest Neighbor Classifiers over Feature Transformations
• Title（参考訳）: 特徴変換による近接近傍分類器の収束について
• Authors: Luka Rimanic, Cedric Renggli, Bo Li, Ce Zhang
• Abstract要約: k-Nearest Neighbors (kNN) は、基本的な非パラメトリック機械学習アルゴリズムである。 kNNの理解を目的とした理論的な結果は、生の特徴空間に対して導出される。 変換された特徴に対するkNN分類器の収束率に関する新しい解析法を提案する。
• 参考スコア（独自算出の注目度）: 23.949684245916732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The k-Nearest Neighbors (kNN) classifier is a fundamental non-parametric machine learning algorithm. However, it is well known that it suffers from the curse of dimensionality, which is why in practice one often applies a kNN classifier on top of a (pre-trained) feature transformation. From a theoretical perspective, most, if not all theoretical results aimed at understanding the kNN classifier are derived for the raw feature space. This leads to an emerging gap between our theoretical understanding of kNN and its practical applications. In this paper, we take a first step towards bridging this gap. We provide a novel analysis on the convergence rates of a kNN classifier over transformed features. This analysis requires in-depth understanding of the properties that connect both the transformed space and the raw feature space. More precisely, we build our convergence bound upon two key properties of the transformed space: (1) safety -- how well can one recover the raw posterior from the transformed space, and (2) smoothness -- how complex this recovery function is. Based on our result, we are able to explain why some (pre-trained) feature transformations are better suited for a kNN classifier than other. We empirically validate that both properties have an impact on the kNN convergence on 30 feature transformations with 6 benchmark datasets spanning from the vision to the text domain.
• Abstract（参考訳）: k-Nearest Neighbors(kNN)分類器は、基本的な非パラメトリック機械学習アルゴリズムである。 しかし、次元の呪いに悩まされることはよく知られているため、実際には(事前訓練された)特徴変換の上にkNN分類器を適用することが多い。 理論的には、kn分類器の理解を目的とした理論的な結果が生の特徴空間に対して導かれるわけではない。 これにより、kNNの理論的理解と実践的応用の間には、新たなギャップが生まれる。 本稿では,このギャップを埋めるための第一歩を踏み出す。 変換された特徴に対するkNN分類器の収束率に関する新しい解析法を提案する。 この解析は変換空間と原特徴空間の両方を接続する性質の深い理解を必要とする。 より正確には、変換空間の2つの重要な特性に束縛された収束性を構築する: (1) 安全性 -- 変換空間からどこまで後方を回復できるか、(2) 滑らかさ -- この回復関数がどれほど複雑か。 この結果に基づいて、kNN分類器に適した(事前訓練された)機能変換が、他のものよりも適している理由を説明することができる。 我々は,視覚からテキスト領域にまたがる6つのベンチマークデータセットを用いた30の機能変換において,両方の特性がkn収束に与える影響を実証的に検証した。

関連論文リスト

• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  我々は,2層変換器が$n$-gramのマルコフ連鎖データ上でICLを実行するためにどのように訓練されているかを検討する。 クロスエントロピー ICL 損失に対する勾配流が極限モデルに収束することを証明する。
  論文  参考訳（メタデータ） (2024-09-09T18:10:26Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Classification with Deep Neural Networks and Logistic Loss [25.56187933090708]
  このロジスティック損失で訓練されたディープニューラルネットワーク(DNN)は、バイナリ分類タスクにおいて目覚ましい進歩を遂げた。 本稿では,新規でエレガントなオラクル型不等式を確立し,対象関数の有界性制限に対処する。 完全に連結されたReLU DNN分類器に対して,ロジスティック損失を訓練したシャープ収束率を導出する。
  論文  参考訳（メタデータ） (2023-07-31T15:58:46Z)
• Restore Translation Using Equivariant Neural Networks [7.78895108256899]
  本稿では,畳み込みニューラルネットワークに変換された(あるいは回転した)入力を復元するための事前分類器復元器を提案する。 復元子は、テンソル空間上の変換同変であるアフィン作用素に十分かつ必要な条件を与える理論的な結果に基づいている。
  論文  参考訳（メタデータ） (2023-06-29T13:34:35Z)
• Understanding Imbalanced Semantic Segmentation Through Neural Collapse [81.89121711426951]
  セマンティックセグメンテーションは自然に文脈的相関とクラス間の不均衡分布をもたらすことを示す。 機能中心にレギュレータを導入し、ネットワークが魅力ある構造に近い機能を学ぶことを奨励する。 我々の手法は、ScanNet200テストリーダーボードで1位にランクインし、新しい記録を樹立する。
  論文  参考訳（メタデータ） (2023-01-03T13:51:51Z)
• Equivariance with Learned Canonicalization Functions [77.32483958400282]
  正規化を行うために小さなニューラルネットワークを学習することは、事前定義を使用することよりも優れていることを示す。 実験の結果,正準化関数の学習は多くのタスクで同変関数を学習する既存の手法と競合することがわかった。
  論文  参考訳（メタデータ） (2022-11-11T21:58:15Z)
• Do We Really Need a Learnable Classifier at the End of Deep Neural Network? [118.18554882199676]
  本研究では、ニューラルネットワークを学習して分類器をランダムにETFとして分類し、訓練中に固定する可能性について検討する。 実験結果から,バランスの取れたデータセットの画像分類において,同様の性能が得られることがわかった。
  論文  参考訳（メタデータ） (2022-03-17T04:34:28Z)
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning [18.464203215845373]
  構造化3変量テンソルをその構成的ポリアディック(CP)因子に分解する問題を考察する。 我々は、構造化テンソル因子分解のための証明可能なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-30T00:31:06Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。