[ML] 機器學習技法:第十四講 Radial Basis Function Network

ML:基礎技法學習
Package:scikit-learn
課程:機器學習技法
簡介:第十四講 Radial Basis Function Network

RBF Network Hypothesis

h(x)=Output(m=1MβmRBF(x,μm)+b) centers:μm,votes:βm
b 通常為 0
  • radial
    • 只跟 x 和中心點 μm 的距離有關
  • basis function
    • 拿來做線性組合的基本 function
故 Radial Basis Function (RBF) Network 就是 radial hypotheses 的線性組合

而 RBF Network 在歷史上其實只是 NNet 的其中一個分支
如下圖,內積 + tanh (NNet) vs 與中心的距離 + RBF (RBF Network)
gSVM(x)=sign(SVαnyne(γxxn2)+b) Gaussian kernel 為其中一種 Radial Basis Function (RBF) kernel
所以將 gSVM 套進 RBF 基本模型,可參考 [ML] 機器學習技法:第三講 Kernel SVM
  • RBF:Gaussian 
  • Output:sign
  • M:SV 的數量
  • μm:SVM SVs xn
  • βmαnyn
事實上,機器學習一直在對相似性進行處理
  • Neuron(x,x)=tanh(γxTw)
    • NNet:wx 的相似
  • DNASim(x,x)=EditDistance(x,x)
    • 使兩個 DNA 字串相同,最少修改的步驟
  • kernel
    • Poly:KQ(x,x)=(ζ+γxTx)Q
    • Gaussian(x,x)=e(γxx2)
      • 同時符合 kernel & RBF 
  • RBF
    • 借由 X 空間的距離決定相似,越近越大,越遠越小
    • Gaussian(x,x)=e(γxx2)
      • 同時符合 kernel & RBF
    • Truncated(x,x)=[xx1](1xx2)

Regularized Full RBF Network

full RBF Network for ridge regression
M=N,也就是將所有的訓練點 x 皆為中心點 μm=xn
h(x)=m=1NβmRBF(x,xm)zn=[RBF(xn,x1)RBF(xn,x2)RBF(xn,xN)]TZ=[z1Tz2TzNT]β=(ZTZ+λI)1ZTy
h(x)=Output(m=1MβmRBF(x,μm)) 這邊將 b=0,且為了偷懶,將所有的訓練點 x 都當作中心點 μm
所有點都有影響力,決定輸入 xy

先討論一個特殊的情況,假設 βm=1ym,且 RBF 為 Gaussian
guniform(x)=sign(m=1Nymeγxxm2) 這就是一個 uniform 形式的 RBF,取每個點的平均意見
但因為 RBF 是 Gaussian ,通常最靠近的 xm 將決定絕大部分的結果
那麼何不直接挑 eγxxm2 最大值的 xm
gnbor(x)=ym s.t. x closest to xm 這也就是 nearest neighbor model
只用一個 xm 決定似乎不保險,那用 k 個呢?k nearest neighbor (KNN)
這是個偷懶的方法,訓練時很簡單,記住 xm 就好,但預測時就得找出最接近的幾個值了

回過頭來,若取 square error
h(x)=m=1MβmRBF(x,μm) 先轉換訓練資料 xn zn=[RBF(xn,x1)RBF(xn,x2)RBF(xn,xN)]T Z=[z1Tz2TzNT] 可得
Ein(β)=1NZN×N βN×1yN×12 借由 [ML] 機器學習基石:第九講 Linear Regression
可得 β=(ZTZ)1ZTy
Z 為對稱矩陣,且當 xn 都不一樣時,Z 必有其 inverse
β=(ZTZ)1ZTy=(ZZ)1Zy=Z1Z1Zy=Z1y 將其代入 Ein
Ein(β)=1NZβy2=1NZZ1yy2=1Nyy2=0 看起來很完美,但記得,對於 Machine learning 這將造成 overfitting

所以加入 ridge regression 也就是 regularization 為 L2
minβ  Ein(β)=minβ  Ein(β)+λNβTβ=minβ  1NZβy2+λNβTβ 借由矩陣微分
Ein(β)=β(1NZβy2+λNβTβ)=β(1N(Zβy)T(Zβy)+λNβTβ)=β(1N(βTZTyT)(Zβy)+λNβTβ)=β(1N(βTZTZββTZTyyTZβ+yTy)+λNβTβ)=β(1N(βTZTZβ2βTZTy+yTy)+λNβTβ)=1N(2ZTZβ2ZTy)+2λNβ=2NZTZβ2NZTy+2λNβ=2NZTZβ+2λNβ2NZTy=2N(ZTZ+λI)β2NZTy 區域最佳解,微分等於 0,故
Ein(β)=2N(ZTZ+λI)β2NZTy=02N(ZTZ+λI)β=2NZTy(ZTZ+λI)β=ZTyβ=(ZTZ+λI)1ZTy 這個解與 KRR 的解 β=(K+λI)1y 極度相似
可參考 [ML] 機器學習技法:第六講 Support Vector Regression (SVR)
事實上 Z=[Gaussian(xn,xm)]=Gaussian kernel matrix K
兩者差異的原因在於 regularization 針對 β 的維度不同
KRR 是在無限維度上處理,而 regularized full RBFNet 是在有限維度上處理的
無限維度的原因,可參考 [ML] 機器學習技法:第三講 Kernel SVM
全部的點都拿來當中心點,容易 overfitting,且計算量又太大
適當的只選擇其中的點做為代表,像是 SVM 的 support vectors
並且限制 β 的大小,才會更加準確

k-Means Algorithm

  1. 初始化 μ1,μ2,,μk
    • 隨機從 xn 挑選出 k 個, k 用 validation 決定
  2. 交替優化 Ein,直到 S1,S2,,Sk 不再有改變
    1. 最佳化 S1,S2,,Sk
      將每個 xn 都個別分類至最近的 μn
    2. 最佳化 μ1,μ2,,μk
      從分完類的 Sn 計算出 μn
此為 unsupervised learning,且非常受歡迎
希望將 xn 分群 M 個,並從其中選出代表
Ein(S1,,SM;μ1,,μM)=1Nn=1Nm=1M[xnSm]xnμm2min{S1,,SM;μ1,,μM}Ein(S1,,SM;μ1,,μM) 這個最佳化很困難,因為同時具有數值的最佳化 μm,還需分群的最佳化 Sm
數值的最佳化需要的是微分,但分群的最佳化需要的是所有的排列組合找出最好的
那是否可以個別最佳化呢?
假設 μ1,,μM 固定
那麼只需要決定 S1,,SM,怎麼決定 xn 屬於哪個群呢?
很簡單,xn 離哪個 μm 最近,就是屬於那個 Sm
再來 S1,,SM 固定
μmEin=μm(1Nn=1Nm=1M[xnSm]xnμm2)=2Nn=1N[xnSm](xnμm)=2N(n=1N[xnSm]xnn=1N[xnSm]μm)=2N(xnSmxn|Sm|μm)μmEin=2N(xnSmxn|Sm|μm)=0xnSmxn=|Sm|μmμm=xnSmxn|Sm| |Sm| 為集合共有幾個 xn,所以 μm 其實就是 Sm 的平均
因為在過程中,Ein 是逐漸往下的,而 Ein 的下限為 0,故確定會收斂
歷史上,最先是用 k,所以將 M 改為 k
此為 unsupervised learning,因跟 yn 無關
對 k 與初始值非常敏感,需特別注意

RBF Network Using k-Means

  1. 執行 k-Means,將 k=M 得到 {μm} 
  2. 建立 Φ(x) ,利用 RBF(例:Gaussian) 和 μm
    Φ(x)=[RBF(x,μ1)RBF(x,μ2)RBF(x,μM)]T
  3. 建立 linear mode {Φ(xn),yn} 得到 β
  4. 回傳 gRBFNET(x)=LinearHypothesis(β,Φ(x))
需適當的選擇中心點的數目,不然可能會像第一張圖,都認為是叉叉
比較,但因為 Full RBF Network 以及 nearest neighbor 計算複雜,實務上並不常用
實務上並不常用 RBF Network,因與 Gaussian SVM or NNet 的表現差不多,但仍不失為一個好的想法

程式碼

k-Means 不見得適用所有情況,視情況需使用 Autoencoder
可參考 [ML] 機器學習技法:第十三講 Deep Learning
  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3.  
  4. from sklearn.cluster import KMeans
  5. from sklearn.datasets import make_blobs
  6.  
  7. plt.figure(figsize=(8, 8))
  8. # 用来正常顯示中文標簽
  9. plt.rcParams['font.sans-serif']=['SimHei']
  10. # 用来正常顯示負號
  11. plt.rcParams['axes.unicode_minus']=False
  12.  
  13. n_samples = 1500
  14. random_state = 170
  15. # 產生 1500 筆資料,共有三群
  16. X, y = make_blobs(n_samples=n_samples, random_state=random_state)
  17.  
  18. # 不正確的群數
  19. y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
  20.  
  21. plt.subplot(221)
  22. plt.scatter(X[:, 0], X[:, 1], c=y_pred)
  23. plt.title("Incorrect Number of Blobs (錯誤的 k)")
  24.  
  25. # Anisotropically distributed data
  26. # 非同方向縮放一致的分佈
  27. transformation = [[0.60834549, -0.63667341], [-0.40887718, 0.85253229]]
  28. X_aniso = np.dot(X, transformation)
  29. y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)
  30.  
  31. plt.subplot(222)
  32. plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
  33. plt.title("Anisotropically Distributed Blobs (非等比例分佈)")
  34.  
  35. # 不同標準差
  36. X_varied, y_varied = make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state)
  37. y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
  38.  
  39. plt.subplot(223)
  40. plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
  41. plt.title("Unequal Variance (不同標準差)")
  42.  
  43. # Unevenly sized blobs
  44. # >>> a = np.array([1, 2, 3])
  45. # >>> b = np.array([2, 3, 4])
  46. # >>> np.vstack((a,b))
  47. # array([[1, 2, 3],
  48. # [2, 3, 4]])
  49. # vstack 在第二個維度堆疊
  50. X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))
  51. y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_filtered)
  52.  
  53. plt.subplot(224)
  54. plt.scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)
  55. plt.title("Unevenly Sized Blobs (數量不同)")
  56.  
  57. plt.show()
k-Means 壓縮圖片
  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3. from sklearn.cluster import KMeans
  4. from sklearn.metrics import pairwise_distances_argmin
  5. from sklearn.datasets import load_sample_image
  6. from sklearn.utils import shuffle
  7. from time import time
  8.  
  9. # 壓縮為 64 個顏色
  10. n_colors = 64
  11.  
  12. # 讀取照片
  13. china = load_sample_image("china.jpg")
  14.  
  15. # 轉換為浮點數,範圍為 [0-1]
  16. china = np.array(china, dtype=np.float64) / 255
  17.  
  18. # 讀取長寬與一個 pixel 的顏色數目
  19. w, h, d = original_shape = tuple(china.shape)
  20. assert d == 3
  21. # 轉成 array
  22. image_array = np.reshape(china, (w * h, d))
  23.  
  24. print("用原圖的小部分當樣本訓練 model")
  25. t0 = time()
  26. image_array_sample = shuffle(image_array, random_state=0)[:1000]
  27. kmeans = KMeans(init='random', n_clusters=n_colors, random_state=0).fit(image_array_sample)
  28. print("done in %0.3fs." % (time() - t0))
  29.  
  30. # 處理整張圖
  31. print("在整張圖上預測顏色")
  32. t0 = time()
  33. # 預測,只會回傳中心點對應的 index
  34. labels = kmeans.predict(image_array)
  35. print("done in %0.3fs." % (time() - t0))
  36.  
  37. # 處理整張圖,但從原圖隨機挑出顏色
  38. codebook_random = shuffle(image_array, random_state=0)[:n_colors + 1]
  39. print("在整張圖上預測顏色 (隨機版)")
  40. t0 = time()
  41. # 挑選出 X 最接近 Y 的顏色,並送出 Y 的 index
  42. labels_random = pairwise_distances_argmin(X=image_array, Y=codebook_random)
  43. print("done in %0.3fs." % (time() - t0))
  44.  
  45. def recreate_image(codebook, labels, w, h):
  46. """用 codebook 和 labels 重新建立圖"""
  47. d = codebook.shape[1]
  48. image = np.zeros((w, h, d))
  49. label_idx = 0
  50. for i in range(w):
  51. for j in range(h):
  52. image[i][j] = codebook[labels[label_idx]]
  53. label_idx += 1
  54. return image
  55.  
  56. # 畫圖
  57. # 用来正常顯示中文標簽
  58. plt.rcParams['font.sans-serif']=['SimHei']
  59. fig, axes = plt.subplots(1, 3)
  60.  
  61. axes[0].xaxis.set_visible(False)
  62. axes[0].yaxis.set_visible(False)
  63. axes[0].set_title('原始圖 (96,615 colors)')
  64. axes[0].imshow(china)
  65.  
  66. axes[1].xaxis.set_visible(False)
  67. axes[1].yaxis.set_visible(False)
  68. axes[1].set_title('壓縮圖 (64 colors, K-Means)')
  69. axes[1].imshow(recreate_image(kmeans.cluster_centers_, labels, w, h))
  70.  
  71. axes[2].xaxis.set_visible(False)
  72. axes[2].yaxis.set_visible(False)
  73. axes[2].set_title('壓縮圖 (64 colors, Random)')
  74. axes[2].imshow(recreate_image(codebook_random, labels_random, w, h))
  75.  
  76. plt.show()

參考

sklearn.cluster.KMeans

留言