马尔可夫逻辑网的域大小渐近行为

《Artificial Intelligence》：Domain size asymptotics for Markov logic networks

　　

马尔可夫逻辑网（MLN）M确定了一个在结构（即“可能世界”）集合Wn上的概率分布PnM，其中结构的域为{1,…,n}。本研究考察了当n趋于无穷时此类分布的属性。 研究表明，在一个带有任意正权重的单一软约束的MLN M满足温和假设的条件下，对于所有充分大的n，分布PnM的表现将与Wn上的均匀分布Pnuni截然不同。 研究人员证明，对于每个至少包含一个一元关系符号的语言，量化自由的MLN与提升贝叶斯网络（LBN）在以下意义上是不可比较的：(a) 存在一个量化自由的MLN M，使得对于每一个LBN G，若n充分大，则M和G在Wn上确定不同的分布。(b) 存在一个LBN G，使得对于每一个量化自由的MLN M，若n充分大，则G和M在Wn上确定不同的分布。 对于一个仅含有一个一元关系符号R的语言，以及任意量化自由的MLN M，研究人员描述了当n→∞时，关于满足R(x)的元素的最可能分布，PnM的渐近行为。由此可知，此类MLN的软约束和权重决定了分布序列的渐近行为。 已知若Mw是一个带有一个一致软约束φ(x1,…,xk)（权重为w）的MLN，则对每个固定的n，有limw→∞ PnMw(?x1,…,xk φ(x1,…,xk))=1。研究人员证明，若k≥3且φ(x1,…,xk)表达x1并未连接到所有x2,…,xk，则对每个固定的w≥0，有limn→∞ PnMw(?x1,…,xk φ(x1,…,xk))=0。因此，在极限情况下，权重维度和域大小维度可能表现出完全不同的行为。

1. 研究背景与问题

在人工智能领域，常需处理对象、属性及其关系，并结合逻辑推理与概率不确定性。统计关系AI（SRAI）旨在融合一阶逻辑的知识表示能力与概率论处理不确定性的方法。然而，传统逻辑框架无法处理不确定性，而纯概率方法缺乏对来自任意未指定域的对象间关系和属性的原则性知识表示方式。为解决此问题，研究者提出了提升概率图模型（LPGM），如马尔可夫逻辑网（MLN）和提升贝叶斯网络（LBN）。这些模型能在不同大小的有限域上定义概率分布，但其关键在于能否实现跨域的知识迁移——即从一个域学习到的参数和结构能否有效应用于另一个域。现有研究表明，某些MLN在大域上其数值参数对重要事件概率的影响会变得微不足道，导致学得的权重失去意义，这严重阻碍了知识的泛化与推理的可扩展性。尽管有向LPGM（如LBN）在知识迁移方面表现更佳，但无向LPGM（如MLN）能够描述循环概率依赖，例如某个体患流感的概率依赖于其他个体的患病情况。因此，深入理解MLN随域大小变化的渐近行为，对于评估其在学习和推理中的适用性至关重要。

2. 研究目标与方法

本研究旨在系统分析MLN所确定的概率分布在域大小趋于无穷时的渐近性质。研究人员采用的主要关键技术方法包括：

• •
  马尔可夫逻辑网（MLN）的形式化定义与概率分布建模：将MLN定义为带有非负权重的软约束集合，并通过指数函数基于各软约束在结构中满足的元组数量定义势函数，从而在可能世界集上建立概率分布。
• •
  渐近持久性与大偏差理论的应用：利用已有定理（结合文献[30]和[29]的结果）判定公式是否渐近持久，并推导出在均匀分布下，大多数结构满足特定公式的比例高度集中于某个常数附近，且偏离概率呈指数衰减。
• •
  量化自由MLN的规范化转换：提出引理表明，任意量化自由MLN均可转化为一种等价的正规形式，该形式由一组互斥且穷举的最大一致合取式及其权重构成，便于后续分析与比较。
• •
  与提升贝叶斯网络（LBN）的表达性对比：通过构造具体的MLN和LBN实例，严格证明在一阶语言背景下两者在定义分布族的能力上是不可比较的。

3. 主要研究结果

3.1. MLN与均匀分布的对比

研究表明，只要MLN包含一个满足温和条件（如软约束与其否定均渐近持久）的正权重软约束，则由该MLN确定的分布P_n^M与均匀分布P_n^uni在渐近意义上行为完全相反。具体地，存在一系列子集X_n?W_n，使得lim_n→∞ P_n^M(X_n)=1，而lim_n→∞ P_n^uni(X_n)=0。这意味着即使权重极小，MLN也会迫使几乎所有可能世界拥有极多（或极少）满足软约束的元组，与均匀分布下绝大多数结构集中在中等比例附近的特性截然不同。

3.2. MLN与LBN的不可比较性

针对至少包含一个一元关系符号的语言，研究人员证明了量化自由MLN与LBN在表达力上不可比较。一方面，存在一个量化自由MLN，其定义的分布序列无法被任何LBN复制；另一方面，也存在一个LBN，其定义的分布序列无法被任何量化自由MLN复制。这一结果首次将命题逻辑中马尔可夫网络与贝叶斯网络的不可比较性推广到了一阶逻辑语境。

3.3. 一元关系下MLN的渐近行为刻画

对于仅含一个一元关系符号R的语言，研究人员完整描述了任意量化自由MLN M所确定的分布P_n^M的渐近行为。结果表明，随着n→∞，满足R(x)的元素比例几乎必然收敛到某个由MLN的软约束权重唯一确定的值。换言之，MLN的权重完全决定了分布序列的极限行为，并且该极限可通过少量计算资源预测。

3.4. 权重与域大小维度的分离效应

研究揭示了一个令人惊讶的现象：对于形如“x₁未连接到所有x₂,…,x_k”（k≥3）的软约束，固定域大小时，增大权重会使全称量化公式的概率趋近于1；但固定权重时，增大域大小却使该概率趋近于0。这表明权重维度和域大小维度在极限情况下可以完全独立甚至反向作用，凸显了MLN在跨域应用中的潜在风险。

4. 总结与结论

本研究系统揭示了MLN随域大小变化的复杂渐近行为。主要结论包括：正权重软约束会导致MLN分布与均匀分布在渐近上彻底分化；量化自由MLN与LBN在一阶逻辑下表达力不可比较；对于一元关系语言，MLN的权重唯一决定其渐近行为；权重与域大小对全称公式概率的影响可能完全相反。这些发现不仅深化了对MLN理论特性的理解，也为实际应用中如何选择或调整模型提供了重要警示：简单地在一个域上学得MLN权重并期望其在大域上保持有效性可能是不合理的。研究同时指出，现有的一些重缩放方法（如自适应MLN或域大小感知MLN）虽试图解决此问题，但在一般情形下仍无法保证权重在极限中持续发挥影响，因此探索更合理且通用的重缩放策略仍是未来研究的重要方向。