机器学习笔记之卡尔曼滤波(一)动态模型基本介绍

引言

本节从动态模型开始，介绍卡尔曼滤波(Kalman Filter)。

回顾：动态模型

我们在机器学习笔记之隐马尔可夫模型中已经介绍了一种动态模型。
假设数据集合$\mathcal{X}$在某连续时刻 { 1 , 2 , ⋯   , T } \{1,2,\cdots,T\} {1,2,⋯,T}内的观测值序列 { o 1 , o 2 , ⋯   , o T } \{o_1,o_2,\cdots,o_T\} {o1​,o2​,⋯,oT​}表示如下：

由于这些观测值是基于同一数据集合$\mathcal{X}$在连续时刻下的观测结果。从常理角度思考，相邻观测值之间存在关联关系。但观测值序列中的关联关系可能不是显式关系，即无法通过观测值序列直接写出它们之间的关联关系。因此有了动态模型的假设(Dynamic Model)：

动态模型是指 观测变量的变化规律是基于隐变量$\mathcal{I}$随着时间/序列的变化而变化，从而影响观测变量$\mathcal{O}$的变化。其概率图模型可表示为如下形式：

称 O = { o 1 , o 2 , ⋯   , o T } \mathcal O = \{o_1,o_2,\cdots,o_{T}\} O={o1​,o2​,⋯,oT​}为观测变量， I = { i 1 , i 2 , ⋯   , i T } \mathcal I = \{i_1,i_2,\cdots,i_{T}\} I={i1​,i2​,⋯,iT​}为隐变量。这种概率图模型也称状态空间模型(State Space Model)，这种模型的核心思想是：
如果找到了隐变量之间的关联关系，观测变量只与对应时刻的隐变量之间存在关联关系，从而观测变量之间相互独立。
这看起来和上述介绍的‘相邻观测值之间存在关联关系’相悖，实际上，只是将‘观测变量中的关联关系’转移至隐变量中，而观测变量被看成‘对应时刻给定隐变量下的结果’。
这种概率图表示也完全符合‘贝叶斯网络’中的描述。以$o_t$为例，可能与$o_t$相关联的结点表示如下：

上图描述的是贝叶斯网络结构表示中提到的‘同父结构’和‘顺序结构’。但无论是其中哪种结构，在给定隐变量$i_t$的条件下，$o_t$与$i_{t-1},i_{t+1}$之间均条件独立。
这也是动态模型中的 观测独立性假设。

动态模型中共包含三类概率：

• 发射概率(Emission Probability)：它描述给定某时刻隐变量$i_t$的条件下，对应时刻观测变量$o_t$的条件概率。
  $$\mathcal{P}(o_t\mid i_t)$$
• 状态转移概率(Transition Probability)：给定某时刻隐变量$i_t$的条件下，后续时刻隐变量$i_{t+1}$的条件概率。
  这里以‘一阶齐次马尔可夫假设’为例。
  $$\mathcal{P}(i_{t+1}\mid i_t)$$
• 初始概率(initial Probability)：在计算隐变量的概率时，基于状态转移概率，我们需要给定上一时刻的隐变量信息，但初始时刻的隐变量概率$\mathcal{P}(i_1)$需要人为给定。

马尔可夫模型的特点是 每一时刻的隐变量$i_t(t=1,2,\cdots ,T)$必须是离散型随机变量，而对应观测变量$o_t(t=1,2,\cdots ,T)$不做要求。
通常为了简化运算，也将观测变量$o_t$定义为‘离散型随机变量’。

如果 隐变量是连续型随机变量，可分为两种情况：

• 线性动态系统/卡尔曼滤波(Linear Dynamic System)：线性动态系统中的观测变量$\mathcal{O}$和隐变量$\mathcal{I}$均属于连续型随机变量，并且各时刻$i_t,o_t(t=1,2,\cdots ,T)$均服从各自的线性关系，且噪声均服从高斯分布(各自对应的高斯分布)。
  从变量的分布条件角度，也可称卡尔曼滤波为‘线性高斯模型’(Linear Gaussian Model)。
• 粒子滤波(Particle Filter)：与卡尔曼滤波对应，它的观测变量$\mathcal{I}$与隐变量$\mathcal{O}$属于非线性关系，而噪声也属于非高斯分布。

动态模型的相关任务

• 学习任务(Learning问题)：
  学习任务本质上是通过给定的观测变量$\mathcal{O}$，使用EM算法求解模型参数$\lambda$。由于隐马尔可夫模型中隐变量$\mathcal{I}$与观测变量$\mathcal{O}$都是离散型随机变量，因此可以直接使用 狭义EM算法 迭代求解模型参数。
  相关推导过程见隐马尔可夫模型(五)学习问题——EM算法
• 推断任务(Inference问题)：
  推断任务本质上是求解 变量的概率问题。主要包含以下几种情况：
  • 解码任务(Decoding)：给定观测序列 { o 1 , o 2 ⋯   , o t } \{o_1,o_2\cdots,o_t\} {o1​,o2​⋯,ot​}条件下，求解对应时刻隐变量序列 { i 1 , i 2 , ⋯   , i t } \{i_1,i_2,\cdots,i_t\} {i1​,i2​,⋯,it​}的条件概率：
    $$\mathcal{P}(\mathcal{I}\mid \mathcal{O})=\mathcal{P}(i_1\cdots ,i_t\mid o_1,\cdots ,o_t)$$
    在隐马尔可夫模型中介绍了维特比算法(Viterbi)，最终得到一组使得$\mathcal{P}(\mathcal{I}\mid \mathcal{O})$最大的隐变量序列取值结果 I ^ = { i 1 ∗ , ⋯   , i t ∗ } \hat {\mathcal I} = \{i_1^*,\cdots,i_t^*\} I^={i1∗​,⋯,it∗​}：
    $$\hat{\mathcal{I}}=\underset{\mathcal{I}}{\mathrm{argmax}}\mathcal{P}(\mathcal{I}\mid \mathcal{O};\lambda )$$
  • 求值问题(Probability of Evidence)：基于模型参数$\lambda$，求解观测变量序列 O = { o 1 , o 2 , ⋯   , o T } \mathcal O = \{o_1,o_2,\cdots,o_T\} O={o1​,o2​,⋯,oT​}的联合概率分布结果：
    $$\mathcal{P}(\mathcal{O}\mid \lambda )=\mathcal{P}(o_1,\cdots ,o_T\mid \lambda )$$
    在隐马尔可夫模型中，针对直接求解$\mathcal{P}(\mathcal{O}\mid \lambda )$过程中时间复杂度随着时刻的增加指数倍增长的情况$({\mathcal{K}}^T)$，分别介绍了前向算法(Forward Algorithm)：
    其中$\mathcal{K}$表示‘离散型随机变量’的隐状态存在$\mathcal{K}$种选择。
    P ( O ∣ λ ) = ∑ i T P ( O , i T = q i ∣ λ ) = ∑ i = 1 K P ( O , i T = q i ∣ λ )
    P(O∣λ)=∑iTP(O,iT=qi∣λ)=∑i=1KP(O,iT=qi∣λ)" role="presentation">P(O∣λ)=∑iTP(O,iT=qi∣λ)=∑i=1KP(O,iT=qi∣λ)$$\begin{array}{rl}\mathcal{P}(\mathcal{O}\mid \lambda )& =\sum _{i_T}\mathcal{P}(\mathcal{O},i_T=q_i\mid \lambda )\\ & =\sum _{i=1}^{\mathcal{K}}\mathcal{P}(\mathcal{O},i_T=q_i\mid \lambda )\end{array}$$
    P(O∣λ)​=iT​∑​P(O,iT​=qi​∣λ)=i=1∑K​P(O,iT​=qi​∣λ)​
    和后向算法(Backward Algorithm)：
    P ( O ∣ λ ) = ∑ i 1 P ( O , i 1 = q i ∣ λ ) = ∑ i 1 P ( O ∣ i 1 = q i , λ ) ⋅ P ( i 1 = q i ∣ λ )
    P(O∣λ)=∑i1P(O,i1=qi∣λ)=∑i1P(O∣i1=qi,λ)⋅P(i1=qi∣λ)" role="presentation">P(O∣λ)=∑i1P(O,i1=qi∣λ)=∑i1P(O∣i1=qi,λ)⋅P(i1=qi∣λ)$$\begin{array}{rl}\mathcal{P}(\mathcal{O}\mid \lambda )& =\sum _{i_1}\mathcal{P}(\mathcal{O},i_1=q_i\mid \lambda )\\ & =\sum _{i_1}\mathcal{P}(\mathcal{O}\mid i_1=q_i,\lambda )\cdot \mathcal{P}(i_1=q_i\mid \lambda )\end{array}$$
    P(O∣λ)​=i1​∑​P(O,i1​=qi​∣λ)=i1​∑​P(O∣i1​=qi​,λ)⋅P(i1​=qi​∣λ)​
  • 滤波问题(Filtering)：给定初始时刻到当前时刻的观测变量序列 { o 1 , o 2 , ⋯   , o t } \{o_1,o_2,\cdots,o_t\} {o1​,o2​,⋯,ot​}，求解当前时刻隐变量$i_t$的条件概率：
    这明显是一个‘在线算法’(on-line Algorithm),只有在对应时刻以及之前所有时刻观测变量给定的条件下，才能够计算出当前时刻的隐变量信息。
    $$\mathcal{P}(i_t\mid o_1,o_2\cdots ,o_t)$$
  • 平滑问题(Smoothing)：给定完整的观测变量序列 { o 1 , o 2 ⋯   , o T } \{o_1,o_2\cdots,o_T\} {o1​,o2​⋯,oT​}，求解某时刻隐变量$i_t$的条件概率：
    与‘滤波问题’相对应的，这是一个‘离线算法’(off-line Algorithm)，在完整序列的观测变量给定的条件下，可以计算任意时刻的隐变量信息。
    $$\mathcal{P}(i_t\mid o_1,o_2,\cdots ,o_T)$$
  • 预测问题(Prediction)：该问题的核心在于 基于已知时刻的观测变量 { o 1 , o 2 , ⋯   , o t } \{o_1,o_2,\cdots,o_t\} {o1​,o2​,⋯,ot​}，对未来时刻的变量(如$i_{t+1},o_{t+1}$)进行预测：
    $$\begin{gathered} \mathcal{P}(i_{t+1},i_{t+2}\mid o_1,o_2,\cdots ,o_t) \\ \mathcal{P}(o_{t+1},o_{t+2}\mid o_1,o_2,\cdots ,o_t) \end{gathered}$$

卡尔曼滤波介绍

与隐马尔可夫模型类似，卡尔曼滤波主要从三个方面进行描述：

• 初始概率：对于初始隐变量的概率$\mathcal{P}(i_1)$，初始化一个高斯分布：
  $$\mathcal{P}(i_1)\sim \mathcal{N}({\mu }_1,{\Sigma }_1)$$
• 发射概率：$t$时刻的隐变量$i_t$与$t-1$时刻的隐变量$i_{t-1}$之间存在线性关系。
  $$i_t=\mathcal{A}\cdot i_{t-1}+\mathcal{B}+ϵ$$
  其中$\mathcal{A},\mathcal{B}$表示线性关系的参数(参数向量)，$ϵ$表示观察隐变量时的噪声信息，假设噪声服从均值为0的高斯分布：
  $\mathcal{Q}$表示基于$i_t$噪声的协方差信息。
  $$ϵ\sim \mathcal{N}(0,\mathcal{Q})$$
• 状态转移概率：$t$时刻的隐变量$i_t$与对应时刻的观测变量$o_t$之间存在线性关系。
  $$o_t=\mathcal{C}\cdot i_t+\mathcal{D}+\delta$$
  同理，$\mathcal{C},\mathcal{D}$表示线性关系的参数(参数向量)，$\delta$表示观测变量的噪声信息，这里同样假设噪声服从高斯分布：
  $\mathcal{R}$表示基于$o_t$噪声的协方差信息。
  $$\delta \sim \mathcal{N}(0,\mathcal{R})$$

这里回顾隐马尔可夫模型中的状态转移过程：

• 隐马尔可夫模型中使用状态转移矩阵描述 隐变量之间的状态转移过程：$\mathcal{A}=[a_{ij}{]}_{\mathcal{K}\times \mathcal{K}}$，其中$a_{ij}$表示隐变量$i_t$与隐变量$i_{t+1}$之间的条件概率：
  $$a_{ij}=\mathcal{P}(i_{t+1}=q_j\mid i_t=q_i)$$
• 隐马尔可夫模型中使用发射矩阵描述 隐变量与对应时刻观测变量之间的状态转移过程：$\mathcal{B}=[b_j(k){]}_{\mathcal{K}\times \mathcal{M}}$
  $$b_j(k)=\mathcal{P}(o_t=v_k\mid i_t=q_j)$$

那么，卡尔曼滤波中状态转移概率$\mathcal{P}(i_{t+1}\mid i_t)$和发射概率$\mathcal{P}(o_t\mid i_t)$的具体表示为：
一个线性函数 + 高斯分布，并不影响其结果是高斯分布的本质，其结果仅对高斯分布的均值位置进行平移，对协方差结果不产生影响。
$$\begin{gathered} \mathcal{P}(i_t\mid i_{t-1})\sim \mathcal{N}(\mathcal{A}\cdot i_{t-1}+\mathcal{B},\mathcal{Q}) \\ \mathcal{P}(o_t\mid i_t)\sim \mathcal{N}(\mathcal{C}\cdot i_t+\mathcal{D},\mathcal{R}) \end{gathered}$$

隐马尔可夫模型与卡尔曼滤波中需要求解的模型参数对比如下：
λ = { ( π , A , B ) → H i d d e n M a r k o v M o d e l ( A , B , C , D , Q , R , μ 1 , Σ 1 ) → K a l m a n F i l t e r \lambda =

λ={(π,A,B)→HiddenMarkovModel(A,B,C,D,Q,R,μ1​,Σ1​)→KalmanFilter​

相关参考：
徐亦达机器学习：Kalman-Filter-part-1
机器学习-线性动态系统1-KalmanFilter-背景介绍