Generalized Additive Bayesian Network Classifiers

1 Introduction

Bayesian networks (BN), also known as probabilistic graphical models, graphically represent the joint probability distribution of a set of random variables, which exploit the conditional independence among variables to describe them in a compact manner. Generally, a BN is associated with a directed acyclic graph (DAG), in which the nodes correspond to the variables in the domain and the edges correspond to direct probabilistic dependencies between them [Pearl, 1988].

Bayesian network classifiers (BNC) characterize the conditional distribution of the class variables given the attributes, and predict the class label with the highest conditional probability. BNCs have been successfully applied in many areas. Naive Bayesian (NB) [Langley et al., 1992] is the simplest BN, which only consider the dependence between each feature xi and the class variable y. Since it ignores the dependence between different features, NB may perform not well on data sets which violate the independence assumption. Many BNCs have been proposed to overcome NB's limitation. [Sahami, 1996] proposed a general framework to describe the limited dependence among feature variables, called k-dependence Bayesian network (kdB). [Friedman et al., 1997] proposed tree augmented Naive Bayes (TAN), a structure learning algorithm which learns a maximum spanning tree (MST) from the attributes. Both TAN and kdB have tree-structure graph. K2 is an algorithm which learns general BN for classification purpose [Cooper and Herskovits, 1992].

The key differences between these BNCs are their structure learning algorithms. Structure learning is the task of finding out one graph structure that best characterizes the true density of given data. Many criteria, such as Bayesian scoring function, minimal description length (MDL) and conditional independence test [Cheng et al., 2002], have been proposed for this purpose. However, it is inevitable to encounter such a situation: several candidate graph structures have very close score value, and are non-negligible in the posterior sense. This problem has been pointed out and presented theoretic analysis by [Friedman and Koller, 2003]. Since candidate BNs are all approximations of the true joint distribution, it is natural to consider aggregating them together to yield a much more accurate distribution estimation. Several works have been done in this manner. For example, [Thiesson et al., 1998] proposed mixture of DAG, and [Jing et al., 2005] proposed boosted Bayesian network classifiers.

In this paper, a new solution is proposed to aggregate candidate BNs. We put a series of simple BNs into the framework of generalized additive models [Hastie and Tibshirani, 1990], and adopt a gradient-based algorithm to learn the combining parameters, and thus construct a more powerful learning machine. Experiments on a large suite of benchmark data sets demonstrate the effectiveness of the proposed approach.

The rest of this paper is organized as follows. In Section 2, we briefly introduce some typical BNCs, and point out the non-negligible problem in structure learning. In Section 3, we propose the generalized additive Bayesian network classifiers. To evaluate the effectiveness of the proposed approach, extensive experiments are conducted in Section 4. Finally, concluding remarks are given in Section 5.

2 Bayesian Network Classifiers

A Bayesian network B is a directed acyclic graph that encodes the joint probability distribution over a set of random variables x = [x1, · · · , xd] T . Denote the parent nodes of xi by Pa(xi), the joint distribution PB(x) can be represented by factors over the network structures as follows:

Given data set D = {(x, y)} in which y is the class variable, BNCs characterize D by the joint distribution P(x, y), and convert it to conditional distribution P(y|x) for predicting the class label.

2.1 Several typical Bayesian network classifiers

The Naive Bayesian (NB) network assumes that each attribute variable only depends on the class variable, i.e,

Figure 1(a) illustrates the graph structure of NB.

Since NB ignores the dependencies among different features, it may perform not well on data sets which violate the attribute independence assumption. Many BNCs have been proposed to consider the dependence among features. [Sahami, 1996] presented a more general framework for limited dependence Bayesian networks, called k-dependence Bayesian classifiers (kdB).

Definition 1: A k-dependence Bayesian classifier is a Bayesian network which allows each feature xi to have a maximum of k feature variables as parents, i.e., the number of variables in Pa(xi) equals to k+1 ('+1' means that k does not count the class variable y).

According to the definition, NB is a 0-dependence BN. The kdB [Sahami, 1996] algorithm adopts mutual information I(xi; y) to measure the dependence between the ith feature variable xi and the class variable y, and conditional mutual information I(xi, x j|y) to measure the dependence between two feature variables xi and x j. Then kdB employs a heuristic rule to construct the network structure via these two measures.

kdB does not maximize any optimal criterion in structure learning. Hence, it yields limited performance improvement over NB. [Keogh and Pazzani, 1999] proposed super-parent Bayesian networks (SPBN), which assumes that there is an attribute acting as public parent (called super-parent) for all the other attributes. Suppose xi is the super parent, denote the corresponding BN as Pi(x, y), we have

It is obvious that SPBN structure is a special case of kdB (k=1). Figure 1(b) illustrates the graph structure of SPBN. The SPBN algorithm adopts classification accuracies as the criterion to select out the best network structure.

[Friedman et al., 1997] proposed tree augmented Naive Bayes (TAN), which is also a special case of kdB (k=1). TAN attempts to add edges to the Naive Bayesian network in order to improve the posterior estimation. In detail, TAN first computes the conditional mutual information I(xi, xj|y) between any two feature variables xi and xj, and thus obtain a full adjacency matrix. Then TAN employs the minimum spanning tree algorithm (MST) on the adjacency matrix to obtain a tree-structure BN. Therefore, TAN is optimal in the sense of MST. Many experiments show that TAN significantly outperforms NB. Figure 1(c) illustrates one possible graph structure of TAN.

Both kdB and TAN generate tree-structure graph. [Cooper and Herskovits, 1992] proposed the K2 algorithm, which adopts the K2 score measure and exhaustive search to learn general BN structures.

2.2 The structure learning problem

Given training data D, structure learning is the task of finding a set of directed edges G that best characterizes the true density of the data. Generally, structure learning can be categorized into two levels: macro-level and micro-level. In the macro-level, several candidate graph structures are known, and we need choosing the best one out. In order to avoid overfitting, people often use model selection methods, such as Bayesian scoring function, minimum descriptive length (MDL), etc [Friedman et al., 1997]. In the micro-level, structure learning cares about whether one edge in the graph should be existed or not. In this case, people usually employ the conditional independence test to determine the importance of edges [Cheng et al., 2002].

However, in both cases, people may face such a situation that several candidates (graphs or edges) have very close scores. For instance, suppose MDL is used as the criterion, people may encounter a situation that two candidate BN structure G1 and G2 have MDL score 0.899 and 0.900, respectively. Which one should be chosen? Someone may say that it is natural to select G1 out since it has a bit smaller MDL score, but practice may show that G1 and G2 have similar performance, and G2 may perform even better in some cases. In fact, both of them are non-negligible in the posterior sense.

This problem has been pointed out and presented theoretic analysis by [Friedman and Koller, 2003]. It shows that when there are many models that can explain the data reasonably well, model selection makes a somewhat arbitrary choice between these models. Besides, the number of possible structures grows super-exponentially with the number of random variables. For these two reasons, we don't want to do structure learning directly. We hope aggregating a series of simpler and weaker BNs together to obtain a much more accurate distribution estimation of the underlying process.

We note that several researchers have proposed some schemes for this purpose, for examples, learning mixtures of DAG [Thiesson et al., 1998], or ensembles of Bayesian networks by model averaging [Rosset and Segal, 2002; Webb et al., 2005]. We briefly introduce them in the following.

2.3 Model averaging for Bayesian networks

Since candidate BNs are all approximations of the true distribution, model averaging is a natural way to combine candidates together for a more accurate distribution estimation.

Mixture of DAG (MDAG)

Definition 2: If P(x| θc,Gc) is a DAG model, the following equation defines a mixture of DAG model

where πc is the prior for the c-th DAGmodel Gc, and πc ≥ 0, ∑c πc = 1, θc is the parameter for graphGc.

MDAG learns the mixture models via maximizing the posterior likelihood of given data set. In detail, MDAG combining uses the Chesseman-Stutz approximation and the Expectation-Maximization algorithm for both the mixture components structure learning and the parameter learning.

[Webb et al., 2005] presented a special and simple case of MDAG for classification purpose, called the average one dependence estimation (AODE). AODE adopts a series of fixstructure simple BNs as the mixture components, and directly assumes that all mixture components in MDAG have equal mixture coefficient. Practices show that AODE outperforms Naive Bayes and TAN.

Boosted Bayesian networks

Boosting is another commonly used technique for combining simple BNs. [Rosset and Segal, 2002] employed the gradient Boosting algorithm [Friedman, 2001] to combine BNs for density estimation. [Jing et al., 2005] proposed boosted Bayesian network classifiers (BBN), and adopted general AdaBoost algorithm to learn the weight coefficients.

Given a series of simple BNs: Pi(x, y), i = 1, · · · , n, BBN aims to construct the final approximation by linear additive models: P(x, y) = ∑n i=1 αiPi(x, y), where αi ≥ 0 are weight coefficients, and ∑i αi = 1. More generally, the constraint on αi can be relaxed, but only αi ≥ 0 is kept: F(x, y) = ∑n i=1 αiPi(x, y). In this case, the posterior can be defined as follows

For general binary classification problem y ∈ {-1,1}, this problem can be solved by the exponent loss function

via the AdaBoost algorithm [Friedman et al., 2000].

3 Generalized additive Bayesian networks

In this section, we present a novel scheme that can aggregate a series of simple BNs to a more accurate density estimation of the true process. Suppose Pi(x, y), i = 1, · · · , n are the given simple BNs, we consider putting them in the framework of generalized additive models (GAM) [Hastie and Tibshirani, 1990]. The new algorithm is called generalized additive Bayesian network classifiers (GABN).

In the GAM framework, Pi(x, y) are considered to be linear additive variables in the link function space:

GABN is an extensible framework since many different link functions can be considered. In this paper, we study a special link function: fi(·) = log(·). Defining z = (x, y) and taking exponent on both sides of the above equation, we have

This is in fact a potential function. It can also be written as a probabilistic distribution when given a normalization factor,

where S λ(z) is the normalization factor:

The likelihood of P(z) is called quasi-likelihood:

3.1 The Quasi-likelihood optimization problem

Maximizing the quasi-likelihood, we can obtain the solution of the additive parameters. To make the GAM model meaningful and tractable, we add some constraints to the parameters. The final optimization problem turns to be:

For equation constraint, the Lagrange multiplier can be adopted to transfer the problem into an unconstraint one; while for inequation constraints, classical interior point method (IPM) can be employed. In detail, the IPM utilizes barrier functions to transfer inequation constraints into a series of unconstraint optimization problems [Boyd and Vandenberghe, 2004].

Here, we adopt the most used logarithmic barrier function, and obtain the following unconstraint optimization problem:

where 1n indicates a n-dimensional vector with all elements equal to 1, rk is the barrier factor in the kth step of the IPM iteration, and α is the Lagrange multiplier.

Therefore, in the kth IPM iteration step, we need to maximize an unconstraint problem L(λ, rk, α). Quasi-Newton method is adopted for this purpose.

3.2 Quasi-Newton method for the unconstraint optimization problem

To solve the unconstraint problem: maxL(λ, rk, α), we must have the gradient of L w.r.t λ.

Theorem 1: The gradient of L(λ, rk, α) w.r.t λ is

Proof: In Equation (10), it is easy to obtain the gradient of the first summation term and non-summation terms. Here, we only present the gradient solution of the second summation term, i.e., logSλ(zk) in L(λ).

For computational cost consideration, we did not further compute the second order derivative of L(λ, rk, α), while adopted the quasi-Newton method [Bishop, 1995] to solve the problem. In this paper, the L-BFGS procedure provided by [Liu and Nocedal, 1989] is employed for this task.

3.3 The IPMbased training algorithm

The interior point method starts from a point in the feasible region, sequentially adjusts the barrier factor rk in each iteration, and solves a series unconstraint problemL(λ, rk, α), k = 1, 2, · · · . The detailed training algorithm is shown in Table 1.

Table 1: The training algorithm for GABN

Input: Given training set D = {(xi, yi)} N i=1

Training Algorithm

S0: set convergence precision ϵ > 0, and the maximal step M;

S1: initialize the interior point as λ = [λ1, · · · , λn] T , λi = 1/n;

S2: generate a series of simple BNs: Pi(x, y), i = 1, · · · , n;

S3: for k = 1 : M

S4: select rk > 0 and rk < rk-1, obtain the kth step optimization problem L(λ, rk, α);

S5: calculate gλ and the quasi-likelihood L(λ);

S6: employ L-BFGS procedure to solve: max L(λ, rk , α);

S7: test of the barrier term

S8: if ak < ϵ jump to S9, else continue the loop;

S9: Output the optimal parameter λ ∗ ,

and obtain the final generalized models P(z; λ ∗ ).

3.4 A series of fix-structure Bayesian networks

There are one unresolved problem in the algorithm listed in Table 1, which is in the S2 step, i.e, how to generate a series of simple BNs as the weak learner. There are many methods for this purpose. In our experiments, we take super parent BN as the weak learner. Readers may consider other possible strategies to generate simple BNs.

For a d-dimensional data set, when setting different attribute as the public parent node according to Equation (1), it can generate d different fix-structure super-parent BNs: Pi(x, y), i = 1, · · · , d. Figure 1(b) depicts one example of this kind of simple BNs. To improve performance, mutual information I(xi, y) is computed for removing several BNs with lowest mutual information score. In this way, we obtain n very simple BNs, and adopt them as weak learners in GABN.

Parameters (conditional probabilistic table) learning in BNs is common, and thus details are omitted here. Note that for robust parameter estimation, Laplacian correction and mestimate [Cestnik, 1990] are adopted.

3.5 Discussions

GABN has several advantages over the typical linear additive BN models: Boosted BN (BBN). First, GABN is much more computational efficient than BBN. Given d-dimensional and N samples training set, it is not hard to prove that the computational complexity of GABN is O(Nd 2 + MNd), where M is the IPM iteration steps. On the contrary, BBN requires sequentially learning BN structures in each boosting step. This leads to a complexity of O(KNd 2 ), where K is the boosting step, which is usually very large (in 10 2 magnitude). Therefore, GABN dominates BBN on scalable learning task. Practice also demonstrates this point.

Furthermore, GABN presents a new direction for combining weaker learners since it is a highly extensible framework. We present a solution for logarithmic link function. It is not hard to adopt other link functions under the GAM framework, and thus propose new algorithms. Many existing GAM properties, optimization methods can be seamlessly adopted to aggregate simple BNs for more powerful learning machines.

4 Experiments

This section evaluates the performance of the proposed algorithm, compared it with other BNCs such as NB, TAN, K2, kdB, SPBN; model averaging methods such as AODE, BBN; and decision tree algorithm CART [Breiman et al., 1984].

The benchmark platform was 30 data sets from the UCI machine learning repository [Newman et al., 1998]. One point should be indicated here: for BNCs, when data sets have continuous features, we first adopted discretization method to transfer them into discrete features [Dougherty et al., 1995]. We employed 5-fold cross-validation for the error estimation, and kept all compared algorithms having the same fold split. The final results are shown in Table 2, in which the results by TAN and K2 are obtained by the Java machine learning toolbox Weka [Witten and Frank, 2000].

To present statistical meaningful evaluation, we conducted the paired t-test to compare GABN with others. The last row of Table 2 shows the win/tie/lose summary in 10% significance level of the test. In addition, Figure 2 illustrates the scatter plot of the comparison results between GABN and other classifiers. We can see that GABN outperforms most other BNCs, and achieves comparable performance to BBN. Specially note, the SPBN column shows results by the best individual super-parent BN, which are significant worse than GABN. This demonstrates that it is effective and meaningful to use GAM for aggregating simple BNs.

5 Conclusions

In this paper, we propose a generalized additive Bayesian network classifiers (GABN). GABN aims to avoid the nonnegligible posterior problem in Bayesian network structure learning. In detail, we transfer the structure learning problem to a generalized additive models (GAM) learning problem. We first generate a series of very simple Bayesian networks (BN), and put them in the framework of GAM, then adopt a gradient-based learning algorithm to combine those simple BNs together, and thus construct a more powerful classifiers. Experiments on a large suite of benchmark data sets demonstrate that the proposed approach outperforms many traditional BNCs such as naive Bayes, TAN, etc, and achieves comparable or better performance in comparison to boosted Bayesian network classifiers. Future work will focus on other possible extensions within the GABN framework.