Bất định và xác suất

Ở phần Knowledge, ta thường làm việc với các phát biểu có thể kết luận là đúng hoặc sai. Nhưng trong thực tế, AI thường không có đủ thông tin để kết luận chắc chắn.

Ví dụ:

Trời nhiều mây trước giờ đi học.
=> Chiều nay có mưa không?

Wi-Fi trong ký túc xá chậm.
=> Router lỗi, mạng đông hay đường truyền nhà mạng có vấn đề?

Một email ghi "học bổng khẩn, bấm link ngay".
=> Có phải spam không?

Trong các tình huống này, câu trả lời hợp lý thường không phải chỉ là True hoặc False. Ta cần nói được mức độ có khả năng xảy ra của từng khả năng.

Đó là vai trò của uncertainty - bất định và probability - xác suất.

Các con số xác suất trong ví dụ của bài là số giả định để học cách tính, không phải thống kê thực tế tại Việt Nam.

Mục tiêu

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

hiểu vì sao AI cần biểu diễn bất định;
hiểu xác suất là gì và đọc được ký hiệu $P(A)$ ;
hiểu possible worlds và event;
tính được xác suất đơn giản, xác suất bù;
hiểu random variable và probability distribution;
phân biệt hai sự kiện độc lập và phụ thuộc.

Từ logic chắc chắn sang xác suất

Trong logic, ta có thể có:

P: Hôm nay có tiết AI.
Q: Lớp không có thông báo nghỉ.

P ∧ Q -> cần đi học.

Nếu các facts đúng và rule đúng, kết luận được suy ra chắc chắn.

Nhưng xét bài toán:

R: Trời đang mưa.
T: Đường có thể đông.
B: Xe buýt có thể trễ.
L: Sinh viên có thể đến lớp muộn.

Mưa có thể làm khả năng tắc đường cao hơn, nhưng không đảm bảo chắc chắn. Xe buýt trễ cũng làm khả năng đến lớp muộn cao hơn, nhưng sinh viên vẫn có thể đi sớm.

Điểm cần nhớ:

Logic nói nhiều về điều gì bắt buộc đúng. Xác suất nói nhiều về điều gì có khả năng đúng đến mức nào.

Hai cách tiếp cận có thể dùng cùng nhau trong một hệ thống AI.

Probability - Xác suất

Ta ký hiệu xác suất của một sự kiện $A$ là:

P(A)

Ví dụ:

P(Rain)=0.3

có nghĩa là theo mô hình đang dùng, xác suất xảy ra sự kiện Rain là 30%.

Với mọi sự kiện $A$ :

0 \le P(A) \le 1

$P(A)=0$ : sự kiện được xem là không thể xảy ra trong mô hình;
$P(A)=1$ : sự kiện được xem là chắc chắn xảy ra;
giá trị càng gần 1: sự kiện càng có khả năng xảy ra.

Xác suất không phải lời hứa rằng một trường hợp cụ thể sẽ xảy ra đúng theo tỉ lệ đó. Nó mô tả mức độ khả năng theo mô hình và dữ liệu đang có.

Possible Worlds - Các tình huống có thể xảy ra

Một cách dễ hiểu xác suất là tưởng tượng tất cả các tình huống có thể xảy ra.

CS50 gọi mỗi tình huống như vậy là một possible world, thường ký hiệu bằng chữ Hy Lạp $\omega$ .

Ví dụ tung một xúc xắc sáu mặt:

ω1: ra 1
ω2: ra 2
ω3: ra 3
ω4: ra 4
ω5: ra 5
ω6: ra 6

Nếu xúc xắc công bằng thì:

P(\omega_i)=\frac{1}{6}

Tổng xác suất của tất cả possible worlds phải bằng 1:

\sum_{\omega}P(\omega)=1

Event có thể gồm nhiều world

Gọi:

A = tung được số chẵn

Sự kiện $A$ xảy ra trong ba world:

2, 4, 6

Nên:

P(A)=\frac{3}{6}=0.5

Nếu các world đồng khả năng, ta có thể dùng:

P(A)=\frac{N(A)}{N}

với $N(A)$ là số world làm $A$ xảy ra và $N$ là tổng số world. Không phải bài toán nào cũng có các world đồng khả năng.

Ví dụ: hai xúc xắc và một lỗi suy nghĩ phổ biến

Tung hai xúc xắc có:

6\times6=36

possible worlds đồng khả năng.

Tổng của hai xúc xắc có thể từ 2 đến 12, tức 11 giá trị. Nhưng 11 giá trị này không có xác suất bằng nhau.

Tổng bằng 7 có sáu cách:

(1, 6)
(2, 5)
(3, 4)
(4, 3)
(5, 2)
(6, 1)

nên:

P(Sum=7)=\frac{6}{36}=\frac{1}{6}

Tổng bằng 12 chỉ có một cách:

(6, 6)

nên:

P(Sum=12)=\frac{1}{36}

Điểm quan trọng:

Có cùng số lượng “nhãn đầu ra” không có nghĩa các đầu ra có xác suất bằng nhau.

Điều này cũng xuất hiện trong AI. Một classifier có 5 lớp không có nghĩa mỗi lớp mặc định có xác suất 20%.

Complement - Sự kiện bù

Nếu $A$ là một sự kiện, $\neg A$ là sự kiện $A$ không xảy ra.

Vì hoặc $A$ xảy ra hoặc không xảy ra:

P(\neg A)=1-P(A)

Ví dụ:

P(Rain)=0.3

thì:

P(\neg Rain)=0.7

Một ví dụ gần với IT:

A: request tới server bị timeout
P(A) = 0.02

thì:

P(\neg A)=0.98

nghĩa là 98% request không timeout theo mô hình giả định.

Random Variable - Biến ngẫu nhiên

Trong lập trình, một biến thường giữ một giá trị tại một thời điểm.

Trong xác suất, random variable - biến ngẫu nhiên là một biến có tập các giá trị có thể nhận, nhưng trước khi quan sát ta chưa biết nó sẽ nhận giá trị nào.

Ví dụ:

Weather ∈ {sunny, cloudy, rainy}

hoặc:

WifiStatus ∈ {good, slow, disconnected}

Weather và WifiStatus là random variables.

Còn:

Weather = rainy
WifiStatus = slow

là các event cụ thể.

Probability Distribution - Phân phối xác suất

Ta thường muốn biết xác suất của từng giá trị mà random variable có thể nhận.

Giả sử mạng Wi-Fi trong một khoảng thời gian được mô hình hóa như sau:

`WifiStatus`	Xác suất
`good`	0.70
`slow`	0.25
`disconnected`	0.05

Ta có:

P(WifiStatus=good)=0.70

và tổng phân phối phải bằng 1:

0.70+0.25+0.05=1

Có thể viết gọn:

P(WifiStatus)=\langle0.70,0.25,0.05\rangle

Nhưng cách viết vector chỉ có ý nghĩa nếu ta biết rõ thứ tự là:

[good, slow, disconnected]

Independence - Độc lập

Hai sự kiện $A$ và $B$ độc lập nếu việc biết $B$ xảy ra không làm thay đổi xác suất của $A$ .

Một cách viết:

P(A\mid B)=P(A)

Một cách tương đương:

P(A\land B)=P(A)P(B)

Ví dụ hai lần tung đồng xu độc lập:

A: lần 1 ra ngửa
B: lần 2 ra ngửa

Biết lần đầu ra ngửa không làm lần sau dễ ra ngửa hơn.

Sự kiện phụ thuộc

Xét:

R: trời mưa đúng giờ sinh viên đi học
T: đường ùn tắc

Nếu biết trời mưa làm xác suất ùn tắc thay đổi thì:

P(T\mid R)\ne P(T)

Khi đó $R$ và $T$ không độc lập.

Một ví dụ IT khác:

S: server đang quá tải
L: response latency > 2 giây

Hai sự kiện này nhiều khả năng phụ thuộc nhau. Nếu server quá tải thì response chậm có thể dễ xuất hiện hơn.

Không được tự giả định độc lập

Đây là lỗi rất thường gặp.

Nếu đề bài chỉ cho:

P(A)=0.4,\qquad P(B)=0.5

thì chưa đủ để kết luận:

P(A\land B)=0.4\times0.5

Chỉ được nhân trực tiếp như vậy khi ta biết hoặc giả định $A$ và $B$ độc lập.

Một cách đọc bài toán xác suất

Khi gặp một bài toán, thử làm theo thứ tự:

Đừng bắt đầu bằng việc tìm công thức. Trước hết phải hiểu các biến đang biểu diễn điều gì.

Tự kiểm tra

Câu 1

Nếu:

P(A)=0.18

thì $P(\neg A)$ bằng bao nhiêu?

Đáp án

P(\neg A)=1-0.18=0.82

Câu 2

Random variable:

SubmissionStatus ∈ {on_time, late, missing}

có phân phối:

<0.78, 0.17, 0.05>

Xác suất SubmissionStatus = late là bao nhiêu?

Đáp án

Nếu thứ tự đúng như khai báo thì:

P(SubmissionStatus=late)=0.17

Câu 3

Biết $P(A)=0.4$ và $P(B)=0.5$ . Có được kết luận ngay $P(A\land B)=0.2$ không?

Đáp án

Không. Chỉ kết luận như vậy nếu $A$ và $B$ độc lập.

Tóm tắt

AI dùng xác suất khi thông tin không đủ để kết luận chắc chắn.
$P(A)$ nằm trong khoảng từ 0 đến 1.
Tổng xác suất của mọi khả năng trong một distribution bằng 1.
Possible world là một tình huống hoàn chỉnh có thể xảy ra.
Random variable có nhiều giá trị có thể nhận.
Event là một điều kiện cụ thể, ví dụ Weather = rainy.
$P(\neg A)=1-P(A)$ .
Independence là một tính chất cần có cơ sở, không được tự giả định.

Tài liệu tham khảo

CS50 AI - Lecture 2: Uncertainty

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