# 14 -- Radial Basis Function Network 上節課我們主要介紹了Deep Learning的概念。Deep Learing其實是Neural Networ的延伸，神經元更多，網絡結構更加復雜。深度學習網絡在訓練的過程中最核心的問題就是pre-training和regularization。pre-training中，我們使用denoising autoencoder來對初始化權重進行選擇。denoising autoencoder與統計學中經常用來進行數據處理的PCA算法具有很大的關聯性。這節課我們將介紹Radial Basis Function Network，把之前介紹的adial Basis Function和Neural Network聯系起來。 ### **RBF Network Hypothesis** 之前我們介紹過，在SVM中引入Gaussian Kernel就能在無限多維的特征轉換中得到一條“粗壯”的分界線（或者高維分界平面、分界超平面）。從結果來看，Gaussian SVM其實就是將一些Gaussian函數進行線性組合，而Gaussian函數的中心就位于Support Vectors上，最終得到預測模型。  Gaussian kernel的另一種叫法是Radial Basis Function(RBF) kernel，即徑向基函數。這個名字從何而來？首先，radial表示Gaussian函數計算結果只跟新的點x與中心點的距離有關，與其它無關。basis function就是指Gaussian函數，最終的矩就是由這些basis function線性組合而成。 從另外一個角度來看Gaussian SVM。首先，構造一個函數：  上式中，指數項表示新的點x與之間的距離大小。距離越近，即權重越大，相當于對投的票數更多；而距離越遠，權重越小，相當于對投的票數更少。其物理意義是新的點與的距離遠近決定了與的接近程度。如果距離越近，則對的權重影響越大；如果距離越遠，則對的權重影響越小。那么整體來說，就由所有的SV組成的線性組合而成，不同對應的系數是，最后由sign函數做最后的選擇。這個過程很類型我們之前介紹的aggregation中將所有較好的hypothesis線性組合，不同的有不同的權重。我們把叫做radial hypotheses，Gaussian SVM就是將所有SV對應的radial hypotheses進行線性組合（linear aggregation）。  那么，Radial Basis Function(RBF) Network其實就是上面Gaussian SVM概念的延伸，目的就是找到所有radial hypotheses的linear aggregation，得到更好的網絡模型。 之所以叫作RBF Network是因為它的模型結構類似于我們之前介紹的Neural Network。  Neural Network與RBF Network在輸出層基本是類似的，都是上一層hypotheses的線性組合（linear aggregation）。但是對于隱藏層的各個神經元來說，Neural Network是使用內積（inner-product）加上tanh()函數的方法，而RBF Network是使用距離（distance）加上Gaussian函數的方法。總的來說，RBF Network是Neural Network的一個分支。  至此，RBF Network Hypothesis以及網絡結構可以寫成如下形式：  上式中，表示每個中心點的位置，隱藏層每個神經元對應一個中心點；表示每個RBF的權重，即投票所占比重。 對應到Gaussian SVM上，上式中的RBF就是Gaussian函數。由于是分類問題，上式中的Output就是sign函數。其中，RBF的個數M就等于支持向量的個數SV，就代表每個SV的坐標，而就是在Dual SVM中推導得到的值。那我們學習的目標就是根據已知的RBF和Output，來決定最好的中心點位置和權重系數。  在之前介紹SVM的時候，我們就講過Mercer定理：一個矩陣是Kernel的充分必要條件是它是對稱的且是半正定的，條件比較苛刻。除了Gaussian kernel還有Polynomial kernel等等。Kernel實際上描述了兩個向量之間的相似性，通過轉換到z空間計算內積的方式，來表征二者之間的相似性。而RBF實際上是直接使用x空間的距離來描述了一種相似性，距離越近，相似性越高。因此，kernel和RBF可以看成是兩種衡量相似性（similarity）的方式。本文介紹的Gaussian RBF即為二者的交集。  除了kernel和RBF之外，還有其它衡量相似性的函數。例如神經網絡中的神經元就是衡量輸入和權重之間的相似性。 經過以上分析，我們知道了RBF Network中distance similarity是一個很好的定義特征轉換的方法。除此之外，我們還可以使用其它相似性函數來表征特征轉換，從而得到更好的機器學習模型。 ### **RBF Network Learning** 我們已經介紹了RBF Network的Hypothesis可表示為：  其中表示中心點的位置。的個數M是人為決定的，如果將每個樣本點都作為一個中心點，即M=N，則我們把這種結構稱為full RBF Network。也就是說，對于full RBF Network，每個樣本點都對最終的預測都有影響（uniform influence），影響的程度由距離函數和權重決定。如果每個樣本點的影響力都是相同的，設為1，，那么相當于只根據距離的遠近進行投票。最終將x與所有樣本點的RBF距離線性組合，經過sign函數后，得到最終的預測分類結果。這實際上就是aggregation的過程，考慮并計入所有樣本點的影響力，最后將x與所有樣本點的distance similarity進行線性組合。  full RBF Network的矩可以表示為：  我們來看上式中的Gaussian函數項，當x與樣本點越接近的時候，其高斯函數值越大。由于Gaussian函數曲線性質，越靠近中心點，值越大；偏離中心點，其值會下降得很快。也就是說，在所有N個中心樣本點中，往往只有距離x最近的那個樣本點起到關鍵作用，而其它距離x較遠的樣本點其值很小，基本可以忽略。因此，為了簡化運算，我們可以找到距離x最近的中心樣本點，只用這一個點來代替所有N個點，最后得到的矩也只由該最近的中心點決定。這種模型叫做nearest neighbor model，只考慮距離x最近的那一個“鄰居”。 當然可以對nearest neighbor model進行擴展，如果不是只選擇一個“鄰居”，而是選擇距離x最近的k個“鄰居”，進行uniformly aggregation，得到最終的矩。這種方法通常叫做k近鄰算法（k nearest neighbor）。  k nearest neighbor通常比nearest neighbor model效果更好，計算量上也比full RBF Network要簡單一些。值得一提的是，k nearest neighbor與full RBF Network都是比較“偷懶”的方法。因為它們在訓練模型的時候比較簡單，沒有太多的運算，但是在測試的時候卻要花費更多的力氣，找出最相近的中心點，計算相對復雜一些。 接下來，我們來看一下Full RBF Network有什么樣的優點和好處。考慮一個squared error regression問題，且每個RBF的權重為而不是前面簡化的。目的是計算最優化模型對應的值。該hypothesis可表示為：  很明顯，這是一個簡單的線性回歸問題，每個RBF都可以看成是特征轉換。特征轉換后的向量可表示為：  那么，根據之前線性回歸介紹過的最優化解公式，就能快速地得到的最優解為：  上述解的條件是矩陣是可逆的。 矩陣Z的大小是NxN，是一個方陣。而且，由于Z中每個向量表示該點與其它所有點的RBF distance，所以從形式上來說，Z也是對稱矩陣。如果所有的樣本點都不一樣，則Z一定是可逆的。  根據Z矩陣的這些性質，我們可以對的解進行化簡，得到：  將的解代入矩的計算中，以為例，得到：  結果非常有趣，模型的輸出與原樣本完全相同。同樣，對任意的，都能得到。因此，。看起來，這個模型非常完美了，沒有error。但是，我們之前就說過，機器學習中，并非好事，很可能造成模型復雜度增加及過擬合。  當然，這種方法在某些領域還是很有用的。比如在函數擬合（function approximation）中，目標就是讓，使得原所有樣本都盡可能地落在擬合的函數曲線上。 為了避免發生過擬合，我們可以引入正則項，得到的最優解為：   我們再來看一下Z矩陣，Z矩陣是由一系列Gaussian函數組成，每個Gaussian函數計算的是兩個樣本之間的distance similarity。這里的Z與之前我們介紹的Gaussian SVM中的kernel K是一致的。當時我們得到kernel ridgeregression中線性系數的解為：  比較一下kernel ridgeregression與regularized full RBF Network的解，形式上相似但不完全相同。這是因為regularization不一樣，在kernel ridgeregression中，是對無限多維的特征轉換做regularization，而在regularized full RBF Network中，是對有限維（N維度）的特征轉換做regularization。因此，兩者的公式解有細微差別。  除此之外，還有另外一種regularization的方法，就是不把所有N個樣本點都拿來作中心點，而是只選擇其中的M個樣本點作為中心點。類似于SVM中的SV一樣，只選擇具有代表性的M個中心點。這樣減少中心點數量的同時也就減少了權重的數量，能夠起到regularization的效果，避免發生過擬合。  下一部分，我們將討論如何選取M個中心點作為好的代表。 ### **k-Means Algorithm** 之所以要選擇代表，是因為如果某些樣本點很接近，那么就可以用一個中心點來代表它們。這就是聚類（cluster）的思想，從所有N個樣本點中選擇少數幾個代表作為中心點。  聚類（clustering）問題是一種典型的非監督式學習（unsupervised learning）。它的優化問題有兩個變量需要確定：一個是分類的分群值，每一類可表示為；另外一個是每一類對應的中心點。那么對于該聚類問題的優化，其error function可使用squared error measure來衡量。  那么，我們的目標就是通過選擇最合適的和，使得最小化。對應的公式可表示為：  從這個最小化公式，我們能夠發現這是一個組合最佳化的問題，既要優化分群值，又要求解每一類的中心點。所以，這個最小化問題是比較復雜、難優化的。通常的辦法是對S和分別進行最優化求解。 首先，如果是固定的，目標就是只要對所有的進行分群歸類。這個求解過程很簡單，因為每個樣本點只能屬于一個群S，不能同時屬于兩個或多個群。所以，只要根據距離公式，計算選擇離最近的中心點即可。  然后，如果是固定的，目標就是只要找出每個類的中心點。顯然，根據上式中的error function，所有的分群是已知的，那么該最小化問題就是一個典型的數值最優化問題。對于每個類群，利用梯度下降算法，即可得到的解。  如上圖所示，中心點就等于所有屬于類群的平均位置處。 經過以上的推導，我們得到了一個非常有名的一種unsupervised learning算法，叫做k-Means Algorithm。這里的k就是代表上面的M，表示類群的個數。 k-Means Algorithm的流程是這樣的：首先，隨機選擇k個中心點；然后，再由確定的中心點得到不同的類群；接著，再由確定的類群計算出新的不同的k個中心點；繼續循環迭代計算，交互地對和S值進行最優化計算，不斷更新和S值，直到程序收斂，實現最小化。具體算法流程圖如下所示：  有一個問題是，k-Means Algorithm的循環迭代一定會停止嗎？或者說一定能得到最優解嗎？答案是肯定的。因為每次迭代更新，和S值都會比上一次的值更接近最優解，也就是說是不斷減小的。而的下界是0，所以，最終會等于0，和S最終能得到最優解。 k-Means Algorithm已經介紹完畢。接下來，我們把k-Means Algorithm應用到RBF Network中去。首先，使用k-Means，得到原始樣本的k個中心點。原始樣本到k個中心點組成了RBF特征轉換。然后，根據上面介紹過的線性模型，由最優化公式解計算得到權重值。最后，將所有的用線性組合，即得到矩的表達式。具體的算法流程如下所示：  值得一提的是，這里我們使用了unsupervised learning（k-Means）與我們上節課介紹的autoencoder類似，同樣都是特征轉換（feature transform）的方法。 在最優化求解過程中，參數有k-Means類群個數M、Gaussian函數參數等。我們可以采用validation的方法來選取最佳的參數值。  ### **k-means and RBF Network in Action** 下面這部分，我們將舉幾個例子，看一下k-Means Algorithm是如何處理分類問題的。 第一個例子，平面上有4個類群，k=4。首先，我們隨機選擇4個中心點，如下圖中四種顏色的方塊所示：  第一次迭代，由初始中心點，得到4個類群點的分布：  4個類群點確定后，再更新4個中心點的位置：  第二次迭代，由上面得到的4個中心點，再計算4個類群點的分布：  4個類群點確定后，再更新4個中心點的位置：  第三次迭代，由上面得到的4個中心點，再計算4個類群點的分布：  4個類群點確定后，再更新4個中心點的位置：  第四次迭代，由上面得到的4個中心點，再計算4個類群點的分布：  4個類群點確定后，再更新4個中心點的位置：  第五次迭代，由上面得到的4個中心點，再計算4個類群點的分布：  4個類群點確定后，再更新4個中心點的位置：  第六次迭代，由上面得到的4個中心點，再計算4個類群點的分布：  4個類群點確定后，再更新4個中心點的位置：  從上圖我們可以看到，經過六次迭代計算后，聚類的效果已經相當不錯了。從另外一個角度來說，k值的選擇很重要，下面我們來看看不同的k值對應什么樣的分類效果。  如上圖所示，初始時，我們分別設定k為2，4，7，隨機選擇中心點位置。在經過多次迭代后，得到的聚類結果如下：  通過上面這個例子可以得出，不同的k值會得到不同的聚類效果。還有一點值得注意的是，初始中心點位置也可能會影響最終的聚類。例如上圖中k=7的例子，初始值選取的右邊三個中心點比較靠近，最后得到的右邊三個聚類中心點位置也跟初始位置比較相近。所以，k值大小和初始中心點位置都會影響聚類效果。 接下來，我們把k-Means應用到RBF Network中，同樣分別設定k為2，4，7，不同模型得到的分類效果如下：  很明顯，k=2時，分類效果不是太好；k=4時，分類效果好一些；而k=7時，分類效果更好，能夠更細致地將樣本準確分類。這說明了k-Means中k值設置得是否合理，對RBF Network的分類效果起到重要的作用。 再來看一個例子，如果使用full RBF Network進行分類，即k=N，如下圖左邊所示，設置正則化因子。下圖右邊表示只考慮full RBF Network中的nearest neighbor。下圖中間表示的是k=4的RBF Network的分類效果。  從上圖的比較中，我們可以發現full RBF Network得到的分類線比較彎曲復雜。由于full RBF Network的計算量比較大，所以一般情況下，實際應用得不太多。 ### **總結** 本節課主要介紹了Radial Basis Function Network。RBF Network Hypothesis就是計算樣本之間distance similarity的Gaussian函數，這類原型替代了神經網絡中的神經元。RBF Network的訓練學習過程，其實就是對所有的原型Hypotheses進行linear aggregation。然后，我們介紹了一個確定k個中心點的unsupervised learning算法，叫做k-Means Algorithm。這是一種典型的聚類算法，實現對原始樣本數據的聚類分群。接著，將k-Means Algorithm應用到RBF Network中，選擇合適數量的中心點，得到更好的分類模型。最后，我們列舉了幾個在實際中使用k-Means和RBF Network的例子，結果顯示不同的類群k值對分類的效果影響很大。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程