提出高效算法学习贝叶斯网络中的有向森林结构，显著提升推理速度与可解释性。
Exact and Approximate Algorithms for Polytree Learning
- 基于度数约束设计最优解算法，时间复杂度降至O((2+ε)^n)
- 对任意评分函数，可在多项式时间内找到接近最优的解
- 理论证明了算法效率的极限，适用于需要快速建模的场景
有向森林（Polytrees）是贝叶斯网络的一个子类，通过有向树状结构表示n个变量间的条件依赖关系，具有高效推理和良好可解释性的优势。由于学习最优有向森林问题是NP难的，本文研究在度数限制、评分函数性质及近似算法等条件下其可 tractability。我们提出一个算法，可在任意常数入度上限k下以O((2+ε)^n)时间求得最优解，优于此前O(3^n)的最快算法。此外，针对任意评分函数，给出了多项式时间算法，可获得与最优解相差不超过k倍的近似解；对于可加评分函数，近似因子可达2。许多结果均配有（几乎）紧致的下界，分别针对时间复杂度或近似因子。
原文摘要 · Abstract (English)
Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。