统计关系学习(Statistical relational learning)

发表于 2025/07/16

作者 Joker

90 分钟阅读

统计关系学习（Statistical Relational Learning, SRL）是人工智能与机器学习的一个子领域，专注于既具备不确定性（可通过统计方法处理），又具有复杂关系结构的领域模型。通常，SRL 中开发的知识表示形式会使用一阶逻辑（的一部分）来以通用方式（普遍量化）描述领域中的关系特性，同时运用概率图模型（如贝叶斯网络或马尔可夫网络）来处理不确定性；有些方法还借鉴了归纳逻辑编程的技术。自 20 世纪 90 年代末以来，该领域取得了显著发展。

一阶逻辑(First-order logic)
一阶逻辑，也称为谓词逻辑、谓词演算或量化逻辑，一阶逻辑使用非逻辑对象的量化变量，并允许使用包含变量的句子。
“一阶”一词区分了一阶逻辑与高阶逻辑，在高阶逻辑中，存在以谓词或函数为参数的谓词，或者允许对谓词、函数或两者进行量化。在一阶理论中，谓词通常与集合相关联。在解释的高阶理论中，谓词可能被解释为集合的集合。
一阶逻辑是数学公理化形式化的标准，并在数学基础中得到研究。皮亚诺算术和策梅洛–弗兰克尔集合论分别是数论和集合论在一阶逻辑中的公理化。然而，没有任何一阶理论具有足够的力量来唯一描述具有无限域的结构，例如自然数或实数线。要完全描述这两种结构，即分类公理系统，可以在更强的逻辑中，如二阶逻辑中，获得这样的公理系统。
进一步的，下面给出一阶逻辑及其组分的示例

考虑两个句子“苏格拉底是一位哲学家”和“柏拉图是一位哲学家”。在命题逻辑中，这些句子本身被视为研究的个体，例如可以用变量 p 和 q 来表示。它们不被视为对论域中任何特定对象的谓词应用，而是被视为纯粹是陈述句，要么为真要么为假。然而，在一阶逻辑中，这两个句子可以被表述为某个特定个体或非逻辑对象具有某种属性的陈述。在这个例子中，两个句子碰巧具有对某个个体$\text{isPhil}(x)$ 。在第一个句子中，变量 x 的值为“苏格拉底”，在第二个句子中为“柏拉图”。由于能够谈论非逻辑个体以及原始的逻辑连接词，一阶逻辑包含了命题逻辑。

一个公式如“x 是一个哲学家”的真值取决于 x 所表示的对象以及谓词“是一个哲学家”的解释。因此，“x 是一个哲学家”本身没有确定的真或假值，类似于一个句子片段。 [8] 谓词之间的关系可以使用逻辑连接词来陈述。例如，一阶公式“如果 x 是一个哲学家，那么 x 是一个学者”是一个条件语句，其假设为“x 是一个哲学家”，结论为“x 是一个学者”，这同样需要指定 x 才能具有确定的真值。

量词可以应用于公式中的变量。前一个公式中的变量 x 可以被全称量化，例如，用一阶句子“对于每一个 x，如果 x 是一个哲学家，那么 x 是一个学者”。这个句子中的全称量词“对于每一个”表达了“如果 x 是一个哲学家，那么 x 是一个学者”这一主张对所有 x 的选择都成立的思想。

句子”对于每一个 x，如果 x 是哲学家，那么 x 是学者”的否定在逻辑上等价于句子”存在某个 x，使得 x 是哲学家且 x 不是学者”。存在量词”存在”表达了”x 是哲学家且 x 不是学者”这一命题对于某些 x 的选择成立的思想。

谓词”是哲学家”和”是学者”各自取一个变量。通常，谓词可以取多个变量。在一阶句子”Socrates 是 Plato 的老师”中，谓词”是…的老师”取两个变量。

统计关系学习的典型任务包括：

集体分类，即根据对象的属性及其关系（同时）预测多个对象的类别
链接预测，即预测两个或多个对象之间是否存在关联
基于链接的聚类，即将相似对象分组，其中相似性根据对象的链接确定，以及相关的协同过滤任务，即过滤与实体相关的信息（其中，如果已知某信息与相似实体相关，则认为该信息与该实体相关）
对象识别/实体解析/记录链接，即识别两个或多个独立数据库/数据集中的等价条目
社交网络建模

需要进一步拓展的内容包括：

关系马尔可夫网络与马尔可夫逻辑网络
关系贝叶斯网络与贝叶斯逻辑程序
概率关系模型(PRMs)与概率关系图
概率软逻辑与概率逻辑编程

关系马尔可夫网络与马尔可夫逻辑网络

关系马尔可夫网络

框架基础：一个基于无向图的概率建模框架

关系马尔可夫网络可能解决的问题：

实现文档的关联分类：考虑一个我们想要使用一组标签进行分类的超文本文档集合。最直观的方法是使用词袋模型。然而，这种方法完全忽略了超文本的丰富结构。一个文档会链接到其他文档，通常表明它们的主题相关；每个文档还具有内部结构。在分类文档集合时，这些线索是重要的，可能有助于我们实现更高的分类准确率。因此，我们不是单独分类每个文档，而是希望提供一种集体分类的形式，即在同时决定所有实体的类别标签，从而可以明确利用相关实体标签之间的相关性。
预测实体间关联关系：一个挑战来自于预测哪些实体与哪些其他实体相关联，以及这些关系的类型。例如，在一个包含一组超链接大学网页的数据集中，我们不仅可能想要预测哪些页面属于教授，哪些属于学生，还可能想要预测哪些教授是哪些学生的导师。在某些情况下，关系的存在将通过页面之间的超链接来预测，我们只需决定该链接是否反映了导师-学生关系。在其他情况下，我们可能需要从间接证据中推断链接的存在，例如大量合著的论文。

关系马尔可夫网络中的关系分类

模式定义一组实体类型：$E={ E_1,\cdots,E_n }$，其具有如下三组属性

内容属性(content attributes)：$E.\bf{X}$
标签属性(label attributes)：$E.\bf{Y}$
引用属性(reference attributes)：$E.\bf{R}$，其包含唯一键属性$E.\bf{K}$用于识别每个实体；其他类型的实体指向单一类型实体$E=Range(E.\bf{R})$，其值在$Domain(E.\bf{K})$中

模式E的实例I指定了每个实体类型$E∈\epsilon$的实体集合$I(E)$，示例$I$同样包括${I.\bf{X}},{I,\bf{Y}},{I.\bf{R}}$，这些属性的值用$I.x,I.y,I.r$表示；其中$I.r$被称为实例骨架(nstantiation skeleton / instantiation graph)，指定实体(节点)集合及其引用属性(边)

案例
假设实体类型集合包括WebPage、Author，那么对应的实例化 I 中会有：I(WebPage)：如 {page1, page2, page3}，I(Author)：如 {Alice, Bob}，作者 Alice 的属性，比如姓名、学科领域等，可设作 I.x(Alice)、I.y(Alice)、I.r(Alice)（如 co-author 的链接关系）
每个实体拥有属性包括网页 page1 的内容（X），标签（Y），及链接（R）：

$I.x(page1)$ = 一篇网页的单词内容

$I.y(page1)$ = 分类标签（如“新闻”）

$I.r(page1)$ = 链向的其它网页（如 {page2, page3}）

同时，在概率关系模型中也需要把“链接”也当作模型里的一等公民，引入结构不确定性（Structural Uncertainty）以便做链接预测（Link Prediction）。假设连接$l$表示实体${ o_i,o_j }$之间的连接，则$l.Exists$表示该链接存在，反之表示不存在；引入结构不确定性的模型可以预测链接是否应存在，并将这种结构作为条件用来提升属性预测准确率，其是建模的核心策略之一。

关系马尔可夫网络的图结构和子图模板

利用概率关系模型(PRMs)对实体进行建模，可以诱导出大型贝叶斯网络，在实体属性间建立依赖。

例如在$Doc.Label$和$Doc.HasWord$之间建立链接，则二者间会关联一个条件概率分布$P(Doc.HasWord| Doc.Label)$。

同时，可以将关系语言和概率图模型结合为建模关系图，该方法具有灵活和关系易展现等优势。

一些完善子图模板的方式：

可以引入更丰富的子图模板，如相似性模板，即共享某种基于土属性的对象更有可能具有相同标签
可以引入对传递模式的研究，即存在A-B链接和B-C链接会增加(或减少)A-C链接的可能性，这种三元依赖只能用无向图建模，并通过 clique 直接表达

但是要实现上述内容，概率依赖图因其必须是定向无环图的约束难以实现，而使用无向马尔科夫网络作为网络则良好解决了该问题

关系马尔可夫网络的定义与设置

第一阶段：原始概率定义

记呈现出的马尔可夫网络为图$G$，其节点集则为$V$，节点集的真子集被称为团$V_{c}$，团内$V_{i},V_{j}$间有边相连。

令$G=(V,E)$为包含团簇$C(G)$的无向图，每个$c \in C(G)$都与一个节点集$V$和一个团势$\phi(V)$相关联，$\phi(V)$在$V$的联合域中非负，$\phi={\phi(V)}$，分布： $P(v)=\frac{1}{Z} \Pi_{c \in C(G)}\phi_{c}({\bf{v_c}})$

其中规范化常数: $Z=\sum_{v'}\Pi_{c \in C(G)}\phi_{c}({\bf{v'_c}})$

每个势函数$\phi_c$可视为一个“不归一化”的表格，衡量给定团内各变量赋值组合的兼容性，表达式为: $\phi_c(v_c)=exp\{ \sum\limits_{i}w_i f_i({\bf{v_c}}) \}=exp\}\}$

其联合分布写作： $logP({\bf{v}})=\sum\limits_{c}{\bf{w_c \cdot f_c(v_c)}}-logZ={\bf{w \cdot f(v)}}-logZ$

其中各参量的含义为：

$\bf{f}$：逻辑或行为函数，指示特定局部模式是否发生
$\bf{w}$：表示该模式对概率的促进或抑制程度

第二阶段：条件概率定义

设$X$为条件随机变量，$Y$为目标(标签)随机变量，条件马尔可夫网络定义了条件分布：

\[P(y|x)=\frac{1}{Z(x)}\Pi_{c \in C(G)}\phi({\bf{x_c,y'_c}})\]

其中：

\[Z(x)=\sum_{\bf{y'}}\phi(\bf{x_c,y'_c})\]

与传统马尔可夫网络建模联合分布 $P(x,y)$ 不同，条件马尔可夫网络直接建模的是 $P(y∣x)$，这种判别式建模只关注标签 $Y$ 在观测到 $X$ 情况下的分布，不试图生成 $X$，适用于分类任务且通常具有更好性能

第三阶段：结构化查询定义

定义关系团模板$C=(F,W,S)$，其中：

F(From)：一组实体变量${ F_i }$，每个带类型$E(F_i)$
W(where)：一个布尔条件，由比较实体键($.R$ 属性)构成，筛选出“真实相连”的实体组合
S(Select)：从这些实体中选出的属性集合(内容$X$或标签$Y$)，构成团内的随机变量

进一步的，经过下面几个步骤，可从关系团模板到实例化团：

实体交叉：$I(F)=I(E(F_1)) \times \cdots \times I(E(F_n))$
筛选：只保留满足W条件的实体元组$f=(f_1,\cdots,f_n)$，表示为$W(F.R)$作为若干等式或不等式的布尔集合
投影：对每个保留的元组，取出在$S$中指定的属性值，形成一个团的实例$c=f.S={ f_i,A:A \in S }$
集合化：所有这样的$c$构成改模板在$I$上的团集合$C(I)$

例如下述代码案例为共同来源三元模板：
1 2 3 4 5 FROM Doc AS doc1, Doc AS doc2, Link AS l1, Link AS l2 WHERE l1.From = l2.From AND l1.To = doc1.Key AND l2.To = doc2.Key AND doc1.Key <> doc2.Key
其对应的$W$为：$(l_1.From=l_2.From) \land (l_1.To=doc_1.Key) \land (l_2.To=doc_2.Key) \land (doc_1.Key \neq doc_2.Key)$

第四阶段：RMN完整的计算构造与实例化

一个 关系马尔可夫网络 (RMN) $M = (\mathcal{C}, \Phi)$ 包含：

$\mathcal{C}$：一组关系团模板。
$\Phi = {\phi_C}_{C \in \mathcal{C}}$：每个模板对应的团势函数。

给定一个实例化 $I$（包含内容属性 $I.x$、关系骨架 $I.r$ 和待预测标签 $I.y$），RMN 定义条件分布：

\[P\bigl(I.y \mid I.x, I.r\bigr) \;=\; \frac{1}{Z\bigl(I.x, I.r\bigr)} \;\prod_{C\in\mathcal{C}} \;\prod_{c\in C(I)} \phi_C\bigl(I.x_c, I.y_c\bigr),\]

其中归一化常数（分区函数）为：

\[Z\bigl(I.x, I.r\bigr)= \sum_{I.y'} \;\prod_{C\in\mathcal{C}} \;\prod_{c\in C(I)} \phi_C\bigl(I.x_c, I.y'_c\bigr).\]

若采用对数线性参数化$\displaystyle \phi_C(v_c) = \exp{\,w_C \cdot f_C(v_c)}$，则可写为：

\[\log P\bigl(I.y \mid I.x, I.r\bigr)= \sum_{C\in\mathcal{C}} \sum_{c\in C(I)} w_C \!\cdot\! f_C\bigl(I.x_c, I.y_c\bigr) \;-\; \log Z\bigl(I.x, I.r\bigr).\]

定义实例化特征：

\[f_C\bigl(I.x, I.y, I.r\bigr)= \sum_{c\in C(I)} f_C\bigl(I.x_c, I.y_c\bigr),\]

记 $w$ 和 $f$ 为所有 $w_C$ 与 $f_C$ 的拼接向量，则有：

\[\log P\bigl(I.y \mid I.x, I.r\bigr)= w \!\cdot\! f\bigl(I.x, I.y, I.r\bigr) \;-\; \log Z\bigl(I.x, I.r\bigr).\]

其中一些关键参量的定义包括：

模板集合$\mathcal{C}$：提前定义好“在哪些局部子图上插入潜势”，例如“每条链接上的两个文档标签”“同一来源的三元组”等
实例化团集合$C(I)$：对每个模板$C$，用前面定义的关系查询在骨架$I.r$上找到所有匹配的子图，得到具体的团$c$
特征函数$f_C$：关系马尔可夫网络中用来量化“局部配置偏好”的基本构件，其将团中每一种可能的变量取值组合$v_C=(v_{i1},\cdots,v_{ik})$映射为一个实数

实际案例
定义一个检测“链接页标签相同”模式的团模板
1 2 3 4 SELECT doc1.Category, doc2.Category FROM Doc AS doc1, Doc AS doc2, Link AS link WHERE link.From = doc1.Key AND link.To = doc2.Key
团模板$C$捕获每条超链接对应的一对文档标签，团变量 $V_C = { Y_1, Y_2 }$，其中$Y_1 = doc_1.Category，Y_2 = doc_2.Category$
然后可以定义两个特征函数：$f_C^{same}:{ 标签 }^2 \to { 0,1 }$，即当$y_1=y_2$时特征取1否则取0，使模型会偏好将相连页面标为同一类别；$f_C^{sim}:{ 标签 }^2 \to R$，写作$f_C^{sim}=|w_1 \cap w_2|$，其中$w_1$为$doc_1$中单词集合，$w_2$为$doc_2$中单词集合$f_C^{sim}$返回它们交集的大小，使共享单词越多时特征值越大
进而利用潜势函数进行计算

第五阶段：基于关系马尔可夫网络的学习模型

假设已知关系团模板集合 $\mathcal{C}$，我们需要估计对应的潜势函数参数（或特征权重）$w$。给定训练集 $D$（其中内容属性 $I.x$ 和标签 $I.y$ 都已观测），我们的目标是：

定义目标函数
- 极大似然（ML）：最大化标签在给定内容和结构下的联合概率
  $L_{\rm ML}(w) = \sum_{d\in D}\log P_w(y_d\mid x_d) = \sum_{d}\bigl[w\!\cdot\!f(x_d,y_d)-\log Z(x_d)\bigr].$
- 最大后验（MAP）：加入零均值高斯先验 $p(w_i)\propto\exp(-w_i^2/2\sigma^2)$，防止过拟合
  $L_{\rm MAP}(w) = \sum_{d}\bigl[w\!\cdot\!f(x_d,y_d)-\log Z(x_d)\bigr] - \frac{\|w\|^2}{2\sigma^2} + C.$
计算梯度
- 对于平坦(i.i.d.)情况： $\nabla L(w) = \sum_{d\in D}\Bigl[f(x_d,y_d)\;-\;\mathbb{E}_{P_w}[\,f(x_d,Y_d)\,]\Bigr] \;-\;\frac{w}{\sigma^2},$ 其中 $\mathbb{E}_{P_w}[f(x_d,Y)] = \sum_{y'} f(x_d,y')\,P_w(y'\mid x_d).$
- 对于关系情况（单个实例化 $I$）： $\nabla L(w) = f(I.y,I.x,I.r)\;-\;\mathbb{E}_{P_w}\bigl[f(I.Y,I.x,I.r)\bigr] \;-\;\frac{w}{\sigma^2},$ 其中 $\mathbb{E}_{P_w}[f(I.Y,I.x,I.r)] = \sum_{I.y'} f(I.y',I.x,I.r)\,P_w(I.y'\mid I.x,I.r).$
优化方法
- 对数‐线性目标函数是凹函数，可用共轭梯度（Conjugate Gradient）或 L‑BFGS 等高效数值优化方法求解。
- 对于 CRF 和 RMN，经验表明 L‑BFGS 收敛更快。
计算期望的难点
- 平坦模型中，各训练样本独立，期望可逐实例分开计算；
- 关系模型中，所有标签相关，需要在展开的巨大马尔可夫网络上运行推断（如 Belief Propagation），才能估计联合期望。

在马尔可夫网络中的推断则可以采用如下流程

目标：计算给定 $x$ 后，各标签变量的后验边缘分布。
方法：
- 对于低树宽图可用精确算法；
- 对于超大稠密图（如超文本分类），采用 Belief Propagation (BP) 进行近似推断：
  - 在任意图上迭代消息传递，经验上即使有循环也往往收敛且结果准确。
  - BP 每次迭代更新节点对邻居的“信念”，直至收敛后读取边缘概率。

流程小结

定义团模板 $\mathcal{C}$

构造对数‐线性目标 $L(w)$（含先验）

重复：

运行 BP 估计 $\mathbb{E}_{P_w}[f]$

用梯度方法更新 $w$

直到收敛

这样即可完成 RMN 的判别式 MAP 学习。

马尔可夫逻辑网络

前一部分关系马尔可夫网络作为概率图模型而存在，而马尔可夫逻辑网络则将关系马尔可夫网络和一阶逻辑作了结合，用于数据库和知识库构建。在上一部分详细讲解了前者，这部分更侧重于梳理一阶逻辑(First Order Logic)，然后以此为起点进入对马尔可夫逻辑网络的阐释。

一阶逻辑(First Order Logic)

一阶知识库(KB)是一阶逻辑中的一组句子/公式，公式使用四种类型的符号构建：常量(constants)、变量(variables)、函数(functions)、谓词(predicates)。

常量(constants)：表示感兴趣领域中的对象，如people:Anna,Bob,Chris
变量(variables)：用于遍历领域中的对象，应该是一类抽象表示
函数(functions)：表示从对象元组到对象元组的映射，如Motherof(Alice)，返回另一个对象（即一个项）
谓词(predicates)：表示领域中对象间的关系或对象的属性，如Friends(Alice,Bob)和Smokes(John)，返回一个真值（True/False），用来构造原子公式
解释(interpretation)：指定了领域中哪些对象、函数和关系由哪些符号表示

备注

变量和常量可以有类型，在这种情况下，变量仅遍历相应类型的对象，常量只能表示相应类型的对象。例如，变量 x 可能遍历人（例如，安娜、鲍勃等），而常量 C 可能表示一个城市（例如，西雅图）

项是任何表示域中对象的表达式，可以是常量、变量或应用于项元组的函数。例如，Anna、x 和 GreatestCommonDivisor(x, y)都是项

原子公式或原子是一个谓词符号应用于项元组（例如，Friends(x, MotherOf(Anna)))

公式通过逻辑连接词和量词递归地从原子公式构造而来，可以使用括号来强制优先级

逻辑表达术语约定与基础性质

知识库（KB）中的公式隐式合取：逻辑知识库里，通常把每条公式当作“需要同时满足”的条件，自动等同于把它们用“∧”连在一起。所以可以把整个 KB 看成一个大公式，里面所有子句（formula）都以“并且”连接。

地面项(ground term)：一个不含变量的项，比如常数Alice、函数FatherOf(Bob)（因为它的参数也是常数），都算地面项

地面原子(ground atom)：一个所有参数都只是地面项的原子公式，比如 Likes(Alice, icecream)，它的两个参数Alice、icecream都是常数，没有变量

可能世界(possible world)：对“所有地面原子”做一次完整的真／假分配——也就是为每一个可能出现的地面原子（例如Smokes(Alice)、Smokes(Bob)、Likes(Bob,icecream)）分别指定它是真还是假；这样一个完整的分配，就对应一个可能世界，也叫一个 Herbrand 解释

一个公式是可满足的，当且仅当存在至少一个世界使其为真。

如果F和G是公式，则对其增加一些逻辑符后也是公式，具体内容如下表所示

逻辑表达式	意义	逻辑表达式	意义
¬F	否定	F∧G	合取
F∨G	析取	F⇒G	蕴涵
F⇔G	等价	∀xF	全称量化
∃xF	存在量化	\	\

一阶逻辑中的基本推理问题是判断知识库KB是否蕴涵公式F，即F是否在KB为真的所有世界中都为真(记作$KB |=F$)。该判断一般通过反驳完成，即说明KB蕴涵F当且仅当$KB \cup ¬F$是不可满足的。对于自动推理，通常将公式转换为更规范的形式，典型的是子句形式。

子句形式中的知识库是子句的合取，子句是文字的析取。一阶逻辑中的任何知识库都可以通过机械的步骤序列转换为子句形式。子句形式用于归结，这是一种对一阶逻辑的可靠且完备的反驳推理过程。

注意
这种转换包括通过 Skolem 化来移除存在量词，这在一般情况下是不可靠的。然而，在有限域中，一个存在量化公式可以简单地用它的实例化析取来替换

一阶逻辑的推理只是半可判定的。由于这个原因，知识库通常使用具有更理想性质的一阶逻辑的受限子集来构建。最广泛使用的限制是 Horn 子句，即最多包含一个正文字的子句。Prolog 编程语言基于 Horn 子句逻辑。可以通过搜索在数据中（近似）成立的 Horn 子句来从数据库中学习 Prolog 程序；这在归纳逻辑编程（ILP）领域进行研究。

大多数领域中，想出总是正确的非平凡公式非常困难，而且这些公式只捕捉了相关知识的很小一部分。因此，尽管一阶逻辑具有丰富的表达能力，但它在实际 AI 问题中的适用性有限。为此，人们提出了许多特设性的扩展方案。在更受限制的命题逻辑情况下，概率图模型能够很好地解决这个问题。下一节将描述如何将这些模型推广到一阶逻辑的情况。

马尔可夫逻辑网络(Markov Logic Network)

一个一阶知识库可以看作是可能世界集合上的硬约束集：如果一个世界违反了任何一个公式，它的概率就为零。马尔可夫逻辑网络（MLNs）的基本思想是软化这些约束：当一个世界违反知识库中的一个公式时，它的概率会降低，但并非不可能。一个世界违反的公式越少，它的概率就越高。每个公式都有一个相关的权重，它反映了该约束的强度：权重越高，满足该公式的世界与不满足该公式的世界之间的对数概率差异就越大，其他条件相同。

马尔可夫逻辑网络的定义：马尔可夫逻辑网络$L$是对$(F_i,w_i)$的集合，其中$F_i$是一阶逻辑中的公式，$w$是一个实数；结合一个有限常量集$C={ c_1, \cdots ,c_{|C|} }$，定义了马尔可夫网络$M_{L,C}$，其遵循下属两条内容：

在$M_{L,C}$中，对于$L$中出现的每个谓词及其每一种可能的替换实例（grounding），都对应一个二值节点。如果该地面原子为真，则该节点值为1，否则为0

通俗解释：把你所有的谓词(比如Smokes(x)、Friends(x,y))和常量(比如Alice,Bob)放在一起，每一种可能的组合——比如Smokes(Alice)、Smokes(Bob)、Friends(Alice,Bob)、Friends(Bob,Alice)——都变成一个“开关”节点。这个节点就表示“这个具体命题是否为真”：如果在我们的世界里确实Alice抽烟，就给Smokes(Alice)这个节点一个值 1，否则给它 0。
在$M_{L,C}$中，对于$L$中的每个公式$F_i$及其每一种可能的替换实例，都对应一个特征。如果该地面公式为真，则该特征值为1，否则为0。这个特征的权重即$L$中与$F_i$关联的$w_i$

通俗解释：把每条带权重的逻辑公式$F_i$(例如带权重0.8的Smokes(x) ⇒ Cancer(x))和常量也全展开：比如Smokes(Alice)⇒Cancer(Alice)、Smokes(Bob)⇒Cancer(Bob)每一个具体的“公式实例”都对应一个“特征开关”。如果这一条在现实里是真的（即如果Alice抽烟那她得癌症的推断在观察数据里也成立），这个特征就值 1，否则值 0。它还带着原来公式的那个权重$w_i$，用来告诉模型“这条规则在多大程度上应该被信任”。

对于马尔可夫逻辑网络中的随机变量x，可以写出概率分布公式：

\[P(X=x)=\frac{1}{Z}exp(\sum\limits_{i}w_i n_i(x))=\frac{1}{Z}\Pi \phi_i(x\{ i \})^{n_i(x)}\]

关键参量解释

$n_i(x)$：在世界$x$中，公式$F_i$为真的地面实例数

$x{ i }$：参与到这些“真”实例的原子（ground atoms）的取值集合

$\phi_i(x{ i })=e^{w_i}$：每个地面实例一旦为真，就贡献一个$e^{w_i}$因子

$Z$：分区函数（所有可能世界的指数和），确保总概率和为 1

利用标准一阶逻辑语法定义的模板层，使用给定常量集$C$，可以把每个公式的所有“地面化”实例都展开出来，得到一个真正的马尔可夫网络，称为地面马尔可夫网络(ground Markov network)。不同的常量集会展开出不同大小的网络，但它们遵循同一个模板的“形状”和“参数共享”规则。

展开后图机构的节点和边就可以成功构建：

节点：MLN 展开后，图中的每个节点就是一个地面原子(ground atom)，如Friends(Anna,Bob)
边：如果两个地面原子在同一个地面公式实例中一起出现，它们之间就连一条无向边。这样，每个地面公式的参与原子自然构成一个（或多个）团

马尔可夫逻辑网络满足的三个假设

唯一名称：不同常量指不同对象
域封闭性：域中仅包含使用$(L,C)$中的常量和函数符号可以表示的对象
已知函数：对$L$中出现的每个函数，该函数应用于所有可能的参数元组的值已知，且是$C$的元素

把一阶公式“地面化”（grounding）成具体的子句集合的伪代码如下：

---------------将一阶公式“地面化”成仅含常量和谓词的子句集合---------------
function Ground(F, C)
 inputs: 
   F  — 一个一阶逻辑公式（已在 Assumptions 1–3 前提下）；  
   C  — 常量集。  
 output:
   GF — 由所有地面子句（ground clauses）构成的集合。
---------------CNF转换和初始化地面子句集---------------
F ← CNF(F, C)
GF = ∅
---------------对每个子句依次展开变量---------------
for each clause Fj ∈ F
  Gj = { Fj }
  for each variable x in Fj
    for each clause Fk(x) ∈ Gj
      replace Fk(x) by { Fk(c1), …, Fk(c|C|) }
    end
  end
  GF ← GF ∪ Gj
end
---------------消除函数项---------------
for each ground clause Fj ∈ GF
  repeat
    for each function term f(a1,…,ak) whose args are all constants
      replace f(a1,…,ak) by its known value c ∈ C
    end
  until Fj contains no functions
end
---------------返回地面子句集---------------
return GF

MLN表达能力的相关分析

对于任意一组布尔变量$(X_1, \cdots, X_n)$，或任意精度的数值离散变量，都存在一个等价MLN能精确表示它们的任意联合分布
令KB为可满足的一阶知识库，L是把KB中每条公式都赋予相同权重后的MLN，C为KB中出现的常量集，P_w为MLN在常量集下得到的地面网路分布，$X_{KB}$是满足KB的所有可能世界集合，则当$w \to \infty$：
- 所有满足KB的世界将等概率出现，且不满足KB的世界概率趋于0
- 对任意公式F，如果且仅如果KB推出F(即$KB⊨F$)，那么在极限下$P_{w}(F)=1$

证明暂略，有兴趣可参考标题链接所附论文；总之这两条结论的目的包括：证明MLN不失一般性，可以表示所有离散或有限精度模型；表明 MLN 还包含了纯粹的——且完全可推广的一阶逻辑推理能力，当“软规则”权重变得极大时即恢复经典逻辑的全称量化蕴含。

马尔可夫逻辑网络的推理

如果$F_1$和$F_2$是两个一阶逻辑公式，$C$为包含$F_1$和$F_2$中任意常量的有限集，$F_1$是一组“查询”地面文字（ground literals），$F_2$是一组“证据”地面文字，则有：

\[P(F_1 \| F_2,L,C)=P(F_1 \| F_2,M_{L,C})=\frac{P(F_1 \land F_2 \| M_{L,C})}{P(F_2 \| M_{L,C})}=\frac{\sum_{x \in \mathcal{X}_{F_1}\cap \mathcal{X}_{F_2}}P(X=x \| M_{L,C})}{\sum_{x \in \mathcal{X}_{F_2}}P(X=x \| M_{L,C})}\]

直接对整个 ground 网络做求和或采样往往规模极大、不切实际。策略是先抠出最小必要部分，只保留与查询或证据相关的那些节点与因子，再在其上做推断。其伪代码如下：

---------------输入---------------
F1:需要推的查询地面原子集合
F2:已知为真的证据地面原子集合
L,C:MLN模板与常量集
---------------初始化---------------
G ← F1    -- G 记录所有“要保留的节点”  
Q ← F1    -- Q 记录当前待扩展的节点队列  
---------------迭代扩展 Markov Blanket---------------
while Q not empty:
  pick one原子 q from Q
  if q ∉ F2:
    MB(q) = Markov Blanket of q in ML,C
    G ← G ∪ MB(q)
    Q ← (Q ∪ MB(q)) \ G
  remove q from Q
  ---------------输出子网络---------------
  保留节点集$G$及它们之间原有的边和对应的因子，就构成了最小子网络$M$

进而在精简的网络上固定$F_2$(证据)后，使用任意推断算法，常用的Gibbs采样步骤如下：

初始化：为每个查询节点和其他未固定节点随机赋值，或用MaxWalkSat找一个高概率模式来启动，减少“热身”时间(burn‑in)
单节点更新：重复地对每个未固定地面原子$X_{l}$
- 看它的 Blanket $B_{l}$和当前状态$b$：马尔可夫毯是指在一个图模型中，一个节点的所有邻居节点。在MLN中，一个基元事实的马尔可夫毯就是所有与它共同出现在某条规则的基元实例中的其他基元事实
- 计算
  \[P(X_l=x_l \| B_l=b_l)=\frac{exp(\sum_{f_i \in F_l} w_i f_i(X_l=x_l, B_l=b_l))}{exp(\sum_{f_i \in F_l} w_i f_i(X_l=0, B_l=b_l))+exp(\sum_{f_i \in F_l} w_i f_i(X_l=1, B_l=b_l))}\]
- 按此分布采样$X_{l}$的新值
阻塞采样(Blocking)：如果一组原子之间在每个世界中只能有一个为真，则一次同时给它们互斥采样
收集样本：足够多迭代后，统计$F_1$为真的样本比例，作为$P(F_1 | F_2)$的估计

马尔可夫逻辑网络的学习

马尔可夫逻辑网络的学习目标是：为MLN中的每一条一阶逻辑规则（formula）找到一个合适的权重$w$，以确定不同规则在模型中的重要程度。学习的一居室一个/多个关系数据库，如果一个事实出现在数据库里则为真，反之则为假，数学表示为$X_l=0 \ or \ 1$

理想化的学习方法是利用梯度计算公式：

\[\frac{\partial}{\partial w_i}log P_w(X=x)=ni(x)-\sum\limits_{x'}P_{w}(X=x')n_i(x')\]

$ni(x)$：表示第i条规则在给定的真实数据库x中，有多少个“基元实例”（groundings）为真。简单来说，即这条规则在你的数据里被满足了多少次
$\sum\limits_{x’}P_{w}(X=x’)n_i(x’)$：这部分复杂一些。它计算的是，根据当前模型（由权重w定义），第i条规则被满足的期望次数。它需要遍历所有可能的数据库x’，计算每个x’出现的概率，再乘以第i条规则在x’中为真的次数，最后求和

这个梯度的直观理解即为：

\[梯度 = 规则在真实数据中的满足次数 - 规则在当前模型下的期望满足次数\]

如果真实满足次数 > 期望满足次数，说明我们低估了这条规则的重要性，梯度为正，我们就应该增大它的权重 wi。反之，如果真实满足次数 < 期望满足次数，我们就应该减小 wi。当两者相等时，梯度为0，模型就达到了一个稳定点。

但是该理想化方法遇到的问题有：

计算$ni(x)$难解：一个数据库中，计算一条一阶逻辑子句(first-order clause)的为真基元实例的数量，是#P-完备(#P-complete)问题；对于非常大的领域，可以不精确计算，而是通过随机抽样来近似估计这个数量
计算期望满足次数难解：它要求我们遍历所有可能的数据库x’。如果模型有N个基元事实，总共就有$2^N$个可能的数据库，数量级过大，无法遍历；同时，计算$Pw(X = x′)$本身就需要计算配分函数Z，而 Z的计算也是一个典型的难解问题，需要对整个模型进行推理(inference)

因此采用伪似然(Pseudo-Likelihood)的方式进行计算。伪似然的核心思想是，不再计算整个数据库x作为一个整体出现的概率$P(X=x)$，而是将它分解为一系列局部概率的乘积：

\[P*w(X = x) = \Pi_{l=1}^{n}Pw(X_l = x_l | MB_x(X_l)), l=1, \cdots, n\]

这个公式的含义是：我们逐一考察数据库中的每一个基元事实$X_l$，然后计算$X_l$取其当前值$x_l$的概率；这个概率是有条件的，其条件是它的马尔可夫毯(Markov Blanket, $MB_x(X_l)$)的状态。计算这种局部条件概率$Pw(X_l = x_l | MB_x(X_l))$不需要计算全局的配分函数Z，计算量大大减小，变得可行。

几个让伪似然优化过程更高效的技巧

忽略不相关的规则：在计算某个事实$X_l$的梯度时，只需要考虑那些包含了$X_l$的规则，其他规则可以直接忽略

预计算：像$ni(x)$这样的计数值，在整个优化过程中（比如用L-BFGS算法时）是不会随权重$w$变化的。因此，可以在优化开始前一次性计算好，无需在每次迭代中重复计算

忽略“强真”子句：如果一个子句（clause）中已经包含了两个或更多为真的文字（literal），那么改变其中任何一个事实的真假值，都不会改变整个子句的真值。因此，在计算梯度时可以忽略这些“强真”的子句，这可以极大地减少计算量

关系贝叶斯网络与贝叶斯逻辑程序

关系贝叶斯网络

对关系贝叶斯网络的基础理解：证据E是一组部分随机变量的实例化，在该组证据下查询某个随机变量X的特定值x的概率表示为：$P(X=x | E)$。同时这里需要做出一个隐性假设，即证据和查询都是单一的随机事件或对象属性。对于判断某一特定查询$w$是否发生，可以只关注其周边的证据，利用贝叶斯公式$P(X(w)=x | E(w))$计算。

在纳入一阶逻辑这种表述方式后，可以用一串长式表示某一查询的概率，如：

\[quake(u) \land quake(v) \land alarm(u) \land \neg alarm(v) \to^{0.8}\to stronger(u,v)\]

但是由于形式化强加了相当严格的句法和/或语义限制，该种表示方式的表达能力被严重限制；相比之下，关系贝叶斯网络(RBN)的优势在于，可以使用以词汇表S中每个关系符号为一个节点的贝叶斯网络，其中S被视为一个随机变量，其值是特定领域D中可能的解释。

典型案例
场景设置：假设有$n$块相互独立的地点，两两之间有多条通道相连；机器人A需要到达目标地点，或和其它机器人合作，完成任务。
数学论断：机器人A对目的地和其它机器人的位置判定是模糊的；假设机器人要从现有位置$z$到终点$x$完成最终目标，只有满足$success(x)$或 $\neg blocked(x,z)$时才会100\%实现；否则需要借助其它机器人，假设从$z$到$x$有$k$条道路，如果每个其它机器人在道上的概率为$p_2$，则机器人A能借助其它机器人完成任务的概率为$1-(1-p_2)^k$

基于该例子探索更一般的形式，目的可以提取为：在给定谓词$b$和$t$的情况下，计算谓词$s(x)$的概率，即对每个有限的集合$D$构建关于${ b,t,s }$结构的概率分布$P$。对于$b$和$t$，因为没有父节点，因此可以直接考虑其的概率$P(b(\cdot))$和$P(t(\cdot))$，假设解释$I \subset \Pi D$，则在整个$b$的事件组合中有$P(I)=(P_b)^{| I |} \cdot (1-P_b)^{N-| I |}$，对于$t$同理。

然后可以开始计算$P(s(x))$，当$b,t \to s$时，记为$condition(b,t)$，该种情况下$F_s(x)=1$；如果$\neg condition(b,t)$，利用$b,t$可以计算出对应的贡献(某个位置$z$对于判断位置$x$是否是错误或异常的“支持力度”或“证据强度”)，将贡献表示为$contribution=max(f(b,t),p_2 \cdot f(b \ or \ t))$该种情况下$H(x)=1-\Pi_{z \neq x}(1-contribution)$；然后计算出总概率：

\[F_s(x)=condition(b,t)+(1-condition(b,t)) \cdot H(x)\]

对关系贝叶斯网络的基础定义

组合函数(Combination Function)：满足指定条件输入输出的函数；输入条件为一个有限多重集（multiset，允许重复元素），每个元素都是一个$[0,1]$区间内的数，输出条件为一个$[0,1]$区间内的数，同时约定$max(\emptyset)=0,min(\emptyset)=1,n-o(\emptyset)=0$

Noise-or组合函数
Noisy‑Or 是一种常用的组合函数，用来将一组“部分证据”合并为“至少一条足够”情形下的总概率
概率公式的相关定义
- (Constants)：每个有理数$q∈[0,1]$本身是一个概率公式
- (Indicator functions)：对每个$n$-元符号${\bf{r}}∈S$和每个$n$元变量组$\bf{x}$，$\bf{r(x)}$是一个概率公式
- (Convex combinations) 若$F_1,F_2,F_3$都是概率公式，则$F_1F_2+(1-F_2)F_3$也是概率公式
- (Combination functions)：若$F_1,F_2,F_3$都是概率公式，则组合函数$comb(F_1,\cdots,F_k | {\bf{z}},c({\bf{x,z}}))$也是一个概率公式
指示任意一阶公式：任何一阶公式$\phi(\bf{x})$都能用仅含max的概率公式$F_{\phi}(\bf{x})$模拟，使得在任何有限结构和任意$\bf{d}$都有：$F_{\phi}({\bf{d}}) \Leftrightarrow \phi({\bf{d}})在结构中为真，否则F_{\phi}({\bf{d}})=0$
关系贝叶斯网络(Relational Bayesian Network)：给定谓词集$S$，关系贝叶斯网络包括 (1) 有向无环图，其中每个节点对应一个谓词$r \in S$ (2) 对每个$n$-元谓词节点$r$，用一个概率公式$F_r(x_1, \cdots, x_n)$表示它的条件概率，其中公式中用到的符号须来自其父节点谓词给定常数域$D$和父谓词的一组解释$\mathcal{I}(Pa(r))$，对每个$d \in D^{n}$，可计算$F_r(d)$，然后利用下述表达式定义，为谓词$r$的解释$\mathcal{I}(r)$构造一个伯努利分布：$P(Pa(r))=\Pi_{d \in D^{n}}F_r(d)^{\mathbb{I}[r(d)为真]}(1-F_r(d))^{\mathbb{I}[r(d)为假]}$

关系贝叶斯网络的推断

目标：在给定关系贝叶斯网络$N$(谓词集$S$)、有限域$D$、证据集$E={ r_i(d_i)^{l_i} | i=1,\cdots,n }$($l_i=+1$表示正文字，$l_i=-1$表示负文字)以及查询地面原子r_0(d_0)下计算$P(r_0(d_0) | E)$的值

综合公式论断：

若辅助网络节点集为$\mathcal{N}$，其联合分布为：

\[P\bigl(\{r(d)\}_{r(d)\in \mathcal{N}}\bigr)= \prod_{r(d)\in \mathcal{N}} F_r\!\bigl(d;\,\{r'(d')\mid (r',d')\in\mathcal{N}\}\bigr)^{\mathbb{I}[r(d)=\text{真}]} \Bigl(1 - F_r(\dots)\Bigr)^{\mathbb{I}[r(d)=\text{假}]}\,\]

具体步骤

步骤1：预处理，构建父依赖公式 对每个谓词$r \in S$与其父谓词$r’ \in Pa(r)$，预先构造一阶公式$pa_{r,r'}(x,y) \Leftrightarrow "F_r(x)的计算会用到r'(y)"$用于快速判定在何种$(d,d’) \in D^{arity(r)} \times D^{arity(r’)}$上连边

步骤2：构造最小辅助网络 初始化${ r_0(d_0) } \to \mathcal{N},队列{r_0(d_0)} \to 队列Q$ 迭代扩展，弹出节点$r(d)$，对每个父谓词$r’ \in Pa(r)$枚举所有$d’ \in D^{arity(r’)}$使得$pa_{r,r’}(d,d’)$为真，若$r’(d’) \notin \mathcal{N}$则加入$\mathcal{N}$并入队$Q$，重复直到$Q$为空

  Function ConstructAuxNetwork(query r0(d0), evidence E):
      Initialize
          Nodes ← { r0(d0) }
          Queue ← [ r0(d0) ]
      While Queue not empty:
          Pop r(d) from Queue
          For each parent predicate r' of r:
          For each d' in D such that pa_{r,r'}(d,d') holds:
              If r'(d') not yet in Nodes:
              Add r'(d') to Nodes and to Queue
      Return subnetwork induced by Nodes

步骤3：证据与推断 将证据集中每个地面原子$r_i(d_i$)固定为“真”或“假”，然后在辅助网络上采用标准离散贝叶斯网算法计算$P(r_0(d_0) | E)$
步骤4：衡量复杂度与优势 其节点数小于等于$O(| D |^{a})$，但通常远小于全展开；同时因$pa_{r,r’}$精准捕捉公式依赖，推断结果和全展开网络一致；也因仅展开与查询和证据相关部分，避免了指数爆炸

递归网络(Recursive Networks)

基础的关系贝叶斯网络无法表达那种“一个谓词实例依赖于自身或其“倒置”实例”的递归关系，因此需要引入“良基”序关系将各种递归依赖拆解为无回路的条件概率定义，统一地扩展关系贝叶斯网络：

对称关系：令 $r(x,y)$ 为二元对称谓词，域 $D$ 上有非严格全序 $\preceq$，则$F_r(x_1,x_2)= \max\Bigl\{ \underbrace{\max\{\,p \mid x_1 \preceq x_2\}}_{\text{先验概率 }p},\; \underbrace{\max\{\,r(x_2,x_1)\mid x_2 \prec x_1\}}_{\text{条件概率}} \Bigr\}.$当 $x_1\preceq x_2$ 时，$F_r=p$；否则，$F_r=r(x_2,x_1)$。
时间递归：域 $D={t_0\prec t_1\prec \cdots\prec t_n}$，谓词 $r(t,x)$ 依赖前一时刻：$F_0(t)= \max\{\,1 \mid \exists\,t':\,s(t',t)\}$ $F_r(t,x)=(1-F_0(t))\,p_0 \;+\; F_0(t)\,\Bigl[p_1\,r(t',x)+p_2\,(1-r(t',x))\Bigr]_{\!t':\,s(t',t)}.$其中 $s(t’,t)$ 是“$t’$ 是 $t$ 的前驱”关系。
随机函数：函数视作谓词 $r(x,y)$，其值域 ${v_1\prec v_2\prec\cdots\prec v_n}$ 上有全序。令$F_r(x,y)= \Bigl(1-\max\{r(x,z)\mid z\prec y\}\Bigr) \;\times\; \max_{i=1\ldots n}\{\,p_i\mid y=v_i\}.$第一因子保证“无较小值已被选中”，第二因子为“选中 $v_i$ 的概率 $p_i$”。

“良基”序关系的基本内容

检查良基性
给定固定结构 R（包含全序、常量等），验证每个递归依赖公式 F_r 在 R 上生成的依赖图是否无回路（well‑founded）。

构造辅助网络

对每对谓词 r, r'，用含 R‑约束的公式 pa_{r,r'}^R(x,y) 替代原先的仅含平等的 pa_{r,r'}(x,y)；

依照第 3 节算法，递归地将所有查询节点及其父节点加入网络，连上原网络中对应的弧，并保留各自的条件概率公式。

执行推断
在生成的辅助贝叶斯网络上，使用标准离散推断技术（如 Gibbs 采样、信念传播或变量消元）计算所需的条件概$率P\bigl(r_0(d_0)\mid E\bigr)$

贝叶斯逻辑程序

同样的，贝叶斯逻辑程序是关系贝叶斯网络和一阶逻辑结合的产物；该程序中关联的条件概率密度计算方法为：给定一个贝叶斯语句$r(t_1, \cdots ,t_n) ← s_1(t_{1,1}, \cdots ,t_{1,n_1}), \cdots , s_m(t_{m,1}, \cdots ,t_{m,n_m})$，对任意一组父原子取值$(u_1,\cdots ,u_m) \in D(s_1) \times \cdots \times D(s_m)$，$cpd(c)$给出一个函数$cpd(c)(· | u_1,\cdots,u_m):D(r) \to [0,1]$满足$cpd(c)(u \| u_1,\cdots,u_m)=P(r(t_1,\cdots,t_n)=U \| s_1(t_{1,1}, \cdots, t_{1,n_1})=U_1, \cdots, s_m(t_{m,1}, \cdots ,t_{m,n_m})=U_m)$

贝叶斯逻辑程序的组合规则(Combining Rule)

输入是一组条件概率密度${ p(A | A_{i1}, \cdots, A_{i n_i}) | i=1, \cdots, n,n_i \ge 0 }$，输出是一组合并后的条件概率密度${p(A | B_1, \cdots, B_n)}$；如果输入是空集（没有任何已知条件分布），那么输出也必须是空集；否则就得产生合并后的分布。

$A_{i1},…,A_{i n_i}$(Local Parents)：第 i 条规则的父变量(Local Parents)，每条模式就会用到一组父变量
${B1,…,Bn}$(Combined Parents)：把所有局部模式的父变量并起来，去掉重复之后得到的全集合

贝叶斯逻辑程序的定义

贝叶斯逻辑程序$B$由一组有限的贝叶斯子句组成。每个贝叶斯子句$c$都恰好有一个$cpd(c)$与之关联，并且对于每个贝叶斯谓词$r$，都恰好有一个 $comb(r)$与之关联的组合规则。与$B$的贝叶斯子句集对应的逻辑肯定子句集称为对应的逻辑程序$B$。

贝叶斯逻辑程序的立即后继算子(Immediate Consequence Operator)：在逻辑程序中，为每个Herbrand解释$I$提供一个算子$T_{\tilde{B}}(I)$，扫描贝叶斯子句库$\tilde{B}$中的每条子句$A | A_{1},…,A_{n}$，对每条子句和每个替换$\theta$，如果所有前提$A_{i}\theta$都在解释$I$中为真，则把结论$A\theta$加入到$T_{\tilde{B}}(I)$

最小Herbrand模型(Least Herbrand Model)：从空解释$\emptyset$开始不断应用$T_{\tilde{B}}$：$\emptyset \to T_{\tilde{B}}(\emptyset) \to T_{\tilde{B}}({\tilde{B}}(\emptyset)) \to \cdots $，当再应用$T{\tilde{B}}$不再新增原子时，得到的解释记作$LH(\tilde{B})$；意义是它是“恰好推出所有可以推出的真原子”且不包含多余假设的最小模型。

贝叶斯逻辑程序中的直接影响(Direct Influence)：在贝叶斯逻辑程序里，每个地面原子（随机变量）都可能被若干子句的前提（父节点）所“影响”；随机变量C直接影响A当且仅当$A,C$都在$LH(\tilde{B})$中，存在一条子句$A’ | A_{1},…,A_{n}$及一次替换$\theta$使得$A’=A\theta$，同时某个前提$A_{i}\theta=C$，且其它所有前提$A_{j}\theta$也都在最小模型中；所有直接影响$A$的变量构成其父集$Pa(A)$，刻画贝叶斯网络的有向边——即实际参与定义A条件分布的那些父变量。

良定义的贝叶斯逻辑程序(Well‑defined BLP)：满足模型非空、无环、父集有限的贝叶斯逻辑程序$B$。

声明式语义(Declarative Semantics)：任何满足上述良定义条件的贝叶斯逻辑程序$B$，都唯一地指定了一个概率测度$P$，即一个完整的联合概率分布——在其随机变量集合$LB(H)$上。

贝叶斯逻辑程序的查询与推理

对于贝叶斯逻辑程序的查询，条件概率密度可以写作$p(Q_1, \cdots, Q_n | E_1=e_1, \cdots , E_m=e_m)$，当$m=0$即没有条件变量时该查询称为无证据查询；具体的查询方式则和关系贝叶斯网络的查询类似。这里把辅助网络命名为支撑网络，写作$N(X_1, \cdots , X_m)=N(X_1) \cup \cdots \cup N(X_m)$。

在对贝叶斯逻辑程序进行推理和解释时，可以通过建立贝叶斯逻辑程序的解图(solution graph)与SLD树之间的对应关系，从而通过Prolog元解释器构建支持网络(support network)实现。

过程名	功能描述
`SupportNetwork`	初始化、调用其他两过程，得到完整支持网络
`SLD-Tree`	执行回溯推理构建 SLD 树，记录子句和替换关系
`ComputeSupportNetwork`	遍历成功路径，插入网络节点和边，并应用组合规则

贝叶斯逻辑程序的概率推理过程可以形式化为一个确定性逻辑推理过程（SLD 树），再通过该路径的概率注解构建支持网络，使得逻辑和概率结合成为可能。

SupportNetwork(B, Q, N):
    N ← 空支持网络
    Tree ← 空 SLD 树
    SLD-Tree(B, Q, Tree)
    ComputeSupportNetwork(Tree, N)
    N ← Prune(N)

动态贝叶斯网络：覆盖了贝叶斯网络和隐马尔可夫模型的一种框架是动态贝叶斯网络(Dynamic Bayesian Networks，简称 DBNs)。其核心思想是将时间划分为多个 time slice，每个 slice 表示过程在该时间点的快照。这些时间点的状态通过每个 time slice 中的一组随机变量形成贝叶斯子网络。

概率关系模型(PRMs)与概率关系图

概率关系模型(PRMs)

概率关系模型是上述两类模型的统称，分为有向PRMs和无向PRMs：

有向 PRM，如关系⻉叶斯⽹络（RBNs），如果它们的结构符合模型的⽆环约束，可以建模⾃相关依赖关系。虽然领域知识有时可以⽤来以⽆环的⽅式结构化⾃相关依赖关系，但通常⽆环的顺序是未知的或不存在的。例如，在遗传系谱分析中，亲属之间的基因存在⾃相关。在这个领域中，因果关系是从祖先到后代，因此我们可以利⽤时间上的亲代⼦代关系来以⽆环的⽅式结构化依赖关系（即，⽗⺟的基因永远不会受到其⼦⼥基因的影响）。然⽽，给定⼀组相互链接的⽹⻚，⼏乎没有信息可以⽤来确定它们主题之间依赖关系的因果⽅向。在这种情况下，我们只能将两个⽹⻚之间的⾃相关表⽰为⽆向相关。有向 PRM 的⽆环约束禁⽌学习任意的⾃相关依赖关系，从⽽严重限制了这些模型在关系领域的应⽤。
⽆向 PRM，如关系⻢尔可夫⽹络（RMNs），可以表⽰和推理任意形式的⾃相关。然⽽，这些模型的研究主要集中在参数估计和推理⽅法上。当前的 RMN 实现不选择特征模型结构必须由⽤⼾预先指定。虽然原则上 RMN 技术可以学习循环⾃相关依赖关系，但由于参数估计效率低下，这在实践中很难实现。因为参数估计需要在整个数据集上进⾏多次推理，将其作为特征选择的⼦组件是不切实际的。最近对序列分析的条件随机字段的研究包括⼀个特征选择算法，该算法可以扩展到 RMNs。然而，该算法放弃了对完整联合分布的估计，⽽是使⽤拟似然估计，这使得⽅法可⾏，但移除了利⽤完整联合分布进⾏推理的⼀些优势。

这里概率关系模型的语义学规则、一阶逻辑定义等和前面两种方式是类似的，在此不再赘述，这里仅呈现一些可以参考的推理算法。

自上而下推理算法(Top-Down)：对于基本命题和逻辑运算符直接根据状态赋值或递归调用处理；对模态公式 $K_i(x) \ α \ r$，遍历所有从当前状态$s$可达的状态，累计满足子查询$x$的概率，并用参数$α \ r$进行调整

  函数 ToDo(状态 s, 查询 q)
  // “value”表示每个状态对基本命题的真值赋值
  // “Pi(s'|s)”表示从状态 s 转移到状态 s' 的概率

  如果 q 是真（⊤）则 返回 真
  否则如果 q 是假（⊥）则 返回 假
  否则如果 q 是一个命题字母，则 返回 value(s, q)
  否则如果 q 是 ¬x，则 返回 ¬ ToDo(s, x)
  否则如果 q 是 x ∧ y，则 返回 ToDo(s, x) 且 ToDo(s, y)
  否则如果 q 是模态形式 Ki(x) α r，则
      设 m = 0
      遍历所有从状态 s 可达的状态 s'：
      如果 ToDo(s', x) 为真，则 m 加上 Pi(s'|s)
      返回 m 经过 α r 运算的结果

自底向上推理算法(Bottom-Up)：对所有状态对之间的概率转移进行细粒度计算，分别累计满足和不满足子查询的概率值；通过对所有状态的真、假概率分开统计，计算最终的概率比值；该方法更精细，适合概率转移复杂且需要精确概率分布的场景

  函数 KBU(状态 s, 查询 q)
  // Pi 表示状态在等价类中的概率
  // val 递归计算无模态函数的公式值

  设 m = 1
  对查询中所有形式为 Ki(x) α r 且 x 无模态的子式：
      遍历关系 i 的所有等价类 e：
      计算 tm = （等价类 e 中满足 val(s, x) = 真 的状态概率和） 经过 α r 运算
      给等价类 e 中所有状态赋值 tm
      用 tm 替换查询中的 Ki(x) α r 子式
      m 自增 1
  返回 val(s, q)

  设 m = 1
  对查询中所有形式为 Ki(x) α r 且 x 无模态的子式：
      初始化 tm_true 和 tm_false 数组，所有状态初值为0

      对所有状态 s2：
      对所有从 s1 可达 s2 的 s1：
          根据 val(s2, x) 是否为真，分别累计 tm_true[s2] 或 tm_false[s2] 加上 Pi(s2|s1)

      对所有状态 s1：
      计算 tm = [tm_true[s1] / (tm_true[s1] + tm_false[s1])] 经过 α r 运算

      用 tm 替换查询中的 Ki(x) α r 子式
      m 自增 1

  返回 val(s, q)

计算最大概率算法(BEST Algorithm)：用于计算查询在状态$s$下的“最大概率”，如果查询是模态表达式，使用类似ToDo的遍历方法计算所有可达状态满足子查询的概率总和，否则直接调用ToDo递归处理，适用于需要评估最优概率路径的推理任务

  函数 BEST(状态 s, 查询 q)
  如果 q 是 Ki(x) 形式：
      设 m = 0
      遍历所有从 s 可达的状态 s'：
      如果 ToDo(s', x) 为真，则 m 加上 Pi(s'|s)
      返回 m
  否则
      返回 ToDo(s, q)

近似推理算法(ARea)：这是一个基于采样和近似的推理算法；其构造查询的依赖图$T(q,s)$，反转所有边得到$N$，方便从叶子到根节点的概率传播；针对不同类型的逻辑运算符（与、非、模态）定义相应的条件概率表（CPT），具体数值根据逻辑运算规则和概率模型确定；利用定义好的 CPT 和采样样本，进行概率推断计算目标查询的概率，适合复杂查询且状态空间巨大时，用近似方法获得结果 ```plaintext 函数 ARea(状态 s, 查询 q) M 是采样数量常数 Pa 映射每个节点到其父节点列表
1. 根据定义0.9 构造查询依赖树 T(q,s)
2. 反转 T(q,s) 中所有边，得到图 N
3. 对图 N 中所有操作符为 ∧ 的节点 l：对所有 v, v1, v2 ∈ {0,1}：定义条件概率 CPTN(l = v | Pa(l) = (v1, v2)) = (v == v1 ∧ v2)
4. 对图 N 中所有操作符为 ¬ 的节点 l：对所有 v, v’ ∈ {0,1}：定义条件概率 CPTN(l = v | Pa(l) = (v’)) = (v == ¬v’)
5. 对图 N 中所有操作符为 Ki(x) 且小于 r 的节点 l：对所有 v, v1,…, vM ∈ {0,1}：定义条件概率 CPTN(l = v | Pa(l) = (v1,…,vM)) 依照公式(1)
6. 利用推理算法计算 Pr(q_s = 1 | 根节点 l1 = v1,…,lr = vr) 返回推理结果 ```

概率关系图

概率关系图具有三层架构，数据实例($G_D$)→定义模板依赖($G_M$)→展开到实例($G_I$)：

数据图($G_D$)：提供实例关系和属性原始值
模型图($G_M$)：提供类型属性的依赖模板
推理图($G_I$)：是展开后的图，将模型图复制到实例化节点用于具体推断

利用概率关系图进行查询的完整流程为：

首先定义并加载数据图$G_D$将所有实体、关系和属性值载入到其中，准备模板模型图$G_M^{0}$用于构建初始的空参数结构框架
然后利用查询，从大规模数据图中筛选出每个待学属性$X$需要的训练样本，然后输出训练数据集$D=\{(x^{(j)},u_1^{(j)}, \cdots,u_r^{(j)},s_1^{(j)},\cdots,s_s^{(j)}) \| j=1,\cdots,M \}$ $t$记为当前要建模的项目类型，$X \in X_t$记为此类型下的一个目标属性，$Q$记为查询模式，${ \mu_{1},\cdots,\mu_{M} }$为所有满足$Q$的映射，则对于$Q$的每个映射：
- $\mu_{j}(t)$是一个具体实例
- 目标值为$x^{(j)}=X(\mu_{j}(t))$
- 单值父属性集合$U=\{ U_1, \cdots,U_r \} \subseteq X_{t}:u_{k}^{(j)}=U_{k}(\mu_{j}(t))$
- 多值slot-chain父属性集合$S={ S_1, \cdots,S_s }$，每个$S_k$通过一条slot-chain在子图中指向一个多重集$s_k^{(j)}=\{ S_k(v) \| v \in neigh_{S_{k}}(\mu_{j}(t)) \}$
进一步构建条件学习器，学习CPD，从而更新模板模型图到量化模型图$G_M$
- 输入：$D=(x^{(j)},u_i^{(j)},s_i^{(j)})_{j=1}^{M}$
- 输出：条件概率分布$p(X | Pa(X))$
然后根据数据图和模型图展开推理图$G_I$，最终实现在图中采样进行推断

推理RDN(GD, GM, P, iter, burnin)
输入：GD（数据图）、GM（模型图）、P（概率参数）、iter（总迭代次数）、burnin（烧入期）
输出：使用采样估计的概率
第一步：根据GD和GM构建GI
    GI(VI, EI) ← (∅, ∅)
    对于每个类型 t ∈ T（模型中的节点类型）
    对于 GM 中类型为 t 的每个随机变量 X_t_k：
        对于 GD 中所有满足类型 T(v_i) = t 的节点 v_i，以及所有满足类型 T(e_i) = t 的边 e_i：
            VI ← VI ∪ {X_t_ik}  # 将实例化的变量加入VI中
    添加依赖边
    对于 GD 中所有满足 T(v_i) = t 的节点 v_i，以及所有满足 T(e_i) = t 的边 e_i：
        对于所有 X_v_j ∈ pa(X_t_ik) 和 Xe_j ∈ pa(X_t_ik)：
            EI ← EI ∪ {e_ij}  # 加入依赖边
第二步：初始化Gibbs采样
    对于每个变量 v ∈ VI：
        随机初始化 x_v，从其先验分布 p(x_v) 中采样一个初始值
    S ← ∅  # S用于存储采样结果
    Gibbs采样过程
    从VI中选择一个随机的遍历顺序
    对于 i 从 1 到 iter：
        按照随机顺序遍历每个变量 v ∈ VI：
            从条件分布 p(x_v | x_{-v}) 中重新采样 x_v：
                x_v ← 新采样值 x'_v
        如果 i > burnin（即过了烧入期）：
            将当前样本 x 加入样本集 S：S ← S ∪ {x}
第三步：使用样本S估计感兴趣的概率

概率软逻辑与概率逻辑编程

概率软逻辑

一种统计关系学习（SRL）框架，用于建模概率性和关系性领域。它适用于各种机器学习问题，如集体分类、实体解析、链接预测和本体对齐。PSL 结合了两种工具：一阶逻辑，它能够简洁地表示复杂的现象，以及概率图形模型，它可以捕捉现实世界知识中固有的不确定性和不完整性。更具体地说，PSL 使用“软”逻辑作为其逻辑组件，使用马尔可夫随机场作为其统计模型。PSL 提供了高级推理技术来找到最可能的答案（即最大后验概率（MAP）状态）。逻辑公式的“软化”使得推理成为多项式时间操作，而不是 NP 难操作。

概率逻辑编程

概率逻辑编程是一种将逻辑编程与概率相结合的编程范式。大多数概率逻辑编程的方法都基于分布语义，该方法将程序分为一组概率事实和一个逻辑程序。它定义了程序赫兰德宇宙的解释的概率分布。

分层程序：如果对于概率事实的任何真值选择，所得到的逻辑程序是分层的，那么它将有一个唯一的最小赫拉德模型，这个模型可以被视为与该真值选择相关的唯一解释。

回答集程序：回答集编程的基础稳定模型语义通过为概率事实的每个真值分配可能不止一个回答集，从而赋予非分层程序意义。这提出了如何在回答集之间分配概率质量的问题。

推理：计算查询概率的问题称为（边缘）推理。通过计算所有可能的世界然后识别那些蕴含查询的方法是不切实际的，因为可能的世界数量随着基础概率事实的数量呈指数增长。(inspiration：这和新闻是一样的，新闻数量也在不断增长至无限多)实际上，即使对于无环程序和原子查询，计算给定原子合取证据条件下查询的条件概率也是 #P 完全问题。

总之，统计关系学习(Statistical Relational Learning, SRL)是一个融合了一阶逻辑与概率图模型的机器学习领域，其核心思想是将传统逻辑中非真即假的“硬”规则，转化为带权重或概率的“软”约束，从而能够在一个统一的框架下对充满复杂关系和不确定性的数据进行建模。通过马尔可夫逻辑网络(MLN)等无向模型表达对称关系，或通过关系贝叶斯网络(RBN)等有向模型刻画因果依赖，这些模型在应用于具体数据时会展开成巨大的“地面网络”，使得精确的概率推理和学习异常困难，因此其实际应用严重依赖吉布斯采样、伪似然估计等近似算法来完成任务。

【参考资料】

数学, 逻辑学

综述笔记

本文由作者按照 CC BY 4.0 进行授权