Bayesian networks are a widely used graphical model which formalize reasoning under uncertainty. Unfortunately, construction of a Bayesian network by an expert is timeconsuming, and, in some cases, all expertsmay not agree on the best structure for a problem domain. Additionally, for some complex systems such as those present in molecular biology, experts with an understanding of the entire domain and how individual components interact may not exist. In these cases, we must learn the network structure from available data. This dissertation focuses on score-based structure learning. In this context, a scoring function is used to measure the goodness of fit of a structure to data. The goal is to find the structure which optimizes the scoring function. The first contribution of this dissertation is a shortest-path finding perspective for the problem of learning optimal Bayesian network structures. This perspective builds on earlier dynamic programming strategies, but, as we show, offers much more flexibility. Second, we develop a set of data structures to improve the efficiency of many of the integral calculations for structure learning. Most of these data structures benefit our algorithms, dynamic programming and other formulations of the structure learning problem. Next, we introduce a suite of algorithms that leverage the new data structures and shortest-path finding perspective for structure learning. These algorithms take advantage of a number of new heuristic functions to ignore provably sub-optimal parts of the search space. They also exploit regularities in the search that previous approaches could not. All of the algorithms we present have their own advantages. Some minimize work in a provable sense; others use external memory such as hard disk to scale to datasets with more variables. Several of the algorithms quickly find solutions and improve them as long as they are given more resources. Our algorithms improve the state of the art in structure learning by running faster, using less memory and incorporating other desirable characteristics, such as anytime behavior. We also pose unanswered questions to drive research into the future.

Indiana University-Purdue University Indianapolis (IUPUI) / Bayesian networks, one of the most widely used techniques to understand or predict the future by making use of current or previous data, have gained credence over the last decade for their ability to simulate large gene expression datasets to track and predict the reasons for changes in biological systems. In this work, we present a dynamic Bayesian model with gene annotation scores such as the gene characterization index (GCI) and the GenCards inferred functionality score (GIFtS) to understand and assess the prediction performance of the model by incorporating prior knowledge. Time-course breast cancer data including expression data about the genes in the breast cell-lines when treated with doxorubicin is considered for this study. Bayes server software was used for the simulations in a dynamic Bayesian environment with 8 and 19 genes on 12 different data combinations for each category of gene set to predict and understand the future time- course expression profiles when annotation scores are incorporated into the model. The 8-gene set predicted the next time course with r>0.95, and the 19-gene set yielded a value of r>0.8 in 92% cases of the simulation experiments. These results showed that incorporating prior knowledge into the dynamic Bayesian model for simulating the time- course expression data can improve the prediction performance when sufficient apriori parameters are provided.

The Bayesian network (BN) formalism is a powerful representation for encoding domains characterised by uncertainty. However, before it can be used it must first be constructed, which is a major challenge for any real-life problem. There are two broad approaches, namely the hand-crafted approach, which relies on a human expert, and the data-driven approach, which relies on data. The former approach is useful, however issues such as human bias can introduce errors into the model. We have conducted a literature review of the expert-driven approach, and we have cherry-picked a number of common methods, and engineered a framework to assist non-BN experts with expert-driven construction of BNs. The latter construction approach uses algorithms to construct the model from a data set. However, construction from data is provably NP-hard. To solve this problem, approximate, heuristic algorithms have been proposed; in particular, algorithms that assume an order between the nodes, therefore reducing the search space. However, traditionally, this approach relies on an expert providing the order among the variables --- an expert may not always be available, or may be unable to provide the order. Nevertheless, if a good order is available, these order-based algorithms have demonstrated good performance. More recent approaches attempt to ''learn'' a good order then use the order-based algorithm to discover the structure. To eliminate the need for order information during construction, we propose a search in the entire space of Bayesian network structures --- we present a novel approach for carrying out this task, and we demonstrate its performance against existing algorithms that search in the entire space and the space of orders. Finally, we employ the hand-crafting framework to construct models for the task of diagnosis in a ''real-life'' medical domain, dementia diagnosis. We collect real dementia data from clinical practice, and we apply the data-driven algorithms developed to assess the concordance between the reference models developed by hand and the models derived from real clinical data.

The application of Bayesian networks within the field of institutional research is explored through the development of a Bayesian network used to predict first- to second-year retention of undergraduates. A hybrid approach to model development is employed, in which formal elicitation of subject-matter expertise is combined with machine learning in designing model structure and specification of model parameters. Subject-matter experts include two academic advisors at a small, private liberal arts college in the southeast, and the data used in machine learning include six years of historical student-related information (i.e., demographic, admissions, academic, and financial) on 1,438 first-year students. Netica 5.12, a software package designed for constructing Bayesian networks, is used for building and validating the model. Evaluation of the resulting model’s predictive capabilities is examined, as well as analyses of sensitivity, internal validity, and model complexity. Additionally, the utility of using Bayesian networks within institutional research and higher education is discussed. The importance of comprehensive evaluation is highlighted, due to the study’s inclusion of an unbalanced data set. Best practices and experiences with expert elicitation are also noted, including recommendations for use of formal elicitation frameworks and careful consideration of operating definitions. Academic preparation and financial need risk profile are identified as key variables related to retention, and the need for enhanced data collection surrounding such variables is also revealed. For example, the experts emphasize study skills as an important predictor of retention while noting the absence of collection of quantitative data related to measuring students’ study skills. Finally, the importance and value of the model development process is stressed, as stakeholders are required to articulate, define, discuss, and evaluate model components, assumptions, and results.

The thesis underpinning this study is as follows; it is possible to build machine models that are indistinguishable from the mental models used by humans to generate language to describe their environment. This is to say that the machine model should perform in such a way that a human listener could not discern whether a description of a scene was generated by a human or by the machine model. Many linguistic processes are used to generate even simple scene descriptions and developing machine models of all of them is beyond the scope of this study. The goal of this study is, therefore, to model a sufficient part of the scene description process, operating in a sufficiently realistic environment, so that the likelihood of being able to build machine models of the remaining processes, operating in the real world, can be established. The relatively under-researched process of reference object selection is chosen as the focus of this study. A reference object is, for instance, the `table' in the phrase ``The flowers are on the table''. This study demonstrates that the reference selection process is of similar complexity to others involved in generating scene descriptions which include: assigning prepositions, selecting reference frames and disambiguating objects (usually termed `generating referring expressions'). The secondary thesis of this study is therefore; it is possible to build a machine model that is indistinguishable from the mental models used by humans in selecting reference objects. Most of the practical work in the study is aimed at establishing this. An environment sufficiently near to the real-world for the machine models to operate on is developed as part of this study. It consists of a series of 3-dimensional scenes containing multiple objects that are recognisable to humans and `readable' by the machine models. The rationale for this approach is discussed. The performance of human subjects in describing this environment is evaluated, and measures by which the human performance can be compared to the performance of the machine models are discussed. The machine models used in the study are variants on Bayesian networks. A new approach to learning the structure of a subset of Bayesian networks is presented. Simple existing Bayesian classifiers such as naive or tree augmented naive networks did not perform sufficiently well. A significant result of this study is that useful machine models for reference object choice are of such complexity that a machine learning approach is required. Earlier proposals based on sum-of weighted-factors or similar constructions will not produce satisfactory models. Two differently derived sets of variables are used and compared in this study. Firstly variables derived from the basic geometry of the scene and the properties of objects are used. Models built from these variables match the choice of reference of a group of humans some 73\% of the time, as compared with 90\% for the median human subject. Secondly variables derived from `ray casting' the scene are used. Ray cast variables performed much worse than anticipated, suggesting that humans use object knowledge as well as immediate perception in the reference choice task. Models combining geometric and ray-cast variables match the choice of reference of the group of humans some 76\% of the time. Although niether of these machine models are likely to be indistinguishable from a human, the reference choices are rarely, if ever, entirely ridiculous. A secondary goal of the study is to contribute to the understanding of the process by which humans select reference objects. Several statistically significant results concerning the necessary complexity of the human models and the nature of the variables within them are established. Problems that remain with both the representation of the near-real-world environment and the Bayesian models and variables used within them are detailed. While these problems cast some doubt on the results it is argued that solving these problems is possible and would, on balance, lead to improved performance of the machine models. This further supports the assertion that machine models producing reference choices indistinguishable from those of humans are possible.

This research addressed one of the hard problems still plaguing the information security profession; detection of network activity deviations from authorized accounts when the deviations are similar to normal network activity. Specifically, when user and administrator type accounts are used for malicious activity, harm can come to the organization. Accurately modeling normal user network activity is hard to accomplish and detecting misuse is a complex problem. Much work has been done in the past with intrusion detection systems, but being able to detect masquerade events with high accuracy and low false alarm rates continues to be an issue. Bayesian networks have been successfully used in the past to reason under certainty by combining prior knowledge with observed data. The use of dynamic Bayesian Networks, such as multi-entity Bayesian network, extends the capability and can address complex problems. The goal of the research was to extend previous research with multi-entity Bayesian networks along with discretization methods to improve the effectiveness of the detection rate while maintaining an acceptable level of false positives. Preprocessing continuous variables has proven effective in prior research but has not been applied to multi-entity Bayesian networks in the past. Five different discretization methods were used in this research. Analysis using receiver operating characteristic curves, confusion matrix, and other comparison methods were completed as part of this research. The results of the research demonstrated that a multi-entity Bayesian network model based on multiple data sources and the relationship between the user attributes could be used to detect unauthorized access to data. The supervised top down discretization methods had better performance related to the overall classification accuracy. Specifically, the class-attribute interdependence maximization discretization method outperformed the other four discretization methods. When compared to previous masquerade detection methods, the class-attribute interdependence maximization discretization method had a comparable true positive rate with a lower false positive rate.

This thesis investigates the use of Bayesian Networks (BNs), augmented by the Dynamic Discretization Algorithm, to model a variety of clinical problems. In particular, the thesis demonstrates four novel applications of BN and dynamic discretization to clinical problems. Firstly, it demonstrates the flexibility of the Dynamic Discretization Algorithm in modeling existing medical knowledge using appropriate statistical distributions. Many practical applications of BNs use the relative frequency approach while translating existing medical knowledge to a prior distribution in a BN model. This approach does not capture the full uncertainty surrounding the prior knowledge. Secondly, it demonstrates a novel use of the multinomial BN formulation in learning parameters of categorical variables. The traditional approach requires fixed number of parameters during the learning process but this framework allows an analyst to generate a multinomial BN model based on the number of parameters required. Thirdly, it presents a novel application of the multinomial BN formulation and dynamic discretization to learning causal relations between variables. The idea is to consider competing causal relations between variables as hypotheses and use data to identify the best hypothesis. The result shows that BN models can provide an alternative to the conventional causal learning techniques. The fourth novel application is the use of Hierarchical Bayesian Network (HBN) models, augmented by dynamic discretization technique, to meta-analysis of clinical data. The result shows that BN models can provide an alternative to classical meta analysis techniques. The thesis presents two clinical case studies to demonstrate these novel applications of BN models. The first case study uses data from a multi-disciplinary team at the Royal London hospital to demonstrate the flexibility of the multinomial BN framework in learning parameters of a clinical model. The second case study demonstrates the use of BN and dynamic discretization to solving decision problem. In summary, the combination of the Junction Tree Algorithm and Dynamic Discretization Algorithm provide a unified modeling framework for solving interesting clinical problems.

One of the hardest challenges in building a realistic Bayesian network (BN) model is to construct the node probability tables (NPTs). Even with a fixed predefined model structure and very large amounts of relevant data, machine learning methods do not consistently achieve great accuracy compared to the ground truth when learning the NPT entries (parameters). Hence, it is widely believed that incorporating expert judgment or related domain knowledge can improve the parameter learning accuracy. This is especially true in the sparse data situation. Expert judgments come in many forms. In this thesis we focus on expert judgment that specifies inequality or equality relationships among variables. Related domain knowledge is data that comes from a different but related problem. By exploiting expert judgment and related knowledge, this thesis makes novel contributions to improve the BN parameter learning performance, including: • The multinomial parameter learning model with interior constraints (MPL-C) and exterior constraints (MPL-EC). This model itself is an auxiliary BN, which encodes the multinomial parameter learning process and constraints elicited from the expert judgments. • The BN parameter transfer learning (BNPTL) algorithm. Given some potentially related (source) BNs, this algorithm automatically explores the most relevant source BN and BN fragments, and fuses the selected source and target parameters in a robust way. • A generic BN parameter learning framework. This framework uses both expert judgments and transferred knowledge to improve the learning accuracy. This framework transfers the mined data statistics from the source network as the parameter priors of the target network. Experiments based on the BNs from a well-known repository as well as two realworld case studies using different data sample sizes demonstrate that the proposed new approaches can achieve much greater learning accuracy compared to other state-of-theart methods with relatively sparse data.

Power optimization is a crucial issue at all levels of abstractions in VLSI Design. Power estimation has to be performed repeatedly to explore the design space throughout the design process at all levels. Dynamic Power Dissipation due to Switching Activity has been one of the major concerns in Power Estimation. While many Simulation and Statistical Simulation based methods exist to estimate Switching Activity, these methods are input pattern sensitive, hence would require a large input vector set to accurately estimate Power. Probabilistic estimation of switching activity under Zero-Delay conditions, seriously undermines the accuracy of the estimation process, since it fails to account for the spurious transitions due to difference in input signal arrival times. In this work, we propose a comprehensive probabilistic switching model that characterizes the circuit's underlying switching profile, an essential component for estimating data-dependent dynamic and static power. Probabilistic estimation of Switching under Real Delay conditions has been a traditionally difficult problem, since it involves modeling the higher order temporal, spatio-temporal and spatial dependencies in the circuit. In this work we have proposed a switching model under Real Delay conditions, using Bayesian Networks. This model accurately captures the spurious transitions, due to different signal input arrival times, by explicitly modeling the higher order temporal, spatio-temporal and spatial dependencies. The proposed model, using Bayesian Networks, also serves as a knowledge base, from which information such as cross-talk noise due to simulataneous switching at input nodes can be inferred.

<p>Given a random sample from a multivariate probability distribution <em>p</em>, the maximum minimum parents and children algorithm locates the skeleton of the directed acyclic graph of a Bayesian network for <em>p</em> provided that there exists a faithful Bayesian network and that the dependence structure derived from data is the same as that of the underlying probability distribution.</p><p>The aim of this thesis is to examine the consequences when one of these conditions is not fulfilled. There are some circumstances where the algorithm works well even if there does not exist a faithful Bayesian network, but there are others where the algorithm fails.</p><p>The MMPC tests for conditional independence between the variables and assumes that if conditional independence is not rejected, then the conditional independence statement holds. There are situations where this procedure leads to conditional independence being accepted that contradict conditional dependence relations in the data. This leads to edges being removed from the skeleton that are necessary for representing the dependence structure of the data.</p>