隱高斯樹的分層合成
——一種基于信息論解決合成問題的方法

Ali Moharrer 魏雙慶 駱 源

1路易斯安那州立大學(xué)巴吞魯日70803

2上海交通大學(xué)上海200240

3上海交大-中國聯(lián)通-廣視通達(dá)大數(shù)據(jù)聯(lián)合實驗室上海200240

引言

本文基于高斯分布，通過提出高效合成概念，研究“具有規(guī)定聯(lián)合密度的隨機向量產(chǎn)生機制”。粗略地說，這種高效性可以通過尋找表達(dá)隨機向量整體依賴性的、最緊湊的公共隨機源實現(xiàn)。如果我們能從隨機變量樣本提取出這些公共隨機性，剩下的樣本就是隨機噪聲。本文所提出的方法不但可以揭示數(shù)據(jù)隱含的內(nèi)部聯(lián)系，而且適用于在機器學(xué)習(xí)領(lǐng)域中產(chǎn)生仿真數(shù)據(jù)。最近的幾篇使用相關(guān)度量來解決某些特定的檢測和估計問題的論文[1-3]，便是旨在找到這樣的公共隨機源。此外，由文獻(xiàn)[4]、[5]表明，通過諸如變分自編碼器(VAEs)和神經(jīng)網(wǎng)絡(luò)(Neural Networks)等機器學(xué)習(xí)工具及其信息瓶頸分析方法來學(xué)習(xí)隨機系統(tǒng)中最緊湊的參數(shù)，可得到更好的泛化效果。

在本文中，我們的目標(biāo)是提出一個直觀可操作的配置方法來合成某些類型的聯(lián)合密度?？傮w思路是對統(tǒng)計數(shù)據(jù)中的隱藏公共隨機性進(jìn)行建模和模擬，然后依次加入獨立噪聲元素來模擬整體數(shù)據(jù)。具體來說，可以通過將適當(dāng)數(shù)量的隨機比特輸入隨機信道來實現(xiàn)這一模型，其輸出向量的經(jīng)驗統(tǒng)計在給定衡量標(biāo)準(zhǔn)下滿足期望值。本文的工作在數(shù)據(jù)合成領(lǐng)域中有廣泛的應(yīng)用：1)數(shù)據(jù)匿名化，例如可以保護(hù)包含了敏感個人信息的真實數(shù)據(jù)集的隱秘性和保密性[6]；2)數(shù)據(jù)集擴充，例如可以用于擴展訓(xùn)練特定機器學(xué)習(xí)算法的數(shù)據(jù)集[7]。在這些用途中，數(shù)據(jù)的特定統(tǒng)計學(xué)特征被捕捉并被用于合成新的數(shù)據(jù)。

我們旨在為如下情況提供解決方案：由規(guī)定的輸出統(tǒng)計數(shù)據(jù)引出一個(隱)高斯樹，假定其聯(lián)合分布為高斯分布，而且隱變量和觀測變量的條件統(tǒng)計獨立關(guān)系具有稀疏的樹結(jié)構(gòu)。由于模型中出現(xiàn)的條件獨立關(guān)系與協(xié)方差矩陣的逆矩陣中的零點直接對應(yīng)，尤其是其稀疏的結(jié)構(gòu)以及現(xiàn)有的拓?fù)鋵W(xué)習(xí)的高效算法[8-9]，使高斯圖模型受到廣泛關(guān)注，并在社交網(wǎng)絡(luò)、生物學(xué)、經(jīng)濟(jì)學(xué)中有不同的用途[10-11]。

2 相關(guān)工作

要解決合成方案中的高效性問題，Han和Verdu[12]引入了給定信道可分解性的概念，該概念被定義為產(chǎn)生輸出數(shù)據(jù)所需的最小隨機性，并用合成密度和規(guī)定密度之間的總變分距離(Total Variation Distance)度量。在文獻(xiàn)[13]、[14]中，作者的目標(biāo)是定義n個相關(guān)隨機變量的公共信息，以進(jìn)一步解決這種問題。雖然他們將以前的工作從雙變量的情況推廣到n個隨機變量，但是他們?nèi)匀徊捎门cWyner[15]一樣的方案，即用單一源來定義這樣的公共隨機性。這對我們的仿真方案來說是一種特殊的情況，其中所有的變量都通過一個公共變量相互關(guān)聯(lián)，我們將這種結(jié)構(gòu)定義為星型樹。在文獻(xiàn)[16]中，作者將兩個聯(lián)合高斯向量之間的公共信息描述為奇異值的函數(shù)，其中奇異值與兩個高斯隨機向量之間的協(xié)方差矩陣有關(guān)，然而，他們?nèi)匀皇菍㈦S機向量分成兩組，這與Wyner的論文[15]中的雙變量情況類似。

3 系統(tǒng)模型

以上介紹的相關(guān)研究僅僅考慮了兩組隨機向量，在本節(jié)中，我們提出一種新的合成方式，不再只考慮通過一個輸入向量來合成數(shù)據(jù)，而是引入了代表相關(guān)系數(shù)符號信息的伯努利變量B作為另一種隨機源，提高了合成效率。

在隱高斯樹中，我們將處理兩組變量。X={X1,X2,…Xn}表示高斯樹上n個觀測變量，其協(xié)方差矩陣∑X已給出。向量集Y={Y1,Y2,…Yn}對我們來說是隱藏的，是需要被估計的。值得注意的是，在使用∑X生成隱高斯樹時，需要滿足文獻(xiàn)[11]中的某些條件。已有一些文獻(xiàn)，如文獻(xiàn)[10]、[17]提出了高效的算法來推算高斯樹的參數(shù)。事實上，Choi等人提出了一種新的遞歸組合(RG)算法及其改進(jìn)版本，即Chow-Liu RG(CLRG)算法，這種算法能恢復(fù)出一棵結(jié)構(gòu)和風(fēng)險與原先一致的高斯樹，這支持了算法的正確性。他們引入了樹的度量，即兩兩相關(guān)值的絕對值的負(fù)對數(shù)，來運行算法。在本文中，我們假設(shè)使用上述算法之一來獲得隱高斯樹的參數(shù)和結(jié)構(gòu)信息。

在這種合成問題中，我們主要關(guān)注的是合成高斯樹所需輸入的公共隨機比特數(shù)量的高效性。這一高效性表征為定義適當(dāng)?shù)碾S機序列以及包含那些序列的隨機容器(我們分別定義為隨機碼字和碼本)。我們用輸入的碼率來定義合成系統(tǒng)的復(fù)雜度，因為極小化這一碼率會減少生成輸出數(shù)據(jù)所需的公共隨機比特位數(shù)。為了讓公共隨機源盡可能緊湊，我們從統(tǒng)計數(shù)據(jù)中提取盡可能多的獨立隨機性。特別的，由于隱高斯樹具有固有的符號奇異性，我們認(rèn)為這種不確定性可以進(jìn)一步幫助我們降低高斯樹的合成率。為了闡明這一點，考慮下面的例子。

例1：考慮圖1所示的高斯樹，它由X1，X2，X3，X4四個觀測變量組成，通過兩個隱藏節(jié)點Y1(1)和互相連接。定義為輸入和輸出X1之間的相關(guān)值(邊權(quán))，類似地，定義其他相關(guān)值。定義符號Bj(1)∈{-1,1}，j∈[1,2]作為第j個輸入值對應(yīng)的二元變量，我們將會看到它反映了兩兩相關(guān)值的符號信息。對于圖1展示的樹，可以假設(shè)符號，而對應(yīng)，其中i∈[1,2]or i∈[3,4]是使用某種推斷算法，比如RG算法[10]所得到的相關(guān)值。同樣的，定義符號。容易看出恢復(fù)相關(guān)值推導(dǎo)出相同的協(xié)方差矩陣∑X，表明了在這個高斯樹中的符號奇異點問題。尤其是，對每個兩兩相關(guān)系數(shù)，k＜ι∈[1,2,3,4]，如果xk，xι有相同的父節(jié)點，可以得到，其中第二個等式是因為不管符號值是多少，等于1。現(xiàn)在，根據(jù)符號在{-1,1}中的取值，可以得到。并且，我們沒有辦法用目前所觀察到的聯(lián)合分布信息來區(qū)分這兩種情況。相似的，如果xk、xι連接不同的輸入結(jié)點，則，第二個等式成立是因為。同樣的，無法僅根據(jù)輸出的相關(guān)值恢復(fù)符號信息。

圖1 一個以Y1(1)，Y1(2)為隱藏節(jié)點的簡單高斯樹

這證明了這樣的符號奇異點可以被視為另一種隨機噪聲源，它可以進(jìn)一步幫助我們降低合成高斯樹所需的碼率。事實上，我們可以將圖1中的高斯樹想象成一個通信信道，來自的信息流通過四個信道，伴隨獨立的加性高斯噪聲變量，從而生成輸出。我們引入以為分布參數(shù)的二元伯努利符號隨機變量，反映了兩兩相關(guān)系數(shù)的符號信息。事實上，我們可以將輸入到輸出定義為以下的仿射變換。

我們的目標(biāo)是描述可達(dá)到/可實現(xiàn)的碼率范圍，并通過一個合成方案來生成密度為的所有高斯樹，其中b(1)可取不同值，合成的混合密度與真實混合高斯樹密度要求很難用總變分度量區(qū)分。為了達(dá)到我們的目的，首先生成許多采樣序列和來形成碼本。碼本的大小為，其中和是碼率，這和符號以及隱藏節(jié)點碼字有關(guān)。每一次生成輸出序列時，我們首先任意的選擇一個符號和隱藏節(jié)點碼字，然后使用(1)中定義的合成信道來獲得一個特定的輸出序列XN。我們的目的是通過生成序列的統(tǒng)計特性，即趨近于期望的統(tǒng)計數(shù)據(jù)，來形成碼率的下界。具體來說，我們定義下界為，其中是輸出X和輸入向量之間的互信息量。這對應(yīng)于在高斯樹假設(shè)下求解最小可達(dá)速率。等價的，我們尋找的最優(yōu)值來最大化由描述的可達(dá)速率范圍。為了闡明這種分層設(shè)計是如何影響統(tǒng)計數(shù)據(jù)的模擬的，考慮下面這個例子。

例2：在這個例子中，我們只證明這種分層方法確實能夠生成目標(biāo)高斯密度的樣本。因此，為了簡單起見，我們不考慮例子中的符號變量。高斯樹此時具有如圖2所示的叉形結(jié)構(gòu)。

圖2 以Y1(1)為隱藏節(jié)點的簡單高斯樹

這是一個有高斯源Y(1)和B(1)符號輸入并以向量X=[X1,X2,X3]為輸出的隱星形拓?fù)浣Y(jié)構(gòu)，可以按照下式建模。方便起見，我們將符號變量設(shè)為B(1)=1。假設(shè)協(xié)方差矩陣∑x已給出，其對角線上值為，非對角線上的值都相等且為，文獻(xiàn)[18]證明了在這種情況下系數(shù)αi可以被唯一確定，在這個例子中它們都相等且。噪聲方差都被確定且均等于。粗略地說，我們首先生成一個樣本Yi和另一個隨機加性噪聲樣本Zi，根據(jù)(2)得到。前文指出當(dāng)速率時可達(dá)，這里互信息可以通過來計算[19]，其中|.|表示行列式，在本例中，。

正如我們討論的，隨著維度N的增加，樣本數(shù)量指數(shù)增加并接近目標(biāo)高斯密度，文獻(xiàn)[20]也證明了這一點，碼本尺寸以速率增加。

例1和例2展示了我們合成方法的總體思路。在這里，我們給出隱高斯樹在一般情況下的嚴(yán)格問題描述和操作設(shè)置。

1)使用總相關(guān)度量而不是KL散度來顯示收斂性。

2)定義了回溯技術(shù)來合成整個混合高斯樹而不僅僅是觀測向量X。特別的，我們想要強調(diào)多變量合成概念，定義一個具有一定依賴性結(jié)構(gòu)的隨機向量Y來表征公共隨機性并生成公共隨機位，而不是僅僅引入一個變量Y。我們提供了一種分層合成算法，配以相應(yīng)的可達(dá)區(qū)域，來合成能夠?qū)С龈咚箻涞姆植?。在文獻(xiàn)[17]中這樣的情況一般使用受約束的凸優(yōu)化問題來定義，文獻(xiàn)[3]證明了這種一般化假設(shè)的好處。事實上，針對盲源分離問題，Steeg等人使用了一種基于多層公共變量的新方法，并證明了他們提出的方法優(yōu)于之前的算法。與文獻(xiàn)[3]、[17]類似，我們也考慮了多變量情況，但不同的是，我們所感興趣的是表征可實現(xiàn)的速率，從而合成滿足特定類別的隱高斯分布，即隱高斯樹。值得指出的是，本文的結(jié)果在假定的結(jié)構(gòu)化合成框架下給出。因此，雖然我們通過定義一個最優(yōu)化問題，證明了提出的方法在建模和碼率上都是高效的，但我們并沒有反過來對該方案和速率區(qū)域的最優(yōu)性進(jìn)行討論。

3)在前文的例子中，將符號變量設(shè)為特殊值。在接下來的內(nèi)容中，我們將展示如何利用符號奇異性，將符號變量作為另一個獨立的隨機源來合成受符號模糊性影響的高斯樹。由于相關(guān)符號不確定性帶來的等效噪聲效應(yīng)，我們實際需要的用于合成隱藏連續(xù)變量的比特數(shù)也隨之減少。

例2通過研究一個具體案例，我們提供操作設(shè)置和可實現(xiàn)速率的區(qū)域，從而合成服從PXY的樹形結(jié)構(gòu)的樣本。這里，向讀者推薦文獻(xiàn)[18]，來更全面地研究一般高斯樹結(jié)構(gòu)。我們在更一般化的情形中處理多分層隱高斯樹。圖3展示了一般的合成方案，在每一層i，定義為合成的輸入向量。

例3：考慮圖4所示的情況，其中高斯樹具有兩層輸入。我們可以計算第一層中的兩兩協(xié)方差，其中。輸入向量對于每個給定的都符合高斯分布。因此，可以將碼本C分成部分，每一部分都服從以為協(xié)方差的特定高斯密度。

圖4 兩層高斯樹

下面闡述在這種情況下連續(xù)碼本的生成方法。首先，需要從頂層到第一層生成每一層的碼本。符號碼本是預(yù)先生成的，且僅僅與符合伯努利分布的符號向量有關(guān)。每個符號碼字是一個向量序列，其元素從{-1，1}中選擇。我們也可以用混合高斯碼字來生成頂層碼本每個時隙中每個碼字由所有可能值組成。每一個設(shè)定都表征了一個頂層隱變量的特定高斯分布，所需碼字的數(shù)量為。我們知道要使用中的碼字來生成第二層的碼字，需先從中隨機選擇碼字，然后基于選擇的符號碼字，生成序列并送入信道中。符號向量包含了個符號變量，因此有個不同信道。所以，我們將選擇的序列通過8個不同信道來產(chǎn)生中的一個碼字。注意，這種方式產(chǎn)生的碼字實際上是高斯向量的集合，每一個都對應(yīng)于一個特殊的符號向量。將這一過程重復(fù)次，產(chǎn)生合成下一層所需的全部碼字。圖5展示了前文描述的合成過程。為了生成一個輸出序列，我們需要做的就是隨機地從選擇碼字。然后根據(jù)每個時隙的符號實現(xiàn)，使用對應(yīng)的信道來生成輸出序列。

圖5 合成圖4所示高斯樹的碼本生成方案

因此，為了合成足夠接近真實高斯樹分布的數(shù)據(jù)，需要首先生成頂層碼本和符號碼本，注意合成方案是需要獨立高斯噪聲作為給定的隨機源。

圖5中給出的自頂向下方案，為每一層生成適當(dāng)?shù)拇a本。為了選擇合適的碼字，需要保持追溯輸入輸出的關(guān)系?？紤]每層的輸出，我們回溯生成這種輸出對應(yīng)的輸入碼字。舉例來說，考慮與圖4中相同的高斯樹，為了生成輸出序列XN，我們從對應(yīng)的碼本中隨機的選擇兩個碼字。符號碼字決定了該輸出對應(yīng)的信道，因此在該輸入碼字和生成的輸出之間有著對應(yīng)關(guān)系。類似的，是頂層輸入的輸出，由隨機選擇的碼字生成。圖6展示了由圖4所示的雙層隱高斯樹的合成方案。

圖6 圖4所示高斯樹的合成方法

在圖6中，碼本中不同的顏色對應(yīng)了不同的符號實現(xiàn)。舉例來說，我們知道對應(yīng)頂層符號輸入可以有個不同的符號實現(xiàn)，因此對應(yīng)的碼本中有兩種不同的顏色。同樣，碼本中每個小格包含一個樣本向量，是因為每層通常包含不止一個變量。比如頂層碼本的每個小格包含兩個高斯樣本，對應(yīng)于，其中。在生成方法中，首先隨機地從中挑選序列并形成，然后找到第一層中對應(yīng)的輸入碼字。接著，被選擇的碼字通過給定的高斯信道生成輸出向量。這種情況下，樣本序列(如圖6)是值得注意的是，每層碼字都攜帶了在碼本生成步驟中被確定的對應(yīng)符號信息。

4 仿真結(jié)果

圖7展示了2 000個合成樣本的一維經(jīng)驗密度和不同維度N下的理論高斯密度的比較。特別的，圖7左側(cè)的圖展示了真實輸出密度和樣本歸一化直方圖之間的比較；右側(cè)的圖比較了合成輸出樣本的密度與真實輸出密度?？梢钥闯?，隨著N的增加，輸入的可選序列也隨之增加，期望的高斯密度被更好地擬合，結(jié)果就是我們更加接近要被模擬的高斯密度。

圖7 合成數(shù)據(jù)的比較

特別的，我們可以計算期望高斯密度P(X)和合成密度P(X)之間的KL距離，并觀察到KL距離隨N的變化規(guī)律。計算方法定義如下。

同樣的，在之前的例子中我們指出，由于高斯樹的符號奇異性，我們可以暫且忽略符號變量，即取，并得到與取 統(tǒng)計學(xué)上相同的結(jié)果。我們可以看到B的選擇不影響合成方案的整體表現(xiàn)。同時，隨著維度N的增加，盡管KL距離整體上減少了，但并非單調(diào)遞減。這是因為合成方案的隨機性，也就是說，一些樣本給出了更接近真實高斯密度的結(jié)果。在文獻(xiàn)[20]中，這些樣本被稱作精選碼字，這種影響在高維度中逐漸消退，使KL距離變成了隨N單調(diào)遞減的函數(shù)。如圖8所示。

圖8 當(dāng)，真實數(shù)據(jù)與合成數(shù)據(jù)之間的KL距離

5 總結(jié)

本文基于高斯分布研究“具有規(guī)定聯(lián)合密度的隨機向量產(chǎn)生機制”。與以往的合成方案相比較，我們增加了代表模糊性的伯努利符號環(huán)節(jié)，使得模型能夠利用更廣泛的混合高斯分布隨機向量。這為揭示數(shù)據(jù)隱含的內(nèi)部聯(lián)系，以及在機器學(xué)習(xí)領(lǐng)域產(chǎn)生仿真數(shù)據(jù)，提供了更寬廣的應(yīng)用場景和模型理論。

[1]STEEG G V.Unsupervised learning via total correlation explanation[C]//Twenty-sixth International Joint Conference on Artificial Intelligence,2017:5151-5155

[2]STEEG G V,GALSTYAN A.Low complexity gaussian latent factor models and a blessing of dimensionality[Z].arXiv preprint arXiv:1706.03353,2017

[3]STEEG G V,GAO S,REING K,et al.Sifting common information from many variables[C]//Twenty-sixth International Joint Conference on Artificial Intelligence,2016:2885-2892

[4]ACHILLE A,SOATTO S.Information dropout:Learning optimal representations through noisy computation[Z].arXiv preprint arXiv:1611.01353,2016

[5]SHWARTZ-ZIV R,TISHBY N.Opening the black box of deep neural networks via information[Z].arXiv preprint arXiv:1703.00810,2017

[6]SORIA-COMAS J,DOMINGO-FERRER J.A nonparametric model for accurate and provably private synthetic data sets[C]//The 12th International Conference on Availability,Reliability and Security.ACM,2017:3

[7]DEVRIES T,TAYLOR G W.Dataset augmentation in feature space[Z].arXiv preprint arXiv:1702.05538,2017

[8]CHOI M J,TAN V Y,ANANDKUMAR A.Learning latent tree graphical models[J].The Journal of Machine Learning Research,2011,12:1771–1812

[9]SHIERS N,ZWIERNIK P,ASTON J A.The correlation space of gaussian latent tree models[J].Biometrika,2016,103(3):531–545

[10]DOBRA A,EICHER T S,LENKOSKI A.Modeling uncertainty in macroeconomic growth determinants using gaussian graphical models[J].Statistical Methodology,2010,7(3): 292–306

[11]MOURAD R,SINOQUET C,ZHANG N L.A survey on latent tree models and applications[J].J.Artif.Intell.Res.(JAIR),2013,47:157–203

[12]Han T S,Verd U S.Approximation theory of output statistics[J].IEEE Transactions on Information Theory,1993,39(3):752–772

[13]Yang P,Chen B.Wyner's common information in gaussian channels[C]//IEEE International Symposium on Information Theory(ISIT),2014:3112–3116

[14]Xu G,Liu W,Chen B.A lossy source coding interpretation of wyner’s common information[J].IEEE Transactions on Information Theory,2016,62(2):754–768

[15]Wyner A D.The common information of two dependent random variables[J].IEEE Transactions onInformation Theory,1975,21(2):163–179

[16]Satpathy S,Cuff P.Gaussian secure source coding and wyner's common information[Z].arXiv preprint arXiv:1506.00193,2015

[17]GASTPAR M C.Total correlation of gaussian vector sources on the gray–wyner network[C]//54th Annual Allerton Conference on Communication,Control and Computing(Allerton),2016

[18]MOHARRER A.Information theoretic study of gaussian graphical models and their applications[D].Louisiana State University,2017

[19]MOHARRER A,WEI S.Algebraic properties of solutions to common information of Gaussian vectors under sparse graphical constraints[C]//55th Annual Allerton Conference on Communication,Control and Computing(Allerton).IEEE,2017

[20]CUFF P.Soft covering with high probability[C]//2016 IEEE International Symposium on Information Theory,Barcelona,Spain,2016:2963–2967