论文标题
在稀疏性约束下学习贝叶斯网络：参数化的复杂性分析
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
论文作者
论文摘要
我们研究了在网络上或其道德图上构成其他约束时学习最佳贝叶斯网络结构的问题。更确切地说，我们认为，就顶点或边缘删除而言，网络或其道德图与稀疏的Graph类$π$紧密相关。例如，我们表明，学习一个最佳网络，其道德图具有最大值1 $ k $的顶点删除距离，即最大程度1的$ k $可以在$ k $ stand的多项式时间内计算。这扩展了先前的工作，该算法给出了无端图的顶点删除距离的运行时间[Korhonen＆Parviainen，NIPS，2015年]。然后，我们表明进一步的扩展或改进是不可能的。例如，我们表明，学习网络或其道德图的最佳网络具有最高度$ 2 $或最多$ C $，$ C \ ge 3 $的连接组件是NP-HARD。最后，我们表明，在道德图中学习一个最佳网络，可能没有$ f（k）\ cdot | cdot | i | i |^{o（1）$ - 时间算法，相比之下，它最多可以在$ 2^{o（k）$ 2^{o | i | i | i | i | i | i | i |是总输入大小。
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class $Π$. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most $k$ from a graph with maximum degree 1 can be computed in polynomial time when $k$ is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree $2$ or connected components of size at most $c$, $c\ge 3$, is NP-hard. Finally, we show that learning an optimal network with at most $k$ edges in the moralized graph presumably has no $f(k)\cdot |I|^{O(1)}$-time algorithm and that, in contrast, an optimal network with at most $k$ arcs can be computed in $2^{O(k)}\cdot |I|^{O(1)}$ time where $|I|$ is the total input size.
