模式識(shí)別12_統(tǒng)計(jì)學(xué)習(xí)

1、2007-6-261統(tǒng)計(jì)學(xué)習(xí)理論2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2概要機(jī)器學(xué)習(xí)的基本問(wèn)題和方法統(tǒng)計(jì)學(xué)習(xí)理論VC維和風(fēng)險(xiǎn)的界結(jié)構(gòu)風(fēng)險(xiǎn)最小化)v)v2007-6-263機(jī)器學(xué)習(xí)的基本問(wèn)題和方法 機(jī)器學(xué)習(xí)問(wèn)題的表示機(jī)器學(xué)習(xí)問(wèn)題的基本模型：預(yù)測(cè)輸出yy輸入x輸出y系統(tǒng)（S）F ( x, y)學(xué)習(xí)機(jī)器（LM）f ( x , ), 2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential4組成 。學(xué)習(xí)問(wèn)題就是

2、：從給定的函數(shù)集 f ( x , ) , 中選擇出能夠最好地逼近系統(tǒng)響應(yīng)的函數(shù)。這種選擇是基于訓(xùn)練集的。訓(xùn)練集由根據(jù)聯(lián)合F ( x , y )1)nn（i.i.d.）觀測(cè) ( x 1 , y, ( x, y), L輸入x輸出y預(yù)測(cè)輸出yy系統(tǒng)（S）F(x, y)學(xué)習(xí)機(jī)器（LM）f ( x, ), L ( y , f ( x , ) = PageWriting Solid Code Module 12007-6-26 Microsoft Confidential何謂最好 風(fēng)險(xiǎn)最小化準(zhǔn)則損失函數(shù)：風(fēng)險(xiǎn)函數(shù)：L( y, f ( x, )R( ) = L( y, f ( x, )dF ( x, y)三

3、種主要學(xué)習(xí)問(wèn)題的損失函數(shù)：y = f ( x , )y f ( x , ) 0 1L ( y , f ( x , ) = ( y f ( x , ) 2L ( p ( x , ) = lo g ( p ( x , )5模式識(shí)別問(wèn)題函數(shù)擬合問(wèn)題密度估計(jì)問(wèn)題2007-6-266學(xué)習(xí)的目標(biāo)就是：在聯(lián)合概率分布函數(shù) F(x,y) 未知，所有可用的信息都包含在訓(xùn)練數(shù)據(jù)集中的情況下，尋找函數(shù)使它（在函數(shù)類f ( x , ) , ）最小化風(fēng)險(xiǎn)泛函f ( x , 0 )R ( )2007-6-26。 log( p ( x , )7函數(shù)擬合問(wèn)題： 最小二乘模式識(shí)別：使訓(xùn)練集樣本錯(cuò)誤率最低的分類器機(jī)器學(xué)習(xí)的基本問(wèn)

4、題和方法經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化(ERM)R em p1NL ( y , f ( x , )Ni = 1( ) =1NNi = 1R e m p ( ) =( y f ( x i , ) 2i1NNi =1概率密度估計(jì)： 最大似然方法 Rem p ( ) =2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential82007-6-26經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化方法的問(wèn)題有限樣本下：經(jīng)驗(yàn)風(fēng)險(xiǎn)最小是否是期望風(fēng)險(xiǎn)最??？以經(jīng)驗(yàn)風(fēng)險(xiǎn)最小得到的解，其期望風(fēng)險(xiǎn)如何？如果存在多個(gè)使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的解的情況(比如線性可分的情況)，那一個(gè)使期望風(fēng)險(xiǎn)最小

5、？2007-6-269機(jī)器學(xué)習(xí)的基本問(wèn)題和方法 復(fù)雜性與推廣能力例1：函數(shù)擬合 f(x , ) = sin(x)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小并不意味著期望風(fēng)險(xiǎn)最小。2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential10例2：模式識(shí)別以經(jīng)驗(yàn)風(fēng)險(xiǎn)最小得到的解，其期望風(fēng)險(xiǎn)可能很大PageWriting Solid Code Module 12007-6-26 Microsoft Confidential過(guò)擬合，過(guò)學(xué)習(xí)（overfitting）2007-6-262007-6-261112過(guò)擬合，過(guò)學(xué)習(xí)（overfitting

6、）過(guò)擬合，過(guò)學(xué)習(xí)（overfitting）13142007-6-26例3: 線性可分問(wèn)題經(jīng)驗(yàn)風(fēng)險(xiǎn)都為0，那一個(gè)使期望風(fēng)險(xiǎn)最小？2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential統(tǒng)計(jì)學(xué)習(xí)理論VC維和風(fēng)險(xiǎn)的界 VC維描述學(xué)習(xí)機(jī)器的復(fù)雜性線性函數(shù)正弦函數(shù)的VC維R ( )Remp ( ) + ?15162007-6-26推廣性的界的定理：R ( ) R e m p ( ) + ( n / h )其中n為樣本數(shù)，h為學(xué)習(xí)機(jī)器VC維，(n / h)稱為置信范圍或VC信任。(n / h)是隨n / h增大而減小的

7、函數(shù)。由上式可知：n / h越小，(n / h)越大，用經(jīng)驗(yàn)風(fēng)險(xiǎn)近似期望風(fēng)險(xiǎn)就有較大的誤差，用經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化取得的最優(yōu)解可能具有較差的推廣性。而n / h較大，則期望風(fēng)險(xiǎn)最小化得到的最優(yōu)解就接近實(shí)際的最優(yōu)解。2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential17R ( ) R em p ( ) + ( n / h ) ( n / h )是 隨 n / h 增 大 而 減 小 的 函 數(shù)對(duì)于特定的問(wèn)題，樣本數(shù)目n一般是固定的，VC維h越大，真實(shí)風(fēng)險(xiǎn)與期望風(fēng)險(xiǎn)間的差就越大。因此我們?cè)谠O(shè)計(jì)分類器時(shí)，不但要使

8、經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化，還要使機(jī)器的復(fù)雜性也即VC維盡量小，從而使期望風(fēng)險(xiǎn)最小。2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential182007-6-26VC維與推廣性的界的討論：函數(shù)集的VC維不一定等于自由參數(shù)的個(gè)數(shù)。尚無(wú)一般方法對(duì)任意函數(shù)集計(jì)算VC維。推廣性的界是對(duì)最壞情況下的結(jié)論，所給出的界往往是松的。近鄰法的討論：近鄰法的VC維無(wú)窮大，但推廣性較好。VC維的條件:各子集的VC維有限損失函數(shù)的條件:有界非負(fù)滿足或者對(duì)一定的參數(shù)對(duì)滿足：結(jié)構(gòu)風(fēng)險(xiǎn)最小化設(shè)計(jì)學(xué)習(xí)機(jī)器的目標(biāo)：同時(shí)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍。如何同時(shí)

9、最小化結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則把函數(shù)集S分解為一個(gè)函數(shù)子集序列（子集結(jié)構(gòu)） S1 S2 Sk S,使得各子集能夠按照VC維的大小排列h1 h2 hk ，這樣同一個(gè)子集中的置信范圍就相同。容許子集結(jié)構(gòu)的條件：1920(n / h)2007-6-26結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則（SRM）2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential兩種構(gòu)造性方法：21222007-6-26理論如何應(yīng)用到SVMSVM的直觀形式2007-6-26PageWriting Solid Code Module 12007-6-26 Micro

10、soft Confidential沒(méi)有免費(fèi)的午餐在很多的算法中，哪一個(gè)是最好的？?jī)蓚€(gè)分類器A和B在訓(xùn)練集上有同樣好的性能，我們更喜歡簡(jiǎn)單的分類器。為什么？23242007-6-26我們更喜歡比較平滑的分類器。為什么？2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential守恒定律物理學(xué)守恒定律：能量守恒，熱力學(xué)第二定律模式識(shí)別領(lǐng)域是否存在類似的定理？2526舉例2007-6-26訓(xùn)練集測(cè)試集兩個(gè)分類器2007-6-26PageWriting Solid Code Module 12007-6-26 Micr

11、osoft Confidential沒(méi)有免費(fèi)的午餐2007-6-262007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2728圖示說(shuō)明沒(méi)有免費(fèi)的午餐不存在任何一種模式分類算法具有天然的優(yōu)越性，甚至不比隨機(jī)猜測(cè)更好。如果某種算法對(duì)某個(gè)特定的問(wèn)題看上去比另一種算法更好，其原因僅僅是它更適合這一特定的模式分類任務(wù)。2007-6-262007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2930舉例舉例50 points

12、 from a Gaussian Distribution (3 times)Blue: original distributionRed: estimated distributionGreen: samples31322007-6-26舉例500 points from a uniform DistributionBlue: original distributionRed: estimated distributionGreen: samples2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential

13、非參數(shù)估計(jì)33342007-6-26非參數(shù)估計(jì)2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential沒(méi)有免費(fèi)的午餐對(duì)于要解決的分類問(wèn)題，什么是事物的本質(zhì)？先驗(yàn)信息數(shù)據(jù)的分布訓(xùn)練樣本的數(shù)量代價(jià)函數(shù)35362007-6-26特征與模式是否存在最好的特征表示？2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2007-6-2637特征與模式4個(gè)人：正常，左眼瞎，右眼瞎，全瞎2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential38丑小鴨定理如果只使用有限的謂詞集合來(lái)區(qū)分待研究的任意兩個(gè)模式，那么任意這樣兩個(gè)模式所共享的謂詞數(shù)目是一個(gè)與模式的選擇無(wú)關(guān)的常數(shù)。此外，如果模式的相似