Bài giảng Khoa học máy tính - Bài 3: Entropy, entropy tương đối và thông tin tương hỗ - Nguyễn Phương Thái
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: http://coltech.vnu.edu.vn/~thainp/
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ụ
1 ꢑớꢒ ꢂáꢓ ꢔꢕấꢖ ꢁ
0 ꢑớꢒ ꢂáꢓ ꢔꢕấꢖ 1 − ꢁ
Giả sử : ꢄ =
ꢐ
( )
( )
(
)
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 :
( ) ( )
ꢅ ꢄ|ꢘ = ꢅ ꢄ, ꢘ − ꢅ(ꢘ)
ꢝ
ꢝ
1 1 1 1
ꢅ ꢄ, ꢘ = − ꢆ ꢆ ꢁ ꢂ, ꢙ ꢇꢈꢉꢁ(ꢂ, ꢙ) = − 2 ꢇꢈꢉ − ꢇꢈꢉ − 6 ꢇꢈꢉ
8 8 4 4 16 16
1
1
( )
( )
ꢚꢞꢎ
ꢊꢞꢎ
1
1 3 1 3 5 6 + 4 + 12 + 5 27
− 4 ꢇꢈꢉ = + + + =
32 32 4 2 2 8
=
8
8
27
11
8
( | )
ꢅ ꢄ ꢘ = − 2 =
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.
Tải về để xem bản đầy đủ
23 trang
22700
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Khoa học máy tính - Bài 3: Entropy, entropy tương đối và thông tin tương hỗ - Nguyễn Phương Thái", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_khoa_hoc_may_tinh_bai_3_entropy_entropy_tuong_doi.pdf
