網易首頁 > 網易號 > 正文申請入駐

自動推導符號推理算法：張量因式分解和概率線路

2025-05-24 12:11:16　來源: CreateAMind

上海舉報

分享至

What is the Relationship between Tensor Factorizationsand Circuits (and How Can We Exploit it)?

張量因式分解和線路有什么關系(以及如何利用它)？

for probabilistic inference. To this end, we highlighted a number of possible future venues for the matrix and tensor factorization communities that leverage the connection with circuits we established:

designing hierarchical factorizations with non-tree structures (Opportunity 1);

using the property-driven calculus that circuits offer to automatically derive tractable algorithms in a compositional way (Opportunity 2);

treat nonnegative (hierarchical) factorizations as deep latent variable models (Opportunity 3);

devise factorizations over non-discrete and non-linear input spaces (Opportunity 4);

embed logical constraints to realize neurosymbolic systems that can reason with symbolic knowledge (Opportunity 5);

devising alternative ways to compactly encode distributions, going beyond probability masses or densities (Opportunity 6);

as well as devising flexible factorizations by changing only the structure of (some) layers in a circuit representation (Opportunity 7).

https://arxiv.org/pdf/2409.07953

我們強調了矩陣和張量分解社區利用我們建立的電路連接的多個未來研究方向：

設計具有非樹結構的層次分解（機會1）；

使用電路提供的屬性驅動演算以組合方式自動推導可處理算法（機會2）；

將非負（分層）分解視為深度潛在變量模型（機會3）；

設計非離散和非線性輸入空間的分解（機會4）；

嵌入邏輯約束以實現能夠與符號知識推理的神經符號系統（機會5）；

設計超越概率質量或密度的緊湊分布編碼的替代方法（機會6）；

以及通過僅改變電路表示中（某些）層的結構來設計靈活分解（機會7）。

摘要

本文建立了電路表示和張量分解這兩個看似不同但本質上相關的領域之間的嚴格聯系。通過連接這些領域，我們強調了一系列可以使兩個社區受益的機會。我們的工作在電路語言中推廣了流行的張量分解，并在單一的廣義分層分解框架下統一了各種電路學習算法。具體來說，我們引入了一種模塊化的“樂高積木”方法來構建張量化電路架構。這反過來使我們能夠系統地構建和探索各種電路和張量分解模型，同時保持可處理性。這種聯系不僅闡明了現有模型之間的相似性和差異，還為構建和優化新的電路/張量分解架構開發了一個全面的流程。我們通過廣泛的實證評估展示了我們框架的有效性，并強調了張量分解在概率建模中的新研究機會。

1 引言

本文旨在彌合兩個表面上看似遙遠，但實際上密切相關的領域：電路表示（Darwiche & Marquis, 2002; Choi et al., 2020; Vergari et al., 2021）和張量分解（Kolda, 2006; Sidiropoulos et al., 2017）。具體來說，我們建立了這兩種表示之間的正式聯系，并展示了后者如何為許多設計用于學習前者的學習算法帶來統一視角，并為兩個社區創造研究機會。

張量是矩陣的多維推廣，廣泛用于表示高維數據（Kroonenberg, 2007）。張量分解是用于以簡單操作作用于低維張量的形式緊湊表示張量的數學對象（Kolda, 2006）。它們在機器學習和人工智能中得到了廣泛應用，例如在計算機視覺（Vasilescu & Terzopoulos, 2002; Savas & Eldén, 2007; Panagakis et al., 2021）、圖分析（Kolda et al., 2005）、計算神經科學（Vos et al., 2007; Tresp et al., 2021）、神經符號AI（Nickel et al., 2015; Balazevic et al., 2019; Gema et al., 2023; Loconte et al., 2023）、語言建模（Ma et al., 2019; Hu et al., 2022; Xu et al., 2023）以及作為編碼概率分布的方式（Jaini et al., 2018b; Novikov et al., 2021; Amiridi et al., 2022; Hood & Schein, 2024）。雖然通常以淺層分解的形式定義，但張量分解也可以表示為分解的層次結構（Grasedyck, 2010），有時在張量網絡的圖形形式中表示（Orús, 2013; Glasser et al., 2019）。

另一方面，電路表示（Darwiche & Marquis, 2002; Choi et al., 2020; Vergari et al., 2021）是在邏輯推理和概率建模背景下引入的結構化計算圖（Darwiche, 2003; Poon & Domingos, 2011; Kisa et al., 2014）。特別是概率電路（PCs）（Vergari et al., 2019b; Choi et al., 2020）是編碼可處理概率分布的電路。它們支持許多需要精確和高效推理例程的應用，例如無損壓縮（Liu et al., 2022）、生物醫學生成建模（Dang et al., 2022b）、可靠的神經符號AI（Ahmed et al., 2022; Loconte et al., 2023）和受限文本生成（Zhang et al., 2023）。過去已經提出了許多從數據中學習PCs的算法（參見例如Sidheekh & Natarajan (2024)的綜述），其中一種范式是構建包含數百萬甚至數十億參數的過參數化電路，并通過梯度上升、期望最大化（Peharz et al., 2016; 2020c）或正則化變體（Dang et al., 2022a）訓練這些參數。

分層張量分解和PCs都被引入作為概率圖模型的替代表示（Song et al., 2013; Robeva & Seigal, 2017; Glasser et al., 2020; Bonnevie & Schmidt, 2021），并且在某些工作中已經暗示了某些電路和分解之間的聯系（Jaini et al., 2018b; Glasser et al., 2019）。然而，它們主要在應用方式上有所不同：張量分解通常用于存在可近似真實張量或可以制定維度縮減問題（即張量草圖）的任務中，而PCs通常以生成模型訓練的精神從數據中學習。然而，與張量分解類似，現代PC表示是過參數化的，通常編碼為張量集合，以利用并行性和現代深度學習框架（Vergari et al., 2019a; Peharz et al., 2020c; Mari et al., 2023）。這就引出了一個問題：電路和張量分解之間是否存在任何正式和系統的聯系？我們的答案是肯定的，我們展示了電路可以被視為廣義稀疏分層張量分解，其中其參數編碼了分解本身的低維張量。或者，分層張量分解是具有特定張量化架構的深度電路的一個特例。對于PCs，這意味著將表示為非負張量的概率分布分解（Cichocki & Phan, 2009）。同時，經典張量分解可以精確編碼為（淺層）電路。通過肯定張量分解和電路的對偶性，我們系統化了文獻中的先前結果，打開了表示和學習電路的新視角，并提出了構建新和擴展現有（概率）分解的可能方法。

具體來說，在本文中，我們將首先推導出一種緊湊的方式來表示幾種張量化電路架構，并使用“樂高積木”方法將它們表示為計算圖，該方法堆疊（局部）密集張量分解，同時保留電路所需的結構特性以確保可處理性。這使我們能夠以即插即用的方式使用新穎的“積木”。然后，我們將迄今為止在文獻中提出的用于學習PCs的許多不同算法統一起來（Peharz et al., 2020c;a; Liu & Van den Broeck, 2021b），這些算法來自不同的視角，并產生被視為不同模型的電路。特別是，我們展示了它們的差異歸結為它們的張量參數的分解和句法變換，因為它們可以在基于Tucker張量分解（Tucker, 1966）及其特化（Kolda & Bader, 2009）的相同廣義（分層）分解框架下理解。因此，我們認為文獻中經常報告的不同性能實際上是不同超參數和學習方法的結果，而不是不同的歸納偏置（Liu et al., 2023b）。

此外，在建立這種聯系之后，我們利用張量分解進一步壓縮已經以張量格式表示的現代PC架構的參數。通過這樣做，我們引入了比以前更參數高效的PCs，并展示了為特定設置找到最佳電路架構的問題遠未解決。最后，我們強調了這種與電路的聯系如何為張量分解社區帶來有趣的研究機會（在整篇論文中以方框突出顯示）：從學習從數據分解張量，到將張量分解解釋為潛在變量概率模型，再到通過指定背景知識誘導稀疏性。

貢獻。i) 我們將流行的張量分解方法及其分層表述推廣到電路語言中（第2節）。

ii) 我們將PCs與非負張量分解聯系起來，并強調后者如何被解釋為潛在變量模型，因此它們可以用作生成模型和神經符號AI（第3節）。

iii) 在我們的框架內，我們將構建和學習現代過參數化架構的許多選項抽象出來，以達到一個通用的算法流程（第4節），用于表示和學習作為張量化電路的分層張量分解。

iv) 這使我們能夠通過利用張量分解分析現有不同電路參數化之間的關系，同時提出保留部分表達能力的更參數高效的建模選擇（第5節）。

v) 我們在廣泛的分布估計任務中評估了我們框架中的幾種算法選擇，突出了時間復雜度和空間復雜性以及結果性能的主要權衡（第7節）。

2 從張量分解到電路

2.1 淺層張量分解是淺層電路

請注意，括號內顏色編碼的塊對應于電路中輸入函數的輸出（圖2），而向量外積（b）實現了c中的乘積單元，同時與w的點積在最終的求和單元中編碼。我們邀請讀者通過這個例子并嘗試恢復張量中的其他條目，直到他們對將張量分解轉換為我們的電路格式感到滿意為止。最后，我們注意到分解的多線性秩現在轉化為電路表示中的輸入單元數量。稍后，對于轉換為深度電路的分層分解（第2.2節），秩也將轉化為位于不同深度的單元數量。

將張量分解表示為這種類型的計算圖將提供許多擴展前一類模型的機會，在這種情況下，我們將在整篇論文中以方框突出顯示它們。同時，我們可以更好地理解為什么這些分解已經支持某些感興趣量的可處理計算，例如積分、信息論度量或最大化（Vergari et al., 2021）。這可以在電路的框架中以系統的方式完成，將這些計算映射到計算圖的某些結構特性，精確地定義可處理性的充分（有時是必要）條件。我們首先定義平滑性和可分解性，這是電路的兩個結構特性，允許對指數級多的變量賦值進行可處理的求和計算，而這對于其他模型通常是難以計算的。

2.2 分層張量分解是深度電路

張量分解可以堆疊在一起形成深度或分層分解，這可以比其淺層具體化更節省空間（即秩更低）。例如，Grasedyck (2010) 提出了分層Tucker，它根據張量維度的固定分層分區堆疊許多低秩Tucker分解。Cohen et al. (2015) 表明，在大多數情況下，等效或甚至近似的淺層分解將需要相對于維度數量的指數級秩。類似的理論結果也適用于電路，即深度電路可以比淺層電路小指數級，其中電路的大小是單元連接的數量（Delalleau & Bengio, 2011; Martens & Medabalimi, 2014; Jaini et al., 2018b）。

在本節中，我們首先介紹分層Tucker分解，展示它是深度電路的一個實例，然后利用這種聯系來描述現代張量化電路表示（第4節）。為此，我們從電路文獻中借用了一個工具：電路范圍的分層分區（Vergari et al., 2021），即區域圖（RG）（Dennis & Ventura, 2012）。RG是一個二分圖，其節點要么是變量集，即要分解的張量的維度，要么指示如何對這些集合進行分區。

附錄A.2展示了構造，圖3a也展示了基于圖4所示RG的分層Tucker分解。以同樣的方式可以將任何張量分解擴展為分層的，可以將這種構造表示為電路。然而，在電路文獻中，我們發現許多架構不僅限于樹狀RG，也不限于具有單變量輸入區域的RG。

請注意，從上述定義的RG實例化張量分解保留了可分解性，并且文獻中從RG構建的電路通常也是平滑的（定義3）。分層Tucker及其變體也是平滑和可分解的，因此支持許多（概率）推理任務的可處理計算（第3節）。這些遵循具有單變量葉子的樹狀RG的分層分解（及其對應的深度電路）滿足一個額外的結構特性，稱為結構可分解性。結構可分解性使得對于平滑性和可分解性不足的更難操作的可處理計算成為可能。例如，在張量網絡的圖形語言中形式化的特定張量分解的平方，在物理學中稱為玻恩規則（Feynman, 1987; Glasser et al., 2019）（另見第2.4節）。我們在下面定義結構可分解性。

定義6（結構可分解性（Pipatsrisawat & Darwiche, 2008））。如果電路滿足以下條件，則它是結構可分解的：(1) 它是平滑和可分解的，(2) 任何具有相同范圍的乘積單元n, m在其輸入單元中以相同方式分解其范圍。

我們可以很容易地檢查分層Tucker是否產生結構可分解電路，因為它通過基于樹狀RG堆疊Tucker分解（由可分解電路計算）獲得，這反過來使所有乘積單元以相同方式分解。我們強調，引出能夠解釋許多不同感興趣量的可處理計算的少數結構特性，可以幫助節省針對特定分層分解（重新）發現和（重新）設計算法的努力。

2.3 以張量化形式表示電路

將（分層）張量分解表示為（深度）電路突顯了電路單元如何可以按類型和范圍自然地分組到層中，如圖2所示。這一視角提出了一個新的機會：將某些電路結構定義和表示為張量化計算圖。雖然文獻中的電路是根據標量計算單元、求和、乘積和輸入以及單個連接（定義2）定義的，但如今許多成功的電路實現已經將單元分組到張量中（Vergari et al., 2019a; Peharz et al., 2020c;a; Liu & Van den Broeck, 2021b; Loconte et al., 2024a），目的是通過使用GPU提供的加速來加快計算速度。遵循這些思想，我們現在提供一個通用的張量化電路定義，它提供了一種模塊化的方式來構建過參數化電路架構。這將使我們能夠設計一個單一的學習流程，涵蓋許多現有架構（第4節），并建議通過混合和重用小的“積木”來創建新架構的方法。

作為一個關于這個定義如何幫助從電路架構細節中抽象出來的第一個例子，參見圖3。在那里，求和層和克羅內克積層用于堆疊兩個Tucker張量分解以表示分層的張量分解。我們在第4節提供了一種系統的方法來堆疊不同的層并以這種方式構建深度電路。我們現在可以通過定義每一層的范圍，輕松地將定義3中單元級的結構特性擴展到這種層級表示。

請注意，通過假設每一層由共享相同范圍的單元組成，并使用定義7中定義的三層，我們獲得的張量化電路在設計上就是平滑和可分解的。此外，如果深度電路的RG是一棵樹，那么張量化電路也將是結構可分解的（定義6）。可以快速從圖3b中分層Tucker作為張量化電路的圖形表示中讀出這些特性。接下來，我們使用這種分層抽象來連接流行的張量網絡，并展示它們如何自然地編碼為深度電路。

2.4 張量網絡作為深度電路

張量網絡（TNs）通常是物理和量子計算等領域表示分層張量分解的首選方式（Markov & Shi, 2008; Schollwoeck, 2010）。TNs帶有圖形化語言——Penrose符號——以緊湊的圖形形式編碼張量點積（也稱為張量收縮）。有關綜述，請參閱Orús (2013)。也許最受歡迎的TN分解是矩陣乘積態（MPS）（Pérez-García等人，2007），也稱為張量列車分解（TT）（Oseledets, 2011; Glasser等人，2019; Novikov等人，2021）。例如，給定一個張量，其秩-R MPS/TT分解在逐元素符號中定義為

3 從非負分解到概率建模的電路

在機器學習中，人們非常關注用于可處理概率建模的電路表示，即用于建模支持可處理推理的概率分布。為此目的構建的電路通常稱為概率電路（PCs）（Vergari et al., 2019b; Choi et al., 2020）。在本節中，我們將非負張量分解與PCs聯系起來，展示了張量分解社區在概率機器學習全景中的多個研究機會。

首先，我們將非負（分層）張量分解與（深度）PCs的離散潛在變量解釋聯系起來，展示了利用這種解釋進行線性時間概率推理的可用算法示例（不僅限于邊際，如前一節所述，還包括采樣）。其次，我們展示了PCs的豐富文獻提供了多種緊湊參數化技術，可以產生非線性分解。同時，我們利用非負張量文獻中的優化技巧來學習PCs。最后，我們與無限維張量分解的文獻聯系起來，展示了它們與編碼概率密度函數的PCs以及配備無限維求和單元的PCs之間的關系。我們首先描述如何將有限離散隨機變量上的概率分布表示為張量分解。

3.1 非負張量分解作為生成模型

作為非負分解（如非負分層Tucker）是平滑的且（結構化）可分解的概率電路（PC）（定義 3 和 6），它們繼承了PC進行可處理推理和生成新數據點（即它們定義的變量的某些配置）的能力。據我們所知，這種將張量分解視為生成模型的處理到目前為止還沒有被注意到。我們在下文中討論這一點，展示如何為這些表示設計（更快的）抽樣算法。

3.2 如何參數化概率張量分解？

例如，我們可以通過指數化來強制每個單個求和單元參數為非負數。

在本文中，我們介紹了第三種方法，一種從基于梯度的非負張量分解優化文獻中借鑒的更簡單的實現技巧（Cichocki et al., 2007）：在每次優化步驟后將所有求和單元的參數投影到正交空間，即

其中?是一個接近零的小閾值，max是逐元素應用的。每次重新參數化都可以產生不同的損失景觀，并在優化過程中導致不同的解決方案。在我們的實驗（第7節）中，我們發現這種第三種重新參數化在學習單調PCs時最為有效。

當涉及到單調PCs中的輸入單元時，它們需要建模有效的分布。常見的參數化可以包括簡單的PMFs（或密度，參見第3.4節），如伯努利或分類分布，甚至其他概率模型，只要它們可以被可處理地邊緣化。這產生了一組超出通常在張量分解中使用的簡單索引到矩陣條目映射的參數化可能性（命題1和圖2）。

3.3 可靠的神經-符號集成

也稱為加權模型計數WMC（Chavira & Darwiche, 2008; van Krieken et al., 2024），這是在結合邏輯和概率推理時需要計算的關鍵量（Darwiche, 2009; Zeng et al., 2020）。據我們所知，這種可能的整合在張量分解社區的雷達之外。

3.4 無限維概率張量和連續分解

到目前為止，我們討論了表示具有有限維度的張量（即每個維度中的條目數量是有限的）的電路分解，即這些電路定義在一組離散變量上，每個變量具有有限數量的狀態。在本節中，我們關注張量的分解，這些張量可以具有具有無限（且可能是不可數的）條目數量的維度或準張量（Townsend & Trefethen, 2015）。類似于（分層）張量分解和電路之間的對稱性（第2節），我們展示了準張量可以表示為定義在至少一個具有無限（且可能是不可數的）域的變量上的電路。此外，通過連接到最近配備積分單元的電路類，我們指出了關于無限秩（分層）張量分解參數化的機會，即其秩不一定有限的分解。我們將這些想法建立在概率密度函數（PDF）建模的問題上。

同樣，可以檢索此類連續張量分解的分層版本，并應用于概率建模（Gala et al., 2024b）。在等式(15)中的積分難以計算的情況下，可以應用求積規則來近似它。詳見Gala et al. (2024a)。

在下一節中，我們將展示一個通用的流程，可以用來構建有限維和無限維的分層概率張量分解作為深度張量化概率電路（定義 7）。

4 如何構建和擴展電路：張量化視角

現在我們已經具備了開始利用（分層）張量分解和（深度）電路之間聯系的所有必要背景。特別是，在本節中，我們將展示如何理解和統一許多——表面上不同的——構建電路（和其他分解）的方法，在一個單一的流程中利用張量分解作為模塊化抽象。通過這樣做，我們可以“解開”構建和有效學習過參數化電路的關鍵要素，即具有大量參數的電路（表1）。

圖8總結了我們的流程：i) 首先，構建一個RG結構以強制執行必要的結構特性（第4.1節），然后，ii) 通過引入單元并將它們分組到層中來填充此模板（第4.2節），遵循許多可能的張量分解抽象（第4.3節），可選地，iii) 這些層可以“折疊”，即堆疊在一起以利用GPU并行性（第4.4節）。最后，可以通過梯度下降或期望最大化來優化電路參數（Peharz et al., 2016; Zhao et al., 2016）。

4.1 構建和學習區域圖

我們流程的第一步是構建一個RG（定義4）。它根據輸入變量的分層分區指定我們構建深度電路架構的方式。特別是，通過滿足關鍵結構特性（如平滑性和可分解性，如果RG是樹且具有單變量葉子，則為結構可分解性，參見第2.2節）的RG構建的PC，反過來保證了許多感興趣查詢的可處理推理（第2節）。一些論文中明確使用RG來構建PC（Peharz et al., 2020c;a），但正如我們接下來展示的，它們可以隱含在許多其他PC和張量分解架構中。我們還介紹了一種為圖像快速構建RG的新方法，這些圖像是數據集無關的，但利用了像素的結構。

也就是說，根區域X通過隨機將變量分割成大約均勻的子集來遞歸分區，直到無法進一步分區為止。這種方法，我們標記為RND，已被引入以構建隨機化和張量化的和積網絡（RAT-SPNs）（Peharz et al., 2020c）。Di Mauro et al. (2017; 2021) 描述了一種類似的方法，不同之處在于在參數化電路時也考慮了數據的一些隨機選擇的子集，從而將RG的構建與電路參數化糾纏在一起。

Poon-Domingos 構造（PD）。可以設計其他針對特定數據模態的RG算法，但仍然是數據集無關的。在圖像的情況下，變量與像素值相關聯，Poon & Domingos (2011) 提出通過遞歸執行水平和垂直切割來分割它們，以形成補丁的深度層次結構。然而，這種方法的主要缺點（標記為PD）是它通常會產生非常深的電路架構，難以優化（第7節），因為它考慮了將圖像遞歸分割成補丁的所有可能方式，補丁數量隨圖像大小快速增長。PD RG在電路文獻中被廣泛使用，例如用于EiNets等架構（Peharz et al., 2020a）。

圖像數據的新RG：四邊形圖（QG）和樹（QT）。我們希望設計數據集無關但仍意識到像素結構的RG，如PD，同時不會陷入相同的優化問題。因此，我們提出了一種更簡單的方法來構建圖像定制的RG，這些RG可以實現更好的性能，即使與從數據中學習的RG相比也是如此（參見第7節）。附錄中的算法D.1詳細說明了我們的構造。與PD類似，它通過遞歸分割大約相同大小的圖像補丁來構建RG，但與PD不同的是，它只將它們分成四個部分（一個垂直和一個水平切割）共享新創建的補丁。我們稱這種RG為四邊形圖（QG）。圖9顯示了一個3x3圖像的QG RG示例。

或者，可以通過水平和垂直分割補丁來獲得樹RG，但不共享補丁。我們稱這種樹RG為四邊形樹（QT）。由于這種RG的區域與圖像補丁相關聯，我們可以選擇以不同的方式對它們進行分區。特別是，我們將表示為QT-2的QT的區域分為兩部分（補丁的底部和頂部部分），并將表示為QT-4的QT的區域分為四部分（遵循象限劃分分區）。通過QT-2，我們檢索了先前工作中用于圖像數據的張量分解定制（Cheng et al., 2019）。

從數據中學習RG。到目前為止討論的方法不依賴于訓練數據。為了在構建RG時利用數據，可以測試區域節點中特征子集的統計獨立性。這是開創性的LearnSPN算法（Gens & Domingos, 2013）中使用的方法，后來在許多其他工作中得到了擴展（Molina等人，2018；Di Mauro等人，2019）。所有這些變體從未提及RG，但通過執行這些統計測試并通過聚類引入與不同“數據塊”相關聯的區域，隱式地構建了一個。

或者，可以根據某些啟發式規則對數據進行區域劃分，從而使得區域節點被共享（Jaini等人，2018a）。Chow-Liu算法用于學習更好地近似數據可能性的樹形概率圖模型（PGM）（Chow & Liu, 1968b），也是基于同樣的想法。Chow-Liu算法（CL）也可以用來隱式構建RG，如許多結構學習變體中所做的那樣（Vergari等人，2015；Rahman等人，2014；Choi等人，2011）。一種更近期的方法利用了這一想法，并且通常能夠達到最先進的性能，首先學習Chow-Liu樹，然后將其視為一個潛在的樹模型（Choi等人，2011），最后將其編譯成PC（Liu & Van den Broeck, 2021b）。這種隱藏的Chow-Liu樹（HCLT）的構建完全遵循我們流程中的步驟，一旦將RG的作用從其余部分中分離出來。

迄今為止提到的其他PC和張量分解架構的構建（即，RAT-SPNs、EiNets、MPSs、BMs等）也遵循相同的模式，并且可以輕松地歸入我們的流程（表1）。它們不僅在構建的RG方面有所不同，而且在所選擇的求和和乘積層的種類上也有所不同。在下一節中，我們將提供一個通用算法，它根據給定的RG和編碼張量分解的求和與乘積層的選擇，構建一個張量化的電路架構。

4.2 過參數化與張量化電路

給定一個RG，構建電路的最簡單方法是每個葉區域關聯一個單一的輸入分布單元，每個內部區域關聯一個單一的求和單元，每個分區關聯一個單一的乘積單元，然后根據RG結構連接它們。這將提供一個平滑且（結構）可分解的稀疏連接電路，這實際上是前一節中討論的許多結構學習算法隱含使用的策略（Gens & Domingos, 2013; Vergari et al., 2015; Molina et al., 2018）。我們可以將這種策略適應“深度學習配方”，并輸出一個局部密集連接的過參數化電路。通過過參數化，我們指的是用相同范圍的多個求和、乘積和輸入單元“填充”RG的過程。生成的張量化計算圖（定義7）具有更多的可學習參數，并且適合在GPU上并行化，因為我們可以將共享相同范圍的計算單元向量化以形成密集層。算法1詳細說明了過參數化和張量化過程。該算法輸入包括：一個RG R，輸入函數類型F（例如，高斯分布），以及控制電路表達能力的求和單元數量K，或等效地，分解的秩。6 此外，我們還可以自定義輸入層的選擇以及如何堆疊求和和乘積層，從而以不同的效率和表達能力構建多種電路。

4.3 將求和和乘積層抽象為模塊

除了輸入層之外，我們在定義7中介紹了張量化電路的其他原子“樂高積木”：求和層、哈達瑪和克羅內克積層。在下面，我們將使用這些積木來創建復合層，這些復合層將作為進一步的抽象，可以無縫插入算法1中。這些復合層包括：Tucker（圖10）、CP（圖14）和CPJ（圖15）層。每個層都編碼一個局部分解，并以不同的方式堆疊和連接內部求和和乘積單元，以增加表達能力或效率。

請注意，鑒于我們對張量化層的語義，通過在RG上應用算法1堆疊這些復合抽象，將始終輸出一個平滑且（結構）可分解的張量化電路（定義8）。

4.4 折疊以進一步加速學習和推理

我們提出的流程的最后一步（圖8）是可選的，包括將共享相同功能形式的層堆疊在一起以增加GPU并行性。我們將此步驟命名為折疊。請注意，折疊只是電路的句法變換，即它不改變編碼的函數，因此保留其表達能力。然而，這種簡單的句法“重寫”可以顯著影響學習和推理性能。事實上，折疊是EiNets（Peharz et al., 2020a）相對于非折疊電路架構（如RAT-SPNs（Peharz et al., 2020c））引入的額外加速的核心要素，這些架構與EiNets共享其他架構細節，例如使用Tucker層（見表1）。

因此，通常在將RAT-SPNs和EiNets視為兩種不同的PC模型類時報告的性能差異（參見例如Liu et al. (2023a)）必須依賴于其他因素，例如RG的選擇或其他用于學習這些模型的超參數的差異，例如所選的優化器。通過在我們的流程中解開這些方面，我們可以設計實驗，真正突出哪些因素負責提高性能（參見第7節）。

折疊層。為了檢索Tucker層的折疊表示（等式(Tucker-layer)），我們需要將參數矩陣沿新引入的維度堆疊，我們稱之為折疊維度。

如何選擇要折疊的層？還需要決定如何選擇要折疊在一起的層。

最簡單的方法是自頂向下遍歷張量化電路（即，從輸出向輸入），并折疊在計算圖中位于相同深度的層。然而，請注意，我們也可以折疊不同深度的層。例如，如果所有輸入層對所有變量編碼相同的輸入函數，那么可以一起折疊所有輸入層。這是EiNets中采用的方法（Peharz等人，2020a），也是我們將在所有實驗和基準測試中使用的方法（見第 7 節）。然而，請注意，這并不被視為折疊層的最優方式，針對特定架構選擇不同的層折疊方式可能會帶來額外的速度提升和內存節省。雖然我們沒有調查除了上面提到的之外的不同折疊層的方法，但在我們的提議流程中將折疊和過度參數化步驟（第 4.2 節）分離開來，將促進未來的工作依賴于廣泛的關于并行化通用計算圖的文獻（Shah等人，2023）。

5 通過張量分解壓縮電路和共享參數

在本節中，我們再次利用張量分解的文獻來改進電路架構的設計和學習。我們首先觀察到，在我們的流程中，電路層的參數存儲在大張量中（參見例如等式(Tucker-layer)和(Tucker-folded)），原則上可以再次分解。由于分解是電路（命題1），最終我們獲得了電路架構和層的幾個變體，其中一些是新的，提供了速度和準確性之間的有趣權衡（第5.2節），而其他一些則隱含地用于現有電路和張量分解的構建中（表1）。同樣，我們從Tucker層開始，目的是使用它們壓縮深度電路，即通過使用更少的參數來近似它。

5.1壓縮打褶層

5.2 通過張量分解共享參數

現在我們關注張量化PC中跨層共享參數的問題。同樣，我們將利用張量分解來完成這項任務。考慮根據我們的流程（第4.2節）從RG構建的張量化PC。可以合理地假設位于RG相同深度的層可以在其參數張量中存儲相似的結構。例如，兩個具有相同大小相鄰像素補丁范圍的不同層可能對其各自的輸入應用相似的變換，因為我們假設這兩個像素補丁的分布非常相似。如果RG是一個完全平衡的二叉樹，折疊生成的電路意味著折疊計算圖中位于相同深度的層，即在參數空間中可能共享相同結構的層。這促使我們將參數共享實現為跨折疊層的分解。

6 其他相關工作

在前幾節中，我們調查并連接了電路表示和張量分解的文獻，因此我們已經回顧了兩個社區的幾個相關工作。現在，我們討論過去部分嘗試建立這種聯系的工作，通過嘗試連接到概率圖模型。

張量網絡和PGMs。TN（Orús, 2013）廣泛用于物理學和量子力學中的多體系統建模（Schollwoeck, 2010），并已用于在經典硬件上模擬量子計算（Markov & Shi, 2008）。最近，它們被應用于機器學習應用（Stoudenmire & Schwab, 2016; Han et al., 2018; Efthymiou et al., 2019; Bonnevie & Schmidt, 2021）。由于它們本質上是對離散變量的概率圖模型的另一種形式（Koller & Friedman, 2009），人們開始在這兩種形式之間建立聯系。例如，Bonnevie & Schmidt (2021) 將非負MPS/TTs與PGMs連接起來，并提供概率推理的例程。同樣，Glasser et al. (2020) 探索了相同的聯系，但不是將TN繪制為PGMs，而是將它們繪制為因子圖（Kschischang et al., 2001）。

有趣的是，這些工作并不知道非負分解的潛在變量解釋（第3.1節），因為它們錯過了通過電路的聯系。出于同樣的原因，它們僅限于自回歸采樣（機會3）。據我們所知，這種潛在變量視角僅在最近由Ghalamkari et al. (2024) 的并發工作中（重新）發現，他們提出了經典的期望最大化（EM）算法來學習它們。EM是通過最大似然學習電路參數的成熟方法（Peharz et al., 2016; 2020a）。

相反，通過將非負張量分解表示為單調PCs，我們輕松解鎖了執行復雜概率推理所需的已開發理論和算法，并可能應用于無損壓縮（Liu et al., 2022）、具有正確性保證的神經符號AI（Ahmed et al., 2022）和受限文本生成（Zhang et al., 2023）。最后，關于這些分解的簡潔性或表達效率的結果（Glasser et al., 2019）最近被用于證明電路的下界（Loconte et al., 2024a;b）。

概率電路和PGMs。PCs的現代表述首次在（Vergari et al., 2019b）中引入，作為幾個現有可處理概率模型（TPMs）的統一框架，包括算術電路（Darwiche, 2001）、概率決策圖（Jaeger, 2004）、與或圖（Marinescu & Dechter, 2009）、割集網絡（Rahman et al., 2014）、和積網絡（Poon & Domingos, 2011）等（Choi et al., 2020）。PCs的目的是從上述TPMs的不同語法和模型形式中抽象出來，專注于每個TPMs中實現可處理推理的結構特性。到目前為止，非負張量分解和張量網絡在這項工作中被忽視了。過去已經設計了幾種將離散PGMs編譯為PCs（或上述形式之一）的方法（Oztok & Darwiche, 2017; Shen et al., 2016; Choi et al., 2013）。這些編譯技術產生了稀疏確定性電路，直到最近，PCs才開始首先在代碼中表示（Peharz et al., 2020c;a; Liu & Van den Broeck, 2021b），然后正式表示（Loconte et al., 2024a）為張量化架構。也許這種缺乏張量化編譯目標的情況掩蓋了PCs和矩陣及張量分解之間的聯系。我們所知的最近的聯系可以在Jaini et al. (2018b)中找到：他們將和積網絡與分層混合模型和HMMs連接起來，并暗示了與張量混合模型（Sharir et al., 2017）的聯系，這是分層Tucker（定義5）的一個變體。Loconte et al. (2024a) 正式將MPSs和BMs簡化為電路，并開始與張量分解表達性文獻建立聯系（Glasser et al., 2019）。

矩陣分解和電路復雜性結果。找到矩陣分解的秩下界可以作為證明滿足特定結構特性的電路大小下界的代理（de Colnet & Mengel, 2021）。證明一類電路的指數（相對于變量數量）大小下界顯示了它們在多項式時間和參數數量下可以計算的函數限制，從而使我們能夠根據表達能力精確區分電路類（Valiant, 1979; Martens & Medabalimi, 2014）。最近，下界非負秩（Gillis, 2020）和平方根秩（Fawzi et al., 2014; Lee & Wei, 2014）已被用于繪制具有負實值和復值參數的PCs類在分布估計中的表達性層次（Loconte et al., 2024a;b）。由于電路概括了許多張量網絡分解（參見第2.4節），顯示一類電路的大小下界可以用于顯示張量網絡的大小下界，而不管其結構如何，例如Loconte et al. (2024b) 在推廣通過平方MPS/TT獲得的實Born機器的已知秩下界時所展示的那樣（Glasser et al., 2019）。

7 實證評估：使用哪種RG和層？

將現代PC架構（以及張量分解）解構到我們的流程（圖8）中，使我們能夠通過簡單的混合與匹配方法（表1）創建新的張量化架構。同時，它幫助我們從表達能力、推理速度和優化難易度的角度理解不同模型類之間的真正差異。我們現在可以輕松解開關鍵要素，例如RG和現代電路架構中復合層的角色選擇，并確定哪個是性能提升的原因。例如，HCLTs在最近的基準測試中被認為是表現最好的電路模型架構之一（Liu et al., 2022; 2023a），但到目前為止，為什么它們優于其他架構（如RAT-SPNs和EiNets）尚不清楚。在我們的框架內，我們可以通過回答更精確的問題來嘗試回答這個問題：是它們從數據中學習的RG的效果（第4.1節）？還是它們復合和積層參數化的使用（第5.1節）？或者是其他超參數選擇的原因？（劇透：是CP層的使用）。

具體來說，在本節中，我們感興趣的是通過嚴格的實證調查回答以下三個研究問題。RQ1）我們目前可以構建的許多張量化架構在測試和訓練時需要哪些計算資源（時間和GPU內存）？RQ2）RG和復合和積層的選擇對作為分布估計器訓練的張量化電路的性能有何影響？RQ3）如果我們將這些Tucker層分解為如圖13a ? 圖13b所示的CP層，我們能否保留（大部分）預訓練張量化PC的性能？請注意，我們不是在問折疊的影響（第4.4節），因為我們已經知道答案：折疊對于大規模張量化架構是必不可少的。因此，在整個實驗中，我們使用折疊的張量化電路。我們強調，我們實驗的目的是理解張量化電路架構要素的作用，而不是在分布估計中達到最先進的結果。所有實驗都在具有48GB內存的單個NVIDIA RTX A6000 GPU上運行。

新的電路命名法。我們注意到，表1中的HCLT、EiNets、RAT-SPNs和其他所有縮寫并不表示不同的模型類，而只是不同的架構。它們是同一模型類的實例：平滑且（結構）可分解的電路。在下面，我們將張量化架構表示為[RG]-[和積層]，可能后跟K，即在算法1中用于過參數化層的單元數量。在這種命名法下，當RAT-SPNs和EiNets都使用隨機RG構建時，它們都將被編碼為RND-Tucker。當它們使用Poon&Domingos RG構建時，它們將被稱為PD-Tucker，而HCLTs將變為CL-CP。

任務與數據集。我們將通過在圖像數據集上進行分布估計來評估我們的架構。我們使用Mnist家族，其中包括6個灰度28x28圖像數據集——Mnist（LeCun et al., 2010）、FashionMnist（Xiao et al., 2017）和EMNIST及其4個分割（Cohen et al., 2017）——以及下采樣為64x64的CelebA數據集（Liu et al., 2015），我們以兩種版本探索：一種是RGB像素，另一種是經過無損YCoCg色彩編碼（Malvar & Sullivan, 2003）預處理的像素，最近的成果表明這種變換可以大大降低bpds。9

參數優化。我們訓練電路來估計假設生成圖像的概率分布，將每個像素視為隨機變量。因此，電路中的輸入單元表示具有256個值的分類分布。對于RGB圖像，我們為每個像素關聯三個分類分布單元（每個顏色通道一個）。我們通過隨機梯度上升進行最大似然估計，即希望最大化以下目標

RQ1) 不同張量化架構的時間和空間基準測試。在這些實驗中，我們考慮了以下RGs：PD，通常用于RAT-SPNs和EiNets等架構，以及我們在第 4.1 節中介紹的兩種新的輕量級和數據不可知RGs，QTs 11 和 QGs。我們不考慮RND，因為它通常只是一個平衡的二叉樹（Peharz等人，2020c），因此會產生與QT相同的時間和內存性能。出于同樣的原因，我們不考慮CL，因為它們是樹形RGs，在生根后最終會變得幾乎是平衡的。對于層，我們考慮Tucker（方程（Tucker層）），CP（方程（CP層）），CPS（方程（CPS層））和CPXS（第 5.2 節）。

在圖 19 中，我們報告了在Mnist、FashionMnist和CelebA上的平均測試集bpd。在比較架構與RG選擇時，一個明顯的模式出現了：基于QT和QG的架構勝過了基于PD的架構，并且也能夠擴展到像CelebA這樣的更大數據集。平均來說，表現最好的架構是由QG構建的。這是預期的，因為這樣的RGs，與QTs不同，允許同一個區域有不同的劃分（因此需要使用混合層，如方程（混合層）中討論的）。盡管PD區域圖與QGs一樣是DAG形狀的，但它們提供的張量化架構表現不佳，這表明更大的模型，雖然具有更強的表達能力，但更難訓練，這是Liu等人（2023a）也注意到的行為。這在觀察基于PD的架構在FashionMnist上的趨勢時尤為明顯。

在表2中，我們將我們表現最好的架構與其他電路文獻之外的最先進概率模型進行了比較。我們的架構提供了接近最先進的結果，優于一些基于VAE和流的模型。當與從數據中學習的RG進行比較時，如HCLT的情況，我們注意到我們更簡單、數據無關的替代方案，QTs和QGs，表現同樣好或更好。使用它們而不是CL RG可以節省學習相應Chow-Liu樹所需的二次成本（Dang et al., 2021）。

關于求積-乘積層類型的選擇，Tucker層和CP層在PD上的表現非常相似。我們猜測，這可能是因為PD通常更難訓練，對于其他RGs，趨勢會有所變化。實際上，使用QT和QG時，我們觀察到Tucker在K的最小值時提供了最佳的bpd。然而，將其擴展到更大的K是不切實際的。CP及其變體不僅擴展性更好（見RQ1和圖18），而且能夠為更大的K提供最佳的bpd。正如預期的那樣，CP始終優于CPS，因為它有更多的可學習參數。然而，如果必須在時間效率和準確性之間做出選擇，CPS可以是一個有用的替代方案。最后，我們在附錄E中報告了CPXS層和可學習混合層的結果，同時以表格形式展示了圖19中的結果。我們確認CPS和CPXS層在準確性上是等效的，并且在具有DAG形狀RGs的張量化PC中不必學習混合層參數，見第4.4節。所有這些結論也適用于更大的圖像數據集，如CelebA，無論是否使用無損YCoCg彩色編碼。

RQ3) 使用Tucker層壓縮電路。對于我們的最后一個研究問題，考慮這樣一個問題：當給定一個訓練有素的帶有Tucker層的電路時，我們希望使用CP層將其壓縮成更小的電路，使用我們在圖13a和圖13b中所示的壓縮管道。考慮到這一點，我們研究了性能的變化（如果有的話），與可調參數的數量有關。具體來說，對于給定電路中的每個折疊的Tucker層（Tucker-folded）（方程式（Tucker-folded）），我們通過交替最小二乘法（Shashua & Hazan, 2005）對每個張量片Wf:::進行非負（NN）CP分解。這種優化最終提供了一個形狀為F?3?R?K的張量W1，用于R等級的分解。

我們在圖20中概述了我們的調查結果。正如預期的那樣，通過NN-CP分解壓縮預訓練的Tucker層PC（藍色虛線）的參數，隨著近似的等級R的增加，會得到一個性能相似的模型，如圖20中紅色曲線的bpd趨勢所示。有趣的是，我們觀察到兩個區域圖之間存在一個關鍵區別。對于基于PD區域圖的張量化PC，即使是等級1的近似（即R “ 1），也只會導致相對較小的bpd損失，而對于由QG構建的PC則不是這種情況。我們推測，基于PD的PC的參數張量比基于QG的PC的參數張量具有更低的等級，并且非常深的PC學習低等級的參數矩陣。

接下來，我們研究是否可以將這些壓縮模型用作較小電路的有效初始化方案，我們進一步訓練（微調）這些電路以最大化訓練數據似然（等式(20)）。同樣，我們看到與使用的區域圖相比，趨勢有所不同，如圖20中綠色曲線所示的bpds。具體來說，對于基于PD的PCs，這種微調在最初的優化步驟中就導致了快速過擬合，導致測試數據上的bpds更高。相比之下，基于QG的PCs的微調導致模型始終匹配甚至優于原始基于Tucker的PCs（藍色虛線），即我們觀察到綠色曲線始終低于紅色曲線并打破藍色虛線。

作為額外的基線，我們使用這些壓縮模型的架構（圖13b），但從頭開始訓練它們：從其參數的隨機初始化開始。圖20表明，NN-CP初始化可能優于隨機初始化，因為它在使用QG RG時（黃色曲線在綠色曲線上方）導致性能更好的模型。當使用PD區域圖時，這種趨勢翻轉（黃色曲線在綠色曲線下方），再次表明這些模型的更多信息可能存儲在RG中，而不是電路的參數中。這反過來表明，雖然具有高度復雜RG但內部張量秩非常低的新分層分解是可能的，但它們可能更難有效學習。

8 結論

在本文中，我們奠定了連接兩個獨立發展但共享許多研究方向的ML社區的基礎：電路和張量分解。盡管它們的語法、通常的呈現方式以及常用的任務看起來不同，但這兩種形式在語義和潛在應用上顯著重疊。我們通過首先在第2節中建立流行張量分解到電路的正式化簡，在這兩個社區之間建立了橋梁。我們希望這可以推動研究如何設計越來越多可擴展的低秩參數化以進行概率推理。為此，我們強調了矩陣和張量分解社區利用我們建立的電路連接的

多個未來研究方向：