離散Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界

羅亭亭, 李本崇

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 西安 710126)

Bayes網(wǎng)絡(luò)[1], 也稱為概率網(wǎng)絡(luò)、 信念網(wǎng)絡(luò)或者因果網(wǎng)絡(luò), 是一種用有向無(wú)環(huán)圖表示隨機(jī)變量間條件獨(dú)立關(guān)系的統(tǒng)計(jì)模型, 最初主要用于處理人工智能中的不確定性信息, 目前廣泛應(yīng)用于不確定性推理和機(jī)器學(xué)習(xí)等領(lǐng)域[2-6]. Bayes網(wǎng)絡(luò)通過(guò)若干條件分布的乘積表示復(fù)雜的聯(lián)合概率分布, 因此有助于處理高維統(tǒng)計(jì)問(wèn)題.

VC(Vapnik-Chervonenkis)維數(shù)和歐氏嵌入維數(shù)是二值函數(shù)類復(fù)雜性的兩種度量[7], 離散Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類的VC維數(shù)和歐氏嵌入維數(shù)的大小備受關(guān)注. Kearns等[8]研究了一般概念學(xué)習(xí)的形式化模型, 著重研究了概念類的可學(xué)習(xí)性和一致收斂性, 并給出了許多有效算法; García-Puente等[9]給出了離散Bayes網(wǎng)的代數(shù)幾何刻畫; Nakamura等[10]給出了二值隨機(jī)變量Bayes網(wǎng)誘導(dǎo)的概念類歐氏嵌入維數(shù)的上下界, 并確定了一些特殊Bayes網(wǎng)誘導(dǎo)的概念類歐氏嵌入維數(shù)的精確值; Yang等[11-12]針對(duì)Boolean域上的二分類任務(wù), 證明了完全Bayes網(wǎng)和幾乎完全Bayes網(wǎng)誘導(dǎo)的概念類的VC維數(shù)和歐氏嵌入維數(shù)相等; Yang等[13]針對(duì)隨機(jī)變量取值均為k個(gè)的二分類問(wèn)題, 證明了任意不含有V-結(jié)構(gòu)的Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)和歐氏嵌入維數(shù)的一致性, 并給出了計(jì)算該維數(shù)的顯示公式; Yang等[14]針對(duì)變量在Boolean域取值的Bayes網(wǎng), 證明了隨機(jī)變量個(gè)數(shù)不超過(guò)5時(shí), Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類的VC維數(shù)與歐氏嵌入維數(shù)相等; Varando等[15]用Lagrange多項(xiàng)式乘積的線性組合評(píng)估Bayes網(wǎng)的表達(dá)能力, 得到了與文獻(xiàn)[13]類似的結(jié)果; Li等[16]擴(kuò)展了Yang等[13]以及Varando等[15]的結(jié)果, 證明了任意不含V-結(jié)構(gòu)的Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)和歐氏嵌入維數(shù)的一致性, 并給出了一般Bayes網(wǎng)誘導(dǎo)的概念類歐氏嵌入維數(shù)的上界(VC維數(shù)的上界). 近年來(lái), 研究者們已利用Bayes網(wǎng)絡(luò)模型解決了許多實(shí)際問(wèn)題[17-19], 但對(duì)Bayes網(wǎng)誘導(dǎo)的概念類的復(fù)雜性理論研究目前尚未見(jiàn)文獻(xiàn)報(bào)道. 當(dāng)一個(gè)網(wǎng)絡(luò)中的每個(gè)隨機(jī)變量取任意有限個(gè)值時(shí), 該Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類VC維數(shù)的下界尚無(wú)一般性結(jié)果. 因此, 基于Yang等[13]的工作, 本文考慮一般的離散Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類VC維數(shù)的下界, 為進(jìn)一步研究Bayes網(wǎng)誘導(dǎo)的概念類的復(fù)雜性做鋪墊, 并為分類任務(wù)提供理論支撐.

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

定義1[1]如果一個(gè)有向圖從任意頂點(diǎn)出發(fā), 沿任意若干條有向邊都不能回到該點(diǎn)(不含有向環(huán)), 則稱該圖是一個(gè)有向無(wú)環(huán)圖, 記作G=(V,E).每個(gè)頂點(diǎn)Xi∈V表示一個(gè)隨機(jī)變量, 一個(gè)有向邊(Xi,Xj)∈E表示Xi和Xj之間的條件依賴性, 其中V={X1,X2,…,Xn},i,j∈{1,2,…,n}且i≠j.

圖G中若(Xi,Xj)∈E, 則Xi稱為Xj的父節(jié)點(diǎn),Xj稱為Xi的子節(jié)點(diǎn).本文用PA(Xi)表示節(jié)點(diǎn)Xi的父節(jié)點(diǎn)集合,mi=|PA(Xi)|表示父節(jié)點(diǎn)的個(gè)數(shù).一個(gè)有向圖是完全的當(dāng)且僅當(dāng)給定節(jié)點(diǎn)的拓?fù)湫驎r(shí), 對(duì)每個(gè)節(jié)點(diǎn)Xi都有PA(Xi)={X1,X2,…,Xi-1}.令X,Z,Y是有向無(wú)環(huán)圖G=(V,E)的3個(gè)節(jié)點(diǎn), 如果G中包含有向邊X→Z和Y→Z, 且X和Y在G中不相鄰, 則稱(X,Z,Y)是一個(gè)V-結(jié)構(gòu), 如圖1所示.

圖1 圖G的一個(gè)V-結(jié)構(gòu)Fig.1 A V-structure of graph G

每個(gè)有向無(wú)環(huán)圖G都對(duì)應(yīng)一個(gè)概率分布族P,P由X上有如下形式的概率分布組成:

(1)

其中p(Xi|PA(Xi))表示給定父變量PA(Xi)時(shí)Xi的條件概率.

定義2(Bayes網(wǎng))[2]一個(gè)Bayes網(wǎng)由有向無(wú)環(huán)圖G=(V,E)和分布族P構(gòu)成, 記作N=(G,P).

例1如圖2所示的一個(gè)有向無(wú)環(huán)圖, 節(jié)點(diǎn)集V={X1,X2,X3,X4}, 有向邊集合E={(X1,X2),(X1,X3),(X2,X4),(X3,X4)}.由式(1)可知, 該有向無(wú)環(huán)圖對(duì)應(yīng)的概率分布族中的每個(gè)分布P滿足

圖2 一個(gè)有向無(wú)環(huán)圖Fig.2 A directed acyclic graph

P(X)=p(X1)p(X2|X1)p(X3|X1)p(X4|X2,X3).

考慮N是一個(gè)有n個(gè)節(jié)點(diǎn)X1,X2,…,Xn的Bayes網(wǎng),Xi∈[ki], 其中ki∈,ki≥2,i=1,2,…,n.易知若PA(Xi)={Xi1,Xi2,…,Xir}, 觀測(cè)向量為x=(x1,x2,…,xn), 則xpa(xi)?(xi1,xi2,…,xir).將N對(duì)應(yīng)的分布族記為DN,DN中X上的任一概率分布由如下形式表示:

(2)

記Bayes網(wǎng)絡(luò)N可自由設(shè)定的參數(shù)個(gè)數(shù)為FA(N), 基于上述討論可知參數(shù)個(gè)數(shù)應(yīng)為所有變量可自由設(shè)定的參數(shù)數(shù)目之和, 即

(3)

根據(jù)式(3), 對(duì)完全的Bayes網(wǎng)絡(luò)NF, 其可自由設(shè)定的參數(shù)個(gè)數(shù)為

(4)

例2以圖2對(duì)應(yīng)的Bayes網(wǎng)絡(luò)為例,X=(X1,X2,X3,X4),Xi取ki個(gè)值,i=1,2,3,4.若x=(1,0,1,2), 則由PA(X4)={X2,X3}可得xpa(x4)=(0,1).若變量X1,X2,X3,X4對(duì)應(yīng)的可自由設(shè)定參數(shù)個(gè)數(shù)分別為k1-1,k1(k2-1),k1(k3-1),k2k3(k4-1), 則由式(3)可得該Bayes網(wǎng)絡(luò)的可自由設(shè)定參數(shù)個(gè)數(shù)為k1-1+k1(k2-1)+k1(k3-1)+k2k3(k4-1).

定義3[10]概念類C是定義在X上的一個(gè)函數(shù)族, 滿足f:X→{-1,1}, 每個(gè)f∈C稱為一個(gè)概念.

定義4[10]一個(gè)有限集合S={s1,s2,…,sm}?X稱為被概念類C打散是指對(duì)任意m維向量b∈{-1,1}m, 存在f∈C使得f(si)=bi, 其中i=1,2,…,m.

定義5[10]概念類的VC維數(shù)定義為

VC dim(C)=sup{m|S?X,S被C打散, 且|S|=m}.

(5)

若由任意數(shù)目的樣本點(diǎn)組成的集合都能被概念類C打散, 則該概念類的VC維數(shù)即為無(wú)窮大.

(6)

由定義5和定義6可得Bayes網(wǎng)誘導(dǎo)的概念類的VC維數(shù), 將CN的VC維數(shù)記作VCdim(N).歐氏嵌入維數(shù)是用來(lái)評(píng)價(jià)Bayes網(wǎng)分類能力的另一個(gè)常用指標(biāo), 其定義如下:

定義7[10]給定X上的一個(gè)概念類C和一個(gè)具有標(biāo)準(zhǔn)內(nèi)積的d維歐氏空間, 若存在d中的向量(uf)f∈C和(vx)x∈X, 使得?f∈C,x∈X, 有則稱概念類C可以嵌入到d維歐氏空間.使C可以被嵌入d中最小的d稱為概念類C的歐氏嵌入維數(shù), 記作Edim(C).

對(duì)于一個(gè)概念類C, 如果不存在有限維的歐氏空間可以被C嵌入, 則Edim(C)為無(wú)窮大.概念類CN的歐氏嵌入維數(shù)記作Edim(N).

例3考慮圖2對(duì)應(yīng)的Bayes網(wǎng), 若Xi∈{0,1},i=1,2,3,4, 則VCdim(N)=Edim(N)=11[12].

命題1[10]對(duì)每個(gè)有限概念類C, 均有Edim(C)≥VCdim(C).

命題1表明,CN的歐氏嵌入維數(shù)是其VC維數(shù)的上界.完全Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類的VC維數(shù)和歐氏嵌入維數(shù)皆等于網(wǎng)絡(luò)中可自由設(shè)定的參數(shù)個(gè)數(shù)[20].

命題2[13]設(shè)N′是有(n-1)個(gè)變量的Bayes網(wǎng)絡(luò),N中有向無(wú)環(huán)圖去掉節(jié)點(diǎn)Xn及與之相連的有向邊后對(duì)應(yīng)的Bayes網(wǎng)為N′, 若S′?[k]n-1被N′打散且VCdim(N′)=|S′|, 則

VCdim(N)≥VCdim(N′)+(k-1)k|PA(Xn)|,

(7)

其中Xi∈[k],i=1,2,…,n.

命題2表明, 一個(gè)有n個(gè)k-值隨機(jī)變量的Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類VC維數(shù)的下界是前(n-1)個(gè)變量組成的Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類VC維數(shù)與最后一個(gè)變量對(duì)應(yīng)的可自由設(shè)定的參數(shù)個(gè)數(shù)之和.

定理1[13]設(shè)N是一個(gè)離散的非完全Bayes網(wǎng)絡(luò), 其有n個(gè)變量X1,X2,…,Xn, 且每個(gè)變量Xi∈[k],k∈,k≥2, 則

(8)

定理2[16]設(shè)N是一個(gè)有n個(gè)隨機(jī)變量, 無(wú)V-結(jié)構(gòu)的非完全Bayes網(wǎng)絡(luò), 且每個(gè)變量Xi∈[ki],ki∈,ki≥2, 則

VCdim(N)=Edim(N)=FA(N)+1.

(9)

定理1給出了當(dāng)隨機(jī)變量取值個(gè)數(shù)均為k時(shí), 非完全Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類VC維數(shù)和歐氏嵌入維數(shù)的上下界.定理2表明, 不含有V-結(jié)構(gòu)的非完全Bayes網(wǎng)誘導(dǎo)的概念類的VC維數(shù)和歐氏嵌入維數(shù)相等.

2 概念類VC維數(shù)的下界

Yang等[13]證明了當(dāng)X=(X1,X2,…,Xn)在[k]n上取值時(shí), 非完全Bayes網(wǎng)中得到的VC維數(shù)的下界為可自由設(shè)定的參數(shù)加1.本文推廣該結(jié)果, 考慮網(wǎng)絡(luò)中每個(gè)隨機(jī)變量Xi∈[ki](ki∈,ki≥2)時(shí)該Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界.

首先給出一個(gè)引理, 其本質(zhì)是在定義Bayes網(wǎng)誘導(dǎo)的函數(shù)類時(shí), 若函數(shù)類中不包含(1,1,…,1), 則可改寫符號(hào)函數(shù)的定義, 以避開(kāi)樣本點(diǎn)概率相等的情形.

引理1設(shè)N是有n個(gè)變量X1,X2,…,Xn的Bayes網(wǎng)絡(luò), 其中Xi∈[ki],ki∈,k≥2,i=1,2,…,n,N誘導(dǎo)的概念類為CN, 則對(duì)每個(gè)k1k2…kn維的向量b=(b1,b2,…,bk1k2…kn)∈CN-{(1,1,…,1)}都存在一對(duì)分布P,Q∈DN, 使得:

1) sign[log(P(xk)/Q(xk))]=bk;

證明: 當(dāng)n=1時(shí),N是一個(gè)完全Bayes網(wǎng)絡(luò), 此時(shí)的結(jié)果是文獻(xiàn)[13]中引理3.4的一個(gè)特例, 因此當(dāng)n=1時(shí)結(jié)論成立.

命題3[13]設(shè)a是一個(gè)非負(fù)實(shí)數(shù),b是一個(gè)m維向量, 其中

b=(b1,b2,…,bm)∈({1,-1}m-{(1,1,…,1),(-1,-1,…,-1)}),

(10)

{x′m+1|PA(Xn),x′m+2|PA(Xn),…,x′m+d-t|PA(Xn)}={zt+1,zt+2,…,zd},

且zt+1,zt+2,…,zd均不相同, 其中zt+1,zt+2,…,zd都是r維的.取

S3={(x′i,1),(x′i,2),…,(x′i,kn-1)|i=m+1,…,m+d-t},

易知S1∩S2=?,S1∩S3=?,S2∩S3=?.現(xiàn)令S=S1∪S2∪S3, 則有

下面證明?b=(b1,b2,…,bm,bm+1,…,bm+d(kn-1))∈{1,-1}m+d(kn-1), 存在一對(duì)分布P,Q∈DN, 使得

sign[log(P(si)/Q(si))]=bi,i=1,2,…,m+d(kn-1),

① (bi,0,bi,1,…,bi,kn-1)∈{(1,1,…,1),(-1,-1,…,-1)}, (bj1,0,…,bjl,0)∈{1,-1}l.

首先考慮si,0,si,1,…,si,kn-1, 可以指定參數(shù)p(xn=u|zi)=q(xn=u|zi), 選擇分布P′,Q′只需滿足P′(x′i)≥Q′(x′i)或P′(x′i)

② (bi,0,bi,1,…,bi,kn-1)∈{1,-1}kn-{(1,1,…,1),(-1,-1,…,-1)}, (bj1,0,…,bjl,0)∈{1,-1}l.

首先考慮si,0=(x′i,0)∈Ai, 由引理1知, 若bi,0=1, 則選擇分布P′,Q′時(shí)需滿足P′(x′i)>Q′(x′i); 若bi,0=-1 , 則選擇分布P′,Q′時(shí)需滿足P′(x′i)Q′(x′j); 若bj,0=-1, 則選擇分布P′,Q′時(shí)需滿足P′(x′j)

引理2是命題2的推廣, 它表明當(dāng)Bayes網(wǎng)絡(luò)中每個(gè)隨機(jī)變量取任意有限個(gè)值時(shí), 該網(wǎng)絡(luò)誘導(dǎo)的概念類的VC維數(shù)大于或等于前(n-1)個(gè)變量組成的Bayes網(wǎng)絡(luò)誘導(dǎo)的概念類的VC 維數(shù)與最后一個(gè)變量的可自由設(shè)定參數(shù)個(gè)數(shù)之和.在引理2的基礎(chǔ)上, 結(jié)合定理2, 有下列結(jié)論.

定理3設(shè)N是一個(gè)有n個(gè)節(jié)點(diǎn)X1,X2,…,Xn的非完全Bayes網(wǎng)絡(luò), 其中Xi∈[ki],ki∈,ki≥2, 則

(11)

證明: 當(dāng)n=1時(shí),N1是一個(gè)完全Bayes網(wǎng)絡(luò), 此時(shí)VCdim(N1)=FA(N1)=k1-1[13,16].考慮非完全Bayes網(wǎng)從n=2開(kāi)始, 由定理2知, VCdim(N2)=k1+k2-1,FA(N2)=k1+k2-2, 結(jié)論成立.

假設(shè)該結(jié)論對(duì)任一有(n-1)個(gè)變量X1,X2,…,Xn-1的非完全Bayes網(wǎng)Nn-1成立, 且Xi∈[ki], 則

證畢.

定理3給出了所有離散非完全Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界, 對(duì)此說(shuō)明如下.

(i) 當(dāng)Bayes網(wǎng)絡(luò)不含有V-結(jié)構(gòu)時(shí), 此類Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界正是VC維數(shù)[16].

(ii) 當(dāng)Bayes網(wǎng)絡(luò)含有V-結(jié)構(gòu)時(shí), 有些情況下這個(gè)下界恰為VC維數(shù).例如, 圖1所示的有向圖對(duì)應(yīng)的非完全Bayes網(wǎng)絡(luò), 令X,Y,Z∈{0,1}, 則該Bayes網(wǎng)絡(luò)的可自由設(shè)定參數(shù)個(gè)數(shù)為1+2×2+1=6, 其誘導(dǎo)的概念類VC維數(shù)的下界為6+1=7, 這與Yang等[14]證明的該Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)等于7一致.

(iii) 在Bayes網(wǎng)絡(luò)含有V-結(jié)構(gòu)時(shí), 這個(gè)下界有時(shí)偏小. 例如, 圖2對(duì)應(yīng)的Bayes網(wǎng)絡(luò)含有一個(gè)V-結(jié)構(gòu), 當(dāng)X1,X2,X3,X4∈{0,1}時(shí), 該Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界為1+2+2+4+1=10, 而Yang等[12]證明了該Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)為11.

綜上所述, 本文主要討論了一般Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界問(wèn)題. 對(duì)每個(gè)隨機(jī)變量都可取任意有限值的任一非完全Bayes網(wǎng)絡(luò), 考慮其誘導(dǎo)的概念類的VC維數(shù)與網(wǎng)絡(luò)中可自由設(shè)定的參數(shù)個(gè)數(shù)的關(guān)系, 證明了任意非完全離散Bayes網(wǎng)的可自由設(shè)定參數(shù)個(gè)數(shù)加1后, 是該Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的一個(gè)下界. 對(duì)于沒(méi)有V-結(jié)構(gòu)的非完全Bayes網(wǎng)絡(luò), 本文給出的這個(gè)下界恰好是VC維數(shù)[16]; 對(duì)于含有V-結(jié)構(gòu)的非完全Bayes網(wǎng)絡(luò), 這個(gè)下界可能等于VC維數(shù), 也可能小于VC維數(shù). 本文的研究結(jié)果對(duì)任一非完全Bayes網(wǎng)絡(luò)都適用, 解決了一般Bayes網(wǎng)誘導(dǎo)的概念類VC維數(shù)的下界問(wèn)題, 為進(jìn)一步研究Bayes網(wǎng)誘導(dǎo)的概念類的復(fù)雜性提供了參考.