Graphical model (2)

Trong bài trước, ta đã điểm qua khái niệm về graphical model. Bài này sẽ viết về một thuật toán quan trọng là Bayes Ball, sau đó nói về các khái niệm Cái mền của Markov (Markov blanket), Markov equivalent, faithfulness… của graphical model. Bài tiếp theo của loạt này hi vọng sẽ nói về một số thuật toán suy diễn trong graphical model, bao gồm Message passing và Junction tree.

(FYI: Lớp Probabilistic Graphical Models của Stanford sắp khai trương, ngoài ra lớp Computer Vision cũng có vẻ thú vị).

1. Thuật toán Bayes ball

Cho graphical model bất kì. Một câu hỏi quan trọng là: cho biết giá trị của tập biến ngẫu nhiên Z, xác định xem hai biến ngẫu nhiên A và B là độc lập hay phụ thuộc. Nói cách khác, ta muốn xác định A \perp B \vert Z hay A\not\perp B \vert Z, nghĩa là xác định sự độc lập/phụ thuộc có điều kiện giữa 2 biến ngẫu nhiên bất kì. Đây chính là mục tiêu của thuật toán  Bayes Ball.

Tư tưởng của  Bayes ball rất đơn giản. Ta đánh dấu (shade) các biến ngẫu nhiên trong Z, với hàm ý là những biến này đã biết. Sau đó “thả” quả bóng Bayes ball từ A. Bayes ball di chuyển trong đồ thị theo một số quy tắc nhất định. Nếu Bayes ball có thể đi từ A đến B thì A và B là phụ thuộc với điều kiện Z. Mặc dù các cạnh trong graphical model là có hướng (đồ thị này là directed acyclic graph – DAG) nhưng Bayes ball có thể di chuyển ngược hướng với các cạnh.

Bayes ball di chuyển trong DAG theo 10 quy tắc được tóm tắt trong hình sau:

10 quy tắc của thuật toán Bayes Ball

Thực ra ý tưởng là rất đơn giản. Từ trái qua ta có 5 trường hợp: cấu trúc serial, divergence, convergence, và các node lá trong đồ thị. Đây là tất cả các trường hợp có thể gặp trong một DAG. Theo đó đối với cấu trúc serial và divergence, nếu biến trung gian là chưa biết thì 2 biến A và B phụ thuộc, do đó Bayes Ball có thể chạy qua. Tuy nhiên nếu biến trung gian đã biết (tô xám trong hình) thì A và B độc lập, nên Bayes Ball bị chặn lại. Tình huống tương tự đối với cấu trúc convergence, nếu biến trung gian là không biết thì Bayes ball bị chặn (độc lập), nhưng nếu biến trung gian là đã biết thì Bayes ball có thể vượt qua. Trường hợp thứ 4 dành cho biến nằm ở node lá của DAG. Nếu biến này đã biết thì Bayes ball có thể quay ngược lại theo đường cũ. Tương tự cho trường hợp thứ 5.

Nói chung trong DAG có thể có nhiều đường đi từ A đến B, và chỉ cần có một đường đi không bị chặn thì A và B là phụ thuộc.

Mô tả nôm na này đã diễn tả đầy đủ thuật toán Bayes Ball. Phiên bản “đàng hoàng” hơn của thuật toán thực ra được trình bày trong một paper kinh điển của  Shachter năm 1998.

Như vậy bằng thuât toán Bayes Ball, ta có thể trả lời mọi câu hỏi về tính độc lập hay phụ thuộc có điều kiện của 2 biến ngẫu nhiên bất kì trong một DAG. Tuy nhiên nếu liệt kê tất cả các trường hợp có thể của  Z thì sẽ quá nhiều trường hợp, do đó để xét mối quan hệ của 2 biến  A và B trong DAG, ta thường làm như sau:

  • Không cho trước gì cả, A và B là độc lập (hay phụ thuộc)?
  • Xác định tập biến ngẫu nhiên nhỏ nhất trong các biến còn lại của  DAG sao cho A và B là phụ thuộc (hay độc lập).

Bằng cách này, cho một  DAG, ta có thể “đọc” ra danh sách các mối độc lập/phụ thuộc giữa các biến ngẫu nhiên. Ý tưởng là thay vì viết hàng chục, hàng trăm biểu thức kiểu như A\perp B, A\not\perp B\vert CD, A\perp C\vert B\dots ta có thể biểu diễn chúng một cách ngắn gọn bằng cách dùng DAG.

Ví dụ Graphical model

Chẳng hạn với ví dụ quen thuộc trên, chỉ bằng cách nhìn vào phần “graphical” (bỏ qua các bảng xác suất), ta có thể đọc ra các mối quan hệ sau:

A \not\perp B, A \not\perp CA \perp C\vert B, A \not\perp D, A \perp D\vert B, A \perp E, A \not\perp E\vert B

B \not\perp C, B \not\perp D, B \not\perp E

C \not\perp D, C \perp D\vert B, C \not\perp E, C \perp D \vert B

D \not\perp E, D \perp E \vert B

Rõ ràng việc liệt kê như trên là không khả thi khi có nhiều biến, và DAG đã giúp ta biểu diễn một cách ngắn gọn hơn nhiều.

2. Markov blanket, Markov equivalent và Faithfulness

Những khái niệm này được trình bày chủ yếu là để cho đầy đủ 1 bài introduction về graphical model.

2.1. Cái mền của  Markov

Markov blanket M của một node C trong graphical model là tập các node “che phủ” C khỏi tất cả các biến còn lại trong mô hình. Vì lí do này nên M mới gọi là “cái mền Markov”.

Nói cách khác, C là độc lập đối với các biến R còn lại của mô hình, cho trước M: C\perp R\vert M.

Trong DAG, Markov blanket của  C = tập các node cha, con và anh em của C.

Ví dụ Markov Blanket

Chẳng hạn trong ví dụ trên thì Markov blanket của C là tập M=\left\{ X_4, X_5, X_6,X_7,X_8,X_9\right\}, và ta có:

C\perp R\vert M, \forall R \subseteq \left\{ X_1, X_2, X_3,X_{10},X_{11},X_{12}\right\}

\mathbb{P}\left(C\vert X_1\dots X_{12}\right) = \mathbb{P}\left(C\vert M\right)

2.2. Markov equivalence

Hai DAG B1 và B2 gọi là tương đương  Markov nếu và chỉ nếu chúng cùng biểu diễn một tập biểu thức độc lập/phụ thuộc có điều kiện. B1 và B2 khi đó phải có cùng skeleton (tập đỉnh và tập cạnh vô hướng), cùng V-structure và có cùng inferred edge.

Inferred edge trong DAG là các cạnh có hướng mà nếu ta đảo ngược hướng của chúng thì sẽ tạo ra/mất đi một V-structure.

Các DAG tương đương Markov với nhau (cùng một lớp tương đương) có thể biểu diễn chung thành một đồ thị gọi là Partially directed DAG (CPDAG) hay Essential graph.

2.3. Khác

Ta đã thấy từ một DAG có thể đọc ra được danh sách các mối độc lập/phụ thuộc (có điều kiện) giữa các biến ngẫu nhiên. Ngoài ra từ các bảng phân phối xác suất ta cũng có thể đọc ra được mối quan hệ này. Do đó một đồ thị G và các bảng xác suất P gọi là faithful với nhau nếu chúng cùng biểu diễn chung một tập các mối độc lập/phụ thuộc (có điều kiện) giữa các biến ngẫu nhiên.

Ta đã thấy Probabilistic graphical model chỉ là một cách biểu diễn ngắn gọn của phân bố xác suất đồng thời \mathbb{P}\left(S\right). Do đó ta hoàn toàn có thể lấy mẫu (sampling) từ phân phối này bằng các kĩ thuật lấy mẫu kinh điển trong XSTK. Ý tưởng là ta lấy mẫu các biến là node cha trong mô hình, sau đó lấy mẫu các biến là các node con. Cứ như vậy ta coi như lấy mẫu từ phân bố \mathbb{P}\left(S\right). Ý tưởng này gọi là Graphical model as a generative model.

3. Kết luận

Bài này nói về thuật toán Bayes Ball. Các khái niệm khác cũng được đề cập. Bài tiếp theo (nếu có) sẽ nói về suy diễn trong graphical model.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s