問題
最近傍法（2.52節）は、新しい入力ベクトル$\mathbf{x}$を、訓練集合の中でこれにもっとも近い入力ベクトル$\mathbf{x} _ {n}$を持つものと同じクラスに分類する。最も単純な場合では、距離はユークリッド距離$||\mathbf{x} - \mathbf{x} _ {n}||^2$が用いられる。これをスカラー積で表すことで、カーネル置換を用いて、一般的な非線形カーネルを用いた最近傍法を導け。
解答
この問題は本文において二乗和誤差に対してカーネル置換を用いたのと同じように、最近傍法に対してもカーネル置換が適用できることを確認する問題である。
ユークリッド距離はスカラー積で表すと、
\begin {align*}
\left\|\mathbf{x}-\mathbf{x}_{n}\right\|^{2}=\mathbf{x}^{\top} \mathbf{x}-2 \mathbf{x}^{\top} \mathbf{x}_{n}+\mathbf{x}_{n}^{\top} \mathbf{x}_{n}
\tag{ex6.3.1}
\end {align*}
となる。
線形カーネル$k(\mathbf{x}, \mathbf{x'}) = \mathbf{x}^{\top} \mathbf{x'}$を用いて(ex6.3.1)を書き直すと、
\begin {align*}
\left\|\mathbf{x}-\mathbf{x}_{n}\right\|^{2} = k(\mathbf{x}, \mathbf{x}) - 2k(\mathbf{x}, \mathbf{x}_{n}) + k(\mathbf{x}_{n}, \mathbf{x}_{n})
\tag{ex6.3.2}
\end {align*}
線形カーネルを用いてユークリッド距離での最近傍法を表現できる。
また、今回はユークリッド距離を用いた最近傍法について述べたが、距離表現には様々なものがあり、例えば、
- ミンコフスキー距離
\begin {align*}
d\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)=\left(\sum_{k=1}^{q}\left|x_{i k}-x_{j k}\right|^{p}\right)^{1 / p}
\tag{ex6.3.3}
\end {align*}
- チェビシェフ距離
\begin {align*}
d\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)=\max _{k}\left(\left|x_{i k}-x_{j k}\right|\right)
\tag{ex6.3.4}
\end {align*}
- キャンベラ距離
\begin {align*}
d\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)=\sum_{k=1}^{q} \frac{\left|x_{i k}-x_{j k}\right|}{\left|x_{i k}\right|+\left|x_{j k}\right|}
\tag{ex6.3.5}
\end {align*}
などが定義されている。
最近傍法においてこのような距離を用いる場合を考慮して、(ex6.3.1)における$\mathbf{x}^{\top} \mathbf{x'}$を非線形カーネル$\kappa(\mathbf{x}, \mathbf{x'})$で置き換えれば、
\begin {align*}
\kappa(\mathbf{x}, \mathbf{x}) - 2\kappa(\mathbf{x}, \mathbf{x}_{n}) + \kappa(\mathbf{x}_{n}, \mathbf{x}_{n})
\tag{ex6.3.6}
\end {align*}
これで一般的な非線形カーネルを用いた最近傍法を導くことができた。
(参考：PRML本文p7)