敲代码学人工智能：概率推理
伯克利大学CS188人工智能导论课程中第五个实验的标题是“P4 Ghostbusters”，课程中介绍了确定推理算法（ExactInference）、近似推理算法（ApproximateInference）、联合粒子过滤器采样算法（JointParticleFilter）以及在上述算法在带有时间推移（withTimeElapse）优化下的基本思想。实验P4要求学习者使用Python语言完善以上算法和优化算法中使用到的参数，并在以吃豆人小游戏作为应用场景的实验中通过所有的测试用例，与之前项目中的吃豆人不同的是，此次的场景中的吃豆人需要主动出击，通过声呐传感器获取鬼鬼怪的位置信息，并计算他们可能出现的位置，然后将他们一网打尽。
通过推理计算鬼怪们的位置，将它们一网打尽为了完成实验的要求，你需要对以下代码中相关的类和函数的定义进行完善：
bustersAgents.py
inference.py
人工智能 一种现代方法 第14章 概论推理
文章目录贝叶斯网络贝叶斯网络是什么一种构造贝叶斯网络的方法条件分布的有效表示贝叶斯网络的精确推理推理任务通过枚举进行推理变量消元算法(避免重复计算)贝叶斯网络的近似推理直接采样似然加权马尔可夫链采样Gibbs采样算法资源分享本文旨在讲明：1）贝叶斯网络(何谓贝叶斯网络;从网络计算概率;如何构建贝叶斯网络;网络中的条件独立性)2）条件概率的有效表示(确定性结点;非确定性结点;连续变量)3）贝叶斯网络的精确推理(枚举;消去重复计算)4）贝叶斯网络的近似推理(直接采样;拒绝采样;加权;马尔科夫链采样)贝叶斯网络贝叶斯网络用于什么？贝叶斯网络用于表示变量之间的依赖关系。可以本质上表示任何完全联合概率分布，在许多情况下这种表示是简明扼要的。
贝叶斯网络是什么每个结点对应一个随机变量，这个变量可以是离散的或者连续的一组有向边或箭头连接结点对。如果有从结点X指向结点Y的箭头，则称X是Y的一个父结点。图中没有有向回路（因此被称为有向无环图，或简写为DAG）。每个结点Xi有一个条件概率分布P(Xi|Parents(Xi))，量化其父结点对该结点的影响。由此可确定所有变量的完全联合概率分布
例子：防盗报警器问题的贝叶斯网络问题：我在上班，邻居John打电话说我的闹钟响了，但邻居Mary没有打电话。有时它是由小地震引起的。有窃贼吗？字母B、E、A、J、M分别表示Burglary(盗贼)、Earthquake、Alarm、JohnCalls以及MaryCalls
看下面两种方法对一个联合概率的计算计算方法一：
计算方法二：
可看出结点的排序对于贝叶斯网络概率的计算具有影响。父节点排在前面时可以计算，子节点排在后面可能不利于计算。
用P(x1,..,xn)P(x_1,..,x_n)P(x1,..,xn)简化表示联合概率P(X1=x1,...,Xn=xn)P(X_1=x_1,...,X_n=x_n)P(X1=x1,...,Xn=xn)，则有：
P(x1,..,xn)=∏i=1nθ(xi∣parents(Xi))P(x_1,..,x_n)=prod_{i=1}^n heta(x_i|parents(X_i))P(x1,..,xn)=i=1∏nθ(xi∣parents(Xi))其中，参数就代表θ(xi∣parents(Xi)) heta(x_i|parents(X_i))θ(xi∣parents(Xi))就是联合概率分别蕴含的条件概率P(Xi∣parents(Xi))P(X_i|parents(X_i))P(Xi∣parents(Xi))
一种构造贝叶斯网络的方法结点:首先确定变量集合。对变量进行排序得到X1,...,Xn{X_1,...,X_n}X1,...,Xn,原因排列在结果之前。虽然任何排序都是可以的，但是原因排在结果之前，可使得网络更紧致。边:i从1到n,执行:从X1,...,Xi−1X_1,...,X_{i-1}X1,...,Xi−1中选择XiX_iXi的父结点的最小集合,使得Parents(Xi)⊆Xi−1,...,X1Parents(X_i)subseteq{X_{i-1},...,X_1}Parents(Xi)⊆Xi−1,...,X1满足。在每个父结点与XiX_iXi之间插入一条边。条件概率表(CPTs):写出条件概率表P(Xi∣Parents(Xi))P(X_i|Parents(X_i))P(Xi∣Parents(Xi))。构造贝叶斯网络的方法,将我们带到结论:
给定父结点,一个结点条件独立于它的其他祖先结点。P(X|U1,…Um,Parents(U1),…Parents(Um))=P(X|U1,…Um)给定父结点,每个变量条件独立于它的非后代结点P(X|U1,…Um,Parents(Y1),…Parents(Yn))=P(X|U1,…Um)拓扑语义蕴含了另一个重要的独立性特性：给定一个结点的父结点、子结点、以及子结点的父结点，即给定它的马尔可夫覆盖(Markovblanket)，这个结点条件独立于网络中的所有其他结点。
结点X条件独立于网络中除了它的马尔可夫盖的所有其他结点。
条件分布的有效表示贝叶斯网络的精确推理推理任务给定一组证据变量的赋值后,计算一组查询变量的后验概率分布。
通过枚举进行推理任何条件概率都可以通过将完全联合概率分布中的某些项相加而计算得到P(X∣e)=αP(X,e)=α∑yP(X,e,y)P(X|e)=alphaP(X,e)=alphasum_yP(X,e,y)P(X∣e)=αP(X,e)=αy∑P(X,e,y)P(x,e,y)可以写成网络中的条件概率的乘积形式
考虑查询P(Burglary∣JohnCalls=true,MaryCalls=true)P(Burglary|JohnCalls=true,MaryCalls=true)P(Burglary∣JohnCalls=true,MaryCalls=true)
P(B∣j,m)=αP(B,j,m)=α∑e∑aP(B,j,m,e,a)P(B|j,m)=alphaP(B,j,m)=alphasum_esum_aP(B,j,m,e,a)P(B∣j,m)=αP(B,j,m)=αe∑a∑P(B,j,m,e,a)
Burglary=true（即b）,的情况
P(b∣j,m)=α∑e∑aP(b)P(e)P(a∣b,e)P(j∣a)P(m∣a)P(b∣j,m)=αP(b)∑eP(e)∑aP(a∣b,e)P(j∣a)P(m∣a)P(b∣j,m)=α×0.00059224P(b|j,m)=alphasum_esum_aP(b)P(e)P(a|b,e)P(j|a)P(m|a)\P(b|j,m)=alphaP(b)sum_eP(e)sum_aP(a|b,e)P(j|a)P(m|a)\P(b|j,m)=alpha×0.00059224P(b∣j,m)=αe∑a∑P(b)P(e)P(a∣b,e)P(j∣a)P(m∣a)P(b∣j,m)=αP(b)e∑P(e)a∑P(a∣b,e)P(j∣a)P(m∣a)P(b∣j,m)=α×0.00059224¬b的相应计算结果为α×0.0014919因此，P(B|j,m)=α≈也就是说，在两个邻居都打了电话的情况下，出现盗贼的概率大约是28%。
公式：P(b∣j,m)=αP(b)∑eP(e)∑aP(a∣b,e)P(j∣a)P(m∣a)P(b|j,m)=alphaP(b)sum_eP(e)sum_aP(a|b,e)P(j|a)P(m|a)P(b∣j,m)=αP(b)e∑P(e)a∑P(a∣b,e)P(j∣a)P(m∣a)的计算过程显示为下图中的一棵表达式树。
求值运算过程自顶向下，将每条路径上的值相乘，并在+号结点求和。注意到j和m有重复路径。P(j|a)P(m|a)和P(j|¬a)P(m|¬a)都分别计算了两次。
变量消元算法(避免重复计算)变量消元算法的工作方式是按照从右到左的次序计算公式，中间结果被保存下来，而对每个变量的求和只需要对依赖于这些变量的表达式部分进行就可以了。
消元顺序
不同顺序决定了不同的时间和空间要求
贝叶斯网络的近似推理####蒙特卡洛算法(随机采样算法)
直接采样####拒绝采样
似然加权马尔可夫链采样Gibbs采样算法资源分享实验代码下载：https://github.com/yyl424525/AI_Homework人工智能-一种现代方法中文第三版pdf、课件、作业及解答、课后习题答案、实验代码和报告、历年考博题下载：https://download.csdn.net/download/yyl424525/11310392