基于核函數(shù)的學(xué)習(xí)算法

Kernel-BasedLearningAlgorithms1.Kernel-BasedLearningAlgorith引言

近幾年，出現(xiàn)了一些基于核函數(shù)的機(jī)器學(xué)習(xí)方法，例如：SVM（可支持向量機(jī)）、KFD（基于核的Fisher判別分析）、KPCA（核主成分分析）等。這些方法在分類(lèi)問(wèn)題、回歸問(wèn)題以及無(wú)監(jiān)督學(xué)習(xí)上都具有現(xiàn)實(shí)意義。這些核函數(shù)方法已經(jīng)成功應(yīng)用到模式識(shí)別的各個(gè)領(lǐng)域，比如目標(biāo)識(shí)別、文本分類(lèi)、時(shí)間序列預(yù)測(cè)等等2.引言近幾年，出現(xiàn)了一些基于核函數(shù)的機(jī)器學(xué)習(xí)方法，例理論基礎(chǔ)監(jiān)督學(xué)習(xí):SVM、KFD無(wú)監(jiān)督學(xué)習(xí)：KPCA模型選擇3.理論基礎(chǔ)3.理論基礎(chǔ)機(jī)器學(xué)習(xí)VC維結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則4.理論基礎(chǔ)機(jī)器學(xué)習(xí)4.SLT(StatisticalLearningTheory)上世紀(jì)90年代中才成熟的統(tǒng)計(jì)學(xué)習(xí)理論，是在基于經(jīng)驗(yàn)風(fēng)險(xiǎn)的有關(guān)研究基礎(chǔ)上發(fā)展起來(lái)的，專(zhuān)門(mén)針對(duì)小樣本的統(tǒng)計(jì)理論。統(tǒng)計(jì)學(xué)習(xí)理論為研究有限樣本情況下的模式識(shí)別、函數(shù)擬合和概率密度估計(jì)等三種類(lèi)型的機(jī)器學(xué)習(xí)問(wèn)題提供了理論框架，同時(shí)也為模式識(shí)別發(fā)展了一種新的分類(lèi)方法——支持向量機(jī)。5.SLT(StatisticalLearningTheor機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)是現(xiàn)代智能技術(shù)中重要的一個(gè)方面，研究從觀測(cè)樣本出發(fā)去分析對(duì)象，去預(yù)測(cè)未來(lái)。機(jī)器學(xué)習(xí)的基本模型：輸出y與x之間存在一種固定的、但形式未知的聯(lián)合概率分布函數(shù)F(y,x)。學(xué)習(xí)機(jī)中有函數(shù)集{f(x,w)}，可估計(jì)輸入與輸出之間依賴關(guān)系，其中w為廣義參數(shù)。6.機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)是現(xiàn)代智能技術(shù)中重要的一個(gè)方面，研究從風(fēng)險(xiǎn)最小化－機(jī)器學(xué)習(xí)問(wèn)題表示

已知變量y與輸入x之間存在一定的未知依賴關(guān)系，即聯(lián)合概率分布F(x,y)機(jī)器學(xué)習(xí)就是根據(jù)獨(dú)立同分布的n個(gè)觀測(cè)樣本：

(x1,y1),(x2,y2),···,(xn,yn)

在一組函數(shù){f(x,w)}中求一個(gè)最優(yōu)函數(shù)f(x,w0)，使預(yù)測(cè)的期望風(fēng)險(xiǎn)R(w)最小化。

L(y,{f(x,w)})為損失函數(shù)，由于對(duì)y進(jìn)行預(yù)測(cè)而造成的損失；w為函數(shù)的廣義參數(shù)，故{f(x,w)}可表示任何函數(shù)集；F(x,y)為聯(lián)合分布函數(shù)。7.風(fēng)險(xiǎn)最小化－機(jī)器學(xué)習(xí)問(wèn)題表示

已知變量y與輸入x之間存在一VC維Vanik和Chervonenkis(1968)提出了VC維的概念。VC維：對(duì)于一個(gè)指示函數(shù)（即只有0和1兩種取值的函數(shù)）集，如果存在h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開(kāi)，則稱函數(shù)集能夠把h個(gè)樣本打散，函數(shù)集的VC維就是能夠打散的最大樣本數(shù)目。VC維是描述函數(shù)集或?qū)W習(xí)機(jī)器的復(fù)雜性或者說(shuō)是學(xué)習(xí)能力的一個(gè)重要指標(biāo),在此概念基礎(chǔ)上發(fā)展出了一系列關(guān)于統(tǒng)計(jì)學(xué)習(xí)的一致性、收斂速度、泛化性能等的重要結(jié)論。8.VC維Vanik和Chervonenkis(1968)提出了該線性分類(lèi)函數(shù)的VC維即為39.該線性分類(lèi)函數(shù)的VC維即為39.一般而言,VC維越大,學(xué)習(xí)能力就越強(qiáng),但學(xué)習(xí)機(jī)器也越復(fù)雜。目前還沒(méi)有通用的關(guān)于計(jì)算任意函數(shù)集的VC維的理論,只有對(duì)一些特殊函數(shù)集的VC維可以準(zhǔn)確知道。10.一般而言,VC維越大,學(xué)習(xí)能力就越強(qiáng),但學(xué)習(xí)機(jī)器也越復(fù)雜。結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則Vapnik和Chervonenkis(1974)提出了SRM。傳統(tǒng)機(jī)器學(xué)習(xí)方法中普遍采用的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則在樣本數(shù)目有限時(shí)是不合理的,因此，需要同時(shí)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍。統(tǒng)計(jì)學(xué)習(xí)理論提出了一種新的策略,即把函數(shù)集構(gòu)造為一個(gè)函數(shù)子集序列,使各個(gè)子集按照VC維的大小排列;在每個(gè)子集中尋找最小經(jīng)驗(yàn)風(fēng)險(xiǎn),在子集間折衷考慮經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍,取得實(shí)際風(fēng)險(xiǎn)的最小。這種思想稱作結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則(StructuralRiskMinimizationPrinciple)。11.結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則Vapnik和Chervonenkis(1核函數(shù)在處理線性分類(lèi)問(wèn)題時(shí)，數(shù)據(jù)以點(diǎn)積的形式(xi·xj)出現(xiàn)。而在處理非線性分類(lèi)問(wèn)題時(shí)，需要采用非線性映射把輸入空間映射到高維特征空間，記為：當(dāng)在特征空間H中構(gòu)造最優(yōu)超平面時(shí)，訓(xùn)練算法僅使用空間中的點(diǎn)積，即存在一種核函數(shù)K,使得:核函數(shù)將m維高維空間的內(nèi)積運(yùn)算轉(zhuǎn)化為n維低維輸入空間的核函數(shù)計(jì)算，從而巧妙地解決了在高維特征空間中計(jì)算的“維數(shù)災(zāi)難”等問(wèn)題。12.核函數(shù)在處理線性分類(lèi)問(wèn)題時(shí)，數(shù)據(jù)以點(diǎn)積的形式(xi·xj13.13.核方法分為核函數(shù)設(shè)計(jì)和算法設(shè)計(jì)兩個(gè)部分,具體情況如圖1所示。核方法的實(shí)施步驟,具體描述為:①收集和整理樣本,并進(jìn)行標(biāo)準(zhǔn)化;②選擇或構(gòu)造核函數(shù);③用核函數(shù)將樣本變換成為核矩陣;④在特征空間對(duì)核矩陣實(shí)施各種線性算法;⑤得到輸入空間中的非線性模型。14.核方法分為核函數(shù)設(shè)計(jì)和算法設(shè)計(jì)兩個(gè)部分,具體情況如圖1所示。核函數(shù)主要的核函數(shù)有三類(lèi)：多項(xiàng)式核函數(shù)徑向基函數(shù)S形函數(shù)15.核函數(shù)主要的核函數(shù)有三類(lèi)：15.有監(jiān)督學(xué)習(xí)(supervised

learning)監(jiān)督學(xué)習(xí)，就是人們常說(shuō)的分類(lèi)，通過(guò)已有的訓(xùn)練樣本（即已知數(shù)據(jù)以及其對(duì)應(yīng)的輸出）去訓(xùn)練得到一個(gè)最優(yōu)模型（這個(gè)模型屬于某個(gè)函數(shù)的集合，再利用這個(gè)模型將所有的輸入映射為相應(yīng)的輸出，對(duì)輸出進(jìn)行簡(jiǎn)單的判斷從而實(shí)現(xiàn)分類(lèi)的目的，也就具有了對(duì)未知數(shù)據(jù)進(jìn)行分類(lèi)的能力。典型的例子就是SVM（可支持向量機(jī)）、KFD（基于核的Fisher判別分析）。16.有監(jiān)督學(xué)習(xí)(supervised

learning)監(jiān)督學(xué)習(xí)SVM（Supportvectormachines)SVM是基于SLT的一種機(jī)器學(xué)習(xí)方法。簡(jiǎn)單的說(shuō)，就是將數(shù)據(jù)單元表示在多維空間中，然后對(duì)這個(gè)空間做劃分的算法。SVM是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性之間尋求最佳折衷，以期獲得最好的推廣（泛化）能力。17.SVM（Supportvectormachines)SV支持向量機(jī)方法建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)之上，專(zhuān)門(mén)針對(duì)小樣本情況下的機(jī)器學(xué)習(xí)問(wèn)題。對(duì)于分類(lèi)問(wèn)題，支持向量機(jī)方法根據(jù)區(qū)域中的樣本計(jì)算該區(qū)域的分類(lèi)曲面，由該曲面決定該區(qū)域中的樣本類(lèi)別。已知樣本x為m維向量,在某個(gè)區(qū)域內(nèi)存在n個(gè)樣本:(x1,y1)，(x2,y2)，…，(xn,yn)其中，xi是訓(xùn)練元組，xi∈Rm，yi是類(lèi)標(biāo)號(hào)，yi∈{1,-1}。若存在超平面(hyperplane):ω·x+b=0(1)18.支持向量機(jī)方法建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)之上，專(zhuān)門(mén)針對(duì)小樣本情況其中·表示向量的點(diǎn)積，如圖1所示，超平面能將這n個(gè)樣本分為兩類(lèi),那么存在最優(yōu)超平面不僅能將兩類(lèi)樣本準(zhǔn)確分開(kāi)，而且能使兩類(lèi)樣本到超平面的距離最大。式(1)中的ω和b乘以系數(shù)后仍能滿足方程，進(jìn)行歸一化處理之后，對(duì)于所有樣本xi，式|ω·xi+b|的最小值為1,則樣本與此最優(yōu)超平面的最小距離為|ω·xi+b|/‖ω‖=1/‖ω‖,那么最優(yōu)超平面應(yīng)滿足條件:yi（ω·xi+b）≥1，i=1，…，n.(2)19.其中·表示向量的點(diǎn)積，如圖1所示，超平面能將這n個(gè)樣本分根據(jù)最優(yōu)超平面的定義可知:ω和b的優(yōu)化條件是使兩類(lèi)樣本到超平面最小距離之和2/‖ω‖最大。此外，考慮到可能存在一些樣本不能被超平面正確分類(lèi),因此引入松弛變量(slackvariable)：

ζi≥0，i=1，…，n.（3）這樣上述二元分類(lèi)問(wèn)題轉(zhuǎn)換為在式(2)和式(3)的約束下最小化：

（4）其中,非負(fù)常數(shù)C為懲罰因子，C值越大表示對(duì)錯(cuò)誤分類(lèi)的懲罰越大。這是一個(gè)具有線性約束的二次規(guī)劃問(wèn)題，利用拉格朗日乘子法可以將式(4)轉(zhuǎn)化為其對(duì)偶形式:(5)約束條件:(6)20.根據(jù)最優(yōu)超平面的定義可知:ω和b的優(yōu)化條件是使兩類(lèi)樣本到超其中ai為原問(wèn)題中與約束條件式(2)對(duì)應(yīng)的拉格朗日乘子。這是一個(gè)不等式約束下的二次函數(shù)尋優(yōu)問(wèn)題，存在高效的算法求解?？梢宰C明，在此尋優(yōu)問(wèn)題的解中有一部分ai不為0，它們所對(duì)應(yīng)的訓(xùn)練樣本完全確定了這個(gè)超平面，因此稱其為支持向量(supportvector)。對(duì)于類(lèi)型未知的樣本x,可以采用線性判決函數(shù):來(lái)判斷其所屬類(lèi)別,綜合式(9)，可得分類(lèi)判決函數(shù):

21.其中ai為原問(wèn)題中與約束條件式(2)對(duì)應(yīng)的拉格朗日乘子。根據(jù)核函數(shù)的相關(guān)知識(shí)，可以使用核函數(shù)K(xi·xj)替代線性分類(lèi)問(wèn)題中的點(diǎn)積形式，從而實(shí)現(xiàn)非線性變換后的線性分類(lèi)。由此,式(5)的對(duì)偶形式可變?yōu)椋?/p>

約束條件：

相應(yīng)的分類(lèi)判決函數(shù)轉(zhuǎn)變?yōu)?22.根據(jù)核函數(shù)的相關(guān)知識(shí)，可以使用核函數(shù)K(xi·xj)替KernelFisherdiscriminantanalysis（基于核的Fisher判別方法）

是由Mika等人于1999年提出的方法。核Fisher判別分析是一種很有用的機(jī)器學(xué)習(xí)方法，將一個(gè)非線性問(wèn)題通過(guò)非線性變換轉(zhuǎn)化為另一個(gè)空間中的線性問(wèn)題進(jìn)行求解.它不依賴于

模型，也不存在維數(shù)災(zāi)難。23.KernelFisherdiscriminantan線性Fisher判別分析對(duì)于兩類(lèi)問(wèn)題,設(shè)待分類(lèi)的樣本有n個(gè):x1,x2,…,xn∈Rd。在進(jìn)行Fisher判別分析時(shí),目標(biāo)是找到線性投影方向(投影軸),使得訓(xùn)練樣本在這些軸上的投影結(jié)果類(lèi)內(nèi)散度最小,類(lèi)間散度最大。設(shè)樣本類(lèi)內(nèi)均值為mi,則設(shè)樣本類(lèi)間離散度矩陣為Sω,則設(shè)樣本類(lèi)間離散度矩陣為Sb,則最佳投影方向是通過(guò)最大化目標(biāo)函數(shù)J(w)W為投影方向。24.線性Fisher判別分析對(duì)于兩類(lèi)問(wèn)題,設(shè)待分類(lèi)的樣本有n個(gè):考慮到J(w)的尺度不變性,令分母為非零常數(shù),用Lagrange乘子法求解得到下面的特征值：W*就是J(w)中的極值解,也就是矩陣S-1ωSb的最大特征值對(duì)應(yīng)的特征向量。測(cè)試樣本在這個(gè)向量上的投影系數(shù)就是所提取的測(cè)試樣本的特征值。則FDA的判別函數(shù)為b為偏移量,可以通過(guò)求解以下方程得到則對(duì)于一待測(cè)樣本xi,求Fisher判別分析判別函數(shù)f(xi)=w*xi+b,通過(guò)f(xi)正負(fù)確定其歸屬。25.考慮到J(w)的尺度不變性,令分母為非零常數(shù),用Lagran基于核的Fisher判別分析KFDA算法的思想是:引入核方法，通過(guò)一個(gè)非線性映射,將輸入數(shù)據(jù)映射到一個(gè)高維的線性可分的特征空間中,然后在這個(gè)特征空間中進(jìn)行線性Fisher判別分析,從而實(shí)現(xiàn)相對(duì)于輸入空間的非線性判別分析。在進(jìn)行KFDA時(shí),首先通過(guò)非線性映射?將輸入數(shù)據(jù)映射到一個(gè)高維特征空間中,即這時(shí),輸入訓(xùn)練樣本由原來(lái)的x變?yōu)?(x),然后在這個(gè)特征空間F中進(jìn)行線性FDA。問(wèn)題轉(zhuǎn)變?yōu)樵贔中最大化目標(biāo)函數(shù)JF(w)式中,ω∈F,

是F中相應(yīng)的矩陣,分別為26.基于核的Fisher判別分析KFDA算法的思想是:引入核方法由于F空間的維數(shù)通常很高甚至是無(wú)窮維,因JF(w)式直接求解很困難。借用非線性支持向量機(jī)的核方法,引入以下內(nèi)積核函數(shù)來(lái)隱含地進(jìn)行運(yùn)算，,定義核矩陣K為式中,(Ki)pj=k(xp,xij),p=1,2,?,n,是n×ni

矩陣(i=1,2),是全體樣本分別與類(lèi)1、類(lèi)2的內(nèi)積核矩陣。由再生核理論可知,F空間的任何解w?

都是F空間中的訓(xùn)練樣本的線性組合,即:是第i類(lèi)各個(gè)樣本與總體的內(nèi)積核的均值。由上述三式可得27.27.在F空間中,求解Fisher線性判別函數(shù):該判別函數(shù)隱式地對(duì)應(yīng)原空間的一個(gè)非線性判別函數(shù),因此,它是一種非線性方法。求解矩陣N-1M的最大特征值對(duì)應(yīng)的特征向量就可求得上式的最優(yōu)解。測(cè)試數(shù)據(jù)在特征向量w?

上的投影為：在實(shí)際應(yīng)用中為了防止N非正定,使解更穩(wěn)定,通常引入一個(gè)正則化參數(shù)λ,令Nλ=N+λI,I是單位矩陣。則判別函數(shù)可以寫(xiě)為:b可以通過(guò)求解具有L1軟邊界的一維線性支持向量機(jī)(SVM)來(lái)確定。28.在F空間中,求解Fisher線性判別函數(shù):28.SVM和KFD的比較核Fisher判別分析與支持向量機(jī)分類(lèi)精度相差不大;但由于SVM需要求解二次優(yōu)化問(wèn)題,因此在訓(xùn)練樣本較多的情況下需要的訓(xùn)練時(shí)間較長(zhǎng),而KFDA只計(jì)算矩陣的特征向量,計(jì)算量小，在消耗時(shí)間上具有明顯的優(yōu)勢(shì)。與SVM分類(lèi)相似,KFDA的分類(lèi)性能受核函數(shù)及參數(shù)影響很大,核函數(shù)參數(shù)在特定的范圍內(nèi)才能得到良好的分類(lèi)精度。29.SVM和KFD的比較核Fisher判別分析與支持向量機(jī)分類(lèi)精無(wú)監(jiān)督學(xué)習(xí)(unsupervised

learning)

無(wú)監(jiān)督學(xué)習(xí)是我們事先沒(méi)有任何訓(xùn)練樣本，而需要直接對(duì)數(shù)據(jù)進(jìn)行建模。典型的例子就是KPCA（核主成分分析）。30.無(wú)監(jiān)督學(xué)習(xí)(unsupervised

learning)

無(wú)KernelPrincipalComponentAnalysisKPCA方法借鑒SVM的核方法思想,將線性的PCA擴(kuò)展到非線性情形。其思想可描述為:通過(guò)一個(gè)非線性函數(shù)，將輸入空間映射到更高維的特征空間中,然后在此高維空間中使用PCA方法提取數(shù)據(jù)特征。由圖1可以看出,非線性可分的輸入空間通過(guò)函數(shù)映射到特征空間后,變成了一個(gè)線性可分的問(wèn)題。31.KernelPrincipalComponentAnaPrincipalComponentAnalysis主成分分析(PrincipalComponentAnalysis,簡(jiǎn)稱PCA)是一種常用的基于變量協(xié)方差矩陣對(duì)信息進(jìn)行處理、壓縮和抽提的有效方法。32.PrincipalComponentAnalysis主成33.33.模型選擇

核函數(shù)方法中模型選擇十分重要,模型選擇包括核函數(shù)的選擇、構(gòu)造以及參數(shù)調(diào)整;就SVMs而言,還包括容量控制參數(shù)(正則化參數(shù))、損失函數(shù)的確定等。34.模型選擇核函數(shù)方法中模型選擇十分重要,模型選擇包括核

多數(shù)應(yīng)用研究都采用高斯核函數(shù),然后再確定其他參