# 12 -- Nonlinear Transformation
上一節課,我們介紹了分類問題的三種線性模型,可以用來解決binary classification和multiclass classification問題。本節課主要介紹非線性的模型來解決分類問題。
### **一、Quadratic Hypothesis**
之前介紹的線性模型,在2D平面上是一條直線,在3D空間中是一個平面。數學上,我們用線性得分函數s來表示:。其中,x為特征值向量,w為權重,s是線性的。

線性模型的優點就是,它的VC Dimension比較小,保證了。但是缺點也很明顯,對某些非線性問題,可能會造成很大,雖然,但是也造成很大,分類效果不佳。

為了解決線性模型的缺點,我們可以使用非線性模型來進行分類。例如數據集D不是線性可分的,而是圓形可分的,圓形內部是正類,外面是負類。假設它的hypotheses可以寫成:
基于這種非線性思想,我們之前討論的PLA、Regression問題都可以有非線性的形式進行求解。

下面介紹如何設計這些非線性模型的演算法。還是上面介紹的平面圓形分類例子,它的h(x)的權重w0=0.6,w1=-1,w2=-1,但是h(x)的特征不是線性模型的,而是。我們令,,,那么,h(x)變成:
這種的轉換可以看成是x空間的點映射到z空間中去,而在z域中,可以用一條直線進行分類,也就是從x空間的圓形可分映射到z空間的線性可分。z域中的直線對應于x域中的圓形。因此,我們把這個過程稱之為特征轉換(Feature Transform)。通過這種特征轉換,可以將非線性模型轉換為另一個域中的線性模型。

已知x域中圓形可分在z域中是線性可分的,那么反過來,如果在z域中線性可分,是否在x域中一定是圓形可分的呢?答案是否定的。由于權重向量w取值不同,x域中的hypothesis可能是圓形、橢圓、雙曲線等等多種情況。

目前討論的x域中的圓形都是圓心過原點的,對于圓心不過原點的一般情況,映射公式包含的所有項為:
也就是說,對于二次hypothesis,它包含二次項、一次項和常數項1,z域中每一條線對應x域中的某二次曲線的分類方式,也許是圓,也許是橢圓,也許是雙曲線等等。那么z域中的hypothesis可以寫成:

### **二、Nonlinear Transform**
上一部分我們定義了什么了二次hypothesis,那么這部分將介紹如何設計一個好的二次hypothesis來達到良好的分類效果。那么目標就是在z域中設計一個最佳的分類線。

其實,做法很簡單,利用映射變換的思想,通過映射關系,把x域中的最高階二次的多項式轉換為z域中的一次向量,也就是從quardratic hypothesis轉換成了perceptrons問題。用z值代替x多項式,其中向量z的個數與x域中x多項式的個數一致(包含常數項)。這樣就可以在z域中利用線性分類模型進行分類訓練。訓練好的線性模型之后,再將z替換為x的多項式就可以了。具體過程如下:

整個過程就是通過映射關系,換個空間去做線性分類,重點包括兩個:
* 特征轉換
* 訓練線性模型
其實,我們以前處理機器學習問題的時候,已經做過類似的特征變換了。比如數字識別問題,我們從原始的像素值特征轉換為一些實際的concrete特征,比如密度、對稱性等等,這也用到了feature transform的思想。

### **三、Price of Nonlinear Transform**
若x特征維度是d維的,也就是包含d個特征,那么二次多項式個數,即z域特征維度是:
如果x特征維度是2維的,即,那么它的二次多項式為,有6個。
現在,如果階數更高,假設階數為Q,那么對于x特征維度是d維的,它的z域特征維度為:
由上式可以看出,計算z域特征維度個數的時間復雜度是Q的d次方,隨著Q和d的增大,計算量會變得很大。同時,空間復雜度也大。也就是說,這種特征變換的一個代價是計算的時間、空間復雜度都比較大。

另一方面,z域中特征個數隨著Q和d增加變得很大,同時權重w也會增大,即自由度增加,VC Dimension增大。令z域中的特征維度是,則在在域中,任何的輸入都不能被shattered;同樣,在x域中,任何的輸入也不能被shattered。是VC Dimension的上界,如果很大的時候,相應的VC Dimension就會很大。根據之前章節課程的討論,VC Dimension過大,模型的泛化能力會比較差。

下面通過一個例子來解釋為什么VC Dimension過大,會造成不好的分類效果:

上圖中,左邊是用直線進行線性分類,有部分點分類錯誤;右邊是用四次曲線進行非線性分類,所有點都分類正確,那么哪一個分類效果好呢?單從平面上這些訓練數據來看,四次曲線的分類效果更好,但是四次曲線模型很容易帶來過擬合的問題,雖然它的比較小,從泛化能力上來說,還是左邊的分類器更好一些。也就是說VC Dimension過大會帶來過擬合問題,不能太大了。
那么如何選擇合適的Q,來保證不會出現過擬合問題,使模型的泛化能力強呢?一般情況下,為了盡量減少特征自由度,我們會根據訓練樣本的分布情況,人為地減少、省略一些項。但是,這種人為地刪減特征會帶來一些“自我分析”代價,雖然對訓練樣本分類效果好,但是對訓練樣本外的樣本,不一定效果好。所以,一般情況下,還是要保存所有的多項式特征,避免對訓練樣本的人為選擇。

### **四、Structured Hypothesis Sets**
下面,我們討論一下從x域到z域的多項式變換。首先,如果特征維度只有1維的話,那么變換多項式只有常數項:
如果特征維度是兩維的,變換多項式包含了一維的:
如果特征維度是三維的,變換多項式包含了二維的:
以此類推,如果特征維度是Q次,那么它的變換多項式為:
那么對于不同階次構成的hypothesis有如下關系:
我們把這種結構叫做Structured Hypothesis Sets:

那么對于這種Structured Hypothesis Sets,它們的VC Dimension滿足下列關系:
它的滿足下列關系:

從上圖中也可以看到,隨著變換多項式的階數增大,雖然逐漸減小,但是model complexity會逐漸增大,造成很大,所以階數不能太高。
那么,如果選擇的階數很大,確實能使接近于0,但是泛化能力通常很差,我們把這種情況叫做tempting sin。所以,一般最合適的做法是先從低階開始,如先選擇一階hypothesis,看看是否很小,如果足夠小的話就選擇一階,如果大的話,再逐漸增加階數,直到滿足要求為止。也就是說,盡量選擇低階的hypothes,這樣才能得到較強的泛化能力。

### **五、總結**
這節課主要介紹了非線性分類模型,通過非線性變換,將非線性模型映射到另一個空間,轉換為線性模型,再來進行線性分類。本節課完整介紹了非線性變換的整體流程,以及非線性變換可能會帶來的一些問題:時間復雜度和空間復雜度的增加。最后介紹了在要付出代價的情況下,使用非線性變換的最安全的做法,盡可能使用簡單的模型,而不是模型越復雜越好。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 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