論文の概要: Lifted Inference with Linear Order Axiom

• arxiv url: http://arxiv.org/abs/2211.01164v1
• Date: Wed, 2 Nov 2022 14:38:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-03 13:56:15.547877
• Title: Lifted Inference with Linear Order Axiom
• Title（参考訳）: 線形次公理を用いたリフト推論
• Authors: Jan T\'oth, Ond\v{r}ej Ku\v{z}elka
• Abstract要約: We consider the task of weighted first-order model counting (WFOMC) 我々は、少なくとも2つの論理変数を持つ論理文の WFOMC が $n$ の時間で実行可能であることを示す。 線形順序でWFOMCをn$で計算できる新しい動的プログラミングベースアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of weighted first-order model counting (WFOMC) used for probabilistic inference in the area of statistical relational learning. Given a formula $\phi$, domain size $n$ and a pair of weight functions, what is the weighted sum of all models of $\phi$ over a domain of size $n$? It was shown that computing WFOMC of any logical sentence with at most two logical variables can be done in time polynomial in $n$. However, it was also shown that the task is $\texttt{#}P_1$-complete once we add the third variable, which inspired the search for extensions of the two-variable fragment that would still permit a running time polynomial in $n$. One of such extension is the two-variable fragment with counting quantifiers. In this paper, we prove that adding a linear order axiom (which forces one of the predicates in $\phi$ to introduce a linear ordering of the domain elements in each model of $\phi$) on top of the counting quantifiers still permits a computation time polynomial in the domain size. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time polynomial in $n$, thus proving our primary claim.
• Abstract（参考訳）: 本稿では,統計関係学習分野における確率的推論に用いる重み付き一階モデルカウント(WFOMC)の課題について考察する。 公式の$\phi$、ドメインサイズ$n$、ウェイト関数のペアを与えられた場合、すべてのモデルの$\phi$の重み付き和は、サイズ$n$? 最小2つの論理変数を持つ任意の論理文の WFOMC を時間多項式で$n$で計算できることが示されている。 しかし、第3変数を追加すると、タスクは$\texttt{#}p_1$-completeであることが示され、これは2変数のフラグメントの拡張を探索し、実行時の多項式を$n$で許すことになった。 そのような拡張の1つは、数量化子を持つ2変数の断片である。 本稿では,数量化器上に線形順序公理($\phi$ の述語のうちの1つに$\phi$ の各モデルにおける領域要素の線形順序付けを強制する)を加えることで,計算時間多項式の領域サイズの計算が可能となることを証明する。 我々は,WFOMCを時間多項式の線形順序で$n$で計算できる,動的プログラミングに基づく新しいアルゴリズムを提案する。

関連論文リスト

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
  Weak Connectedness PolynomialsとStrong Connectedness Polynomialsを1次論理文に使用する。 既存の公理の全てを抽出可能であることが知られているWFOMCを解くのに使用できる。
  論文  参考訳（メタデータ） (2024-07-16T16:01:25Z)
• Lifted Inference beyond First-Order Logic [8.577974472273256]
  関係性の一つが有向非巡回グラフ、連結グラフ、木、森である場合、mathrmC2$文はドメインリフト可能であることを示す。 我々の結果は「分割による数え方」という新奇で一般的な方法論に頼っている。
  論文  参考訳（メタデータ） (2023-08-22T18:58:21Z)
• Weighted First Order Model Counting with Directed Acyclic Graph Axioms [7.766921168069532]
  多くのSRLにおける確率的推論と学習は、重み付き第一モデルカウント(WFOMC)に還元できる WFOMCは難解であることが知られている(mathrm#P$ complete)。 我々は,DAG(Directed Acyclic Graph)を除外したフラグメント$mathrmC2$,すなわち公理DAGを表す公理化グラフがドメインリフト可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-20T08:35:13Z)
• On Exact Sampling in the Two-Variable Fragment of First-Order Logic [8.784424696800214]
  ドメインサイズで時間内に実行される$mathbfFO2$のサンプリングアルゴリズムが存在することを示す。 提案手法は構築的であり,得られたサンプリングアルゴリズムは様々な領域に応用できる可能性がある。
  論文  参考訳（メタデータ） (2023-02-06T12:15:41Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• On polynomially many queries to NP or QMA oracles [0.0]
  本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。 まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。 次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
  論文  参考訳（メタデータ） (2021-11-03T15:29:01Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T22:51:52Z)

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

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