Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress

📄 arXiv: 2503.08786v1 📥 PDF

作者: Sagad Hamid, Tanya Braun

分类: cs.AI

发布日期: 2025-03-11

备注: Contributed to: Sixth Data Science Meets Optimisation (DSO) Workshop at IJCAI 2024

💡 一句话要点

结合局部对称性与强化学习优化概率图模型推理的消除顺序

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 概率图模型 变量消元 强化学习 局部对称性 概率推理 组合优化 张量网络

📋 核心要点

  1. 图模型概率推理中，寻找最优变量消除顺序是NP-hard问题，传统方法在大规模模型中效率低。
  2. 利用强化学习自动搜索最优消除顺序，并结合局部对称性进行中间结果的紧凑编码。
  3. 通过紧凑编码降低代价函数计算复杂度，使智能体能够探索更高效的收缩顺序。

📝 摘要（中文）

在图模型中，通过变量消元进行高效概率推理需要最优的消除顺序。然而，对于具有大量随机变量的模型，找到最优顺序是一个具有挑战性的组合优化问题。最近，一种强化学习方法被提出用于寻找张量网络中的高效收缩顺序。由于图模型和张量网络之间的对偶性，我们将这种方法应用于图模型中的概率推理。此外，我们将结构利用融入到寻找最优顺序的过程中。目前，智能体的代价函数是根据中间结果的大小来制定的，这些大小与索引（即随机变量）的数量成指数关系。我们表明，在推理过程中利用特定的结构可以对中间结果进行紧凑编码，从而显著减小中间结果的大小。通过考虑代价函数的紧凑编码大小，我们使智能体能够探索更有效的收缩顺序。在这项工作中，我们考虑的结构是局部对称性的存在（即模型因子内的对称性）。

🔬 方法详解

问题定义：论文旨在解决概率图模型中变量消元推理时，寻找最优消除顺序的问题。现有方法，如传统启发式搜索算法，在大规模图模型中效率低下，难以找到全局最优解。强化学习方法虽然有所改进，但其代价函数通常基于中间结果的大小，而中间结果的大小与随机变量的数量呈指数关系，导致计算复杂度高，难以探索更优的消除顺序。

核心思路：论文的核心思路是将强化学习与图模型的局部对称性相结合。利用强化学习自动搜索最优消除顺序，同时，通过挖掘和利用图模型中的局部对称性，对中间结果进行紧凑编码，从而降低代价函数的计算复杂度。这样，强化学习智能体可以在更小的状态空间中探索，从而找到更高效的消除顺序。

技术框架：该方法的技术框架主要包含两个部分：强化学习智能体和局部对称性利用模块。强化学习智能体负责探索不同的消除顺序，并根据代价函数（基于紧凑编码的中间结果大小）进行学习和优化。局部对称性利用模块负责检测图模型中的局部对称性，并根据这些对称性对中间结果进行紧凑编码。整体流程是：首先，强化学习智能体选择一个消除顺序；然后，根据该顺序进行变量消元，并在消元过程中利用局部对称性进行中间结果的紧凑编码；最后，根据紧凑编码的中间结果大小计算代价函数，并反馈给强化学习智能体，用于更新其策略。

关键创新：论文的关键创新在于将局部对称性利用与强化学习相结合，用于优化概率图模型的变量消元顺序。传统方法通常忽略图模型中的结构信息，而该论文通过挖掘和利用局部对称性，实现了中间结果的紧凑编码，从而降低了代价函数的计算复杂度，提高了强化学习智能体的搜索效率。

关键设计：论文的关键设计包括：1) 如何有效地检测和利用图模型中的局部对称性，实现中间结果的紧凑编码；2) 如何设计合适的代价函数，使其能够反映消除顺序的效率，并指导强化学习智能体的学习；3) 如何选择合适的强化学习算法，并对其进行调整，以适应概率图模型变量消元顺序优化的问题。具体的参数设置、损失函数、网络结构等技术细节在论文中未详细说明，属于未知信息。

📊 实验亮点

由于是 Work In Progress，论文中没有提供具体的实验结果。但是，论文提出了利用局部对称性进行中间结果紧凑编码的思路，理论上可以显著降低代价函数的计算复杂度，从而提高强化学习智能体搜索最优消除顺序的效率。未来的实验将验证该方法的有效性，并与其他基线方法进行比较。

🎯 应用场景

该研究成果可应用于多种概率图模型推理场景，例如贝叶斯网络、马尔可夫随机场等。在医疗诊断、金融风险评估、自然语言处理等领域，可以利用该方法提高概率推理的效率，从而实现更准确的预测和决策。未来，该方法还可以扩展到其他类型的结构化模型，例如张量网络，从而解决更广泛的优化问题。

📄 摘要（原文）

Efficient probabilistic inference by variable elimination in graphical models requires an optimal elimination order. However, finding an optimal order is a challenging combinatorial optimisation problem for models with a large number of random variables. Most recently, a reinforcement learning approach has been proposed to find efficient contraction orders in tensor networks. Due to the duality between graphical models and tensor networks, we adapt this approach to probabilistic inference in graphical models. Furthermore, we incorporate structure exploitation into the process of finding an optimal order. Currently, the agent's cost function is formulated in terms of intermediate result sizes which are exponential in the number of indices (i.e., random variables). We show that leveraging specific structures during inference allows for introducing compact encodings of intermediate results which can be significantly smaller. By considering the compact encoding sizes for the cost function instead, we enable the agent to explore more efficient contraction orders. The structure we consider in this work is the presence of local symmetries (i.e., symmetries within a model's factors).