贝叶斯网络与概率推理

贝叶斯网络(Bayesian networks)
贝叶斯网络是一个有向图,每个结点对应一个随机变量,一组有向边连接结点。如果结点X指向结点Y,称X是Y的父结点。每个结点\(X_i\)有一个条件概率分布\[\mathbb P(X_i|Parents(X_i))\]用于刻画其父结点对其对影响。

贝叶斯网络的构建:
1. 选定一列(有序的)随机变量\(X_1,\cdots, X_n\);
2. 对\(i=1...n\), 将\(X_i\)添加到网络中,并选择其父结点满足:\[\mathbb P(X_i|Parents(X_i))=\mathbb P(X_i|X_1,\cdots, X_{i-1}).\]

联合分布:\[P(x_1,\cdots, x_n) = \prod_{i=1}^n P(x_i|parents(X_i))\]
概率推理
1. 通过枚举进行推理
根据公式\[\mathbb P(X|e)=\alpha\ \mathbb P(X,e) = \alpha\sum_y \mathbb P(X,e,y)\]对所有变量的可能取值进行枚举后求和。当有n个布尔变量时,算法复杂度为\(O(n\cdot 2^n)\).

2. 变量消元算法
采用动态规划。按照从右到左的顺序\((X_n,X_{n-1},\cdots, X_1)\)计算表达式,并存储中间结果。

    所属分类:人工智能     发表于2022-05-30