馬爾可夫隨機域的線性和并行學(xué)習(xí)

1、馬爾可夫隨機域的線性和并行學(xué)習(xí)Yariv Dror Mizrahi YARIVMATH.UBC.CAMisha Denil MISHA.DENILCS.OX.AC.UKNando de Freitas1;2;3 NANDOCS.OX.AC.UK加拿大英屬哥倫比亞大學(xué)英國牛津大學(xué)加拿大先進的研究所,CIFAR NCAP程序摘要We introduce a new embarrassingly parallel pa-我們引入一個新的令人尷尬的并行參數(shù)馬爾科夫隨機學(xué)習(xí)算法不附帶條件的參數(shù)是一種有效的字段為一大類的實用模型。我們的算法并行化自然派系以及為圖的有界、 其復(fù)雜性是程度的線性的在派系數(shù)目。

2、與其競爭對手不同我們的算法是完全平行和對數(shù)它也是高效的、 需要的數(shù)據(jù)模型只有數(shù)據(jù)到本地充分統(tǒng)計量估計參數(shù)。1.介紹馬爾可夫隨機場 (集控) 也稱為無概率圖模型、 是無處不在的結(jié)構(gòu)有顯著影響的概率模型一大批領(lǐng)域、 包括計算機視覺 (李,2001 年; ; ;Szeliski et al., 2008 年)、 計算攝影和圖形 (et al.加爾, 2004 年)、 計算神經(jīng)科學(xué)(艾克利et al., 1985 年)、 生物信息學(xué) (諾華et al., 2007 年)、 傳感器網(wǎng)絡(luò) (劉 & 伊勒爾, 2012年)、 社會開辟 (- 施特勞斯池田, 1990年)、 馬爾科夫邏輯 ( 理查森與多明戈斯

3、, 2006 年)、 自然語言處理 (拉弗蒂et al., 2001 年; ; ;薩頓&麥卡勒姆, 2012 年) 和統(tǒng)計物理 (Kindermann & Snell, 1980年)。正如指出在溫賴特和Jordan(2008年) 也有很多應(yīng)用程序在統(tǒng)計中、 約束滿足與組合優(yōu)化、 糾錯碼和流行病學(xué)。不出意料、 這許多的綜合治療手段重要的話題似乎在過去的四年 (Kindermann- 斯內(nèi)爾, 1980 年; ; ;勞里岑, 1996 年; ; ;布雷莫, 2001 年;科勒和弗里德曼, 2009 年; ; ;墨菲, 2012 年).盡管巨大的成功，這些模型擬合的影響他們的數(shù)據(jù)仍然是一個艱巨的挑戰(zhàn)

4、。雖然對數(shù)似然是通常凸的參數(shù)，這些模型的梯度是棘手的。在許多情況下，在這些模式中的最大似然是數(shù)據(jù)高效在漸變中的數(shù)據(jù)一詞可以的的感覺可以輕松地預(yù)計算，使其評價期間瑣碎優(yōu)化。使用最大似然的主要困難就是不高效的模型因為評估梯度涉及到在模型計算的期望分布。這就要求指數(shù)評價與一筆許多條款，其中是的頑固性甚至適度中型的模型。確切的最大似然難治性已促使許多近似的介紹參數(shù)估計的方法 (Besag, 1975年; 辛頓,2000 年; ;Hyvarinen, 2005 年; ;馬林 et al., 2010 年; ;瓦蘭 et al.,2011 年; ;馬林和德弗雷塔斯, 2011 年; ;斯沃 et al.,

5、 2011 年).一類重要的這一問題的近似解法近似的隨機逼近方法從分布模型，利用樣本模型術(shù)語通常通過 mcmc 方法。這種模擬是昂貴的和許多樣品往往需要準確的估計。此外，在設(shè)置位置的參數(shù)或數(shù)據(jù)必須被分布到許多機器這種仿真造成更多困難。另一種方法是對近似極大似然目的構(gòu)造的替代方案。領(lǐng)先在這一領(lǐng)域的方法是偽的可能性。在這種方法磁流變液中的所有變量的聯(lián)合分布被取代按條件分布為每個產(chǎn)品變量。替換產(chǎn)品的聯(lián)合分布條件句的消除模型期限從漸變擬似然目標，繞過最大似然估計模型效率低下。然而，偽似然不是高效的因為數(shù)據(jù)條件分布往往取決于實際的數(shù)據(jù)和參數(shù)的當前值。我們回到這個在一節(jié)中詳細的問題2.3.采用偽似然在分布

6、式環(huán)境中的也是很難，因為條件分布共享參數(shù)。幾位研究者有解決這一問題建議 disjointly 近似的擬似然優(yōu)化每個條件和參數(shù)相結(jié)合使用某種形式的平均 (Ravikumar et al., 2010 年;威塞爾與英雄三, 2012 年; ;劉 & 伊勒爾, 2012 年).在本文中，我們介紹一參數(shù)估計新方法在集控不附帶條件的參數(shù)，避免了模型效率低下的一個重要的最大似然類模型，同時保留其數(shù)據(jù)的效率。此外，我們的算法是令人尷尬的平行可以在未經(jīng)修改的分布式環(huán)境中實現(xiàn)。我們的算法取代聯(lián)合最大似然問題與很多規(guī)模較小的輔助的最多的集合能獨立解決的可能性問題。我們證明，如果輔助問題滿足一定的條件，中的輔助問題

7、的相關(guān)參數(shù)收斂到關(guān)節(jié)中的真實參數(shù)值模型。我們的實驗結(jié)果表明良好的性能在這種情況下取得和那良好的性能仍然是當不滿足這些條件實現(xiàn)。違反犧牲理論收斂條件換取，甚至進一步計算的儲蓄同時實證性能良好。下一個較強的假設(shè)，我們證明我們的算法是全面聯(lián)合分布的正好等于最大可能性。雖然不直接適用，提供了這一結(jié)果額外洞察為什么我們的方法是有效的。最近，和獨立，介紹一類似的方法在下高斯的圖形化模型由孟 et al.(2013年)。在那張紙，作者認為本地居民區(qū)的節(jié)點，而我們認為鄰里派系，他們依靠凸松弛通過Schur 補從中他們逆的算法協(xié)方差估計。在修訂這時間紙，同一批作者已經(jīng)表明，收斂性對與它們的方法參數(shù)真值率是可比性

8、以集中最大似然估計 （孟 et al.,2014).雖然我們的工作和孟 et al.到達分布通過不同的路徑，而是他們的學(xué)習(xí)限于 (成對) 高斯圖形模式，均它是能夠利用圖形結(jié)構(gòu)的作品展示超越低樹寬到設(shè)計算法數(shù)據(jù)和模型高效和展覽好實證性能。2。模型規(guī)范和目標我們有興趣評估的參數(shù)向量積極的分布p(x j) 0,滿足馬爾可夫?qū)傩缘臒o向圖g .這是建造 -的構(gòu)造,可以表示為一個產(chǎn)品因素,每一個最大的集團,在C組最大派系的G、C(xc j C)0是勢函數(shù)或因素相關(guān)變量的小團體c、Z()分區(qū)功能:、在我們學(xué)院的搜索模型ten use exponential functions to represent th

9、e potentials,一個使用指數(shù)函數(shù)代表的潛力被稱為能源,我們將假設(shè)選擇這樣參數(shù)是可識別的。結(jié)果聯(lián)合distribu -可以寫成一個吉布斯分布當能量是一個線性函數(shù)的參數(shù),即tor源自我的值變量,我們有一個最大熵或?qū)?shù)線性模型(瓦瑟曼,2004;布赫曼et al .,2012;墨菲,2012)。在這些特點模型也被稱為地方足夠的統(tǒng)計數(shù)據(jù)。符號:我們用x來指代所有變量的向量(節(jié)點)。當需要時,我們增加的精度符號用S來表示所有變量的設(shè)置和使用xS theMRF所有變量的向量。我們限制符號n和c,開方xn指的是觀察磁流變液中所有的變量,我指的子集與集團有關(guān)的變量c。最后廈門指節(jié)點的形式觀察。2.1

10、。最大似然(總的來說)沒有馬克斯-封閉形式的解決方案imum似然(ML)估計的參數(shù)基于磁流變液,因此梯度優(yōu)化是必要的?？紤]遵守最大熵模型c索引最大派系的地方。按比例縮小的日志,可能是由這是一個凸函數(shù)。參數(shù)的導(dǎo)數(shù)的一個特定的小團體是由當方程(4)的預(yù)期功能問(x)模型分布。對于許多感興趣的模型數(shù)量是棘手的。的導(dǎo)數(shù)log-likelihood對比模型期望對特性的預(yù)期值數(shù)據(jù),在優(yōu)化這兩個詞將平等和em -pirical分布特性將匹配模型的預(yù)處理措辭。2.2。最大Pseudo-Likelihood克服的棘手問題計算expec -界定模型分布,pseudo-likelihood con -橫梁簡單fac

11、torised目標函數(shù),當表示所有的組件形式的數(shù)據(jù)向量,除了組件。(與稀疏模型連通性,我們只需要鄰居的情況節(jié)點。)在二進制,對數(shù)線性情況下,梯度目標可以以對比的形式來表達,2.3。模型和數(shù)據(jù)效率有兩個條款的梯度方程5。第一個詞是一個實證的期望派對之前可以預(yù)先計算參數(shù)優(yōu)化這學(xué)期開始,使梯度非常便宜在優(yōu)化評估。ML梯度數(shù)據(jù)來看是與期望模型分布,這是一個許多配置求和成倍增長。對于大型這學(xué)期模型是棘手的。我們描述這種情況說,ML估計數(shù)據(jù)有效,因為只涉及數(shù)據(jù)條款計算效率。然而,ML不是有效率模型字母系數(shù),因為梯度是棘手的模型來看,和評估的困難是主要動機像偽另類的發(fā)展目標可能性。Pseudo-likeli

12、hood地址模型效率低下的從梯度ML通過消除模型來看,這使pseudo-likelihood模型有效。然而,pseudo-likelihood不是數(shù)據(jù)有效,因為計算梯度需要訪問完整的條件分布因為這個外求和數(shù)據(jù)。必須為每個梯度評價計算例子。(請注意,對于二進制模式充分條件之-spond物流回歸,所以任何擴展的進步邏輯回歸模型和數(shù)據(jù)集將非常大在這里使用)。在接下來的部分中,我們介紹一個線性和并行(圈)算法,它使用一個特定的分解避免成本指數(shù)的圖形在ML,pseudo-likelihood圈完全并行和維護數(shù)據(jù)ML估計的效率。重疊上都因此模型和數(shù)據(jù)有效。3。算法描述圈算法操作通過分裂聯(lián)合pa -參數(shù)估計

13、問題分成幾個獨立的子任務(wù)并行可以解決的問題。一旦子-問題已經(jīng)解決,它結(jié)合了解決方案每個子問題成完整的問題提出的解決方案。我們定義其1-neighbourhood固定小團體問包含的所有變量問本身以及變化可以在問至少有一個鄰居。重疊上創(chuàng)建一個為每個最大小團體的子問題。最初的問題,定義了一個輔助的MRF變量水乳型細節(jié)如何構(gòu)造輔助磁流變液將討論后,現(xiàn)在我們假設(shè)一個輔助在水基磁流變液,它包含一個小團體。算法1圈輸入:磁流變液與最大派系C構(gòu)造輔助變量水基磁流變液。估計參數(shù)ML的輔助MRF結(jié)束參數(shù)化的變量在問一樣問原來的問題。圈派生參數(shù)向量問的問題估計參數(shù)在auxiliaryMRF基地使用最大似然參數(shù)和閱讀

14、集團直接問。算法的步驟總結(jié)-算法1的存有。在對數(shù)線性模型估計參數(shù)向量的最大似然一特的輔助磁流變液的相關(guān)衍生品這種方法是數(shù)據(jù)有效,因為足夠的統(tǒng)計數(shù)字很容易的預(yù)先計算。更多的,結(jié)束,數(shù)據(jù)向量xn可以存儲在一個分布式煩惱離子,節(jié)點估計auxiliaryMRF只需要-荷蘭國際集團(ing)訪問sub-vector xAqn。此外,重疊上自期望E模型有效的。水乳型的變量數(shù)量時很容易計算小。為了說明這一點,考慮所示的模型如圖1所示。密集的圖形,如限制博爾茨-曼機器,列舉了成本的指數(shù)所有的變量Aq是禁止的。然而,對于其他感興趣的實際磁流變液,包括晶格和嵌合體。(2011年Denil & de Freitas

15、),這個成本是可以接受的。3.1。建設(shè)輔助MRF重疊上的有效性來自于適當?shù)臉?gòu)造-輔助的MRF。如前所述,輔助-iliary MRF必須包含小團體問,必須支持的聯(lián)合模型中相同的方式。這從上一小節(jié)中需求是明確的,否則算法1的最后一步將是無效的。分析部分中我們將會看到,這是可取的auxiliaryMRF那樣接近邊緣分布xAq越好。這意味著我們必須包括所有派系從最初的MRF Aq子集。-盟友,邊緣化可能會引入額外的派系呈現(xiàn)在原始的聯(lián)合分布。很明顯,這些在Aqnq派系可以只涉及變量,但決定他們的確切結(jié)構(gòu)一般是很困難的圖1所示。左列顯示了幾種流行的磁流變液:(一)re -嚴格的玻耳茲曼機(元),(b)連鎖

16、圖,2 -(c)維伊辛網(wǎng)格,(D)嵌合體3 3 4格,和3 D(e)伊辛晶格。右邊顯示的是對應(yīng)的1 -社區(qū)組織利益派系的(綠色)。模型(b)(e)有小1-neighborhoods和能有效地學(xué)習(xí)圈算法。我們考慮三個構(gòu)造輔助策略磁流變液,這是區(qū)分他們?nèi)绾未偈剐F體結(jié)構(gòu)Aq n問。這三個策略如下。準確:在這里我們計算數(shù)量的確切結(jié)構(gòu)邊際分布在基地從最初的問題。我們有選擇我們的測試模型的邊際真正的很容易計算。密度:對于許多類模型的邊際水乳型2.2圖2。左:相對誤差參數(shù)估計相比最大似然圈和pseudo-likelihood 4 4伊辛網(wǎng)格。標準偏差的幾個運行。正確的:每個算法參數(shù)估計的方差包括一個完全支

17、持集團對水乳型n問近問的每一個選擇(例如,這是在晶格模型)。假設(shè)邊際al -茂密的變體具有這種結(jié)構(gòu)的方法。這有時會選擇最大邊際,但避免了要求顯式計算其結(jié)構(gòu)。成對地:創(chuàng)造高精確和密集的策略訂單方面的輔助MRF。而高階術(shù)語確實存在的邊界離散的磁流變液,它是computa -包括他們操作不方便,因為增加許多參數(shù)為每個子問題。我們兩兩的變體使用相同的圖結(jié)構(gòu)致密,但這里我們在內(nèi)只有一元潛力和二進制Aq n問。結(jié)果為每個子,節(jié)省大量的計算在重疊上的問題,但未能捕捉真正的邊際dis -回波在許多情況下(包括問題提出所有的例子我們考慮問題)。4。實驗在本節(jié)中,我們描述了一些實驗設(shè)計表明,一圈估計量有很好的經(jīng)驗

18、、曼斯。我們專注于小模型,精確的最大值可能是馴良的,以允許性能測量。我們選擇我們的實驗關(guān)注惡魔-起動的準確性,而不是擴展以來的可伸縮性效率和數(shù)據(jù)屬性的重疊上是顯而易見的。本節(jié)中的實驗的目的是展示兩件事:1.一圈估計的準確性并不比它更糟糕主要競爭手,pseudo-likelihood;2.重疊上即使準確的達到良好的性能不使用邊緣結(jié)構(gòu)。在我們的實驗中,我們比較pseudo-likelihood估計對重疊上使用三種不同的策略圖3。左:參數(shù)估計的相對誤差比較最大似然的重疊上和pseudo-likelihood 4.4伊辛晶格。標準偏差的幾個運行。右:參數(shù)估計的方差算法。構(gòu)造輔助MRF previ -討

19、論我們的部分。在每一個情節(jié),行PL對應(yīng)的標簽pseudo-likelihood和ML對應(yīng)于最大likeli -罩。圈D和圈P分別指圈確切的、致密和構(gòu)造-成對地策略荷蘭國際集團(ing)的輔助MRF。我們比較搭,pseudo-likelihood最大lihood估計在三個不同的模型類。第一個是一個44歲的伊辛與4-neighborhoods網(wǎng)格,結(jié)果如圖2所示。第二個是4. 4伊辛晶格與6-neighborhoods,如圖3所示。最后,我們還要考慮嵌合體3 3 3模型,結(jié)果如圖4所示。所有模型的過程是一樣的:我們選擇從隨機生成參數(shù)一致并繪制樣品大約從模型。然后我們適合精確極大似然parame -

20、源物體參數(shù)根據(jù)這些樣本,比較參數(shù)pseudo-likelihood和重疊上獲得的最大值可能性的估計。在每個圖中顯示左邊的陰謀的平均相對誤差參數(shù)估計使用最大似然估計地面實況。具體來說,我們測量為每個估計,平均每組樣本幾個運行。我們還測量方差的估計每個算法在多個運行。在這種情況下,我們mea -確定每個參數(shù)的方差的估計9月-arately這些方差和平均超過所有參數(shù)該模型。這些測量正確的圖所示在每一個人物。我們也顯示方差的供參考這些情節(jié)的最大似然估計。在所有的實驗中,我們看到的性能所有的圈變異基本上是區(qū)分開來pseudo-likelihood,除了少量的樣本。有趣的是,P圈不執(zhí)行明顯惡化比其他圈變體

21、在任何我們的問題被認為是在這里。這很有趣,因為P圈大約-兩兩MRF份額的邊際,這不是見sub -ficient捕捉在任何我們的真正的邊緣結(jié)構(gòu)的例子。圈P也最有效的圈變體我們測試了,因為它所使用的輔助磁流變液最少的數(shù)量的參數(shù)。5。理論在本節(jié)中顯示匹配的參數(shù)聯(lián)合和邊際分布有效,提供了parametrisations選擇正確。然后,我們證明完全sistency圈算法并舉例說明它的連接ML。無向概率圖形可以指定模型,在當?shù)?在馬爾可夫性質(zhì)和條件,的依賴,在全球范圍內(nèi),一個能量函數(shù)Hammersley-Clifford定理(火重疊mersley &克利福德,1971)建立了等價的這兩種表示形式。往往忽略

22、了一個重要事實是,能量功能和分區(qū)功能并不是唯一的。這是但是可以獲得獨特性,對于這兩種功能,通過實施規(guī)范化對一組-ting隨機變量的潛力。這就產(chǎn)生規(guī)范化的概念潛在(Bremaud,2001):定義1。吉布斯?jié)撛趂E(xcjc)gc2C說是歸一化對零如果E(xcjc)= 0時-是否存在t 2 c,xt = 0。(在本節(jié)中,我們使用術(shù)語吉布斯的潛力,或簡單地潛力,指的是能量以匹配的族名clature(Bremaud,2001)。下面的定理中理解圈算法核心作用。證明可以在(Griffeath,1976;Bremaud,1976):定理2。(正常的存在性和唯一性阮氏潛在有一個且只有一個(吉布斯)po -

23、tential規(guī)范化對零對應(yīng)吉布斯分布5.1。搭接參數(shù)假設(shè)我們有一個吉布斯分布p(xS j)因素根據(jù)集團系統(tǒng)C,讓問2攝氏度是一個小團體的興趣。讓輔助磁流變液有相同的數(shù)量簡稱formas邊際分布對水乳型(集團系統(tǒng)Cq)parametrised這樣潛力歸一化對零。圖4。左:相對誤差參數(shù)估計相比ML333圈和pseudo-likelihood嵌合體模型。標準偏差的幾個。正確的:方差的參數(shù)估計算法。我們可以從聯(lián)合在以下獲得的邊際的方式命題3。如果參數(shù)化p(xS j )和p(xAq j)選擇歸一化零,如果參數(shù)識別與尊重勢,然后問=問。證據(jù)。條款E(xq j q)和E(xq金橋)出現(xiàn)單獨的因素在p(xA

24、q j)和p(xAq j)。的存在性和唯一性規(guī)范化的潛力(定理2)這意味著,如果參數(shù)識別。5.2。重疊上的一致性我們是真正的矢量參數(shù)的未知的生成分布p(xS j ?)支持的這種潛力是規(guī)范化對零假設(shè)我們有N iid來自這distribu樣品。ML是考慮到的ML估計和數(shù)據(jù)讓ML對應(yīng)的ML估計輔助磁流變液與真正的參數(shù)。命題4。如果真正的邊際分布con -保留的輔助類的磁流變液,我們問嗎?問N !1。證據(jù)。讓問2攝氏度是一個任意的小團體的利益。這是足以表明ML問。被邊緣化我們有通過搭接參數(shù)(命題3),我們知道嗎?問。自從ML在平滑和參數(shù)化是一致的能力的假設(shè)(例如,見(2012) ),我們也有!嗎?所以

25、注意,在上面的命題,輔助的類磁流變液可以更一般的類的邊際磁流變液,但必須包含后者。漸近,超級fluous在輔助MRF消失為零。5.3。ML的關(guān)系我們證明,在某些(強)的假設(shè),圈完全等于ML。這里的主要結(jié)果所需的假設(shè)下,通過ML和估計邊緣化。假設(shè)我們有一個離散MRF xS因式分解根據(jù)派系C,讓問2攝氏度是一個特定的小團體的利益。我們將利用以下表征ML估計,證明了在(喬丹,2002)。引理5。如果一個分布 p(x)滿足c屬于C然后 p(x)是一種ML估計經(jīng)驗分布 p(x)。這個特性使我們能夠獲得一個明確的表現(xiàn)錫安的ML估計 p(x)。命題6分布是的ML估計p(x)。證據(jù)?？吹竭@我們計算和任意一個小

26、團體c 2 c,c S n q或c水乳型,我們看到, p(xc)= p(xc)通過進一步邊緣化上面的表達式。這表明我們的表達式 p(x)滿足引理5的標準,因此的ML估計 p(x)。假設(shè)我們有一個家庭的分布F xS磁流變液的滿足馬爾可夫性質(zhì),和假設(shè) p(x)2 F p(x)被定義為命題6。與集團相關(guān)定義輔助家庭Fq問，依下列各項證據(jù)?；叵胍幌? p(x)命題6是在F -大前提。因此Fq被定義。 p(xAq)2 Fq anML估計之前因為日志梯度方程5是可能性零當模型和實證分布都是平等的。假設(shè)我們能代表家庭福吉布斯家族,即。此外,假設(shè)我們選擇parametrisation如此歸一化對潛在的功能零。

27、因為F能上演的是吉布斯家族那么auxil -iary家庭Fq吉布斯也可表示的是一個家庭Fq = Fq()= fp(xAq j)j 2 g對于某些域的參數(shù)。我們將再次供給造成這種parametrisation選擇這樣的潛力函數(shù)是歸一化就為零。我們已經(jīng)表明,ML估計 p(x)和 p(xAq)存在于家庭F和Fq,分別。自我們選擇的parametrisations這些家庭規(guī)范化的我們也有獨特的 2ML參數(shù)和 2,p(x )2 F()是一個ML估計 p(x)和p(xAq j )2 F()是一個ML估計 p(xAq)。我們現(xiàn)在可以證明這一節(jié)的主要結(jié)果。定理8。在本節(jié)中使用的假設(shè)下,估計的聯(lián)合參數(shù)通過ML和

28、集成結(jié)果ML分配給相同的結(jié)果作為對施暴者-荷蘭國際集團(ing)的聯(lián)合家庭分布和執(zhí)行MLes -timation的邊際家庭。簡潔,證據(jù)。我們有以下序列的等式:第一個平等的parametrisation F,第二個命題6,第三個命題7和第四遵循parametrisa -Fq。雙方通過加法定理證明在xSnAq的平等。應(yīng)用圈參數(shù)(命題3)定理8我們看到, = q。備注:假設(shè) p(x)2 F等于-人數(shù)加數(shù)據(jù)的經(jīng)驗分布的因素根據(jù)theMRF。這是不太可能在prac -泰斯有限的數(shù)據(jù)。然而,如果真正的模型結(jié)構(gòu)已知,那么這個屬性在無限的極限數(shù)據(jù)。6。結(jié)論我們已經(jīng)提出了一個分布式學(xué)習(xí)算法。實際的磁流變液,每個

29、派系的參數(shù)。估計在不同的機器上。該算法也在對數(shù)線性模型數(shù)據(jù)有效,因為估計每個派系參數(shù)只需要訪問當?shù)刈懔孔帜赶禂?shù)的統(tǒng)計數(shù)據(jù)。不僅是當?shù)氐慕y(tǒng)計數(shù)據(jù)。每個派系的1-neighborhoods,但他們也可以預(yù)先計算的。我們的實驗表明,一圈估計行為同樣pseudo-likelihood和最大似然大樣本大小。然而,這些估計不喜歡相同的數(shù)據(jù)和模型效率的重疊上。最后,我們證明了該估計量是包含-帳篷。這項工作開辟了許多未來工作方向,在-重疊上的應(yīng)用模型選擇問題，與潛變量模型,模型綁定參數(shù)。因為重疊上完全平行,我們的實驗關(guān)注的問題統(tǒng)計效率。然而,在分布式計算平臺上實現(xiàn),作為Apache / Hadoop火花,將非

30、常有價值。其他的理論將PAC的推導(dǎo)抽樣的范圍來提高我們理解com -plexity這些估計確認。我們要感謝亞歷山大Bouchard-Cote,保羅喬爾弗里德曼,Fearnhead Eldad哈伯,弗雷德Roosta,路易斯Tenorio和匿名評論者極大地幫助我們改進這項工作。我們感謝NSERC金融支持。參考文獻Ackley, D. H., Hinton, G., and Sejnowski, T. A learning algo-rithm for Boltzmann machines. Cognitive Science, 9:147169,1985.Agarwala, A., Dontch

31、eva, M., Agrawala, M., Drucker, S., Col-burn, A., Curless, B., Salesin, D., and Cohen, M. Interac-tive digital photomontage. In ACM SIGGRAPH, pp. 294302,2004.Besag, J. Statistical analysis of non-lattice data. Journal of theRoyal Statistical Society. Series D, 24(3):179195, 1975.Bremaud, P. Markov C

32、hains: Gibbs Fields, Monte Carlo Simula-tion, and Queues. Springer-Verlag, 2001.Buchman, D., Schmidt, M. W., Mohamed, S., Poole, D., and deFreitas, N. On sparse, spectral and other parameterizations ofbinary probabilistic models. Journal of Machine Learning Re-search - Proceedings Track, 22:173181,

33、2012.Denil, M. and de Freitas, N. Toward the implementation of aquantum RBM. In NIPS Deep Learning and UnsupervisedFeature Learning Workshop, 2011.Fienberg, S. E. and Rinaldo, A. Maximum likelihood estimationin log-linear models. The Annals of Statistics, 40(2):9961023,2012.Griffeath, D. Introductio

34、n to random elds. In DenumerableMarkov Chains, volume 40 of Graduate Texts in Mathematics,pp. 425458. Springer, 1976.Hammersley, J. M. and Clifford, P. Markov elds on nite graphsand lattices. Unpublished manuscript, 1971.Hinton, G. Training products of experts byminimizing contrastivedivergence. Neu

35、ral Computation, 14(8):17711800, 2000.Hyv arinen, A. Estimation of non-normalized statistical modelsusing score matching. JMLR, 6:695709, 2005.Jordan, M.I. An introduction to probabilistic graphical models,2002.Kindermann, R. and Snell, J. L. Markov Random Fields and theirApplications. American Math

36、ematical Society, 1980.Koller, D. and Friedman, N. Probabilistic Graphical Models:Principles and Techniques. MIT Press, 2009.Lafferty, J. D., McCallum, A., and Pereira, F. C. N. Conditionalrandom elds: Probabilistic models for segmenting and label-ing sequence data. In ICML, pp. 282289, 2001.Lauritz

37、en, S.L. Graphical models. Oxford University Press, USA,1996.Li, S. Z. Markov random eld modeling in image analysis.Springer-Verlag, 2001.Liu, Q. and Ihler, A. Distributed parameter estimation via pseudo-likelihood. In ICML, 2012.Marlin, B. and de Freitas, N. Asymptotic efciency of determinis-tic es

38、timators for discrete energy-based models: Ratio match-ing and pseudolikelihood. In UAI, pp. 497505, 2011.Marlin, B., Swersky, K., Chen, B., and de Freitas, N. Inductiveprinciples for restricted Boltzmann machine learning. In AIS-tats, pp. 509516, 2010.Meng, Z., Wei, D., Wiesel, A., and Hero III, A.

39、 O. Distributedlearning of Gaussian graphical models via marginal likeli-hoods. In AIStats, pp. 3947, 2013.Meng, Z.,Wei, D.,Wiesel, A., and Hero III, A. O. Marginal likeli-hoods for distributed parameter estimation of Gaussian graph-ical models. Technical report, arXiv:1303.4756, 2014.Murphy, K. P.

40、Machine Learning: A Probabilistic Perspective.The MIT Press, 2012.Ravikumar, P., Wainwright, M. J., and Lafferty, J. D. High-dimensional Ising model selection using 1-regularized logisticregression. Annals of Statistics, 38(3):12871319, 2010.Richardson, M. and Domingos, P. Markov logic networks. Ma-

41、chine Learning, 62(1-2):107136, 2006.Strauss, D. and Ikeda, M. Pseudolikelihood estimation for socialnetworks. Journal of the American Statistical Association, 85(409):204212, 1990.Sutton, C. and McCallum, A. An introduction to conditional ran-dom elds. Foundations and Trends in Machine Learning, 4(

42、4):267373, 2012.Swersky, K., Ranzato, M.A., Buchman, D., Marlin, B., and Fre-itas, N. On autoencoders and score matching for energy basedmodels. In ICML, pp. 12011208, 2011.Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov,V., Agarwala, Aseem, Tappen, M., and Rother, C. A compara-tive

43、 study of energy minimization methods forMarkov randomelds with smoothness-based priors. IEEE Transactions onPattern Analysis and Machine Intelligence, 30(6):10681080,2008.Varin, C., Reid, N., and Firth, D. An overview of composite like-lihood methods. Statistica Sinica, 21:542, 2011.Wainwright, M.

44、J. and Jordan, M. I. Graphical models, exponen-tial families, and variational inference. Foundations and Trendsin Machine Learning, 1(1-2):1305, 2008.Wasserman, L. All of Statistics. Springer, 2004.Wiesel, A. and Hero III, A.O. Distributed covariance estimationin Gaussian graphical models. IEEE Tran

45、sactions on SignalProcessing, 60(1):211220, 2012.Yanover, C., Schueler-Furman, O., andWeiss, Y. Minimizing andlearning energy functions for side-chain prediction. In Speed,Terry and Huang, Haiyan (eds.), Research in ComputationalMolecular Biology, volume 4453 of Lecture Notes in ComputerScience, pp.

46、 381395. Springer, 2007.參考文獻艾克，D.H.、 G.，辛頓和謝，T.。一種學(xué)習(xí)算法為玻耳茲曼機。認知科學(xué)，9:147 169，1985 年。加爾，A.，Dontcheva，米，Agrawala，M.，德魯克，在美國，伯恩，A.、 Curless、 B、 D.，salesin 也是這么和科恩，M.互動數(shù)字蒙太奇。在 ACM SIGGRAPH294-302 頁2004 年。Besag J.統(tǒng)計分析非點陣數(shù)據(jù)。雜志皇家統(tǒng)計學(xué)會。D 系列第 24 (3): 179 195，1975年。布雷莫體育馬爾可夫鏈： 吉布斯的田野，蒙特 Carlo 仿真和隊列。施普林格出版社，2001

47、年。布赫曼，D.，施密特，M.W.，Mohamed，美國，普爾，博士和德弗雷塔斯 ；在稀疏、 光譜和其他參數(shù)的二元概率模型。機器學(xué)習(xí)研究學(xué)報-程序跟蹤，22:173 181，2012年。Denil M.和德弗雷塔斯的實現(xiàn) ；量子注重成果的管理。在咬深學(xué)習(xí)和無監(jiān)督功能學(xué)習(xí)講習(xí)班，2011年。Fienberg、 美國 E.和納爾、 A.最大似然估計在對數(shù)線性模型.統(tǒng)計紀事第 40 (2)： 996 10232012 年。Griffeath D.簡介隨機字段。在可數(shù)狀態(tài)馬爾科夫鏈40 卷的在數(shù)學(xué)中的研究生文本,頁 425 458。施普林格，1976年。哈默斯利，J.M.和克利福德，P.馬爾可夫場有限圖和晶格。未出版的手稿，1971年。G.培訓(xùn)產(chǎn)品的專