論文の概要: On Exact Sampling in the Two-Variable Fragment of First-Order Logic

• arxiv url: http://arxiv.org/abs/2302.02730v2
• Date: Sat, 6 May 2023 13:43:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-09 23:10:12.952747
• Title: On Exact Sampling in the Two-Variable Fragment of First-Order Logic
• Title（参考訳）: 一階論理の2変数フラッグメントにおける特殊サンプリングについて
• Authors: Yuanhong Wang, Juhua Pu, Yuyi Wang, and Ond\v{r}ej Ku\v{z}elka
• Abstract要約: ドメインサイズで時間内に実行される$mathbfFO2$のサンプリングアルゴリズムが存在することを示す。 提案手法は構築的であり,得られたサンプリングアルゴリズムは様々な領域に応用できる可能性がある。
• 参考スコア（独自算出の注目度）: 8.784424696800214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the sampling problem for first-order logic proposed recently by Wang et al. -- how to efficiently sample a model of a given first-order sentence on a finite domain? We extend their result for the universally-quantified subfragment of two-variable logic $\mathbf{FO}^2$ ($\mathbf{UFO}^2$) to the entire fragment of $\mathbf{FO}^2$. Specifically, we prove the domain-liftability under sampling of $\mathbf{FO}^2$, meaning that there exists a sampling algorithm for $\mathbf{FO}^2$ that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of counting constraints, such as $\forall x\exists_{=k} y: \varphi(x,y)$ and $\exists_{=k} x\forall y: \varphi(x,y)$, for some quantifier-free formula $\varphi(x,y)$. Our proposed method is constructive, and the resulting sampling algorithms have potential applications in various areas, including the uniform generation of combinatorial structures and sampling in statistical-relational models such as Markov logic networks and probabilistic logic programs.
• Abstract（参考訳）: 本稿では、wangらによって最近提案された一階述語論理のサンプリング問題について述べる。 -- 有限領域上の与えられた一階文のモデルを効率的にサンプルする方法? 2変数論理 $\mathbf{FO}^2$$$\mathbf{UFO}^2$) の普遍的に定式化された部分集合に対して、それらの結果を $\mathbf{FO}^2$ の断片に拡張する。 具体的には、$\mathbf{FO}^2$のサンプリングにより、ドメインサイズの時間多項式で実行される$\mathbf{FO}^2$のサンプリングアルゴリズムが存在することを証明する。 さらに、この結果は、例えば$\forall x\exists_{=k} y: \varphi(x,y)$ and $\exists_{=k} x\forall y: \varphi(x,y)$, for some Quantifier-free formula $\varphi(x,y)$ のような数え上げ制約の存在下でも持続することを示す。 提案手法は構成的であり,結果として得られるサンプリングアルゴリズムは,マルコフ論理ネットワークや確率論理プログラムなどの統計関係モデルにおけるコンビネート構造の一様生成やサンプリングなど,様々な分野において潜在的に応用できる。

関連論文リスト

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。 具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。 本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
  論文  参考訳（メタデータ） (2023-11-22T04:34:09Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
  我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。 凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
  論文  参考訳（メタデータ） (2020-10-07T01:43:07Z)
• Proving Non-Inclusion of B\"uchi Automata based on Monte Carlo Sampling [19.09848789158933]
  B"uchiautoa non-inclusion $mathcalL(mathcalA) notsubseteq mathcalL(mathcalB)$を証明するための具体的なアルゴリズムを提案する。 $mathsfIMC2$は、B"uchiautoaのインクルージョンに対する反例を見つける高速で信頼性の高い方法である。
  論文  参考訳（メタデータ） (2020-07-05T10:17:02Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)

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

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