计算机视觉中的概率图模型：优化、采样与贝叶斯网络

# 计算机视觉中的概率图模型：优化、采样与贝叶斯网络 ## 1. 优化方法 ### 1.1 连续优化 在解决机器学习中的非线性优化问题时，有多种方法可供选择。 - **牛顿法及其变体**：牛顿法通过令导数为零来更新参数，公式为 $\Delta\theta = -(\frac{\partial^2L(\theta)}{\partial\theta^2})^{-1} \frac{\partial L(\theta)}{\partial\theta}$，其中 $\frac{\partial^2L(\theta)}{\partial\theta^2}$ 常被称为海森矩阵。最后，$\theta_t$ 更新为 $\theta_t = \theta_{t - 1} + \Delta\theta$。Broyden–Fletcher–Goldfarb–Shanno (BFGS) 算法是牛顿法的一种变体，它无需显式计算二阶海森矩阵就能进行二阶下降。与一阶方法相比，二阶方法更准确，但要求目标函数二阶可导，且由于二阶导数对噪声的鲁棒性较差。 - **随机梯度法**：一阶和二阶方法都需要对所有训练数据进行求和，当训练数据量很大时，计算成本会很高。随机梯度（SG）方法应运而生，它在每次迭代时随机选择一个训练数据子集来计算梯度，子集大小（称为批量大小）固定，通常在 20 到 100 个样本之间，无论训练数据量多少。理论证明，SG 方法收敛到与全梯度方法相同的点，实证实验也证明了其有效性，它正成为大数据学习的首选方法。 - **次梯度法**：对于不可微的目标函数，可以使用次梯度法。 ### 1.2 离散优化 离散优化是组合优化问题，其解决方案可分为精确方法和近似方法，具体取决于目标函数（如子模性）、模型大小和结构（如链或树结构）。 - **精确方法**：在离散概率图模型的最大后验（MAP）推断中，精确方法包括变量消除、消息传递、图割和动态规划。但对于节点数量多、拓扑结构复杂的模型，由于解空间随变量数量呈指数增长，精确方法变得难以处理。 - **近似方法**：常用的近似方法有坐标上升和循环信念传播。此外，离散优化通常通过目标变量松弛转化为连续优化，例如在计算机视觉中，线性规划松弛常用于解决离散最小化问题。 下面是优化方法的总结表格： | 优化类型 | 方法 | 特点 | | ---- | ---- | ---- | | 连续优化 | 牛顿法及 BFGS | 二阶方法，准确但对目标函数要求高，对噪声鲁棒性差 | | 连续优化 | 随机梯度法 | 每次迭代随机选子集计算梯度，适合大数据 | | 连续优化 | 次梯度法 | 用于不可微目标函数 | | 离散优化 | 精确方法（变量消除等） | 适用于简单模型，复杂模型难以处理 | | 离散优化 | 近似方法（坐标上升等） | 用于复杂模型，通过松弛转化为连续优化 | ## 2. 采样和样本估计 ### 2.1 采样技术 采样（也称为蒙特卡罗模拟）是从基础分布中抽取样本，并使用这些样本作为代理来表示基础分布。以下是一些常见的采样方法： - **单变量采样**：首先需要一个均匀采样器，它可以使用伪随机数生成器从均匀分布 $U \sim U(0,1)$ 中生成样本。对于具有标准分布 $p(X)$ 的随机变量 $X$，设 $F(X)$ 为其累积分布函数（CDF），可以通过先从 $U \sim U(0,1)$ 生成样本 $u$，然后计算 $x = F^{-1}(u)$ 来获得 $X$ 的样本。例如，应用于高斯分布采样时，会产生用于多变量高斯分布采样的 Box–Muller 方法。对于具有 $K$ 个值的分类随机变量 $X$，可以将区间 $(0,1)$ 划分为 $K$ 个区域，根据从 $U(0,1)$ 抽取的样本 $u$ 所在区域确定 $X$ 的值。 - **拒绝采样**：如果无法估计 CDF 的逆，可以使用拒绝采样方法。首先设计一个提议分布 $q(X)$，然后从 $q(X)$ 中采样 $x$，从 $U(0,1)$ 中采样 $u$。如果 $u \geq \frac{p(x)}{q(x)}$，则接受 $x$，否则丢弃。 ### 2.2 样本估计 根据收集到的样本，可以估计随机变量的概率，这些估计的概率称为经验概率，可用于近似总体（真实）概率。 - **离散随机变量**：对于离散随机变量，经验概率通过计算比例 $\frac{n}{N}$ 得到，其中 $N$ 是样本总数，$n$ 是随机变量取特定值的样本数。 - **连续随机变量或更准确估计**：对于连续随机变量或需要更准确的估计，可以使用核密度估计（KDE）方法。 ### 2.3 置信区间 经验概率的一个主要问题是其准确性，即与真实概率的接近程度。采样准确性受样本数量和样本代表性两个因素影响。置信区间常用于衡量估计准确性，设 $p$ 是要估计的真实概率，$\hat{p}$ 是从样本中估计的概率，置信区间定义为 $p \in (\hat{p} - \epsilon, \hat{p} + \epsilon)$，其中 $\epsilon$ 称为区间边界或误差范围。 - **正态方法**：对于二元变量的二项分布，最广泛使用的计算置信区间的方法是正态方法和精确方法。正态方法的区间边界为 $\epsilon = z_{\frac{1 + \alpha}{2}} \sqrt{\frac{1}{N} \hat{p}(1 - \hat{p})}$，其中 $\alpha$ 是置信水平，$z_{\frac{1 + \alpha}{2}}$ 是标准正态分布的 $\frac{1 + \alpha}{2}$ 分位数，$N$ 是样本总数。对于置信区间概率为 0.95 的情况，$z_{\frac{1 + \alpha}{2}} = 1.96$。但正态方法对于小概率或大概率情况效果不佳。 - **精确方法**：精确方法由两个独立的边界组成：下界 $\epsilon_{lower}$ 和上界 $\epsilon_{upper}$，即 $\hat{p} \in (\epsilon_{lower}, \epsilon_{upper})$。上下界难以解析计算，通常用计算机程序数值计算，可通过逆贝塔分布近似。 下面是采样和样本估计的流程 mermaid 图： ```mermaid graph LR A[开始采样] --> B[单变量采样] A --> C[拒绝采样] B --> D[生成均匀样本 u] D --> E[计算 x = F^-1(u)] C --> F[设计提议分布 q(X)] F --> G[采样 x 和 u] G --> H{判断 u >= p(x)/q(x)} H -- 是 --> I[接受 x] H -- 否 --> J[丢弃 x] K[收集样本] --> L[样本估计] L --> M[离散 RV: 计算 n/N] L --> N[连续 RV 或更准确估计: KDE 方法] L --> O[计算置信区间] O --> P[正态方法] O --> Q[精确方法] ``` ## 3. 有向概率图模型 - 贝叶斯网络 ### 3.1 引言 对于一组随机变量 $X_1, X_2, ..., X_N$ 的联合概率 $p(X_1, X_2, ..., X_N)$，可以假设它们遵循参数分布，如连续随机变量的多变量高斯分布或整数随机变量的多项式分布，但这些参数分布可能无法真实捕捉复杂的联合概率分布。也可以假设 $X_n$ 相互独立，此时 $p(X_1, X_2, ..., X_N) = \prod_{n = 1}^{N} p(X_n)$，但这个假设太强。不做任何假设时，可以使用链式法则计算联合概率，但需要指数数量的局部条件概率来完全表征联合概率分布。 ### 3.2 贝叶斯网络表示 贝叶斯网络（BNs）是一种图形模型，通过捕捉变量的内在独立性，能够有效地编码一组随机变量的联合概率分布。 - **定性部分**：一个 BN 可以定义为一个二元组图 $B = (G, \theta)$，其中 $G$ 是有向无环图（DAG），定义了 BN 的定性部分。$G = (V, E)$，$V$ 表示对应于随机变量的节点，$E$ 表示节点之间的有向边，捕捉变量之间的概率依赖关系，这种依赖关系通常是因果关系。 - **定量部分**：$\theta = \{\theta_n\}_{n = 1}^{N}$ 是 BN 的参数，$\theta_n$ 是节点 $n$ 给定其父母的条件概率分布（CPD），即 $\theta_n = p(X_n|\pi(X_n))$，对于根节点，条件概率退化为其先验概率 $p(X_n)$。 给定一个 BN，由于马尔可夫条件（后面会定义）带来的内置条件独立性，$N$ 个节点的联合概率分布可以写为 $p(X_1, X_2, ..., X_N) = \prod_{n = 1}^{N} p(X_n|\pi(X_n))$，这也称为 BN 的链式法则。使用这种紧凑表示，二进制 BN 完全指定联合概率分布所需的参数数量上限为 $2^K \times N$，其中 $K$ 是所有节点的最大父母数量，相比无 BN 时所需的 $2^N - 1$ 个参数，大大节省了参数数量。 为了缓解 CPD 中参数数量随父母数量增加而指数增长的问题，提出了其他替代规范，如将 CPD 指定为某些回归参数的函数、树、通过噪声或原则或父母值的函数，最常见的是线性回归，将 CPD 指定为父母值的加权线性组合。 ### 3.3 贝叶斯网络的性质 #### 3.3.1 马尔可夫条件 BN 的一个重要性质是其显式的内置条件独立性，通过马尔可夫条件（MC）编码。MC 表示节点 $X_n$ 在给定其父母的情况下与其非后代独立，数学表示为 $X_n \perp ND(X_n)|\pi(X_n)$。例如，在一个 BN 示例中，可以根据 MC 得出 $X_4 \perp X_1|X_3$，$X_5 \perp X_2|X_3$，$X_4 \perp X_5|X_3$ 等条件独立性。对于根节点，MC 仍然适用，根节点与其非后代边缘独立。MC 直接导致了 BN 的链式法则，实际上，一个 DAG 满足 MC 时就成为了 BN。 #### 3.3.2 马尔可夫毯和道德图 使用 MC 可以推导出另一个有用的局部条件独立性性质。目标变量 $T$ 的马尔可夫毯 $MB_T$ 是一组节点，在给定这些节点的条件下，所有其他节点与 $T$ 独立。道德图是 DAG 的等效无向图，其中 DAG 的每个节点与其马尔可夫毯相连。 #### 3.3.3 D - 分离 通过 MC 和马尔可夫毯可以确定变量之间的局部条件独立性，MC 可以扩展到确定彼此距离较远的变量之间的独立性关系，这通过 D - 分离原则实现。在正式介绍该概念之前，需要定义一些符号，如无向路径、有向路径和碰撞节点等。 下面是贝叶斯网络相关概念的总结表格： | 概念 | 定义 | 作用 | | ---- | ---- | ---- | | 贝叶斯网络 | 二元组图 $B = (G, \theta)$，$G$ 是 DAG，$\theta$ 是参数 | 有效编码联合概率分布 | | 马尔可夫条件 | $X_n \perp ND(X_n)|\pi(X_n)$ | 导致 BN 链式法则，体现条件独立性 | | 马尔可夫毯 | 目标变量 $T$ 的一组节点，使其他节点与 $T$ 条件独立 | 确定局部条件独立性 | | 道德图 | DAG 的等效无向图，节点与马尔可夫毯相连 | 辅助分析条件独立性 | | D - 分离 | 通过扩展 MC 确定远距离变量独立性 | 分析变量间独立性关系 | ### 3.3.3 D - 分离（续） 在介绍 D - 分离原则之前，我们先明确一些关键概念： - **无向路径**：在图 $G$ 中，两个节点 $X_m$ 和 $X_n$ 之间的无向路径是它们之间的节点序列，其中任意连续的节点通过有向边相连，且序列中没有节点重复出现。 - **有向路径**：有向无环图（DAG）的有向路径是节点序列 $(X_1,X_2,\cdots,X_{N - 1})$，对于 $1\leq n\lt N$，$X_n$ 是 $X_{n + 1}$ 的父节点。 - **碰撞节点**：在一条路径中，如果节点 $X_k$ 有来自 $X_m$ 和 $X_n$ 的两条入边，则 $X_k$ 被定义为碰撞节点。 D - 分离原则指出，如果在图 $G$ 中，节点集合 $Z$ 阻塞了节点 $X$ 和 $Y$ 之间的所有路径，那么在给定 $Z$ 的条件下，$X$ 和 $Y$ 是条件独立的。具体来说，一条路径被阻塞的情况有： - 路径上存在一个非碰撞节点，且该节点在 $Z$ 中。 - 路径上存在一个碰撞节点，且该碰撞节点及其所有后代都不在 $Z$ 中。 例如，在一个贝叶斯网络中，若要判断节点 $A$ 和 $B$ 在给定节点集合 $C$ 时是否独立，就需要检查 $A$ 和 $B$ 之间的所有路径是否被 $C$ 阻塞。通过 D - 分离，我们可以在贝叶斯网络中系统地分析变量之间的独立性关系，这对于概率推理和模型简化非常重要。 下面是一个简单的表格，总结了路径阻塞的情况： | 节点类型 | 条件 | 路径状态 | | ---- | ---- | ---- | | 非碰撞节点 | 在 $Z$ 中 | 阻塞 | | 碰撞节点 | 及其所有后代不在 $Z$ 中 | 阻塞 | ### 3.4 贝叶斯网络的推理 贝叶斯网络的一个重要应用是进行概率推理，即根据已知的证据变量值，计算其他变量的后验概率。常见的推理类型包括： - **因果推理**：从原因变量到结果变量的推理，根据父节点的状态推断子节点的状态。例如，已知某些疾病的致病因素（父节点），推断患病的概率（子节点）。 - **诊断推理**：从结果变量到原因变量的推理，根据子节点的状态推断父节点的状态。比如，根据患者的症状（子节点）推断可能的病因（父节点）。 - **交互因果推理**：在多个原因变量之间进行推理，考虑它们之间的相互作用。例如，当有多个可能导致某种结果的原因时，分析这些原因之间的关系。 推理的方法可以分为精确推理和近似推理： - **精确推理**：对于结构简单的贝叶斯网络，可以使用精确推理方法，如变量消除法和团树传播法。变量消除法通过依次消除非查询变量和非证据变量，逐步简化联合概率分布的计算。团树传播法则是通过构建团树结构，在团之间传递消息来计算后验概率。 - **近似推理**：对于大规模或复杂结构的贝叶斯网络，精确推理的计算复杂度可能过高，此时可以使用近似推理方法，如重要性采样、马尔可夫链蒙特卡罗（MCMC）方法等。重要性采样通过选择合适的提议分布，对样本进行加权来近似后验概率。MCMC 方法则是通过构建马尔可夫链，使其平稳分布为目标后验分布，从而生成样本进行概率估计。 下面是贝叶斯网络推理的流程 mermaid 图： ```mermaid graph LR A[确定推理类型] --> B[因果推理] A --> C[诊断推理] A --> D[交互因果推理] B --> E{网络结构简单?} C --> E D --> E E -- 是 --> F[精确推理] E -- 否 --> G[近似推理] F --> H[变量消除法] F --> I[团树传播法] G --> J[重要性采样] G --> K[MCMC 方法] ``` ## 4. 贝叶斯网络的学习 贝叶斯网络的学习主要包括结构学习和参数学习两个方面。 ### 4.1 结构学习 结构学习的目标是从数据中推断出贝叶斯网络的图结构。常见的方法有： - **基于评分的方法**：定义一个评分函数来评估不同图结构的优劣，然后搜索最优的图结构。评分函数通常考虑了模型的拟合度和复杂度，如贝叶斯信息准则（BIC）和最小描述长度（MDL）准则。搜索算法可以是贪心搜索、模拟退火、遗传算法等。例如，贪心搜索从一个初始图结构开始，通过不断添加、删除或反转边来改进评分，直到无法进一步提高为止。 - **基于约束的方法**：通过检验变量之间的条件独立性来确定图结构。首先，使用统计检验（如卡方检验）来判断变量之间是否独立或条件独立，然后根据这些独立性关系构建图结构。例如，如果发现变量 $X$ 和 $Y$ 在给定变量 $Z$ 的条件下独立，那么在图中 $X$ 和 $Y$ 之间不应该有直接的边。 - **混合方法**：结合基于评分和基于约束的方法，充分利用两者的优点。例如，先使用基于约束的方法得到一个初始的图结构，然后使用基于评分的方法进行局部优化。 ### 4.2 参数学习 在确定了贝叶斯网络的结构后，需要学习网络的参数，即每个节点的条件概率分布（CPD）。常见的参数学习方法有： - **最大似然估计（MLE）**：在给定数据和图结构的情况下，找到使数据出现概率最大的参数值。对于离散变量，MLE 通过计算每个条件下的频率来估计 CPD。例如，对于一个节点 $X$ 及其父节点集合 $\pi(X)$，计算在每个 $\pi(X)$ 的取值组合下 $X$ 取不同值的频率。 - **贝叶斯估计**：考虑了参数的先验分布，通过贝叶斯定理将先验信息和数据结合起来估计参数。贝叶斯估计可以避免 MLE 在数据量较小时出现过拟合的问题。常见的先验分布有狄利克雷分布，它可以方便地与多项分布进行共轭计算。 下面是贝叶斯网络学习的总结表格： | 学习类型 | 方法 | 特点 | | ---- | ---- | ---- | | 结构学习 | 基于评分的方法 | 定义评分函数，搜索最优结构 | | 结构学习 | 基于约束的方法 | 检验条件独立性构建结构 | | 结构学习 | 混合方法 | 结合评分和约束方法 | | 参数学习 | 最大似然估计 | 使数据出现概率最大 | | 参数学习 | 贝叶斯估计 | 考虑参数先验分布 | ## 5. 总结 本文全面介绍了计算机视觉中概率图模型的相关知识，包括优化方法、采样和样本估计、贝叶斯网络等内容。 - **优化方法**：连续优化中的牛顿法及其变体、随机梯度法和次梯度法，以及离散优化中的精确方法和近似方法，为解决不同类型的优化问题提供了多种选择。 - **采样和样本估计**：单变量采样、拒绝采样等采样技术，以及基于样本的概率估计和置信区间计算，是进行概率学习和推理的基础。 - **贝叶斯网络**：作为有向概率图模型，贝叶斯网络通过马尔可夫条件、马尔可夫毯、D - 分离等性质，有效地编码了变量之间的联合概率分布，并支持多种类型的推理和学习方法。 掌握这些知识对于理解和应用概率图模型在计算机视觉中的各种任务（如图像分类、目标检测、图像分割等）具有重要意义。未来，随着数据量的不断增加和问题复杂度的提高，概率图模型的优化、采样和学习方法将不断发展和完善，以更好地适应实际应用的需求。