arXiv:2509.04192cs.AIcs.LO2025-09被引 1

研究马尔可夫逻辑网络在大域下的概率分布行为,揭示其与均匀分布的本质差异。

Domain size asymptotics for Markov logic networks

  • 分析MLN在领域规模趋于无穷时的概率分布渐近特性
  • 证明含一元关系的MLN分布会显著偏离均匀分布
  • 揭示MLN与提升贝叶斯网络在无限域下无法等价

马尔可夫逻辑网络(MLN)$ℝ$ 在领域 $ℝ \{1, …, n\}$ 上定义了一个结构集合 $ℝ_n$(即“可能世界”)上的概率分布 $ℝ_n^ℝ$。本文研究当 $n \to \infty$ 时该分布的性质。在对一个具有任意正权重的软约束施加弱假设的前提下,我们证明对于所有足够大的 $n$,分布 $ℝ_n^ℝ$ 与 $ℝ_n^{uni}$(即 $ℝ_n$ 上的均匀分布)的行为将截然不同。针对仅含一个一元关系符号 $R$ 的语言,我们给出了 $ℝ_n^ℝ$ 在 $n \to \infty$ 时几乎所有可能渐近行为的完整刻画,其中 $ℝ$ 可为该语言的任意MLN。该渐近行为取决于MLN的软约束及其权重。利用此刻画,我们证明:若所考虑的语言中至少包含一个一元关系符号,则 (a) 存在一个MLN $ℝ$,使得对任意提升贝叶斯网络(LBN)$ℝ$,都存在无穷多个 $n$,使得 $ℝ$ 与 $ℝ$ 在 $ℝ_n$ 上诱导不同的分布;(b) 存在一个LBN $ℝ$,使得对任意MLN $ℝ$,都存在无穷多个 $n$,使得 $ℝ$ 与 $ℝ$ 在 $ℝ_n$ 上诱导不同的分布。此外,我们还表明,在极限情况下,权重维度与域大小维度的行为可能完全不同。

原文摘要 · Abstract (English)

A Markov logic network (MLN) $\mathbb{M}$ determines a probability distribution $\mathbb{P}_n^\mathbb{M}$ on the set $\mathbf{W}_n$ of structures, or ``possible worlds'', with domain $\{1, \ldots, n\}$. We study the properties of such distributions as $n$ tends to infinity. We show that with mild assumptions on an MLN $\mathbb{M}$ with one soft constraint with an arbitrary positive weight the distribution $\mathbb{P}_n^\mathbb{M}$ will behave quite differently from the uniform distribution $\mathbb{P}_n^{uni}$ on $\mathbf{W}_n$ for all sufficiently large $n$. For a language with only one relation symbol $R$ which has arity 1 we give an almost complete characterization of the possible asymptotic behaviours of $\mathbb{P}_n^\mathbb{M}$ as $n \to \infty$, where $\mathbb{M}$ may be any MLN for this language. The asymptotic behaviour depends on the soft constraints and weights of the MLN. This characterization is used to show that if the language under consideration contains at least one relation symbol of arity 1 then the following holds: (a) There is an MLN $\mathbb{M}$ such that for every lifted Bayesian network (LBN) $\mathbb{G}$ there are infinitely many $n$ such that $\mathbb{M}$ and $\mathbb{G}$ determine different distributions on $\mathbf{W}_n$. (b) There is an LBN $\mathbb{G}$ such that for every MLN $\mathbb{M}$ there are infinitely many $n$ such that $\mathbb{G}$ and $\mathbb{M}$ determine different distributions on $\mathbf{W}_n$. We also show that, in the limit, the weight dimension and the domain size dimension may behave completely differently.

马尔可夫逻辑概率推理渐近分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。