論文の概要: Solving Projected Model Counting by Utilizing Treewidth and its Limits

• arxiv url: http://arxiv.org/abs/2305.19212v2
• Date: Wed, 31 May 2023 00:51:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 11:39:21.871291
• Title: Solving Projected Model Counting by Utilizing Treewidth and its Limits
• Title（参考訳）: treewidth を利用した投影モデルカウントの解法とその限界
• Authors: Johannes K. Fichte, Markus Hecher, Michael Morak, Patrick Thier, Stefan Woltran
• Abstract要約: 予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。 いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
• 参考スコア（独自算出の注目度）: 23.81311815698799
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projection variables, where multiple solutions that are identical when restricted to the projection variables count as only one solution. Inspired by the observation that the so-called "treewidth" is one of the most prominent structural parameters, our algorithm utilizes small treewidth of the primal graph of the input instance. More precisely, it runs in time O(2^2k+4n2) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding asymptotically tight runtime bounds of our algorithm. While the algorithm above serves as a first theoretical upper bound and although it might be quite appealing for small values of k, unsurprisingly a naive implementation adhering to this runtime bound suffers already from instances of relatively small width. Therefore, we turn our attention to several measures in order to resolve this issue towards exploiting treewidth in practice: We present a technique called nested dynamic programming, where different levels of abstractions of the primal graph are used to (recursively) compute and refine tree decompositions of a given instance. Finally, we provide a nested dynamic programming algorithm and an implementation that relies on database technology for PMC and a prominent special case of PMC, namely model counting (#Sat). Experiments indicate that the advancements are promising, allowing us to solve instances of treewidth upper bounds beyond 200.
• Abstract（参考訳）: 本稿では,予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。 pmc は与えられた射影変数の集合に関してブール公式の解を数えることを要求し、射影変数に制限された複数の解は一つの解として数えられる。 いわゆる「木幅」が最も顕著な構造パラメータの1つであるという観測に触発されて、本アルゴリズムは入力インスタンスの原始グラフの小さな木幅を利用する。 より正確には、時間 O(2^2k+4n2) で、k は木幅、n はインスタンスの入力サイズである。 言い換えると、問題はtreewidthによってパラメータ化されるとき、pmc は固定パラメータ扱い可能である。 さらに, 指数時間仮説 (eth) を考慮に入れ, pmc の有界木幅アルゴリズムの下限を定め, アルゴリズムの漸近的にタイトなランタイム境界を導出する。 上記のアルゴリズムは、最初の理論上界として機能し、kの小さな値に非常にアピールするかもしれないが、当然ながら、この実行時境界に固執する単純な実装は、既に比較的小さな幅のインスタンスに悩まされている。 そこで,本研究では,木幅を活用すべく,いくつかの手法に注意を向ける。我々は,あるインスタンスの木の分解を(再帰的に)計算し,精製するために,基本グラフの抽象レベルが異なるネスト動的プログラミングと呼ばれる手法を提案する。 最後に、ネストされた動的プログラミングアルゴリズムと、MCのデータベース技術に依存した実装と、MCの顕著な特別なケースであるモデルカウント(#Sat)を提供する。 実験によると、この進歩は有望であり、200以上の木幅上限のインスタンスを解決できる。

関連論文リスト

• Des-q: a quantum algorithm to provably speedup retraining of decision trees [2.7262923206583136]
  Des-qは、回帰および二分分類タスクのための決定木を構築し、再訓練するための新しい量子アルゴリズムである。 我々は,複数のデータセット上での最先端の古典的手法に対して,Des-qのシミュレーションバージョンをベンチマークする。 提案アルゴリズムは,最新の決定木に類似した性能を示しながら,周期木再学習を著しく高速化する。
  論文  参考訳（メタデータ） (2023-09-18T17:56:08Z)
• Generalization Bounds for Magnitude-Based Pruning via Sparse Matrix Sketching [2.1485350418225244]
  我々は、エラーが1つ、プルーニングによって引き起こされる近似、および2つのプルーニングモデルにおけるパラメータの数に依存するAroraなどの上に構築する。 破断された推定値は、高い確率で未破断された関数に近づき、第一基準を改善する。 我々は,MNISTおよびCIFAR10データセット上のReLU活性化フィードフォワードネットワークにおける新しい手法の有効性を実証的に検証した。
  論文  参考訳（メタデータ） (2023-05-30T07:00:06Z)
• Threshold Treewidth and Hypertree Width [37.90910578253212]
  樹木幅と高木幅は、制約満足度(CSP)の文脈における構造パラメータとして非常に成功したことが証明されている。 ここでは、新しいしきい値の概念を通じて、木とハイパーツリーの幅を拡大する。 我々は、閾値木幅とハイパーツリー幅を計算するための効率的な理論的アルゴリズムと経験的アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-10-13T13:53:59Z)
• Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract [9.480212602202517]
  この研究は、論理ベースの問題とツリー幅ベースの方法とそれを解決するツールに焦点を当てている。 本稿では,分解誘導(DG)による新しいタイプの問題削減について述べる。 木幅を直接利用して,Satの拡張を効率的に解くアルゴリズムを実装した。
  論文  参考訳（メタデータ） (2022-08-24T07:43:58Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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