| This thesis explores the representational power of classes of Bayesian networks and algorithms for learning Bayesian networks.; A fundamental issue of classes of Bayesian networks is their representational power; that is, what kinds of functions they can or cannot represent. For Bayesian classifiers, such as Naive Bayes and Augmented Naive Bayes (ANB), their representational power is known in the binary domain, in which all variables are Boolean. In the nominal domain, however, a general case of the binary domain, their representational power is unknown.; We investigate Naive Bayes' geometric properties in the nominal domain, and find that Naive Bayes can represent some nonlinear functions, but it still cannot represent any nonlinear function containing an XOR of two variables. We present and prove a representational upper bound on ANB, and then extend it to general Bayesian networks. Roughly speaking, a Bayesian network with nodes having at most m − 1 parents cannot represent any function containing an XOR of m variables.; Another key issue of Bayesian networks is to learn Bayesian networks from data. What kinds of functions are learnable by Bayesian networks from data? This is the problem of learnability. For Naive Bayes, it has been found that it cannot learn even some linear functions, such as certain m-of-n functions, under the uniform sampling distribution. Under what conditions is a linear function learnable by Naive Bayes? For m-of-n functions, we propose and prove a sufficient and necessary condition for their learnability by Naive Bayes under the uniform sampling distribution. We also show that the learnability of Naive Bayes is dramatically affected by the sampling distribution.; In learning Bayesian networks for real-world applications, an important problem is the efficiency of learning algorithms. We propose an efficient algorithm, StumpNetwork, for learning TAN (Tree Augmented Naive Bayes). Both theoretical analysis and empirical comparison show that our StumpNetwork algorithm is faster than the state-of-the-art algorithm SuperParent in learning TAN while maintaining a similar predictive accuracy.; Most traditional learning algorithms are error-based. In many applications, however, accurate probability estimation is essential. We discuss the issue of using the area finder the ROC (Receiver Operating Characteristics) curve, or simply AUC, to evaluate classifiers. We compare Bayesian networks to decision tree learning algorithms, and find that Bayesian networks have significant advantages over decision trees from the view of accurate probability estimation. We propose an AUC-based algorithm for learning TAN, and show empirically that it outperforms several typical error-based learning algorithms not only in AUC, but also in classification accuracy.; In summary, this thesis addresses several fundamental and theoretical issues of Bayesian networks, and obtains some interesting results that help us to gain deeper understanding on the capability and limitations of Bayesian networks. On the other hand, it also presents several practical learning algorithms for learning Bayesian networks efficiently and effectively, which can be useful in real-world applications. |
