总变差距离估计与概率推理一样简单|多项式|定理|概率推理|算法|贝叶斯|高维

Total Variation Distance Estimation Is as Easy as Probabilistic Inference

总变差距离估计与概率推理一样简单

https://arxiv.org/pdf/2309.09134

摘要
本文在总变差（Total Variation，TV）距离估计与概率推理之间建立了新的联系。特别是，我们提出了一种从TV距离相对近似到定向图形模型上概率推理的高效、结构保持的简化方法。这种简化方法导致了一个全多项式随机近似方案（Fully Polynomial Randomized Approximation Scheme，FPRAS），用于估计任何具有高效概率推理算法的贝叶斯网络类别上分布之间的TV距离。特别是，它导致了一个FPRAS，用于估计由有界树宽贝叶斯网定义的分布之间的TV距离。在这项工作之前，此类近似方案仅存在于估计乘积分布之间的TV距离中。我们的方法采用了一种新的高维分布部分耦合的概念，这可能具有独立的研究价值。

1 引言
机器学习和数据科学严重依赖于概率分布，这些分布被广泛用于捕获大量变量之间的依赖关系。这种高维分布在各种领域自然出现，包括神经科学[ROL02, CTY06]、生物信息学[BB01]、文本和图像处理[Mur22]以及因果推理[Pea09]。大量研究致力于开发能够简洁表示高维概率分布的模型。其中一种普遍的方法是图形模型。在图形模型中，一个图描述了变量之间的条件依赖关系，并且概率分布根据图中相邻关系进行分解[KF09]。当底层图是定向图时，该模型称为贝叶斯网络或贝叶斯网。

分布上的两个基本计算任务是距离计算和概率推理。在这项工作中，我们在这两个看似不同的计算任务之间建立了新的联系。利用这种联系，我们设计了新的相对误差近似算法，用于估计具有有界树宽的贝叶斯网分布之间的统计距离。

距离计算。距离计算问题如下：给定两个概率分布P和Q的描述，计算距离度量ρ下的ρ(P, Q)。其中一个非常重要的距离度量是总变差（Total Variation，TV）距离（也称为统计距离或统计差异）。设P和Q是有限域D上的分布。P和Q之间的总变差距离，记为dTV(P, Q)，定义为：

总变差距离满足许多基本性质，使其成为量化概率分布之间差异的一种通用且基础的度量方法。首先，它有一个明确的概率解释：两个分布之间的总变差距离是这两个分布分配给单个事件的概率之间的最大差距。其次，它满足许多数学上期望的性质：它在[0,1]范围内有界，是一个度量标准，并且对于双射是不变的。总变差距离还衡量了在P和Q之间所有耦合(X, Y)中，X=Y的最小概率。由于这些原因，总变差距离是在包括概率论和统计学、机器学习、信息论、密码学、数据隐私和伪随机性在内的广泛领域中采用的核心距离度量方法。

概率推理。在概率推理这一术语下，有几个相关的计算任务。我们使用以下定义：给定随机变量X1,...,Xn（及其表示）和集合S1,...,Sn（及其表示），使得对于所有i，集合Si是Xi值域的子集，计算概率Pr[X1∈S1,...,Xn∈Sn]。

图形模型中的概率推理是一项基础计算任务，具有广泛的应用领域，涵盖了统计学、机器学习和人工智能等学科（例如，[WJ+08]）。针对这个问题，已经提出了各种算法，既包括精确方法，如消息传递[Pea88]、变量消除[Dec99]和连接树传播[LS88]，也包括近似技术，如循环置信传播、基于变分推理的方法[WJ+08]和基于粒子的算法（参考[KF09]的第13章及其中的参考文献）。在多项研究中也得出了计算复杂性的结果[Coo90, LMP01, Rot96, KBvdG10]。

1.1 我们的贡献

我们的主要贡献是将总变差（TV）距离估计问题归结为贝叶斯网络上的概率推理问题，同时保持结构不变。具体来说，我们展示了一种有效的概率归结方法，使得对于在有向无环图（DAG）G上定义的两个贝叶斯网络P和Q，该归结方法可以向在同一DAG G上定义的贝叶斯网络L提出概率推理查询，并返回dTV(P, Q)的相对近似值。

作为推论，我们获得了一个针对在任何有向无环图（DAG）类别上贝叶斯网络之间的总变差（TV）距离进行相对近似的完全多项式时间随机近似方案（FPRAS）。对于树宽为O(log n)的DAG上的贝叶斯网络，可以使用著名的变量消除算法进行高效的概率推理。这导致了一个新的FPRAS，用于对数树宽的DAG上贝叶斯网络的总变差距离估计。

在我们的工作之前，此类近似方案仅适用于无边缘图上的乘积分布，即无环图（DAG）上的贝叶斯网络[FGJW23]。特别是，设计用于估计树（树宽为1的图）上贝叶斯网络之间总变差（TV）距离的FPRAS（完全多项式时间随机近似方案）一直是一个悬而未决的问题。我们的结果解决了这个问题。已知对于一般DAG上的贝叶斯网络，我们不可能希望有用于相对近似TV距离的FPRAS。特别是，[BGM+23]表明，当P和Q是入度为2的DAG上的任意贝叶斯网络时，判断dTV(P, Q)是否为零是NP难的。尽管存在这种不可能性结果，但推论3表明，对于一大类贝叶斯网络（即树宽为O(log n)的贝叶斯网络）来说，确实可以获得FPRAS。

我们的下一组结果关注其中一个分布为均匀分布的情况。我们首先证明，精确计算贝叶斯网络分布与均匀分布之间的TV距离是#P完全的。为了补充这一结果，我们展示了存在一个FPRAS，可以估计均匀分布与任何贝叶斯网络分布之间的TV距离。

1.2 相关工作

Koller和Friedman[KF09]对概率图模型进行了全面概述。他们讨论了图形模型（包括贝叶斯网络和马尔可夫网络）背后的一般原理和哲学。

距离计算。最近，Bhattacharyya、Gayen、Meel、Myrisiotis、Pavan和Vinodchandran[BGM+23]开始了图形模型上TV距离计算复杂性方面的研究。在该工作中，他们证明了精确计算乘积分布之间的TV距离是#P完全的，判断两个入度为2的贝叶斯网络之间的TV距离是否等于0是NP难的，并且为任意乘积分布与均匀分布之间的TV距离近似提供了一个FPTAS（全多项式时间近似方案）。在后续工作中，Feng、Guo、Jerrum和Wang[FGJW23]为两个任意乘积分布之间的TV距离近似提供了一个FPRAS（完全多项式时间随机近似方案）。

之前也从更复杂理论性和密码学性的角度研究了TV距离估计。Sahai和Vadhan[SV03]在一项开创性工作中证明，对于可由布尔电路采样的两个分布，加性地近似其TV距离对于SZK（统计零知识）来说是困难的。Goldreich、Sahai和Vadhan[GSV99]表明，判断一个可由布尔电路采样的分布是接近还是远离均匀分布的问题对于复杂性类NISZK（非交互式统计零知识）来说是完全的。

TV距离的加性近似要容易得多。Canonne和Rubinfeld[CR14]展示了如何加性地估计那些可以高效采样且其概率质量函数可以高效评估的分布之间的TV距离。显然，贝叶斯网络满足这两个条件（其中“高效”通常意味着参数数量的多项式）。Bhattacharyya、Gayen、Meel和Vinodchandran[BGMV20]扩展了这一想法，开发了多项式时间算法，使用从每个网络中多项式数量的样本，加性地近似两个有界入度贝叶斯网络之间的TV距离。

概率推理。有大量工作致力于精确概率推理。如前所述，为概率推理任务开发的一些算法范式是消息传递[Pea88]、变量消除[Dec99]和连接树传播[LS88]。最近，Klinkenberg、Blumenthal、Chen和Katoen[KBCK23]提出了一种精确贝叶斯推理方法，用于推断由可能具有无界循环行为的概率程序编码的后验分布。同样，Klinkenberg、Winkler、Chen和Katoen[KWCK23]探索了生成函数的理论，并研究了其在概率程序精确定量推理中的应用。

随着大数据的出现和模型复杂性的增加，传统的精确推理方法可能在计算上变得不可行。近似推理技术，如变分推理和像马尔可夫链蒙特卡罗这样的采样方法，提供了高效且可扩展的替代方案来解决这些挑战。Minka[Min01]介绍了用于近似贝叶斯推理的期望传播算法。该方法统一了两种先前技术：作为卡尔曼滤波器扩展的假定密度滤波和循环信念传播。Murphy、Weiss和Jordan[MWJ13]研究了循环信念传播的有效性。他们展示了算法性能的实证结果，并讨论了其局限性和权衡。Ranganath、Gerrish和Blei[RGB14]介绍了黑盒变分推理，这是一种灵活且可扩展的近似贝叶斯推理方法。他们的论文提出了一个近似后验分布的一般框架，并讨论了其在潜在变量模型中的应用。Blei、Kucukelbir和McAuliffe[BKM17]对变分推理（一类近似贝叶斯推理方法）进行了全面回顾。他们涵盖了变分推理的原理，介绍了不同的算法方法，并讨论了其在机器学习中的应用。

1.3 文章结构

本文的其余部分组织如下。我们在第2节中提供结果的技术概述，在第3节中提供一些背景资料。我们按如下方式证明主要结果：在第4节中证明定理1；在第4.3节中证明推论3；在第5.1节中证明定理4；在第5.2节中证明定理5。我们在第6节中得出结论。

2 技术概述

在本节中，我们就结果的技术方面提供一些直观理解。

2.1定理1的证明

我们的方法是仔细定义一个估计函数f和一个分布π，使得Eπ[f] = dTV(P, Q)/Z，其中Z是一个可以有效计算出的归一化常数。算法通过估计Eπ[f]，将其乘以Z，并返回该值。我们使用概率推理查询来计算Z并从分布π中进行采样。

这种方法面临几个挑战，包括设置估计函数f和分布π，使得：(i) Eπ[f]足够大，以便经验估计成为一个良好的相对近似；(ii) 可以使用概率推理查询有效地从π中进行采样并计算Z。

我们的出发点是总变差距离（Total Variation Distance，简称TV距离）和耦合之间的一个众所周知的关系。

乍一看，也许令人惊讶的是，最优耦合通常并不具有与基础分布相同的结构。事实上，即使是对于n元变量乘积分布P和Q，最优耦合也不能分解。对于乘积分布的一个自然的最优耦合候选是局部耦合，即在(X, Y) = (X1, . . . , Xn, Y1, . . . , Yn)上的联合分布L，其中每个(Xi, Yi)都是从P和Q的第i个边缘分布的最优耦合中独立采样的。然而，局部耦合通常并不是最优的。

在最近的一项工作中，Feng、Guo、Jerrum和Wang [FGJW23]证明了，当P和Q是乘积分布时，尽管PrL[X = Y]（L是P和Q的局部耦合）的近似值并不直接等于PrO[X = Y]（O是P和Q的最优耦合）的近似值，但它总是能导致对PrO[X = Y]的一个良好近似。更确切地说，如果用α表示PrO[X = Y]/PrL[X = Y]的比率，[FGJW23]证明了对于任何两个n维乘积分布P和Q：

(i) α至少为Ω(1/n)；
(ii) 存在一个α的无偏估计量ˆα ∈ [0, 1]，它可以有效地计算出来。

切诺夫界（Chernoff bound）表明，通过对ˆα（α的无偏估计量）的O(n)个独立副本取平均，可以得到α的相对近似值。由于（其中dTV表示总变差距离）很容易计算，因此对于乘积分布，我们可以得到一个对于dTV(P, Q) = α · PrL[X = Y]的全概率相对近似方案（FPRAS）。

将这种方法推广到一般有向无环图（DAG）上的贝叶斯网络面临几个挑战。即使当我们考虑非常简单的贝叶斯网络——有向路径图时，也会出现主要问题。设P和Q是在长度为n的有向路径上的贝叶斯网络。也就是说，对于P和Q，给定第(i-1)个边缘分布，第i个和第(i-2)个边缘分布是条件独立的。就因子分解而言，对于所有w ∈ [ℓ]^n（这里[ℓ]表示某个有限集合，n表示维度或长度）：

请注意，上述条件并未对Y的分布设定任何限制。当P和Q是通过有向无环图（DAG）描述的任意贝叶斯网络分布时，这些条件可以很容易地从路径推广到一般的有向无环图。

2.2 其余结果的证明

在此，我们概述了我们其余结果的主要证明思路。

推论3的证明。推论3的证明是定理1的一个应用。为了利用定理1，我们建立了在固定字母表和对数树宽的贝叶斯网络中，概率推理（即计算Pr[X1 ∈ S1, . . . , Xn ∈ Sn]）可以有效地实现（引理26）。已知具有对数树宽的图的树分解可以在多项式时间内计算出来[RS84]。[ZP94]中的变量消除算法表明，如果贝叶斯网络的树宽是对数的，那么在给定树分解的情况下，推理可以在多项式时间内完成。

3 预备知识

我们用[n]来表示集合{1, . . . , n}，并用log来表示以2为底的对数。在整篇论文中，我们假设所有概率都以a/b的形式表示为有理数。我们用U来表示均匀分布。

以下集中不等式在我们的证明中将非常有用。

3.1 贝叶斯网络

3.2总变化距离

下面的距离概念是这项工作的核心。

3.3 概率推理

概率推理和概率推理预言机（针对贝叶斯网络）的概念在本工作中至关重要。

对我们来说，概率推理是指以下计算任务：给定随机变量X1, . . . , Xn（及其表示）和集合S1, . . . , Sn（及其表示），使得对于所有i，集合Si是Xi取值范围的一个子集，计算概率Pr[X1 ∈ S1, . . . , Xn ∈ Sn]。3

现在，让我们定义概率推理（预言机）查询。

3.4树宽和树分解

我们需要树宽的定义。

4 从总变差距离估计到概率推理的保结构归约

在本节中，我们将证明定理1和推论3。在下文中，设T(G, ℓ)表示对于在具有字母表大小ℓ的有向无环图G上的贝叶斯网络，某个概率推理预言机实现的运行时间。

本节的其余部分致力于证明定理1，并按以下方式组织。我们首先介绍描述算法所需的成分。在4.1节中，我们展示如何使用概率推断查询来实现算法。最后，在4.2节中我们建立其正确性。

设P和Q是两个在有n个节点和字母表[ℓ]的DAG G上定义的贝叶斯网络分布。不失一般性，假设节点按照序列1, 2, ..., n进行拓扑排序。

4.1 使用概率推理查询实现算法

本小节致力于证明可以通过概率推理查询来从分布π中采样并计算归一化常数Z。

回顾一下，L是联合分布(X, Y)。我们首先提出以下关键观察结果：在L中，边缘分布X是根据分布P分布的。

4.2 算法分析

接下来，我们建立函数f和分布π的一些有用性质。

4.3应用:用于估计有限树宽的贝叶斯网之间的TV距离的FPRAS

在这一小节中，我们证明推论3。

5 贝叶斯网络与均匀分布之间的总变差距离
5.1 #P-完全性

本小节的主要结果是定理4。回顾一下，如果一个从{0, 1}*到非负整数的函数f存在一个多项式时间非确定性图灵机M，使得对于任何x，f(x)等于M(x)的接受路径的数量，那么f就属于#P类。

现在我们来证明定理4。

5.2完全多项式时间内的估计

我们证明定理5。

6 结论

我们建立了概率推理与总变差（Total Variation，TV）距离计算之间的一般联系。特别是，我们证明了总变差距离估计可以归约为概率推理。这使得我们能够证明存在一种新型的全概率相对近似方案（Fully Polynomial Randomized Approximation Scheme，FPRAS），用于估计树宽较小的贝叶斯网络之间的总变差距离。

此外，我们在理解任意贝叶斯网络与均匀分布之间总变差距离计算的复杂性方面取得了一些重要进展：我们证明了精确计算是#P-难的，但对于同一任务存在一个FPRAS。

我们概述了以下未解决的问题：我们能否为无向图形模型之间的总变差距离估计证明类似的结果？另一个有趣的问题是研究其他距离概念，如Wasserstein度量。

https://arxiv.org/pdf/2309.09134