Báo cáo: LÝ THUYẾT THÔNG TIN ppsx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (217.9 KB, 18 trang )
LÝ THUYẾT THÔNG TINLÝ THUYẾT THÔNG TIN
LÝ THUYẾT THÔNG TINLÝ THUYẾT THÔNG TIN
ENTROPYENTROPY
Đị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ó baomộ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ỗnnhiê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à p
A
và p
B
.
Khi đó, p(A,B) = p
A
.p
B
nhưng h(A,B) = h(p
A
) + h(p
B
).
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:
Nếu gọi A
i
là sự kiện X=x
i
, (i=1,2,3, ) thì Entropy của A
i
là: h(A
i
)=h(p
i
)
X x
1
x
2
… x
n
P p
1
p
2
… p
n
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=x
i
, tức là Y=h(X)={h(p
1
), h(p
2
), …, h(p
n
)}
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(p
1
, p
2
, p
3
, …,p
n
) = p
1
h(p
1
)+ p
2
h(p
2
)+…+p
n
h(p
n
).
Tổng quát:
1
( ) ( )
n
i i
i
H X p h p
=
=
∑
Dạng giải tích của entropyDạng giải tích của entropy
h(p)=-log
2
(p) (đvt: bit)
Do đó,
2 2
1 1
1
( ) ( )log ( ) ( )log
( )
n n
i i
H X p i p i p i
p i
= =
= − =
∑ ∑
Qui ước trong cách viết: log(p
i
)= log
2
(p
i
)
Lượng thông tin Shannon của 1 kết cục Lượng thông tin Shannon của 1 kết cục
x x
::
( )
( )
2
1
logh x
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 entropy là 1 bit cho
mỗi ký tựmỗi ký tự
Ví dụVí dụ
Xét biến ngẫu nhiên X có phân phối như sauXét biến ngẫu nhiên X có phân phối như sau
X x
1
x
2
x
3
P 1/2 1/4 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 1Tính chất 1
1 2 1 2 1 2
1
1 2
1 1
( , , , ) ( , )
( ) , ,
n r r r n
r
r
r r
i i
i i
H p p p H p p p p p p
p p
p p p H
p p
+ +
= =
= + + + + + +
+ + + +
∑ ∑
1 1
1
1 2
1 1
( ) , ,
i i
n
r
r r n
n n
i i
i r i r
p
p
p p p H
p p
= =
+
+ +
= + = +
+ + + +
∑ ∑
Tính chất 2: Định lý cực đại của entropyTính chất 2: Định lý cực đại của entropy
H(p
1
, p
2
, …,p
n
)≤ log(n)
Trong đó: đẳng thức xảy ra khi và chỉ khi p
1
=…= p
n
= 1/n
Bài tậpBà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:
Ta có thể gom các sự kiện x
1
, x
2
, x
3
lại thành một sự kiện mới là
x
123
có xác suất xuất hiện là 55%, gom sự kiện x
5
và x
6
lại thành sự
X x
1
x
2
x
3
x
4
x
5
x
6
P 10% 20% 25% 25% 15% 5%
x
123
có xác suất xuất hiện là 55%, gom sự kiện x
5
và x
6
lại thành sự
kiện x
56
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:
Kiểm tra tính chất tính chất 1 và 2?
X* x
123
x
4
x
56
P 55% 25% 20%
ENTROPY CỦA NHIỀU BiẾNENTROPY 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=x
i
,Y=y
j
)
(∀ i=1, ,n và j=1,…,m).
Khi đó, Entropy H(X,Y) có dạng:
2
( , ) log
n m
ij ij
H X Y p p
= −
∑∑
2
1 1
( , ) log
ij ij
i j
H X Y p p
= =
= −
∑∑
Ví dụ entropy của nhiều biếnVí 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
a) Lập phân phối của (X, Y)
b) Tìm H (X,Y)
H(X,Y) =H(0.125, 0.25, 0.125, 0.125, 0.25, 0.125)=2.5 (Bit)
P
1/4
1/2
1/4
Entropy có điều kiện
Entropy của Y với điều kiện X=xi (i=1, ,n):
( ) ( )
1
( / ) / log /
m
i j i j i
j
H Y X x p y x p y x
=
= = −
∑
Entropy của Y với điều kiện X :
1
( / ) ( ) ( / )
n
i i
i
H Y X p x H Y X x
=
= − =
∑
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:
1 2 3 4
1 1/8 1/16 1/32 1/32
2 1/16 1/8 1/32 1/32
Y
X
Tính Tính
a)a) H(X,Y)H(X,Y)
b)b) H(X/Y) ; H(Y/X)H(X/Y) ; H(Y/X)
3 1/16 1/16 1/16 1/16
4 1/4 0 0 0
Homework
Two zero memory sources A
1
and A
2
have N
1
and N
2
symbols respectively. The probabilities of alphabet A
1
are P,
and the probabilities of A
2
are Q:
A
1
={ a
1
a
N1
}
P={ p
1
p
N1
}
A
1
={ a
1
a
N1
}
P={ p
1
p
N1
}
A
2
={ a
1
a
N2
} Q={ q
1
q
N2
}
The probabilities for each source both sum to 1, i.e.,
1 2
1 1
1
i i
i i
p q
= =
= =
∑ ∑
A composite source A={A
1
,A
2
} is formed by combining A
1
and A
2
. The probabilities of A
1
are multiplied by r , and the
probabilities of A
2
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)=
r
H(A1)+
r*
H(A2)+H(
r, r*
)
H(A)=
r
H(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(A
1
) and H(A
2
)
