Learning Cutset Networks by Integrating Data and Noisy, Local Estimates

通过集成数据和噪声、局部估计学习割集网络

https://openreview.net/pdf/4ba438602169ab687c018212d108c26c972934ac.pdf

摘要
我们考虑在切分集网络（CNs）中的以下参数学习任务：给定（1）完全观测数据，（2）大量边际概率分布（每个分布定义在变量的小子集上），以及（3）切分集网络结构，寻找一组参数设置，使得由此产生的切分集网络能够高效地整合数据中以及边际分布中存在的统计信息。在许多实际应用中，边际分布要么来自专家，要么来自外部过程，并且通常是不一致的，因为它们并非来自同一个联合概率分布。为了过滤这种不一致性，我们建议使用两个量的凸组合来近似学习目标：一个量通过KL散度强制接近边际分布，另一个量强制接近从数据中学习的切分集网络。我们开发了一种基于梯度的算法来最小化上述目标，并证明尽管在贝叶斯网络和马尔可夫网络上计算梯度是NP难的，但在切分集网络上可以高效地计算梯度，从而得到一个具有收敛保证的多项式时间算法。我们通过实验表明，我们的方法产生的模型是可行的，并且当边际分布表现出高度不一致性时，这些模型也明显优于仅从数据中学习的模型。

1 引言

迄今为止，学习切分集网络（CNs）以及其他类似的可处理概率模型（TPMs），如和积网络（Poon和Domingos [2011]）和概率句子决策图（Liang等 [2017]）的结构和参数的算法，都假设可以访问没有缺失值或仅有少量变量缺失值的完整或近乎完整的数据。然而，在现实世界中，以下场景却十分常见。学习算法只能访问少量近乎完整或完整的数据，以及大量从噪声数据、不完善领域知识和局部独立预测模型的某种组合中得出的局部边际统计信息。例如：（1）在社交网络Degenne和Forsé [1999]、Scott [1988]等应用领域中，由于隐私顾虑，只有有限的全局数据可供使用。但是，可以轻松检索到局部统计信息，例如关于联系人/连接的信息。（2）在生成模型的惰性学习中（Rahman等 [2019a]、Zheng和Webb [2000]、Zhang和Zhou [2007]），我们从各种来源（如每个统计信息的局部分类器或查询大型数据库）推导出在测试时间（即进行查询时）诱导概率模型所需的充分统计信息。（3）在主动学习（Settles [2012]）中，学习算法会与用户进行交互，请求用户为某些变量提供标签或一般局部边际概率分布，这些变量是用户在给定观测下的专长所在。

在本文中，我们专注于在给定数据和此类局部、噪声统计信息的情况下学习切分集网络（CNs）的参数。我们的学习器以最初从少量几乎没有缺失变量的数据中学习得到的CN作为输入，然后给定一组统计信息，迭代更新其参数，以最小化以下两个量的线性组合：1）由原始参数表示的分布与由更新后的参数表示的分布之间的距离；2）给定局部估计与使用更新后的分布计算得到的估计之间的距离之和。我们为此优化任务推导了一种基于梯度的方法。由于梯度计算需要计算变量子集的边际概率，因此在一般的任意概率模型上这是NP难的，但在CNs上却可以高效计算Vergari等 [2021]。这体现了在我们的学习环境中使用可处理模型的优点。我们在基准数据集上的实验结果表明，即使局部估计不一致，我们利用局部估计的方法在生成和预测性能上都比仅从数据中学习的原始模型有显著改进。此外，由于优化问题是平滑的，我们的方法在温和条件下保证能达到局部最优。

相关工作。Vomlel [1999, 2004]研究了将概率知识库整合在一起的问题，即从一个低维概率分布（局部估计）构建联合概率分布。Vomlel使用了经典优化方法——迭代比例拟合程序（IPFP）Deming和Stephan [1940]，并提出了一种称为广义期望最大化算法（GEMA）的变体来解决该问题。Vomlel为这些方法提供了收敛证明，表明当局部估计一致时IPFP收敛，即使局部估计不一致GEMA也能收敛。然而，Vomlel的方法计算复杂度很高（在局部估计定义的图的树宽上是指数级的），因此不切实际。本文提出的方法没有这个限制。Peng和Ding [2012]为IPFP提出了两种多项式时间近似方法，并将其应用于贝叶斯网络。然而，他们的初步实验研究表明，由于近似导致的误差相当高，如果局部估计不一致，则无法保证收敛。相比之下，我们提出的方法近似极少，并利用可处理推理来得出一种实用方案。

2 我们的方法

2.1 学习问题及其放宽

我们首先介绍所需的符号。大写字母（例如，X, Y, U等）和小写字母（例如，x, y, u等）分别用于表示离散随机变量及其取值。而粗体大写字母（例如，X, Y, U等）和粗体小写字母（例如，x, y, u等）则分别用于表示离散随机变量集合及其取值集合。为了简化说明，我们假设所有变量都是二元的，取值来自集合{0, 1}。

我们专注于学习切割集网络的参数，这是Rahman和Gogate在2016年提出的。有关这些易于处理的概率模型的简要介绍，请参见补充材料。在高层次上，切割集网络是一个AND/OR图，每个AND/OR图的叶节点都附加了一个树状贝叶斯网络。切割集网络由条件概率参数化，每个概率要么附加在AND/OR图中从OR节点到AND节点的边上，要么与叶节点上的树状贝叶斯网络相关联。更正式地说，设Θ表示切割集网络的参数集合，其中θxiui ∈ Θ等于条件概率P(Xi = 1|Ui = ui)。

我们假设我们可以访问可以通过成对分布来总结的局部信息。请注意，我们的算法可以很容易地扩展到任意局部边缘分布，我们仅为了清晰起见做出这一假设。设D表示两个定义在同一组变量上的概率分布之间的KL散度（距离），E表示随机变量对的子集，即E ⊆ {(Xj, Xk)|Xj, Xk ∈ X 且 j < k}。

有了这些符号和假设，我们的学习问题可以这样表述：

其中λ1 ≥ 0和λ2 ≥ 0是超参数（技术上，我们只需要一个超参数；我们使用两个是为了方便），它们分别模拟了局部和全局统计数据的相对重要性。

给定的方程（2）中的优化问题在参数Θ上不是凹的，但是是平滑的，因此可以使用迭代的梯度上升算法来解决。然而，为了有效地处理第二项的梯度，我们提出了以下矩匹配方法。

设Q表示与R具有相同结构的切割集网络相关的分布。因此，Q的参数与R的参数之间存在一一对应关系。设Π表示Q的参数集合。因此，给定一个参数πxi,ui ∈ Π，就有一个对应的参数θxi,ui在Θ中。设参数集合Π通过最大化对数似然从数据X中学习得到。由于切割集网络的参数是条件概率分布，给定从数据中学习得到的Q，我们可以使用Q和R参数之间的负交叉熵来代替方程（2）的第二项（对数似然）。数学上，

2.2 通过梯度上升法解决学习问题

在本节中，我们将推导出关于每个参数θ_xi,ui的梯度。关于θ_xi,ui对第二项求偏导数是直接且给出的（结果）为：

方程（3）中第一项的偏导数计算较为复杂，我们在以下命题中对其进行总结。（证明见附录。）

利用上述导数，我们正式提出了我们的算法，用于学习具有局部不一致统计数据的切割集网络或称为LCN-LIS（见补充材料中的算法1）。

LCN-LIS的主要优点是它具有多项式计算复杂度：时间（和空间）复杂度为O(|E| × |Θ| × T)，其中|E|表示作为输入提供给算法的成对（局部）概率分布的数量，|Θ|表示参数的数量，T表示迭代次数的上限。

备注：请注意，方程（3）中优化问题的可行解，因此算法1返回的解，会过滤掉局部估计中的不一致性，因为它产生了一个全局一致的模型RΘ。与之前提出的解决方程（1）中的优化任务的技术，如迭代比例拟合过程（IPFP）Deming和Stephan [1940]，Vomlel [2004]不同，当局部估计不一致时，这些技术不会收敛，而算法1会收敛到一个局部最优解（因为目标是平滑的）。

总结来说，我们推导并提出了一个基于梯度的算法，用于在存在局部估计的情况下学习切割集网络的参数（见算法1），并展示了该算法所需的时间和空间与给定的局部统计数据的数量成线性关系。请注意，命题1可以很容易地扩展到贝叶斯和马尔可夫网络。然而，问题是，在这些模型上，计算方程5中的分子项通常是NP-hard的。这突出了可处理模型的另一个优点，即使局部信息不一致，也可以有效地整合到一个可处理的模型中。

3 实验

我们进行了一项详细且受控的实验研究，以评估使用不一致的局部统计量对所学模型质量的影响。具体而言，我们采用了以下控制变量：（1）在算法1中从数据X学习到的切分集网络Q的准确性；（2）局部统计量Pjk(Xj, Xk)的不一致程度；（3）切分集网络架构；（4）测试时可用的证据变量或观测值的数量（以测试判别性能）。我们使用了20个基准数据集，这些数据集在之前的研究中已被广泛使用（Rooshenas和Lowd [2014, 2013]），以评估我们的新方法。

我们使用了真实P和所学模型（在各种条件下）之间的负交叉熵作为评估标准。负交叉熵越高，模型越好。对于每个数据集，我们学习了一个切分集网络的混合模型（Rahman等人[2014]），并将其作为真实模型P。我们使用训练集中随机选择的10%的样本来学习Q。因此，算法1使用的数据集比用于学习P的数据集少了90%的样本。我们这样做是为了确保真实模型P与Q之间存在显著差异，从而帮助我们评估局部信息如何改善一个较差的起始点的质量。

我们还使用了一个称为扰动率h的参数来控制Q的质量。h的值介于0和100之间，给定h的一个值，我们将Q中h%的参数替换为一个随机数。我们对Q进行了归一化，以确保它是一个有效的概率分布。

我们使用了三种类型的切分集网络结构来学习Q：（1）深度为0的切分集网络，这等价于Chow-Liu树（Chow和Liu [1968]，简称CLT）；（2）没有任何潜在变量的切分集网络（CN）；（3）切分集网络的混合（MCN）。后者是最新模型（Rahman等人[2019b]）。我们学习了判别式和生成式切分集网络。在判别式网络中，我们将L%的随机变量设置为证据E，并在给定证据变量赋值e的情况下，学习变量X \ E上的概率分布。我们为L使用了四个值：0、20、50和80。当L=0时，我们得到一个生成式模型，而其余模型为判别式模型。

我们使用了三种类型的切分集网络结构来学习Q：（1）深度为0的切分集网络，这等价于Chow-Liu树（Chow和Liu，1968年提出，简称CLT）；（2）没有任何潜在变量的切分集网络（CN）；（3）切分集网络的混合（MCN）。后者是最新模型（Rahman等人，2019b）。我们学习了判别式和生成式两种切分集网络。在判别式网络中，我们将L%的随机变量设置为证据E，并在给定证据变量赋值e的情况下，学习变量X \ E上的概率分布。我们为L使用了四个值：0、20、50和80。当L=0时，我们得到一个生成式模型，而其余模型为判别式模型。

我们从P生成局部统计量如下。由于P是一个可处理的模型，我们可以高效地（在线性时间内）计算所有Xj, Xk ∈ X的Pjk(Xj, Xk)。为了使其不一致，我们添加了一个值ε，该值是从均值为0、标准差为σ的正态分布中随机采样的。我们试验了五个σ值：0.001、0.01、0.05、0.1、0.2。请注意，在添加ε之后，我们必须对分布进行归一化，以确保它们是有效的。

结果。表1分别展示了Q和R在10个数据集上的生成式（0%证据）性能（更多结果请参见表2、3、4和5）。我们使用σ=0.1和h=0来生成表中给出的实验数据。每个表中的每个数字都是5次运行的平均值。为了避免混乱，我们没有报告标准差，因为在所有运行中，标准差都相当小。这些结果有助于我们分析切分集网络架构和证据变量数量对我们评估标准的影响。我们观察到，平均而言，使用局部不一致统计量可以使每种架构的负交叉熵提高17-23%。混合切分集网络（MCNs）是整体表现最好的模型，而Chow-Liu树（CLTs）的表现则明显较差。随着证据节点数量的增加，改进的程度没有显著差异。这表明我们的方法对于判别式和生成式模型同样有效。

图1展示了在电影数据集上训练的切分集网络（CN）的负交叉熵分数随扰动率（h）的变化。我们在补充材料中提供了其余数据集的图表。这些图表有助于我们评估Q的质量（即起点的影响）对算法1所学模型的影响。我们观察到，随着扰动率的增加，P和Q之间的负交叉熵显著下降。然而，P和R之间的负交叉熵保持相对平稳。这表明使用局部统计量可以显著提高模型质量，尤其是当基于全局数据的模型不准确时。

4 结论

在本文中，我们提出了一种在存在噪声局部估计的情况下学习切分集网络参数的新方法。与在学习过程中使用完整独立同分布（i.i.d.）数据的传统算法不同，我们提出了一种新颖的方法，该方法利用噪声局部信息来学习更准确和稳健的模型。使用局部估计的主要优势在于，与完整的i.i.d.数据相比，局部估计通常更容易获得。我们还通过在基准数据集上的实验表明，即使局部估计是不一致和带有噪声的，我们的新算法也能大大提高从i.i.d.数据中学到的初始模型的质量。