用强化学习+局部对称性优化图模型推理顺序，提升效率。
Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress
- 用强化学习搜索变量消除顺序，结合局部对称性压缩中间结果。
- 利用对称性使中间结果编码大小显著减小，降低计算开销。
- 适合处理大规模有对称结构的图模型推理问题。
在图模型中通过变量消除进行高效概率推断，关键在于找到最优消除顺序。然而，对于变量数量庞大的模型，该问题属于难解的组合优化问题。近期有研究提出基于强化学习的方法，在张量网络中寻找高效的收缩顺序。由于图模型与张量网络存在对偶性，本文将此方法适配到图模型的概率推断中，并引入结构利用机制。当前智能体的代价函数基于中间结果大小，而该大小随索引数（即随机变量数）呈指数增长。本文表明，在推理过程中利用特定结构可实现中间结果的紧凑编码，其规模可显著缩小。通过改用紧凑编码大小作为代价函数，使智能体能探索更优的收缩顺序。本文考虑的结构为局部对称性（即模型因子内的对称性）。
原文摘要 · Abstract (English)
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).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。