符号学习简介

概率逻辑系统

(Press ? for help, n and p for next and previous slide)

戴望州

南京大学人工智能学院
2022年-春季

https://daiwz.net

路径图

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

从非经典逻辑到概率逻辑
KBMC
分布语义

“真度”与“概率”

如果雨下的越大，身上打湿得越厉害。

“真度”与“概率”

\[rain\rightarrow wet\]

其中 \(rain\) 和 \(wet\) 均为 fuzzy set

“真度”与“概率”

确定规则：

若身上某处淋到雨，则该处被打湿

“真度”与“概率”

确定规则：

若身上每处都淋到雨，则全身被打湿

“真度”与“概率”

概率事实：

\(0.8\):: 身上每处都淋到雨

“真度”与“概率”

\begin{eqnarray*} &&\text{身上每处都淋到雨}\rightarrow\text{全身被打湿}\\ &0.8::&\text{身上每处都淋到雨}\\ \hline &0.8::&\text{全身被打湿} \end{eqnarray*}

概率逻辑的语义

0.8::身上每处都淋到雨 被称为概率原子公式，它表示：

\[ \mathrm{Pr}\left(v(\text{身上每处都淋到雨})=True\right)=0.8 \]

其中 \(v\) 为赋值函数。为了简便起见，一般省略该函数将 \(P(v(a)=True)\) 记为 \(P(a)\)。

概率逻辑的语义

逻辑连接词的概率语义是什么：

\(\mathrm{Pr}(a\wedge b)=?\)
\(\mathrm{Pr}(a\vee b)=?\)
\(\mathrm{Pr}(\neg a)=?\)
\(\mathrm{Pr}(a\rightarrow b)=?\)

概率关系逻辑解释是什么：

\(\mathrm{Pr}(a\mid b)=?\)
\(\mathrm{Pr}(a,b)=?\)

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

从非经典逻辑到概率逻辑
KBMC
分布语义

基于知识的模型构建

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

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

贝叶斯决策系统（Bayesian Decision Theory）：

事件构成的集合：
- 原因事件（causation, support）
- 结果事件（outcome, decision）
事件之间条件概率关系和概率分布，称为模型
结果事件间的优先级

贝叶斯网

图中的条件概率分布：\(\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)\)

贝叶斯网

有向无环图（directed acyclic graph, DAG）
每条有向边代表一个条件概率关系
子节点与其所有父节点构成一个条件概率分布
联合概率分布由所有条件概率分布组成

贝叶斯网的概率分布函数

给定一个图模型为 \(G=(V,E)\) 的贝叶斯网，其中 \(V\) 为节点（随机变量）集合、\(E\) 为有向边集合，那么所有随机变量的联合概率分布为： \[ \mathrm{Pr}(X) =\prod_{v\in V}\mathrm{Pr}(X_v \mid \mathbf{X}_{\mathrm{pa}(v)})\ \] 其中 \(X_v\) 是 \(v\) 的随机变量取值，\(\mathrm{pa}(v)\) 为 \(v\) 的全部父节点集合。

知识在概率模型中的作用

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

例如：计算 \(n\) 个布尔随机变量构成的联合概率分布 \(\mathrm{Pr}(X_1, X_2, X_3, \ldots, X_n)\)

样本空间大小为 \(2^n\)
计算 \(X_i\) 为真的概率（边际概率）需要对 \(2^{n-1}\) 个事件的概率值求和： \[\mathrm{Pr}(X_i)=\sum_{x_{j\neq i}}\mathrm{Pr}(X_1, X_2, \ldots, X_n)\]

知识可以描述随机变量间的独立关系，对联合概率进行分解

蕴涵的语义

\begin{equation*} \mathrm{Pr}(H\leftarrow B_1 \wedge B_2 \wedge\ldots\wedge B_n)\triangleq\mathrm{Pr}(H\mid B_1, B_2, \ldots, B_n) \end{equation*}

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\)

条件独立性

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

条件独立性

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

条件独立性

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

条件独立性

定义：对于三个随机变量集合 \(\mathcal{X}\), \(\mathcal{Y}\), \(\mathcal{C}\)，若对于任意 \((X,Y)\in\mathcal{X}\times\mathcal{Y}\)，\(\mathcal{C}\) 均阻挡了从 \(X\) 至 \(Y\) 的路径，则 \(\mathcal{X}\bot\!\!\!\bot \mathcal{Y}\mid\mathcal{C}\)。我们也称任意 \(\mathcal{X}\) 中的节点与 \(\mathcal{Y}\) 中的节点被 \(\mathcal{C}\) D-分离。

定义：以下两种情况我们称 \(\mathcal{C}\) 均阻挡了路径 \(\mathcal{P}\)：

\(\mathcal{P}\) 中存在一个碰撞点（collider） \(\bigcirc\rightarrow D\leftarrow\bigcirc\)，且 \(D\) 与它的后代均不属于 \(\mathcal{C}\)；
\(\mathcal{P}\) 中存在一个非碰撞点 \(C\in\mathcal{C}\)。

条件独立性

\(A \bot\!\!\!\bot B\)？
\(A \bot\!\!\!\bot B\mid C\)？
\(A \bot\!\!\!\bot B\mid D\)？
\(A \bot\!\!\!\bot D\)？
\(A \bot\!\!\!\bot D\mid C\)？

贝叶斯网的表达能力

\begin{eqnarray*} &&\mathrm{Pr}(A,B,C,D,H)=\\ &&\hspace{2em}\mathrm{Pr}(A)\mathrm{Pr}(D)\mathrm{Pr}(B\mid A,H)\mathrm{Pr}(C\mid D,H)\mathrm{Pr}(H) \end{eqnarray*}

\(\{A\} \bot\!\!\!\bot \{C,D\}\)
\(\{A,B\} \bot\!\!\!\bot \{D\}\)

贝叶斯网的表达能力

如果将 \(H\) 边际化：

\begin{eqnarray*} &&\mathrm{Pr}(A,B,C,D)=\\ &&\hspace{2em}\mathrm{Pr}(A)\mathrm{Pr}(D)\sum_H \mathrm{Pr}(B\mid A,H)\mathrm{Pr}(C\mid D,H)\mathrm{Pr}(H) \end{eqnarray*}

还能用贝叶斯网的结构保持以下性质吗？

\(\{A\} \bot\!\!\!\bot \{C,D\}\)
\(\{A,B\} \bot\!\!\!\bot \{D\}\)

马尔可夫网

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

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

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

右图的联合概率分布定义如下： \[ \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

马尔可夫网中的条件独立

贝叶斯网中的条件概率 \[\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*}

合取的语义

\begin{equation*} \mathrm{Pr}(A\wedge B \wedge C)\propto \phi_{ABC}(A,B,C) \end{equation*}

析取的语义

\begin{equation*} \mathrm{Pr}(A\vee B \vee C)\propto \phi_{ABC}(A,B,C) \end{equation*}

蕴涵的语义

\begin{equation*} \mathrm{Pr}(A\leftarrow B \wedge C)\propto \phi_{ABC}(A,B,C) \end{equation*}

马尔可夫逻辑网

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

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

马尔可夫逻辑网

马尔可夫逻辑网的概率分布函数： \[ \mathrm{Pr}(\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) \]

\(\mathbf{X}\) 为所有命题原子（随机变量）的集合
\(\phi_i\) 为第 \(i\) 个公式的势函数，是一个指数函数
- \({\color{var(--zenburn-red)}{w_i}}\) 为第 \(i\) 个命题公式的权重
- \({\color{var(--zenburn-blue)}{n_i }}(\mathbf{X})\) 是随机变量取值为 \mathbf{X} 时，命题公式 \(i\) （子句形式）中为真的原子命题个数

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

从非经典逻辑到概率逻辑
KBMC
分布语义

用逻辑来表达概率

公式 \(\varphi\) 为真的概率至少为 \(\frac{1}{2}\) \[w(\varphi)\geq\frac{1}{2}\]

用逻辑来表达概率

公式 \(\varphi_1\) 为真的概率至少为 \(\varphi_2\) 的两倍 \[w(\varphi_1)\geq2w(\varphi_2)\]

用逻辑来表达概率

\[M\models a_1 w(\varphi_1)+\ldots +a_k w(\varphi_k)\geq c\]

用逻辑来表达概率

\(M\) 是什么？

概率空间

概率空间是一个三元组 \((\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\}\)

概率逻辑结构的语义

定义：对于 \(p\in\Phi\) 和它们组成的公式 \(\varphi\)：

\(p^M=\{s\in\Omega\mid\pi(s)(p)=True\}\)
\(\varphi^M=\{s\in\Omega\mid\pi(s)(\varphi)=True\}\)
\(w^M(p)=\mu(p^M)\)
\(w^M(\varphi)=\mu(\varphi^M)\)

概率逻辑结构的语义

\[ M\models a_1 w(\varphi_1)+\ldots +a_k w(\varphi_k)\geq c \] 当且仅当 \[ a_1 w^M(\varphi_1)+\ldots +a_k w^M(\varphi_k)\geq c \]

基于可能世界的推理

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

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

这种概率逻辑语义被称为“分布语义”（Distribution Semantics）

分布语义的公理系统

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

命题逻辑公理
- 所有命题逻辑重言式
- MP 规则
关于线性不等式的一切重言式
关于概率论的公理：
- \(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\) 是一个命题逻辑中的重言式

该公理系统可靠（sound）且完备（complete）

概率逻辑程序的例子

%% 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).

小结

概率逻辑系统

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