诱导因子化概率分布的可比性

# 1 引言
来源：https://arxiv.org/html/2607.20502
诱导分解概率分布的可比性

Jan SpellerMalte LuttermannMarcel GehrkeTanya Braun

明斯特大学数据科学组德国汉堡大学人本人工智能研究所德国汉堡大学人本人工智能研究所明斯特大学数据科学组德国

###### 摘要

为了对定义在非相同变量集上的两个概率图模型进行原则性比较，必须将它们提升到一个共同的可测空间。为此，我们为任意两个给定的模型提出了一种扩展方案，并建立了形式化基础：不匹配的组件使用条件均匀（拉普拉斯）扩展完成，使得得到的联合分布在投影下与原分布仅相差乘法常数且一致。这保留了概率语义，同时使得应用定义良好的分布差异度量成为可能。我们证明了在投影下诱导联合分布的不变性，并使用这些扩展通过确定性算法将两个因子图最小结构扩展至最小公共可测空间以及公共图结构。此外，我们讨论了结构和测度论性质，并确定了比较方法论中有前景的标准。

比较概率分布假设分布定义在相同的支撑集上（例如，全变差距离 (Bretagnolle and Huber,1978 (https://arxiv.org/html/2607.20502#bib.bib404))），具有兼容的度量空间（例如，Wasserstein 度量 (Vaserstein,1969 (https://arxiv.org/html/2607.20502#bib.bib402))），或者理想情况下是相同的可测空间 (MS)（例如，Hellinger 距离 (Hellinger,1909 (https://arxiv.org/html/2607.20502#bib.bib403))）。然而，在许多情况下，我们面临需要比较定义在非相同MS上的分布的挑战。变化可能来自随时间发生的概念漂移 (Hadouxet al.,2014 (https://arxiv.org/html/2607.20502#bib.bib113); Finkeet al.,2021 (https://arxiv.org/html/2607.20502#bib.bib343))、人本感知环境中的更新 (Chakrabortiet al.,2017 (https://arxiv.org/html/2607.20502#bib.bib59); Kulkarniet al.,2019 (https://arxiv.org/html/2607.20502#bib.bib157))，或者仅仅是从两个相关来源（例如，两家包含相似但不完全相同信息的公司的数据库）或使用不同学习算法学习两个模型。由于此类模型只有在提升到共同MS后才能比较，我们研究能保留语义的原则性分布扩展。

具体而言，我们专注于**因子图** (Freyet al.,1997 (https://arxiv.org/html/2607.20502#bib.bib394))，它表示分解概率分布，作为一种广义问题设置，以便能够同时进行全联合分布的全局比较 (Kullback and Leibler,1951 (https://arxiv.org/html/2607.20502#bib.bib401)) 和因子层面的局部比较 (Chan and Darwiche,2005 (https://arxiv.org/html/2607.20502#bib.bib395))。一个全联合分布总可以被视为一个具有单因子的FG。分解分布利用**随机变量**之间的（条件）独立性，用更少的条目存储相同的全联合分布，将复杂度从全联合分布中的O(r^n)（其中r是随机变量可取的最大值数目，n是随机变量的数量）转移到O(m r^s)（其中m是因子数量，s是单个因子中随机变量的最大数量）。这种分解分布通常伴随有图形表示，使其属于**概率图模型**的范畴。PGMs有几种类型，如上述的FGs、**贝叶斯网络** (Pearl,1988 (https://arxiv.org/html/2607.20502#bib.bib216)) 以及**马尔可夫网络** (Moussouris,1974 (https://arxiv.org/html/2607.20502#bib.bib191))。根据 Hammersley-Clifford 定理 (Hammersley and Clifford,1971 (https://arxiv.org/html/2607.20502#bib.bib112))，每个由FG编码的潜在概率分布都可以由BN和MN表示。因此，本文提出的结果不仅限于FGs，也可用于比较由BNs和MNs编码的分解分布。

为了以有原则的方式扩展FGs，我们考虑其结构，添加新的因子、新的随机变量，或将现有的随机变量添加到现有因子。为了在扩展FG时保留其在投影下的语义，我们采用均匀（拉普拉斯）扩展来完成不同模型因子之间不匹配的组件。拉普拉斯扩展是概率论领域中一般扩展的一个特例，用于扩展概率空间 (Bierlein,1962 (https://arxiv.org/html/2607.20502#bib.bib407); Ascherl and Lehn,1977 (https://arxiv.org/html/2607.20502#bib.bib406); Bogachev,2007 (https://arxiv.org/html/2607.20502#bib.bib408))，这一点相对研究不足。我们证明了拉普拉斯扩展允许一个满射、保测度的投影到原始FG上。基于此结果，我们引入了**最小结构拉普拉斯扩展**来对齐具有非相同随机变量集的FGs，从而能够通过现有的距离度量进行比较。据我们所知，这是第一个用于比较具有非相同随机变量集的PGM的原则性方法。

本文的其余部分结构如下：在符号说明之后，我们介绍FG扩展，随后是一个算法，该算法保证将两个任意FGs扩展到相同的MS上，同时强制实现相同的图形结构，从而能够直接比较。之后是讨论和结论。较长的证明以及关于最小性的讨论见附录。

## 2 符号说明

给定一组随机变量R，令XR:=×_{X∈R} range(X)表示其取值范围(值域)的笛卡尔积，其中range(X)是X可以取值的集合。一个FG是一个PGM，它通过将分布分解为因子的乘积，紧凑地编码一个随机变量集上的概率分布 (Freyet al.,1997 (https://arxiv.org/html/2607.20502#bib.bib394); Kschischanget al.,2001 (https://arxiv.org/html/2607.20502#bib.bib156))。

###### 定义 1 (因子图)。

一个**因子图** M = (V, E) 是一个无向二分图，由一组节点 V = R ∪ Φ 组成，其中 R = {X_1, ..., X_n} 是一组随机变量，Φ = {φ_1, ..., φ_m} 是一组因子（函数），以及一组边 E ⊆ R × Φ。如果随机变量 X_i ∈ R 出现在因子 φ_j ∈ Φ 的参数列表（也称为*作用域*）R_(j) := scope(φ_j) 中，则在 E 中存在一条连接 X_i 和 φ_j 的边，其中 R_(j) ⊆ R。因子 φ_j 定义一个函数 φ_j: X_{R_(j)} ↦ ℝ_{>0}，将其参数的值域映射到一个正实数，称为势。我们定义对于赋值 r（其中 r 缩写为 R = r）的联合势为 ψ(r) = ∏_{φ_j ∈ Φ} φ_j(r_j)，其中 r_j 是赋值 r 到 φ_j 的作用域 R_(j) 的投影。给定MS (X_R, P(X_R))，其中 X_R 是所有可能赋值的集合，P(X_R) 是其幂集，作为 σ-代数，概率测度 P_M 是归一化的联合势：

P_M(r) = (1/Z) ∏_{φ_j ∈ Φ} φ_j(r_j) = (1/Z) ψ(r)，

其中 Z = ∑_{r ∈ X_R} ∏_{φ_j ∈ Φ} φ_j(r_j) 是归一化常数（也称为配分函数）。

###### 示例 1 (因子图)。

考虑图1 (https://arxiv.org/html/2607.20502#S2.F1) 中描绘的FG M_ex = (R ∪ Φ, E)，其中 R = {A, B, C}, Φ = {φ_1, φ_2}，且 E = {(A, φ_1), (B, φ_1), (B, φ_2), (C, φ_2)}。作用域由 R_(1) = {A, B} 和 R_(2) = {C, B} 给出。φ_1 和 φ_2 的函数定义见图1中的表格，即 φ_1(A=true, B=true) = φ_1, φ_1(A=true, B=false) = φ_2，依此类推，其中 φ_i ∈ ℝ_{>0}, i ∈ {1, ..., 8}，是正实数。例如，对于赋值 r = (A=true, B=true, C=true) 的联合势由 ψ(r) = φ_1(A=true, B=true) · φ_2(C=true, B=true) = φ_1 · φ_5 给出。

AABBCCφ_1φ_2

图1：一个示例FG，编码三个随机变量A、B和C上的概率分布（左）。因子φ_1和φ_2的函数定义（表示为势表）在右侧给出。
接下来我们介绍用于比较定义在非相同变量集上的模型的FGs扩展。

## 3 因子图扩展

通常，对FG的扩展可以添加新的因子、新的随机变量或边（即，将现有随机变量添加到现有因子中），只要添加新的随机变量，就会产生一个扩大的MS，在该MS上定义FG。其目的可能是部分更新FG，同时保留对潜在分布的准确描述。为了实现可比性，目标不是添加信息，而是使一个FG与另一个FG在结构上对齐，确保共同的MS，同时在投影到原始随机变量集时保留原始分布。在介绍一般FG扩展之后，我们应用均匀变量影响的概念作为特例，以确保理想的比较特性。

### 3.1 一般因子图扩展

本节定义FGs的一般扩展，重点关注结构关系（随机变量、因子），而不对因子中的势施加任何约束。

###### 定义 2 (因子图扩展)。

FG M = (V^{orig}, E^{orig}) = (R^{orig} ∪ Φ^{orig}, E^{orig}) 的一个**扩展** M^x = (V^x, E^x) = (R^x ∪ Φ^x, E^x) 是任意一个FG M^x，其中

- (i) R^x = R^{orig} ∪ R^{new}，且 R^{orig} ∩ R^{new} = ∅，
- (ii) Φ^x = Φ^{orig,x} ∪ Φ^{new}，且 Φ^{orig,x} ∩ Φ^{new} = ∅，并且 Φ^{orig,x} 是任意一组因子，存在一个双射 η: Φ^{orig} → Φ^{orig,x}，使得每当 η(φ_i) = φ_j^x 时，有 R_(i)^{orig} ⊆ R_(j)^x。

边集 E^x 包含一条连接随机变量 X ∈ R^x 和因子 φ_j^x ∈ Φ^x 的边，如果 X ∈ R_(j)^x。对于平凡扩展，有 R^{new} = ∅，Φ^{new} = ∅，且 Φ^{orig,x} = Φ^{orig}，从而得到 M^x = M。

###### 示例 2 (因子图扩展)。

考虑图1 (https://arxiv.org/html/2607.20502#S2.F1) 中描绘的FG M_ex，假设仅向 M_ex 添加一条边 {C, φ_1} 以得到 M_ex 的扩展 M_ex^x。那么，φ_1 的作用域从 R_(1)^{orig} = {A, B} 扩展到 R_(1)^x = {A, B, C}。我们得到 Φ^{orig,x} = {φ_1^x} ∪ (Φ^{orig} \ {φ_1})，其中 φ_1^x(A, B, C) 现在定义了一个具有 2^3 = 8 个条目（而非 2^2 = 4 个）的势表，且 R^{new} = ∅，Φ^{new} = ∅。

一旦任何原始因子 φ_i ∈ Φ^{orig} 被添加了边（作用域扩展），其势的数量会随着额外随机变量的取值范围的数量而增长。一般来说，这意味着 Φ^{orig,x} 既不是原始因子集 Φ^{orig} 的子集也不是超集。此外，尽管 M 在严格的图论意义上不一定是 M^x 的子图，但这种扩展保留了全联合概率分布的原始因子分解，即对于 M 中的每个因子，M^x 中存在一个因子，其作用域包含原始因子的作用域。

实现FG非平凡扩展的方式有多种。为了清晰区分不同情况