Скачать 0.88 Mb.

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: A Visual Tool for Domain Experts Tal Boneh Thesis submitted for Degree: Master in Computer Science Department of Computer Science and Software Engineering The University of Melbourne February, 2003 Produced on acidfree paper Abstract Bayesian networks are accepted in Artificial Intelligence research as representations of knowledge for reasoning under uncertainty and for putting causal models on a solid mathematical basis. A Bayesian Network (BN) represents a joint probability distribution on a set of statistical variables. It consists of a qualitative part (‘graph’ or ‘structure’) and an associated quantitative part (parameters). The graph represents the structural assumptions of the domain – the variables the domain is comprised of, their values, and the relationships between them – and is therefore the most important part of the model and needs to be constructed properly. However, there is little to support the process of constructing and testing the qualitative part independently of the quantitative part. The purpose of my research was to test the hypothesis that examining a BN structure through visualisation and verbal explanation of relationships, independently of the numbers, will help in communicating and explaining the model and BN technology to domain experts, and thus help them in constructing a BN of their domain and reduce their dependency on BN experts. I propose a novel approach that aims to improve on existing methods and tools, and to enable the domain expert to examine the structure of the network. In order to study the usefulness of this approach I designed and implemented a visual tool based on the principles of its materialisation. The tool, called VNET, supports the domain expert in the comparison between the structural assumptions of the domain and the graphical modelling decisions. When a relationship between variables is being investigated, VNET provides a visualisation and generates a verbal explanation, to help the user judge whether the relationship represented in the network matches their knowledge of the domain. This is predicated on the intuitive idea that such materialisation of the approach will give the domain expert insight regarding the BN under construction, and hence support the process of knowledge engineering. I evaluated the performance of the tool using case studies for qualitative evaluation of toy networks, elicited networks and learnt networks, employing three different methods of data collection: ‘evaluation’ of the tool by myself, ‘structured interview’ and ‘unstructured interview’. This evaluation indicated that the proposed approach is helpful in assessing the graph as a representation of the domain independently of the numbers; in revisiting and identifying potential structural errors and misconceptions both in the model and in the domain; in understanding and communicating the model, the domain and BN technology to the domain expert, providing a better insight into the structure of the network and its line of reasoning; for additional tasks such as rapid analysis of a large number of networks, thus supporting teaching tasks; for revealing statistical and logical relationships and investigating how statistical relationships represent logical relationships, and for deciding on the direction of arcs while constructing a network; in reducing the need for the involvement of a BN expert in the construction of a network by the domain expert. Declaration I, Tal Boneh, declare that this thesis is approximately 30,000 words in length, excluding tables, figures and appendices. Signed: ____________________________ Acknowledgements I owe many thanks to many people whose invaluable help enabled me to complete this work: To my husband Avihu, who had Bayesian Networks for dinners, for supporting and encouraging me at every stage of this research and thesiswriting. To my children Yael, Yuval, Michal and Ruthie, for their patience and significant sacrifice, especially during the school holidays. To Liz Sonenberg, my supervisor, who believed in me and allowed me to search and find my research question, for teaching me how to think academically and for her fantastic ‘bird’seye’ vision. To Ann Nicholson, my supervisor, who taught me Bayesian Networks, helped solving practical problems and was always there for me academically and as a friend in strange days and hours. To Kaye Stacey, for many hours of fruitful discussions, for contributing to my academic thinking and for her critical review of this manuscript. To Rik Head, for the time he dedicated for this study and his availability for lengthy telephone conversations regarding this study. To Shahar Mendelson, for teaching me how to write a mathematical text. To Leon Sterling, for his friendship and for his critical review of this manuscript. To my friends who supported me and helped with my kids during rough times. And finally, to my parents, who have always encouraged me to continue my education. Finally, I would like to thank the examiners of this thesis for their constructive comments and suggestions. 1 Introduction 1 1.1 Motivation 2 1.2 Aims 6 1.3 Methods 7 1.4 Specific Outcomes 8 1.5 Overview of Thesis 9 2 Literature Review 10 2.1 Mathematical Models in Artificial Intelligence 10 2.1.1 Probability Theory 11 2.1.2 Graph Theory 19 2.1.3 Graphical Models 20 2.2 Bayesian Networks  Directed graphs 21 2.2.1 BN as a representation of dependency independency assumptions 21 2.2.2 Parameters Considerations (The Quantitative Part) 24 2.2.3 BN as a compact representation of a JPD 25 2.2.4 Reasoning 25 2.2.5 Node elimination algorithm 26 2.3 Knowledge Engineering for BN construction 27 2.3.1 Graphical elicitation 28 2.3.2 Graph assessment 29 2.3.3 Parameters elicitation 30 2.3.4 Parameters assessment 31 2.3.5 Model Assessment 32 2.3.6 Problems arising during the KE process 33 2.3.7 Automated Construction of a Network 35 2.4 Existing tools for building Bayesian Networks 38 2.5 Explanation in BNs 40 3 Proposed Approach and its Materialisation 42 3.1 The approach 42 3.2 Application of the approach 42 3.3 Materialisation of the approach 43 3.4 The Functionality 44 3.4.1 Functionality for Assessment of Relationships 44 3.4.1.1 Questions 44 3.4.1.2 Visualisation and Verbal Explanation 46 3.4.1.3 An Extension for Assessment of Relationships 46 3.4.2 Support Features 47 3.5 The Methodology 49 3.5.1 Assessment of applicability 49 3.5.2 Setting a logical framework for the investigation 51 3.5.3 Components of the Proposed Methodology 52 3.5.3.1 Assessment of relationships 53 3.5.3.2 Assessment of applicability 54 3.5.3.3 Guiding User Verification 54 3.5.4 The Methodology Algorithm 55 4 Implementation: VNET 59 4.1 Foundation 59 4.1.1 Specific Questions 60 4.1.2 Visualisation 61 4.1.3 Language and Terminology 62 4.2 Implemented Functionality 63 4.2.1 Illustrative Example – The fire alarm 64 4.2.2 Assessment of relationships 65 4.2.2.1 Relationships between one node and the rest of the network 65 4.2.2.2 Relationships between two nodes 66 4.2.2.3 Relationships between sets of nodes (question 3, section 4.1.1) 68 4.2.3 Implemented Support features 69 4.3 Algorithms 70 4.3.1 Finding Blocking sets 70 4.3.2 Detecting dSeparation 74 4.3.3 Algorithms All Trails and Isolate 76 4.4 Issues Regarding User Interface 77 4.4.1 Main Screen 79 4.4.2 Menus 79 4.4.3 Tool Bar 79 4.4.4 Software tools and platform 80 4.5 Components of the Materialisation that were not Implemented 81 4.5.1 Functionality 81 4.5.2 Methodology 82 5 Evaluation – Case Studies 83 5.1 Evaluation Methods 83 5.2 Case study 1 – Evaluating the Tool by the Author: Toy Networks 85 5.2.1 Aims and Methods 85 5.2.2 Session 86 5.2.2.1 Marginal independency between common causes 87 5.2.2.2 Conditional independency between common effects 89 5.2.2.3 Conditional independency between nodes in different sub models 93 5.2.2.4 Direction of arcs 95 5.2.3 General Analysis of graphical modelling errors 95 5.3 Case study 2 – Structured Interview: Search and Rescue Domain 99 5.3.1 Domain 99 5.3.2 Expert’s BN Solution 99 5.3.3 Aims and methods 101 5.3.4 Session 102 5.3.5 Additional Analysis – Missing Variables and Divorcing Parents 107 5.3.5.1 Proposed Alternative Structures 108 5.4 Case study 3  Unstructured Interview: Decimal domain 112 5.4.1 Domain 112 5.4.2 BN Solution 113 5.4.3 Aims and Methods 114 5.4.4 Session 1 – Investigating relationships 115 5.4.4.1 Relationship between a Query Node and Observation Nodes 115 5.4.4.2 Relationships between observations 118 5.4.4.3 Revisiting network construction 120 5.4.5 Session 2 – Testing the Methodology 123 5.4.6 Summary 126 5.5 Discussion: Outcome of Evaluation 128 5.5.1 Evaluation of the Tool 128 5.5.2 Outcome 129 6 Conclusions and Future Work 134 6.1 Summary of contributions 135 6.2 Summary of limitations 135 6.3 Future Work 137 References 139 Appendices 147 Appendix 1: Questionnaire for VNET Assessment 147 1 VNET: General Information 150 1.1 Introduction. 150 1.2 Example (based on Poole, D., A. Mackworth, et al. (1998)) 151 1.2.1 Description of the net. 151 1.2.2 The net structure 152 1.2.3 Possible questions for the model 152 1.3 Tool Terminology: 153 1.4 VNET Description. 156 2 Preliminary information about user and model 159 2.1 The User 159 2.2 The Model. 160 3 Self guided tutorial 162 3.1 Selecting two nodes by inspecting the net. 162 3.2 Selecting a pair of nodes from the PairsList. 163 3.3 Selecting a node to be Isolated. 164 3.4 Selecting Query and Known nodes. 165 4 Reassessment of user and model 166 4.1 The User 166 4.2 The Model 166 5 VNET Assessment Questionnaire 168 5.1 Functionality 168 5.2 User Interface 170 Appendix 2: ToyNets 171 Appendix 3: SearchandRescue domain  parameters 184 Appendix 4: VNET Disk and Installation 185 List of Figures Figure 1.1: The place of the proposed approach, materialisation and tool in the context of the knowledge engineering process of BNs. 5 Figure 2.2 Two directed graphs. 20 Figure 2.3 dseparation. 22 Figure 2.4 Different reasoning patterns. 26 Figure 3.5 A simple BN 49 Figure 3.6: Flow chart of the interaction between the three principal components 52 Figure 3.7: Proposed methodology for assessing the graph structure in a BN model. 57 Figure 4.8 Proposed visualisation of the relation “X is dseparated from Y given Z”. 62 Figure 4.9: Proposed visualisation and verbal explanation of the relation “X is dseparated from Y given Z”. 63 Figure 4.10 A Bayesian Network for the Fire alarm structure 64 Figure 4.11: Visualisation of Markov Blanket for the node ‘Report’ 65 Figure 4.12: Visualisation of the relation “ ‘Phone Call’ is dseparated from ‘Alarm’ given ‘Smoke’ and ‘Leaving’ ” 67 Figure 4.13: Visualisation of the relation “ ‘Leaving’ is dseparated from ‘Tampering’ given ‘Alarm’ ” 68 Figure 4.14: Visualisation of the relation “ ‘Phone Call’ is dseparated from ‘Seasons’ and ‘Fire Place’ given ‘Smoke’ and ‘Fire’ ” 69 Figure 4.15 The main window in VNET. 79 Figure 5.16: Original network structure of the Searchand Rescue domain 100 Figure 5.17 Search and Rescue first network 103 Figure 5.18: SearchandRescue Second network. 104 Figure 5.19: A fragment of the new model for the SearchandRescue domain 108 Figure 5.20 : SearchandRescue fragments of the suggested new model 109 Figure 5.21: The elicited network structure for the decimal domain 113 Figure 5.22: Five learnt networks for the decimal domain 114 Figure 5.23: Flowchart of manual classification of the DCT data. 121 List of Tables Episodes Description 102 Physical Health – Mental Health 103 Temperature – Weather 104 Vegetation – Physical Health 105 Vegetation – Age 105 Health when Found – Find Location 105 Health when Found – Find Location 106 Health when Found – Dist_PLS 106 Find Location – Dist_PLS 106 Health when Found 106 Find Location 106 Dist_PLS 106 Vegetation 107 Class – T5 116 Class – T5, T1 and T2 are known 116 Class – T6 117 Class – T6, T1 and T2 are known 117 Class – T2 118 Class – T1 – T3 118 T1 – T2 119 T1 – T4 119 T3 – T2 119 Markov Blanket for Class 119 T5 – Query and T1, T2, T3, T4, T6 – Known 125 T6 – Query and T1, T2, T3, T4, T5 – Known 125 T2 – Query and T1, T3, T4, T5 – Known 125 T5 – Query and T1, T2, T3, T4 – Known 126 Rules for the analysis of data (based on [90]). 113 SearchandRescue Domain: Original Network parameters 184 