# Entropy (Shannon Entropy): Đo lường sự bất ngờ và độ hỗn tạp thông tin Năm 1948, nhà toán học Claude Shannon đặt nền móng cho thời đại số với bài báo kinh điển *"A Mathematical Theory of Communication"*. Trọng tâm công trình ấy là câu hỏi tưởng chừng mang tính triết học: **Làm thế nào để lượng hoá "lượng thông tin" chứa trong một thông điệp?** Câu trả lời của Shannon là khái niệm **Entropy** — thước đo độ bất định (uncertainty) và mức độ hỗn tạp của một nguồn dữ liệu. Trong học máy, Entropy chính là tiêu chí phân nhánh nền tảng của các thuật toán cây quyết định nổi tiếng như ID3 và C4.5. Bài viết này sẽ đi từ trực giác đời thường về "sự bất ngờ" đến công thức toán học của Entropy, và làm sáng tỏ cây cầu nối thanh lịch giữa Entropy với [chỉ số Gini (Gini Impurity)]({{< ref "gini-impurity.md" >}}). --- ## 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: 1. **Bản tin 1:** *"Ngày mai, mặt trời sẽ mọc ở hướng Đông."* 2. **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? Rõ ràng là bản tin thứ hai. Mặt trời mọc hướng Đông là một sự kiện gần như chắc chắn ($p = 1$). Bạn đã biết trước điều đó, nên khi nghe tin, mức độ hiểu biết của bạn về thế giới không tăng thêm chút nào — bản tin mang lại **0 lượng thông tin**. Ngược lại, tuyết rơi ở Sài Gòn là một biến cố cực kỳ hiếm hoi ($p \approx 0$). Khi một điều bất ngờ như vậy xảy ra, nó làm thay đổi hoàn toàn nhận thức của bạn — nó mang lại **một lượng thông tin khổng lồ**. Từ trực giác này, Shannon nhận xét: **Lượng thông tin của một biến cố tỷ lệ nghịch với xác suất xảy ra của nó.** ### Đị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)$. Hàm toán học duy nhất thỏa mãn tính chất cộng tính này chính là hàm logarit: $$ 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: 1. **Thuần khiết tuyệt đối (Độ 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ả hoàn toàn đoán trước được: $$H(X) = -1 \log_2(1) = 0 \text{ bit}.$$ 2. **Hỗn loạn cực đại (Độ 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$) & Đường cong Parabol lồi 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$. Điểm đáng lưu ý nhất là độ dốc của đường cong: tại hai đầu biên ($p \to 0$ và $p \to 1$), tiếp tuyến của đồ thị trở nên dốc đứng (đạo hàm tiến tới $\pm \infty$). Tính chất này khiến Entropy rất nhạy cảm với việc làm sạch dữ liệu khi nút tiến gần trạng thái thuần khiết (pure node). --- ## 4. Entropy trong Cây quyết định: Information Gain Trong các thuật toán cây như ID3 và C4.5 của Ross Quinlan, 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}}. $$ Thuật toán sẽ quét qua các đặc trưng và ngưỡng ứng viên, chọn phép chia mang lại $IG$ lớn nhất để cây học được nhiều thông tin nhất tại mỗi bước. --- ## 5. Cầu nối toán học: Gini chính là xấp xỉ Taylor bậc 1 của Entropy Trong khi C4.5 dùng Entropy, thuật toán CART lại chọn [Độ hỗn tạp Gini]({{< ref "gini-impurity.md" >}}). Hai thước đo này trông có vẻ khác nhau: một bên chứa hàm logarit, một bên chỉ gồm phép nhân và trừ đa thức. Tuy nhiên, giữa chúng tồn tại một mối liên hệ giải tích tuyệt đẹp: **Gini Impurity chính là xấp xỉ Taylor bậc 1 của Entropy.** 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). $$ Đây là một phát hiện toán học vô cùng thanh lịch: 1. **Hành vi phân tách gần như tương đương:** Vì Gini là xấp xỉ tuyến tính bậc một của Entropy quanh điểm $p = 1$, hình dạng đồ thị của hai thước đo (sau khi chuẩn hóa tỷ lệ thang đo) gần như bám sát nhau. Trong hầu hết các bài toán thực tế, CART (dùng Gini) và C4.5 (dùng Entropy) sẽ chọn ra các ngưỡng phân nhánh gần như y hệt. 2. **Tiết kiệm chi phí tính toán:** Thay vì bắt máy tính phải gọi hàm $\log_2$ hàng triệu lần khi thử nghiệm hàng nghìn ngưỡng trên các tập dữ liệu lớn, CART chỉ cần thực hiện các phép nhân và cộng số học đơn giản với Gini. --- ## 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ệ** | Dạng giải tích gốc | Xấp xỉ Taylor bậc 1 của Entropy | --- ## 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. - **Cầu nối với Gini:** Gini Impurity $1 - \sum p_k^2$ chính là xấp xỉ chuỗi Taylor bậc 1 của Entropy, giải thích vì sao hai tiêu chí này vận hành tương tự nhau trong các mô hình [Cây quyết định (Decision Tree)]({{< ref "decision-tree.md" >}}). --- ### Tài liệu tham khảo - Claude E. Shannon (1948), [*A Mathematical Theory of Communication*](https://doi.org/10.1002/j.1538-7305.1948.tb01338.x), *Bell System Technical Journal*, 27(3), 379–423. - J. Ross Quinlan (1986), [*Induction of Decision Trees*](https://doi.org/10.1007/BF00116251), *Machine Learning*, 1, 81–106. - Trevor Hastie, Robert Tibshirani, Jerome Friedman (2009), [*The Elements of Statistical Learning*](https://hastie.su.domains/ElemStatLearn/), 2nd Edition, Springer.