四值貝葉斯網絡誘導的內積空間

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

關鍵詞：貝葉斯網絡; 內積空間; 線性排列; VC維數; 歐幾里德維數

中圖分類號：TN91134文獻標識碼：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引言

貝葉斯網絡是一種應用有向無環圖，表示變量間概率依賴關系的圖形模型，由Pearl最先提出［1］。貝葉斯統計和圖論的發展為貝葉斯網絡提供了堅實的理論基礎，而人工智能、專家系統和機器學習在實踐中的廣泛應用，成為貝葉斯網絡產生和發展的催化劑。

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

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

本文對四值無約束貝葉斯網絡誘導的內積空間維數的研究是多值貝葉斯網絡誘導的內積空間維數研究的起步，為以后更進一步研究一般多值貝葉斯網絡作了很好的鋪墊，也為研究多值貝葉斯網絡提供了新的思路，采用概率分布的等價性方法，將四值貝葉斯網絡轉化為布爾域上的貝葉斯網絡，可將此方法應用到研究多值貝葉斯網絡上。

1預備知識［5］

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

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

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

1，n=1（2）圖1貝葉斯網絡圖N′0定理3由n個節點構成的任意無約束貝葉斯網絡圖N′，滿足：

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

2每個變量取四值時，內積空間的維數

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

圖2貝葉斯網絡圖N0圖3貝葉斯網絡圖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) 即結論P(X)=P*(X*)成立。

定理4每個節點取4個值的n個節點構成的貝葉斯網絡圖N0，結構如圖2所示，則：E dim(N0)=3n+1（4）證明：由引理2，可將此網絡圖轉化為每個節點在布爾域上的取值，且由2n個節點構成貝葉斯網絡圖N2，0′，結構如圖3所示，即求E dim(N0)可轉化為求E dim(N2，0′) 應用定理3，貝葉斯網絡N2，0′歐幾里德維數的下界：∑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}，當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－=，當j=0，1，2，3時，M+j={v∈Mins(j)v∈S+}。其中ins(j)v指將ej插入向量v中。

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

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

qi1，ins(j)=qji

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

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

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

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

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

圖4貝葉斯網絡Nk圖5貝葉斯網絡N2，k′ 網絡圖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）由于每個節點在布爾域上的取值均由n個節點構成貝葉斯網絡圖中，有：∑ni=12mi≤E dim(N)≤∪ni=12Pi∪{i}（13）當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當k=1時，E dim(N2，k′)增加的值為9，由定理7可知，當k=0時，E dim(N0)=3n+1，則：E dim(N1)=E dim(N2′)=3n+1+9（13）當k=k時，有：E dim(Nk)=E dim(N2，k′)

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

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

參考文獻

［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.