跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2606.23715 · v2

Random coloured digraphs defined by a Markov logic network

由马尔可夫逻辑网络定义的随机着色有向图

首次提交 2026-06-16 19:49
版本更新 2026-11-20 00:36
雷达观测 2026-11-20 12:52
arXiv ↗PDF ↗

摘要

A Markov Logic Network (MLN) MM is a probabilistic relational model used in Statistical Relational Artificial Intelligence for defining a probability distribution PDMP_D^M on the set WDW_D of possible worlds with domain DD for an arbitrary finite domain DD. An MLN consists of first-order formulas, which we call soft constraints, with associated weights which are nonnegative real numbers. The behaviour of the probability distribution, including the effect of the weights, on different domain sizes is poorly understood. We approach the problem in a systematic way by studying sequences (PnM(ψ):n=1,2,3,…)(P_n^M(ψ) : n = 1, 2, 3, \ldots) where ψψ is a first-order sentence and PnM(ψ)P_n^M(ψ) is the probability that ψψ holds in WDW_D where D=[n]:={1,…,n}D = [n] := \{1, \ldots, n\}. We consider a first-order language that can express a property P(x)P(x) and relation R(x,y)R(x, y) and show that all of the following cases can be realized for an MLN MM such that each of its soft constraints is a boolean combination of P(x)P(x), P(y)P(y) and R(x,y)R(x, y) in which both xx and yy appears: For every first-order sentence ψψ, PnM(ψ)P_n^M(ψ) converges to 0 or 1 as n→∞n\to\infty. For every first-order sentence ψψ, PnM(ψ)P_n^M(ψ) converges as n→∞n\to\infty but not necessarily to 0 or 1. There is a first-order sentence ψψ such that PnM(ψ)P_n^M(ψ) does not converge as n→∞n\to\infty. In fact, all three cases can be realized even after fixing the soft constraints and, for any ε>0\varepsilon > 0, by varying their weights by less than ε\varepsilon. We also show that, given any MLN as described above, we can efficiently determine which case it belongs to by inspecting the MLN. Then we show that if the weights are scaled by 1/n1/n then we end up in case~(1) no matter how the weights are chosen.

作者备注:This is a major revision, especially with respect to the exposition, of the first arxiv version

AI 论文解读

基于摘要 · 非全文审阅

研究马尔可夫逻辑网络定义的随机有向图概率随域大小变化的极限行为,并给出判定所属情形的有效方法。

正在读取账号与研究记录…

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-20 00:36 · 最新观测版本

Random coloured digraphs defined by a Markov logic network

A Markov Logic Network (MLN) MM is a probabilistic relational model used in Statistical Relational Artificial Intelligence for defining a probability distribution PDMP_D^M on the set WDW_D of possible worlds with domain DD for an arbitrary finite domain DD. An MLN consists of first-order formulas, which we call soft constraints, with associated weights which are nonnegative real numbers. The behaviour of the probability distribution, including the effect of the weights, on different domain sizes is poorly understood. We approach the problem in a systematic way by studying sequences (PnM(ψ):n=1,2,3,…)(P_n^M(ψ) : n = 1, 2, 3, \ldots) where ψψ is a first-order sentence and PnM(ψ)P_n^M(ψ) is the probability that ψψ holds in WDW_D where D=[n]:={1,…,n}D = [n] := \{1, \ldots, n\}. We consider a first-order language that can express a property P(x)P(x) and relation R(x,y)R(x, y) and show that all of the following cases can be realized for an MLN MM such that each of its soft constraints is a boolean combination of P(x)P(x), P(y)P(y) and R(x,y)R(x, y) in which both xx and yy appears: For every first-order sentence ψψ, PnM(ψ)P_n^M(ψ) converges to 0 or 1 as n→∞n\to\infty. For every first-order sentence ψψ, PnM(ψ)P_n^M(ψ) converges as n→∞n\to\infty but not necessarily to 0 or 1. There is a first-order sentence ψψ such that PnM(ψ)P_n^M(ψ) does not converge as n→∞n\to\infty. In fact, all three cases can be realized even after fixing the soft constraints and, for any ε>0\varepsilon > 0, by varying their weights by less than ε\varepsilon. We also show that, given any MLN as described above, we can efficiently determine which case it belongs to by inspecting the MLN. Then we show that if the weights are scaled by 1/n1/n then we end up in case~(1) no matter how the weights are chosen.

查看此版本解读 →查看此版本原文 ↗