Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Mô hình đồ thị xác suất

Probabilistic Graphical Models

Nâng caokhoảng 46 giờ6 bước

Mô hình đồ họa xác suất: biểu diễn mối quan hệ phụ thuộc giữa các biến ngẫu nhiên bằng đồ thị.

Bắt đầu học

Bạn sẽ học được gì

  • Phân biệt mô hình đồ họa có hướng (mạng Bayes) và vô hướng (mạng Markov)
  • Biểu diễn một phân phối xác suất nhiều biến bằng cấu trúc đồ thị và các yếu tố (factor)
  • Cài đặt suy luận chính xác bằng thuật toán loại biến (variable elimination) trên mạng nhỏ
  • Áp dụng suy luận xấp xỉ (lấy mẫu MCMC, suy luận biến phân) khi suy luận chính xác không khả thi
  • Học tham số mô hình đồ họa từ dữ liệu quan sát được bằng maximum likelihood và thuật toán EM
  • Xây dựng một mô hình đồ họa xác suất hoàn chỉnh cho một bài toán thực tế

Nên học trước

Giới thiệu

Mô hình đồ họa xác suất (probabilistic graphical models – PGM) dùng đồ thị để biểu diễn gọn phân phối xác suất trên nhiều biến ngẫu nhiên phụ thuộc lẫn nhau. Thay vì viết một bảng xác suất khổng lồ, ta chỉ cần vẽ mối quan hệ trực tiếp giữa các biến — phần còn lại (độc lập có điều kiện) suy ra được từ cấu trúc đồ thị.

Hai họ mô hình

  • Mạng Bayes (directed): đồ thị có hướng không chu trình; mỗi nút có một phân phối xác suất có điều kiện theo cha của nó. Trực quan để mô hình hóa quan hệ nhân quả (bệnh → triệu chứng).
  • Mạng Markov / MRF (undirected): đồ thị vô hướng, mỗi nhóm nút liên thông (clique) gắn một hàm thế năng không cần chuẩn hóa thành xác suất ngay. Phù hợp khi quan hệ đối xứng, không có chiều nhân quả rõ ràng (như trong ảnh, văn bản).

Cấu trúc đồ thị quyết định trực tiếp những biến nào độc lập với nhau khi biết các biến khác — đọc được bằng quy tắc d-separation (mạng Bayes) hoặc tách đồ thị (mạng Markov).

Bài toán suy luận: biết một phần, hỏi phần còn lại

Cho biết giá trị một số biến (bằng chứng), suy luận là tính phân phối xác suất của các biến còn lại. Với mạng nhỏ, variable elimination tính chính xác bằng cách loại từng biến theo thứ tự hợp lý. Với mạng lớn, bài toán suy luận chính xác là NP-khó, buộc phải dùng phương pháp xấp xỉ: lấy mẫu (Gibbs sampling, MCMC) hoặc suy luận biến phân (variational inference) — đánh đổi độ chính xác lấy tốc độ.

Học mô hình từ dữ liệu

Khi biết cấu trúc đồ thị, học tham số bằng maximum likelihood (đơn giản nếu dữ liệu đầy đủ, cần EM nếu có biến ẩn). Học cả cấu trúc đồ thị từ dữ liệu khó hơn nhiều và ít khi có lời giải đóng.

Công cụ nên dùng

pgmpy (Python) để dựng và suy luận trên mạng Bayes nhỏ; tự cài variable elimination một lần bằng tay trước khi dùng thư viện, để thật sự hiểu thuật toán đang làm gì.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Có phíNâng caoTiếng Anh1.231 trang

Vì sao chọn: Sách giáo khoa toàn diện và chi tiết nhất về PGM, dùng trong hầu hết khóa PGM sau đại học (như Stanford CS228). Không có bản đọc miễn phí hợp pháp và khá dày (hơn 1200 trang) nhưng là tài liệu tham khảo chuẩn nên dùng làm sách chính, đọc theo từng bước thay vì đọc tuần tự hết sách.

Nên đọc: Phần I: Representation (mạng Bayes, mạng Markov); Phần II: Inference; Phần III: Learning

CC BY-NC-NDNâng caoTiếng Anh1.360 trang

Miễn phí, trình bày PGM cô đọng hơn Koller & Friedman và đặt trong bối cảnh học máy hiện đại (kết hợp với deep learning). Dùng làm bản tóm tắt dễ đọc trước khi vào sâu từng phần của sách chính.

Nên đọc: chương về mô hình đồ họa xác suất và các phương pháp suy luận

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Biểu diễn: mạng Bayes

    khoảng 7 giờ

    Đồ thị có hướng không chu trình, phân phối có điều kiện tại mỗi nút, quy tắc chuỗi phân rã phân phối chung; d-separation để đọc tính độc lập có điều kiện. Bài tập: tự vẽ một mạng Bayes 5–6 nút cho một tình huống quen thuộc (vd. báo động trộm, thời tiết và tưới cây) và viết phân phối chung dưới dạng tích các phân phối có điều kiện.

  2. Bước 2: Biểu diễn: mạng Markov và factor

    khoảng 7 giờ

    Đồ thị vô hướng, clique, hàm thế năng, hằng số chuẩn hóa (partition function); so sánh khi nào nên dùng mạng Markov thay vì mạng Bayes. Bài tập: biểu diễn một bài toán phân đoạn ảnh nhỏ (lưới 4x4 pixel nhị phân) bằng mạng Markov với factor phạt hai pixel liền kề khác nhãn.

  3. Bước 3: Suy luận chính xác: variable elimination

    khoảng 8 giờ

    Thuật toán loại biến: nhân factor, lấy tổng theo biến bị loại, ảnh hưởng của thứ tự loại biến tới độ phức tạp tính toán. Bài tập: tự cài variable elimination bằng Python cho mạng Bayes ở bước 1, tính vài truy vấn xác suất có điều kiện và đối chiếu bằng tay.

  4. Bước 4: Suy luận xấp xỉ: lấy mẫu và biến phân

    khoảng 8 giờ

    Gibbs sampling và MCMC để lấy mẫu từ phân phối hậu nghiệm; ý tưởng cơ bản của suy luận biến phân. Bài tập: cài Gibbs sampling cho mạng Markov ở bước 2, so sánh xác suất ước lượng bằng lấy mẫu với kết quả variable elimination trên một mạng đủ nhỏ để tính chính xác.

  5. Bước 5: Học tham số và cấu trúc từ dữ liệu

    khoảng 8 giờ

    Maximum likelihood khi dữ liệu đầy đủ; thuật toán EM khi có biến ẩn; giới thiệu bài toán học cấu trúc đồ thị. Bài tập: sinh dữ liệu giả từ mạng Bayes ở bước 1 (với một biến bị che giấu), rồi dùng EM để ước lượng lại tham số và so sánh với tham số gốc.

  6. Bước 6: Dự án: mô hình đồ họa xác suất cho bài toán thực tế

    khoảng 8 giờ

    Ghép toàn bộ quy trình — chọn cấu trúc mô hình, học tham số từ dữ liệu, suy luận trả lời truy vấn thực tế. Bài tập lớn: xây một mô hình đồ họa hoàn chỉnh bằng pgmpy cho một bài toán tự chọn (vd. chẩn đoán đơn giản từ triệu chứng, hoặc gán nhãn chuỗi bằng HMM), viết báo cáo ngắn giải thích cấu trúc đồ thị đã chọn và kết quả suy luận.

Khái niệm chính

Mạng Bayes (Bayesian network)
Đồ thị có hướng không chu trình biểu diễn phân phối xác suất chung; mỗi nút gắn một phân phối có điều kiện theo các nút cha của nó, tích các phân phối này lại cho phân phối chung.
Mạng Markov (Markov random field)
Mô hình đồ họa vô hướng; phân phối chung là tích các hàm thế năng (potential function) trên từng clique của đồ thị, chia cho hằng số chuẩn hóa (partition function).
Yếu tố (factor)
Hàm không âm trên một tập con các biến, dùng làm khối xây dựng chung cho cả mạng Bayes (phân phối có điều kiện) lẫn mạng Markov (hàm thế năng).
Độc lập có điều kiện và d-separation
Hai biến độc lập có điều kiện khi biết một tập biến thứ ba nếu mọi đường nối giữa chúng trên đồ thị đều bị 'chặn'; d-separation là quy tắc đọc trực tiếp tính độc lập này từ cấu trúc mạng Bayes.
Variable elimination
Thuật toán suy luận chính xác: lần lượt loại bỏ từng biến không cần thiết bằng cách nhân các factor liên quan rồi lấy tổng (marginalize) trên biến đó, theo một thứ tự loại biến được chọn trước.
Suy luận xấp xỉ: MCMC và biến phân
MCMC (như Gibbs sampling) tạo mẫu từ phân phối hậu nghiệm khi không tính được chính xác; suy luận biến phân thay bài toán suy luận bằng bài toán tối ưu, tìm phân phối đơn giản gần đúng phân phối thật nhất.
Thuật toán EM (Expectation-Maximization)
Thuật toán lặp học tham số khi dữ liệu có biến ẩn: bước E ước lượng phân phối biến ẩn theo tham số hiện tại, bước M cập nhật tham số để tối đa hóa khả năng (likelihood) kỳ vọng.
Mô hình Markov ẩn (HMM) và CRF
Hai mô hình đồ họa quan trọng cho dữ liệu chuỗi: HMM (có hướng) mô hình chuỗi trạng thái ẩn sinh ra quan sát; CRF (vô hướng) mô hình trực tiếp phân phối nhãn có điều kiện theo quan sát, thường cho kết quả tốt hơn HMM trong gán nhãn chuỗi.

Học xong để làm gì

  • Hỗ trợ chẩn đoán y tế: suy luận xác suất bệnh từ triệu chứng và kết quả xét nghiệm quan sát được
  • Gán nhãn chuỗi trong xử lý ngôn ngữ tự nhiên (gán từ loại, nhận diện thực thể) bằng HMM/CRF
  • Phân đoạn ảnh (image segmentation) bằng mạng Markov trên các pixel lân cận
  • Hệ gợi ý và phát hiện gian lận trên mạng lưới quan hệ giữa người dùng/giao dịch
  • Định vị và lập bản đồ đồng thời (SLAM) trong robot bằng mô hình đồ họa theo thời gian

Câu hỏi thường gặp

PGM khác gì so với mạng nơ-ron sâu?

Mạng nơ-ron học một hàm ánh xạ đầu vào–đầu ra mạnh nhưng khó diễn giải. PGM biểu diễn tường minh cấu trúc phụ thuộc giữa các biến, cho phép hỏi bất kỳ biến nào khi biết bất kỳ tập bằng chứng nào, và dễ đưa tri thức chuyên gia vào cấu trúc đồ thị — đánh đổi lấy việc thường khó mở rộng bằng deep learning trên dữ liệu phi cấu trúc rất lớn.

Có bắt buộc phải giỏi lý thuyết đồ thị không?

Cần hiểu các khái niệm cơ bản (đồ thị có hướng/vô hướng, đường đi, chu trình, cây) — đủ dùng ở mức môn Toán rời rạc cho khoa học máy tính. Không cần thuật toán đồ thị nâng cao.

Nên học mạng Bayes hay mạng Markov trước?

Học mạng Bayes trước vì trực quan hơn (quan hệ nhân quả, dễ diễn giải), và nhiều khái niệm suy luận (variable elimination, factor) học ở mạng Bayes chuyển sang mạng Markov gần như nguyên vẹn.

Suy luận xấp xỉ có đáng tin cậy không?

Có, khi dùng đúng cách và đủ mẫu/vòng lặp, nhưng luôn có sai số và cần kiểm tra hội tụ (với MCMC) hoặc theo dõi cận dưới của likelihood (với suy luận biến phân). Với mạng nhỏ, luôn đối chiếu kết quả xấp xỉ với suy luận chính xác trước khi tin tưởng.

Chọn nguồn tự học

Cần nền tảng xác suất thống kê và lý thuyết đồ thị vững trước khi học.