論文の概要: Dynamic Blocked Clause Elimination for Projected Model Counting

• arxiv url: http://arxiv.org/abs/2408.06199v1
• Date: Mon, 12 Aug 2024 14:49:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-13 13:03:23.760026
• Title: Dynamic Blocked Clause Elimination for Projected Model Counting
• Title（参考訳）: 予測されたモデルカウントのための動的ブロッククロース除去
• Authors: Jean-Marie Lagniez, Pierre Marquis, Armin Biere,
• Abstract要約: これは、与えられた変数の集合 X を取り除いた後、命題式 Sigma| のモデルエクサスト X.Sigma| の数を決定する問題である。 SAT解決におけるブロック節除去はよく知られた手法であるが, モデルカウントへの直接適用は困難である。 本研究では,ブロックされた節探索中の予測変数に着目して,ブロックされた節の除去を正しいモデルカウントを保ちながら活用できることを実証する。
• 参考スコア（独自算出の注目度）: 20.62154894623858
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we explore the application of blocked clause elimination for projected model counting. This is the problem of determining the number of models ||\exists X.{\Sigma}|| of a propositional formula {\Sigma} after eliminating a given set X of variables existentially. Although blocked clause elimination is a well-known technique for SAT solving, its direct application to model counting is challenging as in general it changes the number of models. However, we demonstrate, by focusing on projected variables during the blocked clause search, that blocked clause elimination can be leveraged while preserving the correct model count. To take advantage of blocked clause elimination in an efficient way during model counting, a novel data structure and associated algorithms are introduced. Our proposed approach is implemented in the model counter d4. Our experiments demonstrate the computational benefits of our new method of blocked clause elimination for projected model counting.
• Abstract（参考訳）: 本稿では,プロジェクテッドモデルカウントにおけるブロック節除去の適用について検討する。 これは、モデル ||\exists X の数を決定する問題である。 変数の与えられた集合 X を実存的に排除した後、命題公式 {\Sigma} の {\Sigma}|| が成立する。 ブロックされた節の除去はSATの解法としてよく知られている手法であるが、モデルカウントへの直接適用は、一般的にはモデル数を変更するため困難である。 しかし, ブロック節探索において, 予測変数に着目して, 正しいモデル数を保持しつつ, ブロック節除去を活用できることを実証する。 モデルカウント中にブロック節の除去を効率的に行うために、新しいデータ構造と関連するアルゴリズムを導入する。 提案手法はモデルカウンタd4に実装されている。 本実験は,予測モデルカウントのためのブロック節除去手法の計算的利点を実証するものである。

関連論文リスト

• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  CoT(Chain-of-Thought)の促進とその変種は、多段階推論問題を解決する効果的な方法として人気を集めている。 統計的推定の観点からCoTのプロンプトを解析し,その複雑さを包括的に評価する。
  論文  参考訳（メタデータ） (2024-08-25T04:07:18Z)
• Mean estimation in the add-remove model of differential privacy [20.78625240235862]
  加算除去モデルに基づく一次元平均推定問題について検討する。 提案アルゴリズムは,実際に頻繁に使用されるアルゴリズムよりも,平均2乗誤差が2倍に向上することを示す。
  論文  参考訳（メタデータ） (2023-12-11T18:59:35Z)
• A model-free feature selection technique of feature screening and random forest based recursive feature elimination [0.0]
  質量特徴を持つ超高次元データのモデルフリー特徴選択法を提案する。 提案手法は選択整合性を示し, 弱正則条件下では$L$整合性を示す。
  論文  参考訳（メタデータ） (2023-02-15T03:39:16Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• A Bayesian Approach to Block-Term Tensor Decomposition Model Selection and Computation [10.91885508254207]
  いわゆるブロック項分解(BTD)テンソルモデル(特にランク=(L_r,L_r,1)$バージョン)は近年注目を集めている。 BTDモデル構造、すなわちブロック項の数とその個々のランクを推定するという課題は、最近になって注目され始めたばかりです。 ランク-$(L_r,L_r,1)$ BTDモデルの選択と計算の問題を、列の間隔を直交するアイデアに基づいて解くためのベイズ的アプローチが採られる。
  論文  参考訳（メタデータ） (2021-01-08T09:37:21Z)
• Control as Hybrid Inference [62.997667081978825]
  本稿では、反復推論と償却推論のバランスを自然に仲介するCHIの実装について述べる。 連続的な制御ベンチマークでアルゴリズムのスケーラビリティを検証し、強力なモデルフリーおよびモデルベースラインを上回る性能を示す。
  論文  参考訳（メタデータ） (2020-07-11T19:44:09Z)
• Selective Inference for Latent Block Models [50.83356836818667]
  本研究では,潜在ブロックモデルに対する選択的推論法を提案する。 我々は,潜在ブロックモデルの行と列クラスタのメンバシップの集合に対する統計的テストを構築した。 提案された正確で近似されたテストは、選択バイアスを考慮していない単純なテストと比較して効果的に機能する。
  論文  参考訳（メタデータ） (2020-05-27T10:44:19Z)
• Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry [16.574508244279098]
  本稿では,重み付き1次モデルカウントを効率的にバウンドする新手法であるApproxWFOMCを提案する。 このアルゴリズムは、様々な一階確率表現を推論する。 本稿では,このアルゴリズムが一階確率モデルにおいて,既存の近似的および高精度な推論手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-01-15T12:21:06Z)

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

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