NP-hardness of MAP in Ternary Tree Bayesian Networks

This paper strengthens the NP-hardness result for the (partial) maximum a posteriori (MAP) problem in Bayesian networks with topology of trees (every variable has at most one parent) and variable cardinality at most three. MAP is the problem of querying the most probable state configuration of some (not necessarily all) of the network variables given evidence. It is demonstrated that the problem remains hard even in such simplistic networks.

Averaged Extended Tree Augmented Naive Classifier

This work presents a new general purpose classifier named Averaged Extended Tree Augmented Naive Bayes (AETAN), which is based on combining the advantageous characteristics of Extended Tree Augmented Naive Bayes (ETAN) and Averaged One-Dependence Estimator (AODE) classifiers. We describe the main properties of the approach and algorithms for learning it, along with an analysis of its computational time complexity. Empirical results with numerous data sets indicate that the new approach is superior to ETAN and AODE in terms of both zero-one classification accuracy and log loss. It also compares favourably against weighted AODE and hidden Naive Bayes. The learning phase of the new approach is slower than that of its competitors, while the time complexity for the testing phase is similar. Such characteristics suggest that the new classifier is ideal in scenarios where online learning is not required.

Learning Extended Tree Augmented Naive Structures

This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds' algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). We enhance our procedure with a new score function that only takes into account arcs that are relevant to predict the class, as well as an optimization over the equivalent sample size during learning. These ideas may be useful for structure learning of Bayesian networks in general. A range of experiments shows that we obtain models with better prediction accuracy than naive Bayes and TAN, and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator (AODE). We release our implementation of ETAN so that it can be easily installed and run within Weka.

Learning Bounded Tree-Width Bayesian Networks via Sampling

Learning Bayesian networks with bounded tree-width has attracted much attention recently, because low tree-width allows exact inference to be performed efficiently. Some existing methods [12, 14] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. In this paper, we propose a sampling method to efficiently find representative k-trees by introducing an Informative score function to characterize the quality of a k-tree. The proposed algorithm can efficiently learn a Bayesian network with tree-width at most k. Experiment results indicate that our approach is comparable with exact methods, but is much more computationally efficient.

Validating the use of intrinsic markers in body feathers to identify inter‑individual differences in non‑breeding areas of northern fulmars

Many wildlife studies use chemical analyses to explore spatio-temporal variation in diet, migratory patterns and contaminant exposure. Intrinsic markers are particularly valuable for studying non-breeding marine predators, when direct methods of investigation are rarely feasible. However, any inferences regarding foraging ecology are dependent upon the time scale over which tissues such as feathers are formed. In this study, we validate the use of body feathers for studying non-breeding foraging patterns in a pelagic seabird, the northern fulmar. Analysis of carcasses of successfully breeding adult fulmars indicated that body feathers moulted between September and March, whereas analyses of carcasses and activity patterns suggested that wing feather and tail feather moult occurred during more restricted periods (September to October and September to January, respectively). By randomly sampling relevant body feathers, average values for individual birds were shown to be consistent. We also integrated chemical analyses of body feather with geolocation tracking data to demonstrate that analyses of δ13C and δ15N values successfully assigned 88 % of birds to one of two broad wintering regions used by breeding adult fulmars from a Scottish study colony. These data provide strong support for the use of body feathers as a tool for exploring non-breeding foraging patterns and diet in wide-ranging, pelagic seabirds.

Learning Bayesian Networks with Bounded Tree-Width via Guided Search

Bounding the tree-width of a Bayesian network can reduce the chance of overfitting, and allows exact inference to be performed efficiently. Several existing algorithms tackle the problem of learning bounded tree-width Bayesian networks by learning from k-trees as super-structures, but they do not scale to large domains and/or large tree-width. We propose a guided search algorithm to find k-trees with maximum Informative scores, which is a measure of quality for the k-tree in yielding good Bayesian networks. The algorithm achieves close to optimal performance compared to exact solutions in small domains, and can discover better networks than existing approximate methods can in large domains. It also provides an optimal elimination order of variables that guarantees small complexity for later runs of exact inference. Comparisons with well-known approaches in terms of learning and inference accuracy illustrate its capabilities.