Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts




НазваниеSupport for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts
страница1/35
Дата05.10.2012
Размер0.88 Mb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   ...   35


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 acid-free 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 V-NET, 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, V-NET 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 thesis-writing.

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’s-eye’ 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: V-NET 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 d-Separation 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 V-NET Assessment 147

1 V-NET: 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 V-NET 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 Pairs-List. 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 V-NET Assessment Questionnaire 168

5.1 Functionality 168

5.2 User Interface 170

Appendix 2: Toy-Nets 171

Appendix 3: Search-and-Rescue domain - parameters 184

Appendix 4: V-NET 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 d-separation. 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 d-separated from Y given Z”. 62

Figure 4.9: Proposed visualisation and verbal explanation of the relation “X is d-separated 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 d-separated from ‘Alarm’ given ‘Smoke’ and ‘Leaving’ ” 67

Figure 4.13: Visualisation of the relation “ ‘Leaving’ is d-separated from ‘Tampering’ given ‘Alarm’ ” 68

Figure 4.14: Visualisation of the relation “ ‘Phone Call’ is d-separated from ‘Seasons’ and ‘Fire Place’ given ‘Smoke’ and ‘Fire’ ” 69

Figure 4.15 The main window in V-NET. 79

Figure 5.16: Original network structure of the Search-and Rescue domain 100

Figure 5.17 Search and Rescue first network 103

Figure 5.18: Search-and-Rescue Second network. 104

Figure 5.19: A fragment of the new model for the Search-and-Rescue domain 108

Figure 5.20 : Search-and-Rescue 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: Flow-chart 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

Search-and-Rescue Domain: Original Network parameters 184



  1   2   3   4   5   6   7   8   9   ...   35

Похожие:

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconThis document is being distributed by the American International Health Alliance (aiha) / the EurasiaHealth Knowledge Network with support from the us agency
Саратовский областной Центр по профилактике и борьбе со спид и инфекционными заболеваниями
Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconStudents will demonstrate competence in; Engineering Curriculum; basic concepts such as significant digits, length, and mass; Engineering Drawing; the use of the computer as an engineering tool; designing a project

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconAn Object-Oriented Support Tool for the Design of Casting Procedures

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconRegional network of co-operation in Europe as a tool of efficient governance

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconEnabling Decision Support and Costing of Product Designs by using Visual Metaphors

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconRepresenting and using legal knowledge in integrated decision support systems: DataLex WorkStations

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconThis document contains a list of references to publications and reports about Bayesian Net technology, and especially Bayesian Net applications. The report will

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconNorwegian Network for the Support of the Indigenous Peoples of the Russian Arctic (nnsipra) Сеть Норвежских Организаций в Поддержку Коренных Народов Российского Севера

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconDevelopment of a Product model to support engineering change management

Support for Graphical Modelling in Bayesian Network Knowledge Engineering: a visual Tool for Domain Experts iconTool Use: Misuse of shop tools will result in the loss of tool privileges

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница