隐马尔可夫模型
隐马尔可夫模型是一种时序概率模型，其过程状态由单个离散随机变量描述。变量的可能的值是世界的可能状态。虽然隐马尔可夫模型要求状态是单个离散变量，但它对证据变量没有相应的限制。这是因为证据变量总是被观测的，这意味着没有必要追踪有关它们值的任何分布。（如果一个变量未被观测，可以简单地将它从模型的那个时间步中移除）。同时隐马尔可夫模型也允许有多个离散的或连续的证据变量存在。
对于单个离散状态变量$X_t$，可以给出转移模型、传感器模型以及前向消息和后向消息的具体表示形式。用整数$1, …, S$表示状态变量$X_t$的可能值，其中$S$是可能状态的数量。那么转移模型$P\left( X_t|X_{t-1} \right) $就变成了一个$S\times S$的矩阵$T$，其中：
$$
P\left( X_t|X_{t-1} \right) =T=t_{ij}=P\left( X_t=j|X_{t-1}=i \right)
$$
也就是说，$t_{ij}$是从状态$i$转移到状态$j$的概率。用同样的方法，可以把传感器模型写成矩阵形式。因为证据变量$E_t$的值在时刻$t$已经得知（称为$e_t$），因此只需要为每个状态指定它导致$e_t$出现的概率。为了数学上的方便，把这些值放入一个对角观测矩阵$O_t$，在每个时间步都构造一个这样的矩阵。$O_t$的第$i$个对角元素是$P\left( e_t|x_t=i \right) $，其余每个元素均为 0。
现在，如果使用列向量来表示前向消息和后向消息，那么所有的计算都可以转换为简单的矩阵-向量运算。前向公式变成：
$$
P\left( X_{t+1}|e_{1:t+1} \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)}
$$
$$
\Downarrow
$$
$$
f_{1:t+1}=\alpha O_{t+1}T^Tf_{1:t}
$$
后向公式变为：
$$
b_{k+1:t}=P\left( e_{k+1:t}|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)}
$$
$$
\Downarrow
$$
$$
b_{k+1:t}=TO_{k+1}b_{k+1}
$$
从这些公式中可以看出，应用于长度为$t$的序列的前向-后向算法的时间复杂性是$O(S^2\cdot t)$，因为每步需要一个$S$元向量与一个$S \times S$矩阵相乘。算法的空间需求是$O(S\cdot t)$，因为前向传递存储$t$个$S$元向量。除了为隐马尔可夫模型提供优雅的滤波和平滑算法的表示，矩阵形式还揭示了改进算法的机会。
这两项改进主要关注于平滑的计算，平滑的计算公式为$\alpha f_{1:k}\times b_{k+1:t}$，其复杂性主要是由于每步计算都要重新进行前向信息和后向信息的传递，改进的主要想法是通过$\alpha f_{1:k}$和$b_{k+1:t}$计算出$\alpha f_{1:k+1}$和$b_{k+2:t+1}$。
第一个改进的角度基于前向-后向算法的一个简单变体，它使平滑可以在独立于序列长度的常数空间中进行。改进算法一的大致想法如下：对任意特定的时间片$k$进行平滑需要同时存有前向消息$f_{1:k}$和后向消息$b_{k+1:t}$。前向-后向算法通过存储在前向传递时计算的$f$来实现这一点，并方便它们在后向传递期间可用。实现这一目标的另一种方法是在同一个方向上传播$f$和$b$。比如将前向消息转变为如下形式的反向传播：
$$
f_{1:t}=\alpha ‘\left( T^T \right) ^{-1}O_{t+1}^{-1}f_{1:t+1}
$$
修改后的平滑算法首先运行标准的前向传递计算$f_{t:t}$（抛弃所有中间结果），之后对$b$和$f$共同执行后向传递，并使用它们在每一步计算平滑估计。因为每条消息只需要一个副本，所以存储需求是常数的（即与序列的长度$t$无关）。该算法有两个明显的限制：它要求转移矩阵是可逆的，并且传感器模型不存在零概率，即每个观测在每个状态下都是可能的。
矩阵形式揭示算法的第二个改进是在固定滞后的在线平滑方面。平滑可以在常数空间中完成这一事实表明，应该存在一种高效的在线平滑的递归算法，即一种时间复杂性与滞后长度无关的算法。假设滞后为$d$；也就是说，当前时间为$t$时，在时间步$t-d$处进行平滑，根据平滑公式：
$$
\alpha f_{1:t-d}\times b_{t-d+1:t}
$$
然后，当新的观测值到达时，需要为时间片$t-d+1$计算：
$$
\alpha f_{1:t-d+1}\times b_{t-d+2:t+1}
$$
前向信息传递的增量形式只需要标准滤波即可计得，以增量方式计算后向消息要复杂一些，因为旧的后向消息$b_{t-d+1:t}$与新的后向消息$b_{t-d+2:t+1}$之间没有简单的关系。考虑：
$$
b_{t-d+1:t}=\left( \prod_{i=t-d+1}^t{TO_i} \right) b_{t+1:t}=B_{t-d+1:t}1
$$
$$
b_{t-d+2:t+1}=\left( \prod_{i=t-d+2}^{t+1}{TO_i} \right) b_{t+2:t+1}=B_{t-d+2:t+1}1
$$
联立以上两式有：
$$
B_{t-d+2:t+1}=O_{t-d+1}^{-1}T^{-1}B_{t-d+1:t}TO_{t+1}
$$
完整的算法要求存储与更新 f 和 B：
卡尔曼滤波器
滤波：根据一段时间内带有噪声的观测来估计状态变量（在这里是运动对象的位置和速度）。如果变量是离散的，可以用隐马尔可夫模型来建模系统。处理连续变量则需要使用算法，该算法以它的发明者之一鲁道夫·卡尔曼的名字命名。
它使用采用线性高斯分布来表示转移模型和传感器模型，这意味着下一个状态$X_{t+1}$必须是当前状态$X_t$的线性函数，再加上某些高斯噪声，这个条件在实践中被证明是相当合理的。
线性高斯分布族的一个关键性质：在贝叶斯更新下它保持封闭。（也就是说，给定任何证据，后验分布仍然属于线性高斯族。）
单步预测的分布是高斯分布：
$$
P\left( X_{t+1}|e_{1:t} \right) =\int_{x_t}{P\left( X_{t+1}|x_t \right) P\left( x_t|e_{1:t} \right) dx}
$$
以新证据为条件的更新后的分布是高斯分布：
$$
P\left( X_{t+1}|e_{1:t+1} \right) =\alpha P\left( e_{t+1}|X_{t+1} \right) P\left( X_{t+1}|e_{1:t} \right)
$$
卡尔曼滤波器及其具体阐述被广泛应用。经典的应用是对飞行器和导弹的雷达追踪。相关的应用包括潜艇和地面车辆的声学追踪以及车辆和人的视觉追踪。在一些更加深奥的领域，卡尔曼滤波器被用来从气泡室照片重建粒子轨迹和从卫星地表测量重建洋流。它的应用范围远不止于运动追踪：它在任何通过连续状态变量和噪声测量刻画的系统中都可以使用。这些系统包括纸浆厂、化工厂、核反应堆、植物生态系统和国民经济。
卡尔曼滤波可以应用于很多系统，但这并不意味着它的结果是有效的或有用的。滤波所作的线性高斯转移模型和传感器模型假设是非常强的。扩展卡尔曼滤波器试图克服建模系统中的非线性。如果一个系统的转移模型不能被描述为状态向量的矩阵乘积，那么称这个系统是非线性的。这对于光滑的、行为良好的系统表现良好，并允许追踪器去维护和更新高斯状态分布，是真实后验的合理近似。
现实中一个系统往往是“不光滑”或“行为不良”的，为了处理这样的问题需要一种更富表达能力的语言来表示所建模的系统的行为。在控制理论领域，例如飞机的规避机动等问题也会带来同样的困难，一个标准的解决方案是使用切换卡尔曼滤波器。在这种方法中，多个卡尔曼滤波器并行运行，且每个滤波器使用不同的系统模型。
