1.1 Lý thuyết thông tin, entropy

Information Theory – lý thuyết thông tin là một nhánh của toán học liên quan tới đo đạc, định lượng và mã hóa thông tin. Cha đẻ của Information Theory là Claude Shannon. Ông nghiên cứu về phong thái mã hóa thông tin khi truyền tin, sao cho quá trình truyền tin đạt hiệu quả tốt nhất mà không làm mất đi mát thông tin.

Bạn Đang Xem: Entropy, Cross Entropy và KL Divergence

H1: Claude Shannon

Năm 1948, trong một nội dung bài viết của mình, Claude Shannon đã nhắc tới khái niệm information entropy như thể một độ đo để định lượng lượng thông tin hay độ biến động/không kiên cố của thông tin. Có vô số phương pháp dịch entropy: độ biến động, độ hỗn loạn, độ không kiên cố, độ bất thần, độ khôn lường … của thông tin hay lượng thông tin. Trong bài này, mình sẽ giữ lại được nguyên từ entropy thay vì dịch sang tiếng Việt.

Để dễ hiểu hơn, mình sẽ lấy một ví dụ như sau: giả sử sau những lần quan sát thời tiết trong một năm, bạn ghi chép được thông tin như sau:

• Vào ngày đông giá rét, xác suất ngày nắng (nhẹ) là 100%, mưa là 0%. Như vậy dựa vào xác suất đó, ngày đông giá rét ta hoàn toàn tự tín đoán được ngày mai mưa hay nắng. Trong trường hợp này, độ kiên cố cao, sáng mai ngủ dậy, trời không có mưa thì ta cũng không thấy bất thần, tức thông tin tiếp nhận đó không có nhiều giá trị.
• Vào ngày hè, xác suất một ngày không mưa là 50%, có mưa là 50%. Như vậy xác suất mưa/nắng là như nhau. Ta rất khôn lường xem ngày mai mưa hay nắng, độ kiên cố là không đảm bảo. Nói cách khác, ngày mai có mưa hay nắng đều làm ta bất thần hơn trong trường hợp 1.
• Như vậy, ta cần một cơ chế để giám sát và đo lường sự biến động của thông tin, nói cách khác là đo lượng thông tin.

Qua ví dụ trên, ta đã có cái nhìn rõ hơn về khái niệm entropy.

1.2 Entropy và mã hóa thông tin

1.2.1 Mã hóa thông tin

Để hiểu hơn về khái niệm, tính ứng dụng và phương pháp tính entropy, trước tiên ta dạo qua một lượt về chủ đề mã hóa thông tin.

Giả sử khi truyền tin thời tiết từ Tokyo tới Thành Phố New York, với giả sử cả hai bên đều đã biết trước thông gửi đi chỉ là vấn đề mưa/nắng của Tokyo. Ta có thể gửi message “Tokyo, Tokyo’s weather is fine” đi. Tuy nhiên, có vẻ cách này hơi dư thừa. Do cả hai điểm cầu Tokyo và Thành Phố New York đều biết rằng thông tin truyền đi/tới đều về thời tiết Tokyo. Nghĩa là vấn đề Tokyo chỉ việc truyền đi 1 trong 2 tin nhắn mưa-nắng là đủ đề người ở Thành Phố New York hiểu. Cách này nghe qua có vẻ khá hợp lý, tuy nhiên vẫn chưa tối ưu. Hai bên chỉ việc quy ước trước với nhau rằng: mưa là 0, nắng là một. Như vậy giá trị truyền đi chỉ việc (0, 1) là đủ. Theo phong cách này, thông tin truyền đi đã được tối ưu mà không sợ bị mất mát, hiểu nhầm giữa hai bên gửi/nhận. Quy tắc mã hóa mưa-0, nắng-1 gọi là một bảng mã hóa.

Với cách mã hóa trên, ta đã dùng tới 1 bit để mã hóa thông tin. Trong hệ nhị phân, 1 bit bất kì có mức giá trị 0 hoặc 1. Ở đây là một mô hình mã hóa và truyền dẫn thông tin. tin tức được mã hóa (theo 1 bảng mã quy ước trước) trước lúc truyền đi. Tại điểm nhận, người nhận sẽ nhận được những thông tin đã trở nên mã hóa, lúc này nơi nhận cần tiến hành lời giải để nhận được thông tin gốc lúc đầu.

Mô hình mã hóa và truyền dẫn thông tin đơn giản

1.2.2 Entropy

Kích cỡ mã hóa trung bình

Ta đã hiểu được cách mã hóa thông tin. Vậy làm thế nào để so sánh độ hiểu quả khi mã hóa bằng hai bảng mã khác nhau. Nói cách khác, làm thế nào để xác định được bảng mã nào tốt hơn. Hãy quan sát hình trong tương lai.

H4. Bảng thống kê tần xuất thời tiết và hai cách mã hóa khác nhau.

Lưu ý: khi mã hóa, các số 0 đừng trước sẽ tiến hành lược bỏ, VD: 001 -> 1, 0000100 -> 100 …

Giả sử, sau 100 lần ghi nhận thời tiết tại Tokyo, người ta thu được phân phối như hình trên với tần xuất nắng-mưa-mây-tuyết tuần tự là 10, 20, 40, 30 lần. Ta có hai bảng mã hóa như trong hình. Để so sánh độ hiểu quả của hai bảng mã trên, ta so sánh số bit trung bình được truyền đi mỗi lần truyền tin.

• Bảng mã 1: everage_bit = (10∗1+20∗1+40∗2+30∗2)/100=1.7(10 * 1 + 20*1 + 40* 2 + 30*2)/100 = 1.7(10∗1+20∗1+40∗2+30∗2)/100=1.7 bit.
• Bảng mã 2: everage_bit = (10∗2+20∗2+40∗1+30∗1)/100=1.1(10* 2 + 20* 2 + 40*1 + 30*1)/100 = 1.1(10∗2+20∗2+40∗1+30∗1)/100=1.1 bit

Trong ngành mã hóa, bảng mã 2 được xem là tối ưu hơn, tốt hơn bảng mã 1 vì nếu dùng bảng mã 2 sẽ tiết kiệm chi phí được số bit hơn, tốn ít băng thông (khi truyền tin) hay chiếm ít dung tích (lưu trữ). Phương pháp tính trên được gọi là tính kích cỡ mã hóa trung bình

Xem Thêm : Vé số Vietlott là gì? Giá mua một vé bao nhiêu tiền? Mua ở đâu? Dò vé như thế nào?

everageBit=p1∗n1+p2∗n2+…+pk∗nneverageBit = p_1*n_1 + p2*n_2 + … + p_k*n_n everageBit=p1​∗n1​+p2∗n2​+…+pk​∗nn​

(1)(1) (1)

Với nin_ini​ là số bít dùng làm mã hóa tín hiệu có tần xuất pip_ipi​

Kích cỡ mã hóa trung bình tối thiểu

Vậy làm thế nào để lựa chọn ra cách mã hóa tối ưu nhất. Tất cả chúng ta cần lựa chọn ra cách mã hóa có kích cỡ mã hóa trung bình nhỏ nhất.

Vừa rồi là một ví dụ đơn giản về chủ đề thời tiết với 4 loại tin nhắn (nắng, mưa, mây, tuyết) cần mã hóa, ta chỉ việc dùng 2 bit là đủ để mã hóa 4 loại tin nhắn này. Tương tự với N kiểu tin nhắn, ta cần số bit mã hóa là:

n=log⁡2Nn = log_2^N n=log2N​

Giả sử 1 các tin nhắn này đều phải sở hữu tần suất xuất hiện như nhau là p=1/Np=1/Np=1/N.

np=log⁡2N=log⁡21p=−log⁡2pn_p = log_2^N = log_2^frac {1} {p}=-log_2^p np​=log2N​=log2p1​​=−log2p​

Như vậy −log⁡2P-log_2^{Phường}−log2P​ là số bit tối thiểu để mã hoá 1 tin nhắn với xác suất xuất hiện ppp. Kết phù hợp với công thức (1), ta được công thức tính kích cỡ mã hóa trung bình tối thiểu, đây đó là công thức tính Entropy:

Entropy=−∑inpi∗ni=−∑inpi∗log⁡2piEntropy = -sum_{i}^{n} p_i * n_i = -sum_{i}^{n} p_i * log_2^{p_i} Entropy=−i∑n​pi​∗ni​=−i∑n​pi​∗log2pi​​

Trong thực tế, ta có thể thay log⁡2log_2log2​ bằng log⁡10log_{10}log10​, log⁡elog_eloge​ ..

Kết luận: entropy cho tất cả chúng ta biết kích thước mã hóa trung bình tối thiểu theo lý thuyết cho những sự kiện tuân theo một phân phối xác suất cụ thể.

Tính chất của Entropy.

Với công thức tính entropy ở trên, entropy được tính hoàn toàn dựa vào xác suất. Giả sử với phân phối xác suất về thời tiết (mưa, nắng) là Phường = {p1, p2}. Người ta nhận ra Entropy(Phường) đạt max khi p1=p2. Khi p1 và p2 càng lệch nhau thì Entropy(Phường) càng giảm. Nếu p1=p2=0.5, entropy đạt max, ta rất khó để đoán thời tiết ngày mai mưa hay nắng. Nếu p1=0.1 và p2=0.9, ta sẽ tự tín đoán rằng ngày mai trời sẽ nắng, lúc này entropy có mức giá trị thấp hơn nhiều.

Entropy cao đồng nghĩa với việc ta khôn lường trước được sự kiện sắp xẩy ra. Ta có thể gọi đó là việc biến động, sự bất ổn hay entropy là một thước đo sự “khôn lường” của thông tin.

Như đã tôi đã khái niệm ở trên, entropy là kích thước mã hóa trung bình tối thiểu theo lý thuyết cho những sự kiện tuân theo một phân phối xác suất cụ thể. Miễn sao tất cả chúng ta biết được phân phối đó, ta sẽ tính được Entropy.

Tuy nhiên, không phải lúc nào ta cũng biết được phân phối đó. Như ví dụ thời tiết trong phần 1, phân phối tất cả chúng ta dùng thực chất chỉ là phân phối ta thu được từ việc thống kê chuỗi sự kiện đã xẩy ra trong quá khứ. Ta không thể đảm nói rằng thời tiết trong năm tiếp theo cũng y hệt năm ngoái. Nói cách khác, các phân phối ta thu được từ việc thống kê trong quá khử chỉ là sấp xỉ, gần đúng của phân phối thực sự của tín hiệu tương lai.

Xem Thêm : DPO là gì? Cách giao dịch với DPO hiệu quả

Để dễ hiểu hơn, mình sẽ lấy ví dụ vẫn về thời tiết như sau:

• Đầu xuân năm mới 2019, người ta thống kê thời tiết cả năm 2018 và thu được phân phối (nắng, mưa, mây, tuyết) là quận = {0.1, 0.3, 0.4, 0.2}
• Người ta dựa vào quận để lập bảng mã hóa 4 tin nhắn này cho năm tới 2019. quận được gọi là phân phối ước tính. Tin nhắn được mã hóa và vẫn tiếp tục được truyền đi trong cả năm 2019 từ Tokyo tới Thành Phố New York.
• Tới ở thời gian cuối năm 2019, người ta thống kê lại thời tiết cả năm, thu được phân phối mới là Phường = {0.11, 0.29, 0.41, 0.19}. Phường được xem là phân phối chuẩn xác khi đối chiếu với năm 2019.

Như vậy, dựa theo công thức đã chứng minh ở phần 1, số bit trung bình được sử dụng trong cả năm 2019 là:

CrossEntropy(Phường,quận)=−∑inpi∗log⁡2qiCrossEntropy(Phường, quận) = -sum_{i}^{n} p_i * log_2^{q_i} CrossEntropy(Phường,quận)=−i∑n​pi​∗log2qi​​

Như vậy, Entropy của tín hiệu này còn có phân phối Phường (tính kì vọng dựa vào Phường) nhưng lại được mã hóa dựa vào phân phối quận. Đó là lí do cái tên CrossEntropy ra đời (cross có tức thị chéo nhau, mình không biết dịch thế nào cho chuẩn).

Tính chất của CrossEntropy đặc biệt quan trọng tại đoạn:

• đạt giá trị minimum nếu Phường == quận
• rất nhạy cảm với sự sai khác giữa pip_ipi​ và qiq_iqi​. Khi pip_ipi​ và qIq_IqI​ càng khác nhau, giá trị cross_entropy càng tăng nhanh.

Bởi vì các bài toán machine learning thường quy về bài toán xây dựng model sao cho output càng gần target càng tốt (output, target thường đều ở dạng phân phối xác suất). Dựa vào tính nhạy cảm này, người ta dùng CrossEntropy để tối ưu hóa các model.

Sau thời điểm đã đi qua phần Cross Entropy, các bạn sẽ thấy KL Divergence rất đơn giản.

Vẫn với ví dụ về thời tiết trong phần 2. Giả sử vào ở thời gian cuối năm 2019, người ta tính được CrossEntropy(Phường, quận). Lúc này, người ta muốn xác định xem họ đã tốn, tổn thất thêm bao nhiêu bit khi mã hóa dựa vào quận thay vì dùng Phường. Ta có:

DKL(Phường∣∣quận)=CrossEntropy(Phường,quận)−Entropy(Phường)D_{KL} (Phường||quận) = CrossEntropy(Phường, quận) – Entropy(Phường) DKL​(Phường∣∣quận)=CrossEntropy(Phường,quận)−Entropy(Phường)

=−∑inpi∗log⁡2qi+∑inpi∗log⁡2pi= -sum_{i}^{n} p_i * log_2^{q_i} + sum_{i}^{n} p_i * log_2^{p_i} =−i∑n​pi​∗log2qi​​+i∑n​pi​∗log2pi​​

=∑inpi∗log⁡2piqi= sum_{i}^{n} p_i * log_2^{frac{p_i}{q_i}} =i∑n​pi​∗log2qi​pi​​​

Như vậy, KL Divergence là một cách để đó tổn thất khi ước tính, xấp xỉ 1 phân phối Phường bằng phân phối quận.

Tính chất DL DIvergence:

• Không có tính đối xứng, tức DKL(Phường∣∣quận)≠DKL(quận∣∣Phường)D_{KL} (Phường||quận) neq D_{KL} (quận||Phường)DKL​(Phường∣∣quận)=DKL​(quận∣∣Phường)
• Tương tự CrossEntropy, DL cũng rất nhạy cảm với sự sai khác giữa pip_ipi​ và qiq_iqi​

Trong các bài toán Machine Learning/Deep Learning, do Entropy(Phường) là không đổi (Phường là phân phối target -> không đổi) nên tối ưu hàm KL_Divergence cũng tương đương với tối ưu hàm CrossEntropy. Nói các khác, việc bạn dùng KL_Divergence hay CrossEntropy trong Machine Learning là như nhau (trong các ngành khác thì không).

1. Machine learning summary fundamental – https://jonathan-hui.medium.com

2. KL Divergence Demystified – Medium.com

3. What is Cross-Entropy in Machine learning? – https://medium.com