ML：基礎技法學習
Package：scikit-learn
課程：
機器學習技法
簡介：第十四講 Radial Basis Function Network
RBF Network Hypothesis
$$
h(\mathbf{x})=\mathrm{Output}(\sum_{m=1}^{M}\beta _m\mathrm{RBF}(\mathbf{x},\boldsymbol\mu _m)+b)\\
$$
centers：\(\boldsymbol\mu _m\)，votes：\(\beta _m\)
\(b\) 通常為 0
- radial
- 只跟 \(\mathbf{x}\) 和中心點 \(\boldsymbol\mu_m\) 的距離有關
- basis function
故 Radial Basis Function (RBF) Network 就是 radial hypotheses 的線性組合
而 RBF Network 在歷史上其實只是 NNet 的其中一個分支
如下圖，內積 + tanh (NNet) vs 與中心的距離 + RBF (RBF Network)
$$
g_{SVM}(\mathbf{x})=sign\left (\sum _{SV} \alpha _ny_ne^{(-\gamma \left \| \mathbf{x}-\mathbf{x}_n \right \|^2)+b} \right )
$$
Gaussian kernel 為其中一種 Radial Basis Function (RBF) kernel
所以將 \(g_{SVM}\) 套進 RBF 基本模型，可參考
[ML] 機器學習技法：第三講 Kernel SVM
- RBF：Gaussian
- Output：sign
- M：SV 的數量
- \(\boldsymbol\mu _m\)：SVM SVs \(\mathbf{x}_n\)
- \(\beta _m\)：\(\alpha _ny_n\)
事實上，機器學習一直在對相似性進行處理
- \(Neuron(\mathbf{x}, {\mathbf{x}}') = tanh(\gamma \mathbf{x}^T \mathbf{w}')\)
- NNet：\(\mathbf{w}\) 與 \(\mathbf{x}\) 的相似
- \(DNASim(\mathbf{x}, {\mathbf{x}}') = EditDistance(\mathbf{x}, {\mathbf{x}}')\)
- kernel
- Poly：\(K_Q(\mathbf{x},{\mathbf{x}}')=(\zeta +\gamma \mathbf{x}^T\mathbf{{x}'})^Q\)
- \(Gaussian(\mathbf{x},{\mathbf{x}}')=e^{(-\gamma \left \| \mathbf{x}-{\mathbf{x}}' \right \|^2)}\)
- RBF
- 借由 \(X\) 空間的距離決定相似，越近越大，越遠越小
- \(Gaussian(\mathbf{x},{\mathbf{x}}')=e^{(-\gamma \left \| \mathbf{x}-{\mathbf{x}}' \right \|^2)}\)
- \(Truncated(\mathbf{x},{\mathbf{x}}')=\left [\left \| \mathbf{x}-{\mathbf{x}}' \right \|\le 1 \right ](1-\left \| \mathbf{x}-{\mathbf{x}}' \right \|^2)\)
Regularized Full RBF Network
full RBF Network for ridge regression
\(M=N\)，也就是將所有的訓練點 \(\mathbf{x}\) 皆為中心點 \(\boldsymbol\mu_m = \mathbf{x}_n\)
$$
\begin{align*}
h(\mathbf{x})&=\sum_{m=1}^{N}\beta _m \mathrm{RBF}(\mathbf{x},\mathbf{x}_m)\\
\mathbf{z}_n &= \begin{bmatrix}\mathrm{RBF}(\mathbf{x}_n,\mathbf{x}_1) & \mathrm{RBF}(\mathbf{x}_n,\mathbf{x}_2) & \cdots & \mathrm{RBF}(\mathbf{x}_n,\mathbf{x}_N)\end{bmatrix}^T\\
\mathbf{Z} &=
\begin{bmatrix}
\mathbf{z}_1^T\\
\mathbf{z}_2^T\\
\vdots \\
\mathbf{z}_N^T
\end{bmatrix}\\
\boldsymbol\beta&=(\mathbf{Z}^T\mathbf{Z}+\lambda \mathbf{I})^{-1}\mathbf{Z}^T\mathbf{y}
\end{align*}
$$
$$
h(\mathbf{x})=\mathrm{Output}\left (\sum_{m=1}^{M}\beta _m\mathrm{RBF}(\mathbf{x},\boldsymbol\mu _m) \right )
$$
這邊將 \(b=0\)，且為了偷懶，將所有的訓練點 \(\mathbf{x}\) 都當作中心點 \(\boldsymbol\mu _m\)
所有點都有影響力，決定輸入 \(\mathbf{x}\) 的 \(y\)
先討論一個特殊的情況，假設 \(\beta _m=1\cdot y_m\)，且 RBF 為 Gaussian
$$
g_{uniform}(\mathbf{x})=sign\left ( \sum_{m=1}^{N}y_m e^{-\gamma \left \| \mathbf{x}-\mathbf{x}_m \right \|^2} \right )
$$
這就是一個 uniform 形式的 RBF，取每個點的平均意見
但因為 RBF 是 Gaussian ，通常最靠近的 \(\mathbf{x}_m\) 將決定絕大部分的結果
那麼何不直接挑 \(e^{-\gamma \left \| \mathbf{x}-\mathbf{x}_m \right \|^2}\) 最大值的 \(\mathbf{x}_m\)
$$
g_{nbor}(\mathbf{x})=y_m\ s.t.\ \mathbf{x}\ closest\ to\ \mathbf{x}_m
$$
這也就是 nearest neighbor model
只用一個 \(\mathbf{x}_m\) 決定似乎不保險，那用 k 個呢？k nearest neighbor (KNN)
這是個偷懶的方法，訓練時很簡單，記住 \(\mathbf{x}_m\) 就好，但預測時就得找出最接近的幾個值了
回過頭來，若取 square error
$$
h(\mathbf{x})=\sum_{m=1}^{M}\beta _m\mathrm{RBF}(\mathbf{x},\boldsymbol\mu _m)
$$
先轉換訓練資料 \(\mathbf{x}_n\)
$$
\mathbf{z}_n = \begin{bmatrix}\mathrm{RBF}(\mathbf{x}_n,\mathbf{x}_1) & \mathrm{RBF}(\mathbf{x}_n,\mathbf{x}_2) & \cdots & \mathrm{RBF}(\mathbf{x}_n,\mathbf{x}_N)\end{bmatrix}^T\\
$$
$$
\mathbf{Z} =
\begin{bmatrix}
\mathbf{z}_1^T\\
\mathbf{z}_2^T\\
\vdots \\
\mathbf{z}_N^T
\end{bmatrix}\\
$$
可得
$$
\begin{align*}
E_{in}(\boldsymbol\beta)
&= \frac{1}{N}\left \| \underset{\mathrm{N\times N\ }}{\underbrace{\mathbf{Z}}}\underset{\mathrm{N\times 1}}{\underbrace{\boldsymbol\beta}}-\underset{\mathrm{N\times 1}}{\underbrace{\mathbf{y}}} \right \|^2
\end{align*}
$$
借由
[ML] 機器學習基石：第九講 Linear Regression
可得 \(\boldsymbol\beta=(\mathbf{Z}^T\mathbf{Z})^{-1}\mathbf{Z}^T\mathbf{y}\)
\(\mathbf{Z}\) 為對稱矩陣，且當 \(\mathbf{x}_n\) 都不一樣時，\(\mathbf{Z}\) 必有其 inverse
$$
\begin{align*}
\boldsymbol\beta&=(\mathbf{Z}^T\mathbf{Z})^{-1}\mathbf{Z}^T\mathbf{y} \\
&= (\mathbf{Z}\mathbf{Z})^{-1}\mathbf{Z}\mathbf{y}\\
&= \mathbf{Z}^{-1}\mathbf{Z}^{-1}\mathbf{Z}\mathbf{y}\\
&= \mathbf{Z}^{-1}\mathbf{y}\\
\end{align*}
$$
將其代入 \(E_{in}\)
$$
\begin{align*}
E_{in}(\boldsymbol\beta)
&= \frac{1}{N}\left \| \mathbf{Z}\boldsymbol\beta-\mathbf{y} \right \|^2\\
&=\frac{1}{N}\left \| \mathbf{Z}\mathbf{Z}^{-1}\mathbf{y}-\mathbf{y} \right \|^2\\
&=\frac{1}{N}\left \| \mathbf{y}-\mathbf{y} \right \|^2\\
&=0
\end{align*}
$$
看起來很完美，但記得，對於 Machine learning 這將造成 overfitting
所以加入 ridge regression 也就是 regularization 為 L2
$$
\begin{align*}
\underset{\boldsymbol\beta}{min}\ \ E_{in}(\boldsymbol\beta) &= \underset{\boldsymbol\beta}{min}\ \ E_{in}(\boldsymbol\beta) + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta\\
&= \underset{\boldsymbol\beta}{min}\ \ \frac{1}{N}\left \| \mathbf{Z}\boldsymbol\beta-\mathbf{y}\right \|^2 + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta\\
\end{align*}
$$
借由
矩陣微分
$$
\begin{align*}
\triangledown E_{in}(\boldsymbol\beta)
&= \frac{\partial }{\partial \boldsymbol\beta}\left (\frac{1}{N}\left \| \mathbf{Z}\boldsymbol\beta-\mathbf{y}\right \|^2 + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta \right )\\
&= \frac{\partial }{\partial \boldsymbol\beta}\left (\frac{1}{N}( \mathbf{Z}\boldsymbol\beta-\mathbf{y})^T( \mathbf{Z}\boldsymbol\beta-\mathbf{y}) + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta \right )\\
&= \frac{\partial }{\partial \boldsymbol\beta}\left (\frac{1}{N}( \boldsymbol\beta^T\mathbf{Z}^T-\mathbf{y}^T)( \mathbf{Z}\boldsymbol\beta-\mathbf{y}) + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta \right )\\
&= \frac{\partial }{\partial \boldsymbol\beta}\left (\frac{1}{N}( \boldsymbol\beta^T\mathbf{Z}^T\mathbf{Z}\boldsymbol\beta -\boldsymbol\beta^T\mathbf{Z}^T\mathbf{y}-\mathbf{y}^T\mathbf{Z}\boldsymbol\beta+\mathbf{y}^T\mathbf{y}) + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta \right )\\
&= \frac{\partial }{\partial \boldsymbol\beta}\left (\frac{1}{N}( \boldsymbol\beta^T\mathbf{Z}^T\mathbf{Z}\boldsymbol\beta -2\boldsymbol\beta^T\mathbf{Z}^T\mathbf{y}+\mathbf{y}^T\mathbf{y}) + \frac{\lambda}{N}\boldsymbol\beta^T\boldsymbol\beta \right )\\
&=\frac{1}{N}\left ( 2\mathbf{Z}^T\mathbf{Z}\boldsymbol\beta-2\mathbf{Z}^T\mathbf{y}\right ) + \frac{2\lambda}{N}\boldsymbol\beta\\
&=\frac{2}{N}\mathbf{Z}^T\mathbf{Z}\boldsymbol\beta-\frac{2}{N}\mathbf{Z}^T\mathbf{y} + \frac{2\lambda}{N}\boldsymbol\beta\\
&=\frac{2}{N}\mathbf{Z}^T\mathbf{Z}\boldsymbol\beta+\frac{2\lambda}{N}\boldsymbol\beta-\frac{2}{N}\mathbf{Z}^T\mathbf{y}\\
&=\frac{2}{N}(\mathbf{Z}^T\mathbf{Z}+\lambda \mathbf{I})\boldsymbol\beta-\frac{2}{N}\mathbf{Z}^T\mathbf{y}\\
\end{align*}
$$
區域最佳解，微分等於 0，故
$$
\begin{align*}
\triangledown E_{in}(\boldsymbol\beta) &=\frac{2}{N}(\mathbf{Z}^T\mathbf{Z}+\lambda \mathbf{I})\boldsymbol\beta-\frac{2}{N}\mathbf{Z}^T\mathbf{y} =0\\
\frac{2}{N}(\mathbf{Z}^T\mathbf{Z}+\lambda \mathbf{I})\boldsymbol\beta &=\frac{2}{N}\mathbf{Z}^T\mathbf{y}\\
(\mathbf{Z}^T\mathbf{Z}+\lambda \mathbf{I})\boldsymbol\beta &=\mathbf{Z}^T\mathbf{y}\\
\boldsymbol\beta &=(\mathbf{Z}^T\mathbf{Z}+\lambda \mathbf{I})^{-1}\mathbf{Z}^T\mathbf{y}\\
\end{align*}
$$
這個解與 KRR 的解 \(\boldsymbol\beta =(K+\lambda \mathbf{I})^{-1}\mathbf{y}\) 極度相似
可參考
[ML] 機器學習技法：第六講 Support Vector Regression (SVR)
事實上 \(\mathbf{Z} = [Gaussian(\mathbf{x}_n, \mathbf{x}_m)] = Gaussian\ kernel\ matrix\ \mathbf{K}\)
兩者差異的原因在於 regularization 針對 \(\boldsymbol\beta\) 的維度不同
KRR 是在無限維度上處理，而 regularized full RBFNet 是在有限維度上處理的
無限維度的原因，可參考
[ML] 機器學習技法：第三講 Kernel SVM
全部的點都拿來當中心點，容易 overfitting，且計算量又太大
適當的只選擇其中的點做為代表，像是 SVM 的 support vectors
並且限制 \(\boldsymbol\beta\) 的大小，才會更加準確
k-Means Algorithm
- 初始化 \(\boldsymbol\mu_1,\boldsymbol\mu_2,\cdots ,\boldsymbol\mu_k\)
- 隨機從 \(\mathbf{x}_n\) 挑選出 k 個， k 用 validation 決定
- 交替優化 \(E_{in}\)，直到 \(S_1,S_2,\cdots ,S_k\) 不再有改變
- 最佳化 \(S_1,S_2,\cdots ,S_k\)
將每個 \(\mathbf{x}_n\) 都個別分類至最近的 \(\boldsymbol\mu_n\)
- 最佳化 \(\boldsymbol\mu_1,\boldsymbol\mu_2,\cdots ,\boldsymbol\mu_k\)
從分完類的 \(S_n\) 計算出 \(\boldsymbol\mu_n\)
此為 unsupervised learning，且非常受歡迎
希望將 \(\mathbf{x}_n\) 分群 M 個，並從其中選出代表
$$
E_{in}(S_1,\cdots ,S_M;\boldsymbol\mu_1,\cdots ,\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_m \right \|^2\\
\underset{\{S_1,\cdots ,S_M;\boldsymbol\mu_1,\cdots ,\boldsymbol\mu_M\}}{min} E_{in}(S_1,\cdots ,S_M;\boldsymbol\mu_1,\cdots ,\boldsymbol\mu_M)
$$
這個最佳化很困難，因為同時具有數值的最佳化 \(\mu_m\)，還需分群的最佳化 \(S_m\)
數值的最佳化需要的是微分，但分群的最佳化需要的是所有的排列組合找出最好的
那是否可以個別最佳化呢？
假設 \(\boldsymbol\mu_1,\cdots ,\boldsymbol\mu_M\) 固定
那麼只需要決定 \(S_1,\cdots ,S_M\)，怎麼決定 \(\mathbf{x}_n\) 屬於哪個群呢？
很簡單，\(\mathbf{x}_n\) 離哪個 \(\boldsymbol\mu_m\) 最近，就是屬於那個 \(S_m\)
再來 \(S_1,\cdots ,S_M\) 固定
$$
\begin{align*}
\triangledown_{\boldsymbol\mu_m} E_{in}&=\frac{\partial }{\partial \boldsymbol\mu_m} \left (\frac{1}{N}\sum_{n=1}^{N}\sum_{m=1}^{M}[\mathbf{x}_n \in S_m]\left \| \mathbf{x}_n-\boldsymbol\mu_m \right \|^2 \right )\\
&= \frac{-2}{N}\sum_{n=1}^{N}[\mathbf{x}_n \in S_m](\mathbf{x}_n-\boldsymbol\mu_m )\\
&= \frac{-2}{N}\left (\sum_{n=1}^{N}[\mathbf{x}_n \in S_m]\mathbf{x}_n-\sum_{n=1}^{N}[\mathbf{x}_n \in S_m]\boldsymbol\mu_m \right ) \\
&= \frac{-2}{N}\left (\sum_{\mathbf{x}_n \in S_m}\mathbf{x}_n-| S_m|\boldsymbol\mu_m \right ) \\
\\
\triangledown_{\boldsymbol\mu_m} E_{in}&=\frac{-2}{N}\left (\sum_{\mathbf{x}_n \in S_m}\mathbf{x}_n-|S_m|\boldsymbol\mu_m \right )=0\\
\sum_{\mathbf{x}_n \in S_m}\mathbf{x}_n&=|S_m|\boldsymbol\mu_m\\
\boldsymbol\mu_m&=\frac{\sum_{\mathbf{x}_n \in S_m}\mathbf{x}_n}{|S_m|}
\end{align*}
$$
\(|S_m|\) 為集合共有幾個 \(\mathbf{x}_n\)，所以 \(\boldsymbol\mu_m\) 其實就是 \(S_m\) 的平均
因為在過程中，\(E_{in}\) 是逐漸往下的，而 \(E_{in}\) 的下限為 0，故確定會收斂
歷史上，最先是用 k，所以將 M 改為 k
此為 unsupervised learning，因跟 \(y_n\) 無關
對 k 與初始值非常敏感，需特別注意
RBF Network Using k-Means
- 執行 k-Means，將 k=M 得到 \(\left \{ \boldsymbol\mu_m \right \}\)
- 建立 \(\Phi (\mathbf{x})\) ，利用 RBF(例：Gaussian) 和 \(\boldsymbol\mu_m\)
$$
\Phi (\mathbf{x}) = \begin{bmatrix}\mathrm{RBF}(\mathbf{x},\boldsymbol\mu_1) & \mathrm{RBF}(\mathbf{x},\boldsymbol\mu_2) & \cdots & \mathrm{RBF}(\mathbf{x},\boldsymbol\mu_M)\end{bmatrix}^T
$$
- 建立 linear mode \(\{ \Phi (\mathbf{x}_n),y_n \}\) 得到 \(\boldsymbol\beta\)
- 回傳 \(g_{RBFNET}(\mathbf{x})=LinearHypothesis(\boldsymbol\beta,\Phi (\mathbf{x}))\)
需適當的選擇中心點的數目，不然可能會像第一張圖，都認為是叉叉
比較，但因為 Full RBF Network 以及 nearest neighbor 計算複雜，實務上並不常用
實務上並不常用 RBF Network，因與 Gaussian SVM or NNet 的表現差不多，但仍不失為一個好的想法
程式碼
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
plt.figure(figsize=(8, 8))
# 用来正常顯示中文標簽
plt.rcParams['font.sans-serif']=['SimHei']
# 用来正常顯示負號
plt.rcParams['axes.unicode_minus']=False
n_samples = 1500
random_state = 170
# 產生 1500 筆資料，共有三群
X, y = make_blobs(n_samples=n_samples, random_state=random_state)
# 不正確的群數
y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
plt.subplot(221)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.title("Incorrect Number of Blobs (錯誤的 k)")
# Anisotropically distributed data
# 非同方向縮放一致的分佈
transformation = [[0.60834549, -0.63667341], [-0.40887718, 0.85253229]]
X_aniso = np.dot(X, transformation)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)
plt.subplot(222)
plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
plt.title("Anisotropically Distributed Blobs (非等比例分佈)")
# 不同標準差
X_varied, y_varied = make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state)
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
plt.subplot(223)
plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
plt.title("Unequal Variance (不同標準差)")
# Unevenly sized blobs
# >>> a = np.array([1, 2, 3])
# >>> b = np.array([2, 3, 4])
# >>> np.vstack((a,b))
# array([[1, 2, 3],
# [2, 3, 4]])
# vstack 在第二個維度堆疊
X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))
y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_filtered)
plt.subplot(224)
plt.scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)
plt.title("Unevenly Sized Blobs (數量不同)")
plt.show()
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.metrics import pairwise_distances_argmin
from sklearn.datasets import load_sample_image
from sklearn.utils import shuffle
from time import time
# 壓縮為 64 個顏色
n_colors = 64
# 讀取照片
china = load_sample_image("china.jpg")
# 轉換為浮點數，範圍為 [0-1]
china = np.array(china, dtype=np.float64) / 255
# 讀取長寬與一個 pixel 的顏色數目
w, h, d = original_shape = tuple(china.shape)
assert d == 3
# 轉成 array
image_array = np.reshape(china, (w * h, d))
print("用原圖的小部分當樣本訓練 model")
t0 = time()
image_array_sample = shuffle(image_array, random_state=0)[:1000]
kmeans = KMeans(init='random', n_clusters=n_colors, random_state=0).fit(image_array_sample)
print("done in %0.3fs." % (time() - t0))
# 處理整張圖
print("在整張圖上預測顏色")
t0 = time()
# 預測，只會回傳中心點對應的 index
labels = kmeans.predict(image_array)
print("done in %0.3fs." % (time() - t0))
# 處理整張圖，但從原圖隨機挑出顏色
codebook_random = shuffle(image_array, random_state=0)[:n_colors + 1]
print("在整張圖上預測顏色 (隨機版)")
t0 = time()
# 挑選出 X 最接近 Y 的顏色，並送出 Y 的 index
labels_random = pairwise_distances_argmin(X=image_array, Y=codebook_random)
print("done in %0.3fs." % (time() - t0))
def recreate_image(codebook, labels, w, h):
"""用 codebook 和 labels 重新建立圖"""
d = codebook.shape[1]
image = np.zeros((w, h, d))
label_idx = 0
for i in range(w):
for j in range(h):
image[i][j] = codebook[labels[label_idx]]
label_idx += 1
return image
# 畫圖
# 用来正常顯示中文標簽
plt.rcParams['font.sans-serif']=['SimHei']
fig, axes = plt.subplots(1, 3)
axes[0].xaxis.set_visible(False)
axes[0].yaxis.set_visible(False)
axes[0].set_title('原始圖 (96,615 colors)')
axes[0].imshow(china)
axes[1].xaxis.set_visible(False)
axes[1].yaxis.set_visible(False)
axes[1].set_title('壓縮圖 (64 colors, K-Means)')
axes[1].imshow(recreate_image(kmeans.cluster_centers_, labels, w, h))
axes[2].xaxis.set_visible(False)
axes[2].yaxis.set_visible(False)
axes[2].set_title('壓縮圖 (64 colors, Random)')
axes[2].imshow(recreate_image(codebook_random, labels_random, w, h))
plt.show()
參考
sklearn.cluster.KMeans
$$
h(\mathbf{x})=\mathrm{Output}(\sum_{m=1}^{M}\beta _m\mathrm{RBF}(\mathbf{x},\boldsymbol\mu _m)+b)\\
$$
centers：\(\boldsymbol\mu _m\)，votes：\(\beta _m\)
比較，但因為 Full RBF Network 以及 nearest neighbor 計算複雜，實務上並不常用
實務上並不常用 RBF Network，因與 Gaussian SVM or NNet 的表現差不多，但仍不失為一個好的想法
留言
張貼留言