機(jī)會(huì)空間上學(xué)習(xí)理論的關(guān)鍵定理

王 芬

(湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 湖北 黃石 435002)

0 引言

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

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

在文獻(xiàn)[4，12]中，哈明虎等人在Sugeno空間和擬概率空間上分別證明了統(tǒng)計(jì)學(xué)習(xí)理論中的相關(guān)理論。因此，本文借助機(jī)會(huì)測(cè)度這一橋梁將統(tǒng)計(jì)學(xué)習(xí)理論中的關(guān)鍵定理推廣到機(jī)會(huì)空間中去，在機(jī)會(huì)空間中證明學(xué)習(xí)理論的關(guān)鍵定理。

1 預(yù)備知識(shí)

首先對(duì)概率空間上的隨機(jī)變量和可信性空間上的模糊變量作出定義，再給出機(jī)會(huì)空間的定義和機(jī)會(huì)測(cè)度的定義以及性質(zhì).

1.1 模糊變量

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

1)Cr{Θ}=1

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

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

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

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

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

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

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

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

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

1.2 混合變量

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

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

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

注2. 在上面的定義中，沒有規(guī)定Λ(w) 的可測(cè)性，這是因?yàn)棣?w) 是Θ的子集，而可信性空間中的σ-代數(shù)定義為冪集，所以Θ的所有子集都是可測(cè)的.

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

定義7(機(jī)會(huì)測(cè)度)可測(cè)集Λ的機(jī)會(huì)測(cè)度定義為

1.3 機(jī)會(huì)測(cè)度的性質(zhì)

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

2)機(jī)會(huì)單調(diào)性 如果可測(cè)集Λ1?Λ2, 則有Ch{Λ1}≤Ch{Λ2};

3)機(jī)會(huì)次可加性 對(duì)于任意可測(cè)集Λ1，Λ2有Ch{Λ1∪Λ2}≤Ch{Λ1}+Ch{Λ2}

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

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

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

為了在機(jī)會(huì)空間上討論統(tǒng)計(jì)學(xué)習(xí)理論的關(guān)鍵定理，下面給出機(jī)會(huì)空間上的Markov不等式,Chebyshev不等式和辛欽大數(shù)定律.

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

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

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

2 機(jī)會(huì)空間上學(xué)習(xí)理論的關(guān)鍵定理

設(shè)Φ(x)是一個(gè)混合變量ξ的機(jī)會(huì)分布函數(shù)，z1,z2,…,zl是一組獨(dú)立同分布的樣本，引入集函數(shù)Q(z,α),α∈Λ，期望風(fēng)險(xiǎn)泛函和經(jīng)驗(yàn)風(fēng)險(xiǎn)泛函定義如下：

則經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則(ERM)就是用經(jīng)驗(yàn)風(fēng)險(xiǎn)泛函Remp(α) 最小化代替期望風(fēng)險(xiǎn)泛函R(α)最小化.

2.1 機(jī)會(huì)空間上的學(xué)習(xí)理論的關(guān)鍵定理

證明 必要性.設(shè)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化方法在函數(shù)集Q(z,α),α∈Λ上是嚴(yán)格一致的.

(1)

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

也就是說如果M出現(xiàn)，則Tk出現(xiàn)，那么T也出現(xiàn).

由機(jī)會(huì)測(cè)度的單調(diào)性可知Ch{M}≤Ch{T} 成立，所以

(2)

成立.即經(jīng)驗(yàn)風(fēng)險(xiǎn)一致單邊收斂于期望風(fēng)險(xiǎn).

充分性.現(xiàn)假設(shè)(2)成立.下面證明嚴(yán)格一致性成立.

其中

(3)

另一方面，假設(shè)N2發(fā)生，則?α**∈Λ,使

所以

(4)

3 結(jié)論

本文利用機(jī)會(huì)測(cè)度的次可加性等性質(zhì)首次給出并證明了機(jī)會(huì)空間上學(xué)習(xí)理論的關(guān)鍵定理，為在機(jī)會(huì)空間上構(gòu)建支持向量機(jī)奠定理論基礎(chǔ).本文進(jìn)一步研究?jī)?nèi)容是研究機(jī)會(huì)空間上學(xué)習(xí)過程一致收斂速度的界及VC維的推廣性的界，建立結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，構(gòu)建支持向量機(jī).

參考文獻(xiàn):

[1]Vapnik V N.統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)[M]. 張學(xué)工,譯.北京:清華大學(xué)出版社,2000.

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

[3]張學(xué)工.關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào),2000,26(1):32～42.

[4]哈明虎,李 顏,李 嘉,等.Sugeno測(cè)度空間上學(xué)習(xí)理論的關(guān)鍵定理和一致收斂速度的界[J].中國科學(xué)(E輯) :信息科學(xué),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]哈明虎,馮志芳,宋士吉,等. 擬概率空間上學(xué)習(xí)理論的關(guān)鍵定理和學(xué)習(xí)過程一致收斂速度的界[J].計(jì)算機(jī)學(xué)報(bào), 2008,3(31):476～485.

[13]李 想. 機(jī)會(huì)測(cè)度及其應(yīng)用[D].北京：清華大學(xué)，2008.