論文の概要: Lifted Inference beyond First-Order Logic
- arxiv url: http://arxiv.org/abs/2308.11738v3
- Date: Thu, 14 Nov 2024 17:50:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-15 15:21:39.321921
- Title: Lifted Inference beyond First-Order Logic
- Title（参考訳）: 第一次論理を超えたリフテッド推論
- Authors: Sagar Malhotra, Davide Bizzaro, Luciano Serafini,
- Abstract要約: 関係性の一つが有向非巡回グラフ、連結グラフ、木、森である場合、mathrmC2$文はドメインリフト可能であることを示す。
我々の結果は「分割による数え方」という新奇で一般的な方法論に頼っている。
- 参考スコア（独自算出の注目度）: 8.577974472273256
- License:
- Abstract: Weighted First Order Model Counting (WFOMC) is fundamental to probabilistic inference in statistical relational learning models. As WFOMC is known to be intractable in general ($\#$P-complete), logical fragments that admit polynomial time WFOMC are of significant interest. Such fragments are called domain liftable. Recent works have shown that the two-variable fragment of first order logic extended with counting quantifiers ($\mathrm{C^2}$) is domain-liftable. However, many properties of real-world data, like acyclicity in citation networks and connectivity in social networks, cannot be modeled in $\mathrm{C^2}$, or first order logic in general. In this work, we expand the domain liftability of $\mathrm{C^2}$ with multiple such properties. We show that any $\mathrm{C^2}$ sentence remains domain liftable when one of its relations is restricted to represent a directed acyclic graph, a connected graph, a tree (resp. a directed tree) or a forest (resp. a directed forest). All our results rely on a novel and general methodology of "counting by splitting". Besides their application to probabilistic inference, our results provide a general framework for counting combinatorial structures. We expand a vast array of previous results in discrete mathematics literature on directed acyclic graphs, phylogenetic networks, etc.
- Abstract（参考訳）: WFOMC(Weighted First Order Model Counting)は、統計関係学習モデルにおける確率論的推論の基礎である。
WFOMCは一般には難解($P完全)であることが知られているので、多項式時間WFOMCを許容する論理的断片は重要な関心事である。
このようなフラグメントをドメインリフト(Domain liftable)と呼ぶ。
最近の研究は、数量化子(\mathrm{C^2}$)で拡張された一階論理の2変数の断片がドメインリフト可能であることを示した。
しかし、引用ネットワークの非巡回性やソーシャルネットワークの接続性のような現実世界のデータの性質の多くは、$\mathrm{C^2}$でモデル化することはできない。
本研究では、複数の性質を持つ$\mathrm{C^2}$の領域持ち上げ可能性を拡張する。
任意の$\mathrm{C^2}$文は、その関係の1つが有向非巡回グラフ、連結グラフ、木(有向木を参照)または森(有向木を参照)を表すように制限されたときに、ドメインリフト可能であることを示す。
すべての結果は、"分割による数え方"という、新しく一般的な方法論に依存しています。
確率的推論へのそれらの応用に加えて、我々の結果は組合せ構造を数えるための一般的な枠組みを提供する。
我々は、有向非巡回グラフや系統ネットワークなどに関する離散数学の文献において、過去の膨大な成果を拡大する。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
Weak Connectedness PolynomialsとStrong Connectedness Polynomialsを1次論理文に使用する。
既存の公理の全てを抽出可能であることが知られているWFOMCを解くのに使用できる。
論文 参考訳（メタデータ） (2024-07-16T16:01:25Z) - The Quantified Boolean Bayesian Network: Theory and Experiments with a
Logical Graphical Model [0.0]
確率的ネットワークが人間の言語の基礎となる論理的理由を表現するためにどのように構成できるかを示す。
推論では,収束が保証されていないLoopy Belief Propagation (LBP) の使用について検討する。
我々の実験は、LBPが実際に非常に確実に収束していることを示し、我々の分析は、LBPのラウンドが、考慮される変数の数を$N$で制限する時間(O(N2n)$)を必要とすることを示している。
論文 参考訳（メタデータ） (2024-02-09T17:15:45Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - 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) - Lifted Inference with Linear Order Axiom [0.0]
We consider the task of weighted first-order model counting (WFOMC)
我々は、少なくとも2つの論理変数を持つ論理文の WFOMC が $n$ の時間で実行可能であることを示す。
線形順序でWFOMCをn$で計算できる新しい動的プログラミングベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-02T14:38:01Z) - Efficient Hierarchical Domain Adaptation for Pretrained Language Models [77.02962815423658]
生成言語モデルは、多種多様な一般的なドメインコーパスに基づいて訓練される。
計算効率のよいアダプタアプローチを用いて,ドメイン適応を多種多様なドメインに拡張する手法を提案する。
論文 参考訳（メタデータ） (2021-12-16T11:09:29Z) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳（メタデータ） (2021-10-20T23:46:35Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳（メタデータ） (2020-12-06T03:42:54Z) - Can Graph Neural Networks Count Substructures? [53.256112515435355]
グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。
我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
論文 参考訳（メタデータ） (2020-02-10T18:53:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。