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

分二類問題

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

當f(x)0

時，輸入賦給正類；當

f(x)0

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

使用線性假設

確定最優超平面，其控制參數為而決策規則由

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

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

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

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

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

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

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

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

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

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

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

(ReproducingKernelHilbertSpace)3）從核函數出發構造核函數4）從特征出發構造核函數1）核函數的性質和Mercer定理i）對稱性：

ii）Cauchy-Schward不等式：

iii）非負定性——Mercer定理

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

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

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

(ReproducingKernelHilbertSpace)函數空間H

的引進及其產生的問題核K對于H中函數的再生性

iii）RKHS及其作用i）函數空間H的引進及其產生的問題

函數空間H

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

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

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

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