Luận án tiến sĩ: Techniques for incorporating data quality assessments into learning algorithms for Bayesian networks

TECHNIQUES FOR INCORPORATING DATA QUALITY ASSESSMENTS INTO LEARNING ALGORITHMS FOR BAYESIAN NETWORKS By Valerie Kay Sessions Bachelor of Science College of Charleston, 2001 Master of Science University of Charleston, 2002 Submitted in Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy in the Department of Computer Science and Engineering College of Engineering and Information Technology University of South Carolina 2006 ụ or Professor Chairman, Examining Committee (comming Member Committee Member Committee Member ˆ Dean of the Graduate School UMI Number: 3245436 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.

® UMI UMI Microform 3245436 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 For my Grandfathers. Elzie Howard McCormick 1932-2003 Henry Thomas Sessions 1931-2006 il Acknowledgements I would like to first thank my husband Kip for his love and support - for listening to me and supporting me during both the highs and lows of the past years. I would like to thank my parents, Tommy and Debbie Sessions, for the drive they have instilled in me to begin this research and degree, and for instilling my faith in God which has allowed me to complete it; my in-laws, Paul and Ann Hooker, for countless hours of babysitting; my Grandmother for many dinner meals in Blythewood; my son Austin and new daughter Remley for sleeping every now and then so that I could finish one last page of writing. I would like to thank my entire committee for their time and patience with this process, especially Marco Valtorta for allowing me to spend countless hours in his office learning and asking endless questions.

I would also like to thank Jewel Rogers for all of her help administratively - she made commuting two hours possible. Thanks to all my fellow classmates for your inspiration and code snippets. Thanks to my girlfriends Chris and Amy for their support and love, my Women’s Bible Study and church for all of their prayers during this endeavor. Thank you to my former supervisor Richard Baker for funding this work and allowing me ample time to commute to Columbia, and many thanks to all my former co- workers at SPAWAR for their support (and covering for me) during this process.

ili Abstract The field of Bayesian Networks (BNs) has had much success in developing structure learning algorithms to learn BNs directly from data. However, research has normally started with the assumption that the data given to the learning algorithm is accurate. This assumption is a naive one and can lead to very biased and unrealistic decision making frameworks. If we are to use decision making algorithms to their full potential we must design them with the capability to account for data quality.

Our research lays the foundation for the development of new algorithms that incorporate data quality assessments into traditional BN learning algorithms — specifically the PC algorithm. We begin by reviewing Bayesian networks, learning algorithms, and data quality measures. We then quantify the effect of inaccurate data on the PC algorithm and develop three techniques for incorporating data quality assessments into the algorithm. Results indicate that a technique which modifies the significance level used by the PC algorithm is promising.

We show and explain these results and offer guidelines for future research in this area. EEE SEE ES 1 Acknowledgements.cececcsceceseeceeeneeeee scent eneeneeeeesneen eens eaenseaeaeneenenes ili t6. ene e ene EA SEE DO EE EEE ESE OEE OE EEE SEES EEE S EE SEE EEE Eee iv Iã520ö ii. vi 0): 5081i 640i nh ee.

HH ng ky 1 1.2 ©) 24:1 010 2:15 (0) | Oe 2 Chapter 2 Bayesian Network BasICS.c co SH HH SH KÝ KH nh x.1 Bayesian Network BaSICS. Lo ng HH ng HH nhà kh na 3 2.2 Learning Algorithms for Bayesian NetWOrks.--‹c-c con Hs HS nh ve, 14 2.3 Learning with Uncertain Evidence. cà se 21 Chapter 3 Data Quality MeasurermenIs.cn Hs nhe 24 3.1 Overview of Data QuaÌity.---c HH HH nh nh xu 24 KÝ 0. 30 E009) ảvvyiađaađiaiiiiiiiÝẢẢốỐốỐỐ.

co HS HH HH kh 34 3.2 Parameter Estimation ResuÌts.3 Structure Learning Resulfs.4 Conclusions Regarding Inaccurate Data.4 Development of Experimental Data Sets.«- 47 Chapter 4 Methods and Resulfs.cQQQQ nn HH HH HH kh he.1 Do Nothing Method.- HH HH nhớ 61 4.- con HH HH HH khe 61 4.3 The DQ Algorithm.- con HH HH he 62 4.2 Method Pseudo Code. ccc eeceeeceeec ee ec eens neeceeee essa eee en eens kệ 65 LEN -haaAaddđiiaiiiiidtidtddiididi.1 Visit to Asia Ñ€SuÏtS. con HH HH HH nha 68 4.-- HS HH nh nh Hy 85 4. ch ng nh nh 93 che.-- con n SH Khen 96 Chapter 5Š Conclusions and Future Work.

HH HH HH nh ke, 99 5.1 PC Algorithm ConcÌusions.2 Conclusions Regarding Methods.1 Visit to Asia ConcÌusiOns.2 Studfarm ConcÌuSiO'S. HS nh nh nhe 104 5.3 Modified DQ Algorithm. ce cecececececee eee eee eneeeesneneneeaenens 105 vi 5. cece ccccccecceeeuctcnateceveccssnceseteseeeeenecanaees 5310119124-104) PNW HiẳdtdddiẳẳẳẳŸẢ.

vi List of Figures PP ¿2a nh.3: Convergence of Beta Distribution.4: Visit to Asia — TWO ConfigurafiO'S. HH HH HH nh su 16 2.5: Relationship of Virtual Evidence to Prior Probability.1: Two Sources Report on Event A.cccccecceeceeeec ene nn HH HH He ng kh nh ng 28 3.2: T1 Probability Table — 80% Sensitivity, 95% SpecifÍicify. cỚ“Taaaa)aiO.5: Average Variance From Baseline. HS HH HH nhà yên 37 3.6: Comparison of learned potentIaÌs.- -- con n HH nh yên 38 3.7: Stud Farm Average Variance from Baseline.8: Stud Farm Learned Potentials Graph.

_- - HH HH n1 kh.9: NPC and CB Structure Learming Results.10: Incorrect links using the NPC Algorithm.11: Incorrect links using the CB algorithm.12: Visit to Asia “True” Probability Tables.13: Studfarm ““Irue” Probability Tables.14: ALARM “True” Probability Tables.--cnnn Hs khe, 59 3.15: Breakdown of Data S€fS. con nn nnnHnnn nn K n TK Ki viện 60 Vili 4. cọ HH HH HH HH KH Ki Ki Tà Ki Ki Ki Ki Ki ni tà tà tà tà ty 62 4.2: Average Degree of Nodes.- con HH HH nh kh nhe 65 4.3: Visit to Asia, One Data Set, Raw Results.4; Visit To Asia, One Data Set, Combined Results.5: Visit To Asia, One Data Set, Zeroed Results.6: Visit to Asia, TWwo Data Sets, Raw Resul(s.7: Visit to Asia, Two Data Sets, Combined Results .8: Visit to Asia, Two Data Sets, Zeroed Results .9: Visit to Asia, Three Data Sets, Raw Results.10: Visit to Asia, Three Data Sets, Combined Results .11: Visitto Asia, Three Data Sets, Zeroed Results .12: Studfarm, One Data Set, Raw Resulfs.13: Studfarm, One Data Set, Combined Results.14: Studfarm, One Data Set, Zeroed ResuÌt.15: Studfarm, Two Data Sets, Raw R€SUÌtS.16: Studfarm, Two Data Sets, Combined Resulfs.17: Studfarm, Two Data Sets, Zeroed Results.18: Studfarm, Three Data Sets, Raw Results.19: Studfarm, Three Data Sets, Combined ResuÌts.20: Studfarm, Three Data Sets, Zeroed ResSuÌts.21: Visit To Asia, Extra Test, Raw ResulÌ(s.22: Visit to Asia, Extra Test, Combined and Zeroed Form.23: Studfarm, Extra Test, Raw Results. con HH nu nhớ 95 1X 4.24: Studfarm, Extra Test, Combined and Zeroed ResuÌts.25: ALARM, Extra Test, Raw ResuÌts.26: ALARM, Extra Test, Combined and Zeroed Results.

96 4,27: Visit to Asia, Significance Test, One Data Set, Raw Results. 97 4,28: Visit to Asia, Significance Test, One Data Set, Combined Results.29: Visit to Asia, Significance Test, One Data Set, Zeroed Results.1: Commutativity of Methods.c HH HH kh nha 107 Chapter 1 Introduction 1.1 Research Motivation The field of Bayesian networks (BNs) has had much success in creating algorithms to learn directly from data. There are both parameter estimation and structure learning algorithms that have a high rate of success in creating useful BNs. However, research has normally started with the assumption that the data given to the learning algorithm is accurate and complete.

This assumption is a naive one and can lead to very biased and unrealistic decision making frameworks. There are numerous examples of faulty data collections — those as technical as the Hubble Telescope’s calibration problems, to the more human centered — lying on a credit card information form. If we are to use decision making algorithms to their full potential we must design them with the capability to account for data quality. Our research lays the foundation for the development of new algorithms that incorporate data quality assessments.

The specific goal of our research is to test three methods for incorporating data quality assessments into the PC structure learning algorithm used by the Hugin™ Decision Engine: the Threshold method, the manual DQ Algorithm (DQ Algorithm Part I), and the dynamic DQ Algorithm (DQ Algorithm Part ID. A method entitled Do Nothing was also tested as a baseline for comparing the effectiveness of these methods. These three methods give us a starting point for developing successful ways to account for, and diminish the effects of inaccurate data on our structure learning algorithms.2 Organization Chapter 2 provides a foundation for our work by giving an overview of BNs and the underlying rules of probability that govern them. This chapter also details popular BN learning algorithms, both in parameter estimation and structure learning.

Chapter 3 provides both the state of current data quality research as well as our own research into the effects of data quality (specifically inaccuracy) on BN learning algorithms. Chapter 4 provides an explanation and pseudo code for our methods, our test set up, and results of our tests. Finally, in Chapter 5 we discuss our conclusions regarding these results, and give suggestions for future research. Chapter 2 Bayesian Network Basics In order to examine the learning of BNs from data sets of low quality, we must first review the background of the algorithms and processes of BNs.

First, we will introduce the basics of probability and statistics, Bayes law, and evidence propagation. Then we will examine learning algorithms for BNs and discuss those employed for this research as well as fading and adaptation methods. We will also examine research in Data quality and how it can be incorporated into our learning algorithms. Finally, we will review complementary work conducted in the area of revision of parameters based on uncertain evidence.1 Bayesian Network Basics We will define a BN using graph theory, following [18].

A BN is a Directed Acyclic Graph (DAG) G = (V,E) where V is a set of variables and E is a set of directed edges between these variables, and a probability distribution, P, over the variables. The set (G, P) satisfies the Markov condition, which states that all variables are independent of their nondescendents given the set of its parents. Therefore following [14], for each variable A with parents Bj, ., Bp, there is a potential table P(A | Bi,. If A has no parents this becomes the unconditional probability P(A).

Each variable’s probability is represented by a probability table which shows its probability based on the states of its parents (or its unconditional probability if it is without parents). All of the basics of probability are relevant to these tables and will be reviewed here. Andrey Kolmogorov [14] formed the probability axioms in the 1930’s. He proposed that given an event E in a probability space S, there is a probability P(E) such that 1.

0< P(E) <1, and P(E) = 1 if E is a certain event. The sum of all of the events, E; (i=1, 2, .), in the sample space, S, is 1. For mutually exclusive events, E; and E2, P(E; U E2) = P(E) + P(E»).