論文の概要: Lifted Algorithms for Symmetric Weighted First-Order Model Sampling

• arxiv url: http://arxiv.org/abs/2308.08828v3
• Date: Fri, 14 Jun 2024 07:39:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-17 20:03:08.314659
• Title: Lifted Algorithms for Symmetric Weighted First-Order Model Sampling
• Title（参考訳）: 対称重み付き一階モデルサンプリングのためのリフテッドアルゴリズム
• Authors: Yuanhong Wang, Juhua Pu, Yuyi Wang, Ondřej Kuželka,
• Abstract要約: 数量化器を用いた一階述語論理の2変数フラグメントのサンプリングにおけるドメインリフト性を証明する。 そして、この結果は、基数制約の存在下においても引き続き持続することを示す。 我々のアルゴリズムは、最先端のWMSサンプリングよりもかなりのマージンで優れています。
• 参考スコア（独自算出の注目度）: 7.007419073974192
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted model counting (WMC) is the task of computing the weighted sum of all satisfying assignments (i.e., models) of a propositional formula. Similarly, weighted model sampling (WMS) aims to randomly generate models with probability proportional to their respective weights. Both WMC and WMS are hard to solve exactly, falling under the $\#\mathsf{P}$-hard complexity class. However, it is known that the counting problem may sometimes be tractable, if the propositional formula can be compactly represented and expressed in first-order logic. In such cases, model counting problems can be solved in time polynomial in the domain size, and are known as domain-liftable. The following question then arises: Is it also the case for weighted model sampling? This paper addresses this question and answers it affirmatively. Specifically, we prove the domain-liftability under sampling for the two-variables fragment of first-order logic with counting quantifiers in this paper, by devising an efficient sampling algorithm for this fragment that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of cardinality constraints. To empirically verify our approach, we conduct experiments over various first-order formulas designed for the uniform generation of combinatorial structures and sampling in statistical-relational models. The results demonstrate that our algorithm outperforms a start-of-the-art WMS sampler by a substantial margin, confirming the theoretical results.
• Abstract（参考訳）: 重み付きモデルカウント(英: Weighted Model counting、WMC)は、命題式の全割り当て(すなわちモデル)の重み付き和を計算するタスクである。 同様に、重み付きモデルサンプリング(WMS)は、それぞれの重みに比例する確率のモデルをランダムに生成することを目的としている。 WMC と WMS はどちらも正確には解けず、$\#\mathsf{P}$-hard complexity class に該当する。 しかし、命題公式をコンパクトに表現し、一階述語論理で表すことができれば、数え上げ問題は時として抽出可能であることが知られている。 そのような場合、モデルカウント問題は、ドメインサイズの時間多項式で解くことができ、ドメインリフト(Domain-liftable)として知られている。 重み付けされたモデルサンプリングについてもそうであるのか? 本稿では,この問題に対処し,肯定的に答える。 具体的には,1次論理の2変数フラグメントを量子化器でサンプリングする際の領域リフト性について,このフラグメントを時間多項式でドメインサイズで効率的にサンプリングするアルゴリズムを考案した。 さらに、この結果は、濃度制約が存在しても引き続き持続することを示す。 提案手法を実証的に検証するために, 組合せ構造を均一に生成し, 統計的関係モデルでサンプリングするために, 様々な一階式について実験を行った。 以上の結果から,本アルゴリズムは最先端のWMSサンプリング器よりも高い性能を示し,理論的結果を確認した。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods [35.24886589614034]
  一般相互作用が$J$である超キューブ上の二次定値イジングモデルを考える。 我々の一般的な結果は、低ランクのIsingモデルに対する最初のサンプリングアルゴリズムを示唆している。
  論文  参考訳（メタデータ） (2022-02-17T21:43:50Z)
• Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
  まず確率分布をモデル化し,そのモデルからサンプリングする。 これらのモデルでは, 少数の評価値を用いて, 高精度に多数の密度を近似することが可能であることが示され, それらのモデルから効果的にサンプルする簡単なアルゴリズムが提示される。
  論文  参考訳（メタデータ） (2021-10-20T12:25:22Z)
• Direct sampling of projected entangled-pair states [0.0]
  投射的絡み合ったペア状態(PEPS)を用いたモンテカルロ変分法(英語版)の研究は、長年の疑問に対する回答を提示できることを最近示した。 本稿では,PEPSから独立したサンプルを生成するサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-15T15:09:20Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)
• On the Approximability of Weighted Model Integration on DNF Structures [13.986963122264632]
  DNF構造上の重み付きモデル積分は、実際には重み関数のクラスに対して近似できることを示す。 我々の近似アルゴリズムは3つのサブルーチンに基づいており、それぞれが弱い(すなわち近似)または強い(すなわち正確な)オラクルとなる。
  論文  参考訳（メタデータ） (2020-02-17T00:29:41Z)
• Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry [16.574508244279098]
  本稿では,重み付き1次モデルカウントを効率的にバウンドする新手法であるApproxWFOMCを提案する。 このアルゴリズムは、様々な一階確率表現を推論する。 本稿では,このアルゴリズムが一階確率モデルにおいて,既存の近似的および高精度な推論手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-01-15T12:21:06Z)

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

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