Giáo trình: Lý thuyết thông tin.H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi )i
Số trang: 16
Loại file: pdf
Dung lượng: 691.56 KB
Lượt xem: 19
Lượt tải: 0
Xem trước 2 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Giáo trình: Lý thuyết thông tin.
H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi )
i =1
M
Qui ước trong cách viết: log(pi)= log2(pi)
Ví dụ minh họ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) Xét BNN X có phân phối sau: X P x1 x2 1/2 1/4 x3 1/4
H(X) = H(1/2, 1/4, 1/4) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit)
Bài toán về cây tìm kiếm nhị phân-Đặt vấn đề
Giả sử, tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau: X x1...
Nội dung trích xuất từ tài liệu:
Giáo trình: Lý thuyết thông tin.H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi )i Giáo trình: Lý thuyết thông tin. M H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi ) i =1 Qui ước trong cách viết: log(pi)= log2(pi) Ví dụ minh họ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) Xét BNN X có phân phối sau: X x1 x2 x3 P 1/2 1/4 1/4 H(X) = H(1/2, 1/4, 1/4) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit) Bài toán về cây tìm kiếm nhị phân-Đặt vấn đề Giả sử, tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau: X x1 x2 x3 x4 x5 P 0,2 0,3 0,2 0,15 0,15 Trong đó: x1, …x5 lần lượt là tên của 5 người mà ta cần nhận ra với cách xác định tên bằng câu hỏi đúng sai (yes/no). Sơ đồ dưới đây minh họa cách xác định tên của một người: x1 Yes X=x1? X=x1/x2? Yes x2 No x3 No Yes X=x3? x4 Yes X=x4? No x5 No Bài toán về cây tìm kiếm nhị phân - Diễn giải Theo sơ đồ trên: Để tìm x1, x2, x3 với xác suất tương ứng là 0.2, 0.3, 0.2 ta chỉ cần tốn 2 câu hỏi. Để tìm x4, x5 với xác suất tương ứng 0.15, 0.15 thì ta cần 3 câu hỏi. Vậy: Số câu hỏi trung bình là: 2 x (0,2+0,3+0,2) + 3 x (0,15+0,15) = 2.3 Mặt khác: Entropy của X: H(X)= H(0.2, 0.3, 0.2, 0.15, 0.15)=2.27. Ta luôn có số câu hỏi trung bình luôn ≥ H(X) (theo định lý Shannon sẽ trình bày sau). Vì số câu hỏi trung bình trong trường hợp này xấp sỉ H(X) nên đây là số câu hỏi trung bình tối ưu để tìm ra tên chính xác của một người. Do đó, sơ đồ tìm kiếm trên là sơ đồ tối ưu. 17 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. Giáo trình: Lý thuyết thông tin. Sinh viên tự cho thêm 1 hay 2 sơ đồ tìm kiếm khác và tự diễn giải tương tự - xem như bài tập. Bài tập Tính H(X) với phân phối sau: X x1 x2 x3 P 1/3 1/3 1/3 Tính H(Y) với phân phối sau: Y x1 x2 x3 x4 P 1/6 2/6 1/6 2/6 18 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. Giáo trình: Lý thuyết thông tin. BÀI 2.2: CÁC TÍNH CHẤT CỦA ENTROPY Mục tiêu: Sau khi hoàn tất bài học này bạn có thể: - Hiểu các tính chất cơ bản của Entropy, - Hiểu định lý cực đại của Entropy, - Vận dụng giải một số bài toán về Entropy, - Làm cơ sở để vận dụng giải quyết các bài toán tính dung lượng kênh truyền. Các tính chất cơ bản của Entropy Xét biến ngẫu nhiên X = {x1, x2, …, xM}. Entropy của biến ngẫu nhiên X có các tính chất: 1 1 1. Hàm số f(M) = H( ,…, ) đơn điệu tăng. M M 2. Hàm số f(ML) = f(M)+f(L). 3. H(p1, p2, …, pM) = H(p1 + p2 +…+pr, pr+1+ pr+2+…+ pM) p p + (p1 + p 2 + … + p r )H( r 1 ,..., r r ) ∑i=1 pi ∑i =1 pi pr +1 pM + (p r +1 + p r + 2 + … + p M )H( ,..., ) ∑i=r +1 pi ∑i=r +1 pi M M 4. H(p, 1-p) là hàm liên tục theo P. Minh họa tính chất 1 và 2 Minh họa tính chất 1: Trong trường hợp biến ngẫu nhiên X có phân phối đều Entropy của X như sau : ⎛1 1⎞ ...
Nội dung trích xuất từ tài liệu:
Giáo trình: Lý thuyết thông tin.H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi )i Giáo trình: Lý thuyết thông tin. M H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi ) i =1 Qui ước trong cách viết: log(pi)= log2(pi) Ví dụ minh họ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) Xét BNN X có phân phối sau: X x1 x2 x3 P 1/2 1/4 1/4 H(X) = H(1/2, 1/4, 1/4) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit) Bài toán về cây tìm kiếm nhị phân-Đặt vấn đề Giả sử, tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau: X x1 x2 x3 x4 x5 P 0,2 0,3 0,2 0,15 0,15 Trong đó: x1, …x5 lần lượt là tên của 5 người mà ta cần nhận ra với cách xác định tên bằng câu hỏi đúng sai (yes/no). Sơ đồ dưới đây minh họa cách xác định tên của một người: x1 Yes X=x1? X=x1/x2? Yes x2 No x3 No Yes X=x3? x4 Yes X=x4? No x5 No Bài toán về cây tìm kiếm nhị phân - Diễn giải Theo sơ đồ trên: Để tìm x1, x2, x3 với xác suất tương ứng là 0.2, 0.3, 0.2 ta chỉ cần tốn 2 câu hỏi. Để tìm x4, x5 với xác suất tương ứng 0.15, 0.15 thì ta cần 3 câu hỏi. Vậy: Số câu hỏi trung bình là: 2 x (0,2+0,3+0,2) + 3 x (0,15+0,15) = 2.3 Mặt khác: Entropy của X: H(X)= H(0.2, 0.3, 0.2, 0.15, 0.15)=2.27. Ta luôn có số câu hỏi trung bình luôn ≥ H(X) (theo định lý Shannon sẽ trình bày sau). Vì số câu hỏi trung bình trong trường hợp này xấp sỉ H(X) nên đây là số câu hỏi trung bình tối ưu để tìm ra tên chính xác của một người. Do đó, sơ đồ tìm kiếm trên là sơ đồ tối ưu. 17 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. Giáo trình: Lý thuyết thông tin. Sinh viên tự cho thêm 1 hay 2 sơ đồ tìm kiếm khác và tự diễn giải tương tự - xem như bài tập. Bài tập Tính H(X) với phân phối sau: X x1 x2 x3 P 1/3 1/3 1/3 Tính H(Y) với phân phối sau: Y x1 x2 x3 x4 P 1/6 2/6 1/6 2/6 18 Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu. Giáo trình: Lý thuyết thông tin. BÀI 2.2: CÁC TÍNH CHẤT CỦA ENTROPY Mục tiêu: Sau khi hoàn tất bài học này bạn có thể: - Hiểu các tính chất cơ bản của Entropy, - Hiểu định lý cực đại của Entropy, - Vận dụng giải một số bài toán về Entropy, - Làm cơ sở để vận dụng giải quyết các bài toán tính dung lượng kênh truyền. Các tính chất cơ bản của Entropy Xét biến ngẫu nhiên X = {x1, x2, …, xM}. Entropy của biến ngẫu nhiên X có các tính chất: 1 1 1. Hàm số f(M) = H( ,…, ) đơn điệu tăng. M M 2. Hàm số f(ML) = f(M)+f(L). 3. H(p1, p2, …, pM) = H(p1 + p2 +…+pr, pr+1+ pr+2+…+ pM) p p + (p1 + p 2 + … + p r )H( r 1 ,..., r r ) ∑i=1 pi ∑i =1 pi pr +1 pM + (p r +1 + p r + 2 + … + p M )H( ,..., ) ∑i=r +1 pi ∑i=r +1 pi M M 4. H(p, 1-p) là hàm liên tục theo P. Minh họa tính chất 1 và 2 Minh họa tính chất 1: Trong trường hợp biến ngẫu nhiên X có phân phối đều Entropy của X như sau : ⎛1 1⎞ ...
Tìm kiếm theo từ khóa liên quan:
thị trường chứng khoán giáo trình đại học kiến thức lịch sử kinh tế thế giới công nghệ thông tin bài tập trắc nghiệmTài liệu liên quan:
-
Giáo trình Thị trường chứng khoán: Phần 1 - PGS.TS. Bùi Kim Yến, TS. Thân Thị Thu Thủy
281 trang 975 34 0 -
Nghiên cứu các nhân tố ảnh hưởng đến ý định đầu tư chứng khoán của sinh viên tại Tp. Hồ Chí Minh
7 trang 571 12 0 -
2 trang 517 13 0
-
Giáo trình phân tích một số loại nghiệp vụ mới trong kinh doanh ngân hàng quản lý ngân quỹ p5
7 trang 473 0 0 -
52 trang 434 1 0
-
Top 10 mẹo 'đơn giản nhưng hữu ích' trong nhiếp ảnh
11 trang 321 0 0 -
293 trang 308 0 0
-
Các yếu tố tác động tới quyết định đầu tư chứng khoán của giới trẻ Việt Nam
7 trang 306 0 0 -
74 trang 304 0 0
-
MARKETING VÀ QUÁ TRÌNH KIỂM TRA THỰC HIỆN MARKETING
6 trang 301 0 0