論文の概要: Efficient Knowledge Compilation Beyond Weighted Model Counting

• arxiv url: http://arxiv.org/abs/2205.07496v1
• Date: Mon, 16 May 2022 08:10:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-17 22:45:36.855218
• Title: Efficient Knowledge Compilation Beyond Weighted Model Counting
• Title（参考訳）: 重み付きモデルカウントを超えた効率的な知識コンパイル
• Authors: Rafael Kiesel, Pietro Totis and Angelika Kimmig
• Abstract要約: このような問題に対する一般的なフレームワークとして,第2レベル代数モデルカウント (2AMC) を導入している。 KC(Knowledge Compilation)に基づく第1レベルのテクニックは、変数順序制約を課すことで、特定の2AMCインスタンスに適応している。 2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。
• 参考スコア（独自算出の注目度）: 7.828647825246474
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantitative extensions of logic programming often require the solution of so called second level inference tasks, i.e., problems that involve a third operation, such as maximization or normalization, on top of addition and multiplication, and thus go beyond the well-known weighted or algebraic model counting setting of probabilistic logic programming under the distribution semantics. We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems. As 2AMC is to (algebraic) model counting what forall-exists-SAT is to propositional satisfiability, it is notoriously hard to solve. First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints on the resulting circuit. However, those constraints can severely increase the circuit size and thus decrease the efficiency of such approaches. We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect. Furthermore, we introduce and implement a strategy to generate a sufficient set of constraints statically, with a priori guarantees for the performance of KC. Our empirical evaluation on several benchmarks and tasks confirms that our theoretical results can translate into more efficient solving in practice. Under consideration for acceptance in TPLP.
• Abstract（参考訳）: 論理プログラミングの量的拡張は、しばしばいわゆる第2レベルの推論タスク(すなわち、加算と乗算の上の最大化や正規化のような第3の操作を含む問題)の解を必要とし、したがって分布意味論の下で確率論的論理プログラミングの設定を数えるよく知られた重み付けまたは代数的モデルを超えた。 この種の問題に対する汎用フレームワークとして,2次代数モデルカウント (2amc) を導入する。 2AMCは(代数的な)モデルであり、すべての既存のSATが命題の満足度を測るものであるため、解決するのは非常に難しい。 KC(Knowledge Compilation)に基づく第1レベルの手法は、結果の回路に可変順序制約を課すことにより、特定の2AMCインスタンスに適用されている。 しかし、これらの制約は回路サイズを大幅に増加させ、そのようなアプローチの効率を低下させる。 2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。 さらに,kcの性能を優先的に保証して,十分な制約セットを静的に生成する戦略を導入し,実装する。 いくつかのベンチマークやタスクにおける経験的評価は、理論的な結果が実際より効率的な解決に変換できることを確認します。 TPLPの受容についての検討

関連論文リスト

• Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thought [61.588465852846646]
  大型言語モデル(LLM)の性能向上のための有望なアプローチとして、Chain-of-Thought(CoT)推論が登場した。 本稿では,これらの課題に対処するための新しい推論境界フレームワーク(RBF)を提案する。
  論文  参考訳（メタデータ） (2024-10-08T05:26:28Z)
• Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning [0.0]
  本稿では,計算効率のよい解法の開発を可能にする2つの新しい定式化法を提案する。 提案した解法は, 計算効率, 理論的収束保証, ビュー数による局所最小値複雑性, 最先端技術と比較して, 例外的な精度を提供する。
  論文  参考訳（メタデータ） (2023-03-28T10:17:51Z)
• Confident Adaptive Language Modeling [95.45272377648773]
  CALMは、入力と生成時間ごとに異なる量の計算を動的に割り当てるフレームワークである。 ハイパフォーマンスを確実に維持しつつ、計算能力、潜在的スピードアップを最大3ドルまで削減する上で、我々のフレームワークの有効性を実証する。
  論文  参考訳（メタデータ） (2022-07-14T17:00:19Z)
• Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach [0.0]
  本稿では,パラメータ化複雑性解析を用いて,アルゴリズムの選択肢を体系的に探索する方法を示す。 環境、実演、ポリシーに対する多くの(しばしば同時に)制限に対して、我々の問題は、一般的にも、あるいは相対的に、効率的に解決できないことを示す。
  論文  参考訳（メタデータ） (2022-05-10T15:54:06Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• High Dimensional Level Set Estimation with Bayesian Neural Network [58.684954492439424]
  本稿では,ベイズニューラルネットワークを用いた高次元レベル集合推定問題を解く新しい手法を提案する。 各問題に対して対応する理論情報に基づく取得関数を導出してデータポイントをサンプリングする。 合成データセットと実世界データセットの数値実験により,提案手法は既存手法よりも優れた結果が得られることが示された。
  論文  参考訳（メタデータ） (2020-12-17T23:21:53Z)
• Robust Finite-State Controllers for Uncertain POMDPs [25.377873201375515]
  不確実部分可観測決定過程 (uPOMDPs) により、標準POMDPの確率的遷移観測関数は不確実集合に属する。 UPOMDPの有限メモリポリシを計算するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-09-24T02:58:50Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)

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

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