Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families-猫眼课题宝

DOI：

发表时间：

2021-10

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Goutham Rajendran;Bohdan Kivva;Ming Gao;Bryon Aragam

贪婪算法长期以来一直是学习图形模型的主力，更广泛地说是学习具有稀疏结构的统计模型。在学习有向无环图的上下文中，贪婪算法是流行的，尽管它们的最坏情况下的指数运行时间。但在实践中，它们非常有效。我们提供了新的见解这一现象，通过研究一个通用的贪婪分数为基础的算法学习DAG。与流行的GES和爬山算法等边贪婪算法不同，我们的方法是顶点贪婪的，最多需要多项式数量的分数评估。然后，我们展示了最近用于学习DAG模型的多项式时间算法如何成为该算法的特例，从而说明了这些基于顺序的算法如何被严格解释为基于分数的算法。这一观察表明，新的得分函数和最优性条件的基础上的二元性Bregman分歧和指数家庭，我们详细探讨。明确的样本和计算复杂性的界限。最后，我们提供了大量的实验表明，该算法确实优化了在各种设置的分数。

Greedy algorithms have long been a workhorse for learning graphical models, and more broadly for learning statistical models with sparse structure. In the context of learning directed acyclic graphs, greedy algorithms are popular despite their worst-case exponential runtime. In practice, however, they are very efficient. We provide new insight into this phenomenon by studying a general greedy score-based algorithm for learning DAGs. Unlike edge-greedy algorithms such as the popular GES and hill-climbing algorithms, our approach is vertex-greedy and requires at most a polynomial number of score evaluations. We then show how recent polynomial-time algorithms for learning DAG models are a special case of this algorithm, thereby illustrating how these order-based algorithms can be rigourously interpreted as score-based algorithms. This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families, which we explore in detail. Explicit sample and computational complexity bounds are derived. Finally, we provide extensive experiments suggesting that this algorithm indeed optimizes the score in a variety of settings.

Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families

文献摘要

相似文献