論文の概要: Categorical Belief Propagation: Sheaf-Theoretic Inference via Descent and Holonomy
- arxiv url: http://arxiv.org/abs/2601.04456v1
- Date: Thu, 08 Jan 2026 00:03:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-09 17:01:52.959923
- Title: Categorical Belief Propagation: Sheaf-Theoretic Inference via Descent and Holonomy
- Title（参考訳）: カテゴリー的信念の伝播--老化とホロノミーによるせん断理論推論
- Authors: Enrique ter Horst, Sridhar Mahadevan, Juan Diego Zambrano,
- Abstract要約: 因子グラフ上での信念伝播のための分類的基盤を開発する。
メッセージパッシングは、分極因子グラフ上のGrothendieckフィブレーション (int to catFG_) を用いて定式化される。
本稿では,因子神経のホロノミーによる降下障害検出アルゴリズムであるHATCCを紹介する。
- 参考スコア（独自算出の注目度）: 1.001355398440049
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a categorical foundation for belief propagation on factor graphs. We construct the free hypergraph category \(\Syn_Σ\) on a typed signature and prove its universal property, yielding compositional semantics via a unique functor to the matrix category \(\cat{Mat}_R\). Message-passing is formulated using a Grothendieck fibration \(\int\Msg \to \cat{FG}_Σ\) over polarized factor graphs, with schedule-indexed endomorphisms defining BP updates. We characterize exact inference as effective descent: local beliefs form a descent datum when compatibility conditions hold on overlaps. This framework unifies tree exactness, junction tree algorithms, and loopy BP failures under sheaf-theoretic obstructions. We introduce HATCC (Holonomy-Aware Tree Compilation), an algorithm that detects descent obstructions via holonomy computation on the factor nerve, compiles non-trivial holonomy into mode variables, and reduces to tree BP on an augmented graph. Complexity is \(O(n^2 d_{\max} + c \cdot k_{\max} \cdot δ_{\max}^3 + n \cdot δ_{\max}^2)\) for \(n\) factors and \(c\) fundamental cycles. Experimental results demonstrate exact inference with significant speedup over junction trees on grid MRFs and random graphs, along with UNSAT detection on satisfiability instances.
- Abstract（参考訳）: 因子グラフ上での信念伝播のための分類的基盤を開発する。
我々は、型付きシグネチャ上に自由ハイパーグラフ圏 \(\Syn_Σ\) を構築し、その普遍性を証明し、一意関手を通して行列圏 \(\cat{Mat}_R\) に合成意味を与える。
メッセージパッシングは、分極因子グラフ上のGrothendieck Fibration \(\int\Msg \to \cat{FG}_Σ\)を用いて定式化され、BP更新を定義するスケジュール付き内在型が定義される。
相関条件が重なり合う場合、局所的な信念は降下ダタムを形成する。
このフレームワークは、木の正確性、ジャンクションツリーアルゴリズム、およびせん断理論的障害物下でのループBP故障を統一する。
HATCC (Holonomy-Aware Tree Compilation) は、因子神経上のホロノミー計算によって降下障害を検出するアルゴリズムであり、非自明なホロノミーをモード変数にコンパイルし、拡張グラフ上の木BPに還元するアルゴリズムである。
複素性は \(n\) 因子および \(c\) 基本サイクルに対して \(O(n^2 d_{\max} + c \cdot k_{\max} \cdot δ_{\max}^3 + n \cdot δ_{\max}^2)\) である。
実験結果から,格子状MRFおよびランダムグラフ上のジャンクションツリー上の有意な高速化と,充足可能性のあるUNSAT検出による推定が得られた。
関連論文リスト
- From GNNs to Trees: Multi-Granular Interpretability for Graph Neural Networks [29.032055397116217]
解釈可能なグラフニューラルネットワーク(GNN)は、モデル予測の背後にある理由を明らかにすることを目的としている。
既存の部分グラフベースの解釈可能なメソッドは、局所構造上のオーバーエンハンシスに悩まされる。
グラフ分類のための新しいツリーライクな解釈フレームワーク(TIF)を提案する。
論文 参考訳（メタデータ） (2025-05-01T07:22:51Z) - Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。
本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。
これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
論文 参考訳（メタデータ） (2023-10-14T07:02:54Z) - Efficient Computation of Counterfactual Bounds [44.4263314637532]
我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。
近似の精度を信頼性のある間隔で評価する。
論文 参考訳（メタデータ） (2023-07-17T07:59:47Z) - Mixtures of All Trees [28.972995038976745]
我々は、すべての木の混合と呼ばれる新しい生成モデルのクラスを提案し、すなわち、$n$変数上のすべての可能な(nn-2$)木形のグラフィカルモデルに混合する。
我々は,この混合木モデル(MoAT)をコンパクトにパラメータ化することで,勾配勾配勾配による抽出可能な可能性と最適化を可能にすることを示す。
論文 参考訳（メタデータ） (2023-02-27T23:37:03Z) - EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
人口のログライクな独特な非自明な点は、その大域的な最大点であることを示す。
予測最大化アルゴリズムは、単一の潜在変数の場合に収束することが保証される。
論文 参考訳（メタデータ） (2022-11-21T23:12:58Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Lassoed Tree Boosting [53.56229983630983]
有界断面変動のカドラー関数の大きな非パラメトリック空間において,早期に停止するn-1/4$ L2の収束速度を持つ勾配向上木アルゴリズムを証明した。
我々の収束証明は、ネストしたドンスカー類の経験的損失最小化子による早期停止に関する新しい一般定理に基づいている。
論文 参考訳（メタデータ） (2022-05-22T00:34:41Z) - From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical
Clustering [33.000371053304676]
本稿では,Dasguptaの離散最適化問題に対して,証明可能な品質保証を用いた最初の連続緩和を提案する。
勾配勾配勾配の近似解でさえ、凝集性クラスタリングよりも優れた品質を有することを示す。
また、下流分類タスクにおけるエンドツーエンドトレーニングによるHypHCの柔軟性についても強調する。
論文 参考訳（メタデータ） (2020-10-01T13:43:19Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。