核函數(shù)特征空間0610

CH.3核函數(shù)特征空間《導(dǎo)論》pp.24-46需要學(xué)習(xí)的目標(biāo)函數(shù)的復(fù)雜度取決于它的表示（自變?cè)獋€(gè)數(shù)、定義域、函數(shù)關(guān)系式、……），學(xué)習(xí)任務(wù)的難易程度隨之而變化。線性學(xué)習(xí)器計(jì)算能力有限核表示方法的特點(diǎn)使用線性學(xué)習(xí)器分二類問(wèn)題

分二類問(wèn)題

尋找一個(gè)實(shí)值函數(shù)（決策函數(shù)）f：XR，

當(dāng)f(x)0

時(shí)，輸入賦給正類；當(dāng)

f(x)0

時(shí)，輸入賦給負(fù)類。線性學(xué)習(xí)器

使用線性假設(shè)

確定最優(yōu)超平面，其控制參數(shù)為而決策規(guī)則由

給出。線性學(xué)習(xí)器計(jì)算能力有限目標(biāo)概念（函數(shù)）通常不能由給定屬性的簡(jiǎn)單線性函數(shù)組合產(chǎn)生導(dǎo)致使用多層閾值線性函數(shù)（如：多層神經(jīng)網(wǎng)絡(luò)、BP算法等）對(duì)目標(biāo)概念的更為簡(jiǎn)潔的直接描述涉及比給定數(shù)據(jù)更為廣泛的抽象特征導(dǎo)致核表示方法核表示方法的特點(diǎn)將給定數(shù)據(jù)映射到高維空間，變線性不可分情形為線性可分，來(lái)增加線性學(xué)習(xí)器的計(jì)算能力用于學(xué)習(xí)的算法和理論可以在很大程度上同應(yīng)用領(lǐng)域的特性分開(kāi)，而這些特性將在設(shè)計(jì)合適的核函數(shù)時(shí)考慮Ch.3主要內(nèi)容1、特征空間和特征選擇問(wèn)題2、使用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性關(guān)系3、關(guān)于核函數(shù)的討論4、特征空間中的計(jì)算5、核與高斯過(guò)程

使用不同技術(shù)的困難所在1、特征空間和特征選擇問(wèn)題

1）一個(gè)合理的思路2）定義和概念3）特征映射可能產(chǎn)生的困難4）特征選擇面臨的重要任務(wù)1）一個(gè)合理的思路需要增加一個(gè)預(yù)處理步驟，將給定數(shù)據(jù)的表達(dá)形式轉(zhuǎn)換成一個(gè)與特定的學(xué)習(xí)問(wèn)題（如P.25,例3.1萬(wàn)有引力，x→lnx)所需要的表示相匹配的一種形式。P.25“萬(wàn)有引力定理”，使用映射：x→lnx2）定義和概念屬性：原始的數(shù)據(jù)量(或輸入量)，空間X是輸入空間（低維）。特征：經(jīng)變化后，用于描述數(shù)據(jù)的量新空間是特征空間（高維）特征選擇（特征映射）：選擇最適合學(xué)習(xí)問(wèn)題的數(shù)據(jù)表達(dá)方式的任務(wù)

P.26圖3.1經(jīng)過(guò)特征映射，使得所得數(shù)據(jù)可以線性分開(kāi)P.26圖3.1特征映射：二維輸入空間→二維特征空間

數(shù)據(jù)線性分開(kāi)：不能→能3）特征映射可能產(chǎn)生的困難考慮二維輸入空間的情形假定關(guān)于問(wèn)題的先驗(yàn)知識(shí)提示：相關(guān)信息已編碼到自由度為2的單項(xiàng)式的形式，則一個(gè)可能使用的映射是：（4維）對(duì)于n維輸入空間，自由度取為d的單項(xiàng)式形式，特征映射：若還要用到交錯(cuò)項(xiàng)的信息表示，則其特征空間的維數(shù)將很快變得不可計(jì)算。4）特征選擇面臨的重要任務(wù)

降低和排除維數(shù)災(zāi)難，提高計(jì)算性能和泛化性能檢測(cè)出無(wú)關(guān)特征并將其去除特別是那些與目標(biāo)值輸出無(wú)關(guān)的特征例：萬(wàn)有引力計(jì)算中，物體的顏色、溫度等維數(shù)約簡(jiǎn)：尋找包含原始屬性中必要信息的最小特征集（d盡可能小于n)關(guān)于萬(wàn)有引力的例子作為學(xué)習(xí)過(guò)程的一個(gè)重要部分，如何實(shí)現(xiàn)自動(dòng)化及避免選擇的任意性。（主成分分析，…）P.26,例3.2關(guān)于萬(wàn)有引力定理的進(jìn)一步例子：2、使用線性學(xué)習(xí)器學(xué)習(xí)一個(gè)非線性

關(guān)系1）考慮問(wèn)題的思路2）到特征空間的隱式映射3）核函數(shù)方法1）考慮問(wèn)題的思路應(yīng)用一個(gè)固定的非線性映射Φ，將原始數(shù)據(jù)（屬性）從輸入空間Χ映射到特征空間F，在特征空間F中使用線性學(xué)習(xí)器，提高計(jì)算能力。所考慮的假設(shè)集是形為f(x)的函數(shù)：

（非線性特征映射）即用二步法建立一個(gè)非線性學(xué)習(xí)器。2）到特征空間的隱式映射線性學(xué)習(xí)器的一個(gè)重要性質(zhì)是可以表述為對(duì)偶形式（對(duì)偶變量）針對(duì)上述變換后的假設(shè)如果能找到一種方式，避開(kāi)對(duì)特征映射Φ的顯式運(yùn)算，而在特征空間F中直接計(jì)算內(nèi)積，則可得到假設(shè)函數(shù)在對(duì)偶空間上的表示：原問(wèn)題化為對(duì)偶空間（）上的一個(gè)線性學(xué)習(xí)問(wèn)題，而特征空間F本身的維數(shù)N

和特征映射的顯式表示不再影響計(jì)算。3）核函數(shù)方法

核的使用，避免了特征向量的顯式表示，而用原始數(shù)據(jù)隱式表達(dá)了特征空間，并在對(duì)偶空間上直接訓(xùn)練線性學(xué)習(xí)器。關(guān)于訓(xùn)練樣例的唯一信息是它們?cè)谔卣骺臻g上的Gram矩陣,稱為核矩陣()，用粗體表示ii）核的幾個(gè)簡(jiǎn)單例子（pp.28-29）iii）核函數(shù)方法的特點(diǎn)內(nèi)積特征空間ii)核的幾個(gè)簡(jiǎn)單例子特征：自由度為d

的多項(xiàng)式返回3.4節(jié)iii）核函數(shù)方法的特點(diǎn)直觀想法：①創(chuàng)建一個(gè)復(fù)雜的特征空間②尋找該特征空間上適當(dāng)?shù)膬?nèi)積③尋找一種直接的方法，用原始輸入計(jì)算該值實(shí)際做法：①直接定義一個(gè)核函數(shù)②通過(guò)它隱式地定義了特征空間（因此，在計(jì)算內(nèi)積時(shí)，在學(xué)習(xí)器的設(shè)計(jì)中，都避開(kāi)了具體的特征空間）3、關(guān)于核函數(shù)的討論1）核函數(shù)的性質(zhì)和Mercer定理2）再生核希爾伯特空間（RKHS）

(ReproducingKernelHilbertSpace)3）從核函數(shù)出發(fā)構(gòu)造核函數(shù)4）從特征出發(fā)構(gòu)造核函數(shù)1）核函數(shù)的性質(zhì)和Mercer定理i）對(duì)稱性：

ii）Cauchy-Schward不等式：

iii）非負(fù)定性——Mercer定理

a）是有限個(gè)輸入組成的空間，是上對(duì)稱函數(shù)

b)更一般情形iii）非負(fù)定性——Mercer定理a）是有限個(gè)輸入組成的空間，是上對(duì)稱函數(shù)：是核函數(shù)矩陣是半正定的（非負(fù)定）（證明：p.30命題3.5）實(shí)際對(duì)應(yīng)特征映射

其中λt是K的第t個(gè)特征值，vt是λt對(duì)應(yīng)的特征向量。有限維輸入下，Mercer定理的證明（命題3.5）命題3.5證明（續(xù)）iii）非負(fù)定性——Mercer定理（續(xù)）b)一般情形（輸入的個(gè)數(shù)可能無(wú)限）①M(fèi)ercer定理：設(shè)輸入空間是緊子集，假設(shè)K是連續(xù)對(duì)稱函數(shù)。任意對(duì)稱，非負(fù)定函數(shù)可以看作平方可積函數(shù)空間上的一個(gè)內(nèi)積。①M(fèi)ercer定理的說(shuō)明假設(shè)K是連續(xù)對(duì)稱函數(shù)b)一般情形的說(shuō)明（續(xù)）決策函數(shù)在原輸入空間上的表示決策函數(shù)在對(duì)偶空間上的表示2）再生核希爾伯特空間（RKHS）

(ReproducingKernelHilbertSpace)函數(shù)空間H

的引進(jìn)及其產(chǎn)生的問(wèn)題核K對(duì)于H中函數(shù)的再生性

iii）RKHS及其作用i）函數(shù)空間H的引進(jìn)及其產(chǎn)生的問(wèn)題

函數(shù)空間H

的引進(jìn)：(假設(shè)空間的轉(zhuǎn)換）引進(jìn)一個(gè)函數(shù)空間H，H是特征空間F在映射T下的映像

由定義在輸入空間X上的函數(shù)組成i）問(wèn)題的產(chǎn)生（續(xù)）在無(wú)窮維F的情況下：H可能不包括所有可能的假設(shè)函數(shù)（它們可能是在F中沒(méi)有有限范數(shù)的點(diǎn)的映像）H可能包括過(guò)多的函數(shù)（不利于計(jì)算、以及泛化性）提出RKHS,就是為了保證H確切地包含假設(shè)集，且有一定的附加性質(zhì)。ii）核K對(duì)于H中函數(shù)的再生性ii)核K對(duì)于H中函數(shù)的再生性（續(xù)）iii)再生核希爾伯特空間（RKHS）及其作用iii)再生核希爾波特空間(RKHS)及其作用(續(xù))③④iii）Mercer核和

再生核希爾伯特空間（RKHS）結(jié)論:(th.3.10,p.37）對(duì)定義在域上的每一個(gè)Mercer核存在一個(gè)由定義在X上的函數(shù)所組成的RKHS.H,其逆定理也成立：對(duì)線性有界函數(shù)的任意Hilbert空間，存在再生核函數(shù)。且此再生核是Mercer核。關(guān)于RKHS作用的一個(gè)例子（p.37,例3.11）＝t(xi)=yi與αi無(wú)關(guān)3）從核函數(shù)出發(fā)構(gòu)造核函數(shù)確認(rèn)一個(gè)對(duì)稱函數(shù)是核函數(shù)的關(guān)鍵：函數(shù)在任意有限點(diǎn)集上定義的Gram矩陣是半正定的可以從簡(jiǎn)單的核出發(fā)，構(gòu)造復(fù)雜的核:(p.38,命題3.12)4）從特征出發(fā)構(gòu)造核函數(shù)直接通過(guò)內(nèi)積的計(jì)算，從而不需要驗(yàn)證半正定性例如：前述的多項(xiàng)式核（pp.28-29）特殊：例3.15（字符串子序列核）（p.40）在非歐氏空間(離散空間)中核方法的應(yīng)用潛力在非歐氏空間(離散空間)中核方法的應(yīng)用潛力_2在非歐氏空間(離散空間)中核方法的應(yīng)用潛力_34、特征空間中的計(jì)算1）核的使用，避免了顯式計(jì)算特征向量

特征映射：得到的內(nèi)嵌是非線性的，它定義了特征空間的n維子流形；此時(shí)，特征空間F中可以用對(duì)偶形式表示的點(diǎn)，即：映像的線性組合通常不對(duì)應(yīng)任意輸入點(diǎn)的映像（即，不一定找得到其在X中的關(guān)于的原像點(diǎn)），但仍然可以計(jì)算這些點(diǎn)之間的距離和內(nèi)積。2）具體計(jì)算方法2）