贝叶斯网络推理算法：从基础到优化

### 贝叶斯网络推理算法：从基础到优化 在贝叶斯网络的推理领域，有多种算法和模型可以帮助我们更高效地进行概率计算和推理。下面将详细介绍几种重要的算法和模型。 #### 1. Pearl消息传递算法 Pearl消息传递算法是贝叶斯网络推理中的重要算法。在一个示例中，计算了在特定条件下的概率： ```plaintext P(b1|{a1, f1}) = .005α .005α+.199α = .025; // Compute P(b|{a1, f1}). P(b2|{a1, f1}) = .199α .005α+.199α = .975; ``` 当Antonio看到房子后面有一辆货运卡车时，窃贼出现的概率从.357降至.025，但由于两个原因在警报条件下并非互斥，所以概率不会降至0，甚至不会降至其先验概率.005。 ##### 1.1 多连接网络中的推理 之前我们主要考虑的是单连接网络，但实际应用中存在很多多连接网络的情况。为了处理多连接网络，我们采用条件化的方法。 假设我们有一个贝叶斯网络，其有向无环图（DAG）如图3.11(a)所示，且每个随机变量有两个值。由于网络是多连接的，算法3.2不能直接应用。但如果从网络中移除节点X，网络就变成了单连接的。我们构建两个贝叶斯网络： - 一个包含给定$X = x_1$时P的条件分布$P'$。 - 另一个包含给定$X = x_2$时P的条件分布$P''$。 这两个网络分别如图3.11(b)和(c)所示。对于每个网络，我们确定每个节点在其父母节点条件下的条件概率。除了根节点Y和Z，这些条件概率与原始网络中的相同。对于根节点，有： - $P'(y_1) = P(y_1|x_1)$ - $P'(z_1) = P(z_1|x_1)$ - $P''(y_1) = P(y_1|x_2)$ - $P'(z_1) = P(z_1|x_2)$ 我们可以通过在这些单连接网络中使用算法3.2进行推理，来实现原始网络中的推理。下面是具体示例： - **示例3.9**：假设在图3.11(a)的网络中，U被实例化为$u_1$。考虑在这种实例化下W的条件概率： $P(w_1|u_1) = P(w_1|x_1, u_1)P(x_1|u_1) + P(w_1|x_2, u_1)P(x_2|u_1)$ $P(w_1|x_1, u_1)$和$P(w_1|x_2, u_1)$的值可以分别通过对图3.11(b)和(c)中的网络应用算法3.2获得。$P(x_i|u_1)$的值由$P(x_i|u_1) = αP(u_1|x_i)P(x_i)$给出，其中α是归一化常数，等于$1/P(u_1)$。 - **示例3.10**：假设在图3.11(a)的网络中，U被实例化为$u_1$，Y被实例化为$y_1$。则有： $P(w_1|u_1, y_1) = P(w_1|x_1, u_1, y_1)P(x_1|u_1, y_1) + P(w_1|x_2, u_1, y_1)P(x_2|u_1, y_1)$ $P(w_1|x_1, u_1, y_1)$和$P(w_1|x_2, u_1, y_1)$的值可以通过对图3.11(b)和(c)中的网络应用算法3.2获得。$P(x_i|u_1, y_1)$的值由$P(x_i|u_1, y_1) = αP(u_1, y_1|x_i)P(x_i)$给出，其中α是归一化常数，等于$1/P(u_1, y_1)$。而$P(u_1, y_1|x_i)$不能直接使用算法3.2计算，但可以通过链式法则结合算法3.2来获得： $P(u_1, y_1|x_i) = P(u_1|y_1, x_i)P(y_1|x_i)$ 我们进行条件化的节点集称为环割集。并不总是能找到仅包含根节点的环割集，寻找最小环割集的问题是NP难的。一般方法如下： 1. 确定一个环割集C。 2. 设E是一组实例化的节点，e是它们的实例化集合。 3. 对于每个$X \in V - \{E \cup C\}$，有$P(x_i) = \sum_{c} P(x_i|e, c)P(c|e)$，其中求和是对C中变量的所有可能值进行的。$P(x_i|e, c)$的值使用算法3.2计算，$P(c|e)$使用$P(c|e) = αP(e|c)P(c)$确定。为了计算$P(e|c)$，我们使用链式法则，然后多次使用算法3.2计算乘积中的各项。 ####