Mạng Bayes

Mạng Bayes (tiếng Anh: Bayesian network hoặc Bayesian belief network hoặc belief network) là một mô hình xác suất dạng đồ thị.

Mạng Bayes là cách biểu diễn đồ thị của sự phụ thuộc thống kê trên một tập hợp các biến ngẫu nhiên, trong đó các nút đại diện cho các biến, còn các cạnh đại diện cho các phụ thuộc có điều kiện. Phân phối xác suất đồng thời (joint probability distribution) của các biến được xác định bởi cấu trúc đồ thị của mạng. Mô tả đồ thị của mạng Bayes dẫn tới các mô hình dễ giải thích, và tới các thuật toán toán học và suy luận hiệu quả.

Trong trường hợp tổng quát hơn, các nút có thể đại diện cho các loại biến khác, một tham số đo được, một biến ẩn (latent variable) hay một giả thuyết, chứ không nhất thiết phải đại diện cho các biến ngẫu nhiên.

Định nghĩa

Một mạng Bayes là một đồ thị có hướng phi chu trình mà trong đó:

• các nút biểu diễn các biến,
• các cạnh biểu diễn các quan hệ phụ thuộc thống kê giữa các biến và phân phối xác suất địa phương cho mỗi giá trị nếu cho trước giá trị của các cha của nó.

Nếu có một cạnh từ nút A tới nút B, thì biến B phụ thuộc trực tiếp vào biến A, và A được gọi là cha của B. Nếu với mỗi biến X_i, $i\in \{1,\ldots ,N\}$, tập hợp các biến cha được ký hiệu bởi parents(X_i), thì phân phối có điều kiện phụ thuộc của các biến là tích của các phân phối địa phương

$Pr(X_{1},\ldots ,X_{n})=\prod _{i=1}^{n}Pr(X_{i}\mid \operatorname {parents} (X_{i}))$

Nếu X_i không có cha, ta nói rằng phân phối xác suất địa phương của nó là không có điều kiện, ngược lại thì gọi là có điều kiện. Nếu biến được biểu diễn bởi một nút được quan sát, thì ta nói rằng nút đó là một chứng cứ (evidence node).

Các câu hỏi về sự phụ thuộc không tương đẳng giữa các biến có thể được trả lời bằng cách nghiên cứu đồ thị. Có thể chứng minh rằng trong đồ thị, tính độc lập có điều kiện được biểu diễn bởi tính chất đồ thị d-khả ly: cho trước một số nút hiển nhiên cụ thể, các nút X và Y là d-khả ly trong đồ thị khi và chỉ khi các biến X và Y là độc lập, với giá trị đã biết các chứng cứ tương ứng. Tập hợp gồm tất cả các nút khác mà X có thể phụ thuộc trực tiếp được cho bởi bao Markov của X.

Một ưu điểm của mạng Bayes là, về mặt trực quan, ta có thể hiểu các quan hệ phụ thuộc một cách trực tiếp và các phân phối địa phương dễ dàng hơn là phân phối có điều kiện phụ thuộc hoàn chỉnh.

Ví dụ

Nếu có hai lý do cho việc cỏ bị ướt (GRASSWET): hoặc do được tưới nước (SPRINKLER), hoặc do trời mưa (RAIN), thì tình huống này có thể được mô hình hóa bởi một mạng Bayes. Ở đây, các biến có hai trạng thái có thể: T (đúng) và F (sai).

Hàm xác suất phụ thuộc có điều kiện là

$Pr(GRASSWET,SPRINKLER,RAIN)=Pr(GRASSWET|SPRINKLER,RAIN).Pr(SPRINKLER|RAIN).Pr(RAIN)$

Mô hình có thể trả lời các câu hỏi như "Nếu cỏ ướt thì khả năng trời mưa là bao nhiêu?" bằng cách sử dụng các công thức xác suất có điều kiện và lấy tổng tất cả các biến trở ngại (nuisance variable):

$Pr({\mathit {RAIN}}=T\mid {\mathit {GRASSWET}}=T)={\frac {Pr({\mathit {GRASSWET}}=T,{\mathit {RAIN}}=T)}{Pr({\mathit {GRASSWET}}=T)}}$

$={\frac {\sum _{{\mathit {SPRINKLER}}\in \{T,F\}}Pr({\mathit {GRASSWET}}=T,{\mathit {SPRINKLER}},{\mathit {RAIN}}=T)}{\sum _{{\mathit {SPRINKLER}},{\mathit {RAIN}}\in \{T,F\}}Pr({\mathit {GRASSWET}}=T,{\mathit {SPRINKLER}},{\mathit {RAIN}})}}$

Thay thế các giá trị số, ta được Pr(RAIN=T | GRASSWET=T) = 891/2491 ≈ 35.77%.

Cách khác: (P(G=T,S=F,R=T) + P(G=T,S=T,R=T)) / (P(G=T,S=F,R=F) + P(G=T,S=T,R=F) + P(G=T,S=F,R=T) + P(G=T,S=T,R=T)) = (15.84%+0.198%) / (0.0%+28.8%+15.84%+0.198%) = 16.038% / 44.838% ≈ 35.77%.

Mạng Bayes nhân quả

Mạng Bayes nhân quả là một mạng Bayes mà trong đó các cạnh có hướng của đồ thị được hiểu là các quan hệ nhân quả trong một miền xác định có thực nào đó. Các cạnh có hướng, một cách tổng quát, không nhất thiết phải được hiểu là các quan hệ nhân quả; tuy nhiên, trong thực tiễn, tri thức về các quan hệ nhân quả rất hay được dùng để hướng dẫn vẽ các đồ thị mạng Bayes, kết quả là có được các mạng Bayes nhân quả.

Học cấu trúc

Trong trường hợp đơn giản nhất, một mạng Bayes được xây dựng bởi một chuyên gia và rồi được dùng để thực hiện việc suy luận. Trong các ứng dụng khác, công việc xây dựng mạng quá phức tạp đối với con người. Trong trường hợp này, cấu trúc và các tham số mạng của các phân bố địa phương phải được học từ dữ liệu.

Học cấu trúc của một mạng Bayes (nghĩa là học đồ thị) là một phần rất quan trọng của ngành nhận thức máy. Giả thiết rằng dữ liệu được sinh từ một mạng Bayes và rằng tất cả các biến là quan sát được (chứng cứ) trong mọi lần lặp, việc tối ưu hóa dựa trên phương pháp tìm kiếm có thể được dùng để tìm cấu trúc mạng. Việc này đòi hỏi một hàm tính điểm (scoring function) và một chiến lược tìm kiếm. Hàm tính điểm thông dụng là xác suất hậu nghiệm (posterior probability) của cấu trúc khi cho trước dữ liệu huấn luyện (training data). Quá trình tìm kiếm duyệt toàn cục để trả về một cấu trúc có số điểm tối ưu đòi hỏi thời gian cấp siêu lũy thừa (superexponential) theo số lượng biến. Ngược lại, các chiến lược tìm kiếm địa phương thực hiện các thay đổi tăng dần hướng tới việc nâng cao điểm số của cấu trúc. Một thuật toán tìm kiếm toàn cục như Phương pháp xích Markov Monte Carlo (Markov chain Monte Carlo) có thể tránh việc bị bẫy trong một cực tiểu địa phương.

Học tham số

Để cụ thể hóa mạng Bayes và biểu diễn đầy đủ các phân bố xác suất phụ thuộc có điều kiện, đối với mỗi biến X, cần phải chỉ ra phân bố xác suất X theo điều kiện thông tin từ các cha của X. Phân bố của X theo các cha của nó có thể có hình thức bất kỳ. Người ta thường dùng các phân bố rời rạc hay phân bố Gauss, do các phân bố này làm đơn giản việc tính toán. Đôi khi, khi chỉ biết được các ràng buộc của các phân bố; ta có thể dùng nguyên lý entropy cực đại để xác định một phân bố cụ thể, phân bố với entropy cực đại thỏa mãn các ràng buộc đó. (Tương tự, trong ngữ cảnh cụ thể của một mạng Bayes động, người ta thường lấy phân bố có điều kiện cho sự phát triển theo thời gian của trạng thái ẩn để cực đại hóa hệ số entropy (entropy rate) của quá trình ngẫu nhiên được nói đến.)

Thông thường, các phân bố có điều kiện này bao gồm các tham số chưa biết và phải được ước lượng từ dữ liệu, đôi khi bằng cách tiếp cận khả năng cực đại (maximum likelihood). Việc cực đại hóa trực tiếp khả năng (hoặc xác suất hậu nghiệm) thường phức tạp khi có các biến không quan sát được. Một cách tiếp cận truyền thống đối với vấn đề này là thuật toán cực đại hóa kỳ vọng (expectation-maximization algorithm), thuật toán này luân phiên giữa việc tính toán các giá trị kỳ vọng của các biến không được quan sát theo dữ liệu quan sát được, với việc cực đại hóa khả năng (hay hậu nghiệm) hoàn chỉnh với giả thuyết rằng các giá trị mong đợi đã tính được là đúng đắn. Dưới các điều kiện chính quy và vừa phải, quá trình này hội tụ về các giá trị khả năng cực đại (hay xác suất hậu nghiệm cực đại) của các tham số. Một cách tiếp cận Bayes đầy đủ hơn đối với việc học tham số là coi các tham số như là các biến không quan sát được khác và tính một phân bố hậu nghiệm đầy đủ trên toàn bộ các nút theo dữ liệu quan sát được, sau đó tách các tham số ra. Cách tiếp cận này có thể có chi phí tính toán cao và dẫn đến các mô hình có số chiều lớn, do đó trong thực tế, các cách tiếp cận truyền thống thường được sử dụng hơn.

Suy luận

Do mạng Bayes là một mô hình hoàn chỉnh cho các biến và các quan hệ giữa chúng, có thể dùng mạng Bayes để trả lời các truy vấn xác suất về các biến này. Ví dụ, mạng Bayes có thể được dùng để tìm tri thức mới nhất về trạng thái của một tập con gồm các biến khi các biến khác (các biến hiển nhiên) được quan sát. Quá trình tính phân bố hậu nghiệm này của các biến khi cho trước các biến hiển nhiên được gọi là suy luận xác suất. Quá trình hậu nghiệm cho ra một thống kê đủ phổ quát (universal sufficient statistic) cho các ứng dụng phát hiện, khi người ta muốn chọn các giá trị cho một tập con các biến nhằm mục đích cực tiểu hóa một hàm phí tổn nào đó, chẳng hạn xác suất của lỗi quyết định. Do đó, có thể coi mạng Bayes là một cơ chế cho việc xây dựng tự động các mở rộng của định lý Bayes cho các bài toán phức tạp hơn.

Ứng dụng

Mạng Bayes được dùng cho việc mô hình hóa tri thức trong các mạng điều hòa gene (gene regulatory network) , trong các hệ thống y học, phân tích văn bản, xử lý ảnh dung hợp dữ liệu , và các hệ hỗ trợ quyết định (decision support system)

Xem thêm

• Suy luận Bayes
• Định lý Bayes
• Thống kê Bayes
• Mô hình đồ thị (Graphical model)
• Học máy
• Đa cây (Polytree)

Liên kết và phần mềm

Tiếng Anh:

• An Introduction to Bayesian Networks and their Contemporary Applications
• On-line Tutorial on Bayesian nets and probability
• Web-App to create Bayesian nets and run it with a Monte Carlo method
• Continuous Time Bayesian Networks
• Bayesian Networks: Explanation and Analogy
• A live tutorial on learning Bayesian networks
• A hierarchical Bayes Model for handling sample heterogeneity in classification problems, provides a classification model taking into consideration the uncertainty associated with measuring replicate samples.
• Hierarchical Naive Bayes Model for handling sample uncertainty Lưu trữ 2007-09-28 tại Wayback Machine, shows how to perform classification and learning with continuous and discrete variables with replicated measurements.

Tài liệu tham khảo thêm

• Finn V. Jensen. Bayesian Networks and Decision Graphs. Springer, 2001.
• Judea Pearl, Stuart Russell. Bayesian Networks. UCLA Cognitive Systems Laboratory, Technical Report (R-277), tháng 11 năm 2000.
• Judea Pearl, Stuart Russell. Bayesian Networks, in M. A. Arbib (Ed.), Handbook of Brain Theory and Neural Networks, pp. 157–160, Cambridge, MA: MIT Press, 2003, ISBN 0-262-01197-2.
• Neil M, Fenton N, Tailor M, "Using Bayesian Networks to model Expected and Unexpected Operational Losses", Risk Analysis: An International Journal, Vol 25(4), 963-972, 2005. http://www.dcs.qmul.ac.uk/~norman/papers/oprisk.pdf
• Enrique Castillo, José Manuel Gutiérrez, and Ali S. Hadi. Expert Systems and Probabilistic Network Models. New York: Springer-Verlag, 1997. ISBN 0-387-94858-9
• Fenton NE and Neil M, "Combining evidence in risk analysis using Bayesian Networks". https://www.dcs.qmul.ac.uk/~norman/papers/Combining%20evidence%20in%20risk%20analysis%20using%20BNs.pdf Lưu trữ 2007-09-27 tại Wayback Machine
• Judea Pearl. Fusion, propagation, and structuring in belief networks. Artificial Intelligence 29(3):241–288, 1986.
• Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988, ISBN 0-934613-73-7
• J.W. Comley and D.L. Dowe, "Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages", chapter 11 Lưu trữ 2006-09-09 tại Wayback Machine (pp 265–294) in P. Grunwald, M.A. Pitt and I.J. Myung (eds)., Advances in Minimum Description Length: Theory and Applications Lưu trữ 2006-06-19 tại Wayback Machine, Cambridge, MA: MIT Press, tháng 4 năm 2005, ISBN 0-262-07262-9. (Bài báo này đưa cây quyết định vào các nút trong của mạng Bayes bằng cách sử dụng Minimum Message Length (MML). Một phiên bản cũ hơn là Comley and Dowe (2003), [1].)
• Christian Borgelt and Rudolf Kruse. Graphical Models – Methods for Data Analysis and Mining, Chichester, UK: Wiley, 2002, ISBN 0-470-84337-3
• Nevin Lianwen Zhang and David Poole, A simple approach to Bayesian network computations, Proceedings of the Tenth Biennial Canadian Artificial Intelligence Conference (AI-94), Banff, tháng 5 năm 1994, 171-178. Bài báo này trình bày việc triệt tiêu biến cho các mạng Bayes.
• David Heckerman, A Tutorial on Learning with Bayesian Networks. In Learning in Graphical Models, M. Jordan, ed.. MIT Press, Cambridge, MA, 1999. Also appears as Technical Report MSR-TR-95-06, Microsoft Research, March, 1995. An earlier version appears as Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, 1:79-119, 1997. Bài báo này viết về việc học cấu trúc và tham số trong các mạng Bayes.