时间与不确定性
部分可观测环境中的智能体必须能够在其传感器允许的范围内追踪当前所处的状态。在搜索中展示了实现这一目标的一种方法：智能体维护一个信念状态，它表示目前哪些世界状态是可能的。根据信念状态和转移模型，智能体可以预测世界在下一个时间步将如何发展。基于观测感知和传感器模型，智能体可以更新信念状态。
这是一个普遍的想法：在搜索中，信念状态是通过显式枚举的状态集合来表示的，而在逻辑中，它们是通过逻辑公式来表示的。这些方法从哪些世界状态是可能的角度来定义信念状态，但它无法说明哪些状态是多大程度可能的。在概率中，将用概率论的工具来量化信念状态元素的信念度。
首先需要刻画时间的表达，这里主要使用离散时间模型，这意味着世界被视为一系列快照或者时间片。将时间片编号为 0、1、2 等，而不是给它们指定特定的时间。通常，片之间的时间间隔$\varDelta $都是相同的。对于任意一个特定的应用，必须选择一个特定的$\varDelta $值。有时这是由传感器决定的；例如，摄像机可能以 1/30 秒的间隔提供图像。在其他情况下，间隔可能由相关变量的标准变化率决定。
离散时间概率模型中的每个时间片包含一组随机变量，其中一些变量是可观测的，一些是不可观测的。为简单起见，假定如果一个变量子集在一个时间片是可观测的，则其在每个时间片中都是可观测的（尽管这在接下来的内容中不是严格必要的）。用$X_t$表示时刻$t$的不可观测的状态变量集合，用$E_t$表示可观测的证据变量集合。对于某一组值$e_t$，时刻$t$的观测值为$E_t = e_t$。
假设状态序列从$t = 0$开始，证据从$t = 1$开始到达。使用记号$a:b$表示从$a$到$b$的整数序列（包含$a$与$b$），使用符号$X_{a:b}$表示从$X_a$到$X_b$的变量集（包含$X_a$与$X_b$）。
确定了给定问题的状态变量集合和证据变量集合之后，下一步需要指定世界如何演变（转移模型）以及证据变量如何获得它们的值（传感器模型）。
转移模型是指给定先前状态的值时，最新状态变量的概率分布，也就是$P\left( X_t|X_{0:t-1} \right) $。随着时间$t$的增长，集合$X_{0:t-1}$的规模将无限扩大。可以通过马尔可夫假设（即当前状态只依赖有限固定数量的过去状态）来解决这个问题。统计学家安德雷·马尔可夫最早对满足这一假设的过程进行了深入研究，因此这种过程被称为马尔可夫过程或马尔可夫链。它们有着各种各样的形式，其中最简单的是一阶马尔可夫过程。在一阶马尔可夫过程中，当前状态只依赖前一个状态，而不依赖任何更早的状：
$$
P\left( X_t|X_{0:t-1} \right) =P\left( X_t|X_{t-1} \right)
$$
因此，在一阶马尔可夫过程中，转移模型即为条件分布$P\left( X_t|X_{t-1} \right) $。二阶马尔可夫过程的转移模型是条件分布$P\left( X_t|X_{t-1},X_{t-2} \right) $。
尽管利用马尔可夫假设规避了一些困难，但仍然存在一个问题：$t$的可能的值有无穷多个。需要为每个时间步指定不同的分布吗？事实上可以通过假设世界状态的变化是一个时间齐次的过程来规避这个问题：也就是说，它是一个由自身不随时间变化的规律所控制的变化过程，对所有$t$都是一样的，只需要指定一个条件概率表即可。
接下来考虑传感器模型（观测模型）。证据变量$E_t$可能依赖于过去的变量和当前的状态变量，但是任何称职的状态都应该足以生成当前的传感器值。因此，做出如下的传感器马尔可夫假设：
$$
P\left( E_t|X_{0:t},E_{1:t-1} \right) =P\left( E_t|X_t \right)
$$
除了指定转移模型和传感器模型之外，还需要说明事物的初始状态——时刻$0$时的先验概率分布$P(X_0)$。这样一来，可以得到所有变量的完整的联合分布。对于任意时间步$t$有：
$$
P\left( X_{0:t},E_{1:t} \right) =P\left( X_0 \right) \prod_{i=1}^t{P\left( X_i|X_{i-1} \right) P\left( E_i|X_i \right)}
$$
一阶马尔可夫过程假设的合理性取决于域本身。一阶马尔可夫假设认为，状态变量包含了描述下一个时间片的概率分布需要的所有信息。有时候这种假设是完全成立的，但有时候这种假设只是近有两种方法可以提高近似的准确性：
（1）增加马尔可夫过程模型的阶数。（2）扩大状态变量的集合。
时序模型中的推断
滤波或状态估计是指计算信念状态——给定迄今为止所有的证据时最近状态的后验分布的任务。一个理性智能体将进行滤波以用于追踪当前的状态，以便做出理性的决策。一个有用的滤波算法需要维护一个对当前状态的估计并更新它，而不是每次更新都要回顾整个感知历史。（否则，每次更新的代价会随着时间的推移而增加。）换句话说，给定直到时刻$t$的滤波结果，智能体需要从新的证据$e_{t+1}$中计算时刻$t+1$的结果。所以，存在某个函数$f$满足：
$$
P\left( X_{t+1}|e_{1:t+1} \right) =f\left( e_{t+1},P\left( X_t|e_{1:t} \right) \right)
$$
这个过程称为递归估计，可以将计算看作由两部分组成：第一部分是当前状态分布从$t$到$t+1$向前投影；第二部分是使用新的证据$e_{t+1}$更新它。通过对公式重新排列，可以得到滤波的递归估计过程：
$$
P\left( X_{t+1}|e_{1:t+1} \right) =P\left( X_{t+1}|e_{1:t},e_{t+1} \right) =P\left( X_{t+1}|e_{t+1},e_{1:t} \right)
$$
$$
=\frac{P\left( e_{t+1}|X_{t+1},e_{1:t} \right) P\left( X_{t+1}|e_{1:t} \right)}{P\left( e_{t+1}|e_{1:t} \right)}=\alpha P\left( e_{t+1}|X_{t+1},e_{1:t} \right) P\left( X_{t+1}|e_{1:t} \right)
$$
$$
\left[ \text{给定}e_{1:t}\text{应用贝叶斯法则的推广：}P\left( Y|X,e \right) =\frac{P\left( X|Y,e \right) P\left( Y|e \right)}{P\left( X|e \right)} \right]
$$
$$
=\alpha P\left( e_{t+1}|X_{t+1} \right) P\left( X_{t+1}|e_{1:t} \right) \left[ \text{应用马尔可夫传感器假设} \right]
$$
$$
=\alpha P\left( e_{t+1}|X_{t+1} \right) \sum_{x_t}{P\left( X_{t+1}|x_t,e_{1:t} \right) P\left( x_t|e_{1:t} \right)}\left[ \text{用全概率公式的思想来理解} \right]
$$
$$
=\alpha P\left( e_{t+1}|X_{t+1} \right) \sum_{x_t}{P\left( X_{t+1}|x_t \right) P\left( x_t|e_{1:t} \right)}\left[ \text{应用马尔可夫状态转移模型} \right]
$$
在这个表达式中，所有的项要么来自模型，要么来自之前的状态估计。因此，得到了递归公式。可以认为滤波估计是沿着序列向前传播的“消息”$f_{1:t}$，消息在每次转移时进行修正并根据每次新的观测进行更新。这个过程可以表述为：
$$
f_{1:t+1}=Forward\left( f_{1:t},e_{t+1} \right)
$$
如果所有的状态变量都是离散的，每次更新所需的时间是常量（即与$t$无关），所需的空间也是常量。（当然，这些常量取决于问题中状态空间的大小和时序模型的类型。）如果一个有限的智能体无限期地追踪当前状态分布，更新的时间与空间要求必须是常数量级。
预测：该任务是指给定迄今为止所有的证据，计算未来状态的后验分布，预测对于根据预期结果评估可能的动作方案是非常有用的。预测的任务可以简单地看作不添加新证据的滤波。事实上，滤波过程已经包含了一个单步预测，容易推导出下面的递归计算，即从时刻$t+k$的预测去预测时刻$t+k+1$的状态，这个计算只涉及转移模型而不涉及传感器模型：
$$
P\left( X_{t+k+1}|e_{1:t} \right) =\sum_{x_{t+k}}{P\left( X_{t+k+1}|x_{t+k} \right) P\left( x_{t+k}|e_{1:t} \right)}
$$
当尝试预测越来越远的未来时，考虑会发生什么是非常有趣的。一些预测分布将收敛到不动点，且之后会一直保持不变。这就是由转移模型定义的马尔可夫过程的平稳分布。人们对于这种分布的性质和混合时间——大致含义是分布达到不动点所花费的时间——有很深入的了解。在实践中，除非平稳分布本身在状态空间的一小部分区域有显著的峰值，否则任何对实际状态进行时间步超过混合时间某个比例的预测都注定失败。一般而言，转移模型的不确定性越大，混合时间就越短，对未来的了解就越模糊。
平滑：该任务是指给定迄今为止所有的证据，计算过去状态的后验分布。平滑提供了比当时能得到的估计更好的估计，因为它包含了更多的证据。可以将计算分成两部分——到时刻$k$为止的证据和从时刻$k+1$到时刻$t$的证据：
$$
P\left( X_k|e_{1:t} \right) =P\left( X_k|e_{1:k},e_{k+1:t} \right) =P\left( X_k|e_{k+1:t},e_{1:k} \right)
$$
$$
==\frac{\alpha P\left( e_{k+1:t}|X_k,e_{1:k} \right) P\left( X_k|e_{1:k} \right)}{P\left( e_{k+1:t}|e_{1:k} \right)}=\alpha P\left( e_{k+1:t}|X_k,e_{1:k} \right) P\left( X_k|e_{1:k} \right)
$$
$$
=\alpha P\left( e_{k+1:t}|X_k \right) P\left( X_k|e_{1:k} \right) =\alpha P\left( X_k|e_{1:k} \right) P\left( e_{k+1:t}|X_k \right) =\alpha f_{1:k}\times b_{k+1:t}
$$
其中，$\times $表示向量的逐点乘积。这里定义了类似于前向消息$f_{1:k}$的“后向”消息$b_{k+1:t}=P\left( e_{k+1:t}|X_k \right) $。前向消息$f_{1:k}$可以通过从时刻$1$到时刻$k$的前向滤波来计算。事实表明，后向消息$b_{k+1:t}$可以通过从时刻$t$开始的后向运行的递归过程来计算：
$$
b_{k+1:t}=P\left( e_{k+1:t}|X_k \right) =\sum_{x_{k+1}}{P\left( e_{k+1:t}|X_k,x_{k+1} \right) P\left( x_{k+1}|X_k \right)}
$$
$$
=\sum_{x_{k+1}}{P\left( e_{k+1:t}|x_{k+1} \right) P\left( x_{k+1}|X_k \right)}=\sum_{x_{k+1}}{P\left( e_{k+1},e_{k+2:t}|x_{k+1} \right) P\left( x_{k+1}|X_k \right)}
$$
$$
=\sum_{x_{k+1}}{P\left( e_{k+1}|x_{k+1} \right) P\left( e_{k+2:t}|x_{k+1} \right) P\left( x_{k+1}|X_k \right)}
$$
在这个表达式中，所有的项要么来自模型，要么来自之前的后向消息。因此，得到了想要的递归公式。在消息形式上有：
$$
b_{k+1:t}=Backward\left( b_{k+2:t}|e_{k+1} \right)
$$
其中 Backward 实现如前所述的更新。与前向递归一样，后向递归每次更新所需的时间代价和空间代价也是与$t$无关的常量。式平滑递归中的两项都可以通过对时间进行递归来计算，一项使用滤波$Forward$，从时刻$1$向前运行到$k$，另一项使用$Backward$从时刻$t$向后运行到$k+1$。后向阶段的初始化，以全 1 向量作为开始。
前向递归和后向递归每一步所花费的时间都是常量的；因此，对证据$e_{1:t}$进行平滑的时间复杂性为$O(t)$。这是对特定的时间步$k$进行平滑的复杂性。如果想要平滑整个序列，一个显而易见的方法是简单地为每个需要平滑的时间步运行一次完整的平滑过程。这个过程的时间复杂性为$O(t^2)$。
更好的方法是简单应用动态规划将复杂性降低到$O(t)$。从上文中对雨伞示例的分析中可以发现，能够复用前向滤波阶段的结果。线性时间算法的关键是记录整个序列的前向滤波结果。然后，从时刻$t$到时刻$1$运行后向递归，从计算的后向消息$b_{k+1:t}$和存储的前向消息$f_{1:k}$来计算每步$k$的平滑估计，该算法被恰当地称为前向-后向算法。
前向-后向算法充当了许多处理噪声观测序列的应用的计算支柱。从到目前为止对前向-后向算法的描述来看，它有两个实际的缺点。第一个缺点是当状态空间庞大且序列很长时，算法的空间复杂性可能过高。它使用了$O\left( \left| f \right|t \right) $的空间，其中$\left| f \right|$是前向消息表示的大小。经过一定的修改，可以把空间复杂性降低到$O\left( \left| f \right|\log t \right) $，但相应的时间复杂性也会增加一个$logt$因子。
这个基本算法的第二个缺点是，它需要进行修改以便在在线环境下工作——随着新的观测数据不断添加到序列末尾时，对较早的时间片进行平滑估计计算。最常见的要求是定滞后平滑，这需要对固定的滞后$d$计算平滑估计$P\left( X_{t-d}|e_{1:t} \right) $。也就是说，只对比当前时刻$t$滞后$d$步的时间片做平滑。随着时刻$t$的增加，平滑必须跟上。显然，可以在每增加一个新的观测时在$d$步窗口上运行前向-后向算法，但这似乎效率不高。但是在某些情况下，定滞后平滑可以独立于滞后$d$在常数时间内完成每次更新。
最可能解释：给定一个观测序列，找到最有可能产生这些观测值的状态序列。寻找最可能序列且具有线性时间的算法是存在的，它依赖于产生高效的滤波和平滑算法的马尔可夫特性。其想法是把每个序列看作图中的一条路径，其中图的节点是每个时间步上可能的状态。现在希望在这个图中找到最可能的路径，其中任一路径的似然是沿着路径的转移概率和每个状态下给定观测值的概率的乘积。
此外，到达每个状态$x_{t+1}$的最可能路径与到达每个状态$x_t$的最可能路径之间存在递归关系。可以利用这个特性直接构造一个递归算法来计算给定证据的最可能路径。将使用递归计算的消息$m{1:t}$，它与滤波算法中的前向消息$f_{1:t}$是类似的。这个消息的定义如下：
$$
m_{1:t}=\underset{x_{1:t-1}}{\max}P\left( x_{1:t-1},X_t,e_{1:t} \right)
$$
接下来推导递归关系：
$$
m_{1:t+1}=\underset{x_{1:t}}{\max}\ P\left( x_{1:t},X_{t+1},e_{1:t+1} \right) =\underset{x_{1:t}}{\max}\ P\left( x_{1:t},X_{t+1},e_{1:t},e_{t+1} \right)
$$
$$
=\underset{x_{1:t}}{\max}\ P\left( e_{t+1}|x_{1:t},X_{t+1},e_{1:t} \right) P\left( x_{1:t},X_{t+1},e_{1:t} \right) \left[ \text{链式法则} \right]
$$
$$
=\underset{x_{1:t}}{\max}\,\,P\left( e_{t+1}|X_{t+1} \right) P\left( x_{1:t},X_{t+1},e_{1:t} \right) \left[ \text{传感器假设} \right]
$$
$$
=\,P\left( e_{t+1}|X_{t+1} \right) \underset{x_{1:t}}{\max}\,P\left( x_{1:t},X_{t+1},e_{1:t} \right) \left[ \text{分离无关变量} \right]
$$
$$
=\,P\left( e_{t+1}|X_{t+1} \right) \underset{x_{1:t}}{\max}\,P\left( X_{t+1}|x_{1:t},e_{1:t} \right) P\left( x_{1:t},e_{1:t} \right) \left[ \text{链式法则} \right]
$$
$$
=\,P\left( e_{t+1}|X_{t+1} \right) \underset{x_{1:t}}{\max}\,P\left( X_{t+1}|x_t \right) P\left( x_{1:t},e_{1:t} \right) \left[ \text{转移模型} \right]
$$
$$
=\,P\left( e_{t+1}|X_{t+1} \right) \underset{x_{1:t}}{\max}\,P\left( X_{t+1}|x_t \right) P\left( x_{1:t-1},x_t,e_{1:t} \right) \left[ \text{证据分解} \right]
$$
$$
=\,P\left( e_{t+1}|X_{t+1} \right) \underset{x_t}{\max}P\left( X_{t+1}|x_t \right) \underset{x_{1:t-1}}{\max}\,P\left( x_{1:t-1},x_t,e_{1:t} \right) \left[ \text{分离} \right]
$$
$$
==\,P\left( e_{t+1}|X_{t+1} \right) \underset{x_t}{\max}P\left( X_{t+1}|x_t \right) \cdot m_{1:t}\left[ \text{递归} \right]
$$
计算最可能序列的算法类似于滤波：它从时刻$0$以先验$m_{1:0}=P\left( X_0 \right) $开始，沿着序列前向运行，利用上式在每个时间步计算消息$m$。在观测序列的末尾，$m_{1:t}$将包含到达每个最终状态的最可能的序列的概率。人们可以很容易选择整体最可能序列的最终状态。为了确定实际的序列，而不仅仅是计算概率，该算法还需要为每个状态记录指向它的最佳状态。
以上算法被称为维特比算法，它以发明者安德鲁·维特比的姓氏命名。和滤波算法一样，它的时间复杂性与序列长度 t 呈线性关系。与使用常量空间的滤波不同，它的空间需求也与$t$呈线性关系。这是因为维特比算法需要保留指针以识别指向每个状态的最佳序列。最后一个实际的问题是：数值下溢是维特比算法的一个重要问题。在递归中概率随着步数变得越来越小，而算法可能有成千上万步。该问题的一种可能的解决方案是在每一步对$m$进行归一化；这种缩放不会影响正确性。第二种解决方案是在计算中处处使用对数概率并用加法代替乘法。同样，其正确性不受影响，因为
$log$函数是单调的.
学习：如果不知道转移模型与传感器模型，那么可以从观测中学习。与静态贝叶斯网络类似，动态贝叶斯网络学习可以作为推断的副产品来完成。推断对实际发生的转移以及产生传感器读数的状态进行估计，这些估计可用于学习模型。学习过程可以通过一种称为期望最大化或$EM$的迭代更新算法来实现，也可以由来自给定证据时模型参数的贝叶斯更新实现。
