【博士论文】吉布斯分布的局部、动态与快速采样算法

吉布斯分布的局部、动态与快速采样算法

吉布斯分布是一类重要的概率模型，它在概率论、统计物理和计算机科学 等领域有着非常广泛的应用。采样是关于吉布斯分布的核心计算任务，它要求 算法按照给定的分布生成一个随机样本。吉布斯分布的采样问题是理论计算机 科学的重要课题之一，人们致力于探索有严格理论保障的算法以及采样问题的 计算复杂性。经过数〸年的深入研究，拒绝采样、马尔可夫链蒙特卡洛方法等 采样技术逐渐被发展起来，很多重要的采样问题被成功解决。

虽然先前的研究回答了关于采样的若干基本问题，但是目前已知的采样算 法较少，分析工具也有待加强，一些重要的问题没有得到很好的解决。例如对 于均匀采样逻辑公式满足解的问题，因为很多经典算法无法适用，所以长期缺 乏高效算法；对于均匀采样合法图染色问题，因为缺乏有力的分析工具，所以 目前已知的算法收敛条件和猜想依然有很大差距。这些公开问题代表了当前技 术上的本质障碍，解决这些问题需要在原理层面上做出创新。另一方面，在大 数据时代，很多新的采样问题涌现出来。一些经典的采样技术只能给出高度串 行、适用于静态数据的采样算法。而在如今的应用中，并行的、动态的采样算 法越来越受到关注。传统的采样理论难以胜任新的问题，在大数据背景下，人 们需要建立新的采样理论体系。

本文研究吉布斯分布的采样算法。对于大数据背景下的新问题，本文从分 布式采样和动态采样这两个具体问题入手，给出有理论保障的算法并研究新模 型下采样问题的复杂性。对于一些经典的公开问题，本文提出新的算法设计和 分析技术来突破先前的障碍，从而得到更快的采样算法。

第一个课题是分布式采样问题。我们在分布式计算的 LOCAL 模型上研究 吉布斯分布的采样。在这个模型中，每个节点通过收集局部信息输出一个随机 变量，所有节点输出变量的联合分布为目标吉布斯分布。我们给出全新的分布式采样算法，证明分布式采样问题的下界，并且在分布式计算模型上复现图灵 机模型上的若干经典结论，例如采样问题和计数问题的计算等价性，采样问题 的计算相变现象。这些结论揭示了分布式采样和传统串行采样之间的联系，对 理解分布式采样的原理有重要意义。

第二个课题是动态采样问题。假设我们有一个吉布斯分布以及一个服从此 分布的随机样本。给定一个更新操作，它把当前吉布斯分布更新成一个新的吉 布斯分布。算法需要以相对较小的增量代价，把原随机样本更新成一个服从新 分布的随机样本。我们给出了两种设计动态采样算法的技术。第一个是条件吉 布斯技术，它不仅能解决动态采样问题，也能用于设计精确采样算法，还和吉 布斯分布的空间混合性质有密切的联系。第二个技术是动态马尔可夫链技术， 它能把一些原本静态的马尔可夫链蒙特卡洛方法动态化，从而一些静态采样的 成果可以直接用应用到动态采样上来。

最后一个课题是具体问题的快速采样算法。一些吉布斯分布在我们的研究 之前只有运行时间为 n f (θ ) 的算法，其中 n 是吉布斯分布变量数；θ 是吉布斯分 布的某个参数，例如变量的最大度数；f (θ) 是 θ 的一个多项式函数或指数函 数。这类采样算法只对 θ = O(1) 的问题有多项式运行时间，且多项式的指数非 常巨大。我们的工作将解决问题的复杂度优化到 poly(nθ) 的时间，有些问题的 时间复杂度可以和 n 呈接近线性的关系。在技术上，我们对具体问题提出了新 的算法设计技术和算法分析技术，从原理上突破了先前的技术障碍。