độ đo lượng tin
ĐỘ ĐO LƯỢNG TIN Mục tiêu: trình bày các khái niệm về chưa biết và đã biết về một biến ngẫu nhiên X. Tính toán các lượng tin này thông qua định nghĩa và các tính chất của Entropy từ một hay nhiều biến ngẫu nhiên. ENTROPY Mục tiêu ...
ĐỘ ĐO LƯỢNG TIN
Mục tiêu: trình bày các khái niệm về chưa biết và đã biết về một biến ngẫu nhiên X. Tính toán các lượng tin này thông qua định nghĩa và các tính chất của Entropy từ một hay nhiều biến ngẫu nhiên.
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ác khái niệm Entropy,
- Biết Entropy của một sự kiện và Entropy của một phân phối,
- Hiểu Định lý dạng giải tích của Entropy,
- Biết Bài toán về cây tìm kiếm nhị phân và
- Làm kiến thức cơ sở để hiểu và học tốt các bài học tiếp theo.
Ví dụ về entropy
Trước hết, ta cần tìm hiểu một ví dụ về khái niệm độ do của một lượng tin dựa vào các sự kiện hay các phân phối xác suất ngẫu nhiên như sau:
Xét 2 BNN X và Y có phân phối sau:
X={1, 2, 3, 4, 5} có phân phối đều hay p(X=i) = 1/5.
Y={1, 2} cũng có phân phối đều hay p(Y=i) = 1/2.
Bản thân X và Y đều mang một lượng tin và thông tin về X và Y chưa biết do chúng là ngẫu nhiên. Do đó, X hay Y đều có một lượng tin không chắc chắn và lượng tin chắc chắn, tổng của 2 lượng tin này là không đổi và thực tế nó bằng bao nhiêu thì ta chưa thể biết. Lượng tin không chắc chắn của X (hay Y) được gọi là Entropy.
Tuy nhiên, nếu X và Y có tương quan nhau thì X cũng có một phần lượng tin không chắc chắn thông qua lượng tin đã biết của Y (hay thông tin về Y đã được biết). Trong trường hợp này, một phần lượng tin không chắc chắn của thông qua lượng tin đã biết của Y được gọi là Entropy có điều kiện.
Nhận xét về
Rõ ràng, ta cần phải xây dựng một đại lượng toán học rất cụ thể để có thể đo được lượng tin chưa biết từ một biến ngẫu nhiên. Một cách trực quan, lượng tin đó phải thể hiện được các vấn đề sau:
Một sự kiện có xác suất càng nhỏ thì sự kiện đó ít xảy ra, cũng có nghĩa là tính không chắc chắn càng lớn. Nếu đo lượng tin của nó thì nó cho một lượng tin không biết càng lớn.
Một tập hợp các sự kiện ngẫu nhiên (hay Biến ngẫu nhiên) càng nhiều sự kiện có phân phối càng đều thì tính không chắc chắn càng lớn. Nếu đo lượng tin của nó thì sẽ được lượng tin không biết càng lớn. Hay lượng tin chắc chắn càng nhỏ.
Một phân phối xác suất càng lệch nhiều (có xác xuất rất nhỏ và rất lớn) thì tính không chắc chắn càng ít và do đó sẽ có một lượng tin chưa biết càng nhỏ so với phân phối xác suất đều hay lượng tin chắc chắn của nó càng cao.
Trong tiếng việt ta chưa có từ tương đương với từ Entropy, tuy nhiên chúng ta có thể tạm hiểu hiểu thoáng qua trước khi đi vào định nghĩa chặc chẽ về mặt toán học của Entropy như sau:
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.
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 đề 01: h(p) là hàm liên tục không âm và đơn điệu giảm.
Tiên đề 02: 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 X có phân phối:
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 Y=h(X) có dạng:
H(X)=H(p1, p2, p3, …,pn) = p1h(p1)+ p2h(p2)+…+pnh(pn).
Tổng quát:
Định lý dạng giải tích của Entropy
Định lý: Hàm H(X) = H(p1, p2,...,pM) 
C = const >0
Cơ số logarithm là bất kỳ.
Bổ đề: h(p)=-Clog(p).
Trường hợp C=1 và cơ số logarithm = 2 thì đơn vị tính là bit.
Khi đó: h(p)=-log2(p) (đvt: bit) và
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:
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:
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:
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ớixá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
