计算机视觉中的概率图模型近似推理方法

### 计算机视觉中的概率图模型近似推理方法 在计算机视觉领域，概率图模型是一种强大的工具，用于处理复杂的概率推理问题。然而，对于大型复杂的贝叶斯网络（BN），精确推理的计算成本可能非常高。因此，近似推理方法成为了一种有效的解决方案。本文将介绍几种常见的近似推理方法，包括循环信念传播、蒙特卡罗采样和变分推理。 #### 1. 联合树方法及其复杂度 联合树方法最初用于离散贝叶斯网络，现在已扩展到高斯贝叶斯网络和最大积推理。该算法将变量消除推广到高效地同时执行大量查询。其计算复杂度由三角剖分过程和消息传递决定，对于非树结构模型，这两个过程都是NP难的，因此最坏情况下的计算复杂度仍然是NP难的。在实际应用中，可以通过近似计算消息来解决计算难题，从而得到高效但近似的联合树推理方法。 #### 2. 近似推理方法概述 对于包含许多循环的大型复杂贝叶斯网络，精确推理在计算上是昂贵的，因此可以使用近似推理方法。近似推理方法在进行后验推理时，会对后验概率值$p(X|E)$进行不精确的估计，以效率换取准确性。对于不需要$p(X|E)$精确值的应用，近似方法是适用的。然而，即使提高了效率，仍证明对于容差小于1/2的近似推理，不存在多项式时间算法，这意味着在最坏情况下，精确的近似推理仍然是NP难的。最广泛使用的近似方法包括循环信念传播、蒙特卡罗采样方法和变分方法。 #### 3. 循环信念传播（LBP） 对于多连通的贝叶斯网络，除了将其转换为联合树然后执行信念传播（BP）外，还可以直接应用BP，这就是所谓的循环信念传播（LBP）算法。然而，在这种情况下，不能保证精确的信念传播会收敛，因为消息可能在循环中无限循环。尽管不能保证收敛或正确性，但LBP在实践中取得了很好的经验成功。如果解不是振荡的而是收敛的（尽管可能收敛到错误的解），LBP通常能产生很好的近似。如果不收敛，可以在固定的迭代次数后或当信念没有显著变化时停止LBP。在这两种情况下，LBP通常都能提供足够好的近似。 #### 4. 蒙特卡罗采样 之前讨论的解析推理方法基于数学推导，虽然理论上正确，但通常需要复杂的理论推导和强假设。蒙特卡罗采样推理提供了一种非常不同的选择，它避免了推导封闭形式解析推理方法所需的理论推导。通过蒙特卡罗模拟获得随机样本，并使用样本分布来近似贝叶斯网络的基础分布。对于离散贝叶斯网络，使用样本进行后验推理变成了一个计数问题。该方法的关键是生成足够有代表性的样本以反映基础分布。随着计算能力的提高和更好的采样策略的出现，随机采样推理越来越受欢迎。采样方法的主要挑战是有效地生成足够且有代表性的样本，特别是在高维变量空间中。以下是几种常见的蒙特卡罗采样策略： ##### 4.1 逻辑采样 如果推理不涉及证据，可以采用祖先采样技术，即按照从根节点到其子节点，再到其后代节点，直到叶节点的拓扑顺序对每个变量进行采样。通过遵循贝叶斯网络的拓扑顺序，采样器总是先访问节点的父节点，再访问节点本身。在每个节点，可以采用之前介绍的标准采样方法。祖先采样可以扩展到涉及证据的推理，从而产生逻辑采样方法。该方法从根节点开始进行祖先采样，当到达观察节点时，如果其采样值与观察值不同，则拒绝整个样本并重新开始。然而，这种采样策略效率非常低，特别是当证据的概率较低时。为了提高效率，引入了加权逻辑采样方法。该方法对于有观察值的节点，使用其观察值作为采样值，并为每个样本赋予一个与其似然相关的权重，从而得到加权样本。 加权逻辑采样算法的伪代码如下： ```plaintext ▷E: 证据节点 按照从根节点到叶节点的拓扑顺序对BN变量X1, X2, ..., XN进行排序 将权重w1, w2, ..., wT初始化为1 for t = 1 to T do // t: 样本数量的索引 for n = 1 to N do // n: 节点编号的索引 if Xt[n] ∉ E then 从p(Xt[n]|π(Xt[n]))中采样xt[n] else xt[n] = en wt = wt * p(Xt[n] = en|π(Xt[n])) end if end for 形成样本xt = {xt[1], xt[2], ..., xt[N]}并计算其权重wt end for 返回(x1, w1), (x2, w2), ..., (xT, wT) ``` 根据中心极限定理，随着样本数量的增加，采样估计渐近地接近真实值。可以使用之前介绍的正态方法或精确方法来确定在一定置信区间内获得估计所需的最小样本数量。逻辑采样和加权逻辑采样有局限性，它们仅限于离散贝叶斯网络，并且对于远离根节点的证据进行推理时效率较低。为了克服这些限制，引入了马尔可夫链蒙特卡罗采样。 ##### 4.2 MCMC采样 传统的蒙特卡罗采样方法在低维空间中效果很好，但在高维空间中扩展性不佳。马尔可夫链蒙特卡罗（MCMC）采样可以解决这个限制，是当今最重要的采样方法。其优势在于能够在高维空间中采样，具有理论保证、可并行性和硬件可实现性。其思想是，如果采样遵循马尔可夫链，并且该马尔可夫链是遍历的，那么经过一定的预热期后，链的样本将紧密遵循基础真实分布$p(X)$，而与链的起始位置无关。此外，由于马尔可夫性质，下一个样本由转移概率决定，该转移概率仅取决于当前样本，与所有先前的样本无关。 在各种MCMC采样方法中，吉布斯采样是最受欢迎的方法，因为它简单、高效且有理论保证。吉布斯采样的基本思想是根据前一个样本的值生成链的下一个样本，每个新样本与前一个样本仅在一个变量上不同。因此，吉布斯采样可以扩展到具有大量变量的模型。 对于贝叶斯网络的吉布斯采样，可以构建一个样本的马尔可夫链，其中下一个样本$x_{t + 1}$从根据贝叶斯网络计算的转移概率$p(x_{t + 1}|x_t)$中获得，并且与$x_t$仅在一个变量上不同。具体来说，设$X = \{X_1, X_2,