概率电路的可扩展学习

Scalable Learning of Probabilistic Circuits

概率电路的可扩展学习

https://repositorio.usp.br/directbitstream/5744fd01-84ef-4171-a340-63cfb294e33f/3156850.pdf

摘要：

概率电路（PCs）是一类可处理的概率模型，能够在多项式时间内精确回答广泛范围的查询。虽然推理通常很直接，但学习既符合推理可处理性所需限制又能利用其表达能力的概率电路已被证明是一个挑战。本论文旨在从两个不同的角度提出快速且可扩展的概率电路结构学习算法：从逻辑的角度来看，我们高效地构建一个概率电路，它以逻辑约束的形式接受某些知识，并可扩展地将其转化为概率电路；从数据引导的结构搜索的角度来看，我们提出从随机超平面分层构建概率电路。我们通过实证表明，这两种方法在性能和可扩展性方面都与同一类别的最新方法具有竞争力。

1. 引言
   在我们的论文中，我们探索并开发了用于学习概率电路（PCs）的算法，概率电路是一类通过图形形式主义明确指定为分布的归纳组合的深度模型。只要确保某些图形属性成立，概率电路不仅具有高度的表达能力和效率，还能提供一系列可查询的可处理推理任务，使其成为强大的统计工具箱。我们从两个不同的视角来解决学习概率电路的问题：一个是逻辑视角，另一个是纯粹以数据为中心的视角。以神经符号主义的方式，我们利用已知的领域知识，从命题逻辑公式和可用数据中学习概率电路。我们表明，这种结合确定性和不确定性知识的学习方法不仅在数据稀缺的情况下优于纯数据驱动的方法，而且与同一类概率电路的现有算法相比，提供了一种更具可扩展性的方法。我们方法的初步版本发表于第8届知识发现、挖掘与学习研讨会[^Geh et al. 2020^]，完整版本随后出现在第37届人工智能不确定性会议[^Geh和Maúa 2021^]，这是概率机器学习和不确定性推理领域的顶级会议。

在一种完全不同的方法中，我们仅从数据的角度研究学习概率电路（PCs）的问题。我们重新审视了随机投影——一种已知的降维方法，并开发了一种通过分层堆叠随机投影高效构建概率电路的方法。我们通过实证表明，我们能够在竞争对手学习时间的一小部分内实现最先进的性能。这一贡献的初步版本发表于第4届可处理概率建模研讨会[^Geh和Maúa 2021^]，这是机器学习和人工智能领域概率建模专家的主要聚集地。此外，该论文在2022年第13届巴西人工智能与计算智能博士和硕士论文竞赛（CTDIAC）中获得第一名，这是一项每两年举办一次的活动，旨在表彰巴西在人工智能和计算智能主题上最佳的硕士和博士论文。最后，作为一项次要贡献，我们在论文中提供了一个关于概率电路最流行的几种学习算法的系统性综述。我们对每种算法进行了简要的复杂度分析——这一主题在机器学习文献中常常缺失——并详细说明了每种方法所假设的内容以及所需和提供的结构保证。由于篇幅限制，我们在本报告中省略了这一最后的贡献。

本文的结构如下。我们在第2节对概率电路进行简要的非正式介绍。随后，在第3节介绍我们第一个主要贡献，简要描述我们提出的学习算法，并展示实证结果。我们的第二个主要贡献在第4节中呈现；我们展示了我们方法背后的思想，并通过实证支持其性能和可扩展性。最后，我们在第5节结束本报告，对我们的贡献进行简要总结。

2 概率电路：鸟瞰视角

概率电路的一个吸引人之处在于其与其他概率模型的区别——可以从电路中提取的查询范围。计算诸如部分赋值（即边缘概率）、条件概率、最大后验概率，甚至是更高级的任务，如逻辑事件的概率和信息论查询（如熵和散度）等查询，只要其结构（即其计算图）满足某些（充分）条件，都可以在多项式时间（相对于电路大小）内提取。为了简化并尊重篇幅限制，我们避免定义这些条件，甚至不提供概率电路或 PSDD 的更正式定义。论文的第2章专门讨论这些形式化内容，包括对条件充分性的广泛讨论、流行概率模型和逻辑模型与概率电路的联系，以及电路的不同推理能力。

在满足可处理性条件组合的结构约束下，从数据中学习表达能力强的概率电路已被证明是一项相当困难的任务。当存在领域知识时，问题变得更加具有挑战性，因为概率电路的支持集还必须与先验知识一致。在下一节中，我们探讨了一种从确定性（以命题逻辑公式的形式）和不确定性知识（以数据的形式）学习 PSDD 的技术。

3. 从数据和先验知识中高效学习

尽管在构建PSDD的文献中已经有许多进展，但大多数工作要么专注于将CNF或DNF编译为最小可能的（即规范的）电路表示的纯逻辑方法[^Oztok和Darwiche 2015, Choi和Darwiche 2013]，要么专注于为特定领域任务学习电路[Choi等 2015, Shen等 2017]。在我们的贡献之前，只有两种现有的领域无关算法可以从数据中学习PSDD的结构：LEARNPSDD[Liang等 2017]和STRUDEL[Dang等 2020]，它们都是通过将初始电路扩展为更具表现力的概率电路，同时保留现有的结构约束和支持。然而，这也意味着它们将逻辑公式的翻译工作委托给一个独立的算法，例如从CNF编译。这种方法的主要缺点在于，那些在逻辑公式中不起作用（但在分布中可能具有概率作用）的变量将完全从逻辑翻译过程中被丢弃，这意味着得到的初始电路将包含这些变量的平凡表示（例如，完全因式分解），与电路的逻辑部分完全分离。

在我们于2021年发表在UAI[Geh和Maúa 2021]的文章中（其内容在论文的第4章中有详细描述），我们提出了第一个既能从逻辑公式又能从数据中学习概率电路的PSDD学习算法。

3.1 采样与电路平均化

3.2 实验
为了了解我们的方法在实际中的表现以及每种集成策略对性能的影响，我们在5个不同的领域对我们的方法进行了评估。由于描述每个实验设置需要较长的篇幅，我们建议读者参考论文的第4.4.1–3节。对于本报告，只需说明每个领域都包含数据和描述其领域知识的命题逻辑公式。
我们将SAMPLEPSDD的性能与STRUDEL[Dang等 2020]、LEARNPSDD[Liang等 2017]和LEARNSPN[Gens和Domingos 2013]进行了比较。值得注意的是，LEARNSPN是一种流行的纯数据驱动方法，用于学习一个更具灵活性的概率电路（PCs）类别（与我们为PSDDs施加的更强结构条件相比），在这里被用作衡量性能的基线。在STRUDEL的情况下，我们使用[Dang等 2020]提出的纯数据驱动方法作为初始电路，这意味着STRUDEL和LEARNSPN都不是基于领域知识的方法。我们实验了两种版本的LEARNPSDD：第一种遵循[Liang等 2017]描述的方法，即从包含逻辑公式的CNF编译初始电路，然后由LEARNPSDD扩展；第二种替代版本用于CNF表示不可行的情况，用BDD替换CNF编译，由于BDD是（P）SDD的严格子集[Bova 2016]，这一过程可以轻松完成。

实验运行于一台配备英特尔 i7-8700K 3.70 GHz 处理器、12 核心和 64GB 内存的计算机上。图 4 对比了我们的方法与竞品在 5 个数据集中的 3 个数据集上的结果（详见论文第 4.4 节），其中横轴量化了用于训练的可用数据的百分比，纵轴显示了测试对数似然值（越高越好）。值得注意的是，我们的方法在低数据量情况下表现尤为出色，即使在数据量增加时仍保持竞争力。图 4 显示了似然加权的性能最差，因为以这种方式训练的集成往往会退化为单个组件。相比之下，堆叠（stacking）被证明具有很强的竞争力。值得注意的是，图 4c 中 LEARNSPN 的中断是由于学习算法的高内存开销；当面对超过 50% 的数据集时，该算法耗尽了内存。图 4d 显示了每种算法的学习时间；每条曲线显示生成单个电路所需的平均时间（以秒为单位），除了 SAMPLEPSDD 的集成，它显示了采样 100 个电路并通过 LLW 学习组件权重的时间。平均而言，STRUDEL 学习单个 PSDD 需要 15 秒，LEARNPSDD 需要 13 分钟，而 SAMPLEPSDD 仅需 3 秒。论文第 4.4.5 节进一步评论了 SAMPLEPSDD 作为一种逻辑模型的性能，实证表明通过修改某些参数，我们能够在学习时间上付出代价的同时，更好地近似原始公式。

4 使用随机投影学习电路

随机投影（Random Projections, RPs）在密度估计树（Density Estimation Trees, DETs）的文献中广为人知，因为它们相比 k-d 树中常见的轴对齐分割，能够产生看似更好的数据分区[^Freund等 2008^]。直观来说，随机投影不过是在数据上分层堆叠的随机生成的斜交超平面，以将数据分割成单元格。有趣的是，[Dasgupta和Freund 2008]证明性地展示了，通过这种方式将数据分割成多面体，应该能够让DET以相当高的概率成功学习低维流形。不幸的是，尽管有这一吸引人的理论保证，DET在表达能力、准确性和灵活性方面仍不如更现代的概率模型。

最近的研究表明，概率电路与DET的关系比之前认为的更为密切[^Correia等 2020^]，事实上，DET是概率电路的一个子集。尽管这是一个有趣的话题，但为了简洁起见，我们把关于DET和PC关系的讨论保留到论文的示例2.3和第5.1节，而专注于一个更重要的问题：如果DET是PC的一种形式，我们能否利用已知的DET学习过程，并将其移植到更一般的电路中？更重要的是，随机投影在DET中的结果是否也适用于PC？我们试图从更实际的角度理解这个问题的答案，从而产生一种受DET已知随机投影学习算法启发的概率电路学习算法。

4.2 实验
我们在20个知名的二元数据集上评估了LEARNRP的性能，这些数据集用于密度估计[Lowd和Davis 2010, Van Haaren和Davis 2012]，并与五种最先进的概率电路（PCs）学习算法的报告结果进行比较：LEARNSPN、STRUDEL、LEARNPSDD、XPC[Mauro等 2021]和PROMETHEUS[Jaini等 2018]。需要注意的是，PROMETHEUS和LEARNSPN生成的电路在结构上限制较少，从而可能更具表达能力（尽管它们可执行的推理任务范围更窄）。我们报告了STRUDEL、LEARNPSDD和XPC的集成结果，这意味着这些方法生成的概率电路都属于LEARNRP生成的同一类电路。

令人惊讶的是，我们发现LEARNRP在与更复杂竞争对手的对比中平均排名第二（见表1），仅次于PROMETHEUS。除了数据拟合度外，我们还评估了LEARNRP和其他所有竞争对手（除了PROMETHEUS，因为没有其源代码）的学习时间。这一比较可以在论文的图5.7和5.8中可视化，其中我们将LEARNRP-F标记为100次小批量EM迭代和30次完整EM迭代，LEARNRP-100标记为100次小批量EM迭代，LEARNRP-0标记为仅学习结构而不微调权重的时间。我们发现，我们的方法比大多数其他技术快几个数量级，尽管我们实现了更好的性能。

5 结论
我们的论文目标有三个方面。第一项（次要）贡献，由于篇幅限制，我们在此文本中省略，包括对概率电路学习算法文献的系统性综述，以更好地呈现当前PC学习领域的最新进展。我们的第二项贡献描述了一种从数据和以命题逻辑公式形式的领域知识中学习特定类别概率电路（称为PSDDs）的算法。我们表明，当面临低数据量情况时，我们的方法表现优于竞争对手，而在其他情况下仍保持竞争力。在我们的第三项也是最后一项贡献中，我们试图利用随机投影——这是密度估计文献中一个众所周知的技巧，通过分层随机划分的方法构建概率电路。实验表明，我们的方法平均排名第二，尽管在学习时间上比其他方法快数个数量级。

原文链接：https://repositorio.usp.br/directbitstream/5744fd01-84ef-4171-a340-63cfb294e33f/3156850.pdf