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