1.1.5 結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則

推廣性是機(jī)器學(xué)習(xí)的一個(gè)關(guān)鍵性能指標(biāo)，在訓(xùn)練樣本數(shù)目有限的情況下，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化并不能代表實(shí)際風(fēng)險(xiǎn)最小化。統(tǒng)計(jì)學(xué)習(xí)理論指出，經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則下的學(xué)習(xí)機(jī)器的實(shí)際風(fēng)險(xiǎn)，由以下兩部分組成：

式中，R_emp（w）是訓(xùn)練樣本的經(jīng)驗(yàn)風(fēng)險(xiǎn)；為置信風(fēng)險(xiǎn)Φ；N為訓(xùn)練樣本數(shù)量；h為函數(shù)集的VC維。當(dāng)0＜η＜1時(shí)，實(shí)際風(fēng)險(xiǎn)R（w）與經(jīng)驗(yàn)風(fēng)險(xiǎn)R_emp（w）以概率1-η滿足式（1.1.7）中的關(guān)系，概率1-η稱為置信水平。

由式（1.1.7）可知，置信風(fēng)險(xiǎn)Φ不但受置信水平1-η的影響，同時(shí)也受函數(shù)集的VC維h和樣本數(shù)N的影響。且隨著N/h的增加，置信風(fēng)險(xiǎn)Φ單調(diào)減小。

經(jīng)驗(yàn)風(fēng)險(xiǎn)與期望風(fēng)險(xiǎn)之間的差距，即置信風(fēng)險(xiǎn)Φ（N/h）反映了根據(jù)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則得到的學(xué)習(xí)機(jī)器的推廣能力，稱為推廣性的界。式（1.1.7）表明，當(dāng)N/h較小時(shí)，置信風(fēng)險(xiǎn)Φ（N/h）較大，此時(shí)，利用經(jīng)驗(yàn)風(fēng)險(xiǎn)代替實(shí)際風(fēng)險(xiǎn)造成的誤差很大，用經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化取得的最優(yōu)解的推廣性也很差。所以，在機(jī)器學(xué)習(xí)過程中，不但要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，還要利用VC維來盡可能地縮小置信風(fēng)險(xiǎn)，這樣才能取得較小的實(shí)際風(fēng)險(xiǎn)，對未知樣本的推廣性也更好。

為了兼顧VC維和置信風(fēng)險(xiǎn)，引進(jìn)了結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則。

結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則是尋找一個(gè)假設(shè)f，使式（1.1.7）右端所示的結(jié)構(gòu)風(fēng)險(xiǎn)達(dá)到最小值。

設(shè)N個(gè)訓(xùn)練樣本為（x（1），y（1）），（x（2），y（2）），…，（x（N），y（N）），選擇一系列嵌套的假設(shè)集F₁?F₂?…?F_N，在對應(yīng)的每個(gè)F_N中找出一個(gè)假設(shè)f（N）使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，這樣可以得到一系列的假設(shè)f（1），f（2），…，f（N）。由于F_N的VC維是遞增的，即h（1）＜h（2）＜…＜h（N），所以置信風(fēng)險(xiǎn)Φ也是遞增的，即隨著N的增大而增大。而經(jīng)驗(yàn)風(fēng)險(xiǎn)則隨著N的增 大 而 減 小，即R_emp[f（1）]＞R_emp[f（2）]＞…＞R_emp[f（N）]。因?yàn)榧僭O(shè)集F_N是嵌套的，所以結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則就是尋找合適的N₀，使置信風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)之和最小，并且得到相應(yīng)的f_N0。

結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的示意圖如圖1.1.3所示。圖中，假設(shè)集S₁?S₂?S₃，其對應(yīng)的VC維h₁＜h₂＜h₃。該圖很直觀地表明，經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信風(fēng)險(xiǎn)是一對矛盾，S₂對應(yīng)于最佳的假設(shè)集子集，經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信風(fēng)險(xiǎn)在此時(shí)之和最小，對應(yīng)的真實(shí)風(fēng)險(xiǎn)在此時(shí)也達(dá)到最小。

圖1.1.3 結(jié)構(gòu)風(fēng)險(xiǎn)最小化示意圖

與經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化相比，結(jié)構(gòu)風(fēng)險(xiǎn)最小化很明顯更加合理，通過對經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信風(fēng)險(xiǎn)的折中，得到的結(jié)構(gòu)風(fēng)險(xiǎn)更接近實(shí)際風(fēng)險(xiǎn)。而支持向量機(jī)就是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則。