---
tags: 機器學習技法
---

Ch14 Radial Basis Function Network
===

## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [RBF Network Hypothesis](https://www.coursera.org/learn/machine-learning-techniques/lecture/A02AE/rbf-network-hypothesis)

### Gaussian SVM Revisited

- 之前說 Gaussian SVM 就是無窮多維的 feature transform 之後，找到一條 large margin 的邊界
- 不過從結果式子來看，也可以說是拿一堆 Gaussian 來做 linear combination，這些 Gaussian 的中心 (mean) 就是我們的 support vector。
- 因為 $\exp(-\gamma\|x-x_n\|^2)$ 就是以 $x_n$ 為 mean 的 Gaussian function。
- 為什麼 Gaussian kernel 又稱 **Radial Basis Function (RBF)** kernel 呢?
- **radial**: 只跟 $x_n$ 的距離有關
- **basis function**: 因為我們要拿這些 function 來做 linear combination，係數就是那些 $\alpha_n$
- 我們把它拆開來看，令 $g_n(x)=y_n\exp(-\gamma\|x-x_n\|^2)$
- $g_n$ 這個 radial hypothesis 可以看成 $x$ 如果離 $x_n$ 越近，我就給 $y_n$ 越高的 weight
- 這樣 Gaussian SVM 就可以看成是**把各 radial hypothesis $g_n(x)$ 做 linear aggregation**
- **RBF Network 也是一樣的概念！**

### From Neural Network to RBF Network

- 為什麼說是 network 呢?
- 之前 NN 的 0~1 層是用 weights 來做 linear transform；而 RBF Network 現在是用 centers 來計算不同的 Radial Basis Function。
- NN: inner-product + tanh
- RBFN: distance + Gaussian
- 而連接 output layer 的部分 RBF Network 就跟 NN 差不多了，就是 linear aggregation。
- RBF Network 歷史上算是一種 NN，它在探討：如果把 neuron 取代成這些跟距離有關的函數，那可以做到什麼事?

### RBF Network Hypothesis

- 使用 RBF Network，你需要選擇的有
1. 哪些 centers $\mu_m$
- Gaussian SVM 使用 support vectors
2. 投票的 weight $\beta_m$
- Gaussian SVM 用 $\alpha_m$ 和 $y_m$ 共同決定
3. 使用什麼樣的 Radial Basis Function
- Gaussian SVM 使用 Gaussian (?

### RBF and Similarity

- (review) kernel 等價於 轉換到 $\mathcal Z$-space 之後做內積，因此必須滿足 Mercer's condition
- (review) 而 kernel 也是在描述一種相似性，轉換到 $\mathcal Z$-空間 之後的內積(相似性)。
- 而 RBF 也是在描述一種相似性，不過它是直接在 $\mathcal X$-空間中計算距離，轉換成的相似性。
- 所以 **Kernel 跟 RBF 可以看成是兩種不同的衡量相似性的方式。**
- 而 Gaussian kernel 就是它們兩個的交集！
- **RBF Network 告訴我們，相似性是一種很好的定義 feature transform 的方式。**
- NN 裡面其實也是在算 feature 跟 weight 之間的相似性(內積)。
- EditDistance 也是一種相似性。

### Fun Time: Different Kinds of RBF

- 4 是我們唯一沒辦法用距離來表示的 function
- 3 可以表示成 1 的極端形式

## [RBF Network Learning](https://www.coursera.org/learn/machine-learning-techniques/lecture/epawX/rbf-network-learning)

### Full RBF Network

- full RBF Network 就是說我們把所有資料點 $x_n$ 都拿當成 center，因此 $M=N$。
- physical meaning: 每個 $x_m$ 都對它周圍的點有影響力，影響力的大小為 $\beta_m$
- e.g. 一個特例是，$\beta_m=1\cdot y_m$
- 此時就是在對每個已知 data point 根據 similarity 做 voting
- full RBF Network 就是一個 **lazy** 的方法，直接納入所有 data point 當作 center
- > 這裡的 **lazy** 意思就是指 **lazy learner** 吧

### Nearest Neighbor

- RBF Network 跟 Nearest Neighbor 有些關聯
- 本來可能選擇 uniform 的 aggregation 全部的 data point
- 但是 RBF 最大的那個 data point 往往可以掌控全局，因為高斯函數衰退得很快 (隨著距離越遠)
- 這樣是不是其實可以不用算這麼大的 summation
- k-NN 的話就是只 aggregate $\exp(...)$ 前 $k$ 大的
- k-NN 也是一個 **lazy** 的方法。
- 意思是，**我其實沒有特別 learn 什麼，而是在要 predict 的時候，才去算**這些距離什麼的
- 因此 **training 時不花什麼力氣；但是 testing 時要花很大力氣。**
- > 這裡的 **lazy** 意思就是指 **lazy learner** 吧

### Interpolation by Full RBF Network

- full RBFN 其實就是用 RBF 做 transform 之後做 linear regression
- 疊出來的 $Z\in\mathbb R^{N\times N}$ 矩陣，它是 symmetric matrix
- 而且 $Z$ 的每個 element 是 Gaussian RBF，這樣的 matrix 它是可逆的
- > Q: 待證明
- 所以可以直接解 linear regression $\beta=Z^{-1}y$，這樣的結果很有趣，等等會講@@
- 注意 $\beta=\begin{bmatrix}\beta_1\\\beta_2\\\vdots\\\beta_N\end{bmatrix}$

### Regularized Full RBF Network

- $z_1$ 就是 $x_1$ 的 transform
- $\beta^T=y^T Z^{-1}$
- $z_1$ 是 $z$ 的第一個 column
- $Z^{-1}$ 跟 $Z$的第一個 column 相乘會得到 $\begin{bmatrix}1&0&...&0\end{bmatrix}^T$
- 可以從 $Z^{-1}Z=I$ 得到直覺。
- 同樣的推導可以得出 $g_{RBF}(x_n)=y_n$ 哇！$E_{in}(g_{RBF})=0$ 呢！好像不太妙...?
- 這樣的 model 較適合用在應用數學當中的 exact interpolation for function approximation，即完美的內插來逼近函數
- 但是以 ML 的角度來看，容易 overfit，那就做 regularization 吧
- kernel ridge regression 是對無窮多維做 regularization；而我們要對 RBFNet 做的是有限維 ($N$ 維) 的 regularization，所以公式會有點不一樣。

### Few Centers as Regularization

- 另一個可能的 regularization：不要用這麼多的 centers，也就是 $M\ll N$
- 像 Gaussian SVM 就只拿 support vectors 當 centers
- 這樣也就是說我 output layer 的 weights 變少了。
- 所以我們現在的目的就是找出好的 **prototypes**。

### Fun Time: Matrix of RBFNet


## [k-Means Algorithm](https://www.coursera.org/learn/machine-learning-techniques/lecture/qhBne/k-means-algorithm)

### Good Prototypes: Clustering Problem

- 不需要同時出現相似的 points
- 所以我們要找一個代表 (prototype) 來表示這些相似的點，而且這個代表到不同點的距離都是很近的，才會做出相似的 RBF function。
- 這裡的 $E_{in}$ 代表同一群裡面的 points 有多不合。
- 現在要最小化這個奇怪的 $E_{in}$

### Partition Optimization

- 這個問題我們又需要做數字(numerical) 的最佳化，又需要做組合(combinatorial) 的最佳化
- 數字：找到實數 $\mu_1,...,\mu_M$
- 組合：每個 $x_n$ 要放到哪個 $S_m$ 裡面
- 兩組 variables 那就輪流最佳化吧
- 先固定 prototypes $\mu$，把每個 data points 指派到離它最近的 prototypes 這樣才會讓上面的 $E_{in}$ 最小。

### Prototype Optimization

- 現在固定分群，要最小化上面那個 $E_{in}$，我們用微分=0，可以推得 $\mu_m$ 就直接算那群的平均即可。

### k-Means Algorithm

- $k$ 對應到剛剛的 $M$。
- 現在只要從原始資料隨機選 $k$ 個 $\mu$，就可以開始 optimize 了
- > Q: 為何說隨機選取才能避免ㄧ些奇怪的局部最佳解???
- 可以保證它會停嗎? 可以，因為每一部輪流都會讓剛剛的 $E_{in}$ 更小，而它最小是 0。

### RBF Network Using k-Means

- (hyper)parameters: $M$(prototypes), RBF
- 實務上較不常見 RBFNet 了。

## [k-Means and RBF Network in Action](https://www.coursera.org/learn/machine-learning-techniques/lecture/zIYUm/k-means-and-rbf-network-in-action)

### Difficulty of k-Means

- 對 initialization 和 $k$ 很敏感

### RBF Network Using k-Means

- $k=2$ 直接爛掉
- cluster 做得不錯的話 RBFNet 就還不錯

### Full RBF Network (Visualization)

- 左邊：full RBFNet + regularization
- 右邊：nearest neighbor
- 不論左邊還是右邊都用上了所有 data，表現都不太好，計算量也很大。

### Summary