機會空間上學習理論的關鍵定理

王 芬

(湖北師范學院 數學與統計學院， 湖北 黃石 435002)

0 引言

統計學習理論(SLT)是由Vapnik等人[1～2]在20世紀60年代末提出并逐漸建立起來的一種在小樣本情況下研究統計學習規律的理論，它的核心思想是通過對學習機器容量進行控制進而研究學習機器的推廣能力，支持向量機(SVM)是這一理論的研究成果。近幾十年來，統計學習理論及支持向量機越來越受到國內外學者的關注[1～5]，同時也將這一理論應用到很多其他的領域，如數據分析、金融預測、交通流量控制等等，可參見文獻[5～8]。統計學習理論已被學術界公認為是機器學習領域一個新的研究熱點。

統計學習理論主要由4部分內容組成[1]，而本文主要是在另一空間中研究學習理論的關鍵定理。統計學習理論中關鍵定理是將經驗風險最小化的嚴格一致性的問題轉化為求均值一致單邊收斂于數學期望的存在性問題.由于統計學習理論是建立在概率空間中的，而概率空間中的概率是要滿足可加性的非負集函數，但這個條件在實際中不容易得到滿足，因此對非可加測度的研究是必要的。目前，比較有代表性的非可加測度有Sugeno測度、擬概率和可信性測度等[9，10].在2001年，Liu[11]首先提出了機會測度，而李想博士在他的博士論文[12]中對機會測度作了具體而全面的闡述，機會測度結合了概率測度與可信性測度的特點，具有廣泛的研究意義。

在文獻[4，12]中，哈明虎等人在Sugeno空間和擬概率空間上分別證明了統計學習理論中的相關理論。因此，本文借助機會測度這一橋梁將統計學習理論中的關鍵定理推廣到機會空間中去，在機會空間中證明學習理論的關鍵定理。

1 預備知識

首先對概率空間上的隨機變量和可信性空間上的模糊變量作出定義，再給出機會空間的定義和機會測度的定義以及性質.

1.1 模糊變量

定義1(可信性空間)設Θ是一個非空集合，ρ是Θ的冪集.如果集函數Cr滿足下面條件：

1)Cr{Θ}=1

2)如果A?B, 則Cr{A}≤Cr{B}

3)對于任意A∈ρ, 有Cr{A}+Cr{Ac}=1;

4)對于ρ中任意集族{Ai} ，如果 supiCr{Ai}<0.5,則Cr{UiAi}=supiCr{Ai}

則稱Cr為可信性測度.此時，稱三元組(Θ,ρ,Cr} 為一個可信性空間.

定義2(模糊變量)模糊變量ξ是一個從可信性空間 (Θ,ρ,Cr)到實數集的函數.

注1. 由于可信性空間中的σ- 代數ρ是Θ的冪集，因此所有定義在可信性空間上的函數都是可測的.

定義3(可信性分布函數)模糊變量ξ的可信性分布函數Φ：→[0,1] 定義為

Φ(x)=Cr{θ∈Θ|ξ(θ)≤x}

即Φ(x)表示ξ的取值小于等于x的可信性測度.

1.2 混合變量

定義4(機會空間)如果(Θ,ρ,Cr) 是一個可信性空間， (Ω,A,Pr)是一個概率空間[15]，那么乘積空間(Θ,ρ,Cr)×(Ω,A,Pr) 叫做機會空間.

機會空間中的論域定義為Θ與Ω的笛卡爾乘積，即Θ×Ω={(θ,w)|θ∈Θ,w∈Ω},設Λ是Θ×Ω的一個子集，記Λ(w)={θ∈Θ|(θ,w)∈Λ},Λ(θ)={w∈Ω|(θ,w)∈Λ}

定義5(可測集)設Λ是Θ×Ω的一個子集，如果對于任意的θ∈Θ, 都有Λ(θ)∈A，則稱Λ為可測集.

注2. 在上面的定義中，沒有規定Λ(w) 的可測性，這是因為Λ(w) 是Θ的子集，而可信性空間中的σ-代數定義為冪集，所以Θ的所有子集都是可測的.

定義6(混合變量)混合變量ξ定義為從(Θ,ρ,Cr)×(Ω,A,Pr) 到實數集的一個可測函數，即對于任意Borel集合B，有{ξ∈B}∈ρ×A

定義7(機會測度)可測集Λ的機會測度定義為

1.3 機會測度的性質

1)Ch{Θ×Ω}=1,Ch{?}=0,0≤Ch{Λ}≤1;

2)機會單調性 如果可測集Λ1?Λ2, 則有Ch{Λ1}≤Ch{Λ2};

3)機會次可加性 對于任意可測集Λ1，Λ2有Ch{Λ1∪Λ2}≤Ch{Λ1}+Ch{Λ2}

定義8(機會分布函數) 混合變量ξ的機會分布Φ:(-∞,+∞)→[0,1] 定義為

Φ(x)=Ch{(θ,ω)∈Θ×Ω|ξ(θ,w)≤x}

定義10(方差) 若ξ是一個期望值有限的混合變量，則ξ的方差定義為V(ξ)=E(ξ-Eξ)2.

為了在機會空間上討論統計學習理論的關鍵定理，下面給出機會空間上的Markov不等式,Chebyshev不等式和辛欽大數定律.

引理1[13](Markov不等式) 設ξ是一個混合變量,則對任意的t>0,p>0,有

引理2[13](Chebyshev不等式) 設ξ是一個混合變量且方差V(ξ)存在,則對任意給定的t>0,有

證明 由概率空間和Sugeno空間上的辛欽大數定律[4]及引理1、2可知該定理成立. 證畢

2 機會空間上學習理論的關鍵定理

設Φ(x)是一個混合變量ξ的機會分布函數，z1,z2,…,zl是一組獨立同分布的樣本，引入集函數Q(z,α),α∈Λ，期望風險泛函和經驗風險泛函定義如下：

則經驗風險最小化原則(ERM)就是用經驗風險泛函Remp(α) 最小化代替期望風險泛函R(α)最小化.

2.1 機會空間上的學習理論的關鍵定理

證明 必要性.設經驗風險最小化方法在函數集Q(z,α),α∈Λ上是嚴格一致的.

(1)

由選定的Λ(ak) ，可知下面不等式成立：

也就是說如果M出現，則Tk出現，那么T也出現.

由機會測度的單調性可知Ch{M}≤Ch{T} 成立，所以

(2)

成立.即經驗風險一致單邊收斂于期望風險.

充分性.現假設(2)成立.下面證明嚴格一致性成立.

其中

(3)

另一方面，假設N2發生，則?α**∈Λ,使

所以

(4)

3 結論

本文利用機會測度的次可加性等性質首次給出并證明了機會空間上學習理論的關鍵定理，為在機會空間上構建支持向量機奠定理論基礎.本文進一步研究內容是研究機會空間上學習過程一致收斂速度的界及VC維的推廣性的界，建立結構風險最小化原則，構建支持向量機.

參考文獻:

[1]Vapnik V N.統計學習理論的本質[M]. 張學工,譯.北京:清華大學出版社,2000.

[2]Vapnik V N.An overview of statistical learning theory[J].IEEE Transactions on Neural Networks, 1999, 10(5) : 988～999.

[3]張學工.關于統計學習理論與支持向量機[J].自動化學報,2000,26(1):32～42.

[4]哈明虎,李 顏,李 嘉,等.Sugeno測度空間上學習理論的關鍵定理和一致收斂速度的界[J].中國科學(E輯) :信息科學,2006,36(4):398～410.

[5]Wechsler H, Duric Z, Li Fa-Yin,et al.Motion estimation using statistical learning theory[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(4):466～ 478.

[6]Zhan Yi-Qing, Shen Ding-Gang. Design efficient support vector machine for fast classification[J]. Pattern Recognition,2005,38(1):157～161.

[7]Jeng J T. Hybrid approach of selecting hyper-parameters of support vector machine for regression[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2005, 36(3):699～709.

[8]Jin Bo, Tang Y C, Zhang Yan-Qing. Support vector machines with genetic fuzzy feature transformation for biomedical data classification[J].Information Sciences,2007,177:476～489.

[9]Choquet G .Theory of capacities[J]. Annal es del Institute Fourier,1954,5:131～295.

[10]Liu Bao-Ding.Theory and Practice of Uncertain Programming[M].Heidelberg: Physica-Verlag,2003.

[11]Liu B. Fuzzy random chance-constrained programming[J]. IEEE Transactions on Fuzzy Systems, 2001, 9(5):713～720.

[12]哈明虎,馮志芳,宋士吉,等. 擬概率空間上學習理論的關鍵定理和學習過程一致收斂速度的界[J].計算機學報, 2008,3(31):476～485.

[13]李 想. 機會測度及其應用[D].北京：清華大學，2008.