四值贝叶斯网络诱导的内积空间

摘要：结合贝叶斯网络与核函数，通过概率分布等价性的转换,分析了四值贝叶斯网络诱导的内积空间,得到无连接、全连接以及k个节点具有一个父节点的特殊四值贝叶斯网络诱导的内积空间的最低维数。为进一步研究多值贝叶斯网络诱导的内积空间开辟了新途径，还通过分析概念类的VC维确定了其欧几里德维数的下界。VC维还可用于估计贝叶斯网络概念类的复杂性和判断概念类的分类性能。

关键词：贝叶斯网络; 内积空间; 线性排列; VC维数; 欧几里德维数

中图分类号：TN91134文献标识码：A文章编号：1004373X(2012)04000103

Inner product spaces induced by Bayesian networks with four values

BAI Xuying

(School of Science, Northwest A&F 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 fourvalued Bayesian network with the nonconnection, 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 multiplevalued 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

收稿日期：201109260引言

贝叶斯网络是一种应用有向无环图，表示变量间概率依赖关系的图形模型，由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): 241288.

［2］TASKAR B, GUESTRIN C, KOLLER D. Maxmargin Markov networks \[J\]. Advances in Neural Information Proceeding Systems, 2004, 16: 2532.

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

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

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