Sum-Product Networks模型的研究及其在文本分類的應用

李 俊

（1.中國科學院 上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；2.上?？萍即髮W 信息科學與技術(shù)學院，上海 201210；3.中國科學院大學 北京 100049）

Sum-Product Networks模型的研究及其在文本分類的應用

李 俊1，2，3

（1.中國科學院 上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；2.上海科技大學 信息科學與技術(shù)學院，上海 201210；3.中國科學院大學 北京 100049）

圖模型在機器學習有著廣泛的應用。相比圖模型，Sum-Product Networks模型具有更強表達能力和更快的推理速度，所以其在對文本和圖像數(shù)據(jù)建模有著廣泛的應用。本文總結(jié)Sum-Product Networks這一新的深度概率模型的研究進展，先介紹了固定結(jié)構(gòu)的Sum-Product Networks的參數(shù)學習方法，再介紹了根據(jù)不同的輸入數(shù)據(jù)而進行的結(jié)構(gòu)和參數(shù)學習方法。并且介紹了判別式和生成模型的Sum-Product Networks，最后介紹了Sum-Product Networks在文本分類上的應用。

Sum-Product Networks模型；概率模型；數(shù)據(jù)挖掘算法；文本分類

隨著信息社會的發(fā)展，互聯(lián)網(wǎng)上的信息爆炸式的增長，如何有效地處理和組織這些數(shù)據(jù)，成為當前研究的重要課題。圖模型常常被用來對大數(shù)據(jù)建模，它可以簡潔的表示變量的概率分布，并且可以高效的計算和精確的學習模型的參數(shù)。一般情況下，我們常常使用圖模型來簡潔的表示復雜的分布，但是它在參數(shù)學習和推理的時候比較困難，這是由于它在歸一化的時候需要比較大的計算量。而且圖模型在做推理的時候，最壞的情況下會有指數(shù)級別的復雜度。另外隨著變量的增加，圖模型的復雜度會越來越高。深度架構(gòu)[1]可以看成一個有著多層隱變量的圖模型，而且很多的分布只可以用深度網(wǎng)絡來表示。然而在混合一些非凸的似然估計和比較高復雜度的推理讓學習這種深度網(wǎng)絡非常的難。而圖模型雖然在推理上是可處理的，但是其在簡潔表征方面的性能是非常有限的。

而Sum-Product Networks具有很強的表達能力和快速的推理能力。在2011年，Poon和Domingos提出了Sum-Product Networks，通過增加層數(shù)來提高表達能力并且可以非常高效的做推理[2]。SPN可以看成是一個廣義的有向無環(huán)的混合圖，SPN中間層一種小的由product節(jié)點和加權(quán)的sum節(jié)點的SPN結(jié)構(gòu)不斷遞歸的組成的，而最下面的葉子節(jié)點是各個單一變量。Sum節(jié)點可以看成變量在集合上的混合，而product節(jié)點可以看成特征的混合。SPN可以看成概率上下文無關(guān)文法的特例，它有著很好的處理能力和很強的表達能力，這使得SPN有著很廣泛的應用，特別是一些視覺應用中。

1 Sum-ProductNetworks介紹

SPN可以表示為一個有根節(jié)點的有向無環(huán)圖。在這個有向無環(huán)圖里面：葉子節(jié)點是不同分布的單變量。一個有著變量X1，X2，X3，···，Xd的sum-product network（SPN），其葉子節(jié)點（終節(jié)點）是X1，X2，X3，···，Xd，和，···，，SPN里面的非終節(jié)點是sum和product節(jié)點。SPN中sum節(jié)點i和子節(jié)點j連接的邊有一個非負的權(quán)值Wij，所以SPN中sum節(jié)點的值是ΣWjWij，其中Vj代表第j個節(jié)點的值，SPN中product節(jié)點的值表示為孩子節(jié)點值的乘積。如圖1，這是一個根節(jié)點是sum節(jié)點SPN結(jié)構(gòu)，根節(jié)點與下面的各個product節(jié)點分別以0.5，0.2，0.3的權(quán)值連接，通常product節(jié)點和sum節(jié)點在每一層交替出現(xiàn)，product節(jié)點下面一層均為sum節(jié)點，sum節(jié)點在與帶不同權(quán)值的葉子節(jié)點X1，X2，，相連。SPN性質(zhì)：一個容易處理的單一分布是一個SPN，一些有著不相交scope的SPN的乘積仍然是一個SPN；一個以i為根節(jié)點的子SPN表示在該i節(jié)點下scope的分布；一個SPN的scope代表變量出現(xiàn)的集合。當一個sum-product network中sum節(jié)點的孩子有著相同的scop，則這個SPN是完全的；當一個sumproduct network中product節(jié)點下面的孩子節(jié)點變量和其他孩子的節(jié)點變量沒有相反的，則說這個SPN是一致的；一個SPN是完全的并且一致的則該SPN是有效的。SPN中的子節(jié)點作為根節(jié)點時所覆蓋的子網(wǎng)絡也是一個SPN。我們可以將一個 sum-product network用 變量 X1，X2，X3，···，Xd，和···，表示成S（X1，X2，X3，···，Xd，，···，），其中（例如Xi=1則=0，或者Xi=0則=1）。當把所有的變量設為1，可以將其表示為S（*），S（*）=S（1，1，1，1）。S（x）的值定義為一個對已變量x未歸一化的概率分布。如圖S（X1，X2，，）=0.5（0.6X1+0.4）*（0.3X2+0.7）+0.2（0.6X1+0.4）*（0.2X2+ 0.8）+0.3（0.9X1+0.1）*（0.2X2+0.8），所以網(wǎng)絡的多項式系數(shù)是（0.5*0.6*0.3+0.2*0.6*0.2+0.3*0.9*0.2）X1X2+···。

圖1 SPN的結(jié)構(gòu)

2 Sum-Product Networks的發(fā)展

SPN的發(fā)展主要圍繞著怎么學習這個SPN結(jié)構(gòu)。對于SPN學習問題，我們可以用生成式模型或者判別式模型的SPN對數(shù)據(jù)建模學習。生成模型是運用聯(lián)合概率分布P（X，Y）來對數(shù)據(jù)建模，X是輸入數(shù)據(jù)，Y是預測值，它的學習收斂速度更快；而判別式模型是運用P（Y/X）對數(shù)據(jù)建模，在處理分類和回歸問題效果更好。對于生成模型的SPN，在2011年P(guān)oon和Domingos在一個固定結(jié)構(gòu)的SPN結(jié)構(gòu)上學習參數(shù)，他們提出了用在線hard EM算法來學習SPN。對于判別式SPN，在2012年Gens和Domingos在固定結(jié)構(gòu)上學習SPN，并用來處理圖像來分類問題，他們使用Back Propagation的梯度下降的算法來學習SPN結(jié)構(gòu)中的參數(shù)，并且取得了很好的分類效果，但是他們面臨著權(quán)衡SPN靈活性和學習SPN開銷的問題[3]。

對于不固定結(jié)構(gòu)SPN的結(jié)構(gòu)學習問題，在2012年Dennis和Ventura提出了對SPN的結(jié)構(gòu)的學習，但是有很多的局限性。該SPN學習方法在一系列分層結(jié)構(gòu)中讓變量聚類，并且這些聚類在一起的變量，在在相似的樣本里面有相似的數(shù)值，這使得依存關(guān)系很強的變量有比較多的減少（使得似然估計的損失減少）。在該SPN中，在一個區(qū)域中sum節(jié)點的數(shù)量不是可以學習得到的，而是固定的一個輸入?yún)?shù)。這個SPN學習算法是很復雜的，而且不能保證找到一個局部最優(yōu)的似然估計，這也表明這種方法學到的SPN不是非常好的SPN。SPN和和積網(wǎng)絡（一種算數(shù)網(wǎng)絡，AC）[4]，與或圖相關(guān)[5]。在2008年Lowd和Domingos[6]，和2010年Gogateetal[7]分別提出了一種和SPN相關(guān)而且很容易學習的模型，但是有著更加多的限制。Lowd和Domingos的算法在上下文無關(guān)的條件下，學習貝葉斯網(wǎng)絡并使用網(wǎng)絡的推理的代價當做正則項的懲罰。Gogat通過不斷的遞歸搜索在近似獨立的集合中拆分開的變量特征，來學習一個很高樹寬的馬爾科夫網(wǎng)絡。在2013年RobertGens和PedroDomingos提出了第一個在不犧牲SPN表達能力的條件下，來學習SPN的結(jié)構(gòu)的算法[8]。他們的算法并行的遞歸調(diào)用這些遞歸的結(jié)構(gòu)。這個算法可以看做一個混合EM算法（學習sum節(jié)點）和圖模型的結(jié)構(gòu)學習（學習product節(jié)點）。但是這種方法學到的SPN的結(jié)構(gòu)質(zhì)量和所取得的似然估計不太好，里面有很多冗余的節(jié)點和子樹。

圖2 SPN結(jié)構(gòu)學習的遞歸調(diào)用算法

如圖2所示，我們學習SPN的結(jié)構(gòu)時候，輸入的每個樣本是用由一系列變量組成的向量來表示的，所有的訓練樣本構(gòu)成一個矩陣。如果矩陣的列數(shù)（變量數(shù)）為一，則返回該單一變量的分布。如果可以將根據(jù)變量的獨立性，將變量拆分成互相獨立的子集合，則再用該算法遞歸的調(diào)用這些子集并且返回這些學到的子SPN的積（圖2的上部分所示）。否則，將樣本聚類到各個子集合里面，再在各個子矩陣中調(diào)用該算法，從而學習子SPN結(jié)構(gòu)，最后再返回這些帶權(quán)重的子SPN的和。Sum節(jié)點下面的權(quán)值代表著對應子SPN中樣本的數(shù)量比例。如果變量不可以再分割，該算法返回一個完全分解的分布。在一種極端的條件下，如果在樣本數(shù)量|T|=1之前，該算法總是不能找到互相獨立的變量的子集合，該算法將返回分布的密度估計。在通常條件下，當樣本數(shù)量|T|遠遠大于變量數(shù)量|V|的時候，該算法常會將樣本集合進行拆分，當|V|遠遠大于|T|的數(shù)量的時候，該算法常會對變量集合進行拆分。這個算法對變量或者樣本可以有不同的切分結(jié)果，最后都得沒有條件獨立而且容易處理的模型。

運用上面 Robert Gens的SPN結(jié)構(gòu)學習算法，學習得到的SPN結(jié)構(gòu)，觀察發(fā)現(xiàn)里面有一些的節(jié)點是相同的，整個SPN結(jié)構(gòu)有點冗雜，而且學習得到的SPN結(jié)構(gòu)深度比較淺（較深的時候，能得到更強的表示）。對此，Vergari和Di[9]在原SPN學習算法上添加了一些限制條件：限制sum節(jié)點下面孩子節(jié)點的個數(shù)，bagging方法。限制sum節(jié)點下面孩子節(jié)點的個數(shù)，從而使得學到的SPN結(jié)構(gòu)更加深，從而模型的表達能力得到提升，優(yōu)化的參數(shù)也會減少，也提高其魯棒性。bagging方法，在運用上述SPN算法對矩陣進行切割時，初始化時將原矩陣切分為幾個子矩陣（即弱的學習算法）經(jīng)過多輪訓練，再進行投票組成一個子矩陣切分方法（強的學習算法），最后學習得到一個表達能力更強和推理速度更快的SPN結(jié)構(gòu)。

圖3 基于SVD分解的SPN結(jié)構(gòu)學習

對于 Robert Gens的 SPN結(jié)構(gòu)學習的一系列問題，Tameem和 David在 2015年提出了一種基于 SVD分解的SPN結(jié)構(gòu)學習算法[10]。像2013年Robert Gens那樣通過對矩陣進行切割來來學習SPN結(jié)構(gòu)，通過在矩陣中提取一個rank-1的子矩陣來對原矩陣進行切割，其中求解rank-1的算法采用power method算法。如圖，對于一個矩陣，找到了一個rank-1的2*2維子矩陣，這可以將切割為三個部分，按照行對矩陣切割得到兩個SPN結(jié)構(gòu)的sum，對列的切割得到SPN結(jié)構(gòu)的product，在子SPN結(jié)構(gòu)里面，不斷重復這個過程，最終學習得到更好SPN結(jié)構(gòu)。

3 評價方法

由于直接計算馬爾科夫網(wǎng)絡的似然估計不好處理，我們常用假似然估計（PLL），一種計算變量的近視聯(lián)合概率分布的方法，來評價圖模型的好壞。在訓練的時候計算的PLL常被當成一種替代的似然估計。另外也有一些其他圖模型來對數(shù)據(jù)建模：Della Pietra[11]和Ravikumar[12]的方法分別簡稱為DP和L1。L1結(jié)構(gòu)學習是使用Andrew和Gao對L1邏輯擬合的提出的OWL-QN包[13]。使用假似然估計（PLL）來評價的實驗表明，這兩種常用的圖模型均不如SPN。

另外一種評價方法是測試數(shù)據(jù)的推理能力，隨機的從大量的測試樣本數(shù)據(jù)中選取一定比例的詢問和證實數(shù)據(jù)（例如，10%的詢問數(shù)據(jù)q和30%的證實數(shù)據(jù)e）。對于一個選定的測試樣本，一個詢問P（Q=q/E=e）是按照比例隨機的選擇變量和其對應的值。最后記錄給定證實的平均條件概率的log似然估計（CLL）。SPN可以在線性時間里面做準確的推理。而圖模型是非常難做精確的推理，我們常用吉布斯采樣來做近視的求解。SPN的推理速度和準確度遠遠好于圖模型。

4 在文本分類的應用

2011年P(guān)oon和Domingos[3]提出了判別式SPN，并將其運用到CIFAR-10數(shù)據(jù)集的圖片分類的問題上，并且取得了當時最好的分類效果。在2015年Tameem和David[10]提出了判別式SPN結(jié)構(gòu)來對文本數(shù)據(jù)進行分類。假設分類的類別集合為C={1，···，n}。對于訓練數(shù)據(jù)，在類別集合中的每一個類別上，使用基于SVD的方法學習得到一個SPN結(jié)構(gòu)，然后再使用HSIC變換[14]，來提取和分類類別強相關(guān)的特征。再用一個sum節(jié)點將各個類別的SPN結(jié)構(gòu)加起來，即得到一個sum節(jié)點混合的條件分布P（Z/Y=j），其中j∈C，其中sum節(jié)點下面的權(quán)值按各個類別上訓練樣本的數(shù)量比例來確定。從而對于不同的樣本輸入這個網(wǎng)絡，可以的得到預測的類別。

Tameem和David選用了USPS[15]和MNIST[16]的數(shù)字手寫體識別數(shù)據(jù)集來驗證該方法的效果（均轉(zhuǎn)化為文本數(shù)據(jù)，分十個類）。USPS這個數(shù)據(jù)集合每個圖片是16*16的，所以數(shù)據(jù)集合中的每一個數(shù)字圖片可以用一個256維的向量來表示，這個數(shù)據(jù)集中每個樣本由256維的向量來表示，數(shù)據(jù)集有7 291個訓練樣本和2 007個測試樣本；其中訓練數(shù)據(jù)集每一個類別800個樣本，測試數(shù)據(jù)集中每個類別中有300個樣本。而MINIST數(shù)據(jù)集中每個樣本由28*28的向量組成，訓練數(shù)據(jù)集每一個類別有6 000個樣本，測試數(shù)據(jù)集中每一個類別有1 000個樣本。我們輸入這些訓練數(shù)據(jù)，可以學到一個SPN的網(wǎng)絡結(jié)構(gòu)，根節(jié)點代表預測的類別，在測試數(shù)據(jù)集上達到比傳統(tǒng)分類方法更高的分類精度。

5 結(jié)束語

在機器學習、數(shù)據(jù)挖掘領域中，我們常需要運用概率模型來對數(shù)據(jù)建模。我們通常使用的圖模型只可以簡潔地表示完全概率分布，而Sum-product networks作為一種有著多個隱含層的概率模型，SPN還可以簡潔的表示各種邊緣分布。此外SPN有著更強的表達能力，還有更加快速和精確的推理能力。在未來處理具體的機器學習應用中，SPN會有著更加廣泛的應用。

參考文獻：

[1]Y.Bengio.Learning deep architectures for AI.Foundations and Trends in Machine Learning[J].2009：1-127.

[2]Hoifung Poon and Pedro Domingos Sum-Product Networks:A New Deep Architecture[C].Uncertainty in Artificial Intelligence 27.

[3]Robert Gens and Pedro Domingos Discriminative Learning of Sum-Product Networks[C].Advances in Neural Information Processing Systems，2012：3248-3256.

[4]Darwiche，A.A dierential approach to inference in Bayesian networks[J].Journal of the ACM，2003，50（3）:280-305.

[5]Dechter，R.Mateescu，R.AND/OR search spaces for graphical models[J].Artificial intelligence2007，171:73-106.

[6]Lowd，D.and Domingos，P.Learning arithmetic circuits[C]. Uncertainty in Artificial Intelligence，2008.

[7]Gogate，V.，Webb，W.，and Domingos，P.Learning effcient Markov networks[C].Advances in Neural Information Processing Systems，2010，748-756.

[8]Gens，R.，Domingos，P.:Learning the structure of sumproduct networks In Proceedings of the 30th International Conference on Machine Learning[C].2013：873-880.

[9]Vergari，Antonio and Di Mauro，Nicola and Esposito，F(xiàn)loriana Simplifying，Regularizing and Strengthening Sum-Product Network Structure Learning [C].Machine Learning and Knowledge Discovery in Databases，2015：343-358.

[10]Tameem Adel，David Balduzzi，and Ali GhodsiLearning the StructureofSum-ProductNetworksviaan SVD-based Algorithm[C].Uncertainty in Artificial Intelligence，2015.

[11]Della Pietra，S.，Della Pietra，V.，and Laerty，J.Inducing features of random fields[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，1997（19）:380-392.

[12]Ravikumar，P.，Wainwright，M.J.，and Laerty，J.D.Highdimensional using model selection using L1 regularized logistic regression[J].The Annals of Statistics，2010，38（3）: 1287-1319.

[13]Andrew，G.and Gao，J.Scalable training of L1-regularized log-linear models[C].Proceedings of the 24th international conference on Machine learning，2007：33-40.

[14]A.Gretton，O.Bousquet，A.Smola，and B.Scholkopf.Measuringstatisticaldependence with Hilbert-Schmidt norms[J].In AlgorithmicLearning Theory，2005，37（34）:63-77.

[15]J.J.Hull.A database for handwritten text recognition research[J].Pattern Analysis andMachine Intelligence，IEEE Transactions on，1994，16（5）:550-554.

[16]Y.LeCun，L.Bottou，Y.Bengio，and P.Haffner.Gradientbased learning applied to document recognition [J].In Proceedings of the IEEE，1998，86（11）:2278-2324.

The development of Sum-Product Networks model and its application in text classification

LI Jun1，2，3
（1.Shanghai Institute of Microsystem and Information Technology，Chinese Academy of Sciences，Shanghai 200050，China；2.School of Information Science and Technology，ShanghaiTech University，Shanghai 201210，China；3. University of Chinese Academy of Sciences，Beijing 100049，China）

Graph model is wide used in the area of machine learning.Compared with Graph model，the model of Sum-Product Networks is more representative and faster than graph model，thus it is widely used to model text and image data.This paper firstly summarizes the research progress of Sum-Product Networks，new deep probability model，and then introduces the method of parameter learning with fixed structure of SPN and the method of structure learning based on different input data for Sum-Product Networks.At last，the paper introduces the application of discriminant Sum-Product Networks in text classification.

Sum-Product Networks model；probability model；data miningalgorithm；text classification

TP391

A

1674－6236（2016）24-0042-04

2015-12-25 稿件編號：201512259

李 ?。?990—），男，湖南邵陽人，碩士。研究方向：信號與信息處理、機器學習，數(shù)據(jù)挖掘。