基于e-范數(shù)的學(xué)習(xí)推廣能力與計算復(fù)雜性.pdf

1、我們已經(jīng)知道基于VC(Vapnik-Chenronenkis)維及其推廣FS(Fat-Shattering)維的統(tǒng)計學(xué)習(xí)理論以及在此理論基礎(chǔ)上構(gòu)造的通用學(xué)習(xí)機器——支持向量機(SVMs)的關(guān)技術(shù)．由于其強大的功能和優(yōu)良的特性，近幾年來SVMs技術(shù)已經(jīng)廣泛應(yīng)用于文本分類，圖像識別，生物信息學(xué)等領(lǐng)域．盡管如此，基于VC維的學(xué)習(xí)理論仍然存在不足．主要表現(xiàn)為有關(guān)推廣能力的界可能太大甚至不切實際：在算法的某些實現(xiàn)中表現(xiàn)為收斂速度慢，所需訓(xùn)練樣本大

2、，錯誤率高等缺陷．因此，尋找能夠更為精確地描述推廣性能和算法復(fù)雜性的參數(shù)就顯得很有意義． 近幾年來，人們在這一方面的探索取得了一定的成果．其中基于Banach空間局部理論的e-范數(shù)為研究學(xué)習(xí)問題的的推廣性能提供了一個表現(xiàn)良好的參數(shù)．已經(jīng)證明如果Banach空間的對偶單位球的經(jīng)驗e-范數(shù)是有界的，那么它的對稱凸包具有一個有著較小直徑的k階余維的部分．而且決定該部分的泛函可以經(jīng)驗的算出．依據(jù)經(jīng)驗數(shù)據(jù)尋求所期望的依賴關(guān)系的學(xué)習(xí)問題可以

3、歸結(jié)為解一個線性方程組的問題．本文在此基礎(chǔ)上利用Banach空間的幾何結(jié)構(gòu)進一步研究了學(xué)習(xí)問題的推廣性能，給出了統(tǒng)計量復(fù)雜性(Statistic Complexity)的概念及其界的估計．本文的主要內(nèi)容安排如下： 第一章：引言．主要介紹學(xué)習(xí)問題的背景和研究方法以及本文的主要結(jié)果． 第二章：介紹基于VC維及其推廣FS維的統(tǒng)計學(xué)習(xí)理論．主要包括學(xué)習(xí)問題收斂性的定性分析和定量分析以及SVMs的思想和方法． 第三章：介紹

4、Banach空間和e-范數(shù)的有關(guān)理論．回顧了Banach空間，e-范數(shù)。覆蓋數(shù)及其與e-范數(shù)的關(guān)系，VC維與e-范數(shù)的關(guān)系等后面將要用到的基本概念和重要結(jié)論． 第四章：基于前面幾章所提得到的已有結(jié)果，我們首先給出了基于經(jīng)驗e-范數(shù)的樣本誤差的界．然后依據(jù)Banach空間中稱為Gauss型的幾何特性，我們又得到了基于Gauss型的樣本誤差的界及樣本復(fù)雜性估計．最后．在Pojor和Tomczak Jaegermann的一個重要結(jié)論的

5、基礎(chǔ)上我們總結(jié)了基于e-范數(shù)求解學(xué)習(xí)問題的方法． 第五章：這一章主要研究了基于e-范數(shù)求解學(xué)習(xí)問題的算法復(fù)雜性．我們把為了達到一定的精度所需構(gòu)造的經(jīng)驗泛函的最小個數(shù)定義為假設(shè)空間的統(tǒng)計量復(fù)雜性．利用e-范數(shù)估計了FS維具有多項式增長級的函數(shù)集的統(tǒng)計量復(fù)雜性． 據(jù)此可以找到一個基數(shù)性為統(tǒng)計量復(fù)雜性的線性經(jīng)驗泛函集，利用該線性經(jīng)驗泛函集可以構(gòu)造以所需的任意精度逼近未知函數(shù)的學(xué)習(xí)算法．同時，給出了隨機生成這些經(jīng)驗泛函的方法．