《计算智能》课程笔记2——概率推理

研一课程,做一个知识重点笔记。笔记分两部分,这个部分是曲延云上老师上的第7章。

本课程主要涉及算法有:不确定性问题——贝叶斯网络,关于时间的概率推理

相关链接《计算智能》课程笔记1

贝叶斯网络 Bayesian network

概率论

objectivist:大部分物理学家认为,量子现象客观上是概率现象,而宏观尺度上的不确定性——比如,掷硬币的不确定性——通常来自对初始条件的无知,而且似乎不符合倾向论。

subjectivist:将概率视为刻画Agent信念的一种方式,认为概率不具备任何外在的物理意义。

贝叶斯定理 Bayes’ Theorem

贝叶斯公式——从结果推原因的概率

实际上很容易看出:

image-20190102210454241

贝叶斯网络 Bayesian network

定义

贝叶斯网络是一个有向图,其中每个节点都标注了定量概率信息。

  • 每个结点对应一个随机变量。变量可以是离散的或连续的。
  • 一个连接点对的有向边或箭头集合。若存在从结点 $X$ 指向结点 $Y$ 的有向边,则称 $X$ 是 $Y$ 的父节点。
  • 图中没有有向回路(有向无环图DAG)
  • 每个结点 $X_i$都有一个条件概率分布:$P(X_i|\text{Parents}(X_i))$ ,量化父结点对于该结点的影响

在简单的例子中,条件概率分布被表示为条件概率表(CPT)。CPT中的每一行包含了每个节点值
对于一个条件事件的条件概率。

紧致性与节点排序

贝叶斯网络能够对域进行一种完备而冗余的表示,比全联合概率分布紧凑得多

  • 贝叶斯网络是紧致性(sparse)的$\Leftrightarrow$局部结构化(locally structure)
  • 每个组成部分都只与数量有限的其他部分发生直接的相互作用,而不考虑组成部分的总数量。

局部结构的复杂度关于变量 $n$ 是线性的,而不是指数增长的。

  • 对布尔变量 $X_i$,有 $k$ 个布尔变量的父节点,CPT中就有 $2k$ 个数据。
  • 若每个变量的父节点不超过 $k$ 个,则该网络需要的数据是 $O(n·2^k)$
  • 即关于 $n$ 是线性的,而全概率分布的数据量是 $O(2^n)$

例如:一个有30个节点的网络,每个节点有5个父节点,那么,该网络需要960个数据,而全联合概率需要10亿个。

构造贝叶斯网络

  1. 选择已排序的节点 $X_1,…,X_n$

  2. For i:=1 to n

    1. 把 $X_i$ 添加到网络

    2. 从 $X_1,…,X_{i−1}$选择父节点

      对父节点的选择能保证:

贝叶斯网络中的条件独立关系

  1. 给定父节点,一个节点与它的非后代节点是条件独立的。例如:给定Alarm的取值后,结点Johncall条件独立于Burglary和Earthquake以及MaryCalls。

  2. 给定一个节点的父节点、子节点以及子节点的父节点——即,给定它的Markov覆盖,该节点与网络中的所有其它节点都是条件独立的。例如:给定Alarm和Earthquake后,Burglary独立于Johncalls及Marycalls。

    image-20190103105521950

例子:

image-20190102212220833

image-20190103111642977

贝叶斯网络中的精确推理

方法1 通过枚举进行推理

在没有实际构建其显式表示的情况下,从节点中枚举出所有情况计算查询。

递归深度优先枚举,空间 $O(n)$ ,时间 $O(d^n)$ 。

不在查询变量中的其他变量,须求和。缺点:枚举法效率低下,存在重复计算。

例如:

方法2 变量消元算法

从右到左执行求和,存储中间结果(因子)以避免重新计算。

其中:

image-20190103154053770

image-20190103154108366

精确推理复杂度

对于单连接网络(或者多树):

  • 任意两个节点通过至多一个(无向)连接
  • 变量消元的时间和空间成本是 $O(d^kn)$

对于多连接网络:在最坏情况下,具有EXPTIME

团算法

  • 对于回答单个查询,变量消元算法是简单有效的。然而,若希望计算网络中所有节点的后验概率它就不那么有效率了。
  • 例如,在一个是多树网络中可能需要处理 O(n) 个查询,查询都需要 O(n)的开销,因此总的时间复杂度是 $O(n^2)$ 。
  • 通过团算法(联合树算法),时间可以减少到 O(n)。

🌟贝叶斯网络中的近似推理 p462

精确推理的局限性:对大规模多连通网络中的精确推理是不可操作的。

近似推理是一种蒙特卡洛方法

近似推理基本思想:

  1. 从分布 S 中进行 N 个样本的采样
  2. 计算一个逼近的后验概率 P̂
  3. 证明它收敛到真实概率 P

以如下例子来说明各种采样方式:

image-20190103165800795

直接采样法

直接采样法,一般用于计算(估计)联合概率分布。

按照拓扑顺序依次对每个变量进行采样。变量值被采样的概率分布依赖于父结点已得到的赋值。

在任何采样方法中,都是通过对实际生成 的样本数来计算答案。假设共有N个样本, 令N(x1,…,xn)为特定事件x1,…xm发生频率,

我们期望该频率在极限情况下收敛到根据 采样概率得到的它的期望值.

image-20190103165910580

image-20190103165926776

拒绝采样法

拒绝采样(reject sampling)原理详解 - jteng的专栏 - CSDN博客

该算法是一类由一个易于采样的分布出发,为一个难以直接采样的分布产生采样样本的通用算法。在其最简单的形式中,它可以用于计算条件概率,确定$P(X|e)$,其中e是证据。

计算步骤:

  1. 根据网络指定的先验概率分布生成采样样本
  2. 拒绝所有与证据不匹配的样本
  3. 在剩余样本中对事件$X=x$的出现频繁程度计数从而得到估计概率

image-20190103170053311

局限性:拒绝了太多的样本。随着证据变量个数的增多,与证据 e 相一致的样本在所有样本中所占的比例呈指数级下降,所以对于复杂问题这种方法是完全不可用的。

似然加权法

似然加权法是重要性抽样的一个特例, 提出它的一个主要目的是避免逻辑抽样因舍弃样本而造成浪费,对拒绝采样的一种改进

只生成与证据e一致的事件,从而避免拒绝采样算法的低效率。

image-20190103170517779

image-20190103170729565

image-20190103170804537

image-20190103170828244

Markov链仿真推理 MCMC

image-20190103172027090

image-20190103172126227

image-20190108163021898

关于时间的概率推理

时间片是一个随机变量的集合,其中一部分是可观察的,一部分是不可观察的。

假设所观察到的随机变量属于同一个变量子集:

  • $X_t$ 为 t 时刻不可观测的状态变量
  • $E_t$ 为 t 时刻可观测的证据变量

假设时间是离散的,时间间隔依赖于具体问题,

时间与不确定性 p495

基本思想

​ 按自然的时序顺序对变量进行排序,按因果次序添加变量,记录每个时间片的观测与证据。

遇到的困难:

​ 变量集合是无界的,因为它需要包含全部时间片的状态与证据。

  1. 与每个时间片中的每个变量相对应,需要指定数目无界的条件概率表
  2. 条件概率表可能涉及数目无界的父节点

解决办法:

  1. 无限多的CFT →稳态过程
  2. 潜在的无限多父节点 → Markov过程

稳态过程:变化过程是由本身不随时间变化的规律支配的。

Markov过程:当前状态只依赖过去有限的已出现状态。最简单的是一阶Markov过程,其中当前状态只依赖于相邻的前一个状态,而与更早的状态无关,即 $P(X_t|X_{0:t−1})=P(X_t|X_{t−1})$。

若一阶Markov过程不精确,可通过如下方法弥补:

  1. 提高Markov过程阶数
  2. 扩大状态变量集合。

推理任务

  1. 滤波:$P(X_t|e_{1:t})$

    估计当前状态的后验概率

    image-20190103172528900

    image-20190103172621778

  2. 预测:$P(X_{t+k}|e_{1:t})$ 对于 k>0

    估计未来状态的后验概率

    image-20190103172636998

  3. 平滑:$P(X_k|e_{1:t})$对于 0≤k<t

    估计过去状态的后验概率。更好地估计过去的状态,对学习至关重要

    image-20190103172700169

  4. 似然解释:$\text{arg max}_{x_{1:t}}P(x_{1:t}|e_{1:t}) $

    估计产生结果的状态序列

    image-20190103172717510

关于“学习”

image-20190103172741420

补充

image-20190106200325806

(a)滤波与预测

滤波

一个有用的滤波算法需要维持一个当前状态来估计并进行更新,而不是每次更新回到整个感知历史。

image-20190106162925615

image-20190106194941179

预测

image-20190106202007259

image-20190106204721456

下略 在纸质笔记中