Finding a path is harder than finding a tree

被引：21

作者：

Meek, C ^{[1
]}

机构：

[1] Microsoft Res, Redmond, WA 98052 USA

来源：

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH | 2001年 / 15卷

关键词：

D O I：

10.1613/jair.914

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 [模式识别与智能系统]; 0812 [计算机科学与技术]; 0835 [软件工程]; 1405 [智能科学与技术];

摘要：

I consider the problem of learning an optimal path graphical model from data and show the problem to be NP-hard for the maximum likelihood and minimum description length approaches and a Bayesian approach. This hardness result holds despite the fact that the problem is a restriction of the polynomially solvable problem of finding the optimal tree graphical model.

引用

页码：383 / 389

页数：7

共 12 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BOEHNKE M, 1991, AM J HUM GENET, V49, P1174

[3]

Chickering D.M., 1996, Learning Bayesian Networks is NPComplete, V112, P121, DOI DOI 10.1007/978-1-4612-2404-4_12

[4]

APPROXIMATING DISCRETE PROBABILITY DISTRIBUTIONS WITH DEPENDENCE TREES [J].

CHOW, CK ;

LIU, CN .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (03) :462-+

[5]

COOPER GF, 1992, MACH LEARN, V9, P309, DOI 10.1007/BF00994110

[6]

Dasgupta S, 1999, UNCERTAINTY IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS, P134

[7]

OPTIMUM BRANCHINGS [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICAL SCIENCES, 1967, B 71 (04) :233-+

[8]

Heckerman D, 1998, NATO ADV SCI I D-BEH, V89, P301

[9]

HECKERMAN D, 1995, MACH LEARN, V20, P197, DOI 10.1007/BF00994016

[10]

KARP R, 1971, MATH PROGRAM, V1, P6

← 1 2 →