Bài giảng 3: Entropy, entropy tương đối và thông tin tương hỗ - Nguyễn Phương Thái

Chia sẻ: Nguyễn Thị Huyền | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

222
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Entropy; Entropy hợp và entropy điều kiện; Entropy tương đối và thông tin tương hỗ; các quy tắc nhân cho entropy, entropy tương đối, và thông tin tương hỗ;... là những nội dung chính mà "Bài giảng 3: Entropy, entropy tương đối và thông tin tương hỗ" hướng đến trình bày.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng 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 ớ á ấ Giả sử : = 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 : ( | )= ( , )− ( ) 1 1 1 1 1 1 ( , )=− ( , ) ( , )=−2 − −6 8 8 4 4 16 16 1 1 3 1 3 5 6 + 4 + 12 + 5 27 −4 = + + + = = 32 32 4 2 2 8 8 8 27 11 ( | )= −2= 8 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.