离散无向图模型维数的计算

2022-06-07张春妮李本崇

陕西师范大学学报（自然科学版） 2022年3期

刘芸，张春妮, 李本崇

(西安电子科技大学数学与统计学院，陕西西安 710126)

一个图模型是一族概率分布，这里图用来表示随机变量间的条件独立关系。图中顶点表示随机变量，图中的条件独立情形由与之相关的分离准则确定。无向图模型已在统计学和机器学习的许多问题中得到应用[1-3]。

在无向图模型中，模型的维数问题对于检验[1]和模型选择[2]来说都非常重要。文献[1]中命题4.35给出了离散可分解图模型维数的显式计算公式。此外，还给出了一个计算层次模型维数的递归公式，层次模型的一个特殊类型是离散无向图模型(DUGMs)。文献[4]将参数定义的模型转化为隐式描述，并从代数几何的角度分析了DUGMs。事实上，这种代数几何刻画的思想起源于文献[5]。给定一个DUGM，可以将其对应的环面理想的维数看作该模型的维数，但并没有明确的公式可用来计算相应的环面理想的维数或相关矩阵的秩。文献[6]提出了一种新的链图参数化方法，将链图模型的维数定义为参数化过程中可自由设定的参数个数，即文献[6]给出了一个显式的计算DUGMs的维数公式。本文研究DUGMs维数的两个定义是否一致。

一个概念类的Vapnik-Chervonenkis维数和欧氏嵌入空间的最小维数是评价一个分类器分类性能的两个重要指标[7-8]。文献[9]证明了任意k值离散可分解图模型诱导出的概念类的Vapnik-Chervonenkis维数和欧氏嵌入空间的最小维数等于其独立参数的个数加1。文献[10]证明了对于任意给定的DUGM，其诱导的概念类的Vapnik-Chervonenkis维数和欧氏嵌入空间的最小维数相同。这些工作也启发我们去讨论DUGMs维数的两个定义之间的关系。

本文探究了上述DUGMs维数的2个定义之间的关系，证明了对任意的DUGM，这两种定义下维数的差值为1，即两个定义等价。因此，文献[1]中的命题4.35可推广到一般的DUGMs。

1 定义和符号

本节给出一些定义及其性质。本文中，N={X1,X2,…,Xn}表示非空的有限随机变量集，并假设每个离散变量Xi的取值为[ri]={1,2,…,ri}，其中ri≥2，是一个正整数。

1.1 无向图

本文考虑简单无向图，有关图论更多的介绍，可参考文献[4]。无向图可表示为G=(N,E)，其中N为所有顶点的集合，E为边的集合。若G中两个顶点X、Y的无序对(X,Y)∈E，则称这两个顶点相邻。如果顶点集K⊆N，且K中任意不相同的顶点的无序对均在E中，即∀X,Y∈K,X≠Y,(X,Y)∈E，则称顶点集K是完全的。特别地，空集∅也是完全的。无向图G的所有非空完全集构成的集合记作C(G)。G中的最大完全集称为团，所有团的集合记作KG。

路是一个顶点序列X=Y1,Y2,…,Yk=Y,k≥2，其中(Yi,Yi+1)∈E,i=1,2,…,k-1。∀N1,N2⊆N,N1∩N2=∅，N3⊆N(N1∪N2),若无向图G中X∈N1和Y∈N2之间的每条路都至少包含N3中的一个点，那么我们就说N3分离了N1和N2。对于集合S⊆N，G(S)表示以S为顶点集的G的导出子图。给定一个无向图G，如果不交三元组(N1,N2,N3)满足：(ⅰ)N=N1∪N2∪N3;(ⅱ)N3分离N1和N2；(ⅲ)N3是N的完全子集，则称该三元组构成G的一个分解。即(N1,N2,N3)将G分解为两个子图G(N1∪N3)和G(N2∪N3)，且G(N1∪N3)⊕G(N2∪N3)是直和。若子集N1,N2⊆N都非空，则这是一个真分解。若G存在一个真分解，则该无向图是可约的，否则是素的。

下面通过一个例子说明部分概念。

例1如图1所示无向图G1。

图1 无向图G1

C(G1)={{X1},{X2},{X3},{X4},{X5},

{X1,X2},{X2,X3},{X2,X4},

{X3,X5},{X4,X5}}。

KG1中的元素为{X1,X2},{X2,X3},{X2,X4},{X3,X5},{X4,X5}。

1.2 离散无向图模型

给定一个无向图G，与之相关联的图模型为一族分布，每一个分布P可分解为如下形式：

(1)

式中：x∈χ=[r1]×[r2]×…×[rn]；ψC(·)的取值仅依赖x中与团C中变量对应的值。文献[4]将相应的图模型视为单项式映射φA(G)的像集，映射如下：

文献[6]提出了一种将链图参数化的新方法。特别地，于无向图而言，有

例2(续例1) 对于图1中的无向图G1，若对i=1,2,3,4,5，均有ri=2。5个团对应的函数共有d=20个取值，分别为

t1=ψ1,2(11),t2=ψ1,2(12),t3=ψ1,2(21),

t4=ψ1,2(22),t5=ψ2,3(11),t6=ψ2,3(12),

t7=ψ2,3(21),t8=ψ2,3(22),t9=ψ2,4(11),

t10=ψ2,4(12),t11=ψ2,4(21),

t12=ψ2,4(22),t13=ψ3,5(11),

t14=ψ3,5(12),t15=ψ3,5(21),

t16=ψ3,5(22),t17=ψ4,5(11),

t18=ψ4,5(12),t19=ψ4,5(21),

t20=ψ4,5(22),

式中ψi,k(xixk)是ψ{Xi,Xk}(xi,xk)的简写。

由定义知本例中可自由设定的参数为ψ1(2)、ψ2(2)、ψ3(2)、ψ4(2)、ψ5(2)、ψ1,2(22)、ψ2,3(22)、ψ2,4(22)、ψ3,5(22)、ψ4,5(22),因此d′=10。

1.3 层次模型的维数

超图是有限集N的幂集的一个子集，记作H，里面的元素称为超边。例如，无向图G的KG是一个超图。若超图H中没有任何一个超边是其他超边的子集，则该超图是约化的。约化超图可以看作层次模型的生成类。通过移除超图H中所有包含在其他超边中的超边，运算red H便可产生H的约化超图。关于2个超边的交运算和并运算如下：

A∨B=red(A∪B),

A∧B=red(A∩B|A∈A,B∈B)。

定义在χ上的实值函数形成向量空间L，其中L为欧几里得空间，可在其上定义内积