パターン認識・機械学習の分類・k近傍法¶
キーワード：パターン認識、k近傍法・近傍法、kd-tree、近似最近傍、距離計算、コサイン距離、ユークリッド距離、マンハッタン距離、Lp距離、マハラノビス距離、教師あり学習、教師なし学習、半教師あり学習
要点
- 機械学習は、ラベルの与えられ方（教師あり・なし・半教師あり・自己教師あり）と、目的（回帰・分類・構造発見）で整理する。
- k近傍法は学習をせず、予測のたびに近い \(K\) 個の訓練データの多数決（分類）か平均（回帰）をとる。\(K\) が小さいほど境界は複雑になる。
- 「近い」の定義は距離で決まる。距離の選び方（尺度・相関・向き）で結果が変わり、次元が高いと距離が意味を失う（次元の呪い）。
機械学習の分類¶
ラベルの与えられ方¶
| 区分 | ラベル | 学ぶもの | 代表例 |
|---|---|---|---|
| 教師あり学習 | すべてに付く | 入力から出力への写像 | 回帰、分類（線形回帰・SVM・決定木・ニューラルネット） |
| 教師なし学習 | なし | データの構造・分布 | クラスタリング、次元圧縮、密度推定、オートエンコーダ |
| 半教師あり学習 | 一部だけ付く | 少数のラベル＋多数のラベルなしデータ | 疑似ラベル、一貫性正則化（MixMatch・FixMatch） |
| 弱教師あり学習 | 粗い・不完全・不正確 | 弱いラベルから細かい予測 | 多重インスタンス学習、画像単位のラベルからの領域推定 |
| 自己教師あり学習 | データ自身から自動生成 | 事前学習のための表現 | マスク予測（BERT・MAE）、次トークン予測（GPT）、対照学習（SimCLR・MoCo・CLIP） |
| 強化学習 | 報酬だけ | 報酬を最大にする方策 | DQN、PPO、SAC（強化学習） |
- 教師あり学習の出力が連続値なら回帰、離散ラベルなら分類。
- 自己教師あり学習・生成モデルは 自己教師あり学習・生成モデル、クラスタリングと次元圧縮は クラスタリング・次元圧縮 で扱う。
- 対照学習は、似たサンプルを近く、似ないサンプルを遠くに置く表現を学ぶ自己教師あり学習の代表的な方法。
学び方・使い方による分類¶
| 名称 | 内容 |
|---|---|
| 転移学習・ファインチューニング | 大規模データで事前学習したモデルを、目的タスクに合わせて再学習する |
| マルチタスク学習 | 関連する複数のタスクを同時に学習し、表現を共有して汎化を高める（例：分類＋位置回帰の検出器） |
| メタ学習 | 「学び方」を学び、少数の例（Few-shot）で新しいタスクに適応する（MAML・Prototypical Networks） |
| 能動学習 | モデルが、ラベルを付ける価値が高いデータ（不確かなもの）を選んで問い合わせる |
| 模倣学習 | 専門家の行動例から方策を学ぶ（行動クローニング・DAgger・逆強化学習・GAIL） |
- 識別モデルは \(p(y\mid\mathbf{x})\) や決定境界を直接学び、生成モデルは \(p(\mathbf{x},y)\) や \(p(\mathbf{x})\) を学ぶ。
手法と目的関数の対応¶
どの手法も「損失（または尤度）を最小（最大）にするパラメータを、ある解き方で求める」形をしている。
| 手法 | 最適化の対象 | 解き方 | ページ |
|---|---|---|---|
| 線形回帰 | 正規分布の負の対数尤度（二乗誤差） | 正規方程式／勾配降下法 | 線形回帰 |
| Ridge／Lasso | 負の対数事後確率（二乗誤差＋正則化項） | 正規方程式（Ridge）／座標降下法・劣勾配法（Lasso） | 同上 |
| ロジスティック回帰 | ベルヌーイ分布の負の対数尤度（交差エントロピー） | 勾配降下法／ニュートン法 | ロジスティック回帰 |
| SVM | マージン最大化（ヒンジ損失＋L2 正則化） | 双対問題の二次計画（SMO 法） | SVM |
| ニューラルネット | 回帰は MSE、分類は交差エントロピー | 誤差逆伝播法＋勾配降下法 | 多層パーセプトロン |
| 決定木 | 不純度の減少量 | 貪欲な再帰分割 | 決定木・アンサンブル |
| ランダムフォレスト | 同上（木の集団） | バギング | 同上 |
| 勾配ブースティング | 任意の損失の負の勾配への当てはめ | 逐次的な加法モデル | 同上 |
| ナイーブベイズ・GPR・CRF・HMM | 事後確率・周辺尤度・条件付き尤度 | 解析解／勾配法／EM 法／動的計画法 | ナイーブベイズ・ガウス過程・CRF |
| PCA・LDA・ICA・t-SNE・UMAP | 分散最大化・クラス間／内分散比・KL ダイバージェンスなど | 固有値問題／勾配法 | 次元圧縮 |
| k-means・GMM・DBSCAN | クラスタ内分散・混合ガウスの対数尤度・密度 | 交互更新／EM 法／密度探索 | クラスタリング |
| AE・VAE・GAN | 再構成誤差・ELBO・ミニマックス目的 | 誤差逆伝播法（交互更新） | 自己教師あり学習・生成モデル |
k近傍法¶
新しい入力 \(\mathbf{x}\) に対し、訓練データ \(\{(\mathbf{x}_n,y_n)\}_{n=1}^{N}\) のうち距離が小さい \(K\) 個（近傍集合 \(\mathcal{N}_K(\mathbf{x})\)）を使って予測する。
\[
\begin{aligned}
&\text{距離} && d(\mathbf{x},\mathbf{x}_n)=\|\mathbf{x}-\mathbf{x}_n\|_2 \\[2mm]
&\text{近傍集合} && \mathcal{N}_K(\mathbf{x})=\{\,d(\mathbf{x},\mathbf{x}_n)\text{ が小さい順に }K\text{ 個の }\mathbf{x}_n\,\} \\[2mm]
&\text{分類} && \hat{y}=\mathop{\rm argmax}_{c}\sum_{\mathbf{x}_n\in\mathcal{N}_K(\mathbf{x})}\mathbb{1}\bigl[y_n=c\bigr] \\[2mm]
&\text{回帰} && \hat{y}=\frac{1}{K}\sum_{\mathbf{x}_n\in\mathcal{N}_K(\mathbf{x})}y_n \\[2mm]
&\text{距離で重み付け} && \hat{y}=\frac{\sum_{n}w_n y_n}{\sum_{n}w_n},\quad w_n=\frac{1}{d(\mathbf{x},\mathbf{x}_n)}
\end{aligned}
\]
- 非パラメトリックで怠惰学習（lazy learning）：訓練では何も学習せず、データを保存するだけ。推論時に全データとの距離を計算する（1 件あたり \(O(ND)\)）。
- ハイパーパラメータは \(K\) と距離。\(K\) は交差検証で選ぶ（評価）。
- \(K=1\) のとき、決定領域は各訓練点を中心とするボロノイ図になる。\(K\) が小さいと境界が複雑（過剰適合）、大きいとなめらか（過少適合）。
- \(N\to\infty\) の1-NN の誤り率は、ベイズ誤り率 \(R^{*}\) を使って \(R^{*}\le R_{\mathrm{1NN}}\le 2R^{*}(1-R^{*})\)（2クラス、Cover–Hart）と抑えられる。
- 特徴量のスケールをそろえる（標準化）。単位が大きい特徴量が距離を支配するため。
動かしてみる
- \(K=1\) にすると、背景の境界がデータの点に張り付いて入り組みます。\(K=15\) にすると、境界がなめらかになり、少数の点は無視されます（\(K\) が小さいほど複雑）。
- 問い合わせ点を 2 つのクラスの境目に動かすと、\(K\) を変えるだけで予測が入れ替わります（境目では \(K\) の選び方が結果を左右する）。
- 距離を L1・L∞ に切り替えると、近傍の範囲（破線）が菱形・正方形になり、選ばれる近傍が変わります。
距離¶
| 距離 | 式 | 特徴 |
|---|---|---|
| ユークリッド（L2） | \(\sqrt{\sum_i (x_i-y_i)^2}\) | 直線距離。最も一般的 |
| マンハッタン（L1） | \(\sum_i \lvert x_i-y_i\rvert\) | 各成分の差の和。外れ値の影響が二乗より小さい |
| チェビシェフ（L∞） | \(\max_i \lvert x_i-y_i\rvert\) | 最大の差だけを見る |
| ミンコフスキー（Lp） | \(\bigl(\sum_i \lvert x_i-y_i\rvert^{p}\bigr)^{1/p}\) | \(p=1,2,\infty\) で上の3つ。\(p\ge1\) で距離の公理を満たす |
| コサイン距離 | \(1-\dfrac{\mathbf{x}\cdot\mathbf{y}}{\lVert\mathbf{x}\rVert\lVert\mathbf{y}\rVert}\) | 向きだけを見る。大きさに依存しない（文書ベクトルなど） |
| マハラノビス | \(\sqrt{(\mathbf{x}-\mathbf{y})^{\top}\boldsymbol{\Sigma}^{-1}(\mathbf{x}-\mathbf{y})}\) | 分散と相関を考慮。\(\mathbf{y}\) を平均 \(\boldsymbol{\mu}\) とすれば、分布の中心からの距離 |
\[
\begin{aligned}
&\text{Lp 距離} && d_p(\mathbf{x},\mathbf{y})=\|\mathbf{x}-\mathbf{y}\|_p=\Bigl(\sum_{i=1}^{D}\lvert x_i-y_i\rvert^{p}\Bigr)^{1/p},\qquad d_\infty=\max_i\lvert x_i-y_i\rvert \\[2mm]
&\text{コサイン類似度・距離} && \cos\theta=\frac{\mathbf{x}\cdot\mathbf{y}}{\|\mathbf{x}\|\,\|\mathbf{y}\|},\qquad d_{\cos}=1-\cos\theta\ \in[0,2] \\[2mm]
&\text{マハラノビス距離} && d_M(\mathbf{x},\boldsymbol{\mu})=\sqrt{(\mathbf{x}-\boldsymbol{\mu})^{\top}\boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu})}
\end{aligned}
\]
- マハラノビス距離：\(\boldsymbol{\Sigma}=\mathbf{I}\) ならユークリッド距離、\(\boldsymbol{\Sigma}\) が対角なら各軸を標準偏差で割ったユークリッド距離。一般には \(\boldsymbol{\Sigma}=\mathbf{L}\mathbf{L}^{\top}\) として \(\|\mathbf{L}^{-1}(\mathbf{x}-\boldsymbol{\mu})\|_2\) に等しく、データを白色化してからユークリッド距離をとることにあたる。等距離面は楕円。
- コサイン距離は三角不等式を満たさず、厳密には距離ではない（角度そのもの \(\arccos(\cos\theta)\) なら距離）。\(L_2\) 正規化したベクトルでは \(\|\mathbf{x}-\mathbf{y}\|_2^2=2\,d_{\cos}\)。
- \(p<1\) の Lp は凹んだ形になり、三角不等式が成り立たない（距離にならない）。
動かしてみる
- Lp距離で \(p\) を 1 から大きくすると、距離 1 の曲線が菱形 → 円 → 正方形へ近づきます（\(p\to\infty\) で L∞）。
- マハラノビス距離で \(\rho\) を 0.9 にすると、右上がりの細い楕円になります。同じ位置の点でも、ユークリッド距離より小さくなります（相関の方向は「ありふれた方向」とみなされる）。
- コサイン距離で \(x_1,x_2\) を同じ比率のまま動かしても距離は変わりません（向きしか見ないため）。
次元の呪いと高速化¶
- 次元 \(D\) が増えると、データが空間に対してまばらになり、最近傍と最遠傍の距離の差が相対的に小さくなる（距離の集中）。「近い」が意味を失い、k-NN の精度が落ちる。対策は次元圧縮（次元圧縮）や特徴選択。
- kd-tree：特徴量の軸に垂直な超平面で空間を二分する木（中央値で分割、軸は順番に回すか分散最大の軸を選ぶ）。探索は葉まで降りたあと、「超平面までの距離 ≥ 現在の \(K\) 番目の距離」の枝を打ち切りながら戻る。次元が低いとき平均 \(O(\log N)\)、次元が高いと全探索に近づく（目安：\(N\gg 2^{D}\) でないと効かない）。
- ボールツリー：超球で分割する木。kd-tree より中程度の次元に強い。
- 近似最近傍探索：厳密な最近傍をあきらめ、「真の最近傍の \((1+\varepsilon)\) 倍以内」の点を高速に返す。ハッシュ（LSH）、近傍グラフ（HNSW）、直積量子化（PQ）など。大規模なベクトル検索で使われる。
試験の着眼点¶
- k-NN は学習フェーズがない（怠惰学習）。計算コストは推論時に大きい。\(K\) はハイパーパラメータで、小さいと過剰適合、大きいと過少適合。
- 分類は多数決、回帰は平均。2クラスでは \(K\) を奇数にすると同数にならない。
- 距離の使い分け：向きだけならコサイン、特徴量の相関・スケールを考慮するならマハラノビス。特徴量の標準化を忘れない。
- マハラノビス距離は \(\boldsymbol{\Sigma}^{-1}\) を挟む。\(\boldsymbol{\Sigma}=\mathbf{I}\) でユークリッド距離に一致。
- kd-tree は低次元で有効、高次元では効果が落ちる。近似最近傍は精度を少し捨てて速度を得る。
- 半教師あり＝一部だけラベルあり、自己教師あり＝データ自身からラベルを作る、教師なし＝ラベルなし。