Bài giảng Khoa học Máy tính - 3. Entropy, entropy tương đối và thông tin tương hỗ

Bài giảng 3. Entropy, entropy tương đối và thông tin tương hỗ Giảng viên: Nguyễn Phương Thái Bộ môn Khoa học Máy tính Trang web cá nhân: Trợ giảng: Nguyễn Kim Anh Nội dung bài giảng - Entropy - Entropy hợp và entropy điều kiện - Entropy tương đối và thông tin tương hỗ - Các qui tắc nhân cho entropy, entropy tương đối, và thông tin tương hỗ - Bất đẳng thức Jensen và hệ quả - Bất đẳng thức tổng log và ứng dụng - Bất đẳng thức xử lý dữ liệu - Thống kê đủ - Bất đẳng thức Fano Entropy Entropy là độ đo mức độ không chắc chắn của biến ngẫu nhiên (bnn). Giả sử X là một bnn rời rạc với bảng chữ cái ߯ và hàm pmf ݌(ݔ) = ܲ{ܺ = ݔ}, ݔ ∈ ߯ ܪ(ܺ) = − ෍ ݌(ݔ)݈݋݃݌(ݔ) ௫∈ఞ = ܧ௣݈݋݃ 1 ݌(ܺ) Chú ý : - Ta cũng có thể viết H(p) để thể hiện đại lượng trên. Log tính theo cơ số 2 và entropy được tính theo bit. Ta cũng qui ước rằng 0log0=0 để tiện cho việc tính toán. - Ta có : ܪ(ܺ) = ܧ௣݈݋݃ ଵ ௣(௑) Ví dụ Giả sử : ܺ = ቊ 1 ݒớ݅ ݔáܿ ݏݑấݐ ݌ 0 ݒớ݅ ݔáܿ ݏݑấݐ 1 − ݌
Khi đó: ܪ(ܺ) = ܪ(݌) = −݌݈݋݃݌ − (1 − ݌)log (1 − ݌) Hình 1. Quan hệ giữa p và H(p) Entropy hợp và entropy điều kiện Entropy hợp của một cặp bnn rời rạc (X, Y) với phân phối hợp p(x, y) là: ܪ(ܺ, ܻ) = − ෍ ෍ ݌(ݔ, ݕ)݈݋݃݌(ݔ, ݕ) ௬∈௒௫∈ఞ Hay ܪ(ܺ, ܻ) = −ܧ݈݋݃݌(ܺ, ܻ) Entropy điều kiện: ܪ(ܻ|ܺ) = − ෍ ෍ ݌(ݔ, ݕ)݈݋݃݌(ݕ|ݔ) ௬∈௒௫∈ఞ = −ܧ݈݋݃݌(ܻ|ܺ) Luật xích ܪ(ܺ, ܻ) = ܪ(ܺ) + ܪ(ܻ|ܺ) Hệ quả: ܪ(ܺ, ܻ|ܼ) = ܪ(ܺ|ܼ) + ܪ(ܻ|ܺ, ܼ) Ví dụ Giả sử (X, Y) có phân phối hợp sau: Hình 2. Hàm pmf phụ thuộc p(x,y) Hãy tính H(X), H(Y), H(X|Y). Ví dụ (tiếp) Phân phối lề của X là (1/2, 1/4, 1/8, 1/8) và của Y là (1/4, 1/4, 1/4, 1/4). Do đó H(X)=7/4 và H(Y)=2. Từ luật xích ta suy ra : ܪ(ܺ|ܻ) = ܪ(ܺ, ܻ) − ܪ(ܻ) ܪ(ܺ, ܻ) = − ෍ ෍ ݌(ݔ, ݕ)݈݋݃݌(ݔ, ݕ) ସ ௬ୀଵ = ସ ௫ୀଵ − 2 1 8 ݈݋݃ 1 8 − 1 4 ݈݋݃ 1 4 − 6 1 16 ݈݋݃ 1 16 − 4 1 32 ݈݋݃ 1 32 = 3 4 + 1 2 + 3 2 + 5 8 = 6 + 4 + 12 + 5 8 = 27 8 ܪ(ܺ|ܻ) = 27 8 − 2 = 11 8 Entropy tương đối Entropy tương đối hay khoảng cách Kullback-Leibler giữa hai hàm pmf p(x) và q(x) là : ܦ(݌||ݍ) = ෍ ݌(ݔ)݈݋݃ ݌(ݔ) ݍ(ݔ) ௫∈ఞ = ܧ௣݈݋݃ ݌(ܺ) ݍ(ܺ) Chú ý : - Entropy tương đối không phải khoảng cách thực sự vì nó không đối xứng và không thỏa mãn bđt tam giác - Tuy vậy, để dễ hình dung, ta có thể coi Entropy tương đối là "khoảng cách" Thông tin tương hỗ Giả sử X và Y là các bnn với hàm pmf phụ thuộc là p(x,y) và các hàm pmf biên là p(x) và p(y). Thông tin tương hỗ I(X ;Y) là độ đo cho ta biết bnn này chứa bao nhiêu thông tin về bnn khác. Nó được tính bởi entropy tương đối giữa phân phối phụ thuộc và phân phối tích p(x)p(y) : ܫ(ܺ; ܻ) = ∑ ∑ ݌(ݔ, ݕ)݈݋݃ ௣(௫,௬) ௣(௫)௣(௬) = ܦ(݌(ݔ, ݕ)|ห݌(ݔ)݌(ݕ)൯ = ܧ௣(௫,௬)݈݋݃ ௣(௑,௒) ௣(௑)௣(௒)௬௫ Ví dụ Giả sử ߯ = {0,1} và p và q là hai phân phối trên đó. Giả sử p(0)=1-r, p(1)=r và q(0)=1-s, q(1)=s. Khi đó: ܦ(݌||ݍ) = (1 − ݎ)݈݋݃ 1 − ݎ 1 − ݏ + ݎ݈݋݃ ݎ ݏ Và ܦ(ݍ||݌) = (1 − ݏ)݈݋݃ 1 − ݏ 1 − ݎ + ݏ݈݋݃ ݏ ݎ Nếu r=s thì D(p||q)=D(q||p)=0. Nếu r=1/2 và s=1/4 thì ܦ(݌||ݍ) = 1 − ଵ ଶ ݈݋݃3 = 0.2075bit Còn ܦ(ݍ||݌) = ଷ ସ ݈݋݃3 − 1 = 0.1887bit Quan hệ giữa entropy và thông tin tương hỗ Hình 3. Quan hệ giữa entropy và thông tin tương hỗ Hình vẽ minh họa các pt sau: ܫ(ܺ; ܻ) = ܪ(ܺ) − ܪ(ܺ|ܻ) ܫ(ܺ; ܻ) = ܪ(ܻ) − ܪ(ܻ|ܺ) Quan hệ giữa entropy và thông tin tương hỗ (tiếp) ܫ(ܺ; ܻ) = ܪ(ܺ) + ܪ(ܻ) − ܪ(ܺ, ܻ) ܫ(ܺ; ܻ) = ܫ(ܻ; ܺ) ܫ(ܺ; ܺ) = ܪ(ܺ) Luật xích cho entropy Giả sử X1, X2, , Xn là các bnn có hàm phân phối phụ thuộc là p(x1, x2, , xn). Khi đó: ܪ( ଵܺ, ܺଶ, , ܺ௡) = ෍ ܪ( ௜ܺ| ௜ܺିଵ, , ଵܺ) ௡ ௜ୀଵ Chứng minh: Luật xích cho thông tin tương hỗ ܫ( ଵܺ, ܺଶ, , ܺ௡; ܻ) = ෍ ܫ( ௜ܺ; ܻ| ௜ܺିଵ, , ଵܺ) ௡ ௜ୀଵ Chứng minh: Trong đó, thông tin tương hỗ có điều kiện của các bnn X và Y cho trước Z là: ܫ(ܺ; ܻ|ܼ) = ܪ(ܺ|ܼ) − ܪ(ܺ|ܻ, ܼ) = ܧ௣(௫,௬,௭)݈݋݃ ݌(ܺ, ܻ|ܼ) ݌(ܺ|ܼ)݌(ܻ|ܼ) Luật xích cho entropy tương đối ܦ(݌(ݔ, ݕ)||ݍ(ݔ, ݕ)) = ܦ(݌(ݔ)||ݍ(ݔ)) + ܦ(݌(ݕ|ݔ)||ݍ(ݕ|ݔ)) Chứng minh: Trong đó, entropy tương đối có điều kiện là: ܦ(݌(ݕ|ݔ)|หݍ(ݕ|ݔ)൯ = ෍ ݌(ݔ) ௫ ෍ ݌(ݕ|ݔ)݈݋݃ ݌(ݕ|ݔ) ݍ(ݕ|ݔ) = ܧ௣(௫,௬)݈݋݃ ݌(ܻ|ܺ) ݍ(ܻ|ܺ) ௬ Bất đẳng thức Jensen và hệ quả Hàm lồi: Hàm f(x) được gọi là lồi (convex) trên khoảng (a,b) nếu với mọi x1,x2 thuộc (a,b) và 0 ≤ ߣ ≤ 1: ݂(ߣݔଵ + (1 − ߣ)ݔଶ) ≤ ߣ݂(ݔଵ) + (1 − ߣ)݂(ݔଶ) Một hàm f được gọi là lồi chặt nếu dấu bằng xảy ra chỉ nếu ߣ = 1 hay ߣ = 0. Ví dụ: ݔଶ, |ݔ|, ݁௫, ݔ݈݋݃ݔ (ݔ ≥ 0) Hàm lõm: Hàm f là lõm nếu –f là hàm lồi. Ví dụ: ݈݋݃ݔ, √ݔ (ݔ ≥ 0) Định lý: Nếu hàm f có đạo hàm bậc hai không âm trên một khoảng thì hàm đó là lồi trên khoảng đó. Bất đẳng thức Jensen và hệ quả (tiếp) Hình 4. Hàm lồi (a) và hàm lõm (b) Bất đẳng thức Jensen và hệ quả (tiếp) Bất đẳng thức (bđt) Jensen: Nếu f là một hàm lồi và X là một bnn: ܧ݂(ܺ) ≥ ݂(ܧܺ) Hơn nữa, nếu f là hàm lồi chặt thì đẳng thức ngụ ý rằng X=EX với xác suất 1. Bđt thông tin: Giả sử p(x) và q(x) là hai hàm pmf, khi đó: ܦ(݌||ݍ) ≥ 0 Dấu bằng xảy ra khi và chỉ khi p(x)=q(x) với mọi x. Tính không âm của thông tin tương hỗ: ܫ(ܺ; ܻ) ≥ 0 Dấu bằng xảy ra khi và chỉ khi X và Y độc lập. Bất đẳng thức Jensen và hệ quả (tiếp) Hệ quả: ܦ(݌(ݕ|ݔ)||ݍ(ݕ|ݔ)) ≥ 0 Dấu bằng xảy ra khi và chỉ khi p(y|x)=q(y|x) với mọi y và x sao cho p(x)>0. Hệ quả : ܫ(ܺ; ܻ|ܼ) ≥ 0 Dấu bằng xảy ra khi và chỉ khi X và Y là độc lập có điều kiện cho trước Z. Định lý : ܪ(ܺ) ≤ ݈݋݃|߯| trong đó |߯| là số phần tử trong khoảng của X, dấu bằng xảy ra khi và chỉ khi X có phân phối đều. Bất đẳng thức Jensen và hệ quả (tiếp) Có điều kiện làm giảm entropy : ܪ(ܺ|ܻ) ≤ ܪ(ܺ) Dấu bằng xảy ra khi và chỉ khi X và Y là độc lập. Ý nghĩa : Biết thêm bnn Y có thể làm giảm độ không chắc chắn của X. Chú ý rằng điều này chỉ đúng theo trung bình (vì H(X|Y=y) có thể lớn hơn, hay nhỏ hơn, hay bằng H(X)). Ví dụ, trong phiên tòa, một chứng cứ mới nào đấy có thể làm tăng sự không chắc chắn, tuy nhiên theo trung bình thì chứng cứ làm giảm sự không chắc chắn. Bất đẳng thức Jensen và hệ quả (tiếp) Giả sử X và Y là các bnn có hàm phân phối phụ thuộc sau: Hình 5. Hàm phân phối phụ thuộc p(x,y) Khi đó ta dễ dàng tính được: H(X)=H(1/8,7/8)=0.544 bit, H(X|Y=1)=0 bit, và H(X|Y=2) = 1 bit. Trong khi: ܪ(ܺ|ܻ) = ଷ ସ ܪ(ܺ|ܻ = 1) + ଵ ସ ܪ(ܺ|ܻ = 2) = 0.25 bit. Do đó, sự không chắc chắn của X tăng nếu biết Y=2, giảm nếu biết Y=1, nhưng tăng theo trung bình. Bất đẳng thức Jensen và hệ quả (tiếp) Biên độc lập của entropy : Giả sử X1, , Xn là các bnn có hàm pmf phụ thuộc là p(x1, , xn). Khi đó : ܪ( ଵܺ, , ܺ௡) ≤ ෍ ܪ( ௜ܺ) ௡ ௜ୀଵ Dấu bằng xảy ra khi và chỉ khi các Xi là độc lập.