論文の概要: Weighted First Order Model Counting with Directed Acyclic Graph Axioms
- arxiv url: http://arxiv.org/abs/2302.09830v2
- Date: Mon, 8 May 2023 16:01:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 22:49:50.714978
- Title: Weighted First Order Model Counting with Directed Acyclic Graph Axioms
- Title（参考訳）: 有向非巡回グラフ公理を用いた重み付き一階数モデル
- Authors: Sagar Malhotra and Luciano Serafini
- Abstract要約: 多くのSRLにおける確率的推論と学習は、重み付き第一モデルカウント(WFOMC)に還元できる
WFOMCは難解であることが知られている(mathrm#P$ complete)。
我々は,DAG(Directed Acyclic Graph)を除外したフラグメント$mathrmC2$,すなわち公理DAGを表す公理化グラフがドメインリフト可能であることを示す。
- 参考スコア（独自算出の注目度）: 7.766921168069532
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Statistical Relational Learning (SRL) integrates First-Order Logic (FOL) and
probability theory for learning and inference over relational data.
Probabilistic inference and learning in many SRL models can be reduced to
Weighted First Order Model Counting (WFOMC). However, WFOMC is known to be
intractable ($\mathrm{\#P_1-}$ complete). Hence, logical fragments that admit
polynomial time WFOMC are of significant interest. Such fragments are called
domain liftable. Recent line of works have shown the two-variable fragment of
FOL, extended with counting quantifiers ($\mathrm{C^2}$) to be domain-liftable.
However, many properties of real-world data can not be modelled in
$\mathrm{C^2}$. In fact many ubiquitous properties of real-world data are
inexressible in FOL. Acyclicity is one such property, found in citation
networks, genealogy data, temporal data e.t.c. In this paper we aim to address
this problem by investigating the domain liftability of directed acyclicity
constraints. We show that the fragment $\mathrm{C^2}$ with a Directed Acyclic
Graph (DAG) axiom, i.e., a predicate in the language is axiomatized to
represent a DAG, is domain-liftable. We present a method based on principle of
inclusion-exclusion for WFOMC of $\mathrm{C^2}$ formulas extended with DAG
axioms.
- Abstract（参考訳）: 統計的関係学習(SRL)は、一階述語論理(FOL)と確率理論を統合し、関係データの学習と推論を行う。
多くのSRLモデルの確率的推論と学習は、重み付き一階モデルカウント(WFOMC)に還元できる。
しかし、WFOMCは難解であることが知られている("\mathrm{\#P_1-}$ complete")。
したがって、多項式時間 WFOMC を許容する論理的断片は重要な関心事である。
このような断片はドメインリフトと呼ばれる。
最近の一連の作品では、folの2変数の断片が、数量化子($\mathrm{c^2}$)をドメインリフト可能に拡張されている。
しかし、実世界のデータの多くの特性は$\mathrm{c^2}$でモデル化できない。
実際、実世界のデータの多くのユビキタスな性質は、FOLでは耐え難い。
非巡回性は, 引用ネットワーク, 系図データ, 時間データ e.t.c. に見られるような性質の1つである。
ここでは,DAG(Directed Acyclic Graph)の公理を持つフラグメント$\mathrm{C^2}$,すなわち,言語内の述語がDAGを表すために公理化され,ドメインリフト可能であることを示す。
DAG公理で拡張された$\mathrm{C^2}$式に対するWFOMCの包含排除原理に基づく方法を提案する。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。
特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
論文 参考訳（メタデータ） (2024-10-30T10:09:05Z) - Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
Weak Connectedness PolynomialsとStrong Connectedness Polynomialsを1次論理文に使用する。
既存の公理の全てを抽出可能であることが知られているWFOMCを解くのに使用できる。
論文 参考訳（メタデータ） (2024-07-16T16:01:25Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Lifted Inference beyond First-Order Logic [8.577974472273256]
関係性の一つが有向非巡回グラフ、連結グラフ、木、森である場合、mathrmC2$文はドメインリフト可能であることを示す。
我々の結果は「分割による数え方」という新奇で一般的な方法論に頼っている。
論文 参考訳（メタデータ） (2023-08-22T18:58:21Z) - 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) - Diffusion Models for Causal Discovery via Topological Ordering [20.875222263955045]
emphTopological ordering approachは、グラフ空間ではなく置換を探索することによって因果発見の最適化空間を減少させる。
ANMsの場合、データログのようなemphHessianは、葉ノードを因果グラフで見つけるのに使用することができ、トポロジ的順序付けを可能にする。
ニューラルネットワークを再トレーニングすることなく、学習したヘッセンを更新する理論を導入し、サンプルのサブセットによる計算が注文の正確な近似を与えることを示す。
論文 参考訳（メタデータ） (2022-10-12T13:36:29Z) - Learning from aggregated data with a maximum entropy model [73.63512438583375]
我々は,観測されていない特徴分布を最大エントロピー仮説で近似することにより,ロジスティック回帰と類似した新しいモデルが,集約データからのみ学習されることを示す。
我々は、この方法で学習したモデルが、完全な非凝集データでトレーニングされたロジスティックモデルに匹敵するパフォーマンスを達成することができるという、いくつかの公開データセットに関する実証的な証拠を提示する。
論文 参考訳（メタデータ） (2022-10-05T09:17:27Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - Weighted Model Counting in the two variable fragment with Cardinality
Constraints: A Closed Form Formula [7.766921168069532]
重み付き一階モデルカウント(WFOMC)は、与えられた有限領域上の一階理論のモデルの重み付き和を計算する。
WFOMCの推論を定式化するためのツールとして,リフト解釈の概念を導入する。
次に、この閉形式を拡張して、存在量化器と濃度制約をドメインリフト性を失うことなく組み込む。
論文 参考訳（メタデータ） (2020-09-25T13:50:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。