Entropy (Shannon Entropy): Đo lường sự bất ngờ và độ bất định
Từ trực giác về biến cố, lý thuyết thông tin đến so sánh với độ hỗn tạp Gini
Năm 1948, Claude Shannon công bố bài báo “A Mathematical Theory of Communication”, xây dựng một khuôn khổ toán học cho truyền thông. Một câu hỏi trung tâm của khuôn khổ ấy là: Làm thế nào để lượng hoá “lượng thông tin” chứa trong một thông điệp?
Một khái niệm trung tâm trong câu trả lời là Entropy — thước đo độ bất định (uncertainty) trung bình của một nguồn. Trong học máy, Entropy là cơ sở của Information Gain trong ID3 và Gain Ratio trong C4.5.
Bài viết này đi từ trực giác về “sự bất ngờ” đến công thức toán học của Entropy, rồi so sánh Entropy với độ hỗn tạp Gini (Gini Impurity).
1. Trực giác cốt lõi: Thông tin đến từ sự bất ngờ
Hãy thử tưởng tượng bạn nhận được hai bản tin thời sự sau:
- Bản tin 1: “Ngày mai, mặt trời sẽ mọc ở hướng Đông.”
- Bản tin 2: “Trưa mai, tuyết sẽ rơi phủ trắng đường phố Sài Gòn.”
Bản tin nào mang lại nhiều “thông tin” hơn cho bạn?
Trong mô hình đơn giản này, bản tin thứ hai bất ngờ hơn nhiều. Ta có thể xem việc mặt trời mọc ở hướng Đông là một sự kiện gần như chắc chắn ($p \approx 1$), nên bản tin ấy mang lại rất ít thông tin mới.
Ngược lại, tuyết rơi ở Sài Gòn là một biến cố rất hiếm ($p \approx 0$). Nếu thực sự xảy ra, biến cố này có độ bất ngờ lớn và vì thế mang nhiều thông tin hơn trong nghĩa của lý thuyết thông tin.
Trực giác cần giữ lại là: xác suất của biến cố càng nhỏ thì độ bất ngờ của việc quan sát thấy nó càng lớn. Quan hệ này là logarit, không phải tỷ lệ nghịch theo nghĩa $1/p$.
Định lượng độ bất ngờ (Surprisal)
Để đo lường lượng thông tin (độ bất ngờ) $I(p)$ của một biến cố có xác suất $p$, hàm đo cần thỏa mãn các tính chất tự nhiên:
- Biến cố chắc chắn xảy ra ($p = 1$) không mang thông tin: $I(1) = 0$.
- Biến cố càng khó xảy ra ($p \to 0$) thì thông tin càng lớn: $I(p) \to \infty$.
- Hai biến cố độc lập $A$ và $B$ cùng xảy ra thì lượng thông tin thu được phải bằng tổng thông tin của từng biến cố: $I(p_A \cdot p_B) = I(p_A) + I(p_B)$.
Nếu thêm các giả thiết chính quy quen thuộc như tính liên tục, các yêu cầu trên xác định hàm logarit đến một hằng số tỷ lệ. Chọn cơ số 2 cho ta:
$$ I(p) = \log_2\left(\frac{1}{p}\right) = -\log_2(p). $$(Khi dùng cơ số 2, đơn vị của thông tin được gọi là bit).
- Nếu bạn tung một đồng xu cân bằng ($p = 0{,}5$): $$I(0{,}5) = -\log_2(0{,}5) = \log_2(2) = 1 \text{ bit}.$$ $1$ bit chính là lượng thông tin cần thiết để giải tỏa sự mơ hồ của một câu hỏi có đúng hai khả năng đồng xác suất (Có / Không).
2. Công thức Shannon Entropy: Độ bất định kỳ vọng
Một nguồn phát thông tin (hoặc một biến ngẫu nhiên rời rạc $X$) thường không chỉ có một kết cục, mà có $K$ trạng thái khả dĩ với các xác suất tương ứng $(p_1, p_2, \ldots, p_K)$ thỏa mãn $\sum_{k=1}^K p_k = 1$.
Mỗi khi hệ thống phát ra trạng thái $k$, ta nhận được lượng thông tin là $-\log_2(p_k)$.
Entropy $H(X)$ chính là giá trị kỳ vọng (lượng thông tin trung bình) mà ta nhận được sau mỗi lần quan sát hệ thống:
$$ H(X) = \mathbb{E}[I(p)] = \sum_{k=1}^K p_k I(p_k) = -\sum_{k=1}^K p_k \log_2(p_k). $$(Quy ước: nếu một trạng thái có $p_k = 0$, ta tính $0 \log_2(0) = \lim_{p \to 0^+} p \log_2(p) = 0$, bởi một biến cố không bao giờ xảy ra thì không đóng góp vào độ bất định trung bình).
Hai trạng thái cực biên của Entropy
- Phân phối tập trung (độ bất định bằng 0): Nếu một lớp chiếm trọn vẹn xác suất ($p_1 = 1$, các $p_j = 0$), kết quả được xác định: $$H(X) = -1 \log_2(1) = 0 \text{ bit}.$$
- Phân phối đều (độ bất định cao nhất): Khi tất cả $K$ kết cục có xác suất ngang nhau ($p_k = \frac{1}{K}$): $$H_{\max} = -\sum_{k=1}^K \frac{1}{K} \log_2\left(\frac{1}{K}\right) = -\log_2\left(\frac{1}{K}\right) = \log_2(K) \text{ bit}.$$
3. Trường hợp hai lớp ($K=2$) và đường cong lõm
Xét bài toán nhị phân quen thuộc: một tập dữ liệu chỉ gồm hai lớp với tỷ lệ $p$ và $1 - p$. Công thức Entropy rút về:
$$ H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p). $$Khảo sát hàm số $H(p)$ trên đoạn $[0, 1]$:
- Tại $p = 0$ hoặc $p = 1$: $H(0) = H(1) = 0$ bit.
- Tại $p = 0{,}5$ (hai lớp chia đều 50:50): $$H(0{,}5) = -0{,}5\log_2(0{,}5) - 0{,}5\log_2(0{,}5) = 1 \text{ bit}.$$
- Đạo hàm bậc hai: $$H''(p) = -\frac{1}{\ln(2)}\left(\frac{1}{p} + \frac{1}{1 - p}\right) < 0 \quad \forall p \in (0, 1).$$ Điều này chứng minh $H(p)$ là một hàm lõm nghiêm ngặt (strictly concave).
Đồ thị của $H(p)$ là một đường cong hình vòm đối xứng qua $p = 0{,}5$. Khi $p \to 0^+$ hoặc $p \to 1^-$, độ lớn đạo hàm tiến tới vô hạn. Vì vậy, entropy phản ứng mạnh với những thay đổi nhỏ của tỷ lệ lớp ở gần một nút thuần khiết (pure node).
4. Entropy trong Cây quyết định: Information Gain
Trong ID3 và các tiêu chí dựa trên thông tin của C4.5, Entropy đóng vai trò là “thước đo độ hỗn tạp” của một nút dữ liệu:
- Một nút chứa các phần tử cùng một lớp có $H = 0$ (nút thuần khiết - pure node).
- Một nút trộn lẫn nhiều lớp có $H > 0$ (nút hỗn tạp).
Khi thuật toán thử chia nút cha $t$ (có $n_t$ quan sát và Entropy $H(t)$) thành hai nhánh con $L$ (trái) và $R$ (phải), Entropy trung bình có trọng số sau khi chia là:
$$ H_{\text{sau}} = \frac{n_L}{n_t} H(L) + \frac{n_R}{n_t} H(R). $$Mức giảm độ bất định được gọi là Mức tăng thông tin (Information Gain):
$$ IG = H(t) - H_{\text{sau}}. $$Với ID3, thuật toán chọn phép chia có $IG$ lớn nhất trong các ứng viên được xét. C4.5 còn hiệu chỉnh thiên lệch của Information Gain đối với thuộc tính có nhiều giá trị bằng tỷ số mức tăng thông tin (Gain Ratio). Đây là lựa chọn tham lam tại từng nút, không phải bảo đảm tìm được cây tối ưu toàn cục.
5. Một liên hệ hình thức giữa Entropy và Gini
Trong khi C4.5 dùng tiêu chí dựa trên Entropy, thuật toán CART thường dùng Độ hỗn tạp Gini. Hai thước đo này có dạng khác nhau: một bên chứa hàm logarit, một bên là biểu thức bậc hai.
Ta có thể nhìn thấy công thức Gini khi tuyến tính hóa từng số hạng logarit quanh $1$, nhưng cần hiểu đúng phạm vi của phép xấp xỉ này.
Khai triển chuỗi Taylor của hàm $\ln(x)$ quanh điểm $x = 1$ cho ta:
$$ \ln(x) \approx x - 1 \implies -\ln(p) \approx 1 - p. $$Thay xấp xỉ này vào công thức Entropy tự nhiên $H_e(t) = -\sum_{k=1}^K p_k \ln(p_k)$:
$$ H_e(t) \approx \sum_{k=1}^K p_k (1 - p_k) = 1 - \sum_{k=1}^K p_k^2 = G(t). $$Phép thay thế trên chỉ chính xác khi đối số $p_k$ gần $1$. Nó không phải là xấp xỉ đều trên toàn bộ miền xác suất; đặc biệt, khai triển quanh $1$ mô tả kém các xác suất nhỏ. Vì vậy, nên xem đây là một liên hệ đại số gợi trực giác, không phải khẳng định rằng Gini là xấp xỉ Taylor tốt của Entropy cho mọi phân phối.
Hai tiêu chí vẫn có nhiều tính chất chung: đều bằng $0$ ở nút thuần khiết, đạt cực đại tại phân phối đều và là các hàm lõm của phân phối lớp. Do đó chúng thường có thể xếp hạng nhiều phép chia giống nhau, nhưng hoàn toàn có thể chọn các phép chia khác nhau. Gini tránh phép tính logarit, song chênh lệch thời gian huấn luyện thực tế còn phụ thuộc cách cài đặt và dữ liệu.
6. So sánh: Entropy và Gini Impurity
| Tiêu chí | Shannon Entropy $H(p)$ | Gini Impurity $G(p)$ |
|---|---|---|
| Công thức ($K=2$) | $-p\log_2 p - (1-p)\log_2(1-p)$ | $2p(1-p)$ |
| Giá trị cực đại | $1{,}0$ bit (tại $p=0{,}5$) | $0{,}5$ (tại $p=0{,}5$) |
| Thuật toán tiêu biểu | ID3, C4.5 | CART |
| Bản chất | Lượng thông tin kỳ vọng (Information Theory) | Xác suất đoán sai / rút trúng hai phần tử khác nhãn |
| Chi phí tính toán | Tốn kém hơn do gọi hàm $\log_2$ | Rất nhẹ, chỉ cần phép nhân và trừ |
| Mối quan hệ | Độ bất định Shannon | Có thể thu được về mặt hình thức khi tuyến tính hóa $-\ln p$ quanh $p=1$; không phải xấp xỉ đều |
7. Tóm tắt
- Độ bất ngờ (Surprisal): Biến cố càng ít xảy ra thì khi xuất hiện càng mang lại nhiều thông tin: $I(p) = -\log_2(p)$.
- Shannon Entropy: Là độ bất ngờ trung bình (kỳ vọng) của toàn bộ hệ thống: $H(X) = -\sum p_k \log_2(p_k)$.
- Tính chất cốt lõi: Bằng $0$ khi hệ thống hoàn toàn thuần khiết (chỉ có một kết cục) và đạt cực đại khi các kết cục đồng xác suất.
- So sánh với Gini: Gini Impurity $1 - \sum p_k^2$ và Entropy có chung nhiều tính chất hình học, nhưng là hai tiêu chí khác nhau và có thể chọn các phép chia khác nhau trong Cây quyết định (Decision Tree).
Tài liệu tham khảo
- Claude E. Shannon (1948), A Mathematical Theory of Communication, Bell System Technical Journal, 27(3), 379–423.
- J. Ross Quinlan (1986), Induction of Decision Trees, Machine Learning, 1, 81–106.
- J. Ross Quinlan (1993), C4.5: Programs for Machine Learning, Morgan Kaufmann.
- Trevor Hastie, Robert Tibshirani, Jerome Friedman (2009), The Elements of Statistical Learning, 2nd Edition, Springer.