Inference and Learning in Multi-dimensional Bayesian Network Classifiers

Abstract. We describe the family of multi-dimensional Bayesian network clas-siers which include one or more class variables and multiple feature variables. The family does not require that every feature variable is modelled as being de-pendent on every class variable, which results in better modelling capabilities than families of models with a single class variable. For the family of multi-dimensional classiers, we address the complexity of the classication problem and show that it can be solved in polynomial time for classiers with a graph-ical structure of bounded treewidth over their feature variables and a restricted number of class variables. We further describe the learning problem for the sub-family of fully polytree-augmented multi-dimensional classiers and show that its computational complexity is polynomial in the number of feature variables.