Particle Filtering, Utility Theory(16)

我们已经学习了隐马尔可夫模型（HMMs），但当状态空间变得非常大或连续时，精确的前向算法在计算上变得不可行。粒子滤波提供了一种强大的近似推理方法来解决这个问题, 是HMMs的“采样”版本。。

粒子滤波

粒子滤波的核心目标是，在一个动态系统中，根据一系列带噪音的、不完整的观测数据，实时地、近似地追踪一个我们无法直接看到的隐藏状态。

它专门用于解决那些状态空间巨大或连续的问题，例如：

• 机器人定位：机器人在一个连续的2D或3D空间中的精确位置。

• 物体追踪：追踪雷达信号中飞机的精确位置和速度。

• 金融预测：追踪一个经济体背后那个复杂且不可见的“真实状态”。

在这些问题中，像前向算法那样的精确算法因为需要处理无限或天文数字级别的状态而完全不可行。

其核心思想是, 用“群体智慧”近似“真实情况”, 放弃了为每个可能状态计算精确概率的想法，转而采用一种基于采样的“群体模拟”思想

在HMM模型下的步骤

HMM是描述问题的“理论框架”，而粒子滤波则是解决这个框架下特定问题的一种实用算法

首先, 我们再次阐述HMM的模型结构:

• 隐藏状态 (X_t)：我们关心但无法直接观测的变量（例如，物体的真实位置）。

• 观测证据 (E_t)：我们能实际测量到的数据（例如，摄像头的读数）。

• 初始分布 (P(X₀))：描述了在最开始时，隐藏状态的概率分布。

• 转移模型 (P(X_t + 1|X_t))：描述了隐藏状态随时间演变的规律（例如，物体如何从一个位置移动到另一个位置）。

• 发射模型 (P(E_t|X_t))：描述了在某个隐藏状态下，产生特定观测证据的概率（例如，在某个真实位置，摄像头读数为某值的概率）。

HMM的目标之一：计算在给定所有历史观测证据 e_1 : t 的情况下，当前隐藏状态 X_t 的概率分布，即 P(X_t|e_1 : t)。当状态空间巨大时，粒子滤波就是实现这一目标的强大工具。

而粒子滤波的每一步, 恰恰精确地对应了HMM框架的每一个组成部分：

1. 初始化 (Initialization) 算法操作：生成 N 个初始粒子，每个粒子代表一个对初始隐藏状态的猜测。

HMM中的对应：这个过程直接使用了HMM的初始分布 P(X₀)。算法会根据 P(X₀) 来进行采样。如果初始分布是均匀的，粒子就会被均匀地撒在所有可能的状态上；如果初始分布集中在某个区域，那么大部分粒子就会被生成在该区域。

2. 提议 (Proposal) 算法操作：对于现有的每一个粒子，预测它在下一个时间步的位置。这也被称为时间流逝更新。

HMM中的对应：这个预测过程完全由HMM的转移模型 P(X_t + 1|X_t) 驱动。对于一个当前状态为 x_t 的粒子，算法会从条件概率分布 P(X_t + 1|X_t = x_t) 中随机采样一个新的状态 x_t + 1，作为该粒子移动后的新位置。

3. 加权 (Weighting) 算法操作：在粒子完成移动后，我们获取了新的观测证据 e_t + 1。现在，我们需要根据这个新证据为每一个粒子打分（赋予权重）。

HMM中的对应：这个打分过程精确地使用了HMM的发射模型 P(E_t|X_t)。对于一个预测位置为 x_t + 1 的粒子，它的权重正比于 P(E_t + 1 = e_t + 1|X_t + 1 = x_t + 1)。这意味着，如果一个粒子的预测位置能够很好地”解释”我们看到的证据，它的权重就高；反之则权重低。

4. 重采样 (Resampling) 算法操作：淘汰低权重的粒子，复制高权重的粒子，生成新一代的粒子群。

HMM中的对应：这一步是整个滤波（Filtering）过程的核心。它将由发射模型提供的信息（即权重）“吸收”到粒子群中，使得新的粒子群能够更好地近似后验概率分布 P(X_t + 1|e_{1 : t + 1})。具体步骤是从旧的粒子中进行有放回的随机抽样来生成新100个粒子。一个粒子被抽中的概率正比于它的权重。这是实现”用观测来修正预测”的关键机制。

效用与决策 (Utilities & Decision Networks)

这部分将我们从单纯的“信念推理”带入到“理性决策”的领域。

理性偏好 (Rational Preferences)

核心问题：一个理性智能体应该如何做出选择？讲义指出，它必须遵循最大化期望效用 (Maximum Expected Utility) 的原则。

换句话说, 它必须遵从以下五条理性的公理 (Axioms of Rationality)：

• 可排序性 (Orderability)：对于任意两个选项，总能做出偏好判断。

• 传递性 (Transitivity)：偏好不能形成循环。

• 连续性 (Continuity)：对于不同偏好的选项，总能找到一个概率组合使其等价。

• 可替代性 (Substitutability)：如果两个选项等价，那么它们在更复杂的选择中可以相互替换。

• 单调性 (Monotonicity)：如果更喜欢A而不是B，那么在其他条件相同时，会选择获得A概率更高的那个选项。

如果一个智能体的偏好满足这些公理，那么必然存在一个实值效用函数 U，使得智能体的行为可以被描述为在最大化这个函数的期望值。

决策网络 (Decision Networks)

决策网络是贝叶斯网络的一个扩展，它将概率、行动和效用整合到了一个统一的图形模型中, 可以被看作是贝叶斯网络和期望最大化 (Expectimax) 算法的结合体 。

其具有三种节点类型：

• 机会节点 (Chance Nodes)：椭圆形，代表随机变量，和贝叶斯网络中的节点一样。

• 行动节点 (Action Nodes)：矩形，代表智能体可以选择的行动。

• 效用节点 (Utility Nodes)：菱形，代表最终的效用值。效用节点是决策网络的核心，它没有子节点，其父节点通常是行动节点和一些机会节点 。它的作用是根据其父节点的状态（即采取的行动和随机事件的结果）输出一个数值，这个数值代表了智能体在该情况下的“满意度”或“回报” 。

使用决策网络的最终目标是选择能带来最大期望效用 (Maximum Expected Utility, MEU) 的行动。这个过程可以通过一个清晰的、分步骤的算法来实现：

1. 第一步：实例化证据并进行概率推理(计算)

首先，我们将所有已知的证据（例如，天气预报是“坏”）在网络中进行实例化 。然后，利用贝叶斯网络的推理算法（如变量消除或采样），计算出效用节点的所有机会父节点的后验概率分布 。

这一步的目的是更新我们对世界状态的信念。例如，当我们得知天气预报是“坏”时，下雨的概率会比不知道预报时更高。我们需要这个更新后的概率来更准确地评估行动的后果。

2. 第二步：为每个可能的行动计算期望效用 接下来，我们遍历行动节点中的每一个可能行动。对于每个行动 a，我们根据第一步计算出的后验概率，计算其期望效用 EU(a|e) 。计算公式如下：

EU(a|e) = ∑_{x1, ..., xn}P(x₁, ..., x_n|e)U(a, x₁, ..., x_n)

其中：

a 是当前考虑的行动。

e 是已知的证据。

x₁, ..., x_n 是效用节点的所有机会父节点的各种状态组合。

P(x₁, ..., x_n|e) 是在给定证据 e 的情况下，这些机会节点处于特定状态组合的后验概率。

U(a, x₁, ..., x_n) 是在采取行动 a 且机会事件为 (x₁, ..., x_n) 时，效用节点给出的具体效用值。

这个公式本质上是在计算一个加权平均值 。我们将每种可能结果的效用值，乘以该结果发生的概率，然后将所有可能结果的加权效用相加，就得到了采取该行动的平均期望回报。

第三步：选择最优行动

最后，我们比较所有行动的期望效用，并选择那个能够产生最高期望效用的行动 。这个最高的期望效用值就是 MEU(e)。

MEU(e) = max_aEU(a|e)

这一步是最终的决策环节。作为一个理性的智能体，我们选择那个在统计上最有可能给我们带来最佳结果的行动。

示例分析

这个例子的目标是，在已知”天气预报是坏消息” (Forecast = bad) 的前提下，计算出能带来最大期望效用 (MEU) 的行动。

第一步：明确已知信息:

在采取行动前，我们已经通过贝叶斯网络推理获得了关键信息, 即后验概率 (Posterior Probabilities)给定预报为”坏”，实际天气的概率分布如下。

• P(Weather = sun|Forecast = bad) = 0.34

• P(Weather = rain|Forecast = bad) = 0.66

效用表 (Utility Table)：不同行动和天气组合下的效用值如下。

• U(leave, sun) = 100 (不带伞，天晴，完美)

• U(leave, rain) = 0 (不带伞，下雨，最糟)

• U(take, sun) = 20 (带伞，天晴，有点累赘)

• U(take, rain) = 70 (带伞，下雨，非常明智)

第二步：计算每个行动的期望效用 (EU)

我们使用期望效用公式 EU(a|e) = ∑_wP(w|e)U(a, w) 来分别评估两个行动。

• 行动：不带伞 (leave) 这个行动的期望效用是两种天气结果（晴天和雨天）的效用与其相应概率的加权和。

EU(leave|bad) = P(sun|bad) × U(leave, sun) + P(rain|bad) × U(leave, rain)

EU(leave|bad) = (0.34 × 100) + (0.66 × 0)

EU(leave|bad) = 34 + 0 = 34

这个计算告诉我们，在预报为坏的情况下，如果不带伞，我们平均可以期望获得 34 个单位的效用。这个值综合了 34% 的概率获得 100 效用和 66% 的概率获得 0 效用的情况。

• 行动：带伞 (take) 同理，我们计算带伞这一行动的期望效用。

EU(take|bad) = P(sun|bad) × U(take, sun) + P(rain|bad) × U(take, rain)

EU(take|bad) = (0.34 × 20) + (0.66 × 70)

EU(take|bad) = 6.8 + 46.2 = 53

这个计算表明，如果带伞，我们平均可以期望获得 53 个单位的效用。它平衡了”天晴时带伞有点麻烦”（效用20）和”下雨时带伞非常有用”（效用70）这两种可能性。

第三步：选择最优行动 最后一步是比较两个行动的期望效用，并选择值最大的那个。

MEU(F = bad) = max(EU(leave|bad), EU(take|bad))

MEU(F = bad) = max(34, 53) = 53

结论：因为行动”带伞 (take)“的期望效用 (53) 大于”不带伞 (leave)” (34)，所以理性的决策是带伞

完美信息价值 (Value of Perfect Information - VPI)

在决策时，我们常常面临一个问题：是否值得花成本去获取更多的信息？

完美信息的价值 (VPI) 就是一个用来量化“新信息能给我们的决策带来多大好处”的工具 。VPI 的核心思想是计算在获取新证据之前和获取新证据之后，最大期望效用的差值 。

VPI 的计算公式定义为：VPI(E^′|e) = MEU(e, E^′) − MEU(e)

其中：

• MEU(e) 是仅基于当前证据 e 所能得到的最大期望效用。
• MEU(e, E^′) 是在决定观察新证据变量 E^′ （但还不知道 E^′ 的具体值）之后，我们期望能得到的最大期望效用。它的计算方式是：
  • MEU(e, E^′) = ∑_e^′P(e^′|e)MEU(e, e^′)
  • 这里 P(e^′|e) 是观察到新证据具体值为 e^′ 的概率，MEU(e, e^′) 是当我们同时拥有旧证据 e 和新证据 e^′ 时的最大期望效用。

示例分析 : 是否要看天气预报？

假设我们一开始没有任何证据（e 为空集 ∅），我们想知道”看天气预报”这个信息的价值是多少。

下面我们先计算无证据时的 MEU：

首先，我们用先验概率 P(W) 计算 MEU(∅)。假设 P(sun) = 0.7, P(rain) = 0.3 。

EU(leave) = 0.7 × 100 + 0.3 × 0 = 70

EU(take) = 0.7 × 20 + 0.3 × 70 = 14 + 21 = 35

MEU(∅) = max (70, 35) = 70 。

下面我们计算获取新信息后的期望 MEU：

我们需要计算如果我们看了天气预报 (F)，期望的 MEU 是多少。我们需要知道 P(F) 的分布，假设 P(F = good) = 0.59，P(F = bad) = 0.41 。

我们已经计算出 MEU(F = bad) = 53 。假设我们同样可以计算出 MEU(F = good) = 95 。

那么，期望的 MEU 是：

MEU(F) = P(F = good)MEU(F = good) + P(F = bad)MEU(F = bad)

MEU(F) = (0.59 × 95) + (0.41 × 53) = 56.05 + 21.73 = 77.78

计算 VPI： VPI(F) = MEU(F) − MEU(∅) = 77.78 − 70 = 7.78 。

这个结果意味着，天气预报这个”完美信息”平均能给我们的决策带来 7.78 个效用单位的提升。如果获取预报的成本（例如时间、金钱）低于这个值，那么我们就应该去获取它 。

VPI 的重要性质

• 非负性：VPI(E^′|e) ≥ 0。获取新信息永远不会让你的期望决策变得更糟，最差也是保持不变 。
• 非可加性：VPI(E_j, E_k|e) ≠ VPI(E_j|e) + VPI(E_k|e)。通常情况下，不同信息之间的价值不是简单相加的，因为它们可能包含重叠或互补的信息 。
• 顺序无关性：VPI(E_j, E_k|e) = VPI(E_j|e) + VPI(E_k|e, E_j)。获取一组信息的总价值与你观察它们的顺序无关 。