Mạng Bayes
Bách khoa toàn thư mở Wikipedia
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ột mạng Bayes được biểu diễn bởi một đồ thị, trong đó các nút đại diện cho các biến, còn các cung đại diện cho các phụ thuộc có điều kiện. Phân bố xác suất có điều kiện phụ thuộc (joint probability distribution) của các biến được xác định bởi cấu trúc đồ thị của mạng. Cấu trúc đồ thị của một 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 học và suy luận hiệu quả. Các nút có thể đại diễn cho đủ loại biến, 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.
Mục lục |
[sửa] Đị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 cung biểu diễn các quan hệ phụ thuộc thống kê giữa các biến và phân bố 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 cung 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 Xi, , tập hợp các biến cha được ký hiệu bởi parents(Xi), thì phân bố có điều kiện phụ thuộc của các biến là tích của các phân bố địa phương
Nếu Xi không có cha, ta nói rằng phân bố xác suất địa phương của nó là không có điều kiện, nếu không, nó 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 nút hiển nhiên (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-separation: cho trước một số nút hiển nhiên cụ thể, các nút X và Y là d-separated trong đồ thị khi và chỉ khi các biến X và Y là độc lập, biết trước các biến hiển nhiên tương ứng. Tập hợp gồm tất cả các bút khác mà X có thể phụ thuộc trực tiếp được cho bởi Markov blanket của X.
Một ưu điểm của mạng Bayes là, về mặt trực quan, con người có thể hiểu các quan hệ phụ thuộc trực tiếp và các phân bố địa phương dễ dàng hơn là phân bố có điều kiện phụ thuộc hoàn chỉnh.
[sửa] 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):
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%.
[sửa] Mạng Bayes nhân quả
Một mạng Bayes nhân quả là một mạng Bayes mà trong đó các cung 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 cung có hướng 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ả.
[sửa] 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 họ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à thấy đượ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. Một 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. Quá trình tìm kiếm duyệt toàn bộ để 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. Một 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ư Markov chain Monte Carlo có thể tránh việc bị bẫy trong một cực tiểu địa phương.
[sửa] 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 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 số; người ta có thể dùng nguyên lý entropy cực đại để xác định một phân bố đơn, 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 (hay xác suất hậu nghiệm) thường phức tạp khi có các biến không được quan sát. 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ị mong đợi 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 hậu nghiệm cực đại) cho 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í 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.
[sửa] 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.
The most common exact inference methods are variable elimination, which eliminates (by integration or summation) the non-observed non-query variables one by one by distributing the sum over the product; clique tree propagation, which caches the computation so that many variables can be queried at one time and new evidence can be propagated quickly; and recursive conditioning, which allows for a space-time tradeoff and matches the efficiency of variable elimination when enough space is used. All of these methods have complexity that is exponential in the network's treewidth. The most common approximate inference algorithms are stochastic MCMC simulation, mini-bucket elimination which generalizes loopy belief propagation, and variational methods.
[sửa] Ứ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 chỉnh gien (gene regulatory network), trong các hệ thống y học, kỹ thuật, phân tích văn bản, xử lý ảnh, data fusion, và các hệ hỗ trợ quyết định (decision support system).
[sửa] 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)
[sửa] Liên kết và phần mềm
Tiếng Anh:
- Association for Uncertainty in Artificial Intelligence: http://www.auai.org/
- Intro to Bayesian networks : http://www.niedermayer.ca/papers/bayesian/bayes.html
- On-line Tutorial on Bayesian nets and probability: http://www.dcs.qmw.ac.uk/%7Enorman/BBNs/BBNs.htm
- AgenaRisk Bayesian network tool: http://www.agenarisk.com
- Bayesian network application library: http://www.norsys.com/netlibrary/index.htm
- Bayesia: http://www.bayesia.com
- GeNIe & SMILE: http://genie.sis.pitt.edu
- Hugin: http://www.hugin.com
- Netica: http://www.norsys.com
- BNet: http://www.cra.com/bnet
- Dezide: http://www.dezide.com
- SamIam: http://reasoning.cs.ucla.edu/samiam
- OpenBayes: http://www.openbayes.org
- MSBNx: a component-centric toolkit for modeling and inference with Bayesian Network (from Microsoft Research): http://research.microsoft.com/adapt/MSBNx/
- Bayes Net Toolbox for Matlab: http://bnt.sourceforge.net/
- dVelox: http://www.aparasw.com/sp/index.php?option=com_content&task=view&id=65&Itemid=102
- SIAM & Causeway: http://www.inet.saic.com/
[sửa] Tham khảo
- Finn V. Jensen. Bayesian Networks and Decision Graphs. Springer, 2001.
- Judea Pearl, Stuart Russell. Bayesian Networks. UCLA Cognitive Systems Laboratory, Technical Report (R-277), November 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
- 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 (pp265–294) in P. Grunwald, M.A. Pitt and I.J. Myung (eds)., Advances in Minimum Description Length: Theory and Applications, Cambridge, MA: MIT Press, April 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), .pdf.)
- 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, May 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.