Chuỗi Markov và bài toán khám phá - khai thác trong Python

Khái niệm bằng lời đơn giản

AI thường phải hành động khi chưa chắc chắn. Chuỗi Markov mô hình hóa cách một hệ chuyển giữa các trạng thái với xác suất cố định, còn bài toán multi-armed bandit cho thấy lựa chọn cốt lõi của học tăng cường: thử cái mới hay dùng cái đang hiệu quả nhất.

Dự đoán trạng thái tương lai bằng chuỗi Markov và cân bằng giữa khám phá và khai thác với bandit epsilon-greedy.

Ý chính

Trong chuỗi Markov, trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại.
Các xác suất chuyển ra từ một trạng thái luôn cộng lại bằng 1.
Khám phá giúp tìm lựa chọn tốt hơn; khai thác thu thưởng từ lựa chọn tốt nhất đã biết.
Epsilon điều khiển sự cân bằng: epsilon càng lớn thì khám phá càng nhiều.

Khi nào nên sử dụng?

Hiểu điều gì diễn ra bên trong mạng nơ-ron và các thư viện AI.
Nắm ý tưởng trước khi tự cài đặt nó trong các thử thách tương ứng.
Chuẩn bị cho khóa học machine learning, phỏng vấn và dự án.

Xem trực quan

Đổi xác suất chuyển trạng thái thời tiết để xem chuỗi ổn định ở đâu. Nhấn Phát để bandit học xem máy nào trả thưởng nhiều hơn.

Code ví dụ

Chạy code →

main.py

import random

# Markov chain: tomorrow's weather depends only on today's.
transitions = {"sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}}
dist = {"sunny": 1.0, "rainy": 0.0}
for day in range(1, 4):
    dist = {s: sum(dist[p] * transitions[p][s] for p in dist) for s in dist}
    print(f"day {day}:", {s: round(v, 3) for s, v in dist.items()})

# Epsilon-greedy bandit: usually pick the best arm so far, sometimes explore.
random.seed(1)
true_payouts = [0.3, 0.7]
counts, totals = [0, 0], [0.0, 0.0]
epsilon = 0.1
for _ in range(500):
    if random.random() < epsilon or 0 in counts:
        arm = random.randrange(2)                                  # explore
    else:
        arm = max(range(2), key=lambda a: totals[a] / counts[a])  # exploit
    reward = 1 if random.random() < true_payouts[arm] else 0
    counts[arm] += 1
    totals[arm] += reward
print("pulls per arm:", counts)
print("estimated payouts:", [round(t / c, 2) for t, c in zip(totals, counts)])

Kết quả dự kiến

day 1: {'sunny': 0.8, 'rainy': 0.2}
day 2: {'sunny': 0.72, 'rainy': 0.28}
day 3: {'sunny': 0.688, 'rainy': 0.312}
pulls per arm: [25, 475]
estimated payouts: [0.16, 0.7]

Cách hoạt động

Mỗi ngày, xác suất mới là xác suất cũ nhân với xác suất chuyển trạng thái, nên khả năng nắng giảm từ 1.0 xuống 0.688 sau ba ngày. Bandit chọn ngẫu nhiên một cần gạt 10% số lần, còn lại kéo cần có trung bình tốt nhất cho tới lúc đó; nó nhanh chóng dồn phần lớn lượt kéo vào cần tốt hơn và ước lượng mức thưởng của cần này vào khoảng 0.7.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy sửa code theo các bài tập dưới đây để hiểu rõ cách hoạt động thay vì chỉ sao chép kết quả.

Đổi đầu vào hoặc trọng số và đoán kết quả trước khi chạy.
In các giá trị trung gian để theo dõi từng bước tính toán.
Giải các thử thách được liên kết bên dưới để tự cài đặt ý tưởng.

Chạy trong Python IDE →

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách