# 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值對分類的效果影響很大。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale