Nadaraya-Watson推定 と k近傍法(後編)


この記事は[古川研究室 Workout calendar](https://qiita.com/flab5420/private/aee38a24be700d146817) 7日目の記事です. 
本記事は古川研究室の学生が学習の一環として書いたものです．

一回ほとんど書いてた記事が全部消えて夜中に吠えました. 「下書き保存」と友達になりましょう.

# 前回のおさらい
前回の記事 [Nadaraya-Watson推定 と k近傍法(前編)](https://qiita.com/kpasso1015/items/50e62ca52b4a19bfb782)では 回帰の問題設定を述べ, その回帰を解く手法の一つとしてk近傍法を解説しました。

## 回帰の問題設定
given: $D$次元ベクトルの観測データ$\mathbf{x} \in \mathbb R^D$とラベル$y \in \mathbb R$のペア$\left\\{ ( \mathbf{x}_n,y_n )\right\\} _{n=1}^N $
estimate: $y \simeq f(\mathbf{x})$となるような写像 $f$

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/9dcd5d02-0d57-1d04-918e-e50712e8a0e7.png)

横軸はデータ$x$軸, 縦軸はラベル$y$軸の図です. 真の関数(緑線)にノイズが加わって, 入力(青点)を得ます. 真の関数がわからない中でデータとラベル集合を使って写像を推定してします. 

## k近傍法

真の関数(緑線)にノイズが加わった入力(青点)が得られている状況で, 4つの近傍のラベルの平均として得られた写像 $f$ (オレンジ線)が以下の図になります.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/272d05ae-9647-fb55-a447-3ddeb8917ab6.png)

着目点(赤点線: $x=1.8$)とそこの近傍の範囲(赤線)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/ab44fe7a-7076-0fc6-9c09-7ce559269ea3.png)


k近傍法は重みや基底関数を使わずに写像を推定していますが, その推定した写像は**不連続**な写像になっており**微分ができません**. 

# Nadaraya-Watson推定

Nadaraya-Watson推定（NW）は回帰手法の一つです. 

k近傍では近傍に含むデータに等しい重みを付与して(平均)していますが, Nadaraya-Watson推定では着目点とデータの距離に応じて滑らかに減少する重みを与えます. 
Nadaraya-Watson重み付きカーネル平均はカーネル関数を使って以下の式で与えられます.

```math
f(\mathbf{x}) = \frac{\sum_{i=1}^N K_\lambda(\mathbf{x},\mathbf{x}_i)y_i}{\sum_{j=1}^N K_\lambda(\mathbf{x},\mathbf{x}_j)}

```

今回 カーネル関数$K_\lambda(\mathbf{x},\mathbf{x_j})$は次式で与えます.

```math
K_\lambda(\mathbf{x},\mathbf{x_j}) = \exp(\frac{-1}{2\sigma^2}||\mathbf{x} - \mathbf{x_j}||^2)
```

この式はガウス関数の式と等価です. 他のカーネル関数としてはイパネクニコフ関数や短形3次関数が一般的です.
「カーネル関数, 」と続けますと[本一冊](https://www.amazon.co.jp/%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB%E5%A4%9A%E5%A4%89%E9%87%8F%E8%A7%A3%E6%9E%90%E2%80%95%E9%9D%9E%E7%B7%9A%E5%BD%A2%E3%83%87%E3%83%BC%E3%82%BF%E8%A7%A3%E6%9E%90%E3%81%AE%E6%96%B0%E3%81%97%E3%81%84%E5%B1%95%E9%96%8B-%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA%E7%A2%BA%E7%8E%87%E3%81%A8%E6%83%85%E5%A0%B1%E3%81%AE%E7%A7%91%E5%AD%A6-%E8%B5%A4%E7%A9%82-%E6%98%AD%E5%A4%AA%E9%83%8E/dp/4000069713)書くのにちょうどいい分量になるので省略し, ここではカーネル関数 $K_\lambda(\mathbf{a},\mathbf{b})$は$\mathbf{a}=\mathbf{b}$のとき最大値の1をとること, $\mathbf{a}$ と$\mathbf{b}$の近さを表す値になっているということだけを押さえましょう.

## 実装
k近傍法と同様の状況です.(データ数は5)

### 近傍半径: 0.2のとき
```python
def NW(sigma=0.2):
    global H, R, Y
    Delta = x[:,None] - x_star[None,:] #データ点と任意のx_starを全ての距離をnumpyのBroad castで計算している
    Dist = np.square(Delta)
    H = np.exp(-0.5/sigma * Dist) #近傍半径が大きいほど、距離をあまり考慮しなくなるのがわかる
    G = np.sum(H, axis=0)[None,:] 
    R = H/G
    check_sum = np.sum(R, axis=0)
    # print(check_sum)
    Y = R.T@t #(任意のx_starの数,データ数) x_star (データ数, ラベルの次元(今回は1))

sigma = 0.2 #近傍半径 
NW(sigma)
```

<font color="MediumVioletRed">↑ 式の実装をミスっていました． 5行目のHの実装のところのsigmaは正しくはsigma** 2です．</font>

#### カーネル関数: 

```math
f(\mathbf{x}) = K_\lambda(\mathbf{x},\mathbf{x}_i):
``` 

各データ点$x_i$を中心とした近傍半径0.2のガウス関数が描画されました．
各ラベルが及ぼす範囲を可視化したものと思ってよいでしょう．着目点（任意の$x$）で
例えば，任意の$x$を$x=4$としたとき，紫のガウス関数が他のデータ点よりも大きくなっています．
つまり，x=4の写像f(x)の値は紫のデータ点$x_{purple}$に対応するラベル$y_{purple}$の重みを他のラベルよりも大きく用いるつもりのようです．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/41eb32a4-d167-37b1-6dac-1edf2f001568.png)



#### カーネル関数: 

```math
f(\mathbf{x}) = \frac{K_\lambda(\mathbf{x},\mathbf{x}_i)}{\color{red}{\sum_{j=1}^N K_\lambda(\mathbf{x},\mathbf{x}_j)}}:
``` 

任意の$x$において全ての重みの合計が1となるように ~~正規化~~(カーネル関数なので元から $0 < x \leqq 1$ でした．) 処理をします.
着目点(青点線 $x=4$)を見ると, 総和が1(紫の関数がほぼ1)になっていることがわかりやすいと思います.

x<4でも紫の関数がほぼ１になっています．この処理をすることによって，$f(x) \simeq 1 * x_{purple}$ となって，x<4のとき，$f(x) \simeq x_{purple}$となるわけですね．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/2ad009b9-1019-9cf9-f0ea-2379c8bf6e87.png)

#### 重み付きカーネル平均:

```math
f_{NW}(\mathbf{x}) = \frac{\color{red}{\sum_{i=1}^N} K_\lambda(\mathbf{x},\mathbf{x}_i) \color{red}{y_i} }{\sum_{j=1}^N K_\lambda(\mathbf{x},\mathbf{x}_j)}
```
最終的なNadaraya-Watson推定における式は上式になります．

```math
f_{NW}(\mathbf{x})= {\sum_{i=1}^N} r_i(\mathbf{x}) {y_i} \\
r_i(\mathbf{x})= \frac{K_\lambda(\mathbf{x},\mathbf{x}_i)}{{\sum_{j=1}^N K_\lambda(\mathbf{x},\mathbf{x}_j)}}
```
これを上のようかけば，ある重み$r_i$でy_iをかけてその総和をとったものがfということがわかると思います．

先ほどのカーネル関数でそれぞれのラベルに重みをつけ 総和をとったもの(総和が1なので重み付き平均)が推定した写像(オレンジ線)です.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/d7de7db4-3487-fda6-5376-1ac9533d391e.png)

k近傍法と同様にデータの**内分点**を通り, 得られた写像は滑らかな写像になっていることが確認できます. またデータの端点以降（$x > -3.0, 3.3 < x$）の写像は端点のラベルに収束しています.

データ数を増やした場合以下のような結果になります.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/72e89e4c-24c3-3a85-2031-f1fbf2a2092d.png)

データ数の数ほどガウス関数を用意しているので, データ数の数ほど表現力があがることになります.

次に近傍半径の大きさを変えた実行結果を見ていきましょう.


### 近傍半径: 2.0のとき

近傍半径を大きくした場合, 任意の$x$ではより遠くのデータの影響を受けやすくなります.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/540b96db-782a-8ba7-5603-16b81d27aa36.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/95af30b1-7a26-3535-0f0a-5aec7bf24378.png)

限りなく近傍半径を大きくした場合写像は単純にラベルのほぼ平均になります.

#### 近傍半径: 10000.0のとき
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/6f920d1b-bad0-27c7-439d-533322fed78a.png)

(そういえばk近傍法も$k=n$のときラベルの平均になったなあ....あれれ??)

### 近傍半径: 0.001のとき

近傍半径を小さくした場合, 任意の$x$で他のデータの影響を受けにくくなります.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/86efb187-15c2-6f18-56fe-efff31b0cb0a.png)


カーネル関数はデルタ関数のようになります.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/696a357e-9dd4-d95b-3456-8ef8579b768c.png)

任意の$x$では, ほぼ一つの点にしか重みがついてないことがわかります.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/a5aaec12-39c5-f7b7-00ae-b2672ce93ba5.png)



#### k近傍法(k=1)
ここで近傍法との関わりを見ていきましょう.
近傍の数が1の時の結果は以下のようになります.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/154814/6222c1b4-b6eb-1e70-37be-182ea46b1be4.png)


<font color="DarkViolet">NWで近傍半径の大きさを限りなく小さくした時と同じような結果になりました.　</font>

今回は近傍の数が１の場合でしたが，１以外の場合のk近傍法をあえてカーネル回帰として捉えるならば, 近傍が変わるまでの長さが一律ではないことから, カーネル幅がデータごとによって変わるデジタル波形のような関数をカーネル関数としたカーネル回帰といえそうです．？

## まとめ
Nadayawa-Watson推定はk近傍法と違い,滑らかな写像が推定できることがわかりました.どちらの手法もラベルを使って写像を表現するということは変わらず どちらもデータの*内分点*を通るような写像で, 近傍半径を変えることによってその写像の様相は変化します.　


## 実行ソース
[Google Colab](https://drive.google.com/file/d/1rMXCLd5ruMlTbwHMM6VeoopQTYKPxf69/view?usp=sharing)
[Github](https://github.com/kpasso1015/qiita)
ここにあげているのでよければ実行してみてください.


## 参考文献

Trevor Hastie・Robert Tibshirani・Jerome Friedman著, 杉山 将・井出 剛 ら監訳 [「統計的学習の基礎」](https://www.amazon.co.jp/%E7%B5%B1%E8%A8%88%E7%9A%84%E5%AD%A6%E7%BF%92%E3%81%AE%E5%9F%BA%E7%A4%8E-%E2%80%95%E3%83%87%E3%83%BC%E3%82%BF%E3%83%9E%E3%82%A4%E3%83%8B%E3%83%B3%E3%82%B0%E3%83%BB%E6%8E%A8%E8%AB%96%E3%83%BB%E4%BA%88%E6%B8%AC%E2%80%95-Trevor-Hastie/dp/432012362X/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&keywords=%E7%B5%B1%E8%A8%88%E7%9A%84%E5%AD%A6%E7%BF%92%E3%81%AE%E5%9F%BA%E7%A4%8E&qid=1563430788&s=gateway&sr=8-1) $\S 6$  p.220~