Báo cáo: LÝ THUYẾT THÔNG TIN

Chia sẻ: Chao Hello | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

182
lượt xem 19
download

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

THÔNG TIN là một đại lượng toán học dùng để đo lượng tin không chắc (hay lượng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trước. Hay một số tài liệu tiếng anh gọi là Uncertainty Measure. Ý nghĩa entropy: Entropy thông tin mô tả mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên. Nói cách khác, entropy cũng chỉ ra có bao nhiêu thông tin trong tín hiệu, với thông tin là các phần không hỗn loạn ngẫu nhiên của tín hiệu....

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo: LÝ THUYẾT THÔNG TIN

LÝ LÝ THUYẾT THÔNG TIN
ENTROPY ENTROPY Định nghĩa entropy: Entropy là một đại lượng toán học dùng để đo lượng tin không chắc (hay lượng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trước. Hay một số tài liệu tiếng anh gọi là Uncertainty Measure. Ý nghĩa entropy: nghĩa Entropy thông tin mô tả mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên. Nói cách khác, entropy cũng chỉ ra có bao nhiêu thông tin trong tín hiệu, với thông tin là các phần không hỗn loạn ngẫu nhiên của tín hiệu. Ở đây ta chỉ nghiên cứu các sự kiện ngẫu nhiên rời rạc.
Entropy của một sự kiện Giả sử có một sự kiện A có xác suất xuất hiện là p. Khi đó, ta nói A có một lượng không chắc chắn được đo bởi hàm số h(p) với p ⊆ [0,1]. Hàm h(p) được gọi là Entropy nếu nó thoả 2 tiêu đề toán học sau: Tiên đề 1: h(p) là hàm liên tục không âm và đơn điệu giảm. Tiên đề 2: nếu A và B là hai sự kiện độc lập nhau, có xác suất xuất hiện lần lượt là pA và pB. Khi đó, p(A,B) = pA.pB nhưng h(A,B) = h(pA) + h(pB).
Entropy của một phân phối Xét biến ngẫu nhiên rời rạc X có phân phối: X x1 x2 … xn P p1 p2 … pn Nếu gọi Ai là sự kiện X=xi, (i=1,2,3,..) thì Entropy của Ai là: h(Ai)=h(pi) Gọi Y=h(X) là hàm ngẫu nhiên của X và nhận các giá trị là dãy các Entropy của các sự kiện X=xi, tức là Y=h(X)={h(p1), h(p2), …, h(pn)} Vậy, Entropy của X chính là kỳ vọng toán học của hàm Y=h(X) có dạng: H(X)=H(p1, p2, p3, …,pn) = p1h(p1)+ p2h(p2)+…+pnh(pn). Tổng quát: n H ( X ) = ∑ pi h( pi ) i =1
Dạng Dạng giải tích của entropy h(p)=-log2(p) (đvt: bit) Do đó, 1 n n H ( X ) = −∑ p(i ) log 2 p (i ) = ∑ p(i ) log 2    p (i )  i =1 i =1 Qui ước trong cách viết: log(pi)= log2(pi)
Lượng thông tin Shannon của 1 kết cục x : Lượng 1 h ( x ) = log 2 p ( x)
Ví Ví dụ Một dòng chữ luôn chỉ có các ký tự "a" sẽ có entropy bằng 0, vì ký tự tiếp theo sẽ luôn là "a". Nếu sự kiện A có xác suất xuất hiện là 1/2 thì h(A)=h(1/2)= -log(1/2) = 1 (bit) Một Một dòng chữ chỉ có hai ký tự 0 và 1 ngẫu nhiên hoàn toàn sẽ có entropy là 1 bit cho mỗi ký tự. mỗi
Ví Ví dụ Xét biến ngẫu nhiên X có phân phối như sau X x1 x2 x3 P 1/2 1/4 1/4 H(X) H(X) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit)
Tính Tính chất 1 H ( p1 , p2 ,..., pn ) = H ( p1 + p2 + ... + pr , pr +1 + pr + 2 + ... + pn )   p  pr + ( p1 + p2 + ... + pr ) H  r  1 ,..., r    ∑ pi ∑ pi   i =1  i =1   p  p + ( pr +1 + pr + 2 + ... + pn ) H  n r +1 ,..., n n     ∑ pi ∑1 pi   i = r +1  i =r +
Tính Tính chất 2: Định lý cực đại của entropy H(p1, p2, …,pn)≤ log(n) Trong đó: đẳng thức xảy ra khi và chỉ khi p1=…= pn= 1/n
Bài Bài tập Xét con xúc sắc có 6 mặt với xác suất xuất hiện các mặt được cho trong bảng sau: X x1 x2 x3 x4 x5 x6 P 10% 20% 25% 25% 15% 5% Ta có thể gom các sự kiện x1, x2, x3 lại thành một sự kiện mới là x123 có xác suất xuất hiện là 55%, gom sự kiện x5 và x6 lại thành sự kiện x56 có xác suất 20%. Ta được một biến ngẫu nhiên mới X* có phân phối sau: X* x123 x4 x56 P 55% 25% 20% Kiểm tra tính chất tính chất 1 và 2?
ENTROPY ENTROPY CỦA NHIỀU BiẾN
Định Định nghĩa entropy của nhiều biến Giả sử X và Y là 2 biến ngẫu nhiên cho trước với pịj = p(X=xi,Y=yj) (∀ i=1,..,n và j=1,…,m). Khi đó, Entropy H(X,Y) có dạng: n m H ( X , Y ) = −∑∑ pij log 2 pij i =1 j =1
Ví Ví dụ entropy của nhiều biến Cho 2 BNN X và Y độc lập nhau và có các phân phối: X 0 1 P 1/2 1/2 Y 0 1 2 P 1/4 1/2 1/4 Lập phân phối của (X, Y) a) Tìm H (X,Y) b) H(X,Y) =H(0.125, 0.25, 0.125, 0.125, 0.25, 0.125)=2.5 (Bit)
Entropy có điều kiện Entropy của Y với điều kiện X=xi (i=1,..,n): m H (Y / X = xi ) = −∑ p ( y j / xi ) log p ( y j / xi ) j =1 Entropy của Y với điều kiện X : n H (Y / X ) = −∑ p ( xi ) H (Y / X = xi ) i =1
Bài Bài tập: Cho biến ngẫu nhiên X, Y có bảng phân phối đồng thời sau: 1 2 3 4 X Y 1 1/8 1/16 1/32 1/32 2 1/16 1/8 1/32 1/32 3 1/16 1/16 1/16 1/16 4 1/4 0 0 0 Tính H(X,Y) a) a) H(X/Y) ; H(Y/X) b)
Homework Two zero memory sources A1 and A2 have N1 and N2 symbols respectively. The probabilities of alphabet A1 are P, and the probabilities of A2 are Q: A1={ a1 ..............aN1 } P={ p1..............pN1 } A2={ a1 ..............aN2 } Q={ q1..............qN2 } The probabilities for each source both sum to 1, i.e., 1 2 ∑ p = ∑q =1 i i i =1 i =1
A composite source A={A1,A2} is formed by combining A1 and A2. The probabilities of A1 are multiplied by r , and the probabilities of A2 are multiplied by r *, where r*=1-r. In this way the probabilities of the composite source sum to 1. 1. Show that the entropy of the composite source has the form H(A)=rH(A1)+ r*H(A2)+H(r, r*) 2. Interpret the above result. Consider the special case of when r=0.5. 3. Find the value of r which optimizes (maximizes) H(A) in terms of H(A1) and H(A2)