Suy luận xác suất và Sampling

Có Bayesian Network rồi, câu hỏi tiếp theo là:

Khi đã quan sát một số biến, làm sao tính xác suất của biến chưa biết?

Ví dụ với mạng đi học muộn:

Nếu ta biết hôm nay Late=True, có thể muốn hỏi:

Đó là probabilistic inference - suy luận xác suất.

Mục tiêu

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

• xác định query, evidence và hidden variables;
• hiểu inference by enumeration;
• phân biệt exact inference và approximate inference;
• hiểu sampling trong mô hình xác suất;
• hiểu rejection sampling;
• hiểu vì sao rejection sampling kém hiệu quả khi evidence hiếm;
• hiểu ý tưởng likelihood weighting.

Ba nhóm biến khi inference

Query variable

Biến ta muốn hỏi.

Ví dụ:

Rain

khi cần tính:

Evidence variables

Biến đã quan sát giá trị.

Ví dụ:

Late=True

Hidden variables

Các biến còn lại chưa được quan sát và không phải query.

Trong ví dụ:

Traffic
BusLate

Inference by Enumeration - Liệt kê các khả năng ẩn

Ta muốn:

Nhưng còn các hidden variables $Y$ chưa biết.

Ý tưởng enumeration là:

1. liệt kê mọi giá trị có thể của $Y$;
2. tính joint probability cho từng trường hợp;
3. cộng các trường hợp lại;
4. normalize để tổng bằng 1.

Dạng tổng quát:

Trong đó:

• $X$ là query;
• $e$ là evidence đã biết;
• $Y$ là hidden variables;
• $\alpha$ là hằng số normalization.

Ví dụ nhỏ

Giả sử chỉ có ba biến nhị phân:

Rain -> Traffic -> Late

Ta muốn:

Traffic là hidden variable, nên với mỗi giá trị của Rain, ta phải cộng cả hai khả năng:

Traffic=True
Traffic=False

Ví dụ phần tử chưa normalize cho Rain=True:

Sau đó làm tương tự với Rain=False, rồi normalize hai giá trị.

Điểm cần hiểu là cộng bỏ hidden variables.

Vì sao exact inference có thể đắt?

Nếu có nhiều hidden variables, số assignments cần xét tăng rất nhanh.

Ví dụ có 20 hidden variables nhị phân thì có thể có:

assignments.

Enumeration đơn giản có thể phải đi qua rất nhiều trường hợp.

Có các exact algorithms tốt hơn như variable elimination, nhưng với mô hình rất lớn, người ta thường chấp nhận approximation.

Exact inference và approximate inference

Không có phương pháp luôn tốt nhất. Lựa chọn phụ thuộc kích thước mô hình, yêu cầu độ chính xác và thời gian tính toán.

Sampling - Lấy mẫu

Sampling là cách tạo các ví dụ giả lập theo probability distribution của mô hình.

Ví dụ một random variable:

Nếu sample 10,000 lần, tỉ lệ quan sát được thường sẽ gần các xác suất trên, dù không nhất thiết đúng chính xác.

Một code Python rất đơn giản:

import random
from collections import Counter

states = ["good", "slow", "down"]
weights = [0.70, 0.25, 0.05]

samples = random.choices(states, weights=weights, k=10_000)
counts = Counter(samples)

for state in states:
    print(state, counts[state] / len(samples))

Kết quả có thể gần:

good 0.699
slow 0.251
down 0.050

Mỗi lần chạy có thể hơi khác.

Forward Sampling trong Bayesian Network

Với Bayesian Network, ta sample theo topological order: parent trước, child sau.

Ví dụ:

Một sample có thể được tạo như sau:

1. Sample Rain
2. Sample Traffic dựa trên Rain
3. Sample BusLate dựa trên Rain
4. Sample Late dựa trên Traffic và BusLate

Kết quả một sample có thể là:

{
    "Rain": True,
    "Traffic": True,
    "BusLate": False,
    "Late": True
}

Lặp quá trình hàng nghìn lần ta có một tập samples từ joint distribution của mạng.

Một ví dụ Python thuần

Đây là phiên bản tối giản, không phụ thuộc API thư viện xác suất cụ thể:

import random


def bernoulli(p):
    return random.random() < p


def generate_sample():
    rain = bernoulli(0.30)

    p_traffic = 0.70 if rain else 0.25
    traffic = bernoulli(p_traffic)

    p_bus_late = 0.50 if rain else 0.15
    bus_late = bernoulli(p_bus_late)

    if traffic and bus_late:
        p_late = 0.95
    elif traffic and not bus_late:
        p_late = 0.70
    elif not traffic and bus_late:
        p_late = 0.80
    else:
        p_late = 0.10

    late = bernoulli(p_late)

    return {
        "rain": rain,
        "traffic": traffic,
        "bus_late": bus_late,
        "late": late,
    }

Code này chỉ nhằm minh họa cơ chế sampling. Các xác suất đều là giả định cho ví dụ học tập.

Ước lượng xác suất từ samples

Muốn ước lượng:

ta đếm số samples có late=True:

N = 100_000
samples = [generate_sample() for _ in range(N)]

late_count = sum(s["late"] for s in samples)
print(late_count / N)

Khi $N$ tăng, ước lượng thường ổn định hơn.

Rejection Sampling - Lấy mẫu rồi loại

Muốn ước lượng:

ta chỉ giữ samples phù hợp evidence Late=True.

N = 100_000
accepted = []

for _ in range(N):
    sample = generate_sample()
    if sample["late"]:
        accepted.append(sample)

p_rain_given_late = (
    sum(s["rain"] for s in accepted) / len(accepted)
)

print(p_rain_given_late)

Ý tưởng:

Vấn đề khi evidence hiếm

Giả sử evidence là:

Late=True AND BusLate=False AND Traffic=False

Nếu tổ hợp này rất hiếm, phần lớn samples sẽ bị bỏ.

Ví dụ:

Sinh 1,000,000 samples
Chỉ 2,000 samples khớp evidence
=> 998,000 samples bị vứt

Đó là nhược điểm lớn của rejection sampling.

Likelihood Weighting - Không vứt evidence

Likelihood weighting xử lý khác:

1. evidence variables được cố định đúng theo giá trị quan sát;
2. non-evidence variables vẫn được sample;
3. mỗi sample nhận một weight dựa trên xác suất của evidence với parent đã sample.

Ví dụ ta biết:

Late=True

Thay vì sample Late rồi loại khi nó False, ta luôn đặt:

Late=True

Nếu sample được:

Traffic=True
BusLate=False

thì weight của sample có thành phần:

Nếu sample khác:

Traffic=False
BusLate=False

weight có thành phần:

Sample đầu đóng góp mạnh hơn vì nó phù hợp evidence hơn.

Rejection sampling và likelihood weighting

Likelihood weighting cũng không hoàn hảo. Nếu network sâu hoặc evidence có xác suất cực nhỏ, weights có thể rất lệch. Nhưng ở mức nhập môn, điều cần nắm là nó tránh việc vứt bỏ hàng loạt samples chỉ vì evidence.

Sampling không có nghĩa là “đoán bừa”

Một sample ngẫu nhiên, nhưng không phải uniform random nếu distribution không đều.

Nếu:

thì sample Rain=True khoảng 30%, không phải 50%.

Sampling dùng randomness để mô phỏng đúng distribution mà mô hình quy định.

Bao nhiêu samples là đủ?

Không có một con số cố định cho mọi bài toán.

Nhiều samples hơn thường giảm sampling noise, nhưng tốn thời gian hơn. Với event hiếm, có thể cần rất nhiều samples mới thấy đủ trường hợp.

Vì vậy trong thực tế ta quan tâm cả:

• sai số ước lượng;
• tốc độ hội tụ;
• chi phí tính toán;
• cấu trúc của mô hình.

Tự kiểm tra

Câu 1

Trong bài toán $P(Rain\mid Late=True)$, biến nào là query và biến nào là evidence?

Câu 2

Rejection sampling làm gì với sample có Late=False nếu evidence là Late=True?

Câu 3

Likelihood weighting khác rejection sampling ở điểm cốt lõi nào?

Tóm tắt

• Inference hỏi distribution của query khi đã có evidence.
• Hidden variables cần được cộng bỏ hoặc xử lý gián tiếp.
• Enumeration là exact inference nhưng có thể đắt.
• Sampling tạo samples theo distribution của mô hình.
• Rejection sampling giữ samples khớp evidence và bỏ phần còn lại.
• Likelihood weighting cố định evidence và dùng trọng số để giảm lãng phí.
• Approximate inference đổi một phần độ chính xác lấy khả năng tính toán tốt hơn.

Tài liệu tham khảo

• CS50 AI - Lecture 2: Inference and Sampling

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