PAC-learning Bounded Tree-width Graphical Models
PAC-learning Bounded Tree-width Graphical Models
复制标题
PAC学习有界树宽图形模型
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Bilmes
中科院分区：
文献类型：
--
作者：
Mukund Narasimhan;J. Bilmes
我们表明，相对于Kullback-Leibler Divergence，最多可以有效地有效地有效地有k的PAC-LEARNT。以前解决此问题的方法，例如Chow（[1]）和Hoffgen（[7]）的方法表明，通过将其减少为组合优化问题，可以通过将其pac-learnnnne。但是，对于k> 1，此问题是NP完整的（[15]），因此，除非p = np，否则这些方法将需要指数级的时间。我们的方法与这些方法显着不同，因为它首先试图通过求解（多项式多个）下义优化问题来找到近似条件独立性，然后使用动态编程公式将近似条件独立性信息结合起来，以与图形模型相结合，并具有基础图形模型。指定的树宽。这为我们提供了有效的（随机变量数量中的多项式时间）PAC学习算法，该算法仅需要真实分布的多项式数量，仅需要多项式运行时间。
We show that the class of strongly connected graphical models with tree-width at most k can be properly efficiently PAC-learnt with respect to the Kullback-Leibler Divergence. Previous approaches to this problem, such as those of Chow ([1]), and Hoffgen ([7]) have shown that this class is PAC-learnable by reducing it to a combinatorial optimization problem. However, for k > 1, this problem is NP-complete ([15]), and so unless P=NP, these approaches will take exponential amounts of time. Our approach differs significantly from these, in that it first attempts to find approximate conditional independencies by solving (polynomially many) submodular optimization problems, and then using a dynamic programming formulation to combine the approximate conditional independence information to derive a graphical model with underlying graph of the tree-width specified. This gives us an efficient (polynomial time in the number of random variables) PAC-learning algorithm which requires only polynomial number of samples of the true distribution, and only polynomial running time.