論文の概要: Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence
- arxiv url: http://arxiv.org/abs/2511.09174v1
- Date: Thu, 13 Nov 2025 01:37:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-13 22:34:54.446967
- Title: Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence
- Title（参考訳）: 境界木幅二項証拠を用いたトラクタブル重み付き一階モデル
- Authors: Václav Kůla, Qipeng Kuang, Yuyi Wang, Yuanhong Wang, Ondřej Kuželka,
- Abstract要約: 重み付き一階述語モデルカウント問題(WFOMC)は、与えられた一階述語論理文のモデルの重み付き和を計算することを要求する。
本稿では,WFOMCを2本の木の破片に対して演算するアルゴリズムについて述べる。
- 参考スコア（独自算出の注目度）: 2.5551288018371157
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. Conditioning WFOMC on evidence -- fixing the truth values of a set of ground literals -- has been shown impossible in time polynomial in the domain size (unless $\mathsf{\#P \subseteq FP}$) even for fragments of logic that are otherwise tractable for WFOMC without evidence. In this work, we address the barrier by restricting the binary evidence to the case where the underlying Gaifman graph has bounded treewidth. We present a polynomial-time algorithm in the domain size for computing WFOMC for the two-variable fragments $\text{FO}^2$ and $\text{C}^2$ conditioned on such binary evidence. Furthermore, we show the applicability of our algorithm in combinatorial problems by solving the stable seating arrangement problem on bounded-treewidth graphs of bounded degree, which was an open problem. We also conducted experiments to show the scalability of our algorithm compared to the existing model counting solvers.
- Abstract（参考訳）: 重み付き一階述語モデルカウント問題(WFOMC)は、与えられた一階述語論理文のモデルの重み付き和を与えられたドメイン上で計算することを要求する。
証拠に関する WFOMC の条件付け -- 基底リテラルの集合の真理値の固定 -- は、証拠無しでWFOMC に抽出可能な論理の断片であっても、ドメインサイズの時間多項式($\mathsf{\#P \subseteq FP}$を除く)では不可能であることが示されている。
本研究では、基礎となるゲイフマングラフが木幅が有界である場合に二項証拠を制限することで障壁に対処する。
2変数フラグメント $\text{FO}^2$ および $\text{C}^2$ に対する WFOMC 計算の領域サイズにおける多項式時間アルゴリズムを提案する。
さらに,有界木幅グラフ上の安定着座配置問題を解くことで,組合わせ問題におけるアルゴリズムの適用性を示す。
また,既存のモデルカウント法と比較して,アルゴリズムのスケーラビリティを示す実験を行った。
関連論文リスト
- Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。
ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-10-24T19:57:56Z) - Lifted Algorithms for Symmetric Weighted First-Order Model Sampling [7.007419073974192]
数量化器を用いた一階述語論理の2変数フラグメントのサンプリングにおけるドメインリフト性を証明する。
そして、この結果は、基数制約の存在下においても引き続き持続することを示す。
我々のアルゴリズムは、最先端のWMSサンプリングよりもかなりのマージンで優れています。
論文 参考訳（メタデータ） (2023-08-17T07:40:47Z) - Efficient Computation of Counterfactual Bounds [44.4263314637532]
我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。
近似の精度を信頼性のある間隔で評価する。
論文 参考訳（メタデータ） (2023-07-17T07:59:47Z) - Robust affine point matching via quadratic assignment on Grassmannians [50.366876079978056]
Robust Affine Matching with Grassmannians (RoAM) は点雲のアフィン登録を行うアルゴリズムである。
このアルゴリズムは、グラスマンの2つの要素間のフロベニウス距離を最小化することに基づいている。
論文 参考訳（メタデータ） (2023-03-05T15:27:24Z) - Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
多くのSRLにおける確率的推論と学習は、重み付き第一モデルカウント(WFOMC)に還元できる
WFOMCは難解であることが知られている(mathrm#P$ complete)。
我々は,DAG(Directed Acyclic Graph)を除外したフラグメント$mathrmC2$,すなわち公理DAGを表す公理化グラフがドメインリフト可能であることを示す。
論文 参考訳（メタデータ） (2023-02-20T08:35:13Z) - Diffusion models as plug-and-play priors [98.16404662526101]
我々は、事前の$p(mathbfx)$と補助的な制約である$c(mathbfx,mathbfy)$からなるモデルにおいて、高次元データ$mathbfx$を推論する問題を考える。
拡散モデルの構造は,異なるノイズ量に富んだ定性デノナイジングネットワークを通じて,微分を反復することで近似推論を行うことができる。
論文 参考訳（メタデータ） (2022-06-17T21:11:36Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - Weighted Model Counting in the two variable fragment with Cardinality
Constraints: A Closed Form Formula [7.766921168069532]
重み付き一階モデルカウント(WFOMC)は、与えられた有限領域上の一階理論のモデルの重み付き和を計算する。
WFOMCの推論を定式化するためのツールとして,リフト解釈の概念を導入する。
次に、この閉形式を拡張して、存在量化器と濃度制約をドメインリフト性を失うことなく組み込む。
論文 参考訳（メタデータ） (2020-09-25T13:50:18Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。