Kỹ Thuật Đánh Giá Chất Lượng Dữ Liệu Trong Thuật Toán Học Máy Cho Mạng Bayesian

Luận án tiến sĩ nghiên cứu techniques for incorporating data quality assessments into learning algorithms for bayesian networks, phân tích chuyên sâu, xây dựng mô hình lý thuyết,

• Tác giả: Valerie Kay Sessions
• Người hướng dẫn: Professor Chairman, Examining Committee
• Trường học: University South Carolina
• Chuyên ngành: Computer Science and Engineering
• Đề tài: Kỹ Thuật Đánh Giá Chất Lượng Dữ Liệu Trong Thuật Toán Học Máy Cho Mạng Bayesian
• Loại tài liệu: thesis
• Năm xuất bản: 2006
• Địa điểm: Columbia

Tóm tắt

I. Tổng Quan Về Đánh Giá Chất Lượng Dữ Liệu Trong Học Máy

Trong lĩnh vực thuật toán học máy, việc đảm bảo chất lượng dữ liệu là yếu tố then chốt để xây dựng các mô hình chính xác và đáng tin cậy. Đặc biệt, khi áp dụng các mạng Bayesian, vốn nhạy cảm với sai sót dữ liệu, việc đánh giá chất lượng dữ liệu trở nên vô cùng quan trọng. Dữ liệu không chính xác, không đầy đủ hoặc không nhất quán có thể dẫn đến những kết luận sai lệch và ảnh hưởng tiêu cực đến hiệu suất của mô hình. Bài viết này sẽ đi sâu vào các kỹ thuật đánh giá và cải thiện chất lượng dữ liệu trong bối cảnh mạng Bayesian. Chúng ta sẽ khám phá các phương pháp tiếp cận khác nhau, từ tiền xử lý dữ liệu đến các chỉ số đánh giá cụ thể, nhằm đảm bảo rằng dữ liệu đầu vào đáp ứng các tiêu chuẩn cần thiết cho việc xây dựng một mô hình học máy hiệu quả. Theo nghiên cứu của Valerie Kay Sessions, giả định rằng dữ liệu đầu vào cho thuật toán học là chính xác và đầy đủ là một giả định ngây thơ và có thể dẫn đến những quyết định sai lệch.

1.1. Tầm quan trọng của chất lượng dữ liệu cho mạng Bayesian

Mạng Bayesian là một công cụ mạnh mẽ để mô hình hóa các mối quan hệ xác suất giữa các biến. Tuy nhiên, độ chính xác của mô hình phụ thuộc rất lớn vào độ tin cậy của dữ liệu đầu vào. Dữ liệu sai lệch, nhiễu hoặc thiếu thông tin có thể làm sai lệch cấu trúc và tham số của mạng, dẫn đến những dự đoán không chính xác. Do đó, việc đánh giá chất lượng dữ liệu là bước không thể thiếu trong quy trình xây dựng và triển khai mạng Bayesian. Việc này giúp xác định và khắc phục các vấn đề tiềm ẩn, đảm bảo rằng mô hình được xây dựng dựa trên nền tảng dữ liệu vững chắc.

1.2. Các khía cạnh chính của chất lượng dữ liệu cần đánh giá

Khi đánh giá chất lượng dữ liệu, cần xem xét nhiều khía cạnh khác nhau, bao gồm tính chính xác, tính đầy đủ, tính nhất quán, tính kịp thời và tính hợp lệ. Tính chính xác đề cập đến mức độ dữ liệu phản ánh đúng thực tế. Tính đầy đủ đảm bảo rằng không có thông tin quan trọng nào bị thiếu. Tính nhất quán đảm bảo rằng dữ liệu không có mâu thuẫn nội bộ. Tính kịp thời đảm bảo rằng dữ liệu được cập nhật thường xuyên và phản ánh tình hình hiện tại. Tính hợp lệ đảm bảo rằng dữ liệu tuân thủ các quy tắc và ràng buộc đã được xác định. Việc kiểm định dữ liệu toàn diện trên các khía cạnh này giúp đảm bảo độ tin cậy của mô hình.

II. Thách Thức Trong Đánh Giá Chất Lượng Dữ Liệu Học Máy

Việc đánh giá chất lượng dữ liệu trong thuật toán học máy không phải là một nhiệm vụ đơn giản. Có nhiều thách thức cần vượt qua, từ việc xác định các nguồn sai lệch dữ liệu đến việc xử lý dữ liệu nhiễu và dữ liệu ngoại lai. Một trong những thách thức lớn nhất là sự thiếu hụt các phương pháp đánh giá tiêu chuẩn và khách quan. Các phương pháp hiện tại thường dựa trên kinh nghiệm chủ quan hoặc các chỉ số đánh giá đơn giản, không thể nắm bắt được toàn bộ bức tranh về chất lượng dữ liệu. Hơn nữa, việc xử lý dữ liệu thiếu và dữ liệu không nhất quán đòi hỏi các kỹ thuật tiền xử lý phức tạp và tốn thời gian. Theo Valerie Kay Sessions, việc phát triển các thuật toán mới để kết hợp đánh giá chất lượng vào các thuật toán học truyền thống là rất quan trọng.

2.1. Xác định và xử lý sai lệch dữ liệu trong mạng Bayesian

Sai lệch dữ liệu có thể xuất phát từ nhiều nguồn khác nhau, chẳng hạn như lỗi thu thập dữ liệu, lỗi nhập liệu hoặc sự thiên vị trong quá trình chọn mẫu. Trong mạng Bayesian, sai lệch dữ liệu có thể dẫn đến những kết luận sai lệch về mối quan hệ giữa các biến. Để giảm thiểu tác động của sai lệch dữ liệu, cần áp dụng các kỹ thuật kiểm định dữ liệu và xác thực dữ liệu nghiêm ngặt. Ngoài ra, có thể sử dụng các phương pháp làm sạch dữ liệu để loại bỏ hoặc sửa chữa các giá trị sai lệch.

2.2. Quản lý dữ liệu nhiễu và dữ liệu ngoại lai hiệu quả

Dữ liệu nhiễu và dữ liệu ngoại lai là những vấn đề phổ biến trong các tập dữ liệu thực tế. Dữ liệu nhiễu có thể làm giảm độ chính xác của mô hình, trong khi dữ liệu ngoại lai có thể làm sai lệch các tham số của mô hình. Để xử lý dữ liệu nhiễu, có thể sử dụng các kỹ thuật lọc dữ liệu và làm mịn dữ liệu. Để phát hiện và loại bỏ dữ liệu ngoại lai, có thể sử dụng các phương pháp thống kê hoặc các thuật toán phát hiện bất thường.

III. Phương Pháp Đánh Giá Độ Tin Cậy Dữ Liệu Cho Thuật Toán

Để giải quyết các thách thức trong đánh giá chất lượng dữ liệu, cần áp dụng các phương pháp tiếp cận toàn diện và có hệ thống. Một trong những phương pháp quan trọng nhất là kiểm định dữ liệu dựa trên các quy tắc và ràng buộc đã được xác định trước. Phương pháp này giúp phát hiện các giá trị không hợp lệ hoặc không nhất quán. Ngoài ra, có thể sử dụng các kỹ thuật phân tích dữ liệu để khám phá các mẫu và xu hướng bất thường trong dữ liệu. Các chỉ số đánh giá chất lượng dữ liệu cũng đóng vai trò quan trọng trong việc đo lường và theo dõi chất lượng dữ liệu theo thời gian. Theo Valerie Kay Sessions, việc kết hợp đánh giá chất lượng vào thuật toán PC (một thuật toán học cấu trúc mạng Bayesian) cho thấy nhiều hứa hẹn.

3.1. Sử dụng các chỉ số đánh giá chất lượng dữ liệu phù hợp

Có nhiều chỉ số đánh giá chất lượng dữ liệu khác nhau, mỗi chỉ số tập trung vào một khía cạnh cụ thể của chất lượng dữ liệu. Ví dụ, độ chính xác có thể được đo bằng tỷ lệ các giá trị đúng trên tổng số giá trị. Độ đầy đủ có thể được đo bằng tỷ lệ các giá trị không bị thiếu trên tổng số giá trị. Độ nhất quán có thể được đo bằng tỷ lệ các giá trị không mâu thuẫn trên tổng số giá trị. Việc lựa chọn các chỉ số đánh giá phù hợp phụ thuộc vào mục tiêu cụ thể của việc đánh giá chất lượng dữ liệu.

3.2. Áp dụng kỹ thuật kiểm định và xác thực dữ liệu toàn diện

Kiểm định dữ liệu và xác thực dữ liệu là các quy trình quan trọng để đảm bảo rằng dữ liệu tuân thủ các quy tắc và ràng buộc đã được xác định trước. Kiểm định dữ liệu có thể bao gồm việc kiểm tra phạm vi giá trị, kiểm tra định dạng và kiểm tra tính hợp lệ của các mối quan hệ giữa các biến. Xác thực dữ liệu có thể bao gồm việc so sánh dữ liệu với các nguồn thông tin bên ngoài hoặc việc yêu cầu xác nhận từ người dùng.

IV. Kỹ Thuật Tiền Xử Lý Dữ Liệu Để Cải Thiện Độ Tin Cậy Mô Hình

Tiền xử lý dữ liệu là một bước quan trọng trong quy trình xây dựng mô hình học máy. Các kỹ thuật tiền xử lý có thể giúp cải thiện chất lượng dữ liệu, giảm thiểu sai lệch và tăng cường độ chính xác của mô hình. Một số kỹ thuật tiền xử lý phổ biến bao gồm làm sạch dữ liệu, biến đổi dữ liệu, giảm chiều dữ liệu và tăng cường dữ liệu. Việc lựa chọn các kỹ thuật tiền xử lý phù hợp phụ thuộc vào đặc điểm cụ thể của dữ liệu và mục tiêu của mô hình. Theo Valerie Kay Sessions, việc xử lý dữ liệu thiếu là rất quan trọng vì dữ liệu thiếu là gần như không thể tránh khỏi.

4.1. Làm sạch dữ liệu để loại bỏ nhiễu và giá trị sai lệch

Làm sạch dữ liệu là quá trình loại bỏ hoặc sửa chữa các giá trị nhiễu và sai lệch trong dữ liệu. Các kỹ thuật làm sạch dữ liệu có thể bao gồm việc loại bỏ các giá trị trùng lặp, sửa chữa các lỗi chính tả, điền các giá trị bị thiếu và loại bỏ các dữ liệu ngoại lai. Mục tiêu của làm sạch dữ liệu là tạo ra một tập dữ liệu sạch và nhất quán, sẵn sàng cho việc phân tích và mô hình hóa.

4.2. Xử lý dữ liệu thiếu bằng các phương pháp phù hợp

Dữ liệu thiếu là một vấn đề phổ biến trong các tập dữ liệu thực tế. Có nhiều phương pháp khác nhau để xử lý dữ liệu thiếu, bao gồm việc loại bỏ các bản ghi có giá trị bị thiếu, điền các giá trị bị thiếu bằng các giá trị trung bình hoặc trung vị, hoặc sử dụng các thuật toán ước lượng giá trị thiếu. Việc lựa chọn phương pháp phù hợp phụ thuộc vào tỷ lệ dữ liệu thiếu và tác động của việc điền các giá trị bị thiếu đến độ chính xác của mô hình.

V. Ứng Dụng Thực Tế Cải Thiện Mô Hình Mạng Bayesian Với Dữ Liệu Chuẩn

Việc áp dụng các kỹ thuật đánh giá chất lượng dữ liệu và tiền xử lý dữ liệu có thể mang lại những cải thiện đáng kể cho hiệu suất của mô hình mạng Bayesian. Trong nhiều ứng dụng thực tế, việc cải thiện chất lượng dữ liệu đã dẫn đến tăng độ chính xác của mô hình, giảm sai số dự đoán và cải thiện khả năng khái quát hóa. Ví dụ, trong lĩnh vực y tế, việc làm sạch dữ liệu bệnh nhân và điền các giá trị bị thiếu có thể giúp cải thiện độ tin cậy của các mô hình dự đoán bệnh tật. Theo Valerie Kay Sessions, kết quả nghiên cứu chỉ ra rằng kỹ thuật sửa đổi mức ý nghĩa được sử dụng bởi thuật toán PC là rất hứa hẹn.

5.1. Ví dụ về ứng dụng trong lĩnh vực y tế và tài chính

Trong lĩnh vực y tế, mạng Bayesian được sử dụng rộng rãi để dự đoán bệnh tật, chẩn đoán bệnh và lựa chọn phương pháp điều trị. Việc đánh giá chất lượng dữ liệu bệnh nhân, bao gồm thông tin về tiền sử bệnh, kết quả xét nghiệm và triệu chứng lâm sàng, là rất quan trọng để đảm bảo độ tin cậy của các mô hình dự đoán. Trong lĩnh vực tài chính, mạng Bayesian được sử dụng để đánh giá rủi ro tín dụng, phát hiện gian lận và dự đoán thị trường chứng khoán. Việc đánh giá chất lượng dữ liệu tài chính, bao gồm thông tin về lịch sử tín dụng, giao dịch tài chính và dữ liệu thị trường, là rất quan trọng để đảm bảo độ chính xác của các mô hình dự đoán.

5.2. So sánh hiệu suất mô hình trước và sau khi cải thiện dữ liệu

Để chứng minh hiệu quả của việc cải thiện chất lượng dữ liệu, cần so sánh hiệu suất của mô hình mạng Bayesian trước và sau khi áp dụng các kỹ thuật đánh giá và tiền xử lý dữ liệu. Các chỉ số đánh giá có thể được sử dụng để đo lường sự cải thiện về độ chính xác, độ tin cậy và khả năng khái quát hóa của mô hình. Việc so sánh này giúp chứng minh giá trị của việc đầu tư vào quản lý chất lượng dữ liệu.

VI. Kết Luận và Hướng Nghiên Cứu Tương Lai Về Chất Lượng Dữ Liệu

Việc đánh giá chất lượng dữ liệu là một yếu tố then chốt để xây dựng các mô hình học máy chính xác và đáng tin cậy, đặc biệt là trong bối cảnh mạng Bayesian. Bằng cách áp dụng các phương pháp tiếp cận toàn diện và có hệ thống, có thể cải thiện chất lượng dữ liệu, giảm thiểu sai lệch và tăng cường hiệu suất của mô hình. Trong tương lai, cần tập trung vào việc phát triển các phương pháp đánh giá chất lượng dữ liệu tự động và khách quan hơn, cũng như các kỹ thuật tiền xử lý dữ liệu tiên tiến hơn. Theo Valerie Kay Sessions, cần có các hướng dẫn cho nghiên cứu trong tương lai.

6.1. Tóm tắt các phương pháp đánh giá và cải thiện dữ liệu

Bài viết đã trình bày một tổng quan về các phương pháp đánh giá chất lượng dữ liệu và tiền xử lý dữ liệu trong bối cảnh mạng Bayesian. Các phương pháp này bao gồm việc sử dụng các chỉ số đánh giá chất lượng dữ liệu, áp dụng các kỹ thuật kiểm định và xác thực dữ liệu, làm sạch dữ liệu, biến đổi dữ liệu, giảm chiều dữ liệu và tăng cường dữ liệu. Việc áp dụng các phương pháp này có thể giúp cải thiện độ chính xác, độ tin cậy và khả năng khái quát hóa của mô hình mạng Bayesian.

6.2. Hướng nghiên cứu tiềm năng trong lĩnh vực này

Trong tương lai, có nhiều hướng nghiên cứu tiềm năng trong lĩnh vực đánh giá chất lượng dữ liệu và tiền xử lý dữ liệu cho mạng Bayesian. Một hướng nghiên cứu là phát triển các phương pháp đánh giá chất lượng dữ liệu tự động và khách quan hơn, dựa trên các thuật toán học máy và trí tuệ nhân tạo. Một hướng nghiên cứu khác là phát triển các kỹ thuật tiền xử lý dữ liệu tiên tiến hơn, có thể xử lý các loại dữ liệu phức tạp và dữ liệu phi cấu trúc. Ngoài ra, cần nghiên cứu các phương pháp kết hợp đánh giá chất lượng dữ liệu và tiền xử lý dữ liệu vào quy trình xây dựng mô hình mạng Bayesian một cách tự động và hiệu quả.

Trích đoạn nội dung tài liệu

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»).