論文の概要: Pseudo-Boolean d-DNNF Compilation for Expressive Feature Modeling Constructs

• arxiv url: http://arxiv.org/abs/2505.05976v1
• Date: Fri, 09 May 2025 12:00:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-12 20:40:10.251585
• Title: Pseudo-Boolean d-DNNF Compilation for Expressive Feature Modeling Constructs
• Title（参考訳）: 表現的特徴モデリングのための擬似ブールd-DNNFコンパイル
• Authors: Chico Sundermann, Stefan Vill, Elias Kuiter, Sebastian Krieter, Thomas Thüm, Matthias Tichy,
• Abstract要約: 特徴モデルのための擬似ブール符号化を提供し、一般的に使用される構成物のより小さな表現を容易にする。 また,擬似ブール式をブールd-DNNFにコンパイルする新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 2.4497587364567925
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Configurable systems typically consist of reusable assets that have dependencies between each other. To specify such dependencies, feature models are commonly used. As feature models in practice are often complex, automated reasoning is typically employed to analyze the dependencies. Here, the de facto standard is translating the feature model to conjunctive normal form (CNF) to enable employing off-the-shelf tools, such as SAT or #SAT solvers. However, modern feature-modeling dialects often contain constructs, such as cardinality constraints, that are ill-suited for conversion to CNF. This mismatch between the input of reasoning engines and the available feature-modeling dialects limits the applicability of the more expressive constructs. In this work, we shorten this gap between expressive constructs and scalable automated reasoning. Our contribution is twofold: First, we provide a pseudo-Boolean encoding for feature models, which facilitates smaller representations of commonly employed constructs compared to Boolean encoding. Second, we propose a novel method to compile pseudo-Boolean formulas to Boolean d-DNNF. With the compiled d-DNNFs, we can resort to a plethora of efficient analyses already used in feature modeling. Our empirical evaluation shows that our proposal substantially outperforms the state-of-the-art based on CNF inputs for expressive constructs. For every considered dataset representing different feature models and feature-modeling constructs, the feature models can be significantly faster translated to pseudo-Boolean than to CNF. Overall, deriving d-DNNFs from a feature model with the targeted expressive constraints can be substantially accelerated using our pseudo-Boolean approach. Furthermore, our approach is competitive on feature models with only basic constructs.
• Abstract（参考訳）: 構成可能なシステムは通常、相互に依存関係を持つ再利用可能な資産で構成されます。 このような依存関係を特定するために、機能モデルは一般的に使用される。 機能モデルは多くの場合複雑であるため、依存関係を分析するために自動化推論が使用されるのが一般的である。 ここで、デファクトスタンダードは、SATや#SATソルバのような既製のツールを使えるように、特徴モデルを接続正規形式(CNF)に翻訳している。 しかし、現代の特徴モデリング方言は、CNFへの変換に不適な濃度制約のような構造を含むことが多い。 推論エンジンの入力と利用可能な特徴モデリング方言とのこのミスマッチは、より表現力のある構成物の適用性を制限している。 本研究では,表現的構造と拡張性のある自動推論とのギャップを短くする。 まず、機能モデルに対して擬似ブール符号化を提供し、Booleanエンコーディングと比較して、一般的に使用されるコンストラクトのより小さな表現を容易にする。 次に,擬似ブール式をブールd-DNNFにコンパイルする新しい手法を提案する。 コンパイルされたd-DNNFでは、既に機能モデリングに使われている効率的な分析を多用することができる。 実験による評価の結果,提案手法はCNF入力による表現的構成の精度を著しく上回ることがわかった。 異なる特徴モデルと特徴モデリング構造を表現するすべての考慮されたデータセットに対して、機能モデルはCNFよりもはるかに高速に擬似ブールに変換できる。 全体として、目的とする表現的制約を持つ特徴モデルからd-DNNFを導出することは、擬似ブール手法により大幅に加速することができる。 さらに,本手法は基本構造のみを持つ特徴モデルと競合する。

関連論文リスト

• Compilation and Fast Model Counting beyond CNF [31.620928650659586]
  本稿では,関数のクラスを効率的にd-DNNFに変換するか,あるいはコンパイルするかに関する理論的知識を強化する。 問題の制約は、すべての変数順序付けに対して、定数幅順序付きバイナリ決定図(OBDD)で表現可能なすべての関数である。 制約のサブファミリーに適用し,コンパイルを必要としないモデルカウントのためのより効率的なFPTアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-01T14:00:04Z)
• Bayesian Prompt Learning for Image-Language Model Generalization [64.50204877434878]
  我々はベイズ法の正規化能力を用いて、変分推論問題としてプロンプト学習をフレーム化する。 提案手法は,プロンプト空間を正規化し,目に見えないプロンプトへの過剰適合を低減し,目に見えないプロンプトのプロンプト一般化を改善する。 ベイジアン・プロンプト学習がプロンプト空間の適切なカバレッジを提供する15のベンチマークを実証的に示す。
  論文  参考訳（メタデータ） (2022-10-05T17:05:56Z)
• Language Model Cascades [72.18809575261498]
  テスト時に1つのモデルで繰り返し対話する、あるいは複数のモデルの合成は、さらに機能を拡張する。 制御フローと動的構造を持つ場合、確率的プログラミングのテクニックが必要となる。 この観点から、スクラッチパッド/思考連鎖、検証器、STaR、選択推論、ツール利用など、いくつかの既存のテクニックを定式化します。
  論文  参考訳（メタデータ） (2022-07-21T07:35:18Z)
• Space-Efficient Representation of Entity-centric Query Language Models [8.712427362992237]
  モデル生成時の非項の明示的な拡張を回避するため,確率文法に決定論的近似を導入する。 また、同じ大きさのn-gramモデルを用いた場合と比較して、長テールエンティティクエリの単語誤り率を10%改善する。
  論文  参考訳（メタデータ） (2022-06-29T19:59:50Z)
• Indeterminacy in Latent Variable Models: Characterization and Strong Identifiability [3.959606869996233]
  潜在変数モデルの不確定性を解析するための理論的枠組みを構築する。 次に、強く識別可能な潜在変数モデルを特定する方法について検討する。
  論文  参考訳（メタデータ） (2022-06-02T00:01:27Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  本稿では,強化学習目標を直接最適化し,期待される報酬を最大化するための新しいアプローチを提案する。 提案手法は、ユーザ定義プロパティを持つ分子の生成と、所定の目標値を評価する短いピソン表現の同定という2つのタスクで検証する。
  論文  参考訳（メタデータ） (2020-10-05T20:03:13Z)
• Exchangeable Neural ODE for Set Modeling [13.582728834152062]
  常微分方程式(ODE)による置換等式を実現するためのより一般的な定式化を提案する。 提案するモジュールであるExNODE(Exchangeable Neural ODE)は,識別タスクと生成タスクの両方にシームレスに適用できる。 また、時間次元における集合モデリングを拡張し、時間的集合モデリングのためのVAEベースモデルを提案する。
  論文  参考訳（メタデータ） (2020-08-06T14:11:36Z)
• Interpretable Entity Representations through Large-Scale Typing [61.4277527871572]
  本稿では,人間の読みやすいエンティティ表現を作成し,箱から高パフォーマンスを実現する手法を提案する。 我々の表現は、微粒な実体型に対する後続確率に対応するベクトルである。 特定のドメインに対して,学習に基づく方法で,型セットのサイズを縮小できることを示す。
  論文  参考訳（メタデータ） (2020-04-30T23:58:03Z)
• Improve Variational Autoencoder for Text Generationwith Discrete Latent Bottleneck [52.08901549360262]
  変分オートエンコーダ(VAE)は、エンドツーエンドの表現学習において必須のツールである。 VAEは強い自己回帰デコーダで潜伏変数を無視する傾向がある。 よりコンパクトな潜在空間において暗黙的な潜在特徴マッチングを強制する原理的アプローチを提案する。
  論文  参考訳（メタデータ） (2020-04-22T14:41:37Z)

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

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