離散無向圖模型維數(shù)的計(jì)算

劉 蕓， 張春妮, 李本崇

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

一個(gè)圖模型是一族概率分布，這里圖用來表示隨機(jī)變量間的條件獨(dú)立關(guān)系。圖中頂點(diǎn)表示隨機(jī)變量，圖中的條件獨(dú)立情形由與之相關(guān)的分離準(zhǔn)則確定。無向圖模型已在統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)的許多問題中得到應(yīng)用[1-3]。

在無向圖模型中，模型的維數(shù)問題對(duì)于檢驗(yàn)[1]和模型選擇[2]來說都非常重要。文獻(xiàn)[1]中命題4.35給出了離散可分解圖模型維數(shù)的顯式計(jì)算公式。此外，還給出了一個(gè)計(jì)算層次模型維數(shù)的遞歸公式，層次模型的一個(gè)特殊類型是離散無向圖模型(DUGMs)。文獻(xiàn)[4]將參數(shù)定義的模型轉(zhuǎn)化為隱式描述，并從代數(shù)幾何的角度分析了DUGMs。事實(shí)上，這種代數(shù)幾何刻畫的思想起源于文獻(xiàn)[5]。給定一個(gè)DUGM，可以將其對(duì)應(yīng)的環(huán)面理想的維數(shù)看作該模型的維數(shù)，但并沒有明確的公式可用來計(jì)算相應(yīng)的環(huán)面理想的維數(shù)或相關(guān)矩陣的秩。文獻(xiàn)[6]提出了一種新的鏈圖參數(shù)化方法，將鏈圖模型的維數(shù)定義為參數(shù)化過程中可自由設(shè)定的參數(shù)個(gè)數(shù)，即文獻(xiàn)[6]給出了一個(gè)顯式的計(jì)算DUGMs的維數(shù)公式。本文研究DUGMs維數(shù)的兩個(gè)定義是否一致。

一個(gè)概念類的Vapnik-Chervonenkis維數(shù)和歐氏嵌入空間的最小維數(shù)是評(píng)價(jià)一個(gè)分類器分類性能的兩個(gè)重要指標(biāo)[7-8]。文獻(xiàn)[9]證明了任意k值離散可分解圖模型誘導(dǎo)出的概念類的Vapnik-Chervonenkis維數(shù)和歐氏嵌入空間的最小維數(shù)等于其獨(dú)立參數(shù)的個(gè)數(shù)加1。文獻(xiàn)[10]證明了對(duì)于任意給定的DUGM，其誘導(dǎo)的概念類的Vapnik-Chervonenkis維數(shù)和歐氏嵌入空間的最小維數(shù)相同。這些工作也啟發(fā)我們?nèi)ビ懻揇UGMs維數(shù)的兩個(gè)定義之間的關(guān)系。

本文探究了上述DUGMs維數(shù)的2個(gè)定義之間的關(guān)系，證明了對(duì)任意的DUGM，這兩種定義下維數(shù)的差值為1，即兩個(gè)定義等價(jià)。因此，文獻(xiàn)[1]中的命題4.35可推廣到一般的DUGMs。

1 定義和符號(hào)

本節(jié)給出一些定義及其性質(zhì)。本文中，N={X1,X2,…,Xn}表示非空的有限隨機(jī)變量集，并假設(shè)每個(gè)離散變量Xi的取值為[ri]={1,2,…,ri}，其中ri≥2，是一個(gè)正整數(shù)。

1.1 無向圖

本文考慮簡單無向圖，有關(guān)圖論更多的介紹，可參考文獻(xiàn)[4]。無向圖可表示為G=(N,E)，其中N為所有頂點(diǎn)的集合，E為邊的集合。若G中兩個(gè)頂點(diǎn)X、Y的無序?qū)?X,Y)∈E，則稱這兩個(gè)頂點(diǎn)相鄰。如果頂點(diǎn)集K?N，且K中任意不相同的頂點(diǎn)的無序?qū)贓中，即?X,Y∈K,X≠Y,(X,Y)∈E，則稱頂點(diǎn)集K是完全的。特別地，空集?也是完全的。無向圖G的所有非空完全集構(gòu)成的集合記作C(G)。G中的最大完全集稱為團(tuán)，所有團(tuán)的集合記作KG。

路是一個(gè)頂點(diǎn)序列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中的一個(gè)點(diǎn)，那么我們就說N3分離了N1和N2。對(duì)于集合S?N，G(S)表示以S為頂點(diǎn)集的G的導(dǎo)出子圖。給定一個(gè)無向圖G，如果不交三元組(N1,N2,N3)滿足：(ⅰ)N=N1∪N2∪N3;(ⅱ)N3分離N1和N2；(ⅲ)N3是N的完全子集，則稱該三元組構(gòu)成G的一個(gè)分解。即(N1,N2,N3)將G分解為兩個(gè)子圖G(N1∪N3)和G(N2∪N3)，且G(N1∪N3)⊕G(N2∪N3)是直和。若子集N1,N2?N都非空，則這是一個(gè)真分解。若G存在一個(gè)真分解，則該無向圖是可約的，否則是素的。

下面通過一個(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è)無向圖G，與之相關(guān)聯(lián)的圖模型為一族分布，每一個(gè)分布P可分解為如下形式：

(1)

式中：x∈χ=[r1]×[r2]×…×[rn]；ψC(·)的取值僅依賴x中與團(tuán)C中變量對(duì)應(yīng)的值。文獻(xiàn)[4]將相應(yīng)的圖模型視為單項(xiàng)式映射φA(G)的像集，映射如下：

文獻(xiàn)[6]提出了一種將鏈圖參數(shù)化的新方法。特別地，于無向圖而言，有

例2(續(xù)例1) 對(duì)于圖1中的無向圖G1，若對(duì)i=1,2,3,4,5，均有ri=2。5個(gè)團(tuán)對(duì)應(yīng)的函數(shù)共有d=20個(gè)取值，分別為

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)的簡寫。

由定義知本例中可自由設(shè)定的參數(shù)為ψ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 層次模型的維數(shù)

超圖是有限集N的冪集的一個(gè)子集，記作H，里面的元素稱為超邊。例如，無向圖G的KG是一個(gè)超圖。若超圖H中沒有任何一個(gè)超邊是其他超邊的子集，則該超圖是約化的。約化超圖可以看作層次模型的生成類。通過移除超圖H中所有包含在其他超邊中的超邊，運(yùn)算red H便可產(chǎn)生H的約化超圖。關(guān)于2個(gè)超邊的交運(yùn)算和并運(yùn)算如下：

A∨B=red(A∪B),

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

定義在χ上的實(shí)值函數(shù)形成向量空間L，其中L為歐幾里得空間，可在其上定義內(nèi)積

對(duì)于N的子集A,L的因子子空間FA是通過xA依賴于x的函數(shù)集，即對(duì)所有令xA=yA的x,y，

f∈FA?f(x)=f(y)。

層次模型由含有如下形式的層次模型子空間確定：

文獻(xiàn)[1]給出了計(jì)算層次模型(層次模型子空間)維數(shù)的計(jì)算公式

dimHA∨B=dimHA+dimHB-dimHA∧B，

無向圖G的離散無向圖模型就是一個(gè)層次模型，其生成類為κG。

2 離散無向圖模型的維數(shù)

本節(jié)將證明離散無向圖模型維數(shù)的2種定義本質(zhì)上一致。

首先，考慮完全無向圖對(duì)應(yīng)的離散無向圖模型。

證明通過對(duì)|N|用歸納法來進(jìn)行證明。當(dāng)|N|=1時(shí)，等式顯然成立。假設(shè)該引理適用于所有頂點(diǎn)數(shù)不少于k的完全圖，當(dāng)|N|=k+1時(shí)，則有

還注意到如下引理。

引理2給定一個(gè)無向圖G，若N3分離N1和N2，則有如下等式成立:

C(G)=C(G(N1∪N3))∪C(G(N2∪N3)),

C(G(N3))=C(G(N1∪N3))∩

C(G(N2∪N3)),

dim(κG(N1∪N3)∧κG(N2∪N3))=

rank(A(G(N3)))。

證明由G(N1∪N3)和G(N2∪N3)是G的兩個(gè)導(dǎo)出子圖，可知C(G(N1∪N3))?C(G),C(G(N2∪N3))?C(G),故C(G(N1∪N3))∪C(G(N2∪N3))?C(G)。相反地，由N3分離N1和N2，所以任意一個(gè)完全的頂點(diǎn)集N4一定包含在N1∪N3或N2∪N3中，即

C(G)?C(G(N1∪N3))∪C(G(N2∪N3))。

同理，可證得

C(G(N3))=C(G(N1∪N3))∩

C(G(N2∪N3))。

由文獻(xiàn)[1,5]中

κG(N1∪N3)∧κG(N2∪N3)=κG(N3)，

dim(κG(N3))=dim(IA(G(N3)))=rank(A(G(N3)))

可得

dim(κG(N1∪N3)∧κG(N2∪N3))=

rank(A(G(N3)))。

接下來考查一般的離散無向圖模型。

定理1G為一個(gè)無向圖，則rank(A(G))=d′+1。

證明由于零理想是全維的，根據(jù)引理1和文獻(xiàn)[5]中引理4.2，只需考慮非完全的無向圖。同樣用歸納法對(duì)此定理進(jìn)行證明。當(dāng)|C(G)|=2時(shí)，結(jié)論顯然成立?，F(xiàn)假設(shè)該結(jié)論對(duì)所有完全集個(gè)數(shù)不少于k個(gè)的圖也成立，當(dāng)|C(G)|=k+1時(shí)，考慮以下兩種情況：

情況1G可約。假設(shè)G=G(N1)⊕G(N2)，由于N1∩N2是完全的，所以

C(G(N1∩N2))=C(G(N1))∩C(G(N2))。

文獻(xiàn)[1]中的引理2.23證明了κG=κG(N1)∪κG(N2)，故

C(G)=C(G(N1))∪C(G(N2))。

由引理1，可得

rank(A(G(N1∩N2)))=

結(jié)合歸納假設(shè)，有

利用1.3節(jié)提及到的公式，可得

rank(A(G))=rank(A(G(N1)))+

rank(A(G(N2)))-dim(κG(N1)∧κG(N2))=

情況1證畢。

情況2G是素的。通過給G添加一些邊，可使得此圖可約，新的可約圖記作G′，且G′=G′(N1)⊕G′(N2)，即(N1N2,N2N1,N1∩N2)構(gòu)成了G′的一個(gè)真分解。同時(shí)，N1∩N2在圖G中分離了N1N2和N2N1。由引理2，可得

C(G)=C(G(N1))∪C(G(N2)),

C(G(N1∩N2))=C(G(N1))∩C(G(N2)),

dim(κG(N1)∧κG(N2))=

rank(A(G(N1∩N2)))。

因?yàn)閨C(G(N1∩N2))|<|C(G)|，結(jié)合歸納假設(shè)可得

rank(A(G(N1∩N2)))=

情況2證畢，因此定理1在兩種情況下均成立。

定理1將文獻(xiàn)[1]中的命題4.35推廣到一般DUGMs。事實(shí)上，DUGMs維數(shù)在兩種定義上的取值差異在于文獻(xiàn)[1]和文獻(xiàn)[5]中給出的定義沒有考慮與參數(shù)向量對(duì)應(yīng)的歸一化常數(shù)。文獻(xiàn)[6]中的引理2表明可自由設(shè)定的參數(shù)向量和一個(gè)DUGM中的正概率分布存在著一一對(duì)應(yīng)關(guān)系。

3 結(jié)語

模型的維數(shù)問題對(duì)于檢驗(yàn)、模型選擇和分類都具有重要意義。本文證明了DUGMs維數(shù)的兩種定義本質(zhì)上是一致的，即計(jì)算DUGMs維數(shù)有一個(gè)簡單公式。