Efficient Recovery Of General Multi-dimensional Bayesian Network Classifier

Bayesian network(BN) is a probabilistic graphical model: an effective knowledge representative and reasoning tools for uncertainty. It can represent the relationships between variables in human understandable form. BN can provide powerful reasoning engine for instances including observations based on the complete sample observations or with missing values. BN has been widely applied in many fields of applications, including a variety of diagnostic and decision making applications. There are two common methods to learn the structure of BN:(1) building by experts in the field based on their expertise and experience;(2) learning by algorithms from the sample contains the information. The first method is suitable for small-scale applications; the second one became most common method when we deal the problems with large number of variables. It can be further divided into:(1) constraint based search(by using statistical dependency analysis method);(2) scores based search(Scoring and Search);(3) hybrid search(combines these two above methods). There are many BN learning algorithms have been proposed with various approaches. All BN structure learning algorithms have exponential complexity called NP-hard problem.Classification is a fundamental task in machine learning and data mining. According to the number of target variables can be divided into single and multi-dimensional classification. The BN has been applied to single-dimensional classification tasks, many classic simplified models were proposed in order to reduce the cost of learning, such as(Naive Bayes, NB) and many enhanced version of Naive Bayes. Although they require the assumption does not hold in the real world, but these simplified Bayesian network classifier(BNC) has achieved noticeable success.Multi-dimensional classification(MDC) aims to defining a function that assigns a vector of class values to a vector of observed features. Researches on multi-dimensional classification has been widely proposed to apply in the real world in recent years, such as one patient who has "high blood pressure", will be accompanied by the concurrent emergence of a variety of symptoms, including cardiac complications(such as left ventricular hypertrophy/UA/ myocardial infarction/heart failure), stroke(hemorrhagic stroke/ischemic stroke/hypertensive encephalopathy), the size of the arteries(atherosclerosis/aortic dissection), hypertensive renal damage(small renal arterial sclerosis/malignant small renal artery sclerosis/chronic renal failure) and so on. The specific symptoms of different dimensions are interrelated and dependent with each other; both values are predicted to detect objects based on mutual influence on each other's predictions. Multi-label classification is a special case of the multi-dimensional classification; the former can only predict the presence or absence of the target label(binary prediction).Multi-dimensional Bayesian network classifier(MBNC) was devised for MDC in 2006, but with constrained structure given strict assumption. MBNC is defined as two bipartite graph(Bi-partitie graph), can be driven into three separate sub-graphs: Class Sub-graph, Feature Sub-graph and Bridge Sub-graph. Traditional MBNC parent node in the target variable is only allowed(other) class variables, class sub-graph and feature sub-graph is relatively independent Directed acyclic graph(DAG), it can beexpressed as MBNC <DAG>- <DAG>. To reduce the cost of learning complexity, it applies some constraints on class sub-graph and feature sub-graph, <DAG>-<DAG>, the corresponding changes to <Empty>- <Empty>, <Polytree>- <Polytree> and <Tree >- <Tree>. In addition, the conventional MBNC default modeling features for all variables, including redundant and irrelevant variables. By eliminating the constraints and unnecessary variables, an unrestricted model called general multi-dimensional Bayesian network classifier(GMBNC) is proposed, and it contains only optimal features these are necessary for the prediction on vector of unknown classes, which is not owned by currently proposed MBNCs. Generally, GMBNC is only a small part of the whole BN, but it inherits all mature techniques applicable for BN, including parameter learning and inference. To avoid having to learn the complete BN initially, exact induction algorithms are proposed to conduct only local search. It has three merits,(1) recover general structure with no constrain on class/feature/bridge sub-graphs,(2) conduct local search without needing to recover the global Bayesian network, and(3) naturally embedded with feature subset selection.Through this thesis, we introduce a novel Bayesian network model for multi-dimensional classification. To accomplish this model, we deal with three novel algorithms for learning GMBNC.Our first contribution is to propose a novel general multi-dimensional Bayesian network classifier model called general multi-dimensional Bayesian network classifier. GMBNC only allows only essential nodes in the network these are optimal to classify the incoming instances with a vector of unknown class labels. GMBNC can give accurate classification performance. It is also different from current multi-dimensional Bayesian network classifiers(MBNCs) because of its unrestricted structure on the network.Our second contribution is addressing the novel algorithms for learning GMNBC. We propose three novel algorithms called IPC-GMNBC, based on iterative search of parents and children given on nodes of class variables. While DOS-GMBNC, dynamically ordering conditioning sets by their number of frequency appeared in previous tests when testing conditional dependency among nodes, and the last one LAS-GMNBC addressing the ordering of frequency number by replacing the weighting frequency. Those algorithms apply the constraint based filtering approach by using backward elimination techniques. These algorithms provide significant computational efficiency without scarifying the quality of network. The experimental study includes comparisons of IPC-GMBNC, DOS-GMNBC and LAS-GMBNC against state-of-the-art conventional approach of learning BN like PC algorithm. Experiments are conducted using samples generated from known Bayesian networks, including two real network(small one like Asia(8 nodes), medium ones like Alarm with 37 nodes)) and two synthetic networks(large ones like Test 100(100 nodes) and Test200(200 nodes)). The results demonstrate that LAS-GMNBC has better computation efficiency than DOS, IPC and PC. IPC-GMBNC can save 85% computational complexity, DOS-GMBNC achieve up to 95% and LAS-GMBNC even can reduce up to 99% compared to PC algorithm. Meanwhile all networks induced from proposed algorithms have the same(or even better) quality of density estimation as the whole structure of Bayesian network. Besides, these all algorithms can provide better quality in knowledge discovery than PC algorithm. This reflects the advantages of local search and feature selection respectively.