符号学习简介
概率逻辑推断
(Press ? for help, n and p for next and previous slide)
路径图
符号学习简介・概率逻辑推断
- 图模型推断
- 从 SAT 到 WMC
- 知识编译
统计关系模型
Startistical Relational AI (StaRAI) 的本质是将 ground rules 转换为布尔随机变量构成的概率图模型（Probabilistic Graphical Model, PGM）。
PGM 中的推理
统计推断（Statistical Inference）：
- 通过基于概率分布的计算来回答关于领域的问题。
- \(\mathrm{Pr}(x=1\mid y=4, z=3)\) 的概率是多少？
- \(\mathrm{Pr}(x, y)\) 联合概率分布中最可能出现的 \((X,Y)\) 是什么？
- 联合概率分布 \(\mathrm{Pr}(x,y,z)\) 的熵是多少？
- 明天大盘下跌的概率是多少？
消元法
计算如下边际概率：
\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*}
消元的次序
计算如下边际概率：
\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*}
如果我们按照 \(e,c,b,g,a,d\) 的次序进行消元： \[ \mathrm{Pr}({\color{var(--zenburn-red)}{f}})=\sum_d \mathrm{Pr}(f\mid d)\sum_a \mathrm{Pr}(a)\sum_g \sum_b \mathrm{Pr}(d\mid a,b)\mathrm{Pr}(b)\sum_c \mathrm{Pr}(c\mid a)\sum_e \mathrm{Pr}(g\mid d,e)\mathrm{Pr}(e) \]
消元的次序
计算如下边际概率：
\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*}
如果我们按照 \(g,c,e,d,b,a\) 的次序进行消元： \[ \mathrm{Pr}({\color{var(--zenburn-red)}{f}})=\sum_a \mathrm{Pr}(a)\sum_b \mathrm{Pr}(b)\sum_d \mathrm{Pr}(f\mid d)\mathrm{Pr}(d\mid a,b)\underbrace{\sum_c \mathrm{Pr}(c\mid a)\underbrace{\sum_e \mathrm{Pr}(e)\underbrace{\sum_g \mathrm{Pr}(g\mid d,e)}_{=1}}_{=1}} _{=1} \]
消息传递
将边际概率看作“消息传递”（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)\)
计算 \(\mathrm{Pr}(a=0)=?\)：
- 第一种方式：直接计算 \(\mathrm{Pr}(a=0)=\sum_{b,c,d}\mathrm{Pr}(a=0\mid b)\mathrm{Pr}(b\mid c)\mathrm{Pr}(c\mid d)\mathrm{Pr}(d)\)
- 共需要计算 \(7\) 次求和。
- 第二种方式：将求和操作分解
- 先将 \(d\) 推进去：
\[\mathrm{Pr}(a=0)=\sum_{b,c}\mathrm{Pr}(a=0\mid b)\mathrm{Pr}(b\mid c)\underbrace{\color{var(--zenburn-blue)}{\sum_d {\mathrm{Pr}(c\mid d) \mathrm{Pr}(d)}}}_{\gamma_d(c)}\]
- 对于 \(\gamma_d(c)\) 需要计算 \(2\) 次求和。
- 先将 \(d\) 推进去：
\[\mathrm{Pr}(a=0)=\sum_{b,c}\mathrm{Pr}(a=0\mid b)\mathrm{Pr}(b\mid c)\underbrace{\color{var(--zenburn-blue)}{\sum_d {\mathrm{Pr}(c\mid d) \mathrm{Pr}(d)}}}_{\gamma_d(c)}\]
消息传递
- 先将 \(\sum_d\) 推进去：
\[\mathrm{Pr}(a=0)=\sum_{b,c}\mathrm{Pr}(a=0\mid b)\mathrm{Pr}(b\mid c)\underbrace{\color{var(--zenburn-blue)}{\sum_d {\mathrm{Pr}(c\mid d) \mathrm{Pr}(d)}}}_{\gamma_d(c)}\]
- 对于 \(\gamma_d(c)\) 需要计算 \(2\) 次求和。
- 再将 \(\sum_c\) 推进去：
\[\mathrm{Pr}(a=0)=\sum_{b}\mathrm{Pr}(a=0\mid b)\underbrace{\color{var(--zenburn-blue)}{\sum_c {\mathrm{Pr}(b\mid c)\gamma_d(c)}}}_{\gamma_c(b)}\]
- 对于 \(\gamma_c(b)\) 需要计算 \(2\) 次求和。
- 最后将 \(\sum_b\) 推进去：
\[\mathrm{Pr}(a=0)=\underbrace{\color{var(--zenburn-blue)}{\sum_b {_{}\mathrm{Pr}(a=0\mid b)\gamma_c(b)}}}_{\gamma_b(a)}\]
- 对于 \(\gamma_b(a)\) 需要计算 \(1\) 次求和。
消息传递
\begin{equation*}
\mathrm{Pr}(a=0)=\underbrace{\sum_{b}\mathrm{Pr}(a=0\mid b)\underbrace{\sum_c \mathrm{Pr}(b\mid c)\underbrace{\sum_d {\mathrm{Pr}(c\mid d) \mathrm{Pr}(d)}}_{\gamma_d(c)}}_{\gamma_c(b)}}_{\gamma_b(a)}
\end{equation*}
消元法
- 消元法可看作一种消息传递：
- 每消去一个随机变量 \(=\) 将关于该变量的信息汇总，传递给相邻变量
- 对于长度为 \(T+1\) 的马尔可夫链：
- 第一种方式需要 \(2^T-1\) 求和运算（指数级）
- 第二种方式只需 \(2T-1\) 次求和运算（线性）
- 被传递的消息：
- 每一步只从一个节点 \(i\) 传到另一个节点 \(j\)
- 消息 \(\gamma_i(j)\) 通常可看作未归一化的势函数
因子图
图模型中用方形节点表示其相邻节点随机变量构成的因子（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)}}\]
边界因子（无输入邻居变量）的信息为其本身。
Sum-Product 算法的例子
\[
\mathrm{Pr}(a,b,c,d)\propto f_1(a,b)f_2(b,d)f_3(b,c)f_4(c)
\]
| \(a\) | \(b\) | \(f_1(a,b)\) |
|---|---|---|
| \(0\) | \(0\) | \(10\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(10\) |
| \(b\) | \(d\) | \(f_2(b,d)\) |
|---|---|---|
| \(0\) | \(0\) | \(10\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(10\) |
| \(b\) | \(c\) | \(f_3(b,c)\) |
|---|---|---|
| \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(10\) |
| \(1\) | \(0\) | \(10\) |
| \(1\) | \(1\) | \(1\) |
| \(c\) | \(f_4(c)\) |
|---|---|
| \(0\) | \(10\) |
| \(1\) | \(1\) |
Sum-Product 算法的例子
\[
\mathrm{Pr}(a,b,c,d)\propto f_1(a,b)f_2(b,d)f_3(b,c)f_4(c)
\]
| \(a\) | \(b\) | \(f_1(a,b)\) |
|---|---|---|
| \(0\) | \(0\) | \(10\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(10\) |
| \(b\) | \(d\) | \(f_2(b,d)\) |
|---|---|---|
| \(0\) | \(0\) | \(10\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(10\) |
| \(b\) | \(c\) | \(f_3(b,c)\) |
|---|---|---|
| \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(10\) |
| \(1\) | \(0\) | \(10\) |
| \(1\) | \(1\) | \(1\) |
| \(c\) | \(f_4(c)\) |
|---|---|
| \(0\) | \(10\) |
| \(1\) | \(1\) |
Sum-Product 算法的例子
- 选择一个根节点（root）
- 初始化
- 从叶子因子节点出发的消息即为因子本身；
- 从叶子变量节点出发的消息为 \(1\)；
- 从叶子开始将消息传递至根节点；
- 从根节点再将消息传回叶子节点；
信念传播・Max-Product
我们也可以用信念传播算法来计算
\[X=\mathop{\arg\max}\limits_{X\in\mathcal{X}}\prod_f\phi(\mathcal{X}_f)\]
信念传播・Max-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)}}=\max_{\{v_i\}}f(v,\{v_i\})\prod_{v_i \sim f\backslash v}{\color{var(--zenburn-blue)}{ \mu_{v_i \rightarrow f}(v_i)}}\]
边界因子（无输入邻居变量）的信息为其本身。
Max-Product 的直观例子
\[
\mathrm{Pr}(a,b,c,d)\propto f_1(a,b)f_2(b,d)f_3(b,c)f_4(c)
\]
| \(a\) | \(b\) | \(f_1(a,b)\) |
|---|---|---|
| \(0\) | \(0\) | \(10\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(10\) |
| \(b\) | \(d\) | \(f_2(b,d)\) |
|---|---|---|
| \(0\) | \(0\) | \(10\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(10\) |
| \(b\) | \(c\) | \(f_3(b,c)\) |
|---|---|---|
| \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(10\) |
| \(1\) | \(0\) | \(10\) |
| \(1\) | \(1\) | \(1\) |
| \(c\) | \(f_4(c)\) |
|---|---|
| \(0\) | \(10\) |
| \(1\) | \(1\) |
Max-Product 算法的例子
- 选择一个根节点（root）
- 初始化
- 从叶子因子节点出发的消息即为因子本身；
- 从叶子变量节点出发的消息为 \(1\)；
- 从叶子开始将消息传递至根节点；
- 从根节点再将消息传回叶子节点；
Max-Product 算法的例子
消息 1：初始化为 \(1\)
\begin{eqnarray*} \mu_{a\rightarrow f_1}(a) &= &1\\ \mu_{a\rightarrow f_1}(0) &= &1\\ \mu_{a\rightarrow f_1}(1) &= &1 \end{eqnarray*}消息 2：初始化为 \(1\)
\begin{eqnarray*} \mu_{d\rightarrow f_2}(d) &= &1\\ \mu_{d\rightarrow f_2}(0) &= &1\\ \mu_{d\rightarrow f_2}(1) &= &1 \end{eqnarray*}
Max-Product 算法的例子
- 消息 3：
\begin{eqnarray*}
\mu_{f_1\rightarrow b}(b) &= &\max_a f_1(a,b)\cdot\mu_{a\rightarrow f_1}(a)\\
&=&\max(f_1 (a=0,b)\cdot\mu_{a\rightarrow f_1}(0), f_1 (a=1,b)\cdot\mu_{a\rightarrow f_1}(1))\\
\mu_{f_1\rightarrow b}(0) &= &\max_a f_1(a,b=0)\cdot\mu_{a\rightarrow f_1}(a)\\
&=&\max(\underbrace{f_1 ({\color{var(--zenburn-red)}{a=0}},b=0)}_{10}\cdot\underbrace{\mu_{a\rightarrow f_1}(0)}_{1}, \underbrace{f_1 (a=1,b=0)}_{1}\cdot\underbrace{\mu_{a\rightarrow f_1}(1)}_{1})\\
&=& 10\\
\mu_{f_1\rightarrow b}(1) &= &\max_a f_1(a,b=1)\cdot\mu_{a\rightarrow f_1}(a)\\
&=&\max(\underbrace{f_1 (a=0,b=1)}_{1}\cdot\underbrace{\mu_{a\rightarrow f_1}(0)}_{1}, \underbrace{f_1 ({\color{var(--zenburn-red)}{a=1}},b=1)}_{10}\cdot\underbrace{\mu_{a\rightarrow f_1}(1)}_{1})\\
&=& 10
\end{eqnarray*}
Max-Product 算法的例子
- 消息 4：
\begin{eqnarray*}
\mu_{f_2\rightarrow b}(b) &= &\max_a f_2(b,d)\cdot\mu_{d\rightarrow f_2}(d)\\
&=&\max(f_2 (b,d=0)\cdot\mu_{d\rightarrow f_2}(0), f_2 (b,d=1)\cdot\mu_{d\rightarrow f_2}(1))\\
\mu_{f_2\rightarrow b}(0) &= &\max_d f_2(b=0,d)\cdot\mu_{d\rightarrow f_1}(d)\\
&=&\max(\underbrace{f_2 (b=0,{\color{var(--zenburn-red)}{d=0}})}_{10}\cdot\underbrace{\mu_{d\rightarrow f_2}(0)}_{1}, \underbrace{f_2 (b=0,d=1)}_{1}\cdot\underbrace{\mu_{d\rightarrow f_2}(1)}_{1})\\
&=& 10\\
\mu_{f_2\rightarrow b}(1) &= &\max_d f_2(b=1,d)\cdot\mu_{d\rightarrow f_2}(d)\\
&=&\max(\underbrace{f_2 (b=1,d=0)}_{1}\cdot\underbrace{\mu_{d\rightarrow f_2}(0)}_{1}, \underbrace{f_2 ({b=1,\color{var(--zenburn-red)}{d=1}})}_{10}\cdot\underbrace{\mu_{d\rightarrow f_2}(1)}_{1})\\
&=& 10
\end{eqnarray*}
Max-Product 算法的例子
消息 5：将消息 3 和 消息 4 相乘
\begin{eqnarray*} \mu_{b\rightarrow f_2}(b) &= &\mu_{f_1 \rightarrow b}(b)\cdot\mu_{f_2 \rightarrow b}(b)\\ \mu_{b\rightarrow f_2}(0) &= &\underbrace{\mu_{f_1 \rightarrow b}(0)}_{10}\cdot\underbrace{\mu_{f_2 \rightarrow b}(0)}_{10}=100\\ \mu_{b\rightarrow f_2}(1) &= &\underbrace{\mu_{f_1 \rightarrow b}(1)}_{10}\cdot\underbrace{\mu_{f_2 \rightarrow b}(1)}_{10}=100 \end{eqnarray*}
Max-Product 算法的例子
- 消息 6：
\begin{eqnarray*}
\mu_{f_3\rightarrow c}(c) &= &\max_b f_3(b,c)\cdot\mu_{b\rightarrow f_3}(b)\\
&=&\max(f_3 (b,c=0)\cdot\mu_{b\rightarrow f_3}(0), f_3 (b,c=1)\cdot\mu_{b\rightarrow f_3}(1))\\
\mu_{f_3\rightarrow c}(0) &= &\max_b f_3(b,c=0)\cdot\mu_{b\rightarrow f_3}(b)\\
&=&\max(\underbrace{f_3 (b=0,c=0)}_{1}\cdot\underbrace{\mu_{b\rightarrow f_3}(0)}_{100}, \underbrace{f_3 ({\color{var(--zenburn-red)}{b=1}},c=0)}_{10}\cdot\underbrace{\mu_{b\rightarrow f_3}(1)}_{100})\\
&=& 1000\\
\mu_{f_3\rightarrow c}(1) &= &\max_b f_3(b,c=1)\cdot\mu_{b\rightarrow f_3}(b)\\
&=&\max(\underbrace{f_3 ({\color{var(--zenburn-red)}{b=0}},c=1)}_{10}\cdot\underbrace{\mu_{b\rightarrow f_3}(0)}_{100}, \underbrace{f_3 (b=1,c=1)}_{1}\cdot\underbrace{\mu_{b\rightarrow f_3}(1)}_{100})\\
&=& 1000
\end{eqnarray*}
Max-Product 算法的例子
消息 7：
\begin{eqnarray*} \mu_{c\rightarrow f_4}(c) &= &\mu_ {f_3 \rightarrow c}(c)\\ \mu_{c\rightarrow f_4}(0) &= &\mu_ {f_3 \rightarrow c}(0)=1000\\ \mu_{c\rightarrow f_4}(1) &= &\mu_ {f_3 \rightarrow c}(1)=1000 \end{eqnarray*}消息 8：初始化为 \(f_4\)
\begin{eqnarray*} \mu_{f_4\rightarrow c}(c) &= &f_4(c)\\ \mu_{f_4\rightarrow c}(c=0) &= &f_4(c=0)=10\\ \mu_{f_4\rightarrow c}(c=1) &= &f_4(c=1)=1 \end{eqnarray*}
Max-Product 算法的例子
消息 8：计算边际概率：
\begin{eqnarray*} c^* &= &\mathop{\arg\max}\limits_b \mu_{f_4\rightarrow c}(c)\cdot\mu_{f_3\rightarrow c}(c)\\ &=&\mathop{\arg\max}\limits_b (\underbrace{\mu_{f_4\rightarrow c}(c=0)}_{10}\cdot\underbrace{\mu_{f_3\rightarrow c}(c=0)}_{1000}, \underbrace{\mu_{f_4\rightarrow c}(c=1)}_{1}\cdot\underbrace{\mu_{f_3\rightarrow c}(c=1)}_{1000})\\ &=& 0 \end{eqnarray*}消息 9 & 10：根据 \(c^*=0\) 开始回溯
\begin{eqnarray*} \mu_ {f_3 \rightarrow c}(0)&=&\max_b f_3(b,c=0)\cdot \mu_{b\rightarrow f_3}(b)\\ &=&\max(\underbrace{f_3 (b=0,c=0)}_{1}\cdot\underbrace{\mu_{b\rightarrow f_3}(0)}_{100}, \underbrace{f_3 ({\color{var(--zenburn-red)}{b=1}},c=0)}_{10}\cdot\underbrace{\mu_{b\rightarrow f_3}(1)}_{100})\\ &\Rightarrow& b^*=1& \end{eqnarray*}
Max-Product 算法的例子
消息 11-14：根据 \(b^*=1\) 开始回溯
\begin{eqnarray*} \mu_{f_2\rightarrow b}(1) &= &\max_d f_2(b=1,d)\cdot\mu_{d\rightarrow f_2}(d)\\ &=&\max(\underbrace{f_2 (b=1,d=0)}_{1}\cdot\underbrace{\mu_{d\rightarrow f_2}(0)}_{1}, \underbrace{f_2 ({b=1,\color{var(--zenburn-red)}{d=1}})}_{10}\cdot\underbrace{\mu_{d\rightarrow f_2}(1)}_{1})\\ &=&10\\ &\Rightarrow& d^*=1\\ \mu_{f_1\rightarrow b}(1) &= &\max_a f_1(a,b=1)\cdot\mu_{a\rightarrow f_1}(a)\\ &=&\max(\underbrace{f_1 (a=0,b=1)}_{1}\cdot\underbrace{\mu_{a\rightarrow f_1}(0)}_{1}, \underbrace{f_1 ({\color{var(--zenburn-red)}{a=1}},b=1)}_{10}\cdot\underbrace{\mu_{a\rightarrow f_1}(1)}_{1})\\ &=&10\\ &\Rightarrow& a^*=1 \end{eqnarray*}
关于信念传播算法的补充
- 处理证据（evidence）
- 有有观测值作为证据 \(x=e\) 时引入指示函数，令 \(\delta(x,e)=1\) 且 \(\delta(x,e')=0\)，其中 \(e\neq e'\)。
- 归一化系数（配分函数） \[Z=\sum_{\mathcal{X}}\prod_f\phi_f(\mathcal{X}_f)\] 即所有节点收到邻居因子传来的全部信息总和： \[Z=\sum_x \prod_{f\in ne(x)} \mu_{f\rightarrow x}(x)\]
- 关于图中的回路
- 若无回路（因子图为树），算法复杂度是线性的；
- 若出现回路，信念传播仍然可以当作一种近似算法；
- 也可以通过 Loop-cut 技术将环路消除；
关于信念传播算法的补充
- \(\max\prod\) 和 \(\sum\prod\) 其实是类似的
- 由于这两组运算可分配，它们构成了半环（semi-ring）
- 自定义不同的半环，可以实现不同类型的推断
- 非半环无法采用信念传播进行推断，例如 \(\max\sum\)
- 利用对数
- 当网络特别庞大时，消息的乘积可能会变得非常小；
- 实现时一般采用 \(\lambda=\log\mu\) 和求和来代替乘积。
符号学习简介・概率逻辑推断
- 图模型推断
- 从 SAT 到 WMC
- 知识编译
可满足性问题（SAT）
可满足性问题（SAT）
输入：
- 一组布尔变量集合（游戏中的 \(1,\ldots,9\)）
- 一组形如 \(l_1 \vee \ldots \vee l_k\) 的子句（在游戏中 \(k=3\)，因此它是 \(3\)-SAT），其中每个文字 \(l_i\) 是布尔变量或其否定形式
输出：
- 对所有布尔变量的一个真值指派，使得它能够满足（satisfies）所有子句
可满足性问题（SAT）
例如，下列两个子句：
\begin{eqnarray*}
A\vee B\vee C&\\
\neg A\vee \neg B\vee \neg C&\\
\end{eqnarray*}
存在一组解（一个模型）为： \[A=True, B=False, C=True\] 许多时候我们面对的是更一般形式的逻辑表达式，而不仅仅是 \(k\)-CNF（conjunctive normal form，合析范式）
| \(A\) | \(B\) | \(C\) | SAT? |
|---|---|---|---|
| 0 | 0 | 0 | No |
| 0 | 0 | 1 | Yes |
| 0 | 1 | 0 | Yes |
| 0 | 1 | 1 | Yes |
| 1 | 0 | 0 | Yes |
| 1 | 0 | 1 | Yes |
| 1 | 1 | 0 | Yes |
| 1 | 1 | 1 | No |
模型计数（model counting）：一个逻辑理论（规则集）拥有多少个模型？6
可满足性问题（SAT）
- 是计算机科学中最基础的问题之一
- 是可计算理论的基石之一，号称“NP 之壁”
- 许多问题能够归约为 SAT，例如规划（planning）、约束求解（constraint solving）、验证（verification）……
- 大型 SAT 问题依然是计算机科学面临解决的核心问题之一，每年都有竞赛，且 SotA 榜一直在更新
- SAT 可以拓展至其他领域，例如模型计数、贝叶斯网中的概率推断等等。
贝叶斯网与 SAT
- 能不能将 SAT 问题转换为一个贝叶斯网推断问题？
- 考虑如下的例子： \[(\neg A\vee B)\wedge(\neg B\vee C)\wedge(A\vee C)\]
贝叶斯网与 SAT
\[(\neg A\vee B)\wedge(\neg B\vee C)\wedge(A\vee C)\]
- 给 \(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：若每个模型拥有不同的权重，计数所得的权重是多少？
从 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
\[(\neg A\vee B)\wedge(\neg B\vee C)\wedge(A\vee C)\] \[w(A)=w(\neg A)=w(B)=w(\neg B)=w(C)=w(\neg C)=0.5\]
| \(A\) | \(B\) | \(C\) | 模型？ | 权重 | \(wmc(T)\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | \(0.5^3\) | \(0\) |
| 0 | 0 | 1 | 1 | \(0.5^3\) | \(0.5^3\) |
| 0 | 1 | 0 | 0 | \(0.5^3\) | \(0\) |
| 0 | 1 | 1 | 1 | \(0.5^3\) | \(0.5^3\) |
| 1 | 0 | 0 | 0 | \(0.5^3\) | \(0\) |
| 1 | 0 | 1 | 0 | \(0.5^3\) | \(0\) |
| 1 | 1 | 0 | 0 | \(0.5^3\) | \(0\) |
| 1 | 1 | 1 | 1 | \(0.5^3\) | \(0.5^3\) |
DPLL 算法回顾
function DPLL(Vars::variables, S::clauses)
if S is ∅
return 1
else if □ ∈ S
return 0
else select(v) ∈ Vars
S_t = S where v = 1 # making the variable true
S_f = S where v = 0 # making the variable false
return DPLL(Vars - {v}, S_t) + DPLL(Vars - {v}, S_f)
end
end
S为 CNF 理论，例如 \((A\vee \neg B)\wedge(C\vee D)\) 中的S为[[1,-2],[3,4]]（\(\{A\vee\neg B, C\vee D\}\)）- 单位子句（unit clause）是只有一个文字的子句，例如 \(A\) 与 \(\neg A\)
- 空子句（empty clause） \(\square\) 是没有任何文字的子句，因此它无法被任何模型满足
DPLL 算法回顾
注：图中所有分支取值左 \(0\) 右 \(1\)
DPLL 算法回顾（UP）
单位子句传播（Unit Propagation, UP）
注：图中所有分支取值左 \(0\) 右 \(1\)
DPLL 算法回顾（Caching）
利用缓存来记住之前遇到过的子公式
注：图中所有分支取值左 \(0\) 右 \(1\)
DPLL 的 #SAT 变体
function sharp_SAT(Vars::variables, S::clauses)
if S is ∅
return 2^len(Vars)
else if □ ∈ S
return 0
else select(v) ∈ Vars
S_t = S where v = 1 # making the variable true
S_f = S where v = 0 # making the variable false
return sharp_SAT(Vars - {v}, S_t) + sharp_SAT(Vars - {v}, S_f)
end
end
DPLL 的 WMC 变体
function WMC(Vars::variables, S::clauses)
if S is ∅
product = 1.0
for v ∈ Vars
product = product * (w(v) + w(not(v)))
end
return product
else if □ ∈ S
return 0
else select(v) ∈ Vars
S_t = S where v = 1 # making the variable true
S_f = S where v = 0 # making the variable false
return w(v)*WMC(Vars - {v}, S_t) + w(not(v))*sharp_SAT(Vars - {v}, S_f)
end
end
注：当权重不是概率时可能有 w(v)+w(not(v))!=1
Sum-Product 半环
上面的操作再次用到了 BP 算法中的 Sum-Product 思想：
定义：一个半环（semi-ring）是一个代数结构 \((\mathcal{A},\oplus,\otimes,e^\oplus, e^\otimes)\)，其中：
- \(\mathcal{A}\) 为半环中的元素集合
- 加法 \(\oplus\) 和乘法 \(\otimes\) 是满足结合律的二元运算
- \(\oplus\) 满足交换律
- \(\otimes\) 对加法满足分配律
- 分别存在加法和乘法的单位元 \(e^\oplus\) 和 \(e^\otimes\)
- 若 \(\otimes\) 也满足交换律，则它被称为交换半环
代数模型计数
利用半环将 sum-product 推广为更一般的 Algebraic Model Counting (AMC)
- 定义一个交换半环 \((\mathcal{A},\oplus,\otimes,e^\oplus, e^\otimes)\)
- 代数文字（algebraic literals） \[L(F)=\{f_1, \ldots, f_n\}\cup\{\neg f_1, \ldots, \neg f_n\}\]
- 标记函数（labling function） \(\alpha:L(F)\mapsto \mathcal{A}\)
- 命题逻辑理论 \(T\)： \[AMC(T)=\bigoplus_{M\models T}\bigotimes_{l\in M}\alpha(l)\]
常见的半环
A. Kimmings, G. van den Broeck, L. de Raedt, Algebraic Model Counting, 2016.
注：idp. （幂等）；neut. （中性的，\(\forall v\in\mathcal{V}\) 有 \(\alpha(v)\oplus\alpha(\neg v)=e^\otimes\)）；icp. （幂等且一致，\(\forall v\in\mathcal{V}\) 有 \(\alpha(v)\otimes\alpha(\neg v)=e^\oplus\)）
通过 WMC 进行概率推断
一共分为四个步骤：
- 将概率图模型，如贝叶斯网编码为布尔表达式
- 将布尔表达式编译为特殊的数据结构（例如 sd-DNNF）
- 将该数据结构转化为算术电路（arithmetic circuit）
- 进行概率推断
将贝叶斯网编码为 WMC 问题
| \(A\) | \(\Theta_A\) |
|---|---|
| 1 | \(\theta_A=0.3\) |
| 0 | \(\theta_A=0.7\) |
| \(A\) | \(B\) | \(\Theta_A\) |
|---|---|---|
| 1 | 1 | \(\theta_{B\mid A}=0.3\) |
| 1 | 0 | \(\theta_{\neg B\mid A}=0.7\) |
| 0 | 1 | \(\theta_{B\mid \neg A}=0.7\) |
| 0 | 0 | \(\theta_{\neg B\mid \neg A}=0.7\) |
\(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*}
将贝叶斯网编码为 WMC 问题
- 从完整的条件概率表开始（包含所有可能赋值）
- 将每个随机变量、参数都编码为一个布尔变量
- 将权重初始化为如下形式：
- \(w(A)=w(\neg A)=w(B)=w(\neg B)=1\)
- \(w(\theta_x)=\)，而 \(w(\neg \theta_x)=CPT(x)\) 为条件概率表中的原始权重
符号学习简介・概率逻辑推断
- 图模型推断
- 从 SAT 到 WMC
- 知识编译
知识编译
Knowledge Compilation： 将逻辑表达式编译为一个电路（circuit）以进行高效运算
- 编译一次，重复利用
- 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*}
知识编译
\begin{eqnarray*}
(\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))
\end{eqnarray*}
对应着：
\begin{eqnarray*}
(\mathrm{Pr}(A=true)\cdot A)\cdot((\mathrm{Pr}(B=true\mid A=true)\cdot B)+(\mathrm{Pr}(B=false\mid A=true)\cdot \neg B))+\\
(\mathrm{Pr}(A=false)\cdot \neg A)\cdot((\mathrm{Pr}(B=true\mid \neg A=true)\cdot B)+(\mathrm{Pr}(B=false\mid A=false)\cdot \neg B))
\end{eqnarray*}
当我们将 \(A, B, \neg A, \neg B\in \{0,1\}\) 代入时，即可获得欲求得的概率值。
例如，令 \(A=1, B=1\) 可得：
\begin{eqnarray*}
&&(\mathrm{Pr}(A=true)\cdot A)\cdot(\mathrm{Pr}(B=true\mid A=true)\cdot B)\\
&&=\mathrm{Pr}(A=true)\cdot\mathrm{Pr}(B=true\mid A=true)
\end{eqnarray*}
转化为算数电路
将 and 和 or 分别换成 \(\times\) 和 \(+\)，可将贝叶斯网转化为一个多项式：
\begin{eqnarray*}
&&\theta_A A(\theta_{B\mid A}B+\theta_{\neg B\mid A}\neg B)+\theta_{\neg A} \neg A(\theta_{B\mid \neg A}B+\theta_{\neg B\mid \neg A}\neg B)\\
&=&\theta_A A\theta_{B\mid A}B+\theta_A A\theta_{\neg B\mid A}\neg B+\theta_{\neg A} \neg A\theta_{B\mid \neg A}B+\theta_{\neg A} \neg A\theta_{\neg B\mid \neg A}\neg B
\end{eqnarray*}
可以看到，这里的 \(A,B,\neg A,\neg B\) 均为布尔表达式 \(\theta_x\) 的权重！
转化为算数电路
\begin{equation*}
\theta_A A\theta_{B\mid A}B+\theta_A A\theta_{\neg B\mid A}\neg B+\theta_{\neg A} \neg A\theta_{B\mid \neg A}B+\theta_{\neg A} \neg A\theta_{\neg B\mid \neg A}\neg B
\end{equation*}
计算 \(\mathrm{Pr}(A=false)\) 时，只需令权重 \(A=0,\neg A=1, B=1, \neg B=1\)
\begin{eqnarray*}
&&\mathrm{Pr}(A=false)=0+0+\theta_{\neg A} \neg A\theta_{B\mid \neg A}B+\theta_{\neg A} \neg A\theta_{\neg B\mid \neg A}\neg B\\
&=&0+0+\theta_{\neg A} \theta_{B\mid \neg A}+\theta_{\neg A} \theta_{\neg B\mid \neg A}=\theta_{\neg A}
\end{eqnarray*}
Max-Product
当需要计算 MPE（most-probable explanation）时，可编译一个 max-product 电路：
将 and 和 or 分别换成 \(\times\) 和 \(\max\)：
\[
\max(\theta_A A\cdot \max(\theta_{B\mid A}B,\theta_{\neg B\mid A}\neg B),\theta_{\neg A} \neg A\cdot\max(\theta_{B\mid \neg A}B,\theta_{\neg B\mid \neg A}\neg B))
\]
计算 \(\mathop{\arg\max}\limits_b \mathrm{Pr}(A=false, B=b)\) 时，只需令权重 \(A=0,\neg A=1, B=1, \neg B=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)\)
- 因为权重可以重新设置，算数电路可被用于多次重复运算
- 仅需要编译一次（花费较高），但以后每次推断速度都很快
- 可类比于信念传播，完成传播后可获得所有变量的边际分布
- 如何保证算数电路能够计算出正确的结果？
- sd-DNNF （smooth, deterministic, Decomposable Negation Normal Form）
编译其它的半环
A. Kimmings, G. van den Broeck, L. de Raedt, Algebraic Model Counting, 2016.
注：idp. （幂等）；neut. （中性的，\(\forall v\in\mathcal{V}\) 有 \(\alpha(v)\oplus\alpha(\neg v)=e^\otimes\)）；icp. （幂等且一致，\(\forall v\in\mathcal{V}\) 有 \(\alpha(v)\otimes\alpha(\neg v)=e^\oplus\)）
算数电路·NNF
否定范式（Negation Normal Form, NNF）：
- 只有 and 与 or 运算符，且叶子节点均为命题逻辑文字
- 可以看作一种逻辑电路
- 可以计算文字的真值指派是否满足电路结构
算数电路·NNF
NNF 的几种特殊形式：
- CNF（clausal/conjunctive normal form）：深度为 2 且 and 为根节点；
- DNF（disjunctive normal form）：深度为 2 且 or 为根节点；
算数电路·d-NNF
- d-NNF 全称为 deterministic NNF （决定否定范式）
- determinism 的意思是析取项在逻辑上不相交（即两个析取项不可能同时为真）
算数电路·d-DNNF
- d-DNNF 全称为 decomposable DNNF （可分解决定否定范式）
- decomposable 的意思是合取项无共同变量（注意是变量而非文字）
算数电路·sd-DNNF
- s-DNNF 全称为 smooth DNNF （平滑决定否定范式）
- smooth 的意思是析取项包含相同的变量集合（不考虑贝叶斯网中的 \(\theta\) 变量）
- 平滑化电路的方式是引入缺失变量（在一阶逻辑 DNNF 中非常常见）
\[(r\wedge q(X))\vee(\neg r\wedge p(X))\]
NNF 的几种特殊形式
为什么要考虑这些特殊形式？
- WMC 需要将 and 与 or 换成 \(\otimes\) 与 \(\oplus\)
- “可分解”（decomposable）保证了 \(\mathrm{Pr}(A\wedge B)=\mathrm{A}\otimes\mathrm{B}\)
- “可判定”（determinism）保证了 \(\mathrm{Pr}(A\vee B)=\mathrm{A}\oplus\mathrm{B}\)
- d-DNNF 的可满足性检验为线性复杂度
- “平滑性”（smoothness）保证了 WMC 计算到含有所有变量的 models
- 并非任意逻辑公式都能满足这些性质！
- 编译复杂度在最坏情况下是 NP-hard，但大部分时候非常快
d-DNNF 的编译算法
Huang and Darwiche. The language of search. JAIR, 2007.
function DPLL_d(S::clauses)
if S is ∅
return true sink
end
if □ ∈ S
return false sink
end
components = disjoint_partitions(S)
if len(components) > 1
conjuncts = Set()
for C ∈ components
conjuncts = union!(conjuncts, DPLL(C))
end
return get_and_node(conjuncts)
end
key = compute_key(S)
if key ∈ cache
return result[key]
else select(v) ∈ Vars
S_t = S where v = 1 # making the variable true
S_f = S where v = 0 # making the variable false
result[key] = get_node(v, DPLL(S_t), DPLL(S_f))
return result[key]
end
end
小结
小结
大作业
《符号学习》课程中，我们讨论的主题包括：
- 命题逻辑规则学习；
- 归纳逻辑程序；
- 概率逻辑规则学习；
- 神经-符号学习。
绝大部分都是采用一阶逻辑表示的符号学习方法。
但是，还有一类重要的符号学习方法我们没有提及，它能够采用任意形式语言，例如 DSL、编程语言、脚本语言等等。这个领域被称为：
程序合成（Program Synthesis）
作业要求
本课程最终考核为一篇关于程序合成领域的短综述：
- 可以中文、也可以英文；
- 中文模板：计算机学报
- 英文模板：AAAI Template
- 长度不超过 \(8\) 页
- 体现自己对该领域的看法和分析
- 推荐使用图表对领域归类、梳理
- 包含最新进展
- 可参考 2017 年 Gulwani 的综述
- 体现自己对该领域的看法和分析
- 截止时间：2022 年 7 月 17 日