論文の概要: Towards Projected and Incremental Pseudo-Boolean Model Counting

• arxiv url: http://arxiv.org/abs/2412.14485v2
• Date: Fri, 20 Dec 2024 15:18:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 13:01:30.493946
• Title: Towards Projected and Incremental Pseudo-Boolean Model Counting
• Title（参考訳）: Pseudo-Boolean Model Counting の予測とインクリメンタル化に向けて
• Authors: Suwei Yang, Kuldeep S. Meel,
• Abstract要約: Pseudo-Boolean(PB)モデルカウンタは,プロジェクションとインクリメンタルモデルカウントをサポートする。 我々の評価では、PBCount2は、投影されたモデルカウントの競合するメソッドのベンチマーク数を少なくとも1.40倍、インクリメンタルモデルカウントにおける競合するメソッドの少なくとも1.18倍のベンチマークを完了した。
• 参考スコア（独自算出の注目度）: 32.92936885170422
• License:
• Abstract: Model counting is a fundamental task that involves determining the number of satisfying assignments to a logical formula, typically in conjunctive normal form (CNF). While CNF model counting has received extensive attention over recent decades, interest in Pseudo-Boolean (PB) model counting is just emerging partly due to the greater flexibility of PB formulas. As such, we observed feature gaps in existing PB counters such as a lack of support for projected and incremental settings, which could hinder adoption. In this work, our main contribution is the introduction of the PB model counter PBCount2, the first exact PB model counter with support for projected and incremental model counting. Our counter, PBCount2, uses our Least Occurrence Weighted Min Degree (LOW-MD) computation ordering heuristic to support projected model counting and a cache mechanism to enable incremental model counting. In our evaluations, PBCount2 completed at least 1.40x the number of benchmarks of competing methods for projected model counting and at least 1.18x of competing methods in incremental model counting.
• Abstract（参考訳）: モデルカウント(英: Model counting)は、論理式(典型的には共役正規形式(英語版)(CNF))への代入を満足させる数を決定することを含む基本的なタスクである。 近年、CNFモデルカウントは注目されているが、PB式がより柔軟であることから、Pseudo-Boolean(PB)モデルカウントへの関心が高まっている。 その結果,既存のPBカウンタでは,プロジェクションやインクリメンタル設定のサポートが欠如しているため,採用の妨げとなる可能性がある。 本研究では,PBモデルカウンタPBCount2を導入し,プロジェクテッドモデルカウンタとインクリメンタルモデルカウンタをサポートするPBモデルカウンタについて述べる。 我々のカウンタPBCount2は、我々のLast Occurrence Weighted Min Degree (LOW-MD) 計算注文ヒューリスティックを使用して、投影されたモデルカウントとインクリメンタルモデルカウントを可能にするキャッシュメカニズムをサポートします。 我々の評価では、PBCount2は、投影されたモデルカウントの競合するメソッドのベンチマーク数を少なくとも1.40倍、インクリメンタルモデルカウントにおける競合するメソッドの少なくとも1.18倍のベンチマークを完了した。

関連論文リスト

• Model Counting in the Wild [31.05707402954459]
  モデルカウンタの荒野におけるスケーラビリティの厳密な評価を行う。 我々は、これらのインスタンス上で6つの最先端モデルカウンタを評価し、スケーラビリティと実行時のパフォーマンスを評価する。 私たちの分析は、モデルカウントにおけるポートフォリオベースのアプローチの課題と機会を強調します。
  論文  参考訳（メタデータ） (2024-08-13T17:49:46Z)
• MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
  Amortized Pareto Front (MAP) を用いた新しい低演算アルゴリズム Model Merging を導入する。 MAPは、複数のモデルをマージするためのスケーリング係数のセットを効率的に識別し、関連するトレードオフを反映する。 また,タスク数が比較的少ないシナリオではベイジアンMAP,タスク数の多い状況ではNested MAPを導入し,計算コストを削減した。
  論文  参考訳（メタデータ） (2024-06-11T17:55:25Z)
• 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)
• Engineering an Exact Pseudo-Boolean Model Counter [38.901687092266094]
  そこで我々は,代数的決定図を用いた知識コンパイル手法に依存する,最初の正確なPseudo-BooleanモデルカウンタPBCountを提案する。 PBCountは1513インスタンスのカウントを計算できるが、現状のアプローチでは1013インスタンスしか処理できない。
  論文  参考訳（メタデータ） (2023-12-19T17:14:06Z)
• The Languini Kitchen: Enabling Language Modelling Research at Different Scales of Compute [66.84421705029624]
  本稿では,アクセル時間で測定された等価計算に基づくモデル比較を可能にする実験的プロトコルを提案する。 私たちは、既存の学術的ベンチマークを上回り、品質、多様性、文書の長さで上回る、大規模で多様で高品質な書籍データセットを前処理します。 この研究は、GPT-2アーキテクチャから派生したフィードフォワードモデルと、10倍のスループットを持つ新しいLSTMの形式でのリカレントモデルという2つのベースラインモデルも提供する。
  論文  参考訳（メタデータ） (2023-09-20T10:31:17Z)
• Fast Converging Anytime Model Counting [34.295512073482186]
  本稿では、近似モデルカウントのための新しい時限アプローチであるPartialKCを設計する。 我々の経験的分析により、PartialKCは最先端の近似カウンタよりも高いスケーラビリティと精度を達成できることが示された。 興味深いことに、実験の結果は、PartialKCが多くのインスタンスに収束し、したがって、最先端の正確なカウンタに匹敵する正確なモデルカウント性能を提供することを示している。
  論文  参考訳（メタデータ） (2022-12-19T12:01:28Z)
• CounTR: Transformer-based Generalised Visual Counting [94.54725247039441]
  我々は任意の意味圏からオブジェクト数を数える計算モデルを開発し、任意の数の「例」を用いて計算する。 FSC-147のような大規模カウントベンチマークの徹底的なアブレーション研究を行い、ゼロおよび少数ショット設定の両方で最先端の性能を示す。
  論文  参考訳（メタデータ） (2022-08-29T17:02:45Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Projected Model Counting: Beyond Independent Support [27.606526752377615]
  現代のカウンタで使われる鍵となる考え方は、しばしば射影集合の小さな部分集合である指数依存的なサポートに射影されたモデルを数えることである。 本稿では直観とは対照的に、射影集合を超えた変数を射影することは有益であることを示す。
  論文  参考訳（メタデータ） (2021-10-18T10:40:22Z)

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

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