一、Quadratic Hypothesis
之前介紹的線性模型，在2D平面上是一條直線，在3D空間中是一個平面。數學上，我們用線性得分函數s來表示：
。其中，x為特征值向量，w為權重，s是線性的。
線性模型的優點就是，它的VC Dimension比較小，保證了Ein≈Eout。但是缺點也很明顯，對某些非線性問題，可能會造成Ein很大，雖然Ein≈Eout，但是也造成Eout很大，分類效果不佳。
為了解決線性模型的缺點，我們可以使用非線性模型來進行分類。例如資料集D不是線性可分的，而是圓形可分的，圓形内部是正類，外面是負類。假設它的hypotheses可以寫成：
基于這種非線性思想，我們之前讨論的PLA、Regression問題都可以有非線性的形式進行求解。
這種xn→zn的轉換可以看成是x空間的點映射到z空間中去，而在z域中，可以用一條直線進行分類，也就是從x空間的圓形可分映射到z空間的線性可分。z域中的直線對應于x域中的圓形。是以，我們把xn→zn這個過程稱之為特征轉換（Feature Transform）。通過這種特征轉換，可以将非線性模型轉換為另一個域中的線性模型。
已知x域中圓形可分在z域中是線性可分的，那麼反過來，如果在z域中線性可分，是否在x域中一定是圓形可分的呢？答案是否定的。由于權重向量w取值不同，x域中的hypothesis可能是圓形、橢圓、雙曲線等等多種情況。
目前讨論的x域中的圓形都是圓心過原點的，對于圓心不過原點的一般情況，xn→zn映射公式包含的所有項為：
也就是說，對于二次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域特征次元是：
現在，如果階數更高，假設階數為Q，那麼對于x特征次元是d維的，它的z域特征次元為：
由上式可以看出，計算z域特征次元個數的時間複雜度是Q的d次方，随着Q和d的增大，計算量會變得很大。同時，空間複雜度也大。也就是說，這種特征變換的一個代價是計算的時間、空間複雜度都比較大。
上圖中，左邊是用直線進行線性分類，有部分點分類錯誤；右邊是用四次曲線進行非線性分類，所有點都分類正确，那麼哪一個分類效果好呢？單從平面上這些訓練資料來看，四次曲線的分類效果更好，但是四次曲線模型很容易帶來過拟合的問題，雖然它的Ein比較小，從泛化能力上來說，還是左邊的分類器更好一些。也就是說VC Dimension過大會帶來過拟合問題，d˘+1不能太大了。
那麼如何選擇合适的Q，來保證不會出現過拟合問題，使模型的泛化能力強呢？一般情況下，為了盡量減少特征自由度，我們會根據訓練樣本的分布情況，人為地減少、省略一些項。但是，這種人為地删減特征會帶來一些“自我分析”代價，雖然對訓練樣本分類效果好，但是對訓練樣本外的樣本，不一定效果好。是以，一般情況下，還是要儲存所有的多項式特征，避免對訓練樣本的人為選擇。
四、Structured Hypothesis Sets
下面，我們讨論一下從x域到z域的多項式變換。首先，如果特征次元隻有1維的話，那麼變換多項式隻有常數項：
從上圖中也可以看到，随着變換多項式的階數增大，雖然Ein逐漸減小，但是model complexity會逐漸增大，造成Eout很大，是以階數不能太高。
那麼，如果選擇的階數很大，确實能使Ein接近于0，但是泛化能力通常很差，我們把這種情況叫做tempting sin。是以，一般最合适的做法是先從低階開始，如先選擇一階hypothesis，看看Ein是否很小，如果Ein足夠小的話就選擇一階，如果Ein大的話，再逐漸增加階數，直到滿足要求為止。也就是說，盡量選擇低階的hypothes，這樣才能得到較強的泛化能力。
五、總結
這節課主要介紹了非線性分類模型，通過非線性變換，将非線性模型映射到另一個空間，轉換為線性模型，再來進行線性分類。本節課完整介紹了非線性變換的整體流程，以及非線性變換可能會帶來的一些問題：時間複雜度和空間複雜度的增加。最後介紹了在要付出代價的情況下，使用非線性變換的最安全的做法，盡可能使用簡單的模型，而不是模型越複雜越好。