論文の概要: Compilation and Fast Model Counting beyond CNF

• arxiv url: http://arxiv.org/abs/2502.00434v1
• Date: Sat, 01 Feb 2025 14:00:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 14:56:16.857818
• Title: Compilation and Fast Model Counting beyond CNF
• Title（参考訳）: CNFを超えるコンパイルと高速モデルカウント
• Authors: Alexis de Colnet, Stefan Szeider, Tianwei Zhang,
• Abstract要約: 本稿では,関数のクラスを効率的にd-DNNFに変換するか,あるいはコンパイルするかに関する理論的知識を強化する。 問題の制約は、すべての変数順序付けに対して、定数幅順序付きバイナリ決定図(OBDD)で表現可能なすべての関数である。 制約のサブファミリーに適用し,コンパイルを必要としないモデルカウントのためのより効率的なFPTアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 31.620928650659586
• License:
• Abstract: Circuits in deterministic decomposable negation normal form (d-DNNF) are representations of Boolean functions that enable linear-time model counting. This paper strengthens our theoretical knowledge of what classes of functions can be efficiently transformed, or compiled, into d-DNNF. Our main contribution is the fixed-parameter tractable (FPT) compilation of conjunctions of specific constraints parameterized by incidence treewidth. This subsumes the known result for CNF. The constraints in question are all functions representable by constant-width ordered binary decision diagrams (OBDDs) for all variable orderings. For instance, this includes parity constraints and cardinality constraints with constant threshold. The running time of the FPT compilation is singly exponential in the incidence treewidth but hides large constants in the exponent. To balance that, we give a more efficient FPT algorithm for model counting that applies to a sub-family of the constraints and does not require compilation.
• Abstract（参考訳）: 決定論的分解可能な否定正規形(d-DNNF)の回路は、線形時間モデルカウントを可能にするブール関数の表現である。 本稿では,関数のクラスを効率的にd-DNNFに変換するか,あるいはコンパイルするかに関する理論的知識を強化する。 我々の主な貢献は、入射木幅によってパラメータ化された特定の制約の結合の固定パラメータトラクタブル(FPT)コンパイルである。 これはCNFの既知の結果を仮定する。 問題の制約は、すべての変数順序付けに対して、定数幅順序付きバイナリ決定図(OBDD)で表現可能なすべての関数である。 例えば、これはパリティ制約と定数しきい値を持つ濃度制約を含む。 FPTコンパイルの実行時間は、入射ツリー幅において単独で指数的であるが、指数において大きな定数を隠蔽する。 そのバランスをとるために、制約のサブファミリーに適用され、コンパイルを必要としないモデルカウントのためのより効率的なFPTアルゴリズムを提供する。

関連論文リスト

• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  構造エントロピー誘導型確率的符号化モデルSEPCを提案する。 我々は、構造エントロピー正規化損失を提案することにより、潜在変数間の関係を最適化に組み込む。 分類タスクと回帰タスクの両方を含む12の自然言語理解タスクに対する実験結果は、SEPCの優れた性能を示す。
  論文  参考訳（メタデータ） (2024-12-12T00:37:53Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures [12.47276164048813]
  1次モデルカウント(英: First-order model counting、FOMC)は、有限領域の1次論理において文のモデルを数えるように要求する計算問題である。 私たちは、典型的にドメイン再帰に伴う制限を緩和し、サイクルを含むかもしれない有向グラフを扱う。 これらの改良により、アルゴリズムはそれまで到達範囲を超えていた問題を数えるための効率的な解を見つけることができる。
  論文  参考訳（メタデータ） (2023-06-07T06:49:01Z)
• Bayesian Kernelized Tensor Factorization as Surrogate for Bayesian Optimization [13.896697187967545]
  カーネル最適化(BO)は主にガウス過程(GP)をキーサロゲートモデルとして用いている。 本稿では,BOにおける新しい代理モデルとしてベイズ因子化(BKTF)を提案する。 BKTFは、不確実量化を伴う複素関数を特徴づけるための柔軟で効果的なアプローチを提供する。
  論文  参考訳（メタデータ） (2023-02-28T12:00:21Z)
• A Lower Bound on DNNF Encodings of Pseudo-Boolean Constraints [3.42658286826597]
  疑似ブール制約をSATにエンコーディングする際の2つの大きな考慮事項は、エンコーディングのサイズとその伝播強度である。 命令されたBDD(OBDD)表現と推論されたCNFエンコーディングがすべて指数的サイズを持つPB制約が存在することが示されている。
  論文  参考訳（メタデータ） (2021-01-06T10:25:22Z)
• Exponentially Weighted l_2 Regularization Strategy in Constructing Reinforced Second-order Fuzzy Rule-based Model [72.57056258027336]
  従来の高木スゲノカン(TSK)型ファジィモデルでは、定数あるいは線形関数がファジィ規則の連続部分として使用されるのが普通である。 調和解析で遭遇する重み関数理論にインスパイアされた指数重みアプローチを導入する。
  論文  参考訳（メタデータ） (2020-07-02T15:42:15Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  特徴相互作用の効率的なモデリングは、非順序的タスクに対する教師あり学習の基盤となる。 この問題を緩和するため、モデルパラメータをテンソルとして暗黙的に表現することが提案されている。 表現性を向上するため,任意の高次元特徴ベクトルに特徴写像を適用できるようにフレームワークを一般化する。
  論文  参考訳（メタデータ） (2020-01-27T22:38:40Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)
• Learning Likelihoods with Conditional Normalizing Flows [54.60456010771409]
  条件正規化フロー(CNF)はサンプリングと推論において効率的である。 出力空間写像に対する基底密度が入力 x 上で条件づけられた CNF について、条件密度 p(y|x) をモデル化する。
  論文  参考訳（メタデータ） (2019-11-29T19:17:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。