Entropy thông tin

Entropy thông tin là một khái niệm mở rộng của entropy trong nhiệt động lực học và cơ học thống kê sang cho lý thuyết thông tin.

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.

Ví dụ, nhìn vào một dòng chữ tiếng Việt, được mã hóa bởi các chữ cái, khoảng cách, và dấu câu, tổng quát là các ký tự. Dòng chữ có ý nghĩa sẽ không hiện ra một cách hoàn toàn hỗn loạn ngẫu nhiên; ví dụ như tần số xuất hiện của chữ cái x sẽ không giống với tần số xuất hiện của chữ cái phổ biến hơn là t. Đồng thời, nếu dòng chữ vẫn đang được viết hay đang được truyền tải, khó có thể đoán trước được ký tự tiếp theo sẽ là gì, do đó nó có mức độ ngẫu nhiên nhất định. Entropy thông tin là một thang đo mức độ ngẫu nhiên này.

Khái niệm này lần đầu giới thiệu bởi Claude E. Shannon trong bài báo "A Mathematical Theory of Communication Lưu trữ 1998-01-31 tại Wayback Machine", năm 1948. Trước đó von Neumann đã dùng đến công thức có entropy vào năm 1927.

Định nghĩa

Claude E. Shannon đã xây dựng định nghĩa về entropy để thoả mãn các giả định sau:

• Entropy phải tỷ lệ thuận liên tục với các xác suất xuất hiện của các phần tử ngẫu nhiên trong tín hiệu. Thay đổi nhỏ trong xác suất phải dẫn đến thay đổi nhỏ trong entropy.
• Nếu các phần tử ngẫu nhiên đều có xác suất xuất hiện bằng nhau, việc tăng số lượng phần tử ngẫu nhiên phải làm tăng entropy.
• Có thể tạo các chuỗi tín hiệu theo nhiều bước, và entropy tổng cộng phải bằng tổng có trọng số của entropy của từng bước.

Shannon cũng chỉ ra rằng bất cứ định nghĩa nào của entropy, cho một tín hiệu có thể nhận các giá trị rời rạc, thoả mãn các giả định của ông thì đều có dạng:

$-K\sum _{i=1}^{n}p(i)\log p(i).\,\!$

với

• K là một hằng số, chỉ phụ thuộc vào đơn vị đo.
• n là tổng số các giá trị có thể nhận của tín hiệu.
• i là giá trị rời rạc thứ i.
• p(i) là xác suất xuất hiện của giá trị i.

Ngẫu nhiên rời rạc

Entropy của một phép thử Bernoulli được vẽ như một hàm số theo xác suất thành công, thường gọi là hàm entropy nhị phân.

Nếu một sự kiện ngẫu nhiên rời rạc x, có thể nhận các giá trị là 1..n, thì entropy của nó là:

$H(x)=\sum _{i=1}^{n}p(i)\log _{2}\left({\frac {1}{p(i)}}\right)=-\sum _{i=1}^{n}p(i)\log _{2}p(i).\,\!$

với p(i) là xác suất xảy ra của giá trị i. Như vậy, entropy của x cũng là giá trị kì vọng của các độ ngạc nhiên của các giá trị mà x có thể nhận.

Entropy thông tin trong trường hợp phần tử tín hiệu ngẫu nhiên rời rạc còn được gọi là entropy Shannon.

Ngẫu nhiên liên tục

Nếu x là số thực ngẫu nhiên liên tục, thì định nghĩa entropy có thể được biểu diễn là:

$h[f]=-\int _{-\infty }^{\infty }f(x)\log f(x)\,dx,\quad$

với f là hàm mật độ xác suất. Định nghĩa này thường được gọi là entropy Boltzmann hay entropy liên tục, hay entropy vi phân.

Có thể chứng minh rằng entropy Boltzmann không phải là giới hạn của entropy Shannon khi n → ∞ và do đó không phải là độ đo mức độ hỗn loạn của thông tin.

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". 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ột dòng chữ tiếng Anh thông thường có entropy khoảng 1,1 đến 1,6 bit cho mỗi ký tự. Thuật toán nén PPM có thể tạo ra tỷ lệ nén 1,5 bit cho mỗi ký tự. Trên thực tế, tỷ lệ nén của các thuật toán nén thông dụng có thể được dùng làm ước lượng cho entropy của dữ liệu.

Entropy của dòng văn bản thuần thường được định nghĩa dựa trên mô hình Markov. Nếu các ký tự tiếp theo hoàn toàn độc lập với các ký tự trước đó, entropy nhị phân sẽ là:

$H({\mathcal {S}})=-\sum p_{i}\log _{2}p_{i},\,\!$

với p_i là xác suất của i.

Liên hệ với cơ học thống kê

Định nghĩa entropy của Shannon có liên hệ chặt chẽ với định nghĩa entropy trong cơ học thống kê. Chính các công trình của Ludwig Boltzmann hay Willard Gibbs trong cơ học thống kê đã kích thích việc sử dụng từ entropy trong lý thuyết thông tin. Theo Edwin Thompson Jaynes (1957), thực tế cơ học thống kê và nhiệt động lực học có thể coi là ứng dụng của lý thuyết thông tin: entropy trong nhiệt động lực học có thể cọi là độ đo của thông tin vi mô (mô tả các trạng thái vi mô của từng phần tử trong hệ vật lý) mà chưa được mô tả hết bởi các thông số vĩ mô của hệ nhiệt động lực học.

Ví dụ về tương quan giữa entropy nhiệt động lực học và entropy thông tin còn được thể hiện ở con quỷ Maxwell. Quỷ Maxwell có thể tạo ra được khi nó làm giảm entropy nhiệt động lực học nhưng làm tăng entropy thông tin và cả hệ vẫn tuân thủ định luật hai nhiệt động lực học với tổng entropy không đổi và quá trình hoạt động của quỷ là thuận nghịch.

Liên kết ngoài

• Description of information entropy from "Tools for Thought" by Howard Rheingold Lưu trữ 2011-05-15 tại Wayback Machine