Hôm nay:
- Mô hình đồ họa
- Mạng Bayes:
- Biểu diễn phân phối
- Tính độc lập có điều kiện
- Suy luận đơn giản
- Học đơn giản
Bài đọc:
- Bishop chương 8, đến 8.2
Mô hình đồ họa
- Ý tưởng chính:
- Các giả định độc lập có điều kiện hữu ích
- nhưng Naïve Bayes là cực đoan!
- Các mô hình đồ thị thể hiện các tập hợp giả định độc lập có điều kiện thông qua cấu trúc đồ thị
- Cấu trúc đồ thị cộng với các tham số liên quan xác định phân phối xác suất đồng thời trên tập hợp các biến
- Hai loại mô hình đồ họa:
- Đồ thị có hướng (còn gọi là Mạng Bayes) ← 10-601
- Đồ thị vô hướng (còn gọi là Trường ngẫu nhiên Markov)
Mô hình đồ họa – Tại sao phải quan tâm?
- Trong số những phát triển ML quan trọng nhất của thập kỷ
- Các mô hình đồ họa cho phép kết hợp:
- Kiến thức có sẵn ở dạng phụ thuộc/độc lập
- Kiến thức có sẵn ở dạng ưu tiên hơn các tham số
- Dữ liệu đào tạo được quan sát
- Nguyên lý và những phương pháp chung cho
- Suy luận xác suất
- Học tập
- Hữu ích trong thực tế
- Chẩn đoán, hệ thống trợ giúp, phân tích văn bản, mô hình chuỗi thời gian, …
Tính độc lập có điều kiện
Định nghĩa: X độc lập có điều kiện với Y cho trước Z, nếu phân phối xác suất chi phối X không phụ thuộc vào giá trị của Y, cho trước giá trị của Z 
Độc lập biên
Định nghĩa: X độc lập biên với Y nếu 
Biểu diễn Phân phối xác suất đồng thời trên các biến
Mô tả mạng lưới các phụ thuộc
Bayes Nets xác định Phân phối xác suất đồng thời theo biểu đồ này, cộng với các tham số
Lợi ích của Bayes Nets:
- Biểu thị phân phối đồng thời đầy đủ với ít tham số hơn, sử dụng kiến thức trước đây về các phụ thuộc
- Các thuật toán để suy luận và học tập
Mạng Bayesian Định nghĩa
Mạng Bayes biểu thị phân phối xác suất đồng thời trên một tập hợp các biến ngẫu nhiên
Mạng Bayes là một đồ thị không tuần hoàn có hướng và một tập hợp các phân phối xác suất có điều kiện (CPD’s)
- Mỗi nút biểu thị một biến ngẫu nhiên
- Các cạnh biểu thị các phụ thuộc
- Đối với mỗi nút Xi, CPD của nó xác định P(Xi | Pa(Xi))
- Phân phối đồng thời trên tất cả các biến được định nghĩa là
Pa(X) = cha mẹ trực tiếp của X trong biểu đồ
Bayesian Network
Nodes = các biến ngẫu nhiên
Phân phối xác suất có điều kiện (CPD) được liên kết với mỗi nút N, xác định P(N | Parents(N))
Phân phối đồng thời trên tất cả các biến:
Bayesian Network
Chúng ta có thể nói gì về tính độc lập có điều kiện trong Bayes Net?
Một điều là thế này:
Mỗi nút độc lập có điều kiện với các nút không phải là con cháu của nó, chỉ được cung cấp các nút cha trực tiếp của nó.
Một số thuật ngữ hữu ích
Cha mẹ = Pa(X) = cha mẹ trực tiếp
Tiền đề = cha mẹ, cha mẹ của cha mẹ, …
Con cái = con cái trực tiếp
Con cháu = con cái, con cái của con cái, …
Mạng Bayesian
- CPD cho mỗi nút Xi mô tả P(Xi | Pa(Xi))
Quy tắc xác suất dây chuyền nói rằng nói chung:
Nhưng trong lưới Bayes:
Có bao nhiêu thông số?
Để xác định phân phối đồng thời nói chung?
Để xác định phân phối đồng thời cho Bayes Net này?
Suy luận trong Bayes Nets
P(S=1, L=0, R=1, T=0, W=1) =
Học trên Bayes Net
Xem xét việc học khi cấu trúc biểu đồ được cung cấp và dữ liệu = { <s,l,r,t,w> }
Giải pháp MLE là gì? MAP?
Thuật toán xây dựng mạng Bayes
- Chọn thứ tự cho các biến, ví dụ: X1, X2, … Xn
- Với i=1 đến n
Lưu ý sự lựa chọn này của cha mẹ đảm bảo
(theo quy tắc dây chuyền)
(theo cấu trúc)
Ví dụ
- Cúm gia cầm và Allegies đều gây ra các vấn đề về Mũi
- Các vấn đề về mũi gây ra Hắt hơi và Nhức đầu
Mạng Bayes cho X1,…X4 là gì mà KHÔNG có tính độc lập có điều kiện giả định?
Mạng Bayes cho Naïve Bayes là gì?
Chúng ta phải làm gì nếu các biến là hỗn hợp của giá trị rời rạc và giá trị thực?
Mạng Bayes cho Mô hình Markov ẩn
Ngụ ý rằng tương lai độc lập với quá khứ một cách có điều kiện, với điều kiện hiện tại
Trạng thái không quan sát: S
Đầu ra đã quan sát: O
Những gì bạn nên biết
- Lưới Bayes là biểu diễn thuận tiện cho việc mã hóa các phụ thuộc/độc lập có điều kiện
- BN = Đồ thị cộng với các tham số của CPD’s
- Xác định phân phối đồng thời trên các biến
- Có thể tính toán mọi thứ khác từ đó
- Mặc dù có thể khó suy luận
- Đọc các quan hệ độc lập có điều kiện từ đồ thị
- Mỗi nút không phụ thuộc vào những nút không phải là con cháu, với điều kiện cho trước cha mẹ của nó
- ‘Giải thích đi’
Xem ứng dụng Bayes Net: http://www.cs.cmu.edu/~javabayes/Home/applet.html
Suy luận trong Bayes Nets
- Nói chung, khó kiểm soát (NP-đầy đủ)
- Đối với một số trường hợp nhất định, dễ kiểm soát
- Gán xác suất cho tập hợp các biến được quan sát đầy đủ
- Hoặc nếu chỉ một biến không được quan sát
- Hoặc cho các đồ thị được kết nối đơn lẻ (nghĩa là không có vòng lặp vô hướng)
- Lan truyền niềm tin
- Đối với các đồ thị được kết nối nhân
- Cây nối
- Đôi khi sử dụng phương pháp Monte Carlo
- Tạo nhiều mẫu theo phân phối Bayes Net, sau đó đếm kết quả
- Các phương pháp biến đổi cho các giải pháp gần đúng có thể xử lý được
Ví dụ
- Cúm gia cầm và Allegies đều gây ra các vấn đề về Xoang
- Các bệnh về xoang gây Nhức Đầu, Sổ Mũi
Xác suất nhiệm vụ chung: dễ dàng
- Giả sử chúng ta quan tâm đến nhiệm vụ chung <F=f,A=a,S=s,H=h,N=n>
P(f,a,s,h,n) là gì?
hãy sử dụng p(a,b) làm cách viết tắt của p(A=a, B=b)
Xác suất cận biên: không dễ
- Làm cách nào để tính P(N=n) ?
hãy sử dụng p(a,b) làm tốc ký cho p(A=a, B=b)
Tạo mẫu từ phân phối đồng thời: dễ dàng
Làm thế nào chúng ta có thể tạo mẫu ngẫu nhiên được rút ra theo P(F,A,S,H,N)?
hãy sử dụng p(a,b) làm tốc ký cho p(A=a, B=b)
Tạo mẫu từ phân phối đồng thời: dễ dàng
Lưu ý rằng chúng ta có thể ước tính các biên như P(N=n) bằng cách tạo nhiều mẫu từ phân phối đồng thời, sau đó đếm tỷ lệ mẫu mà N=n
Tương tự, đối với bất kỳ điều gì khác, chúng ta quan tâm đến P(F=1|H=1, N=0)
→ phương pháp chung nhưng yếu để ước tính bất kỳ số hạng xác suất nào…
hãy sử dụng p(a,b) làm cách viết tắt cho p(A=a, B=b)
Xác suất của các biên: không dễ dàng lắm
Nhưng đôi khi cấu trúc của mạng cho phép chúng ta khéo léo → tránh làm việc theo cấp số nhân
ví dụ: chuỗi
Suy luận trong Bayes Nets
- Nói chung, khó kiểm soát (NP-đầy đủ)
- Đối với một số trường hợp nhất định, có thể kiểm soát được
- Chỉ định xác suất cho tập hợp các biến được quan sát đầy đủ
- Hoặc nếu chỉ một biến không được quan sát
- Hoặc cho các biểu đồ được kết nối đơn lẻ (ví dụ: , không có vòng lặp vô hướng)
- Loại bỏ biến
- Lan truyền niềm tin
- Đối với đồ thị liên thông nhân
- Cây nối
- Đôi khi sử dụng phương pháp Monte Carlo
- Tạo nhiều mẫu theo phân phối Bayes Net, sau đó đếm kết quả
- Phương pháp biến thiên cho các giải pháp gần đúng có thể xử lý