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

CH.3核函數(shù)特征空間《導論》pp.24-46需要學習的目標函數(shù)的復雜度取決于它的表示（自變元個數(shù)、定義域、函數(shù)關系式、……），學習任務的難易程度隨之而變化。線性學習器計算能力有限核表示方法的特點使用線性學習器分二類問題

分二類問題

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

當f(x)0

時，輸入賦給正類；當

f(x)0

時，輸入賦給負類。線性學習器

使用線性假設

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

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

使用不同技術的困難所在1、特征空間和特征選擇問題

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

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

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

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

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

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

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

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

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

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

ii）Cauchy-Schward不等式：

iii）非負定性——Mercer定理

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

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

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

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

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

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

函數(shù)空間H

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

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

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

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