論文の概要: Scalable Algorithms for Approximate DNF Model Counting

• arxiv url: http://arxiv.org/abs/2601.10511v1
• Date: Thu, 15 Jan 2026 15:38:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-16 19:43:19.197625
• Title: Scalable Algorithms for Approximate DNF Model Counting
• Title（参考訳）: 近似DNFモデルカウントのためのスケーラブルアルゴリズム
• Authors: Paul Burkhardt, David G. Harris, Kevin T Schmitt,
• Abstract要約: DNF(Disjunctive Normal Form)公式のモデルカウントは確率的推論やネットワーク信頼性といった応用において重要な問題である。 適応的な停止規則を短時間で評価するモンテカルロ法を開発した。 実験により,従来のアルゴリズムは桁違いに性能が向上し,数百万の変数に対してはるかに大きな問題にスケールできることが示された。
• 参考スコア（独自算出の注目度）: 1.4146420810689422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. These include Monte Carlo approaches such as the classical algorithms of Karp, Luby, and Madras (1989), as well as methods based on hashing (Soos et al. 2023), and heuristic approximations based on Neural Nets (Abboud, Ceylan, and Lukasiewicz 2020). We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and is asymptotically more efficient than the previous methods. We also show experimentally that it out-performs prior algorithms by orders of magnitude, and can scale to much larger problems with millions of variables.
• Abstract（参考訳）: DNF(Disjunctive Normal Form)公式のモデルカウントは確率的推論やネットワーク信頼性といった応用において重要な問題である。 例えば、確率的データベースにおけるクエリ評価によく使用される。 正確なDNFカウントの計算難易度のため、様々な近似アルゴリズムの研究が続けられている。 例えば、カルプ、ルビー、マドラスの古典的アルゴリズム(1989年)やハッシュに基づく手法(Soos et al 2023年)、ニューラルネットに基づくヒューリスティック近似(Abboud、Ceylan、Lukasiewicz 2020年)などがある。 適応的停止規則と短絡式評価を併用したモンテカルロの新手法を開発した。 確率的近似学習境界(PAC)を実現し,従来の手法よりも漸近的に効率的であることを示す。 また,従来のアルゴリズムを桁違いに上回り,数百万の変数に対してはるかに大きな問題にスケールできることを実験的に示す。

関連論文リスト

• Quantum speedup of non-linear Monte Carlo problems [3.534338813984755]
  本研究では,非線形推定問題の幅広いクラスに対する高速化を実現する量子インサイド量子モンテカルロアルゴリズムを提案する。 このアプローチの重要な革新は、量子コンピューティング用に特別に設計されたマルチレベルモンテカルロ近似の新しいシーケンスである。
  論文  参考訳（メタデータ） (2025-02-07T17:13:27Z)
• Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood [2.312692134587988]
  連続時間(生死)および離散時間(可逆ジャンプ)マルコフ連鎖モンテカルロ(MCMC)アルゴリズムを開発し、グラフ空間の後方を効率的に探索する。 アルゴリズムは巨大なグラフ空間にスケールし、1000以上のノードを持つグラフの並列探索を可能にする。
  論文  参考訳（メタデータ） (2023-06-30T20:37:40Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。 より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。 我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
  論文  参考訳（メタデータ） (2022-05-17T15:28:46Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  既存の不確実性推定アルゴリズムでは、モデルアーキテクチャとトレーニング手順を変更する必要がある。 本研究では、与えられたトレーニングされたニューラルネットワークに適用し、近似予測間隔を生成できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:18:31Z)
• Benchmarking Simulation-Based Inference [5.3898004059026325]
  確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。 推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。 性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
  論文  参考訳（メタデータ） (2021-01-12T18:31:22Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)
• Scalable Distributed Approximation of Internal Measures for Clustering Evaluation [5.144809478361603]
  クラスタリング評価のための内部測度はシルエット係数であり、計算には2つの距離計算が必要である。 本稿では,任意の距離に基づいてクラスタリングの評価を行うための厳密な近似を計算した最初のスケーラブルアルゴリズムを提案する。 また,このアルゴリズムは凝集や分離などのクラスタリング品質の他の内部指標の厳密な近似に適応可能であることも証明した。
  論文  参考訳（メタデータ） (2020-03-03T10:28:14Z)

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

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