中科院統(tǒng)計學課程2kernelmethod

1、1,今天內容,核回歸核方法Kernel trick正則化理論,2,非參數(shù)回歸,參數(shù)回歸（線性回歸）時，假設r (x) 為線性的 。當r (x) 不是x的線性函數(shù)時，基于最小二乘的回歸效果不佳 非參數(shù)回歸：不對r (x)的形式做任何假定局部加權方法：用點x附近的Yi的加權平均表示r (x),3,回憶：knn,回歸函數(shù)：Knn： 用訓練樣本中最鄰近x0的k個樣本的均值估計條件期望其中 為x0的鄰

2、域，由訓練樣本中最鄰近x0的k個點xi 定義,4,回憶：knn,例：,5,核回歸：Nadaraya-Watson,鄰域中點的權重不是等權重，而是每個樣本的權重隨其到目標點的距離平滑衰減其中參數(shù)h稱為帶寬(bandwidth)，核函數(shù)有時可寫為：K可為任意平滑的函數(shù)，滿足,6,常用核函數(shù),Epanechnikov 核：使風險最小的核函數(shù)高斯核：三次方核：,7,核回歸：Nadaraya-Watson,回憶一下回歸方

3、程的定義：分別對 用核密度估計，得到,8,核回歸：Nadaraya-Watson,證明：,,,9,核回歸：Nadaraya-Watson,證明（續(xù)）,10,核回歸：Nadaraya-Watson,這可以被看作是對y取一個加權平均，對x附近的值給予更高的權重：其中,11,核回歸：Nadaraya-Watson,將核回歸估計寫成如下形式：其中

4、 ，,,,12,核回歸：Nadaraya-Watson,類似核密度估計中求期望的展開，得到同理，其中,13,核回歸：Nadaraya-Watson,最后，得到估計的風險為最佳帶寬以 的速率減少，在這種選擇下風險以 的速率減少，這是最佳收斂速率（同核密度估計）,14,核回歸：Nadaraya-Watson,實際應用中，利用交叉驗證

5、對求最佳帶寬h。交叉驗證對風險的估計為實際上不必每次留下一個計算單獨估計，可以寫成以下形式,15,例：Example 20.23,,不同帶寬下Nadaraya-Watson回歸的結果,16,核回歸：Nadaraya-Watson,模型類型：非參數(shù)損失：平方誤差參數(shù)選擇：留一交叉驗證,17,局部線性回歸,問題：加權核回歸在訓練數(shù)據中靠近邊界的點的估計很差核在邊界區(qū)域不對稱，局部加權平均在邊界區(qū)域上出現(xiàn)嚴重偏差 ? 局部線性回

6、歸局部線性回歸：在每一個將要被預測的點x處解一個單獨的加權最小二乘問題，找到使下述表達式最小的,18,局部線性回歸,,邊界上的N-W核： 核在邊界不對稱?偏差大,邊界上的局部線性回歸： 將偏差降至一階,藍色曲線：真實情況綠色曲線：估計值黃色區(qū)域：x0的局部區(qū)域,19,核回歸：局部線性回歸,則估計為：其中W(x)是一個 的對角矩陣且第i個對角元素是

7、 估計在yi上是線性的，因為權重項 wi(x)不涉及yi ，可被認為是等價核,20,局部線性回歸,局部線性回歸通過自動修改核，將偏差降至一階由于 ,偏差 為,,21,局部線性回歸,,邊界上的局部等價核（綠色點）,內部區(qū)域的局部等價核（綠色點）,22,局部多項式回歸,局部多項式回歸：用d次多項式回歸代替線性回歸可以考慮任意階的多項式，但有一個偏差和方差的折中

8、通常認為：超過線性的話，會增大方差，但對偏差的減少不大，因為局部線性回歸能處理大多數(shù)的邊界偏差，,23,可變寬度核,可變寬度核：如使每一個訓練點的帶寬與它的第k個近鄰的距離成反比在實際應用中很好用，雖然尚未有理論支持怎樣選擇參數(shù)不會改變收斂速度，但在有限樣本時表現(xiàn)更好注意：上述這些擴展（包括局部線性/局部多項式）都可應用到核密度估計中,24,核方法,為什么要用核方法？得到更豐富的模型，但仍然采用同樣的方法如嶺回歸方法?核嶺

9、回歸內容Kernel trick再生Hilbert空間,25,線性模型,線性模型：方便、應用廣泛有很強的理論保證但還是有局限性可以通過擴展特征空間增強線性模型的表示能力如特征空間為R6而不是R2特該特征空間的線性預測器為,26,嶺回歸,對給定的最小化正則化的殘差則最優(yōu)解為,需O(p3)運算,27,對偶表示,一種對偶表示為：其中,需O(n3)運算,28,對偶嶺回歸,為了預測一個新的點

10、其中此時只需計算Gram矩陣G,嶺回歸只需計算數(shù)據點的內積,29,特征空間中的線性回歸,基本思想：將數(shù)據映射到高維空間（特征空間）然后在高維空間中用線性方法嵌入式特征映射：,30,核函數(shù),則核函數(shù)為其中 為將數(shù)據映射到高維空間的映射有許多可能的核函數(shù)最簡單的為核,31,特征空間中的嶺回歸,為了預測一個新的點其中計算Gram矩陣G,利用核函數(shù)計算內積,32,另一種對偶表示推導方式,線性嶺回歸最小

11、化：等價于滿足約束則拉格朗日函數(shù)為,33,Wolfe對偶問題,轉化為其對偶問題：對L求偏導并置為0，得到,34,Wolfe對偶問題,將 和 代入拉格朗日函數(shù)原目標函數(shù)轉化為,35,最優(yōu)解,寫成矩陣形式為：得到解：相應的回歸方程為：,,點積,36,核化嶺回歸,將點積

12、換成核函數(shù)Kernel trick就實現(xiàn)了對線性嶺回歸的核化，在空間統(tǒng)計學中稱為Kriging算法。,37,核方法,通過將輸入空間映射到高維空間（特征空間），然后在高維空間中用線性方法高維：維數(shù)災難通過核技巧，避免維數(shù)災難,38,Kernel Trick,將問題變?yōu)槠鋵ε紗栴}：只需計算點積，與特征的維數(shù)無關，如在線性嶺回歸中，最大化下列目標函數(shù)在高維空間中的點積可寫成核(kernel)的形式，如果選定核函數(shù)，這無需計算映

13、射 可以計算點積,39,Kernel Trick,總之，這些被稱為核技巧(kernel trick ) , 尋找一個映射： 和一個學習方法，使得F的維數(shù)比X高 , 因此模型更豐富算法只需要計算點積存在一個核函數(shù)，使得在算法中任何出現(xiàn)項 的地方，用 代替,亦稱為原方法的核化(kernelizing the original method

14、).,點積核,40,什么樣的函數(shù)可以作為核函數(shù)？,Mercer’s 定理給出了連續(xù)對稱函數(shù)k可作為核函數(shù)的充要條件：半正定半正定核：對稱：且對任意訓練樣本點和任意滿足K被稱為Gram矩陣或核矩陣。,矩陣形式：,41,半正定核的性質,對稱Cauchy-Schwarz不等式,42,Mercer’s Theorem,當且僅當一個函數(shù)K滿足半正定形式時，函數(shù)K可以寫成其中 為特征映射：該核定義

15、了一個函數(shù)集合 ，其中每個元素 可以寫成因此某些核對應無限個預測變量的變換,Mercer核,43,RKHS：再生Hilbert空間—Reproducing Kernel Hilbert Spaces,為了證明上述定理，構造一個特殊的特征空間,,定義函數(shù)空間,再生性質,映射到一個函數(shù)空間,有限、半正定,,44,Mercer’s Theorem,粗略地說，如果K對可積函數(shù) 是正定的，即則對K存在對應的

16、因此K是一個合適的核,45,Mercer 核,一些常用的核函數(shù)滿足上述性質：對字符串、圖等對象，也可以構造核函數(shù),高斯核：,多項式核：,sigmoid核：,46,RKHS：點積空間,定義該函數(shù)空間的點積Mercer定理隱含,47,正則化和RKHS,一種通用的正則化的形式為假設 f 在RKHS中，則,48,正則化和RKHS,則求解轉化為求解下述“簡單”問題,49,例：嶺回歸,當回歸分析取平方誤差損失

17、時，因此,50,正則化的貝葉斯解釋,為貝葉斯MAP估計其中先驗為似然為損失函數(shù)取L2時，高斯分布：損失函數(shù)取L1時，為Laplace分布：,,51,其他與核方法相關的一些論題,高斯過程 SVM…關于核方法一本較好的參考書：支持向量機導論（An Introduction to Support Vector Machines and Other Kernel-based Learning Methods）Ne

18、llo Cristianini, John Shawe-Taylor著，李國正，王猛， 曾華軍譯， 電子工業(yè)出版社，北京，2004Bernhard Schölkopf: Introduction to Kernel Methods, Analysis of Patterns Workshop, Erice, Italy, 2005Schölkopf& Smola: Learning with Kernel