中科院統(tǒng)計(jì)學(xué)課程2kernelmethod

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

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

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

4、 ，,,,12,核回歸：Nadaraya-Watson,類(lèi)似核密度估計(jì)中求期望的展開(kāi)，得到同理，其中,13,核回歸：Nadaraya-Watson,最后，得到估計(jì)的風(fēng)險(xiǎn)為最佳帶寬以 的速率減少，在這種選擇下風(fēng)險(xiǎn)以 的速率減少，這是最佳收斂速率（同核密度估計(jì)）,14,核回歸：Nadaraya-Watson,實(shí)際應(yīng)用中，利用交叉驗(yàn)證

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

6、歸局部線(xiàn)性回歸：在每一個(gè)將要被預(yù)測(cè)的點(diǎn)x處解一個(gè)單獨(dú)的加權(quán)最小二乘問(wèn)題，找到使下述表達(dá)式最小的,18,局部線(xiàn)性回歸,,邊界上的N-W核： 核在邊界不對(duì)稱(chēng)?偏差大,邊界上的局部線(xiàn)性回歸： 將偏差降至一階,藍(lán)色曲線(xiàn)：真實(shí)情況綠色曲線(xiàn)：估計(jì)值黃色區(qū)域：x0的局部區(qū)域,19,核回歸：局部線(xiàn)性回歸,則估計(jì)為：其中W(x)是一個(gè) 的對(duì)角矩陣且第i個(gè)對(duì)角元素是

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

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

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

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

11、化：等價(jià)于滿(mǎn)足約束則拉格朗日函數(shù)為,33,Wolfe對(duì)偶問(wèn)題,轉(zhuǎn)化為其對(duì)偶問(wèn)題：對(duì)L求偏導(dǎo)并置為0，得到,34,Wolfe對(duì)偶問(wèn)題,將 和 代入拉格朗日函數(shù)原目標(biāo)函數(shù)轉(zhuǎn)化為,35,最優(yōu)解,寫(xiě)成矩陣形式為：得到解：相應(yīng)的回歸方程為：,,點(diǎn)積,36,核化嶺回歸,將點(diǎn)積

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

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

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

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

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

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

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