12.09课堂作业：贝叶斯网络

2024年12月9日 概率图模型

作业题目

题目：给定一个包含6个变量的贝叶斯网络，计算联合概率密度公式，并比较完全概率表和贝叶斯网络的存储效率。

问题1：联合概率密度计算公式

贝叶斯网络的联合概率分解

根据贝叶斯网络的条件独立性假设，6个变量的联合概率密度可以分解为：

$$P(x_1, x_2, x_3, x_4, x_5, x_6) = P(x_1) \cdot P(x_2|x_1) \cdot P(x_3|x_1,x_5) \cdot P(x_4|x_2) \cdot P(x_5|x_1) \cdot P(x_6|x_2,x_3,x_4)$$

公式解释

这个公式表示了变量之间的依赖关系：

  • \(P(x_1)\)：\(x_1\) 是根节点，没有父节点
  • \(P(x_2|x_1)\)：\(x_2\) 依赖于 \(x_1\)
  • \(P(x_3|x_1,x_5)\)：\(x_3\) 依赖于 \(x_1\) 和 \(x_5\)
  • \(P(x_4|x_2)\)：\(x_4\) 依赖于 \(x_2\)
  • \(P(x_5|x_1)\)：\(x_5\) 依赖于 \(x_1\)
  • \(P(x_6|x_2,x_3,x_4)\)：\(x_6\) 依赖于 \(x_2\)、\(x_3\) 和 \(x_4\)

网络结构示意

根据公式可以推断出网络结构：

        x₁ (根节点)
       /  |  \
      /   |   \
    x₂   x₅   (x₃依赖x₁和x₅)
    / \   |   /
   /   \  |  /
  x₄   x₆←x₃
         ↑
        x₂,x₄

箭头表示依赖关系，指向的节点依赖于箭头起点的节点

问题2：完全概率表有多少行

完全概率表（Full Joint Probability Table）

假设每个变量都是二值变量（取值为0或1），则完全概率表需要存储所有可能的变量组合。

计算过程

6个二值变量的所有可能组合数为：

$$2^6 = 64 \text{ 行}$$

完全概率表示例（部分）

x₁ x₂ x₃ x₄ x₅ x₆ P(x₁,x₂,x₃,x₄,x₅,x₆)
0 0 0 0 0 0 p₁
0 0 0 0 0 1 p₂
0 0 0 0 1 0 p₃
...
1 1 1 1 1 1 p₆₄

存储问题

完全概率表需要存储 64个概率值（实际上是63个，因为最后一个可以通过归一化计算得出）。

随着变量数量增加，存储需求呈指数增长：

  • 10个变量：\(2^{10} = 1024\) 行
  • 20个变量：\(2^{20} = 1,048,576\) 行
  • 30个变量：\(2^{30} = 1,073,741,824\) 行

问题3：贝叶斯网络需要多少行

贝叶斯网络的条件概率表（CPT）

贝叶斯网络利用条件独立性，只需要存储每个节点的条件概率表。

逐个计算每个节点的CPT大小

1. \(P(x_1)\)

无父节点，需要存储：

$$2^1 = 2 \text{ 行}$$

（\(x_1=0\) 和 \(x_1=1\) 的概率）

2. \(P(x_2|x_1)\)

1个父节点，需要存储：

$$2^1 \times 2 = 4 \text{ 行}$$

（对于 \(x_1\) 的每个取值，\(x_2\) 有2个可能的取值）

3. \(P(x_3|x_1,x_5)\)

2个父节点，需要存储：

$$2^2 \times 2 = 8 \text{ 行}$$

（\(x_1\) 和 \(x_5\) 的4种组合，每种组合下 \(x_3\) 有2个取值）

4. \(P(x_4|x_2)\)

1个父节点，需要存储：

$$2^1 \times 2 = 4 \text{ 行}$$
5. \(P(x_5|x_1)\)

1个父节点，需要存储：

$$2^1 \times 2 = 4 \text{ 行}$$
6. \(P(x_6|x_2,x_3,x_4)\)

3个父节点，需要存储：

$$2^3 \times 2 = 16 \text{ 行}$$

（\(x_2\)、\(x_3\) 和 \(x_4\) 的8种组合，每种组合下 \(x_6\) 有2个取值）

总计

$$\text{总行数} = 2 + 4 + 8 + 4 + 4 + 16 = 38 \text{ 行}$$

存储效率对比

完全概率表 vs 贝叶斯网络

完全概率表

64 行

存储所有变量的联合概率

贝叶斯网络

38 行

利用条件独立性压缩存储

存储效率提升

$$\text{压缩率} = \frac{38}{64} \approx 59.4\%$$
$$\text{节省空间} = \frac{64 - 38}{64} \approx 40.6\%$$

贝叶斯网络节省了约 40.6% 的存储空间！

贝叶斯网络的优势

存储效率高

利用条件独立性大幅减少存储需求

计算效率高

推理计算更快，避免了指数级复杂度

可解释性强

图结构直观展示变量间的因果关系

模块化

每个节点的CPT可以独立学习和更新

规模扩展性

随着变量数量增加，贝叶斯网络的优势更加明显：

变量数量 完全概率表 贝叶斯网络（假设平均2个父节点） 压缩率
6 64 38 59.4%
10 1,024 ~80 7.8%
20 1,048,576 ~160 0.015%
30 1,073,741,824 ~240 0.000022%

注：贝叶斯网络的实际大小取决于网络结构，这里假设平均每个节点有2个父节点

总结

关键要点

联合概率可以通过条件独立性分解为多个条件概率的乘积

完全概率表需要 \(2^6 = 64\) 行存储

贝叶斯网络只需要 38 行，节省约 40.6% 的空间

变量越多，贝叶斯网络的优势越明显

上一个作业 返回主页