LÝ THUYẾT THÔNG TIN LÝ THUYẾT THÔNG TIN LÝ THUYẾT THÔNG TIN LÝ THUYẾT THÔNG TIN
ENTROPY ENTROPY
Định nghĩa 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: Entropy thông tin mô tả mức độ hỗn loạn trong một tín hiệu lấy từ 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 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 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. 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. Ở đâ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é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).
n
Tổng quát:
H X (
)
)
p h p ( i i
= ∑
i
= 1
Dạng giải tích của entropy Dạng giải tích của entropy
h(p)=-log2(p) (đvt: bit)
Do đó,
n
n
H X (
)
= −
p i
( ) log
p i ( )
=
p i
( ) log
2
2
∑
∑
1 p i ( )
i
i
= 1
= 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 x :: Lượng thông tin Shannon của 1 kết cục
=
log
( ) h x
2
1 ( ) p x
Ví dụ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ự 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". 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 dòng chữ chỉ có hai ký tự 0 và 1 ngẫu nhiên hoàn toàn sẽ có 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ự entropy là 1 bit cho mỗi ký tự..
Ví dụVí dụ
Xét biến ngẫu nhiên X có phân phối như sau Xét biến ngẫu nhiên X có phân phối như sau
X
P
x1 1/2
x2 1/4
x3 1/4
H(X) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit) H(X) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit)
Tính chất 1 Tính chất 1
+ 1
+
2
( , ,..., ) = + + + ... + + + ... ) H p p 1 2 p n H p ( 1 p 2 p p , r r p r p n
r
r
p 1 p r + + ( + + ... ,..., p 1 p 2 p H ) r
∑
∑
i i
= 1 1 =
i i
= 1 1 =
p i p i
+ 1
+ 1
+
2
+ ( + + + ... ,..., p r p r ) p H n p r n p n n
∑
∑
= + 1 i r
= + 1 i r
p i p i
Tính chất 2: Định lý cực đại của entropy 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 tập 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%
X*
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ự 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: x56 x123
x4
P
55%
25%
20%
Kiểm tra tính chất tính chất 1 và 2?
ENTROPY CỦA NHIỀU BiẾN ENTROPY CỦA NHIỀU BiẾN
Định nghĩa entropy của nhiều biến Đị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 ( ( H X Y
, ,
) )
log log
p p ij ij
2 2
p p ij ij
= −∑∑ = −∑∑
i
= 1
j
= 1
Ví dụ entropy của nhiều biến 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 P
1/4 1/4
1/2 1/2
1/4 1/4
a)
b)
Lập phân phối của (X, Y) Tìm H (X,Y)
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
=
(
)
/
log
/
H Y X x / i
j
x i
j
x i
( p y
)
( p y
)
= −∑
j
= 1
Entropy của Y với điều kiện X :
n
H Y X
(
/
)
= −
=
(
)
/
)
p x H Y X x ( i
i
∑
i
= 1
Bài tập: Cho biến ngẫu nhiên X, Y có bảng phân phối đồng thời sau: Bài tập: Cho biến ngẫu nhiên X, Y có bảng phân phối đồng thời sau:
X
1
2
3
4
Y
1/8
1/16
1/32
1/32
1
1/16
1/8
1/32
1/32
2
1/16
1/16
1/16
1/16
3
1/4
0
0
0
4
Tính Tính
a)a)
b)b)
H(X,Y) H(X,Y) H(X/Y) ; H(Y/X) H(X/Y) ; H(Y/X)
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 } A1={ a1 ..............aN1 } A2={ a1 ..............aN2 }
P={ p1..............pN1 } P={ p1..............pN1 } Q={ q1..............qN2 }
(cid:13)
(cid:13) 1
2
=
1
q i
The probabilities for each source both sum to 1, i.e., ∑ ∑ = p i
= 1
= 1
i
i
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*) 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)
