Title: The complexity of probabilistic inference in multi-dimensional Bayesian classifiers
Authors: Li, Guangdi
Issue Date: Jun-2014
Conference: Second International Conference of Advanced Computer Science & Information Thechnology (ACSIT-2014) edition:2 location:Zurich date:June 14-15
Abstract: Multi-dimensional Bayesian networks (MBCs) have been recently shown to perform efficient classifications. In this study, we evaluate the computational complexity of
exact inference, MAP (maximum a posterior) and MPE (most probable explanation) in
MBCs. Even when MBCs have simple graphical structures under strong constraints, we find that computing exact inference is NP-Complete, while computing MAP and MPE is NP-hard.
Publication status: accepted
KU Leuven publication type: IC
Appears in Collections:Laboratory of Clinical and Epidemiological Virology (Rega Institute)

Files in This Item:
File Description Status SizeFormat
MBC.pdf Accepted 146KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.