論文の概要: Engineering an Exact Pseudo-Boolean Model Counter

• arxiv url: http://arxiv.org/abs/2312.12341v2
• Date: Sun, 18 Feb 2024 01:49:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-21 03:53:31.914894
• Title: Engineering an Exact Pseudo-Boolean Model Counter
• Title（参考訳）: 擬似ブールモデルカウンタの工学
• Authors: Suwei Yang and Kuldeep S. Meel
• Abstract要約: そこで我々は,代数的決定図を用いた知識コンパイル手法に依存する,最初の正確なPseudo-BooleanモデルカウンタPBCountを提案する。 PBCountは1513インスタンスのカウントを計算できるが、現状のアプローチでは1013インスタンスしか処理できない。
• 参考スコア（独自算出の注目度）: 38.901687092266094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Model counting, a fundamental task in computer science, involves determining the number of satisfying assignments to a Boolean formula, typically represented in conjunctive normal form (CNF). While model counting for CNF formulas has received extensive attention with a broad range of applications, the study of model counting for Pseudo-Boolean (PB) formulas has been relatively overlooked. Pseudo-Boolean formulas, being more succinct than propositional Boolean formulas, offer greater flexibility in representing real-world problems. Consequently, there is a crucial need to investigate efficient techniques for model counting for PB formulas. In this work, we propose the first exact Pseudo-Boolean model counter, PBCount, that relies on knowledge compilation approach via algebraic decision diagrams. Our extensive empirical evaluation shows that PBCount can compute counts for 1513 instances while the current state-of-the-art approach could only handle 1013 instances. Our work opens up several avenues for future work in the context of model counting for PB formulas, such as the development of preprocessing techniques and exploration of approaches other than knowledge compilation.
• Abstract（参考訳）: モデルカウント(英: model counting)とは、コンピュータ科学における基本的なタスクであり、結合正規形(cnf)で表されるブール公式の割り当て数を決定することを含む。 CNF式に対するモデルカウントは幅広い用途で広く注目されているが、Pseudo-Boolean(PB)式に対するモデルカウントの研究は比較的見過ごされている。 擬ブール公式は命題のブール公式よりも簡潔であり、現実世界の問題を表現できる柔軟性を提供する。 その結果,PB式に対するモデルカウントの効率的な手法を検討する必要がある。 本研究では,代数的決定図による知識コンパイルアプローチに依拠する,最初の完全擬ボアリーンモデルカウンタpbcountを提案する。 pbcountは1513インスタンスのカウントを計算できるが、現在の最先端のアプローチでは1013インスタンスしか処理できない。 私たちの研究は,事前処理手法の開発や知識コンパイル以外のアプローチの探求など,pb公式のモデルカウントという文脈で,今後の作業へのいくつかの道を開いた。

関連論文リスト

• PBCounter: Weighted Model Counting on Pseudo-Boolean Formulas [18.02313966511695]
  重み付きPBカウントツールPBCounterを実装した。 我々はPBCounterとSharpSAT-TD, ExactMC, D4, ADDMCの最先端の重み付きモデルカウンタを比較した。 ベンチマークの3つの領域の実験は、PBCounterがCNF式上のモデルカウンタよりも優れていることを示している。
  論文  参考訳（メタデータ） (2023-12-26T04:03:23Z)
• Lifted Algorithms for Symmetric Weighted First-Order Model Sampling [7.007419073974192]
  数量化器を用いた一階述語論理の2変数フラグメントのサンプリングにおけるドメインリフト性を証明する。 そして、この結果は、基数制約の存在下においても引き続き持続することを示す。 我々のアルゴリズムは、最先端のWMSサンプリングよりもかなりのマージンで優れています。
  論文  参考訳（メタデータ） (2023-08-17T07:40:47Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Fast Converging Anytime Model Counting [34.295512073482186]
  本稿では、近似モデルカウントのための新しい時限アプローチであるPartialKCを設計する。 我々の経験的分析により、PartialKCは最先端の近似カウンタよりも高いスケーラビリティと精度を達成できることが示された。 興味深いことに、実験の結果は、PartialKCが多くのインスタンスに収束し、したがって、最先端の正確なカウンタに匹敵する正確なモデルカウント性能を提供することを示している。
  論文  参考訳（メタデータ） (2022-12-19T12:01:28Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
  まず確率分布をモデル化し,そのモデルからサンプリングする。 これらのモデルでは, 少数の評価値を用いて, 高精度に多数の密度を近似することが可能であることが示され, それらのモデルから効果的にサンプルする簡単なアルゴリズムが提示される。
  論文  参考訳（メタデータ） (2021-10-20T12:25:22Z)
• How to Design Sample and Computationally Efficient VQA Models [53.65668097847456]
  テキストを確率的プログラムとして表現し,イメージをオブジェクトレベルのシーングラフとして表現することが,これらのデシラタを最も満足していることが判明した。 既存のモデルを拡張して,これらのソフトプログラムとシーングラフを活用して,エンドツーエンドで質問応答ペアをトレーニングします。
  論文  参考訳（メタデータ） (2021-03-22T01:48:16Z)
• Control as Hybrid Inference [62.997667081978825]
  本稿では、反復推論と償却推論のバランスを自然に仲介するCHIの実装について述べる。 連続的な制御ベンチマークでアルゴリズムのスケーラビリティを検証し、強力なモデルフリーおよびモデルベースラインを上回る性能を示す。
  論文  参考訳（メタデータ） (2020-07-11T19:44:09Z)
• On the Approximability of Weighted Model Integration on DNF Structures [13.986963122264632]
  DNF構造上の重み付きモデル積分は、実際には重み関数のクラスに対して近似できることを示す。 我々の近似アルゴリズムは3つのサブルーチンに基づいており、それぞれが弱い(すなわち近似)または強い(すなわち正確な)オラクルとなる。
  論文  参考訳（メタデータ） (2020-02-17T00:29:41Z)
• Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry [16.574508244279098]
  本稿では,重み付き1次モデルカウントを効率的にバウンドする新手法であるApproxWFOMCを提案する。 このアルゴリズムは、様々な一階確率表現を推論する。 本稿では,このアルゴリズムが一階確率モデルにおいて,既存の近似的および高精度な推論手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-01-15T12:21:06Z)

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

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