机器学习笔记19: 线性二次型高斯

线性二次型高斯(Linear Quadratic Gaussian (LQG))

在现实世界中，我们通常不能获取到所有的状态s_t。比如一个自动驾驶汽车可以通过摄像头获取图像，但这仅仅是一个观察(observation)，并不能反映真实世界的所有状态。我们之前的讨论都是基于状态是可以完全获得的。考虑到真实世界并不是这样，我们需要一个新工具来对真实世界建模，这个工具就是部分可观测的MDP(Partially Observable MDP (POMDP))。

一个POMDP是在MDP的基础上增加一个观察层。也就是说，我们引入一个新变量o_t，在给定状态s_t下，o_t遵循某个条件概率分布，即：

一个有界的POMDP由如下六元组构成：

在这个框架下，一般的策略是基于一组观察o₁, ..., o_t维护一个信念状态(belief state)(状态的概率分布)。而一个POMDP的策略将信念状态映射成行动。

这一小节我们将对LQR做一些扩展，假设我们观察到y_t∈ R^m并且有：

其中C ∈ R^m×n是一个压缩矩阵(compression matrix)，v_t是噪音(和w_t一样都是服从高斯分布)。注意现在奖励函数的定义保持不变，依旧是关于状态和行动的一个函数。由于概率分布是高斯的，所以信念状态也服从高斯分布。在这个新设定下，我们来看下求解最佳策略的方法。

步骤1: 首先基于观察求出可能状态的概率分布

其中s_t|t和Σ_t|t分别为这个概率分布的均值和方差

步骤2: 使用均值s_t|t作为s_t的最佳近似

步骤3: 最佳行动a_t := L_ts_t，其中L_t的定义来自普通LQR算法

由于LQR中我们已经证明结果与噪音无关，所有步骤2中我们可以用s_t|t作为s_t的最佳近似。

其中步骤1我们需要详细展开讲一下。简单起见，我们先考虑动态模型与行动无关，假设：

由于噪音都服从高斯分布，因此它们的联合分布也服从高斯分布，即：

根据在因子分析中介绍的边缘概率分布公式，可得：

然而计算边缘分布非常耗时，这需要我们对t×t的矩阵进行计算。由于计算一个逆矩阵的时间复杂度是O(t³)，而这个计算需要重复t次，因此总的时间复杂度是O(t⁴)。

为了提高计算的速度，我们将采用卡尔曼滤波(Kalman filter)算法来计算均值和方差，这个算法的时间复杂度只有O(t)。

卡尔曼滤波算法只有两步：预测步(predict step)和更新步(update step)。假设我们知道s_t|y₁, ..., y_t的概率分布，即：

那么：

预测步: 下一个状态的概率也服从高斯分布，并且：

更新步: 给定s_t+1|t和Σ_t+1|t，并且满足：

我们可以证明：

其中：

矩阵K_t被称为卡尔曼增益(Kalman gain)。

如果我们仔细看一下上面的公式，会发现我们并不需要上一个时刻的观察值。更新步中只需要依赖上一步的概率分布。总的来说，这个算法首先进行向前推算(forward pass)计算出K_t, Σ_t|t和s_t|t，然后再进行向后推算(backward pass)(也就是LQR更新)计算出Φ_t, Ψ_t和L_t，最后根据公式a_t^* = L_ts_t|t计算出最优策略。

总结

• 由于在现实世界中通常不能获取到所有的状态，我们只能获取到观察值，因此在MDP的基础上增加一个观察层，这个模型叫做POMDP
• 求解POMDP的最优策略需要用到卡尔曼滤波算法，该算法时间复杂度只有O(t)，可以大幅提高运算性能

参考资料

• 斯坦福大学机器学习课CS229讲义 LQR, DDP and LQG
• 网易公开课：机器学习课程 双语字幕视频