論文の概要: Bounds on BDD-Based Bucket Elimination
- arxiv url: http://arxiv.org/abs/2306.00886v1
- Date: Thu, 1 Jun 2023 16:48:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 14:27:21.179619
- Title: Bounds on BDD-Based Bucket Elimination
- Title（参考訳）: BDDベースのバケット排除の境界
- Authors: Stefan Mengel
- Abstract要約: 変数除去を用いた満足度テストのアプローチであるBDDベースのバケット除去について検討する。
可変除去とBDD表現の異なる順序を許容する場合、標準のハトホール原理を効率的に解けることが証明された。
- 参考スコア（独自算出の注目度）: 4.797216015572358
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study BDD-based bucket elimination, an approach to satisfiability testing
using variable elimination which has seen several practical implementations in
the past. We prove that it allows solving the standard pigeonhole principle
formulas efficiently, when allowing different orders for variable elimination
and BDD-representations, a variant of bucket elimination that was recently
introduced. Furthermore, we show that this upper bound is somewhat brittle as
for formulas which we get from the pigeonhole principle by restriction, i.e.,
fixing some of the variables, the same approach with the same variable orders
has exponential runtime. We also show that the more common implementation of
bucket elimination using the same order for variable elimination and the BDDs
has exponential runtime for the pigeonhole principle when using either of the
two orders from our upper bound, which suggests that the combination of both is
the key to efficiency in the setting.
- Abstract（参考訳）: bddベースのバケット除去について検討し,変数除去を用いた満足度テストのアプローチについて検討した。
最近導入されたバケット除去の変種である可変除去とBDD表現の異なる順序を許容する場合、標準的なハトホール原理を効率的に解けることが証明されている。
さらに、この上界は、ハトホールの原理から得られる式、すなわち、いくつかの変数を修正することで、同じ変数の順序を持つ同じアプローチが指数関数的なランタイムを持つように、やや不安定であることを示した。
また,変分除去とBDDを併用したバケット除去のより一般的な実装は,上界からの2つの順序のどちらかを用いることで,ハトホール原理の指数的実行が可能であることを示し,両者の組み合わせが,設定における効率の鍵であることを示唆している。
関連論文リスト
- Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。
ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-10-24T19:57:56Z) - Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams [38.04922933299814]
テストバイベッティングフレームワークの上に構築し、停止時間にまたがる非漸近的な$alpha$レベルのテストを提供します。
実験の結果,PEAKは停止前のサンプル数を最大85%削減できることがわかった。
論文 参考訳（メタデータ） (2024-02-09T01:11:34Z) - Predicting Ordinary Differential Equations with Transformers [65.07437364102931]
単一溶液軌道の不規則サンプリングおよび雑音観測から,スカラー常微分方程式(ODE)を記号形式で復元するトランスフォーマーに基づくシーケンス・ツー・シーケンス・モデルを開発した。
提案手法は, 1回に一度, ODE の大規模な事前訓練を行った後, モデルのいくつかの前方通過において, 新たな観測解の法則を推測することができる。
論文 参考訳（メタデータ） (2023-07-24T08:46:12Z) - Direct Diffusion Bridge using Data Consistency for Inverse Problems [65.04689839117692]
拡散モデルに基づく逆問題解法は優れた性能を示したが、速度は制限されている。
いくつかの最近の研究は、拡散プロセスを構築し、クリーンで破損したものを直接ブリッジすることでこの問題を緩和しようと試みている。
微調整を必要とせずにデータの一貫性を強制する改良された推論手順を提案する。
論文 参考訳（メタデータ） (2023-05-31T12:51:10Z) - Discovering ordinary differential equations that govern time-series [65.07437364102931]
本研究では, 1つの観測解の時系列データから, スカラー自律常微分方程式(ODE)を記号形式で復元するトランスフォーマーに基づくシーケンス・ツー・シーケンス・モデルを提案する。
提案手法は, 1回に一度, ODE の大規模な事前訓練を行った後, モデルのいくつかの前方通過において, 新たに観測された解の法則を推測することができる。
論文 参考訳（メタデータ） (2022-11-05T07:07:58Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳（メタデータ） (2022-10-27T17:59:09Z) - A Stochastic Variance Reduced Gradient using Barzilai-Borwein Techniques
as Second Order Information [0.0]
本研究では,対象関数の曲率情報を組み込むことにより,勾配分散低減法(SVRG)の改良を検討する。
計算効率の良いBarzilai-Borwein(BB)法による勾配の分散をSVRGに組み込むことにより低減することを提案する。
線形収束定理は,提案手法だけでなく,2次情報を持つSVRGの既存変種に対しても有効である。
論文 参考訳（メタデータ） (2022-08-23T16:38:40Z) - Lazy Queries Can Reduce Variance in Zeroth-order Optimization [34.29567699904557]
LAZOと呼ばれる適応遅延クエリに基づくゼロ階法(ZO)の勾配推定手法を提案する。
LAZOは、古いクエリを司法的に再利用することで、勾配推定のばらつきを減らすことができることを厳格に証明する。
論文 参考訳（メタデータ） (2022-06-14T19:38:51Z) - GroupifyVAE: from Group-based Definition to VAE-based Unsupervised
Representation Disentanglement [91.9003001845855]
他の誘導バイアスを導入しないと、VAEベースの非監視的非絡み合いは実現できない。
グループ理論に基づく定義から導かれる制約を非確率的帰納的バイアスとして活用し,vaeに基づく教師なし不連続に対処する。
提案手法の有効性を検証するために,5つのデータセット上で,vaeベースモデルが最も目立つ1800モデルをトレーニングした。
論文 参考訳（メタデータ） (2021-02-20T09:49:51Z) - Squared $\ell_2$ Norm as Consistency Loss for Leveraging Augmented Data
to Learn Robust and Invariant Representations [76.85274970052762]
元のサンプルと拡張されたサンプルの埋め込み/表現の距離を規則化することは、ニューラルネットワークの堅牢性を改善するための一般的なテクニックである。
本稿では、これらの様々な正規化選択について検討し、埋め込みの正規化方法の理解を深める。
私たちが特定したジェネリックアプローチ(squared $ell$ regularized augmentation)は、それぞれ1つのタスクのために特別に設計されたいくつかの手法より優れていることを示す。
論文 参考訳（メタデータ） (2020-11-25T22:40:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。