[读书笔记] 人工智能中的不确定知识与推理 PART 2：关于时间的概率推理

BOOK：Stuart Russell, Peter Norvig, Artifical Intelligence: A Modern Approach（中译第二版，姜哲等）, Pearson

---

在静态世界中，每一个随机变量的取值都是唯一固定的；而有时问题是动态的，环境状态会随时间不断变化，比如考虑病情的发展，因此有必要对时间上的不确定性建模。我们将状态的改变过程描述为一系列快照，每一个快照（或时间片）都描述了世界在某个特定时刻的状态，包含一个随机变量集合，其中一部分是可观察的，如证据变量Effect，另一部分是不可观察的，如Cause。为了方便标记，一般假设时间片间有一个固定的有限时间间隔，以整数标记。符号U1:3对应变量U1，U2，U3。

• 马尔可夫假设
  马尔可夫假设认为，当前状态值只依赖于过去“有限的”已出现状态历史。这一假设使我们得以避免指定数目无界的条件假设表（过去的历史是无限的）。满足这一假设的过程被称为马尔可夫过程或者马尔可夫链，最简单的也应用最广的是一阶马尔可夫过程，即当前状态只依赖于相邻的前一个状态，与更早的状态无关：
            | 转移模型
  另外，也假设时刻t的证据变量只取决于当前状态：
            | 传感器模型
  一阶马尔可夫的假设在大多数情况下都只是一种近似，而且往往是太不精确的，有两种可能的弥补方法：1）提高马尔可夫过程的阶数；2）扩大状态变量集合。但是可以证明，提高阶数，总能够通过增加状态变量的个数重新形式化，以保持阶数不变。
  
• 基本推理任务
  1）滤波和预测（Forward）
  滤波指在到目前为止所有已知的证据下，计算“当前”状态的后验概率分布，即已知直到时刻t的滤波结果，根据新的证据 计算t+1时刻的滤波结果。滤波的过程可分为两步：首先，将当前状态分布由时刻t向前投影到时刻t+1；然后，通过新的证据进行更新。
        
  式子的第一部分是传感器模型，第二部分是一个求和式中，其中第一个因子是转移模型，第二个因子是时刻t状态分布。求和式完成滤波的第一步，总式子完成第二步。并且，可以认为因子2是沿着变量序列向前传递的“消息”f1:t，在每次转移时得到修正，并根据新的证据进行更新，也就是前向递归：
        
  预测指计算“未来”某个状态的后验概率分布，可以认为是没有增加新证据的条件下的滤波：
        
  这也是一个前向递归，并且这个计算只涉及转移模型而与传感器模型无关。可以证明，预测结果分布会在将来收敛到一个不动点，之后一直保持不变，即稳态分布。收敛的时间称为混合时间，转移模型中的不确定性越多，混合时间就越短，未来也就越模糊。
  
  2）平滑（Backward）
  平滑指在到目前为止所有已知的证据下，计算“过去”状态的后验概率分布，也可分为两步：时刻1到k的前向递归和时刻k+1到t的后向递归。
         
  这个求和式中的因子1是传感器模型，因子3是转移模型，因子2是后向传递“消息”：
           
  后向递归和前向递归复杂度相同，每次更新所需的空间和时间都是常量，与时间t无关，而是取决于状态空间的大小以及问题所需的特定时序模型。我们可以通过记录整个序列进行前向滤波的每步结果，来降低全序列平滑的时间复杂度为线性，这也就是Forward-Backward算法，先从时刻1到t前向滤波，再从时刻t到1后向平滑。这个基本算法有两个主要缺点：它提高了算法的空间复杂度；它需要修改才能工作在联机环境下，即对于不断新加入的证据，平滑以前的时间片。
  
  3）寻找最可能序列
  寻找最可能序列指给定一系列观察结果，找到最可能生成这些观察结果的状态序列。应当注意到，平滑计算得到的是“单个”时间片上的后验概率分布，而寻找最可能序列，需要考虑所有时间步上的“联合”概率分布，即
        
  典型地，考虑动态规划的思想，寻找一条以每个时间片上的可能状态为节点最大化后验概率的路径，路径上的状态就组成了最可能序列。在一次前向的遍历中，计算并记录到达每一个状态的最可能路径的概率（通过其父节点上的最可能路径概率记录），并标记产生该概率的父节点。遍历结束后，通过标记就可以回溯到这条最大化概率的最可能路径。这就是经典的Viterbi算法，其空间和时间复杂度都是O(t)。
   
  
• 隐马尔可夫模型Hidden Markov Model
  HMM指用“单一离散”随机变量描述过程状态的时序概率模型。该模型的可能取值就是世界的可能状态。多个状态变量可以组合成一个单一的“大变量”，以单个变量取值构成的所有可能元组为取值范围，来保持HMM框架。
  HMM使得所有的基本算法有一种非常简单而优雅的矩阵实现（优雅这词用的，作者太有爱了）。令状态变量用整数1，…，S表示，其中S为可能状态的数目，那么，转移模型就可表示为一个S×S的矩阵T，Tij表示从状态i转移到状态j的概率；对每个时间片t，传感器模型就可表示为一个对角型矩阵Ot（证据取值已知，因此为对角型），Oii表示当状态为i时生成证据et的概率；前向消息和后向消息用列向量表示：
          
  矩阵的形式化还揭示了改进算法的机会（值得借鉴的一句话）。
  我们可以通过取逆的方式调换等式位置，将前向消息修改为后向传递。那么Forward-Backward算法就可以被修改为：先执行标准的前向过程计算f t:1，但抛弃中间过程，然后b和f同时执行后向计算，得到平滑估计。这种修改降低了算法存储空间的需求，但它要求转移矩阵必须是可逆的，传感器矩阵也是可逆的，即所有观察值在每个状态下都是可能的。类似的，还可以修改平滑算法使之支持固定延时的联机平滑（Fixed-Lag-Smoothing算法）。
  HMM被广泛地应用于语音识别、动作手势识别等领域。
   
  
• 卡尔曼滤波器Kalman Filter
  卡尔曼滤波用一些“连续”变量来描述系统的状态（可以是多元的），然后选用合适的条件概率密度“函数”来表示转移模型和传感器模型，典型地，如线性高斯分布。假设位置X由速度和前一时间点的位置决定：
        
  那么如果增加一个高斯噪声，就得到一个线性高斯转移模型：
        
  并且，其给出的单步预测分布也是高斯的，对给定新证据进行条件化后得到的更新分布也是高斯的。一个d元高斯分布的卡尔曼滤波公式传递的“消息”是一个d元均值向量和一个d×d协方差矩阵，其与通用滤波公式或HMM模型的滤波公式的功能是相同的，但由于高斯分布的特殊本质，附加了一些有趣的性质，比如方差值的更新与观察值无关，并且其会很快收敛到一个固定的值而大大简化后续的计算过程。
  卡尔曼滤波最常见的应用是物体运动轨迹的跟踪，甚者能够应用于任何通过连续状态变量和噪声测量来刻画的系统。但是注意，这些系统必须是“光滑的、表现良好”的，并且允许追踪者保持和更新一个合理近似于真实后验概率分布的高斯状态分布。这是因为卡尔曼率滤波器将高斯均值附近的状态Xt当作局部线性的，而“不光滑、表现不良”的系统是高度非线性的，比如Xt+1的取值会因Xt与环境中某值间的相对关系而改变，参考书中鸟撞树干的例子。这种情况下，就需要考虑使用切换卡尔曼滤波器，并行多个卡尔曼滤波器，再根据每个滤波器对当前数据的适合程度，对预测结果取加权和。
   
  
• 动态贝叶斯网络Dynamic Bayesian Network
  DBN中的每个时间片都具有任意数量的状态变量和证据变量，HMM和卡尔曼滤波都是DBN的特殊形式。DBN通过将复杂系统的状态分解成一些组成变量，充分利用时序概率模型中的稀疏性，使得其比纯马尔可夫模型更适合大规模系统。DBN需要指定状态变量的先验概率、转移模型和传感器模型，后两者还需要指定相继时间片之间、状态变量与证据变量之间的链接关系的拓扑结构，如左下图所示。
                 
  DBN仍然是贝叶斯网络，因此变量消元、似然加权等推理方法仍然适用。但是DBN的精确推理是不适用的，随着规模的扩大（序列过长），变量消元的因子增长将是指数级的。近似推理中的似然加权也不是很好的选择，与真实的事件序列保持相当接近的样本比例将随着观察序列长度t的增加而呈指数级下降，举个极端的例子，以老板是否带伞来判断是否下雨的DBN，即使老板天天带伞，也仍然会产生有无尽的晴天的幻觉。
  一种比较有效的算法族是粒子滤波，它的工作机理是：首先根据时刻0的先验分布进行采样得到N个样本构成的总体，然后对接下去的每个时间片，对于每个样本通过转移模型使之向前传播，再赋予新证据的似然值进行加权，最后对总样本进行重采样，某个样本被选中的概率与其权值成正比，如右上图所示。例子滤波是高效的，它通过常数数目的样本维持对真实后验概率的良好近似，并且由于它是一个采样算法，能够很容易在混合的和连续的DBN中使用，被广泛应用于复杂的运动模式跟踪以及市场预测。