Bayesian Network

Joint distribution chứa rất nhiều thông tin, nhưng có một vấn đề lớn: khi số random variables tăng, số tổ hợp tăng rất nhanh.

Nếu có $n$ biến nhị phân, số full assignments có thể là:

2^n

Với 30 biến:

2^{30}>10^{9}

tức hơn 1 tỷ. Lưu một bảng xác suất đầy đủ cho mọi tổ hợp nhanh chóng trở nên bất tiện.

Bayesian Network - mạng Bayes giải quyết vấn đề bằng cách biểu diễn các quan hệ phụ thuộc có cấu trúc.

Mục tiêu

Sau bài này, bạn cần:

hiểu Bayesian Network là gì;
đọc được node, edge, parent và child;
hiểu vì sao mạng phải là directed acyclic graph - DAG;
đọc được Conditional Probability Table - CPT;
tính xác suất của một full assignment bằng factorization;
hiểu local dependency và conditional independence;
phân biệt dependency trong mạng với khẳng định nhân quả tuyệt đối.

Ý tưởng: không phải biến nào cũng phụ thuộc trực tiếp vào mọi biến khác

Xét bài toán sinh viên có đến lớp muộn hay không.

Ta mô hình hóa bốn biến:

Rain       : có mưa hay không
Traffic    : đường có ùn tắc hay không
BusLate    : xe buýt có trễ hay không
Late       : sinh viên có đến lớp muộn hay không

Một mô hình đơn giản có thể là:

Ý nghĩa của mũi tên là:

Probability distribution của node con phụ thuộc trực tiếp vào node cha.

Trong mô hình đồ chơi này:

Traffic phụ thuộc vào Rain;
BusLate phụ thuộc vào Rain;
Late phụ thuộc vào Traffic và BusLate.

Đây là mô hình minh họa, không phải khẳng định rằng mưa là nguyên nhân duy nhất của ùn tắc hay xe buýt trễ.

Bayesian Network là gì?

Một Bayesian Network có ba thành phần chính:

một directed acyclic graph - DAG;
mỗi node là một random variable;
mỗi node có một probability distribution phụ thuộc vào các parent của nó.

Với node $X$ :

P(X\mid Parents(X))

Nếu $X$ không có parent, nó có prior distribution:

P(X)

Directed Acyclic Graph - DAG

Directed: cạnh có hướng.
Acyclic: không có đường đi theo hướng các mũi tên rồi quay lại node ban đầu.

Một chu trình kiểu:

A -> B -> C -> A

không hợp lệ với Bayesian Network chuẩn.

Lý do trực quan: khi xác định distribution của một node từ parent, ta cần có một thứ tự phụ thuộc rõ ràng. Chu trình sẽ làm các định nghĩa phụ thuộc lẫn nhau theo vòng.

Hình công khai: một Bayesian Network đơn giản

Ví dụ một Bayesian Network đơn giản

Hình: một Bayesian Network đơn giản. Nguồn: Wikimedia Commons, tác giả AnAj, public domain.

Hình trên là một mạng ví dụ phổ biến. Điểm cần nhìn là cấu trúc DAG: node được nối bằng các mũi tên để chỉ dependency trực tiếp, thay vì tạo một bảng joint khổng lồ.

Conditional Probability Table - CPT

Mỗi node cần biết probability distribution của nó với từng tổ hợp giá trị của parent.

Ta dùng ví dụ đi học muộn.

Node Rain

Rain không có parent:

`Rain`	Xác suất
`True`	0.30
`False`	0.70

Node Traffic phụ thuộc Rain

`Rain`	`Traffic=True`	`Traffic=False`
`True`	0.70	0.30
`False`	0.25	0.75

Ví dụ:

P(Traffic=True\mid Rain=True)=0.70

Node BusLate phụ thuộc Rain

`Rain`	`BusLate=True`	`BusLate=False`
`True`	0.50	0.50
`False`	0.15	0.85

Node Late phụ thuộc Traffic và BusLate

`Traffic`	`BusLate`	`Late=True`	`Late=False`
True	True	0.95	0.05
True	False	0.70	0.30
False	True	0.80	0.20
False	False	0.10	0.90

Ví dụ:

P(Late=True\mid Traffic=True,BusLate=False)=0.70

Vì sao CPT giúp giảm độ phức tạp?

Nếu Late phải phụ thuộc trực tiếp vào mọi biến trong một hệ thống lớn, CPT của nó sẽ rất to.

Bayesian Network cố gắng chỉ giữ các dependency trực tiếp cần thiết.

Trong ví dụ:

không có cạnh Rain -> Late.

Điều này biểu diễn giả định:

Khi đã biết Traffic và BusLate, thông tin Rain không còn trực tiếp thay đổi distribution của Late trong mô hình này.

Đây là một dạng conditional independence.

Factorization - Tách joint probability thành các phần nhỏ

Với mạng:

Rain -> Traffic
Rain -> BusLate
Traffic, BusLate -> Late

joint probability có thể tách thành:

P(R,T,B,L) =P(R)P(T\mid R)P(B\mid R)P(L\mid T,B)

Đây là công thức cốt lõi của Bayesian Network.

Dạng tổng quát:

P(X_1,\ldots,X_n) =\prod_i P(X_i\mid Parents(X_i))

Ta không cần lưu trực tiếp một bảng joint cho mọi tổ hợp. Thay vào đó, ta lưu các local distributions.

Tính xác suất một full assignment

Giả sử muốn tính xác suất của tình huống:

Rain=True
Traffic=True
BusLate=False
Late=True

Ta lấy từng số từ CPT:

P(R=True)=0.30

P(T=True\mid R=True)=0.70

P(B=False\mid R=True)=0.50

P(L=True\mid T=True,B=False)=0.70

Do đó:

P(R,T,\neg B,L) =(0.30)(0.70)(0.50)(0.70)

=0.0735

Tức 7.35% theo mô hình giả định.

Parent chỉ biểu diễn dependency trực tiếp

Xét:

Rain có thể liên quan tới Late qua Traffic, dù không có cạnh trực tiếp Rain -> Late.

Do đó:

Không có edge không đồng nghĩa hai biến hoàn toàn không liên quan.

Điều quan trọng là cấu trúc mạng nói về dependency có điều kiện.

Bayesian Network có phải causal graph không?

Không tự động.

Một edge:

X -> Y

trong Bayesian Network trước hết nói rằng distribution của $Y$ được biểu diễn phụ thuộc vào $X$ trong factorization.

Đôi khi người thiết kế mạng có ý định causal. Nhưng chỉ nhìn một Bayesian Network xác suất không đủ để kết luận quan hệ nhân quả.

Để suy luận nhân quả cần thêm giả định và phương pháp causal inference riêng.

Ví dụ IT: chẩn đoán Wi-Fi

Ta có thể xây một mạng toy khác:

CrowdedNetwork -> HighLatency
RouterProblem   -> HighLatency
HighLatency     -> VideoBuffering

Nếu quan sát VideoBuffering=True, ta có thể muốn suy ngược:

P(HighLatency | VideoBuffering=True)
P(RouterProblem | VideoBuffering=True)

Đây chính là inference trên Bayesian Network, nội dung của bài tiếp theo.

Cách thiết kế một Bayesian Network nhỏ

Khi mô hình hóa một bài toán, có thể đi theo các bước:

Với bài học, CPT có thể do đề bài cung cấp. Trong hệ thống thực tế, các xác suất có thể đến từ dữ liệu, chuyên gia hoặc quá trình học tham số.

Những lỗi thường gặp

Nối mọi biến với mọi biến

Làm như vậy mất lợi ích của Bayesian Network. Mục tiêu chính là tận dụng cấu trúc dependency.

Nhầm parent với “xảy ra trước”

Parent không đơn giản chỉ là biến xuất hiện trước trong câu chuyện. Nó phải có ý nghĩa trong cách ta factorize distribution.

Nghĩ không có edge nghĩa là độc lập tuyệt đối

Conditional independence phụ thuộc vào những biến đã biết.

Nghĩ edge luôn chứng minh nhân quả

Bayesian Network không tự chứng minh causality.

Tự kiểm tra

Cho mạng:

Câu 1

Parents của D là gì?

Đáp án

B và C.

Câu 2

Joint probability factorize thế nào?

Đáp án

P(A,B,C,D)=P(A)P(B\mid A)P(C\mid A)P(D\mid B,C)

Câu 3

Nếu biết B và C, CPT của D có cần thêm A làm parent không?

Đáp án

Theo đúng cấu trúc mạng đã cho thì không. Distribution của D được định nghĩa bằng $P(D\mid B,C)$ .

Tóm tắt

Bayesian Network là DAG của các random variables.
Edge biểu diễn dependency trực tiếp trong mô hình.
Mỗi node có $P(X\mid Parents(X))$ .
CPT lưu distribution của node theo từng tổ hợp parent.
Joint distribution được factorize thành tích của các local distributions.
Cấu trúc mạng giúp giảm việc phải lưu một joint table quá lớn.
Edge xác suất không tự động là bằng chứng nhân quả.

Tài liệu tham khảo

Bản tiếng Anh đang soạn.