基于e-范數的學習推廣能力與計算復雜性.pdf

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

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

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

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

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