# 最近傍法 ## 定義 最近傍法(nearest-neighbor methods)は、目的関数を明示的に学習せず、訓練データ(またはその要約であるプロトタイプ)そのものを予測時に参照するメモリベース(memory-based)な分類・回帰手法群である。k最近傍分類は、クエリ点$x_0$に標準化Euclid距離で最も近い$k$個の訓練点の多数決でクラスを決める(式13.1)。プロトタイプ法(K-means・学習ベクトル量子化(LVQ)・ガウス混合)は、訓練データそのものではなく少数の代表点でクラスを表現する点で最近傍法と異なるが、1最近傍法では各訓練点自体がプロトタイプになるため両者は連続的につながる。[[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]]は、Cover and Hart (1967) による古典的な漸近誤差率(1最近傍法の誤差率は漸近的にベイズ誤差率の高々2倍)、既知の変換に対する不変計量(tangent distance)、そして高次元で近傍が「伸びる」問題への対処である判別適応最近傍法(DANN)を中心に論じる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.2-§13.4) ## 横断的知見 - **k最近傍法は回帰(第2章)と分類(第13章)とで、同じ「近傍で平均する」操作が質的に異なる誤差の振る舞いを生む**: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.9は、k最近傍回帰のバイアス-バリアンス分解(EPE$_k(x_0)=\sigma^2+\text{Bias}^2+\text{Var}$)を導き、$k$を増やすとバイアスが増え分散が減るという加法的なトレードオフを示す(詳細は[[バイアス-バリアンストレードオフ]])。一方[[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.3は、Cover and Hart (1967) の結果として1最近傍**分類**の漸近誤差率が高々ベイズ誤差率の2倍にとどまることを示す。これは0-1損失のもとでバイアスと分散が加法的でなく乗法的に相互作用する([[バイアス-バリアンストレードオフ]]の横断的知見、第7章 §7.3.1由来)という一般論の具体例であり、$k=1$という最もバイアスが小さくばらつきが大きい設定でも分類誤差が有界にとどまるのは、判定境界の正しい側にいれば大きな二乗バイアスが誤差に直結しない分類特有の性質による。回帰では同じ$k=1$がバイアス最小・分散最大の望ましくない極端な設定として扱われるのと対照的である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.9, [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.3) - **距離計量を適応的に変形するというアイデアは、第6章の構造化カーネルと第13章のDANNとで「いつ・どの範囲で」適応するかという粒度が異なる**: [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] §6.3-6.4が示す構造化カーネル(計量行列$A$による座標ごとの重み付け)は、データ全体に対して**大域的に固定**された1つの計量を学習する(次元の呪いへの回避策の一つ、[[次元の呪い]]参照)。これに対し[[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.4のDANNは、クエリ点ごとに局所的なクラス内・クラス間共分散行列から計量$\Sigma$(式13.8-13.9)を**その都度再計算**する局所適応である。両者はともに「次元の呪いの本体は名目上の次元数ではなく、有効自由度・局所的な情報の構造である」という[[次元の呪い]]の横断的知見を裏づける具体例だが、構造化カーネルが1つのグローバルな構造的仮定を課すのに対し、DANNは仮定なしにクエリ点ごとの局所構造をデータから直接推定する点で対極にある。この違いは、DANNの大域版(§13.4.2、$\bar B$の固有ベクトルによる大域的部分空間削減)が構造化カーネルに近い折衷案として提示されていることからも確認できる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]] §6.3-6.4, [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.4) - **入門書(ch.2)は1最近傍法を「丸暗記(memorization)」という否定的な出発点として位置づけ、ESL第13章がCover and Hartの漸近誤差率で理論的に正当化する対象と、同じアルゴリズムを正反対の評価で扱う**: 本ページはESL第13章から、1最近傍分類の誤差率が漸近的にベイズ誤差率の高々2倍にとどまるという理論的保証(Cover and Hart, 1967)を引き、1-NNを正当な統計的手法として扱う。これに対し[[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3は、新しい入力に最も近い過去のデータをそのまま予測値として使うアプローチを「丸暗記(memorization)」と呼び、「この丸暗記で解ける問題の場合は、わざわざ機械学習を使う必要はない」と述べたうえで、画像のような高次元データでは取りうる入力の種類数が天文学的(32×32の2値画像で約$2^{1024}$通り)であるため丸暗記は不可能であり、真の汎化能力を持つ機械学習が必要になると論じる(図2.4・図2.5)。同一のアルゴリズム(最も近い訓練事例を参照する)が、ESL第13章では「理論的に妥当な分類手法」として、ch.2では「機械学習が不要になってしまう退化ケース、かつ高次元では実行不可能な反面教師」として扱われるという評価の違いは、両ソースが暗黙に想定する問題規模の違い(ESLは低〜中次元の統計的分類問題、ch.2は画像のような高次元問題)に起因する。ch.2の高次元での不可能性の指摘は、本ページの[[次元の呪い]]における「サンプリング密度が$N^{1/p}$に比例して低下する」という統計的な破綻とは異なる、**組合せ論的な破綻**(取りうる入力パターン数が有限記憶を超える)を追加する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.3, [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3) ## 未解決の問い - 構造化カーネル(第6章、大域的に固定された計量行列$A$)とDANN(第13章、クエリ点ごとに再計算される局所計量)を同一データセットで直接比較した実証結果は本書に見当たらない。局所適応の柔軟性が、計算コスト増加に見合う精度向上を常にもたらすかは未検証。 - DANNの大域的次元削減版(§13.4.2、$\bar B$の固有ベクトル)は、sliced inverse regression(Duan and Li, 1991)との関係が本文で示唆されるのみで詳細な比較はない。[[主成分分析]]による次元削減との使い分けの基準は何か。 - editing・condensing(multi-edit法・condensing法、§13.5)による訓練集合削減は、著者ら自身が「体系的な性能比較を文献に見出していない」と述べる未検証領域である。削減後の集合サイズと最終的な汎化誤差の関係はどの程度定量化されているか。 ## 関連 - source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]](k最近傍回帰のバイアス-バリアンス分解) / [[@2009__Springer__The Elements of Statistical Learning - Chapter 6 Kernel Smoothing Methods]](構造化カーネルとの対比) / [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]](丸暗記としての否定的な位置づけ) - concept: [[次元の呪い]] / [[バイアス-バリアンストレードオフ]] / [[局所回帰]] / [[クラスタリング]] / [[EMアルゴリズム]] / [[汎化能力]] ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 13. - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.3.