Budgeted Machine Learning with Bayesian Networks

Framework and C API for Budged Machine Learning with Bayesian Networks

In supervised machine learning, a learning algorithm is traditionally presented with training data consisting of labeled examples of some concept, represented by a set of variable parameters along with the label, to be learned and the type of model it should use for knowledge representation. The task of the learning algorithm is to construct a predictive model that can generalize from information modeled with the fully-specified examples in the training data to predict unknown labels from a previously-unobserved set of variable parameters.

In budgeted machine learning, the learning task is more complicated. While all of the examples’ labels remain available, their attribute values (descriptors) are initially unknown. Now the learning algorithm must purchase each value from the corresponding attribute, using a limited budget available to pay for them. After a value is purchased, it remains available and can be used for learning. So, a budgeted machine learning algorithm is presented not only with training data and the type of model to learn, but also with a budget of some value. The task of the learning algorithm is to both select the attributes from which to purchase values, and to construct a general model for the purchased values.

In this research, I extended existing budgeted machine learning algorithms that learn na ̈ıve Bayes classifiers to learn Bayesian networks. Conceptually, this is a natural extension because a Bayesian network can represent more general knowledge than a na ̈ıve Bayes classifier and stem from the same set of theoretical concepts. Specifically, a na ̈ıve Bayes classifier can only accurately model examples with attributes whose values occur independently of each other, but a Bayesian network can model conditional independence among attributes, allowing a much richer model to be constructed. To understand the performance gains of my algorithms, I ran the algorithms to learn both types of models for a number of data sets, using a range of budgets and various levels of prior knowledge. I compared the models by how accurately they could predict the labels of new examples (not used for learning) based on their known attribute values.

Budgeted Machine Learning Framework and C API

The Budgeted Machine Learning with Bayesian Network Experiment Framework (BLBN-EF) consists of two main components, in the form of computer programs: (1) the learner and (2) the generator. Both of these computer programs are implemented in the C programming language and make use of the BLBN application programming interface (API), which is also implemented in the C programming language. The BLBN API depends on the Norsys Netica C API for its Bayesian network data structures and algorithms. The BLBN API does not include its own Bayesian network data structure implementation. The BLBN API provides a framework for implementing budgeted machine learning algorithms that relies on the data structures and algorithms provided by the Netica C API whenever possible.

The BLBN-EF and the BLBN API was built to be used in an academic research environment. It has been designed to be simple and extensible, so new algorithms can be easily integrated into the API in a strightforward manner. To effectively use the BLBN-EF and BLBN API, it is crucial to be familiar with the Netica C API, since the BLBN-EF depends on the BLBN API, which in turn depends on the Netica C API.

This project was done with Stephen Scott, Yaling Zheng, Kung Deng at the University of Nebraska–Lincoln from 2009 to 2011.