劉洋，羅晨希，羅鐵堅(jiān)

(1 中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)與控制學(xué)院，北京 101408； 2 中國(guó)科學(xué)院軟件所，北京 100080)

概率圖模型，例如貝葉斯網(wǎng)絡(luò)和馬爾科夫網(wǎng)絡(luò)，已經(jīng)被廣泛應(yīng)用在人工智能領(lǐng)域[1]。這類圖模型用簡(jiǎn)潔的結(jié)構(gòu)表示復(fù)雜的概率分布，在推理和參數(shù)學(xué)習(xí)方面，由于歸一化參數(shù)的計(jì)算量非常大，在最壞情況下為指數(shù)級(jí)別[2]，一般情況下精確計(jì)算條件概率的復(fù)雜度也為#P完全[3]的。此外，隨著變量個(gè)數(shù)的增加，模型也更加復(fù)雜。Poon和Domingos[1]于2011年提出一種新型深度模型結(jié)構(gòu)——和積網(wǎng)絡(luò)(sum-product network, SPN)來(lái)解決上述問(wèn)題。和積網(wǎng)絡(luò)(圖1)是有向無(wú)環(huán)圖，它將觀測(cè)變量作為葉子結(jié)點(diǎn)，將“和”與“積”操作作為深度網(wǎng)絡(luò)的內(nèi)部結(jié)點(diǎn)。和積網(wǎng)絡(luò)可以在高樹寬模型中快速計(jì)算精確推理，其推理開銷和網(wǎng)絡(luò)大小成線性關(guān)系，具有很強(qiáng)的表達(dá)能力和快速推理能力，在計(jì)算機(jī)視覺[4]、語(yǔ)音識(shí)別[5]、自然語(yǔ)言處理[6]等領(lǐng)域均有應(yīng)用。當(dāng)前和積網(wǎng)絡(luò)的研究主要聚焦在結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)等應(yīng)用方面，而制約其應(yīng)用發(fā)展的理論問(wèn)題，如SPN有效性、MAP推理復(fù)雜性等問(wèn)題仍未得到根本解決。

圖1 和積網(wǎng)絡(luò)示例Fig.1 An example of sum-product networks

和積網(wǎng)絡(luò)將分布分解為混合(sum)與分解(product)的層次結(jié)構(gòu)，因而可看做基于變量集合的非歸一化概率分布。和積網(wǎng)絡(luò)的有效性(validity)即它可以正確表示概率分布，例如，僅當(dāng)和積網(wǎng)絡(luò)有效時(shí)，計(jì)算聯(lián)合概率分布px的等式才成立：對(duì)?x,p(X=x)=S(x)/∑x～XS(x)，X表示變量集合，S(x)表示輸入為x的和積網(wǎng)絡(luò)計(jì)算得到的數(shù)值。在實(shí)踐中并非所有生成的和積網(wǎng)絡(luò)都是有效的，和積網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)過(guò)程中，部分算法基于有效性對(duì)于范圍的限制，應(yīng)用分層聯(lián)合聚類[7-9]，每迭代一次，都需對(duì)現(xiàn)有模型進(jìn)行有效性驗(yàn)證，因而快速判斷和積網(wǎng)絡(luò)的有效性成為必要，開展和積網(wǎng)絡(luò)有效性問(wèn)題的研究具有理論意義和應(yīng)用價(jià)值。

本文的主要工作及其貢獻(xiàn)在于：1)探討和積網(wǎng)絡(luò)的一些內(nèi)部結(jié)構(gòu)性質(zhì)；2)提出驗(yàn)證和積網(wǎng)絡(luò)的有效性算法及其正確性證明，分析其復(fù)雜度和適用場(chǎng)景；3)提出一種新的關(guān)于和積網(wǎng)絡(luò)中生成樹個(gè)數(shù)的計(jì)算方式。

1 相關(guān)工作

和積網(wǎng)絡(luò)被提出后在基礎(chǔ)理論方面、參數(shù)學(xué)習(xí)、結(jié)構(gòu)學(xué)習(xí)方面以及應(yīng)用方面都有了相應(yīng)的研究，從和積網(wǎng)絡(luò)的基礎(chǔ)理論研究方面，Zhao等[10]證明任意和積網(wǎng)絡(luò)都可以轉(zhuǎn)化為二分貝葉斯網(wǎng)絡(luò)。Martens和Medabalimi[11]證明網(wǎng)絡(luò)的表達(dá)性隨著深度增長(zhǎng)而增加。和積網(wǎng)絡(luò)有效性的定義給出后[1]，由于沒有相應(yīng)的驗(yàn)證算法，Peharz[2]弱化有效性的條件要求，證明和積網(wǎng)絡(luò)的參數(shù)可以被轉(zhuǎn)化為局部歸一化。一致且完備的和積網(wǎng)絡(luò)同樣保證有效性[12]。Martens和Medabalimi[11]找到有效和積網(wǎng)絡(luò)的特例，證明Peharz的結(jié)論是充分不必要條件，因而強(qiáng)化了有效性的條件，給出強(qiáng)有效性的定義，并證明強(qiáng)有效性與網(wǎng)絡(luò)輸出多重線性多項(xiàng)式的等價(jià)關(guān)系，而關(guān)于和積網(wǎng)絡(luò)有效性的算法驗(yàn)證的研究仍不充分。本文嘗試給出兩個(gè)驗(yàn)證算法，并比較兩個(gè)算法的適用場(chǎng)所及復(fù)雜度。

從和積網(wǎng)絡(luò)的權(quán)重學(xué)習(xí)方面，Zhao等[13]提出一種統(tǒng)一的學(xué)習(xí)和積網(wǎng)絡(luò)參數(shù)的方法。

從和積網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)方面，Dennis和Ventura[14]提出和積網(wǎng)絡(luò)的第一個(gè)結(jié)構(gòu)學(xué)習(xí)算法，Adel等[15]提出一種基于SVD分解的算法，通過(guò)對(duì)樣本矩陣進(jìn)行切割學(xué)習(xí)和積網(wǎng)絡(luò)的結(jié)構(gòu)。 Rashwan等[16]提出在線貝葉斯矩匹配算法。目前最為常用的算法為L(zhǎng)earnSPN[7]，雖然提出較早，但由于執(zhí)行速度快，至今仍被頻繁使用，也出現(xiàn)對(duì)其改進(jìn)的算法SPN-BT[8]。目前最好的結(jié)構(gòu)學(xué)習(xí)算法為ID-SPN[9]，通過(guò)利用變量之間的間接和直接相互作用、自上而下聚類的方式學(xué)習(xí)和積網(wǎng)絡(luò)，該算法將sum結(jié)點(diǎn)和product結(jié)點(diǎn)作為內(nèi)部結(jié)點(diǎn)，運(yùn)算電路AC(arithmetic circuits)作為葉結(jié)點(diǎn)，從單個(gè)AC結(jié)構(gòu)開始，只在直接改善了似然性的情況下將每個(gè)AC葉結(jié)點(diǎn)拆分為兩個(gè)新的AC葉結(jié)點(diǎn)，最后估計(jì)葉結(jié)點(diǎn)的分布。由于該算法與AC的基礎(chǔ)算法相結(jié)合，因而比一般的樹形結(jié)構(gòu)如Chow-Liu葉結(jié)點(diǎn)更好地逼近復(fù)雜的分布。

從應(yīng)用方面，Cheng等[6]利用和積網(wǎng)絡(luò)構(gòu)造語(yǔ)言模型，根據(jù)前K個(gè)詞計(jì)算第K+1個(gè)詞出現(xiàn)的概率，得到比之前語(yǔ)言模型更好的預(yù)測(cè)準(zhǔn)確性。Nath和Domingos[17]引入關(guān)系和積網(wǎng)絡(luò)的概念，并利用關(guān)系和積網(wǎng)絡(luò)構(gòu)造一個(gè)關(guān)于缺陷定位問(wèn)題的易解概率學(xué)習(xí)模型，可以鑒別重復(fù)發(fā)生的bug。

和積網(wǎng)絡(luò)可以進(jìn)行概率密度估計(jì)，因而也被解釋為特殊的深度神經(jīng)網(wǎng)絡(luò)。同時(shí)，它還可以表達(dá)一些其他類型的易解概率分布，如稀疏聯(lián)結(jié)樹和隱藏樹模型。近期，和積網(wǎng)絡(luò)也被解釋為特殊形式的前饋神經(jīng)網(wǎng)絡(luò)[4]和概率卷積網(wǎng)絡(luò)[18]。

和積網(wǎng)絡(luò)經(jīng)常被稱作一種新型的概率圖模型，其性質(zhì)更像是運(yùn)算電路。在經(jīng)典的概率圖模型中，葉結(jié)點(diǎn)代表隨機(jī)變量，邊代表變量間的依賴關(guān)系。然而和積網(wǎng)絡(luò)的中間結(jié)點(diǎn)為運(yùn)算單元，即“和”與“積”，邊決定運(yùn)算單元的計(jì)算順序，不再關(guān)心變量間的關(guān)系。

2 和積網(wǎng)絡(luò)的有效性驗(yàn)證算法

和積網(wǎng)絡(luò)是有向無(wú)環(huán)圖(如圖1)，隱藏變量為求和或者求積，并且被交替排列在相鄰層次上，sum結(jié)點(diǎn)可看作是變量在集合上的混合，product結(jié)點(diǎn)可看作是特征的混合，即sum結(jié)點(diǎn)提供混合模型，product結(jié)點(diǎn)建立特征層次，“有效性”以一種很好的方式約束和積網(wǎng)絡(luò)，因而網(wǎng)絡(luò)具有很強(qiáng)的表達(dá)能力和推理能力。每一個(gè)以和積網(wǎng)絡(luò)內(nèi)部結(jié)點(diǎn)為根結(jié)點(diǎn)的子網(wǎng)絡(luò)依然為和積網(wǎng)絡(luò)，和積網(wǎng)絡(luò)可看作由小的和積網(wǎng)絡(luò)連接組成，因而在計(jì)算上具有潛在的可擴(kuò)展性，使得學(xué)習(xí)和推理更加便于處理，在該模型下得到的結(jié)果也應(yīng)用得更加廣泛。

現(xiàn)在給出和積網(wǎng)絡(luò)的形式化定義。

定義1 和積網(wǎng)絡(luò)[1]：和積網(wǎng)絡(luò)是一個(gè)有根且有權(quán)重的有向無(wú)環(huán)圖，內(nèi)部結(jié)點(diǎn)為sum結(jié)點(diǎn)與product結(jié)點(diǎn)，葉結(jié)點(diǎn)為網(wǎng)絡(luò)輸入，輸入變量集合為X={X1,…,Xn}，X的分布為φn，|X|=n。

令ch(Q)作為結(jié)點(diǎn)Q的所有子結(jié)點(diǎn)的集合，pa(Q)作為結(jié)點(diǎn)Q的所有父結(jié)點(diǎn)的集合，desc(Q)為結(jié)點(diǎn)Q的所有后代的集合。每條連接sum結(jié)點(diǎn)Q與其子結(jié)點(diǎn)c∈ch(Q)的邊均有非負(fù)權(quán)重ωQc，令w為和積網(wǎng)絡(luò)所有權(quán)重的集合。SQ是S的子網(wǎng)絡(luò)，其根結(jié)點(diǎn)為Q。網(wǎng)絡(luò)內(nèi)所有結(jié)點(diǎn)個(gè)數(shù)設(shè)為m。對(duì)于X的一個(gè)實(shí)例x，或者稱之為完全示例(complete evidence)，用x～X表示。為簡(jiǎn)化討論，本文假定隨機(jī)變量為布爾變量，然而本文結(jié)論可被拓展到離散和連續(xù)變量。不失一般性，本文假設(shè)和積網(wǎng)絡(luò)有交替的內(nèi)部結(jié)點(diǎn)類型，即sum結(jié)點(diǎn)層與product結(jié)點(diǎn)層交替出現(xiàn)。

葉結(jié)點(diǎn)的范圍(scope)[1]是結(jié)點(diǎn)對(duì)應(yīng)向量的集合，父結(jié)點(diǎn)的范圍是所有子結(jié)點(diǎn)范圍的并集，并把根結(jié)點(diǎn)的范圍作為和積網(wǎng)絡(luò)的范圍。

和積網(wǎng)絡(luò)的深度是為sum結(jié)點(diǎn)層與product結(jié)點(diǎn)層交替出現(xiàn)的和積網(wǎng)絡(luò)中從根結(jié)點(diǎn)到子結(jié)點(diǎn)的最長(zhǎng)路徑長(zhǎng)度[1]。

當(dāng)變量集合X取值為x且和積網(wǎng)絡(luò)(以下用S表示)有效時(shí)，S(x)表示輸入為x基于S計(jì)算得到的非歸一化概率值，即P(X=x)=S(x)/Z，Z=∑xS(x)為歸一化參數(shù)。當(dāng)每個(gè)sum結(jié)點(diǎn)Qi連接所有子結(jié)點(diǎn)的權(quán)重和為1時(shí)，即∑Nj∈ch(Ni)ωQiNj=1，且葉結(jié)點(diǎn)的分布為歸一化分布，則S表示歸一化分布，即?x,P(X=x)=S(x)。

定義2 計(jì)算(evaluation)[1]：對(duì)于和積網(wǎng)絡(luò)S，給定變量集合X，X的分布為φn，|X|=n,參數(shù)集合w，若SQ是S的子網(wǎng)絡(luò)，其根結(jié)點(diǎn)為Q，則SQ(x)的計(jì)算公式為

整個(gè)網(wǎng)絡(luò)的值S(x)為根結(jié)點(diǎn)的值。

和積網(wǎng)絡(luò)的有效性即S可以正確表示分布，下面給出有效性的形式化定義。

定義4 有效性[10]：對(duì)于和積網(wǎng)絡(luò)S，給定變量集合X，若對(duì)于任意x～X，均有S(x)=φS(x)，則稱S是有效的，其中，φS(x)為基于S的網(wǎng)絡(luò)多項(xiàng)式。

定義5 完備性，可分解性[1]：和積網(wǎng)絡(luò)S，令S+為S中所有sum結(jié)點(diǎn)的集合，S×為S中所有product結(jié)點(diǎn)的集合，則

1)S是完備的當(dāng)且僅當(dāng)?n∈S+，?c1，c2∈ch(n):sc(c1)=sc(c2)；

2)S是可分解的當(dāng)且僅當(dāng)?n∈S×，?c1，c2∈ch(n)，c1≠c2:

sc(c1)∩sc(c2)=?。

定義6 拓?fù)渑判?topological sorting)[13]：在圖論中，由一個(gè)有向無(wú)環(huán)圖的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿足下列條件時(shí)，稱為該圖的一個(gè)拓?fù)渑判颉?/p>

1)每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)1次；

2)若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。

2.1 Veri-SPN算法

算法1對(duì)每個(gè)結(jié)點(diǎn)都進(jìn)行驗(yàn)證，計(jì)算量較大。首先自下而上標(biāo)記所有結(jié)點(diǎn)的范圍，再自上而下，逐層分別檢查每個(gè)結(jié)點(diǎn)的完備性和可分解性，即對(duì)于sum結(jié)點(diǎn)，檢查其子結(jié)點(diǎn)的范圍是否相同，對(duì)于product結(jié)點(diǎn)，檢查其子結(jié)點(diǎn)的范圍是否互不相交，通過(guò)驗(yàn)證和積網(wǎng)絡(luò)的完備性和可分解性進(jìn)而驗(yàn)證有效性，第1個(gè)算法為Veri-SPN，具體描述如下。

定理2.1對(duì)結(jié)點(diǎn)個(gè)數(shù)為m，變量個(gè)數(shù)為n的和積網(wǎng)絡(luò)S，算法一在Ο(n×m2)內(nèi)完成驗(yàn)證。

證明算法1的證明方式為自下而上，設(shè)Q1,…,Qm是S所有結(jié)點(diǎn)的一個(gè)拓?fù)渑判?，即k>l?Qk?desc(Ql)。首先對(duì)每個(gè)結(jié)點(diǎn)Qk初始化賦值為0：ak=[ak1,ak2,…,akn]=[0,0,…,0]，該向量的含義是：若Xi∈sc(Qk)，則aki=1，否則為0。即，若Xi∈sc(Qk)，則ak在第i個(gè)位置的值為1。

當(dāng)結(jié)點(diǎn)Qk為葉結(jié)點(diǎn)時(shí)，需將該葉結(jié)點(diǎn)對(duì)應(yīng)的向量反映在自己的矩陣中，即，若X1?sc(Qk),X2∈sc(Qk)?ak=[0,1,…,0]，由于本文假設(shè)變量類型為布爾變量，變量個(gè)數(shù)為n，結(jié)點(diǎn)個(gè)數(shù)為m，由于葉結(jié)點(diǎn)個(gè)數(shù)可能超過(guò)n，并且與n并無(wú)明顯關(guān)系，但是卻一定小于m，則所有葉結(jié)點(diǎn)的計(jì)算成本為Ο(m)。

當(dāng)結(jié)點(diǎn)Qk為product結(jié)點(diǎn)時(shí)，需要驗(yàn)證Qk的子結(jié)點(diǎn)范圍互不相同，即?Qi,Qj∈ch(Qk),i≠j,sc(Qi)∩sc(Qj)=?，首先逐個(gè)找到Qk的子結(jié)點(diǎn)，然后將子結(jié)點(diǎn)的范圍并入到Qk的范圍，若并入過(guò)程中發(fā)現(xiàn)已經(jīng)存在重復(fù)變量，則S不滿足可分解性，進(jìn)而不是有效的，則算法停止，所有的product結(jié)點(diǎn)的計(jì)算成本為Ο(n×m2)。

Algorithm 1 Veri-SPN1: Find some topological ordering Q1,…,Qm of nodes in SPN 2: For all nodes Qk initialize ak=[ak1,ak2,…,akn]=[0,0,…,0],aki∈[0,1]3: for k=1:m do4: b←05: if Qk is a leaf node then6: if Xi∈sc(Qk),i=1:n then7: aki←18: end if9: end if 10: if Qk is a product node then 11:if Qi∈ch(Qk),i=1:k then12:if aij=1,j=1:n then13:if akj=1 then14:abort15:else16:akj←aij17:end if 18:end if 19:end if20:end if21: if Qk is a sum node then22:if Qi∈ch(Qk),i=1:k then23:if b=0then24:akj←aij,j=1:n,b←125:else 26:if akj≠aij,j=1:n then 27:abort 28:end if29:end if30:end if31:end if32: end for

當(dāng)結(jié)點(diǎn)Qk為sum結(jié)點(diǎn)時(shí)，需要驗(yàn)證Qk的子結(jié)點(diǎn)范圍完全相同，即?Qi,Qj∈ch(Qk)，sc(Qi)=sc(Qj)。首先把第一個(gè)得到的子結(jié)點(diǎn)的范圍并入到Qk的范圍，之后逐個(gè)比較Qk的每個(gè)子結(jié)點(diǎn)的范圍與Qk的范圍，若出現(xiàn)不同，則S不滿足完備性，進(jìn)而不是有效的，則算法停止，所有的sum結(jié)點(diǎn)的計(jì)算成本為Ο(n×m2)。

若和積網(wǎng)絡(luò)是完備的且是可分解的，則該和積網(wǎng)絡(luò)是有效的[1]，因而算法1可以證明和積網(wǎng)絡(luò)的有效性。

綜上，總的計(jì)算成本為Ο(n×m2)。

□

由于目前沒有任何關(guān)于m與n關(guān)系的探討，m的取值范圍可以是n的多項(xiàng)式范圍，也可以是n的指數(shù)范圍。如果是前者，則算法1在實(shí)踐中已滿足使用需求；相反，如果是后者，在m相當(dāng)大的情況下，算法1計(jì)算量過(guò)大。

因而，本文提出第2個(gè)驗(yàn)證算法，犧牲一部分準(zhǔn)確性，換取相對(duì)快速的驗(yàn)證效果，在S的層數(shù)低時(shí)效果更好。

2.2 Induce-SPN算法

有效的和積網(wǎng)絡(luò)可看做是一些生成樹T(induced tree)的疊加，且每個(gè)生成樹的范圍與對(duì)應(yīng)和積網(wǎng)絡(luò)是相同的，因而對(duì)和積網(wǎng)絡(luò)的有效性驗(yàn)證就可以一定概率轉(zhuǎn)化為對(duì)T進(jìn)行驗(yàn)證，算法2基于上述思想，具體描述如下。

Algorithm 2 Induce-SPN1:Let T=(TV,TE) be a subgraph of S2:TV={Root(S)},TE=?3:while exist node Qk∈TV that ch(Qk)≠?,ch(Qk)∩TE=? do4: if Qk is a sum node then5:choose exactly one child of Qk in S randomly, put the node in TV, the responding edges in TE6: end if7: if Qk is a product node then8: put all the children of Qk in S in TV in order, the responding edges in TE9: end if10: if Qk is a leaf node then11: skip12: end if13: k←k+114:end while

定理2.2S的范圍與T的范圍是一樣的，并且，T中每個(gè)結(jié)點(diǎn)的范圍與對(duì)應(yīng)的S中結(jié)點(diǎn)的范圍是一樣的。

證明由于S的根結(jié)點(diǎn)Root(S)也是T中的結(jié)點(diǎn)，

1) 當(dāng)S的高度h=2時(shí)，若Root(S)是sum結(jié)點(diǎn)，則根結(jié)點(diǎn)與相鄰子結(jié)點(diǎn)的范圍是一樣的，顯然，sc(S)=sc(T)，若Root(S)是product結(jié)點(diǎn)，則Root(S)的所有相鄰子結(jié)點(diǎn)也在T中，S=T，因而sc(S)=sc(T)。

2) 假設(shè)當(dāng)h=n時(shí)，sc(S)=sc(T)，那么，當(dāng)h=n+1時(shí)，若Root(S)是sum結(jié)點(diǎn)，有k個(gè)子結(jié)點(diǎn)，則S與每個(gè)子網(wǎng)絡(luò)的根結(jié)點(diǎn)的范圍一樣，同理于T，因而sc(S)=sc(T)。若Root(S)是product結(jié)點(diǎn)，則Root(S)與子結(jié)點(diǎn)連接的邊也在T中，因而sc(S)=sc(T)。

綜上，sc(S)=sc(T)。

用同樣的方法可以得到，T中每個(gè)結(jié)點(diǎn)的范圍與對(duì)應(yīng)的S中結(jié)點(diǎn)的范圍是一樣的。

□

定理2.3若和積網(wǎng)絡(luò)S是不可分解的，則存在T也是不可分解的。

證明首先，若S是有效的，則T也是有效的。由于T中所有的sum結(jié)點(diǎn)均只有一個(gè)子結(jié)點(diǎn)，完備性要求sum結(jié)點(diǎn)的所有子結(jié)點(diǎn)的范圍完全相同，因而T天然地滿足完備性。T中任意product結(jié)點(diǎn)與其子結(jié)點(diǎn)均來(lái)自于S中的一個(gè)product結(jié)點(diǎn)及其所有的子結(jié)點(diǎn)，由于S是有效的，則所有子結(jié)點(diǎn)的范圍是互不相交的，由于T的生成過(guò)程，T是S的子圖，T中每個(gè)結(jié)點(diǎn)在T中的范圍均小于等于在S中的范圍，因而，在T中所有子結(jié)點(diǎn)的范圍依舊是不相交的，滿足可分解性要求，所以，T也是有效的。

若S是不可分解的，則存在product結(jié)點(diǎn)Qk，其子結(jié)點(diǎn)的范圍是有交集的，由定理2.2，T中每個(gè)結(jié)點(diǎn)的范圍與對(duì)應(yīng)的S中結(jié)點(diǎn)的范圍是一樣的。因而，若T包含結(jié)點(diǎn)Qk，則T包含Qk所有子結(jié)點(diǎn)，因而T中Qk的子結(jié)點(diǎn)的范圍是有交集的，T不可分解。

□

定理2.4若S不是完備的，則存在T是不可分解的。

證明若S不是完備的，則存在結(jié)點(diǎn)Qi、Qj有共同的父結(jié)點(diǎn)Q，Q為sum結(jié)點(diǎn)且sc(Qi)≠sc(Qj)。由于T中每個(gè)sum結(jié)點(diǎn)只連接一條邊，因而Qi、Qj不會(huì)出現(xiàn)在同一個(gè)T中，則存在Ti、Tj分別包含邊(Q，Qj)與邊(Q，Qi)。

由于sc(Qi)≠sc(Qj)，父結(jié)點(diǎn)的范圍是子結(jié)點(diǎn)范圍的并集，因而Q在Ti中與Q在Tj中的范圍不一樣，然而根據(jù)定理2.2，Ti與Tj的范圍是一樣的(均與S相同)，則根據(jù)生成樹的生成規(guī)則，Ti與Tj至少有一個(gè)是不可分解的。

□

定理2.5若和積網(wǎng)絡(luò)S不是有效的，則算法2至少以1/fS(1|1)的概率證明S的無(wú)效。

證明盡管存在極端情況，即和積網(wǎng)絡(luò)S是有效的，但是卻不滿足完備性或可分解性[11]，由于數(shù)量極少，故在一般使用中忽略此情況。綜上，若S是不可分解的，則存在T是不可分解的，同樣，若S是不完備的，也存在T是不可分解的，由于S中所有不同的T的個(gè)數(shù)為fS(1|1)[13],根據(jù)定理2.2、2.3、2.4，算法2至少以1/fS(1|1)的概率證明S的無(wú)效。

□

下面給出兩個(gè)算法的具體比較(如表1所示)。

表1 兩個(gè)算法比較Table 1 Comparison between the two algorithms

3 一種新的計(jì)算和積網(wǎng)絡(luò)生成樹個(gè)數(shù)的方法

和積網(wǎng)絡(luò)中的生成樹T為算法2中產(chǎn)生的樹：自上而下，首先包含S的根Root(S)，若為sum結(jié)點(diǎn)則T只包含其中的一個(gè)子結(jié)點(diǎn)，若為product結(jié)點(diǎn)則其所有子結(jié)點(diǎn)均在T中，以此類推，直至有一個(gè)葉結(jié)點(diǎn)包含在T中。Zhao等[13]提到S中T的個(gè)數(shù)τS僅依賴網(wǎng)絡(luò)結(jié)構(gòu)，并且遠(yuǎn)小于2Ο(M)，其中M為S中sum結(jié)點(diǎn)的個(gè)數(shù)，并給出τS=Ω(2h)，h為S的高度，然而，本文找到的高度為h的最簡(jiǎn)單結(jié)構(gòu)的和積網(wǎng)絡(luò)的T個(gè)數(shù)為22h/2，即：任意高度為h的和積網(wǎng)絡(luò)，可以得到的個(gè)數(shù)大于等于22h/2，因而得出更加準(zhǔn)確的結(jié)論：τS=Ω(22h/2)。

計(jì)算過(guò)程如下：不失一般性，設(shè)Root(S)為sum結(jié)點(diǎn)(product結(jié)點(diǎn)情況類似，可以類推)，設(shè)S中sum結(jié)點(diǎn)層與product結(jié)點(diǎn)層交替出現(xiàn)，并且每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)為2(以此達(dá)到最簡(jiǎn)單的構(gòu)造S)，自上而下對(duì)每個(gè)結(jié)點(diǎn)Nij賦予變量bi,j，i代表層數(shù)(i≤h)，j代表自左向右的順序，如圖2(a)，bi,j的值代表以結(jié)點(diǎn)Nij為根結(jié)點(diǎn)的子網(wǎng)絡(luò)Sij中T的個(gè)數(shù)。

圖2 和積網(wǎng)絡(luò)生成樹個(gè)數(shù)計(jì)算步驟Fig.2 Calculation steps for the number of generation trees in SPN

由于S是對(duì)稱結(jié)構(gòu)，任意包含邊(N11,N21)的T(深灰色)都可以在包含邊(N11,N22)的T*(淺灰色)找到一條來(lái)對(duì)應(yīng)，且由于T的構(gòu)造，不存在T同時(shí)包含邊(N11,N21)，(N11,N22)。因而b2,1=b2,2，b1,1=2·b2,1。如圖2(b),以N11為根結(jié)點(diǎn)的計(jì)數(shù)問(wèn)題轉(zhuǎn)化為以N21為根結(jié)點(diǎn)的子網(wǎng)絡(luò)S21中T的計(jì)數(shù)問(wèn)題。

由于N31是sum結(jié)點(diǎn)，再次得到b3,1=2·b4,1。

=2·(2b4,1)2

=….

若h為奇數(shù)，則

τS=b1,1

=220+21+22+…+2(h-3)/2=22(h-1)/2-1，

若h為偶數(shù)，則

τS=b1,1

=220+21+22+…+2h/2=22(h+2)/2-1.

綜上，τS=Ω(22h/2)。

4 總結(jié)

和積網(wǎng)絡(luò)可以簡(jiǎn)潔地表示各種邊緣分布，其模型的表達(dá)能力強(qiáng)，推理速度快，具有廣泛應(yīng)用前景。針對(duì)和積網(wǎng)絡(luò)理論體系中的有效性驗(yàn)證問(wèn)題，通過(guò)分析和積網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)性質(zhì)，給出驗(yàn)證和積網(wǎng)絡(luò)有效性的兩個(gè)算法及其適用場(chǎng)景，并通過(guò)定理證明確保算法的正確性。還提出一種新的和積網(wǎng)絡(luò)中生成樹個(gè)數(shù)的計(jì)算方法。

論文算法1的計(jì)算復(fù)雜度為Ο(n×m2)，與網(wǎng)絡(luò)結(jié)點(diǎn)個(gè)數(shù)和變量個(gè)數(shù)相關(guān)，利用和積網(wǎng)絡(luò)能夠快速計(jì)算邊緣分布的特點(diǎn)進(jìn)行構(gòu)造。算法2的計(jì)算復(fù)雜度為Ο(n[h/2])，與網(wǎng)絡(luò)高度和變量個(gè)數(shù)相關(guān)，首先分析和積網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)性質(zhì)，找到網(wǎng)絡(luò)與生成樹之間的關(guān)系，根據(jù)結(jié)構(gòu)特點(diǎn)進(jìn)行構(gòu)造。

現(xiàn)已發(fā)現(xiàn)和積網(wǎng)絡(luò)是特殊形式的前饋神經(jīng)網(wǎng)絡(luò)和概率卷積網(wǎng)絡(luò)。和積網(wǎng)絡(luò)的應(yīng)用已經(jīng)不限制在概率圖模型的框架中，將逐漸與深度神經(jīng)網(wǎng)絡(luò)一樣有廣泛的影響。但和積網(wǎng)絡(luò)的理論體系仍需完善，例如，和積網(wǎng)絡(luò)中的MAP推理的復(fù)雜性，學(xué)習(xí)和積網(wǎng)絡(luò)的過(guò)程中合適的消耗函數(shù)是否存在等問(wèn)題。