A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction

用于代數約束滿足的概率性神經符號層

https://arxiv.org/abs/2503.19466

摘要

在安全關鍵型應用中，保證在連續環境中的約束滿足至關重要。例如，一個自主智能體（如自動駕駛汽車）永遠不能撞上障礙物或駛出道路。神經網絡模型在處理這些約束時存在困難，尤其是當這些約束涉及復雜的代數關系時。為了解決這個問題，我們引入了一個可微分的概率層，能夠保證滿足連續變量上的非凸代數約束。

這個概率代數層（Probabilistic Algebraic Layer, PAL）可以無縫嵌入到任何神經網絡架構中，并可以通過最大似然進行訓練，而無需依賴近似方法。PAL 定義了一種在線性不等式的合取（and）與析取（or）之上的分布，其參數由多項式表示。這種建模方式使得我們可以通過符號積分實現高效且精確的歸一化操作，這一過程可以在不同數據點之間共享計算成本，并且可以輕松地在 GPU 上并行執行。我們在多個代數約束整合任務的基準測試中以及真實世界的軌跡數據上展示了 PAL 及其積分方案的效果。

1 引言

在安全關鍵型應用中，一個可靠的 AI 系統應當具備不確定性感知能力，并對其預測結果提供校準良好的概率輸出。同時，它應當對某些不可能的狀態明確地、一致地賦予零概率，如果這些狀態違反了系統必須遵守的約束條件的話。這些約束可以編碼先驗知識，例如一些明確的規則 [Marconato et al., 2023, 2024; Bortolotti et al., 2024]，這些知識對于系統的安全性及其用戶的安全部署至關重要。例如，它們可以表示自動駕駛汽車應避免碰撞障礙物或駛出道路 [Xu et al., 2020; Giunchiglia et al., 2023]。

概率神經符號（NeSy）方法 [Garcez et al., 2019, 2022; De Raedt et al., 2021] 在構建可信 AI 方面的承諾在于，將對這些高層約束的符號推理能力整合進神經網絡預測模型中。最簡單的方式是在訓練過程中通過損失函數中的懲罰項來鼓勵模型滿足這些約束 [Xu et al., 2018; Fischer et al., 2019; De Smet et al., 2023a]。然而，這種方法在測試階段可能導致災難性后果，因為它無法保證所有違反約束的配置都被賦予精確為零的概率 ：即使一個約束被違反的概率只有 0.001%，在如自動駕駛這樣的安全關鍵型應用中也可能被視為有害。

一些近期研究通過設計出能夠從結構上保證約束滿足 的模型架構來克服這一問題 [Manhaeve et al., 2018; Giunchiglia 和 Lukasiewicz, 2020; Ahmed et al., 2022a; Hoernle et al., 2022]。遺憾的是，這些方法大多僅適用于布爾變量或離散變量 [De Smet 和 Dos Martires, 2024]，將其擴展到連續變量是非常困難的。這是因為處理連續變量上的約束帶來了獨特的挑戰：

首先，確保在約束范圍內建模一個合理的分布，即通過對密度函數進行歸一化，使其在約束區域內積分恰好為 1，這是一個 #P-難問題 [Baldoni et al., 2008]，即便分布和約束本身結構相對簡單也是如此 [Zeng et al., 2020b,a]。

其次，現實世界中關于連續變量的約束通常以復雜的代數關系 形式出現 [Barrett et al., 2021; Morettin et al., 2017]。即使是考慮變量之間簡單的線性不等式，也會導致所誘導的概率密度的支持集形成（多個）非凸多面體（non-convex polytopes）。

雖然聚焦于單一凸多面體約束可能更容易處理 [Stoian et al., 2024c]，但這無法刻畫真實場景，例如地圖中需要同時避開多個障礙物的情況（見圖1）。

學習過程中的可擴展性是另一個重要問題，理想情況下我們希望對每個數據點都能快速且準確地計算梯度。實踐中，有時通過近似或放松約束來實現這一點 [De Smet et al., 2023a,b]，但代價是放棄了基于精確最大似然 的學習方式。

在本工作中，我們填補了上述空白，提出了一種概率代數層（Probabilistic Algebraic Layer, PAL） ，它可以無縫嵌入任何神經網絡架構的最后一層，同時保證概率預測滿足復雜的代數約束。

我們的 PAL 建模方式使用了一種符號積分方案 ，其計算可以很好地擴展，因為它是可攤銷的 （amortized），即只需為所有數據點一次性計算，同時支持精確梯度 的計算，從而實現精確的最大似然訓練 ，并與現成的自動微分優化器完全兼容。

貢獻概述：

在第2節中我們正式定義了在代數約束下的概率預測問題之后：

C1) 我們在第3節中介紹 PAL 及其構成要素，并討論其性質；

C2) 然后我們在第4節中介紹用于驅動 PAL 的 GPU 加速符號多項式積分器 ；

C3) 最后，我們在一系列廣泛的實驗中評估我們的方法，包括標準的代數約束整合基準任務，以及來自 Stanford 無人機數據集 [Robicquet et al., 2016] 的真實軌跡數據。我們手動標注了表示障礙物和建筑物的約束條件，對原始數據進行了增強。

2 基于代數約束的概率預測

符號說明 ：大寫字母表示隨機變量（如 X,Y），小寫字母表示它們的具體賦值（如 x,y）。我們使用粗體表示變量集合（如 X,Y）及其聯合賦值（如 x,y）。我們用小寫希臘字母表示代數約束（如 ?），用大寫希臘字母表示（向量形式的）可學習參數。

當將變量 Y替換為賦值 y后，若公式 ?成立，則稱 y滿足 ?，記作 y??。我們用 ?{·} 表示指示函數，因此 ?{Y??} 在所有滿足 ?的 Y取值下為 1，否則為 0。

設定 ：我們的目標是從一個包含混合連續與離散變量 X和 Y的數據集 中，學習出在給定 X條件下關于 Y的參數化條件分布 pΘ(Y∣X)。

正如后文所述，挑戰主要出現在某些 Y是連續變量的情形。不失一般性，我們可以假設所有的 Y都是連續變量。

與傳統的監督學習場景不同，這里的 pΘ的定義域不是整個 R∣Y∣，而是由一個定義在 Y上的約束 ?所限制的一個子集。該約束編碼了標簽空間中哪些區域是無效的，即這些區域應具有精確為零的概率 ，因此既不應被采樣，也不應被預測 [Grivas et al., 2024]。

關注哪類約束？我們聚焦于線性不等式的布爾組合 這類代數約束。這種形式足夠靈活，能夠以非凸多面體的析取形式表示復雜的支撐集（support）。我們采用的是無量詞線性實數邏輯下的可滿足性問題 （Satisfiability Modulo Linear Real Arithmetic, SMT(LRA)）公式的語言來表達這些約束 [Barrett et al., 2021]。

從現在起，我們將 SMT(LRA) 中的約束簡稱為 SMT 公式或約束。它是一個邏輯公式，其結構是在原子 （atoms）上任意組合標準布爾連接符（∧, ∨, ?）構成的，而這些原子僅限于對 Y的線性不等式。

在引言中提到的更貼近現實的避障示例（圖1）中，? 可以建模為車輛和行人允許移動的表面。一種設計能夠感知約束條件的條件分布 pΘ 的原則性解決方案是構造一個“專家乘積”（product of experts）：

其中 qΘ是一個無約束的密度函數，其支撐集為完整的 R∣Y∣（見圖2，中間），而 1{Y??}編碼了對約束條件 ?的滿足情況。不幸的是，式(1) 并不代表一個合法的概率密度函數，因為它在積分時無法得到 1。雖然存在其他方式來訓練這樣的“專家乘積”模型 [Hinton, 2002]，但這些方法與用于訓練神經網絡的標準梯度下降優化方法——最大似然估計（MLE）并不兼容。為了通過精確的 MLE 來學習參數 Θ，從而設計出可以無縫嵌入任意網絡中的網絡層，我們需要計算式(1) 的歸一化常數，即：

這也可以被稱為加權模型積分（Weighted Model Integration, WMI）問題 [Belle 等，2015]，即約束條件 ?被滿足的概率 Pr(?)。附錄 A 深入討論了 WMI 的背景及相關文獻。

這里我們首先指出，在本文中我們將方程 (WMI) 中的所有變量 Y都視為連續變量。這樣做并不失一般性，因為我們總可以將一個包含混合離散-連續變量的 WMI 問題歸約為僅涉及連續變量的問題，而不會增加問題的維度 [Zeng 和 Van den Broeck, 2019]。然而，精確求解一個 WMI 問題在計算復雜度上通常是 #P-難的 [Zeng 等，2020a]，只有當約束條件 ?具有某些特定結構時，才存在可行的求解算法 [Zeng 等，2020b]。

為了能夠高效地計算式 (WMI)，許多神經符號系統（NeSy）選擇對其進行近似。例如 DeepProbLog 的變體 DeepSAD（DSP）[De Smet 等，2023a]，可以說是與本工作最接近的系統（見第5節），它采用拒絕采樣（rejection sampling）來估計 WMI 積分。這種方法不僅需要對約束進行松弛以進行反向傳播，從而導致梯度估計方差較高，而且也限制了系統的可擴展性，因為每個數據點 x都需要近似一次 WMI 積分。

為了能夠在如圖1所示的復雜現實約束條件下擴展神經網絡的規模，同時保持對約束滿足的理論保證，我們必須推動當前 WMI 研究的邊界。接下來，我們將討論如何做到這一點，并通過為 qΘ選擇一種參數形式（第3節），使得我們可以高效地將 WMI 積分的計算“攤銷”（amortize）進一個符號計算圖中。一旦構建完成，該計算圖便可以利用 GPU 實現并行加速（第4節）。

3 一種確保約束滿足的可微概率代數層（PAL）

我們設計了一種可微分的概率代數層（Probabilistic Algebraic Layer，PAL），用于實現以下條件分布：

更關鍵的是選擇一個合適的模型族 qλ，使得我們可以高效地“攤銷”（amortize）PAL 分母的計算。如果我們只需要處理布爾變量 Y和命題邏輯約束 ?，那么我們可以利用概率電路（Probabilistic Circuits, PCs）[Darwiche 和 Marquis, 2002；Choi 等，2020]，即像 Ahmed 等 [2022a] 中那樣的可追蹤函數上的緊湊多線性多項式。遺憾的是，對于具有所需結構屬性以確保可追蹤性的 SMT 約束，并不存在等效的電路表示 [Vergari 等，2021]。

一般多項式來解圍 。盡管我們無法利用如 PC 這類結構化多項式的性質，但我們仍可以使用一般的（分段）多項式來建模 PAL 中的無約束密度 qλ。它們仍然具備足夠的表達能力，因為它們可以以任意精度逼近任意密度函數 [Morettin 等，2021；Cheng 等，2024]，更重要的是，它們在多面體區域上的積分是封閉的 [Zeng 等，2020b]。

因此我們考慮的一般形式的多項式如下：

其中每個系數 λi∈R是主干網絡 fψ的輸出之一，而指數 αij∈N是常數參數。正如我們將在下一節中討論的那樣，積分的復雜度將取決于多項式的次數 以及單項式（monomial）的數量 M等因素。同時，這也為我們提供了一個設計固定參數可追蹤積分方案 的機會，因為我們可以人為地限制多項式的最大次數。

如何構造多項式？
我們可以通過給定一個最大次數 d，以窮舉的方式生成多項式結構，即生成所有可能的、次數不超過 d的單項式；或者通過隨機采樣這些單項式的一部分，從而構建一個緊湊但高次的多項式。另外，我們也可以使用諸如樣條函數（splines）之類的分段多項式 ，它們在機器學習中即使在低次情況下也被證明具有很高的表達能力 [Durkan 等，2019b]。具體而言，在我們的實驗中，我們使用了三次 Hermite 樣條 [Smith, 1980]，詳見附錄 B.2。

盡管上述所有多項式都可以重寫為式 (2) 所示的標準形式，但它們并不能保證所建模的是一個合法的概率密度函數，因為它們可能會產生負值。為此，我們在 PAL 中提出使用平方多項式 （squared polynomials），這類多項式因其良好的表達性而在概率電路（PC）文獻中受到關注 [Loconte 等，2024, 2025b；Loconte 和 Vergari, 2025]。

具體來說，我們考慮平方和多項式 （sum of squared polynomials），即如下形式的多項式：

4 在 GPU 上對多項式積分的極致并行化

當前最先進的（SoTA）WMI 求解器提出了多種方法，將關于約束 ?的 WMI 積分拆分為若干個在不相交的凸多面體 μ1,...,μK上的積分，使得 ?iμi≡?。因此，從現在起，我們將專注于在單個凸多面體 上對以標準形式表示的多項式（見式 (2)）進行積分的問題。

我們對該簡化問題的高效求解方案，將能夠加速所有 SoTA 的 WMI 求解器。在實際應用中，對于 PAL，我們將采用 SAE4WMI [Spallitta 等，2024] 來將 ?分解為 μ1,...,μK，因為它是目前最先進的、能夠處理任意非凸代數約束 ?的 WMI 求解器。詳見附錄 A 的討論。

我們的解決方案名為 GPU 加速單純形積分器（GPU-Accelerated Simplicial Integrator, GASP!），其核心思想是：一次性將 WMI 積分編譯成一個高度可并行化的計算圖 I?(λ)，該圖是一個關于多項式參數 λ的函數，并通過重復使用這個已編譯的函數，來“攤銷”（amortize）每個數據點 x對應的 PAL 分母的計算成本。

事實上，我們可以將定義在凸多面體 μ上的 WMI 積分表示為多個單項式積分的和：

通過將 λ視為符號變量 ，我們不再依賴于具體的數據點 x，并得到了一個符號多項式形式的積分結果 I?(λ)，其系數是各個單項式積分的結果：

請注意，求解所有這些積分是一個高度可并行化的問題 。理論上，我們可以使用像 sympy[Meurer 等，2017a] 這樣的符號計算工具，或其它精確的 WMI 求解器來完成這項任務，但在實際應用中它們速度非常慢，無法支持 PAL 的擴展性——這一點我們在第 6.1 節的實驗中已驗證。

該轉換過程詳見附錄 C.1。

為了充分發揮 GPU 的加速潛力，我們進一步探索了對每個單項式積分的并行化方法 。像 Sampo [Dos Martires 等，2019] 這樣的近似求解器可以利用 GPU 執行拒絕采樣（rejection sampling）。然而，正如在第 6.1 節中所觀察到的那樣，這種近似方法在維度和約束復雜度增加時性能迅速下降。

我們的 GASP!（GPU 加速單純形積分器） 將并行性推向極致，它通過進一步將問題分解為多個子問題（見算法1），并將這些子問題作為小型數值積分任務運行，從而充分利用 GPU 的張量運算能力（見算法2）。

簡而言之，我們采用 Grundmann 和 M?ller 積分公式 [Grundmann 和 M?ller, 1978] 來對單項式進行積分，這是一種簡單的求積規則，但它僅適用于單位單純形（unit simplex） 。

因此，我們首先使用 Delaunay 三角剖分 將每個凸多面體 μ分解為若干個單純形（見算法1 第5–7行）。接著，我們將這些單純形全部變換為單位單純形 （見算法2 第5、8和12行）。最后，我們應用 Grundmann 和 M?ller 的求積規則：該規則只需在單位單純形上的特定點處評估（變換后的）單項式，并根據預先計算的權重進行加權求和即可完成積分。

該求積規則通過生成與多項式次數相關的采樣點數量，保證了精確積分 。圖3展示了 GASP! 中完整的積分流程。

值得注意的是，GASP! 也可以作為一個獨立的多項式數值積分器使用，例如當沒有神經網絡 fψ且參數 λ是常數時。

復雜度分析

在一個凸多面體上對任意多項式進行積分是一個 NP-難的問題，但如果維度固定 ，而允許多項式次數 和單純形維度 變化，則該問題是可追蹤的 [Baldoni 等，2011]。

因此，我們的可擴展性取決于以下因素：

• 約束條件 ? 的復雜度（即分解出的單純形數量）；

• 多項式的次數（影響單項式數量和求積點數量）；

• 積分所涉及的變量維度。

我們在附錄 C.2 中深入討論了這些參數如何影響 GASP! 的性能。

需要強調的是，我們只需要在訓練前執行一次 GASP! ，之后就可以重復使用編譯好的計算圖 I?(λ)來處理所有的數據點 x，從而大大攤銷了計算成本（見圖4）。

借助 GASP! 實現高級概率推理 由于 GASP! 使我們能夠有效地對所有變量 Y進行邊緣化，從而計算 WMI 積分，因此它也允許我們在僅對 Y的一部分變量進行積分時，計算任意的 邊緣分布（marginals） 。更重要的是，它還使我們能夠在 測試階段回答其他復雜的概率推理任務 。例如，我們可以 精確地計算滿足（或違反）一個新約束的概率 ，比如在類似圖1的地圖上突然出現的新障礙物所占據的區域。

這可以通過計算：

5 相關工作

許多概率神經符號系統（NeSy）[Marra 等，2024] 只能在期望意義上 滿足約束條件。這些方法通常將約束作為損失項引入訓練過程中，并應用于多種形式化表達中，例如命題邏輯 [Xu 等，2018；Ahmed 等，2023]、模糊邏輯 [Diligenti 等，2017]、物理定律 [Stewart 和 Ermon，2017] 或者對神經網絡輸出的其他代數約束 [Fischer 等，2019]。

與 PAL 不同的是，這些方法并不能保證約束一定被滿足 。

另一系列工作則通過將約束嵌入網絡結構中 來確保其滿足。例如，Stoian 等 [2024a,b] 采用了與 PAL 類似的方法，在神經網絡之上添加了一個約束層，但該方法僅限于以不等式合取形式表示的約束，且并不提供概率建模能力 。MultiplexNet [Hoernle 等，2022] 引入了一種僅支持析取范式（DNF）形式約束的網絡層，但在學習過程中必須對該約束進行松弛。因此，它難以擴展到我們設定中的復雜約束。

DeepSade [Goyal 等，2024] 則采取了不同的路徑，它將梯度下降與約束優化相結合，以保證分類和回歸任務中的 SMT 約束。雖然該方法支持帶有量詞的 SMT 公式，但將其擴展到概率設置中非常困難。我們的工作受到語義概率層（Semantic Probabilistic Layers, SPL）[Ahmed 等，2022b] 的啟發，后者在命題邏輯情形下結合了神經網絡與概率電路 [Loconte 等，2025a]。我們在本文中將 SPL 推廣到了包含邏輯變量與連續變量混合約束 的情形。

與 SPL 類似，DeepProbLog [Manhaeve 等，2021] 使用概率邏輯編程創建了一種網絡層，但它只考慮布爾邏輯和完全分解分布 [van Krieken 等，2024]。

正如第2節所討論的那樣，最接近我們工作的系統是 DeepSeaProbLog (DSP) [De Smet 等，2023a]，它是 DeepProbLog 在連續域上的擴展。與 PAL 不同的是，在 DSP 的實現中，密度函數并不保證滿足約束條件 。實際上，DSP 是通過采樣來最大化約束被滿足的概率（即 WMI 積分）進行訓練的。附錄中詳細介紹了 DSP 的損失函數（DSP-Loss）。作為一種副作用，DSP 中無法避免使用拒絕采樣層，因為直接從 DSP 程序的無約束概率分布中采樣的樣本可能會違反約束。

附錄 D 還討論了更多相關工作。

6 PAL 的實際應用

在本節中，我們旨在回答以下研究問題：

• RQ1

  ：GASP! 與其他積分求解器相比表現如何？

• RQ2

  ：PAL 是否能夠在約束數量增加的情況下進行學習并保持可擴展性？

• RQ3

  ：PAL 是否能夠處理現實世界的數據及其復雜約束？

我們首先將 GASP! 與常用的近似數值方法（如拒絕采樣 rejection sampling）進行比較——這類方法常用于擴展概率神經符號系統（NeSy），例如 DSP（見第5節）；接著我們再將其與當前最先進的精確多項式積分工具 LattE [Baldoni 等, 2014] 進行對比。

GASP! 與 PAL 中的數值近似方法對比

我們將 GASP! 與一種基于 GPU 實現的拒絕采樣方法進行比較，在一系列維度和次數逐漸增加的非凸積分問題上評估其性能。實驗設置詳見附錄 E.1，完整結果見圖11。

在此我們展示圖4（左、中）的結果：當時間預算固定為1小時、多項式次數為8和12時，隨著維度上升，拒絕采樣難以獲得準確結果，因為被拒絕的樣本數呈指數級增長。

值得注意的是，在本實驗中約束的復雜度是固定的（由4個隨機單純形構成）。我們可以預期，當區域變得越來越復雜時，拒絕采樣的表現會更差。

相比之下，GASP! 提供了精確計算 ，并且具有更好的擴展性 （注意 y 軸是對數刻度）。更重要的是，GASP! 可以通過預先編譯好的多項式 I?(λ)來“攤銷”計算成本，并在整個 PAL 訓練過程中重復使用。

圖4（右）展示了這一點：對于一個10維、次數為12的多項式，對10?個數據點在單個凸多面體上進行積分，GASP! 僅需不到10秒，而拒絕采樣則需要長達1小時。這正是將 GASP! 應用于 PAL 的關鍵優勢之一，因為 WMI 積分的調用次數通常可以比這個規模高出幾個數量級。

GASP! 作為獨立積分器的表現 我們進一步將 GASP! 與基于錐分解的當前最先進的精確多項式積分工具 LattE [Baldoni 等, 2014] 在 WMI 積分任務中進行比較（詳情見附錄 E.2）。

我們采用 SAE4WMI（也用于 PAL，見第4節），并在從 Spallitta 等 [2024] 中提取的270個不同復雜度的 WMI 實例上，分別使用 GASP! 和 LattE 進行比較。

與前一實驗相比，這些 WMI 問題是高度非凸的，每個問題可能需要計算多達數百個積分。重要的是，在這種情況下，GASP! 無法利用其“攤銷”能力，每次都需要重新構建不同的計算圖。

盡管如此，GASP! 在270個實例中有263個都快于 LattE，速度提升了一到兩個數量級 ，如圖5所示。

最后，作為一個合理性檢查，我們在附錄 E.2.1 中還將 GASP! 與經典的符號積分工具 sympy 進行比較，結果表明 GASP! 的速度提升了約1200倍。

總體而言，我們的實驗結果確認了 GASP! 是目前最適合 PAL 的求解器 ，從而正面回答了 RQ1。

6.2 RQ2）使用 PAL 擴展約束數量

在本實驗中，我們在一個受控環境下評估 PAL 的表現，以探索在約束數量增加 的情況下，PAL 的學習準確率如何變化，同時保持變量維度不變 。

任務是學習一個受 N-pointed 星形約束 的分布，如圖6所示。對于 N=7的情形，其無約束分布是一個具有固定尺度和模式（mode）為 X的柯西分布（Cauchy distribution）。

表1報告了 PAL 與以下模型的平均測試對數似然（test log-likelihood）對比：

• 無約束神經網絡（unconstrained NN）

• 混合密度網絡 [Bishop, 1994]，輸出為高斯混合模型（GMM），不同成分數（K）

• DeepSADProbLog（DSP）

所有模型均采用相同的全連接 ReLU 神經網絡作為主干結構。具體實驗設置詳見附錄 E.3.1。

隨著 N增大，PAL 與其他競爭模型之間的性能差距逐漸拉大，因為此時可行區域的邊緣更接近模式點（mode）。由于對約束條件 ?缺乏感知，NN+GMM 難以同時擬合數據并滿足約束。

DSP 同樣面臨挑戰：它試圖通過最大化位于約束區域內（即 Pr(?)）的概率質量來訓練一個單一的多元高斯分布（multivariate Gaussian），從而導致 DSP-Loss 中提到的問題。這常常帶來一個不良后果 ——學習到的模式點偏離目標值。

這也促使我們選擇根據保留數據上的最佳對數似然 （而不是標準的最小損失）來選取 DSP 的模型。

相比之下，PAL 更容易處理這類問題，因為它天然支持約束建模 ，只需將概率質量重新分布在可行區域內即可。

6.3 RQ3）斯坦福無人機數據集（Stanford Drone Dataset）

在展示了 PAL 能夠擴展到大量約束的場景后，我們現在將其應用于真實世界數據 上進行評估，在這種情況下通常無法獲得真實標簽（ground truth） 。

由于大多數現有方法無法處理非凸約束（見第5節），目前缺乏成熟的基準測試。為此，我們引入了一個新的、具有挑戰性的任務，基于 斯坦福無人機數據集（SDD, Stanford Drone Dataset）[Robicquet 等，2016]，該數據集展示了從空中視角拍攝的行人、汽車和自行車在斯坦福校園不同場景中穿行的情況。

我們按照 Wu 等 [2023] 的方式提取軌跡，并手動標注了兩個場景：

• 場景12：包含最多軌跡；

• 場景2：包含高度非凸的約束區域。

具體來說，我們在圖像上對不可通行區域 進行分割，并將這些信息編碼為 SMT 約束。圖7展示了一個來自場景12的交叉路口及其對應的提取出的約束。

我們評估兩種設置：

1. 對所有軌跡進行聯合建模；

2. 在給定部分觀察軌跡的情況下，概率性地預測未來位置。

與 RQ1 和 RQ2 不同的是，在本實驗中我們使用了三次 Hermite 樣條函數 ，因為它們在真實數據上的訓練更容易、擴展性更好（詳見附錄 B.2）。

建模聯合軌跡分布 p(Y)

我們嘗試估計所有軌跡的聯合分布 p(Y)。這意味著我們將 PAL 作為一個獨立的概率分布估計器 來優化，而不使用任何神經網絡主干結構。實驗設置詳見附錄 E.4。

我們比較了以下模型：

• 使用復雜度逐漸增加的多項式樣條建模的 PAL；

• 成分數逐漸增加的高斯混合模型（GMM）；

• 多層變換的神經樣條流（Neural Spline Flow）[Durkan 等，2019a]。

如表2所示，PAL 實現了與尺寸相近的 GMM 相當、甚至優于更大規模的神經樣條流（參數量高出一個數量級）的測試對數似然性能。

更重要的是，PAL 從不在約束區域之外分配概率質量 ，而其他競爭模型則會違反約束條件，如圖1和表2中的 p(??)所示（表示撞上障礙物的概率，這里通過對 GMM 和樣條流模型進行 106次采樣近似得到）。

請注意，即使只有不到2%的時間違反約束，在安全關鍵型應用中也可能造成嚴重后果。

總結來說，PAL 能夠在不犧牲準確性或效率的前提下保證約束滿足 。事實上，GASP! 在 NVIDIA RTX A6000 上僅需 17 秒 即可完成對我們所考慮的最大多項式（次數 d=12）在圖7右側復雜約束下的積分。

建模未來位置分布 p(Y∣X) 在展示了我們的層能夠有效建模聯合分布之后，我們進一步考慮在 給定當前軌跡的部分觀測值 下，預測未來位置的概率分布。為此，我們從每條軌跡中采樣五個等距點作為輸入變量 X，并預測模型在地圖中任意其他位置 Y1,Y2出現的概率。

實驗設置詳見附錄 E.5。

圖8和圖9展示了PAL與NN+GMM對單條觀測軌跡所建模的條件分布。正如預期，PAL所建模的分布中呈現出多個可能的未來軌跡。

相比之下，條件GMM在捕捉 p(Y∣X)的多模態性方面表現較差，同時還明顯違反了約束條件。

表3報告了NN+PAL與NN+GMM以及DSP的定量比較（更細致的結果見表19和表22），展示了模型對未來（未觀測到的）軌跡點的平均對數似然，以及采樣出違反約束 ?的未來位置的平均概率（對于NN+GMM和DSP，使用了次采樣進行估計）。

在這個設置下我們沒有與流模型（flow）進行比較，因為將其參數化為神經網絡被證明是不可行的：僅實現一個線性的門控函數 g（見第3節）就需要數百萬個參數。

表3中的結果表明，基線方法在所有軌跡上的平均約束違反率約為18%。而對于某些軌跡，GMM模型的違反率甚至高達70%。

我們強調，條件預測中的約束違反率更高的原因在于數據量較少：而PAL由于能夠直接訪問約束 ?，因此在數據效率上具有顯著優勢。

總的來說，這些結果表明，無論是單獨使用還是與神經網絡結合使用，PAL 都展現出在不犧牲表達能力的前提下有效建模復雜真實世界分布的潛力，而這正是其他基線方法所不具備的。

因此，我們正面回答了研究問題 RQ3 。

7 結論

在本項工作中，我們提出了 PAL （Probabilistic Algebraic Layer），這是一種概率神經符號層（NeSy layer），可以作為預測層無縫嵌入任何需要處理多個連續標簽，并且這些標簽受到代數約束的神經網絡中。

為了使 PAL 能夠擴展到真實世界的數據，我們推動了 WMI（加權模型積分）領域的發展，提出了一種可并行化的多項式積分器 GASP! 。該方法甚至挑戰了像 LattE 這樣的成熟科學計算軟件，實現了高達一個數量級的加速。

未來，我們計劃進一步研究和擴展 GASP!，將其作為一個獨立的軟件工具，應用于一系列依賴多項式的高性能計算任務，例如貝葉斯推理 [Zeng 和 Van den Broeck, 2023] 和物理信息神經網絡 [Lu 等, 2021]。

與此同時，PAL 也為多個有趣的研究方向打開了大門，包括在公平性 [Pfrommer 等, 2022; Ren 等, 2024]、氣候建模 [Beucler 等, 2021; Harder 等, 2023; Willard 等, 2020; Beucler 等, 2020] 以及概率驗證 [Morettin 等, 2024] 等應用中強制引入約束條件。

此外，我們還計劃將 PAL 擴展至支持非線性約束，同時保持高度并行性 [Chin 和 Sukumar, 2020]。

原文鏈接： https://arxiv.org/abs/2503.19466