符号学习简介

Final Project

Science World

https://github.com/allenai/ScienceWorld

Task

https://sciworld.apps.allenai.org/explore

1. 选取其中的 1 个task，通过自己玩 or 用（比较强的） LLM 收集完成该任务的 examples （trajectory）
2. 运用你学到的关于“程序归纳”的知识，实现一个简单的归纳算法，将上面的 examples 归纳为一个成功率较高的 program / workflow （命题 or 一阶均可）
3. 撰写课程报告（ddl, 2026 年 1 月 11 日）
4. 其他要求：
   • 若你的 program / workflow 需调用大模型，请使用 10b 以下模型
   • 为降低难度，可提供一定先置背景知识（如地图等），但关于任务执行本身的 Program / workflow 不能是手写的
   • 报告中必须严格描述你如何将该任务形式化为一个逻辑归纳问题，并描述你的归纳算法
5. 打分标准：技术报告的完成程度 + 选取任务的难度

符号学习简介・概率逻辑系统

“真度”与“概率”

“真度”与“概率”

“真度”与“概率”

“真度”与“概率”

“真度”与“概率”

“真度”与“概率”

概率逻辑的语义

概率逻辑的语义

符号学习简介・概率逻辑系统

基于知识的模型构建

Knowledge-Based Model Construction （KBMC）：构建一个具有逻辑结构的概率模型

• 起源于知识工程应对不确定推理的不足
  • 决策支持系统（Decision Support System, DSS），1970s
• 先决条件是贝叶斯网的出现，1988

贝叶斯网

图中的条件概率分布：\(\mathrm{Pr}(R)\), \(\mathrm{Pr}(S\mid R)\), \(\mathrm{Pr}(G\mid S,R)\)

贝叶斯网

图中的联合概率分布：\(\mathrm{Pr}(G,S,R)=\mathrm{Pr}(R)\cdot\mathrm{Pr}(S\mid R)\cdot\mathrm{Pr}(G\mid S,R)\)

贝叶斯网

贝叶斯网的概率分布函数

知识在概率模型中的作用

在概率模型中引入知识是为了简化推理的运算与存储复杂度。

蕴涵的语义

Noisy Or

\[\mathrm{Pr}(X_1 \vee X_2 \vee\ldots \vee X_n)=1-\prod_{i=1}^n \mathrm{Pr}(\neg X_i)\]

• 原始的 \(\vee\) 若用贝叶斯网来表示需要 \(O(2^n)\) 个参数
• 引入独立性以后将参数缩小为 \(O(n)\) 个

Noisy And

\[\mathrm{Pr}(X_1 \wedge X_2 \wedge\ldots \wedge X_n)=\prod_{i=1}^n \mathrm{Pr}(X_i)\]

• 原始的 \(\wedge\) 若用贝叶斯网来表示需要 \(O(2^n)\) 个参数
• 引入独立性以后将参数缩小为 \(O(n)\) 个

条件独立性

• \(X_1 \top\!\!\!\top X_2\)
• \(X_1 \perp\!\!\!\perp X_2 \mid Y\)

马尔可夫网

通过无向图构建随机变量间的依赖关系。

• 通过一种叫做团（clique）的子图来分解随机联合概率分布
• 每个团是一个完全连通图
• 团拥有自己的势函数，用来描述它对联合概率分布的贡献

---

符号学习

概率逻辑系统

https://daiwz.net

马尔可夫网的概率分布函数

右图的联合概率分布定义如下： \[ \mathrm{Pr}(A,B,C,D,E)=\frac{1}{Z}\phi(A,C)\phi(C,D)\phi(B,C,E) \] 其中 \(Z\) 为用来归一的配分函数（partition function）： \[ Z=\sum_{A,B,C,D,E}\phi_{AC}(A,C)\phi_{CD}(C,D)\phi_{BCE}(B,C,E) \] 而 \(\phi\) 为每个团的势函数，例如：

\(A\)	\(C\)	\(\phi_{AC}(A,C)\)
0	0	1
0	1	10
1	0	10
1	1	100

---

符号学习

概率逻辑系统

https://daiwz.net

马尔可夫网中的条件独立

贝叶斯网中的条件概率 \[\mathrm{Pr}(Y\mid X_1, X_2)=\phi_{X_1 X_2 Y}(X_1, X_2, Y)\] 因此，在马尔可夫网中右图会变成一个大小为 \(3\) 的团。

马尔可夫网中的条件独立

一个节点所有相邻的节点被称为它的马尔可夫毯（Markov Blanket）。给定马尔可夫毯时，该节点与图中其他节点条件独立。

\begin{eqnarray*} &&\mathrm{Pr}(B\mid A,C,D)=\frac{\mathcal{Pr}(A,B,C,D)}{_{}\mathcal{Pr}(A,C,D)}\\ &&\hspace{2em}=\frac{\phi_{AB}(A,B)\phi_{BC}(B,C)\phi_{CD}(C,D)\phi_{AD}(A,D)}{\phi_{CD}(C,D)\phi_{AD}(A,D)\sum_{B}\phi_{AB}(A,B)\phi_{BC}(B,C)}\\ &&\hspace{2em}=\frac{\phi_{AB}(A,B)\phi_{BC}(B,C)}{\sum_{B}\phi_{AB}(A,B)\phi_{BC}(B,C)}\\ &&\hspace{2em}=\mathrm{Pr}(B\mid A,C) \end{eqnarray*}

---

符号学习

概率逻辑系统

https://daiwz.net

合取的语义

析取的语义

蕴涵的语义

马尔可夫逻辑网

将逻辑公式的语义用马尔可夫网表达，即得到马尔可夫逻辑网（Markov Logic Network, MLN）。

• MLN 可看作用一阶逻辑公式作为模板 生成的具体马尔可夫网
• 将每个具体逻辑公式作为一个团
• 一阶逻辑公式的权重作为势函数的来源

马尔可夫逻辑网

马尔可夫逻辑网

符号学习简介・概率逻辑系统

用逻辑来表达概率

用逻辑来表达概率

用逻辑来表达概率

用逻辑来表达概率

概率空间

概率空间是一个三元组 \((\Omega, \mathcal{F}, \mathrm{Pr})\)，其中：

• \(\Omega\) 是一个非空集，被称为样本空间
• \(\mathcal{F}\subseteq 2^\Omega\) 是一个 \(\sigma\)-代数，代表可能事件
  • 它关于可数并和补运算封闭
• \(\mathrm{Pr}:\mathcal{F}\mapsto[0,1]\) 是概率测度函数
  • \(\mathrm{Pr}(\Omega)=1\)
  • 它可数可加：若 \(\{A_i\}^\infty_{i=1}\subseteq\mathcal{F}\) 两两不相交，则 \[\mathrm{Pr}(\cup^\infty_{i=1}A_i)=\sum^\infty_{i=1}\mathrm{Pr}(A_i)\]

概率逻辑语言

我们仍然有一个自由代数，它包含一系列基本符号：

• \(\Phi=\{p_1, p_2, \ldots\}\) 为所有的原子命题
• 实数符号
• \(\neg\) 与 \(\vee\) 为逻辑连词
• \(w(\varphi)\) 是一个权重函数，\(\varphi\) 为以上符号构成的公式
• 算数符号
• 大小于符号

概率逻辑结构

四元组 \(M=(\Omega, \mathcal{F}, \mathrm{Pr}, \pi)\) 是一个概率逻辑结构（probabilistic logic structure），其中：

• \((\Omega, \mathcal{F}, \mathrm{Pr})\) 是一个概率空间
  • \(\Omega\) 是关于 \(\Phi\) 的所有可能世界
  • \(\mathcal{F}\subseteq 2^\Omega\) 是一个 \(\sigma\)-代数
  • \(\mathrm{Pr}:\mathcal{F}\mapsto[0,1]\) 是概率测度函数
• \(\pi\) 为真值指派函数，例如：
  • 原子命题 \(p\in\Phi\) 在可能世界 \(s\in\Omega\) 中的真值 \(\pi(s)(p)\in\{True,False\}\)

概率逻辑结构的语义

概率逻辑结构的语义

基于可能世界的推理

考虑一个逻辑理论的 Herbrand universe：

1. 每个具体事实可看作一个随机变量；
2. 对它们的真值指派可看作一个可能世界（Possible world）；
3. 每个可能世界中均能够进行纯逻辑推理；
4. 对问句（query）求它在所有可能世界中为真的期望；
5. 概率分布只需定义在该 Herbrand universe 上即可

分布语义的公理系统

分布语义涵盖了命题逻辑与概率论公理，具体包含了：

1. 命题逻辑公理
   • 所有命题逻辑重言式
   • MP 规则
2. 关于线性不等式的一切重言式
3. 关于概率论的公理：
   • \(0\leq w(\varphi)\leq 1\)
   • \(w(True)=1\)
   • \(w(\varphi\wedge\psi)+w(\varphi\wedge\neg \psi)=w(\varphi)\)
   • \(w(\varphi)=w(\psi)\) 仅当 \(\varphi\equiv\psi\) 是一个命题逻辑中的重言式

概率逻辑程序的例子

%% Probabilistic facts:
0.5::heads1.
0.6::heads2.

%% Rules:
twoHeads :- heads1, heads2.
someHeads :- heads1.
someHeads :- heads2.

%% Queries:
query(twoHeads).
query(someHeads).

prob(twoHeads, 0.3).
prob(someHeads, 0.8).

概率逻辑程序的例子

%% Probabilistic rules:
0.3::stress(X) :- person(X).
0.2::influences(X,Y) :- person(X), person(Y).
0.4::cancer(X) :- smokes(X).

%% Non-probabilistic rules:
smokes(X) :- stress(X).
smokes(X) :- friend(X,Y), influences(Y,X), smokes(Y).

%% Facts
person(angelika).
person(joris).
person(jonas).
person(dimitar).

friend(joris,jonas).
friend(joris,angelika).
friend(joris,dimitar).
friend(angelika,jonas).

%% Query
query(cancer(X)).

%% Output
prob(cancer(angelika), 0.1368).
prob(cancer(dimitar), 0.12).
prob(cancer(jonas), 0.12).
prob(cancer(joris), 0.16920518).

符号学习简介・概率逻辑推断

统计关系模型

Startistical Relational AI (StaRAI) 的本质是将 ground rules 转换为布尔随机变量构成的概率图模型（Probabilistic Graphical Model, PGM）。

PGM 中的推理

统计推断（Statistical Inference）：

• 通过基于概率分布的计算来回答关于领域的问题。

消元法

计算如下边际概率：

\begin{eqnarray*} &\mathrm{Pr}({\color{var(--zenburn-red)}{f}})=\sum_{{\color{var(--zenburn-blue)}{a,b,c,d,e,g}}}\mathrm{Pr}({\color{var(--zenburn-blue)}{a,b,c,d,e}},{\color{var(--zenburn-red)}{f}},{\color{var(--zenburn-blue)}{g}})\\ &\hspace{1em}= \sum_{a,b,c,d,e,g}\mathrm{Pr}(f\mid d)\mathrm{Pr}(g\mid d,e)\mathrm{Pr}(c\mid a)\mathrm{Pr}(d\mid a,b)\mathrm{Pr}(a)\mathrm{Pr}(b)\mathrm{Pr}(e) \end{eqnarray*}

消息传递

将边际概率看作“消息传递”（message passing）。考虑如下布尔马尔可夫链： 其联合概率分布的分解形式为：\(\mathrm{Pr}(a,b,c,d)=\mathrm{Pr}(a\mid b)\mathrm{Pr}(b\mid c)\mathrm{Pr}(c\mid d)\mathrm{Pr}(d)\)

消息传递

消息传递

因子图

图模型中用方形节点表示其相邻节点随机变量构成的因子（factor），它是一个非负函数。

左边因子图表示是 \(4\) 个因子的乘积： \[f(a,b,c,d,e)=f_1(a,b)f_2(b,c,d)f_3(c,e)f_4(d,e)\]

马尔可夫网的因子图

(a)

(b)

(c)

• (a) 的势函数因子：\(\phi(a,b,c)\)
• (b) 的势函数因子：\(\phi_1(a,b)\phi_2(b,c)\phi_3(a,c)\)
• (a) 和 (b) 有着相同的马尔可夫网结构 (c)
• 但 (b) 表达了更多关于势函数的约束（例如逻辑规则）

隐马尔可夫模型的因子图

信念传播

Belief Propagation：

因子图中一个节点只有在完全收集到邻居传来的“信息”时才可以将自己的“信息”传递出去。 \[\mathrm{Pr}(a,b,c,d,e)\propto f_1(a,b)f_2(b,c,d)f_3(c)f_4(d,e)f_5(d)\]

信念传播・Sum-Product

随机变量到因子节点

\[{\color{var(--zenburn-red)}{\mu_ {v\rightarrow f}(v)}}=\prod_{f_i \sim v\backslash f}{\color{var(--zenburn-blue)}{ \mu_{f_i \rightarrow v}(v)}}\]

边界变量（无输入邻居因子）的信息为 \(1\)。

因子节点到随机变量

\[{\color{var(--zenburn-red)}{\mu_{f\rightarrow v}(v)}}=\sum _{\{v_i\}}f(v,\{v_i\})\prod_{v_i \sim f\backslash v}{\color{var(--zenburn-blue)}{ \mu_{v_i \rightarrow f}(v_i)}}\]

边界因子（无输入邻居变量）的信息为其本身。

符号学习简介・概率逻辑推断

可满足性问题（SAT）

输入：

• 一组布尔变量集合（游戏中的 \(1,\ldots,9\)）
• 一组形如 \(l_1 \vee \ldots \vee l_k\) 的子句（在游戏中 \(k=3\)，因此它是 \(3\)-SAT），其中每个文字 \(l_i\) 是布尔变量或其否定形式

输出：

• 对所有布尔变量的一个真值指派，使得它能够满足（satisfies）所有子句

可满足性问题（SAT）

可满足性问题（SAT）

贝叶斯网与 SAT

贝叶斯网与 SAT

• 给 \(A,B,C\) 各自为真的事件赋概率值 \(0.5\)，并令它们到 \(C_1, C_2, C_3\) 的条件概率分布表为以上表达式（例如，\(C_1\) 为真当且仅当 \(\neg A\vee B\)）
• 若 \(\mathrm{Pr}(F)>0\) 当且仅当上面的 CNF 可满足
• 因此，贝叶斯网推断的复杂度至少与 SAT 等价（NP-难）
• 那么，\(\mathrm{Pr}(F)=3/8\) 代表什么意思?

从 SAT 到 #SAT 到 WMC

从 SAT 到 #SAT 到 WMC

从前面的例子可以看出，贝叶斯网的概率推断与带权模型计数有着极强的关联：

• 该例子中的 CNF 一共有 \(3\) 个模型
• 在该贝叶斯网中，每个可能世界有 \(1/8\) 的概率，每个变量为真的概率（权重）为 \(0.5\)。我们可按如下方式定义带权模型计数（weighted model counting, WMC）：
  • 给定一个逻辑理论 \(T\)（通常为 CNF）
  • 它的任意文字 \(l\) 均被赋有一个（非负）权重 \(w(l)\)
• 那么，带权模型计数问题的结果 \(wmc(T)\) 即为：
  • \(wmc(T)=\sum_{M\models T}w(M)\)，其中 \(M\) 是 \(T\) 的模型（例如 least Herbrand model）
  • 假设所有文字之间相互独立，那么 \(w(M)=\prod_{l\in M}w(l)\)

从 SAT 到 #SAT 到 WMC

符号学习简介・概率逻辑推断

知识编译

Knowledge Compilation： 将逻辑表达式编译为一个电路（circuit）以进行高效运算

• 编译一次，重复利用
  • SAT 求解算法的 DPLL 每次计算都需要从头开始
  • 贝叶斯网推断方法中的 SoTA
  • 针对不同种类的问题，存在许多电路类型
  • 已经被应用在许多领域（软件验证、计算机体系结构、数据挖掘等等）

知识编译

贝叶斯网可以编码为如下布尔表达式： \[ \{(\theta_A \wedge A)\wedge ((\theta_{B\mid A}\wedge B)\vee(\theta_{\neg B\mid A}\wedge\neg B))\}\vee\{(\theta_{\neg A}\wedge A)\wedge((\theta_{B\mid \neg A}\wedge B)\vee(\theta_{\neg B\mid \neg A}\wedge \neg B))\} \]

• \(A\):

  \begin{eqnarray*} A&\Leftrightarrow&\theta_A\\ \neg A&\Leftrightarrow&\theta_{\neg A} \end{eqnarray*}

• \(A\rightarrow B\):

  \begin{eqnarray*} A\wedge B&\Leftrightarrow&\theta_ {B\mid A}\\ A\wedge \neg B&\Leftrightarrow&\theta_ {\neg B\mid A}\\ \neg A\wedge B&\Leftrightarrow&\theta_ {B\mid \neg A}\\ \neg A\wedge \neg B&\Leftrightarrow&\theta_ {\neg B\mid \neg A} \end{eqnarray*}

知识编译

对应着：

转化为算数电路

可以看到，这里的 \(A,B,\neg A,\neg B\) 均为布尔表达式 \(\theta_x\) 的权重！

转化为算数电路

计算 \(\mathrm{Pr}(A=false)\) 时，只需令权重 \(A=0,\neg A=1, B=1, \neg B=1\)

Max-Product

当需要计算 MPE（most-probable explanation）时，可编译一个 max-product 电路：

计算 \(\mathop{\arg\max}\limits_b \mathrm{Pr}(A=false, B=b)\) 时，只需令权重 \(A=0,\neg A=1, B=1, \neg B=1\) 并计算上式。

算数电路中的概率推断

1. 计算观测变量（或称为证据，evidence）\(\mathrm{Pr}(evidence)\) 的概率只需要重新设置权重：
   • 若 \(e=true\) 则令权重 \(e=1\) 且 \(\neg e=0\)，反之亦然
   • 若 \(v\) 不是观测变量，则令 \(v=1\) 且 \(\neg v=1\)
   • 对于所有条件概率表中的条目：令 \(\neg\theta_x=1\) 且 \(\theta_x=CPT(x)\)
2. 因为权重可以重新设置，算数电路可被用于多次重复运算
   • 仅需要编译一次（花费较高），但以后每次推断速度都很快
   • 可类比于信念传播，完成传播后可获得所有变量的边际分布
3. 如何保证算数电路能够计算出正确的结果？
   • sd-DNNF （smooth, deterministic, Decomposable Negation Normal Form）

d-DNNF 的编译算法

Huang and Darwiche. The language of search. JAIR, 2007.

概率规则学习

参数学习

参数学习

马尔可夫逻辑的参数估计

\[ \mathrm{Pr}_w(\mathbf{X})=\frac{1}{Z}\prod_i \phi_i (\mathbf{X})=\frac{1}{Z}\exp\left(\sum_i {\color{var(--zenburn-red)}{w_i}} {\color{var(--zenburn-blue)}{n_i }}(\mathbf{X})\right) \]

马尔可夫逻辑的参数估计

判别式学习：预测条件似然 \(\mathrm{Pr}(y\mid x)\) \[ \mathrm{Pr}(y\mid x)=\frac{1}{Z_x}\exp\left(\sum_{i\in F_Y}w_i n_i (x,y)\right) \]

• \(\color{var(--zenburn-red)}{w_i}\)：第 \(i\) 个子句的权重
• \(Z_x\)：取值 \(X=x\) 的所有 possible world 权重之和（条件配分函数）
• \(F_Y\)：包含问句原子 \(Y\) 的所有子句（马尔可夫毯）
• \(n_i(x,y)\)：当变量取值为 \((X,Y)=(x,y)\) 时，第 \(i\) 个子句中为真的原子个数

马尔可夫逻辑的参数估计

生成式学习：预测联合概率似然 \(\mathrm{Pr}(x)\) \[ \mathrm{Pr}_w(X=x)=\frac{1}{Z}\exp\left(\sum_{i\in F} w_i n_i (x)\right) \] 参数 \(w_i\) 关于对数似然函数的梯度 \[ \frac{\partial}{\partial w_i}\log\mathrm{Pr}_w(X=x) = n_i(x) - \sum_{x'}\mathrm{P}_w(X=x')n_i(x') \]

马尔可夫逻辑的参数估计

对于含递归规则的一阶概率逻辑问题来说
基于 MCMC （如 Gibbs 采样）的推理基本很难在短时间内收敛

伪似然函数

伪似然函数

参数 \(w_i\) 关于对数伪似然函数的梯度

• \(n_i(x_{[X_l=0]})\)：在第 \(i\) 个子句中令 \(X=x\) 并强行设置 \(X_l=0\) 时真原子的个数

Max-margin Learning

对于判别式学习，除了之间最大化条件对数似然函数，还可以最大化如下“margin”： \[ \frac{\mathrm{Pr}_\mathbf{w}(y|x)}{\mathrm{Pr}_\mathbf{w}(\hat{y}|x)} \]

• 其中 \(\hat{y}\) 是参数 \(\mathbf{w}\) 下随机变量 \(Y\) 除了 \(y\) 以外最可能的赋值： \[\hat{y}=\mathop{\arg\max}\limits_{\bar{y}\in Y\backslash y}\mathrm{Pr}_\mathbf{w}(\bar{y}\mid x)\]

ProbLog 中的参数学习

一阶 ProbLog 的概率分布函数： \[ \mathrm{Pr}(L\mid\mathcal{T})=\prod_{f_n \theta_{n,k}\in L} p_n \prod_{f_n \theta_{n,k}\in L_\mathcal{T}\backslash L} (1-p_n) \] 其中

• \(\{\theta_{n,1},\ldots, \theta_{n,K}\}\) 是第 \(n\) 个一阶概率原子的所有可能变量替换
• \(\mathcal{T}=\mathcal{F}\cup\mathcal{BK}=\{p_1::f_1,\ldots p_N::f_N\}\cup \mathcal{BK}\) 为 ProbLog 程序，其中 \(p_i::f_i\) 为概率原子公式，\(BK\) 是一阶逻辑程序
• 概率原子公式及它们的变量替换定义了一个在其 Herbrand Universe \(L_\mathcal{T}=\{f_1 \theta_{1,1},\ldots, f_1 \theta_{1,K_1},\ldots,f_N \theta_{N,1},\ldots, f_N \theta_{N,K_N}\}\) 上的分布语义

ProbLog 中的参数学习

概率事实 \(\mathcal{F}\)

0.1::burglary.
0.2::earthquake.
0.7::heard(X).

一阶知识库 \(\mathcal{BK}\)

person(mary).
person(john).
alarm :- burglary; earthquake.
calls(X) :- person(X), alarm, heard(X).

\(\mathcal{F}\) 构成的Herbrand Universe 为：

heard(mary), heard(john), burglary, earthquake

ProbLog 中的“解释”

0.1::burglary.
0.2::earthquake.
0.7::heard(X).
person(mary).
person(john).
alarm :- burglary; earthquake.
calls(X) :- person(X), alarm, heard(X).

部分解释（partial interpretation）

\[ \mathrm{Pr}_w((I^+, I^-))=0.1\times 0.7\times(1-0.7)\times\underbrace{(0.2+(1-0.2))}_{\text{earthquake}} \]

LFI-Problog

Learning from Interpretation：

• 从部分或完整观测数据（即证据包含部分/全部 groundings）中学习。

本质上，LFI 是一种最大似然估计：

其中，

• 训练数据 \(\mathcal{D}=\{I_1, \ldots, I_M\}\) 所有 Interpretation 的集合
• \(\theta=\{p_1, p_2, \ldots, p_n\}\) 为所有概率事实的权重

LFI-Problog

LFI-Problog

当 \(\mathcal{D}\) 中的训练数据为“部分解释”时：

• \(I_m\) 中包含隐变量（无真值指派的 groundings）
• 通过 EM 算法求解

\begin{equation*} \hat{p}_n^{(i+1)}=\frac{1}{Z_n}\sum_{m=1}^M \sum_{k=1}^{K^m_n} \mathrm{Pr}_ {\mathcal{T}_\hat{\mathbf{p}}^{(i)}}\left[f_{n,k}\mid I_m \right] \end{equation*}

其中计算期望的步中需要将 \(I_m\) 编译为 d-DNNF 来推理隐变量的边际概率。

LFI-Problog

LFI-Problog

概率规则学习

结构学习的一般框架

Beam search

Kok and Domingos, ICML’05

function Markov_Structure_Learning
    while beam ≠ ∅
        add unit clauses to beam
        while beam has changed
            for each clause c ∈ beam
                c' ← add a literal to c
                newClauses ← newClauses ∪ c'
            end
            beam ← k best clauses in beam ∪ newClauses
        end
        add best clause in beam to MLN
    end
end

Relational Path Finding

Richards and Mooney, AAAI’92

• 将常元看作图中的点、谓词看作边
• 多个原子公式的合取看作一条路径

advises(pete, sam), teaches(pete, cs1), tas(sam, cs1).

advises(X, Y), teaches(X, Z), tas(Y, Z).

BUSL

Mihalkova and Mooney, ICML’07

• 利用 relational pathfinding 找到数据中的短路径并泛化
• 将这些路径作为布尔变量 \(\rightarrow\) 马尔可夫网中的节点
• 连接这些节点，形成团簇（cliques）
  • 将团簇重构为子句形式
• 对子句打分，并加入模型

BUSL

例如在上面的例子中，可先找到长度小于 2 的短路径

[advises(pete, sam), teaches(pete, cs1)], [tas(sam, cs1)].

利用 Lifting 技术剪枝

Kok and Domingos, ICML’09; ICML’10

• 利用 relational pathfinding 找到 ground paths
• 根据 ground paths 的结构对领域中的常元进行聚类
• 用 random walk 找到图中具有代表性的子结构
  • 常见子图
  • 对称路径
  • …

其他方法

小结

概率逻辑系统

1. 真度与概率的区别
2. KBMC：从概率出发，引入逻辑
   • 只做概率推断
   • 借助逻辑知识结构来建模联合概率分布
3. 分布语义：从逻辑出发，引入概率
   • 同时进行概率和逻辑推理
   • 概率分布从哪来？