摘要：結(jié)合貝葉斯網(wǎng)絡(luò)與核函數(shù)，通過概率分布等價性的轉(zhuǎn)換，分析了四值貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間，得到無連接、全連接以及k個節(jié)點(diǎn)具有一個父節(jié)點(diǎn)的特殊四值貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間的最低維數(shù)。為進(jìn)一步研究多值貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間開辟了新途徑，還通過分析概念類的VC維確定了其歐幾里德維數(shù)的下界。VC維還可用于估計貝葉斯網(wǎng)絡(luò)概念類的復(fù)雜性和判斷概念類的分類性能。

關(guān)鍵詞：貝葉斯網(wǎng)絡(luò); 內(nèi)積空間; 線性排列; VC維數(shù); 歐幾里德維數(shù)

中圖分類號：TN91134文獻(xiàn)標(biāo)識碼：A文章編號：1004373X(2012)04000103

Inner product spaces induced by Bayesian networks with four values

BAI Xuying

(School of Science， Northwest AF University， Yangling 712100， China)

Abstract： Combining Bayesian networks and kernel functions， the inner product spaces induced by Bayesian network with four values is analyzed through the transform of probability distribution equivalence property. As main results， the smallest dimension for the inner product space induced by fourvalued Bayesian network with the nonconnection， full connection and one parent node in k nodes was obtained. The results provide a new method to study the inner product spaces induced by Bayesian networks with multiplevalued nodes. The lower bounds are obtained by analyzing the VC dimension of the concept class associated with the Bayesian network. VC dimension can be used to estimate the complexity of the concept class induced by Bayesian network and judge the classification performance of the concept class.

Keywords： Bayesian network; inner product space; linear arrangement; VC dimension; Euclidean dimension

收稿日期：201109260引言

貝葉斯網(wǎng)絡(luò)是一種應(yīng)用有向無環(huán)圖，表示變量間概率依賴關(guān)系的圖形模型，由Pearl最先提出［1］。貝葉斯統(tǒng)計和圖論的發(fā)展為貝葉斯網(wǎng)絡(luò)提供了堅實(shí)的理論基礎(chǔ)，而人工智能、專家系統(tǒng)和機(jī)器學(xué)習(xí)在實(shí)踐中的廣泛應(yīng)用，成為貝葉斯網(wǎng)絡(luò)產(chǎn)生和發(fā)展的催化劑。

貝葉斯網(wǎng)絡(luò)作為一種特殊的概率模型，通過找出問題的潛在結(jié)構(gòu)，能夠表示對象之間的依賴關(guān)系以及條件獨(dú)立關(guān)系，但是不能處理高維特征空間，不能保證泛化性能；核方法能夠處理高維特征空間，并且具有較強(qiáng)的泛化能力，但是忽略了對象中的依賴性，假定每個對象之間相互獨(dú)立，丟失了有用的信息。為了結(jié)合這兩種方法的優(yōu)點(diǎn)，Taskar提出了結(jié)合最大間隔距離思想和馬爾科夫網(wǎng)絡(luò)的M模型［2］，該模型能夠處理高維結(jié)構(gòu)化數(shù)據(jù)；Altun等提出了隱馬爾科夫支持向量機(jī)(HMSVM)［3］。與標(biāo)準(zhǔn)的HMM訓(xùn)練方法相比，HMSVM基于最大和柔性間距標(biāo)準(zhǔn)的判別學(xué)習(xí)，能夠處理特征不獨(dú)立的情形。Guo等研究了基于最大間距準(zhǔn)則的貝葉斯網(wǎng)絡(luò)的訓(xùn)練問題，并針對一類拓?fù)浣Y(jié)構(gòu)提出了有效的訓(xùn)練算法［4］。該算法對任意拓?fù)浣Y(jié)構(gòu)收斂到一個近似解。Nakamura等研究了布爾型的二類分類貝葉斯網(wǎng)絡(luò)中的內(nèi)積空間［5］，即如何將一個貝葉斯網(wǎng)絡(luò)的決策函數(shù)表示為維數(shù)盡可能小的內(nèi)積空間，并給出了內(nèi)積空間維數(shù)的上界和下界［6］．

對結(jié)構(gòu)相同的網(wǎng)絡(luò)圖，每個節(jié)點(diǎn)取值個數(shù)的不同，就表示不同的貝葉斯網(wǎng)絡(luò)，所以由該貝葉斯網(wǎng)絡(luò)導(dǎo)出概念類的分類能力就不同。結(jié)合貝葉斯網(wǎng)絡(luò)與核函數(shù)的優(yōu)點(diǎn)，本文在具有標(biāo)準(zhǔn)點(diǎn)乘定義的歐幾里德內(nèi)積空間中，以歐幾里德維數(shù)來討論貝葉斯網(wǎng)絡(luò)的分類性能，通過概率分布的等價性，重點(diǎn)分析了四值貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間，得到無連接、全連接以及k個節(jié)點(diǎn)具有一個父節(jié)點(diǎn)的特殊四值貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間的最低維數(shù)和VC維數(shù)。在此通過分析概念類的VC維來確定內(nèi)積空間維數(shù)的下界，同時VC維也被廣泛地應(yīng)用于其他領(lǐng)域，如模式識別、神經(jīng)網(wǎng)絡(luò)等。

本文對四值無約束貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間維數(shù)的研究是多值貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間維數(shù)研究的起步，為以后更進(jìn)一步研究一般多值貝葉斯網(wǎng)絡(luò)作了很好的鋪墊，也為研究多值貝葉斯網(wǎng)絡(luò)提供了新的思路，采用概率分布的等價性方法，將四值貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為布爾域上的貝葉斯網(wǎng)絡(luò)，可將此方法應(yīng)用到研究多值貝葉斯網(wǎng)絡(luò)上。

1預(yù)備知識［5］

引理1 每一個概念類C滿足：

E dim(C)≥VC dim(C)。

定理1N′是由n個節(jié)點(diǎn)構(gòu)成的任意無約束貝葉斯網(wǎng)絡(luò)，則有：E dim(N′)≤∪ni=12Pi∪{i}≤2∑ni=12mi（1）定理2n個節(jié)點(diǎn)構(gòu)成的貝葉斯網(wǎng)絡(luò)圖N0′，結(jié)構(gòu)如圖1所示，則有：E dim(N0)=n+1，n≥2

1，n=1（2）圖1貝葉斯網(wǎng)絡(luò)圖N′0定理3由n個節(jié)點(diǎn)構(gòu)成的任意無約束貝葉斯網(wǎng)絡(luò)圖N′，滿足：

∑ni=12mi≤E dim(N′)≤∪ni=12Pi∪{i}≤2∑ni=12mi（3）

2每個變量取四值時，內(nèi)積空間的維數(shù)

引理2結(jié)構(gòu)如圖2的n個節(jié)點(diǎn)構(gòu)成的貝葉斯網(wǎng)絡(luò)圖N0，每個節(jié)點(diǎn)取4個值；結(jié)構(gòu)如圖3的2n個節(jié)點(diǎn)構(gòu)成的貝葉斯網(wǎng)絡(luò)圖N2，0′，每個節(jié)點(diǎn)取二個值。對N0的概率分布P(X)，存在N2，0′的概率分布P*(X*)，使得P(X)=P*(X*)。其中，X*=f(X)；f是滿射函數(shù)。

圖2貝葉斯網(wǎng)絡(luò)圖N0圖3貝葉斯網(wǎng)絡(luò)圖N′2，0證明:P(X)=P(x1)P(x2)…P(xn)，

P*(X*)=P(x11)P(x12|x11)P(x21)P(x21|x22)…

P(xn1)P(xn2|xn1)由于：P(xi=1)=pi1，P(xi=2)=pi2，P(xi=3)=pi3，

P(xi=4)=1－pi1－pi2－pi3

P*(xi1=1)P*(xi2=1|xi1=1)=p*i1p*i11，

P*(xi1=1)P*(xi2=0|xi1=1)=p*i1(1－p*i11)

P*(xi1=0)P*(xi2=1|xi1=0)=(1－p*i1)p*i10，

P*(xi1=0)P*(xi2=0|xi1=0)=(1－p*i1)·

(1－p*i10)所以有P(xi)=P(xi1)P(xi2|xi1) 即結(jié)論P(yáng)(X)=P*(X*)成立。

定理4每個節(jié)點(diǎn)取4個值的n個節(jié)點(diǎn)構(gòu)成的貝葉斯網(wǎng)絡(luò)圖N0，結(jié)構(gòu)如圖2所示，則：E dim(N0)=3n+1（4）證明：由引理2，可將此網(wǎng)絡(luò)圖轉(zhuǎn)化為每個節(jié)點(diǎn)在布爾域上的取值，且由2n個節(jié)點(diǎn)構(gòu)成貝葉斯網(wǎng)絡(luò)圖N2，0′，結(jié)構(gòu)如圖3所示，即求E dim(N0)可轉(zhuǎn)化為求E dim(N2，0′) 應(yīng)用定理3，貝葉斯網(wǎng)絡(luò)N2，0′歐幾里德維數(shù)的下界：∑2ni=12mi=∑ni=1(20+21)=3n(5)上界:∪2ni=12Pi∪{i}=∪ni=12PAi1∪{Ai1}∪2PAi2∪{Ai2}=

∪ni=i{Ji1|Ji1{Ai1}}∪{Ji2|Ji2{Ai1，Ai2}}

=∪ni=1{Ji|Ji{Ai1，Ai2}}（6）則∪2ni=12Pi∪{i}=3n+1，所以:3n≤E dim(N2，0′)≤3n+1（7）令M={e1，e2，…，en，e0}，當(dāng)i=1，2，…，n時，ei表示第i個分量為1，其余分量為0的n維向量；e0表示所有分量為1的n維向量。T={e1，e2，e3}，將T的每個向量插入M/{e0}中，將e0插入e0中，得到S={s(i，j)i=1，2，…，n;j=1，2，3}∪{s(0，0)}，則S=3n+1，若ei∈M，且ei=(a11i，a21i，…an1i)，ej∈T，且ej=(a12j，a22j，…，an2j)，則s(i，j)=(a11i，a12j，a21i，a22j，…，an1i，an2j)。S的二分集合為S+和S－，即S+∪S－=S，S+∩S－=，當(dāng)j=0，1，2，3時，M+j={v∈Mins(j)v∈S+}。其中ins(j)v指將ej插入向量v中。

由文獻(xiàn)［5］對本文定理2的證明可知，存在參數(shù)集pji，qji，1≤i≤n，使得M的任意二分集合(M－j，M+j)都可分，在貝葉斯網(wǎng)絡(luò)N2，0′中，定義：

當(dāng)i=1，2，…，n時:pi1，ins(j)=pji

qi1，ins(j)=qji

pi2，α=qi2，α=12， α∈{0，1}則:

當(dāng)s(i，j)∈S+時，sgnlogP(x)Q(x)=1；

當(dāng)s(i，j)∈S－時，sgnlogP(x)Q(x)=－1。

由引理1可知E dim(N2，0′)=3n+1。

定理5每個節(jié)點(diǎn)取4個值的n個節(jié)點(diǎn)構(gòu)成貝葉斯網(wǎng)絡(luò)圖Nk，結(jié)構(gòu)如圖4所示，則：E dim(Nk)=3n+9k+1（8）證明：可將其轉(zhuǎn)化為求每個節(jié)點(diǎn)在布爾域上取值的由2n個節(jié)點(diǎn)構(gòu)成貝葉斯網(wǎng)絡(luò)圖N2，k′的歐幾里德維數(shù)，則轉(zhuǎn)化后的網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示。

圖4貝葉斯網(wǎng)絡(luò)Nk圖5貝葉斯網(wǎng)絡(luò)N2，k′ 網(wǎng)絡(luò)圖N2，k′，E dim的下界為：∑2ni=12mi=∑ni=1(2mi1+2mi2)=1+2+∑k+1i=2(22+23)+∑ni=k+2(1+2)=3n+9k（9）上界 ：∪2ni=12Pi∪{i}={J1J1{A11，A12}}∪k+1i=2{JiJi{A11，A12，Ai1，Ai2}}∪ni=k+2{JiJi{Ai1，Ai2}} （10）

∪2ni=12Pi∪{i}=4+(24－4)k+3(n－k+1)=3n+9k+1 （11）

3n+9k≤E dim(N′2，k)≤3n+9k+1 （12）由于每個節(jié)點(diǎn)在布爾域上的取值均由n個節(jié)點(diǎn)構(gòu)成貝葉斯網(wǎng)絡(luò)圖中，有：∑ni=12mi≤E dim(N)≤∪ni=12Pi∪{i}（13）當(dāng)k=1時，E dim(N2，k′)的下界增加值為22－1+23－2=9，上界增加的排列：S={{A11，Ai1}，{A12，Ai1}，{A11，Ai2}，{A12，Ai2}，

{A11，A12，Ai1}，{A11，A12，Ai2}，{A12，Ai1，Ai2}，

{A11，Ai1，Ai2}，{A11，A12，Ai1，Ai2}}

|S|=9當(dāng)k=1時，E dim(N2，k′)增加的值為9，由定理7可知，當(dāng)k=0時，E dim(N0)=3n+1，則：E dim(N1)=E dim(N2′)=3n+1+9（13）當(dāng)k=k時，有：E dim(Nk)=E dim(N2，k′)

=3n+1+9k=3n+9k+1（14）由文獻(xiàn)［12］的定理3和引理2可直接得出結(jié)論:每個節(jié)點(diǎn)取4個值的n個節(jié)點(diǎn)構(gòu)成完全連接貝葉斯網(wǎng)絡(luò)圖NF，有：E dim(NF)=4n－1 （15）4結(jié)語

在模式識別和統(tǒng)計分析的概率技術(shù)方面，貝葉斯網(wǎng)絡(luò)被越來越深入的研究和應(yīng)用。將貝葉斯網(wǎng)絡(luò)與核函數(shù)結(jié)合起來，綜合兩者優(yōu)勢的研究方向日益受到研究者的重視。本文首先討論了變量在布爾域上取值時，某些無約束貝葉斯網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間；通過概率分布的等價性，重點(diǎn)討論了每個變量取4個值時，某些無約束貝葉網(wǎng)絡(luò)誘導(dǎo)的內(nèi)積空間維數(shù)和VC維數(shù)，在研究一般多值貝葉斯網(wǎng)絡(luò)時可參考此方法。同時，對于當(dāng)每個變量取多值時，一般的貝葉斯網(wǎng)絡(luò)維數(shù)如何，當(dāng)每個變量上取值個數(shù)不同，或者當(dāng)每個變量不是取離散值而是取連續(xù)值時，貝葉斯網(wǎng)絡(luò)的維數(shù)又該如何，這將有待進(jìn)一步的研究和思考。

參考文獻(xiàn)

［1］PEARL J. Fusion， propagation and structuring in belief networks \\[J\\]. Artificial Intelligence， 1986， 29 (3): 241288.

［2］TASKAR B， GUESTRIN C， KOLLER D. Maxmargin Markov networks \\[J\\]. Advances in Neural Information Proceeding Systems， 2004， 16: 2532.

［3］ALTUN Yasemin， TSOCHANTARIDIS Ioannis， HOFMANN Thomas. Hidden Markov support vector machines \\[C\\]// Proceedings of the 20th International Conference on Machine Learning. \\[S.l.\\]: ICMl， 2003: 310.

［4］GUO Y， WILKINSON D， SCHUURMANS D. Maximum margin Bayesian networks \\[C\\]// Proc of the 21st Conf on Uncertainty in Artificial Intelligence. Virginia: AUAI Press， 2005: 233242.

［5］NAKAMURA Atsuyoshi， SCHMITT Michael. Bayesian networks and inner product spaces \\[C\\]// Proceedings of 2004 the 17th Annual Conference on Learning Theory. \\[S.l.\\]: COLT， 2004， 3120: 518533.