Parent Assignment Is Hard for the MDL, AIC, and NML Costs

DOI10.1007/11776420_23MaRDI QIDQ5307575zbMATH OpenOpenAlexFDO

Authors Mikko Koivisto

Publication date 14 September 2007

Published in Learning Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11776420_23

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Large-sample learning of Bayesian networks is NP-hard
• Approximating MAPs for belief networks is NP-hard and other theorems
• scientific article; zbMATH DE number 1753154
• Learning Bayesian Networks Does Not Have to Be NP-Hard
• scientific article; zbMATH DE number 2243356

Cited in

(3)

• scientific article; zbMATH DE number 1753154 (Why is no real title available?)
• Improved building blocks for secure multi-party computation based on secret sharing with honest majority
• Entropy-based pruning for learning Bayesian networks using BIC

This page was built for publication: Parent Assignment Is Hard for the MDL, AIC, and NML Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5307575)