讲稿2

Report
第Ⅳ部分 不确定知识与推理
第14章 概率推理
中国科大 计算机学院
本章内容
•
•
•
•
•
•
•
14.1 不确定性问题域中的知识表示
14.2 贝叶斯网络的语义
14.3 条件分布的有效表示
14.4 贝叶斯网络中的精确推理
14.5 贝叶斯网络中的近似推理
14.6 关系和一阶概率模型
14.7 不确定推理的其他方法
贝叶斯网络中的精确推理
• 在给定某个己观察事件——也就是一组证据变量值
的某个赋值后,任何概率推理系统的基本任务都是
要计算一组查询变量的后验橄率分布。
• 这里指考虑一个查询变量。相应的算法可以很容易
扩展到多个查询变量的情况。
贝叶斯网络中的精确推理
• 约定:
– X表示查询变量;
– E表示证据变量集E1, E2, ..., Em,e则表示一个观察
到的特定事件。
– Y表示非证据变量集Y1, Y2, ...., Yl(有时称为隐变
量, hidden variable) 。
– 因此,全部变量的集合 = {} ∪  ∪ 。
– 典型的查询是询问后验概率(|)。
贝叶斯网络中的精确推理
• 例如,在防盗网络中,我们可能观察到一个事件中
JohnCalls = true且MaryCalls = true,然后我们会
问,出现盗贼的概率是多少:
   = ,  = 
= . , .  。
• 本节将讨论计算后验概率的精确算法,并将考虑此
任务的复杂度。最后的结果是,一般情况下的精确
推理是不可操作的,因此下一节节将讨论近似推理
方法。
通过枚举进行推理
• 任何条件概率都可以通过将完全联合概率分布表中
的某些项相加而计算得到,即
   = (, ) = 
(, , )

• 贝叶斯网络给出了完全联合概率分布的完备表示。
– 联合概率分布中的项(, , )可以根据网络写成
条件概率乘积的形式。
– 因此,可以在贝叶斯网络中通过计算条件概率的
乘积再求和来回答查询。
通过枚举进行推理
• 考虑如下查询:
   = ,  = 
• 该查询的隐变量是Earthquake和Alarm,因此,
  ,  = (, , ) = 
(, , , , )


• 贝叶斯网络的语义给了我们一个根据条件概率表描
述的表达式。为了简化,仅给出Burglary=true的计
算过程:
  ,  = 
      ,     (|)


通过枚举进行推理
• 仅给出Burglary=true的计算过程:
  ,  = 
      ,     (|)


• 为了计算这个表达式,需要对4个项进行加法运算,
而每一项都是通过5个数相乘计算得到。
• 在最糟糕的情况下,我们需要对所有的变量进行求
和,因此对于有n个布尔变量的网络而言,算法的复
杂度将是O(n2n)。
通过枚举进行推理
• 不过可以改进:P(b)是常数,因此可以从对a和e的
求和符号中挪出去,而P(e)项也可以从对a 的求和符
号中挪出去。因此,
  , 
=  
 

  ,     (|)

• 这个表达式可以通过按顺序循环遍历所有变量并把
条件概率表中的对应条目乘起来进行求值计算。对
于每次求和运算,还需要对变量的可能取值进行循
环。
通过枚举进行推理
• 计算结果是  ,  =  × . ,而¬的
计算结果是 × . 。
• 因此,
  ,  =  . , . 
≈ . , . 
• 也就是说,在两个邻居都给你打电话的条件下出现
盗贼的概率大约是28% 。
通过枚举进行推理
• 该表达式的计算过程可显示为一棵树:
通过枚举进行推理
• ENUMERATION-ASK算法(在贝叶斯网络上回答查询的枚
举算法)通过深度优先递归对这棵树进行求值。
通过枚举进行推理
• 算法ENUMERATION-ASK的空间复杂度对于变量
个数是线性的(算法对全联合分布求和而不用显式
地构造它)。不幸的是,对于一个有n个布尔变量的
网络,该算法的时间复杂度始终都是O(2n) ——比前
面描述的那种简单算法的O(n2n)的复杂度要低,但
仍然非常可怕。
• 值得注意:前面给出的树中有需要算法计算的重复
子表达式。对于e的每个不同取值,乘积
   (|)和  ¬ (|¬)都分别计算了两
次。下面描述能够避免这种计算浪费的方法。
变量消元算法
• 通过消除子表达式的重复计算能够大大提高枚举算
法的效率。
– 其思想非常简单:只进行一次计算,并保存计算
结果以备将来使用。
– 这是动态规划的一种形式。这种方法有几种不同
的版本。
– 这里给出其中最简单的变量消元算法(variable
elimination algorithm)。
– 变量消元算法按照从右到左的次序计算这样的表
达式(即在树种按照自底向上的次序),中间结
果被保存下来,而对每个变量的求和只需要对依
赖于这些变量的表达式部分进行就可以了。
本章内容
•
•
•
•
•
•
•
14.1 不确定性问题域中的知识表示
14.2 贝叶斯网络的语义
14.3 条件分布的有效表示
14.4 贝叶斯网络中的精确推理
14.5 贝叶斯网络中的近似推理
14.6 关系和一阶概率模型
14.7 不确定推理的其他方法
贝叶斯网络中的近似推理
• 既然大规模多连通网络中的精确推理是不可操作的,
考虑近似的推理方法是必要的。
• 本节描述的随机采样算法,也称为蒙特卡洛算法
(Monte Carlo algorithm)能够给出一个问题的近
似解答,而其近似的精度依赖于所生成采样点的多
少。
• 近年来,蒙特卡洛算法在计算机科学中广泛用于对
难以精确计算的数据进行估计。例如,第4章中所描
述的模拟退火算法就是一种用于优化问题的蒙特卡
洛算法。
贝叶斯网络中的近似推理
• 本节中,我们的兴趣在于应用于后验概率计算的采
样方法。
• 这里给出两个算法族:直接来样方法和马尔可夫链
采样方法。
• 另外两种方法——变分法(variational method)和环
传播(loopy propagation) 方法——在本章末尾的注
释中会提及。
直接采样方法
• 任何采样算法中最基本的要素是根据己知概率分布
生成样本。
• 例如,一个无偏差硬币可以被认为是一个随机变量
Coin,可能取值为<heads, tails>,分别表示硬币
正面或者背面朝上,先验概率是P(Coin) = (0.5, 0.5)。
根据这个分布进行采样的过程,其实就跟抛硬币一
模一样, 它以概率0.5返回heads. 以概率0.5 返回
tails。
• 给定了一个[0, 1]区间上的随机数发生器,要对任何
单变量的分布进行采样都是一件非常简单的事情。
直接采样方法
• 对于贝叶斯网络而言,最简单的随机采样过程是从网络中生成
无关联证据的事件。
– 其思想是按照拓扑次序依次对每个变量进行采样。变量值被
采样的概率分布依赖于父节点己得到的赋值。
• 采样算法:
1.
2.
3.
4.
5.
6.
Function PRIOR-SAMPLE(bn) returns an event sampled from the prior
specified by bn
inputs: bn, a Bayesian network specifying joint distribution P(X1,…, Xn)
xan event with n elements
For i=1 to n do
xia random sample from P(Xi | parents(Xi))
return x
直接采样方法
• 例,假设顺序为[Cloudy, Sprinkler, Rain, WetGrass]。
① 根据P(C)=<0.5,0.5>对C进行采样,假设得到true。
② 根据P(S|C=true)=<0.1, 0.9>对S进行采样,假设得到false。
③ 根据P(R|C=true)=<0.8, 0.2>对S进行采样,假设得到true。
④ 根据P(W|S=false, R=true)=<0.9, 0.1>对W进行采样,假设
得到true。
– PRIOR-SAMPLE返回事件:
• <true, false, true, true>。
草坪喷灌网络
直接采样方法
• 容易证明PRIOR-SAMPLE生成的样本服从网络所指
定的先验联合概率分布。
– 令 , … ,  为PRIOR-SAMPLE生成的特定
事件的概率。根据采样过程,因为每个采样步骤
都只依赖于父节点的取值,因此有

 , … ,  =
(|  )
=
– 上式就是按照贝叶斯网络对联合概率分布的表示
而得到的该事件的概率。因此,
 , … ,  = (, … , )
– 因此,可以利用采样来回答问题。
直接采样方法
• 在任何采样方法中,都是通过对实际生成的样本进
行计数来计算答案的。
• 假设总共有N个样本,令(, … , ) 为特定事件
(, … , )发生的频率。
– 我们期望这个频率在极限情况下能够收敛到根据
采样概率得到的它的期望值:
(, … , )
lim
=  , … ,  = (, … , )
→∞

直接采样方法
• 例如,考虑前面生成的事件[true, false, true, true] ,
这个事件的采样概率应该是:
 , , , 
= .  × .  × .  × .  = . 
– 因此,在N的大量样本极限下(N趋近于无穷大),
我们期望有32.4% 的样本是这个事件。
• 例如,假设从草坪喷灌网络生成了1000个样本,其
中511个样本满足Rain=true,那么下雨的估计概率,
记作( = ),就等于0.511。
本章小结
• 贝叶斯网络的基本概念
• 贝叶斯网络中的精确推理
• 贝叶斯网络中的近似推理

similar documents