# 回顧 RBF

在 [Gaussian SVM](https://hackmd.io/DNYe1DzxReW0b53OaMFedA?view#%E4%B8%8D%E5%90%8C%E8%A7%92%E5%BA%A6--Radial-Basis-Function-RBF-kernel) 的時候我們有提到 RBF 這個酷東西。

- Radial：輻射狀。代表只跟「距離有關」
- Basis Function：代表要拿來做線性組合 to be combined
- 是被做線性組合

那時有提到 Gassian SVM 可以看成是由各個 SV 的高斯函數做線性組合。

如果把 $y_{n}$ 跟高斯函數合在一起當作一個 $g$：

$$
g_{n}(\mathbf{x})=y_{n}exp(-\gamma\left\|\mathbf{x}-\mathbf{x}_{n}\right\|^{2})
$$

這個 $g_{n}$ 決定了要投多少票出來，看那個 $\mathbf{x}$ 到底值多少 $y_{n}$；那麼 Gaussian SVM 可以看做是這些 $g_{n}$ 的線性組合：

$$
g_{SVM}(\mathbf{x})=sign\left(\sum_{SV}\alpha_{n}g_{n}(\mathbf{x})+b\right)
$$

我們試著把這種線性組合延伸到神經網路上。

# RBF Network

原本的網路：

- 輸入 $\mathbf{x}_{n}$ 有「權重 $\mathbf{w}_{n}$」對應
- 「內積」後代入 tanh 函式做 S 型轉換

RBF 網路：

$$
h(\mathbf{x})=output\left(\sum_{m=1}^{M}\beta_{m}RBF(\mathbf{x},\boldsymbol{\mu}_{m})\right)
$$

- 輸入 $\mathbf{x}_{m}$ 有「中心點 $\boldsymbol{\mu}_{m}$」對應
- 算出 RBF 的值後再乘上 $\beta_{m}$

RBF 網路的目的就是要學會 $\boldsymbol{\mu}_{m}$ 跟 $\beta_{m}$。

**RBF 網路只有三層**，也就是說就只有中間一層隱藏層，因此 RBF 網路又叫做
「linear aggregation of radial hypothes」

# 相似性

[之前講 Kernel 的時候](https://hackmd.io/DNYe1DzxReW0b53OaMFedA#Other-Valid-Kernel)有提到做內積是在算一種相似性，而 RBF kernel 也是在計算一種相似性。

這種相似性是建立在「距離」上，越近代表越相似。

所以也有其他以距離作為相似性的 函數，例如 Truncated 函數：

$$
Truncated(\mathbf{x},\mathbf{x}^{'})=\left[\left[\left\|\mathbf{x}-\mathbf{x}^{'}\right\|\le 1\right]\right]\left(1-\left\|\mathbf{x}-\mathbf{x}^{'}\right\|\right)^{2}
$$
>又叫截尾函數，也就是 $(1-x)^{2}$ 的圖形，只剩下 $x\le 1$ 的部分。

## 其他相似性

其實除了距離之外：

- 神經網路：
- 透過層層向量內積並經由 tanh 轉換得到的值來評估相似性
- $Neuron(\mathbf{x},\mathbf{x}^{'})=tanh(\gamma \mathbf{x}^{T}\mathbf{x}^{'}+1)$
- DNA 序列比對(一般資料)：
- DNA 序列就是一種字串
- 會使用「修改距離函數」$EditDistance(\mathbf{x},\mathbf{x}^{'})$
- 算出如何以最小的「修改距離」得到想要的樣子
- $EditDistance(\mathbf{x},\mathbf{x}^{'})$ 就是一種計算相似性的函數，只不過可能不是利用內積，也不是利用向量間的距離，而是其他更複雜的方式。

- [參考資料：Edit Distance](https://www.cis.upenn.edu/~cis110/12su/hw/hw06/dynprog.shtml)

## 特徵轉換

從上面可以發現相似性是一個很好定義特徵轉換的方法。

所以可以自己去設計出一個相似性的衡量作為特徵轉換。

---

# Full RBF

$$
h(\mathbf{x})=output\left(\sum_{m=1}^{M}\beta_{m}RBF(\mathbf{x},\boldsymbol{\mu}_{m})\right)\\
M=N,\boldsymbol{\mu}_{m}=\mathbf{x}_{m}
$$

把所有的 $\mathbf{x}_{m}$ 作為中心點，這種比較~~偷懶~~的方法叫 Full RBF。

這樣一來每個 $\mathbf{x}_{m}$ 都會對周遭的 $\mathbf{x}$ 依照 $\beta_{m}$ 的量產生影響。

## 平等投票

$$
g_{uniform}(\mathbf{x})=sign\left(\sum_{m=1}^{M}y_{m}RBF(\mathbf{x},\mathbf{x}_{m})\right)
$$

做分類的時候，如果 $\beta_{m}=1\cdot y_{m}$，代表每個點都有相同的基本影響力，只是會隨距離增加而減弱而已。

# Nearest Neighbor 好鄰居法

$$
g_{neighbor}(\mathbf{x})=y_{m}\ of\ \mathbf{x}_{m}\text{ that closest to }\mathbf{x}
$$

在上面平等投票的例子中，由於 RBF 內部有指數然後又是平方，距離造成的影響甚鉅，距離最近的會主導加總的分數。

那麼就直接一點，直接以最近的鄰居的意見作為意見。

## k Nearest Neighbor / KNN

或者找多一點的鄰居來統合意見，把 k 個人的意見進行投票。

:::info
鄰居法是偷懶的進階版，訓練的時候不需要花力氣，只要挑最近的幾個人就好根本就不用訓練。

但是在測試的時候就真的需要做「挑選」這個動作，所以反而是這裡需要花力氣。
:::

# For squared error regression:

RBF Network 改做 Regression 並以 squared error 做為 error function，然後不要那麼偷懶，改來最佳化 $\beta_{m}$。

$$
h(\mathbf{x})=\left(\sum_{m=1}^{M}\beta_{m}RBF(\mathbf{x},\boldsymbol{\mu}_{m})\right)\\
$$

會發現其實就只是將資料經過 RBF 轉換過的 Regression 問題。

$$
\mathbf{z}_{n}=[RBF(\mathbf{x}_{n},\mathbf{x}_{1}),RBF(\mathbf{x}_{n},\mathbf{x}_{2}),...,RBF(\mathbf{x}_{n},\mathbf{x}_{n})]
$$

## 有趣特性 -- 完美 $E_{in}$

原本：

$$
\boldsymbol{\beta}=(\mathbf{Z}^{T}\mathbf{Z})^{-1}\mathbf{Z}^{T}\mathbf{y}
$$

其中 $Z^{T}Z$ 要是可逆矩陣。

不過如果是經過 RBF 轉換的資料會有個有趣的特性：

1. 他是個方陣
2. 如果全部 $\mathbf{x}_{n}$ 都不一樣，則 $\mathbf{Z}$ 是可逆的。

那麼上面的式子就可化簡為：

$$
\boldsymbol{\beta}=\mathbf{Z}^{-1}{\mathbf{Z}^{T}}^{-1}\mathbf{Z}^{T}\mathbf{y}=\mathbf{Z}^{-1}\mathbf{y}
$$

而用這個 $\boldsymbol{\beta}$ 代入原先的 $\mathbf{x}_{m}$：

$$
g_{RBF}(\mathbf{x}_{m})=\boldsymbol{\beta}^{T}\mathbf{z}_{m}=\mathbf{y}^{T}\mathbf{Z}^{-1}(m\ th\ column\ of\ \mathbf{Z})=\mathbf{y}^{T}[0,0,..,\underbrace{1}_{m\ th},0,0..]=y_{m}
$$

>因為 $\mathbf{Z}^{-1}\mathbf{Z}=\mathbf{I}$，所以只有一個 column 的話對角線只有一個位置會是 1

會發現輸入 $\mathbf{x}_{m}$ 就會得到 $\mathbf{y}_{m}$，也就是說 $E_{in}=0$。

## Regularized Full RBF Network

### Exact Interpolation

在數學的某些領域，例如要近似某些函數的 function approximation，這樣 E_in 是 0 叫做完美的內插 exact interpolation。

但是在 ML 裡面這是我們最不想遇到的事情。所以我們可以來加些 Regularization。

## Regularization

加了 Regularization 公式解會變成：

$$
\boldsymbol{\beta}_{RBF}=(\mathbf{Z}^{T}\mathbf{Z}+\lambda\mathbf{I})^{-1}\mathbf{Z}^{T}\mathbf{y}
$$

可以發現這個結果跟之前的 [Kernel Ridge Regression](https://hackmd.io/@ShawnNTU-CS/SkcCdKRnn) 很像：

$$
\boldsymbol{\beta}_{KRR}=(\mathbf{K}+\lambda\mathbf{I})^{-1}\mathbf{y}=(\mathbf{Z}+\lambda\mathbf{I})^{-1}\mathbf{y}\\
$$

因為 $\mathbf{K}$ 恰好是經過 kernel trick 的 $N\times N$ 矩陣，也就是 $\mathbf{Z}$。

但是他們只是「看起來很像」，實則不一樣，因為：

- KRR 是把 $\mathbf{x}_{i}$ 轉換到無限多維的 $\mathbf{d}_{i}$
- RBF Net 是把 $\mathbf{x}_{i}$：
- 先轉換到無限多維的 $\mathbf{d}_{i}$
- 接著跟其他 $N$ 個(包含自己)轉換出來的 $\mathbf{d}_{n}$ 做內積
- 得到最終的轉換結果 $\mathbf{z}_{i}$
$$
\begin{bmatrix}
-\ \mathbf{d}_{1}^{T} - \\
-\ \mathbf{d}_{2}^{T} - \\
\vdots \\
-\ \mathbf{d}_{n}^{T} -
\end{bmatrix}\cdot\mathbf{d}_{i}=
\mathbf{D}\cdot\mathbf{d}_{i}=\mathbf{z}_{i}\\
\mathbf{D}\cdot\mathbf{D}^{T}=\mathbf{Z}
$$

也就是說上面 RBF 的 $\mathbf{Z}$，其實是 KRR 的 $\mathbf{Z}$ 的平方：

$$
\mathbf{Z}_{RBF}=\mathbf{D}\cdot\mathbf{D}^{T}=\mathbf{Z}_{KRR}\cdot\mathbf{Z}^{T}_{KRR}
$$

所以其實 KRR 的轉換是到無限多維，而 RBF 則是到 N 維；上面公式其實兩者差異蠻大的：

$$
\boldsymbol{\beta}_{RBF}=(\mathbf{Z}_{RBF}^{T}\mathbf{Z}_{RBF}+\lambda\mathbf{I})^{-1}\mathbf{Z}_{RBF}^{T}\mathbf{y}
$$

$$
\boldsymbol{\beta}_{KRR}=(\mathbf{K}+\lambda\mathbf{I})^{-1}\mathbf{y}=(\mathbf{Z}_{RBF}+\lambda\mathbf{I})^{-1}\mathbf{y}=(\mathbf{Z}_{KRR}\cdot\mathbf{Z}^{T}_{KRR}+\lambda\mathbf{I})^{-1}\mathbf{y}\\
$$

# Fewer Centers as Regularization

之前[ SVM 的 KRR 跟 KLR 使用了 Kernel ](https://hackmd.io/@ShawnNTU-CS/SkcCdKRnn#dense-boldsymbolbeta) 的 $\boldsymbol{\beta}$ 是個緻密矩陣，跟使用 Dual Problem 得到的稀疏矩陣 $\boldsymbol{\alpha}$ 不一樣，有計算量上面的差異，所以那時候才從 Tube Regression 延伸出一個 SVM 的 Regression Model。

而上面的 Full RBF Network 也發生了一樣的情形，所以我們接著嘗試只以某些點做為中心，這樣可以減少權重的數量，做到 Regularization 的效果。

那些選出的點又叫做 **prototypes**。

## 好的 prototypes

好的議員可以為民眾發聲，好的 prototypes 可以很好的代表資料們的意見。

要找出好的 prototypes，要將資料分群，要把近的點分在一起，從中選出 prototypes。

- 群不可以重疊
- 不可以沒有人分到

所以分群有以下的 Error measure：

$$
E_{in}(S_{1},...,S_{M};\boldsymbol{\mu}_{1},...,\boldsymbol{\mu}_{M})=\frac{1}{N}\sum_{n=1}^{N}\sum_{m=1}^{M}[[\mathbf{x}_{n}\in S_{m}]]\left\|\mathbf{x}_{n}-\boldsymbol{\mu}_{n}\right\|^{2}
$$

但是這種混合了布林運算跟數值的極值問題，我們在 PLA 的地方遇過一次，知道這是個難以解決的問題。

# k-Means / Alternating Optimization

既然混在一起最佳化很難，那我們可以「分開」著最佳化。

## 先固定中心

先固定中心點，就可以很容易地依據「與中心的距離」將每個資料分群。

## 再更新中心

分好群後，布林運算就解決掉了，決定新的中心點就變得很容易，因為是個無限制的最佳化問題

$$
min \sum_{\mathbf{x}_{n}\in S_{m}}\left\|\mathbf{x}_{n}-\boldsymbol{\mu}_{m}\right\|^{2}
$$

經過梯度等於 0 可以發現最佳中心就是平均：

$$
\boldsymbol{\mu}_{m}=\frac{\sum_{\mathbf{x}_{n}\in S_{m}}\mathbf{x}_{n}}{|S_{m}|}
$$

這樣交替最佳化的方式就是有名的 k-Means 分群演算法。

## $\boldsymbol{\mu}$ 初始值

起始步驟需要給 $\boldsymbol{\mu}$ 初始值，老師說他常用的選取方法，是從 $\mathbf{x}_{n}$ 當中隨機選出來。

當然其他論文可能會有不同的方法，但是重點是要**隨機選取**，因為 k-Means 跟神經網路一樣，是有可能在複雜的最佳化問題中掉入區域極值；只要初始值不同，結果就有可能不一樣。

## 停下來？

因為每一步都是在讓 $E_{in}$ 下降，所以最終會收斂在一個區域極值。

---

# RBF + K MEANS

這下我們成功挑出好的代表了，接著再用 RBF 網路學會 $\beta$ 就行了；或者說用公式解算出最佳的 $\beta$。

像這樣使用非監督式學習從原始資料萃取出某些重要得起始點來幫助特徵轉換方法，就好像之前的自動編碼機。

所以做 Validation 時的參數就有：

- M：要有幾個中心點
- 適當的中心點數量很重要
- M 越大，越有力量
- RBF：如果是用 Gaussian 的話就是 $\gamma$
- $\lambda$：Regularizer 的調整參數
- $\lambda$ 越大，代表限制越大。