論文の概要: On the Approximability of Weighted Model Integration on DNF Structures
- arxiv url: http://arxiv.org/abs/2002.06726v3
- Date: Mon, 13 Jul 2020 09:27:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 12:55:01.345674
- Title: On the Approximability of Weighted Model Integration on DNF Structures
- Title（参考訳）: DNF構造上の重み付きモデル積分の近似性について
- Authors: Ralph Abboud, \.Ismail \.Ilkan Ceylan, Radoslav Dimitrov
- Abstract要約: DNF構造上の重み付きモデル積分は、実際には重み関数のクラスに対して近似できることを示す。
我々の近似アルゴリズムは3つのサブルーチンに基づいており、それぞれが弱い(すなわち近似)または強い(すなわち正確な)オラクルとなる。
- 参考スコア（独自算出の注目度）: 13.986963122264632
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Weighted model counting (WMC) consists of computing the weighted sum of all
satisfying assignments of a propositional formula. WMC is well-known to be
#P-hard for exact solving, but admits a fully polynomial randomized
approximation scheme (FPRAS) when restricted to DNF structures. In this work,
we study weighted model integration, a generalization of weighted model
counting which involves real variables in addition to propositional variables,
and pose the following question: Does weighted model integration on DNF
structures admit an FPRAS? Building on classical results from approximate
volume computation and approximate weighted model counting, we show that
weighted model integration on DNF structures can indeed be approximated for a
class of weight functions. Our approximation algorithm is based on three
subroutines, each of which can be a weak (i.e., approximate), or a strong
(i.e., exact) oracle, and in all cases, comes along with accuracy guarantees.
We experimentally verify our approach over randomly generated DNF instances of
varying sizes, and show that our algorithm scales to large problem instances,
involving up to 1K variables, which are currently out of reach for existing,
general-purpose weighted model integration solvers.
- Abstract（参考訳）: 重み付きモデルカウント(wmc)は、命題公式のすべての充足代入の重み付き和を計算することからなる。
WMCは正確な解法として#P-hardとして知られているが、DNF構造に制限されたときに完全に多項式ランダム化近似スキーム(FPRAS)を認める。
本研究では、重み付きモデル積分(重み付きモデルカウントの一般化)について検討し、命題変数に加えて実変数を含む重み付きモデルカウントの一般化について、以下の疑問を提起する。
近似体積計算と近似重み付きモデルカウントによる古典的結果に基づいて, dnf構造上の重み付きモデル積分を重み付き関数のクラスに対して近似できることを示す。
我々の近似アルゴリズムは3つのサブルーチンに基づいており、それぞれが弱い(すなわち近似的)または強い(正確に)オラクルであり、全ての場合、正確性を保証する。
様々なサイズでランダムに生成されたDNFインスタンスに対する我々のアプローチを実験的に検証し、我々のアルゴリズムが最大1K変数を含む大きな問題インスタンスにスケールすることを示す。
関連論文リスト
- Scaling and renormalization in high-dimensional regression [72.59731158970894]
本稿では,様々な高次元リッジ回帰モデルの訓練および一般化性能の簡潔な導出について述べる。
本稿では,物理と深層学習の背景を持つ読者を対象に,これらのトピックに関する最近の研究成果の紹介とレビューを行う。
論文 参考訳（メタデータ） (2024-05-01T15:59:00Z) - Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。
CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。
CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
論文 参考訳（メタデータ） (2024-02-05T03:25:04Z) - Lifted Algorithms for Symmetric Weighted First-Order Model Sampling [7.007419073974192]
数量化器を用いた一階述語論理の2変数フラグメントのサンプリングにおけるドメインリフト性を証明する。
そして、この結果は、基数制約の存在下においても引き続き持続することを示す。
我々のアルゴリズムは、最先端のWMSサンプリングよりもかなりのマージンで優れています。
論文 参考訳（メタデータ） (2023-08-17T07:40:47Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳（メタデータ） (2022-12-06T12:42:11Z) - Bayesian Learning of Coupled Biogeochemical-Physical Models [28.269731698116257]
海洋生態系の予測モデルは、様々なニーズに使われている。
希少な測定と海洋プロセスの理解が限られているため、かなりの不確実性がある。
候補モデルの空間での処理と新しいモデルの発見を可能にするベイズモデル学習手法を開発した。
論文 参考訳（メタデータ） (2022-11-12T17:49:18Z) - Git Re-Basin: Merging Models modulo Permutation Symmetries [3.5450828190071655]
提案手法は,大規模ネットワークに適合する簡単なアルゴリズムを実例で示す。
我々は、独立に訓練されたモデル間のゼロモード接続の最初のデモ(私たちの知る限り)を実演する。
また、線形モード接続仮説の欠点についても論じる。
論文 参考訳（メタデータ） (2022-09-11T10:44:27Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - Post-mortem on a deep learning contest: a Simpson's paradox and the
complementary roles of scale metrics versus shape metrics [61.49826776409194]
我々は、ニューラルネットワーク(NN)モデルの一般化精度を予測するために、コンテストで公に利用可能にされたモデルのコーパスを分析する。
メトリクスが全体としてよく機能するが、データのサブパーティションではあまり機能しない。
本稿では,データに依存しない2つの新しい形状指標と,一連のNNのテスト精度の傾向を予測できるデータ依存指標を提案する。
論文 参考訳（メタデータ） (2021-06-01T19:19:49Z) - Collaborative Nonstationary Multivariate Gaussian Process Model [2.362467745272567]
我々は、協調非定常ガウス過程モデル(CNMGP)と呼ばれる新しいモデルを提案する。
CNMGPは、出力が共通の入力セットを共有していないデータを、入力と出力のサイズに依存しない計算複雑性でモデル化することができる。
また,本モデルでは,出力毎に異なる時間変化相関を推定し,予測性能の向上を図っている。
論文 参考訳（メタデータ） (2021-06-01T18:25:22Z) - Measure Theoretic Weighted Model Integration [4.324021238526106]
重み付きモデルカウント(WMC)は、離散的ランダム変数による確率推論を行う一般的なフレームワークである。
近年、WMCは連続変数の追加処理のために重み付けモデル統合(WMI)に拡張されている。
重み付きモデル統合の理論的に健全な測定理論定式化を提案し、連続変数がない場合に重み付きモデルカウントに自然に減少する。
論文 参考訳（メタデータ） (2021-03-25T15:11:11Z) - Generalized Matrix Factorization: efficient algorithms for fitting
generalized linear latent variable models to large data arrays [62.997667081978825]
一般化線形潜在変数モデル(GLLVM)は、そのような因子モデルを非ガウス応答に一般化する。
GLLVMのモデルパラメータを推定する現在のアルゴリズムは、集約的な計算を必要とし、大規模なデータセットにスケールしない。
本稿では,GLLVMを高次元データセットに適用するための新しい手法を提案する。
論文 参考訳（メタデータ） (2020-10-06T04:28:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。