Thuật toán Entropy cực đại

Thuật toán Entropy cực đại

(Tác giả: Tuan Anh Luu – Nguồn: viet.jnlp.org)

Đối với bài toán phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mô hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng / đều nhất có thể”. Tập dữ liệu học (tức là tập gồm các dữ liệu đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mô hình, đó là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mô hình sẽ tiến hành tính toán để có được một phân phối cho Entropy cực đại.
Ví dụ một mô hình Entropy cực đại: “Giả sử với bộ phân lớp về lĩnh vực kinh tế trên báo VnEconomy có bốn lớp chính được chỉ ra là ngân_hàng, chứng_khoán, bất_động_sản, doanh_nghiệp. Các thống kê dữ liệu chỉ ra rằng trung bình 70% các tài liệu trong lớp ngân_hàng có chứa từ vay_vốn. Như vậy một cách trực quan có thể thấy rằng nếu một tài liệu D có chứa từ vay_vốn thì xác suất được phân vào lớp ngân_hàng là 70% và xác suất phân vào ba lớp còn lại là 10% đối với mỗi lớp. Nếu tài liệu D không chứa từ vay_vốn thì xác suất phân phối của D là 25% đều cho mỗi lớp.” Trong ví dụ trên, “nếu tài liệu chứa cụm từ vay_vốn thì có xác suất phân vào lớp ngân_hàng là 70%” là một ràng buộc của mô hình.
1. Các ràng buộc và đặc trưng
Trong nguyên lý Entropy cực đại, chúng ta sử dụng tập dữ liệu mẫu làm để thiết lập ràng buộc cho phân phối điều kiện. Với mỗi ràng buộc được mô tả bởi một đặc tính của tập dữ liệu học. Một đặc trưng trong mô hình Entropy cực đại được biểu diễn bởi một hàm fi(d, c), trong đó d là tài liệu và c là lớp. Entropy cực đại cho phép giới hạn mô hình phân phối để có thu các giá trị kỳ vọng cho mỗi đặc trưng của tập dữ liệu. Vì vậy, ta có thể đặt xác suất phân phối của dữ liệu d cho lớp c là P(c|d) thỏa mãn phương trình sau:
Trong quá trình huấn luyện, phân phối tài liệu P(d) là không biết và chúng ta không cần quan tâm tới nó. Vì vậy, ta chỉ sử dụng tập dữ liệu mẫu như là một điều kiện để phân phối dữ liệu tuân theo ràng buộc sau:
2.Mô hình Entropy cực đại
Mô hình xác suất Entropy cực đại cung cấp một cách đơn giản để kết hợp các đặc trưng của tài liệu trong những ngữ cảnh khác nhau để ước lượng xác suất của một số lớp xuất hiện cùng với một số ngữ cảnh này. Tư tưởng cơ bản của phương pháp Entropy cực đại là tìm ra một mô hình có phân phối xác suất thỏa mãn mọi ràng buộc quan sát được từ dữ liệu mà không đưa thêm bất kì một giả thiết nào khác. Theo nguyên lý Entropy cực đại, phân phối cần đáp ứng dữ liệu quan sát và làm cực đại độ đo Entropy có điều kiện:
Trong đó p* là phân xác suất tối ưu.
Mô hình Entropy cực đại xây dựng các đặc trưng từ tập dữ liệu huấn luyện. Mỗi đặc trưng được biểu diễn dưới một hàm nhận một trong hai giá trị đúng hoặc sai. Tập các ràng buộc sẽ được thiết lập từ các đặc trưng này. Một ràng buộc là một điều kiện từ dữ liệu buộc mô hình phải thỏa mãn. Mỗi đặc trưng fi được gán cho một trọng số λi . Khi đó, bài toán phân lớp được đưa về bài toán ước lượng xác suất có điều kiện:

Trong đó Z(d) là biểu thức chuẩn hóa để đảm bảo điều kiện Σp(c | d ) = 1. Từ đó đưa ra công thức sau:

3. Entropy cực đại cho phân lớp văn bản

Để áp dụng mô hình Entropy cực đại cho một miền, chúng ta cần phải chọn ra một tập các đặc trung để sử dụng thiết lập các ràng buộc. Đối với phân lớp văn bản với mô hình Entropy cực đại, chúng ta sử dụng số lượng từ như là các đặc trưng. Trong nghiên cứu này cho với mỗi từ kết hợp, ta đưa ra một đặc tính như sau:
Trong đó, N(d, w) là số lần từ w xuất hiện trong tài liệu d, và N(d) là số lượng các từ có trong tài liệu d.
Trong công thức này, nếu một từ xuất hiện thường xuyên trong một tài liệu, ta sẽ tính trọng số cho các cặp từ này và thấy rằng trọng số đó sẽ cao hơn so với trọng số của các từ ghép trong tài liệu. Trong hầu hết ngôn ngữ tự nhiên sử dụng Entropy cực đại thì các đặc trưng thường là đặc trưng nhị phân. Trong phân lớp văn bản, chúng ta mong muốn các đặc trưng được tính bằng số lần suất hiện của một từ trong một tài liệu có thể củng cố cho phân lớp.
Một trong những khía cạnh đặc biệt của Entropy cực đại là nó không bị bất kỳ giả thuyết độc lập nào ràng buộc. Ví dụ, với cụm từ “Buenos Aires”, hai từ này hầu như luôn xuất hiện động thời cùng nhau.Với giả thiết Naïve Bayes sẽ đếm số từ xuất hiện hai lần trong cụm từ này. Mặt khác, Entropy cực đại sẽ giảm giá trị trọng số λi của mỗi đặc trưng đi một nửa. Một trong những hệ của việc không phụ thuộc vào
bất kỳ giả thuyết độc lập nào đó là các sơ đồ và các cụm từ có thể được thêm vào các đặc trưng của Entropy cực đại một cách dễ dàng mà không cần lo lắng rằng các đặc tính này chồng lên nhau.
􀂾 Ưu điểm của mô hình Entropy cực đại:
– Cho phép khả năng hầu như không hạn chế trong việc biểu diễn các vấn đề phức tạp về tri thức thông qua dạng các hàm đặc trưng.
– Có thể giải quyết nhiều dạng thuộc tính khác nhau.
– Các giả thiết không cần phải độc lập với nhau.
– Trọng số của các đặc trưng được xác định một cách tự động.
—————-&&—————

Tất cả là tại Ên Trô Pỳ

Tất cả là tại Ên Trô Pỳ

(Tác giả: Nguyễn Tiến Dũng – Nguồn: zung.zetamu.net)

– Lịch sử đã cho VN một sứ mệnh anh hùng: hết đuổi giặc Tàu, giặc Pháp, đến giặc Mỹ, rồi lại đuổi gì tiếp ?

– Tiên sư cha thằng lịch sử, toàn bắt VN làm những việc khó !

Tay sai của thằng lịch sử

Thằng lịch sử đúng là oái oăm, làm khổ VN. Nhưng thằng lịch sử cũng không làm được vậy, nếu không có một quỉ sứ tay sai đắc lực của nó mang tên Ên Trô Pỳ.  Nghe có vẻ như tên Tàu, nhưng thực ra đây là tên Tây. Thằng quỉ sứ này luôn làm những việc phá phách, nhưng nó ẩn danh cho đến tận năm 1865 mới bị một lão người Đức tên là Clausius phát giác ra, và gọi nó là thằng Entropy, có nghĩa là thằng xáo trộn hỗn độn. Theo gốc Hy Lạp, “tropy” (τροπή ), có nghĩa là thay đổi, chuyển hướng, còn “en” có nghĩa là “bên trong”. Khi sang tiếng Việt thì Entropy trở thành Ên Trô Pỳ (chữ trô đọc chờ nặng). Số là, có lần tôi gọi taxi để đi đến Ciputra. Tôi nói Ci-pu-t-ra, anh lái taxi mãi mới hiểu ra là Ci-pu-tra, và chê tôi nhà quê không biết nói tiếng Tây. Từ đó tôi cứ nói Ci-pu-tra, ai cũng hiểu, và entropy thì gọi là Ên Trô Pỳ cho chuẩn.

Ở đâu có lộn xộn, là ở đó có En Trô Pỳ hoành hành. Không chỉ ở những trận đánh nhau chết cả triệu người, mà ngay trong căn nhà nhỏ của bạn, En Trô Pỳ cũng ra tay quấy phá. Bạn có biết vì sao phòng của bạn cứ dọn sạch được 1-2 hôm lại bừa đâu vào đấy không, vì sao hàng xóm hay đồng nghiệp thỉnh thoảng lại cãi nhau chí chóe không ? Chính là tại bởi Ên Trô Pỳ!

Ên Trô Pỳ luồn lách mọi nơi, ảnh hưởng đến mọi vật, một cách cộng tính: Ên Trô Pỳ (độ lộn xộn) của một tổng thể các vật (các “systems”), thì bằng tổng của các Ên Trô Pỳ của các vật. Một đặc điểm nhận biết thằng En Trô Pỳ là, nó là thằng ăn hại năng lượng. Ví dụ, khi xe ô tô đi trên đường phẳng nằm ngang vẫn tốn xăng, chính là vì thằng Entropy ăn mất năng lượng do động cơ chạy xăng tao ra, qua các thứ ma sát. Cụ Newton đã nói năng lượng luôn bảo toàn, không bị mất đi. Thế nhưng, năng lượng dự trữ trong xăng là năng lưỡng hữu ích, có thể dùng để làm việc này việc nọ, còn năng lượng khi đã bị thằng En Trô Py ăn vào, thì trở thành năng lượng vô dụng, ta khó có thể đòi lại để dùng đươc nữa! Tuy nhiên, bản thân Ên Trô Pỳ không phải là năng lượng, nó chỉ là thằng phá phách biến năng lượng hữu dung thành vô dụng trong quá trình béo lên của nó thôi. Lão Clausius cũng biết điều đó; đầu tiên lão định tìm từ gì tương tự như năng lượng để đặt tên cho nó, trước khi nghĩ ra từ Entropy.

Càng nóng càng khó béo lên

Clausius nhận thấy rằng, chỗ nào càng nóng thì entropy càng khó béo lên, tức là càng cần bơm vào nhiều năng lượng (ở dạng nhiệt năng) để nó béo lên. Nói một cách chính xác hơn:

dS = \frac{\delta q}{ T }

trong đó S là độ lớn của entropy (của một hệ nào đó), dS là sự thay đổi độ lớn của Ên Trô Pỳ, T là nhiệt độ (tuyệt đối), còn {\delta q} là độ thay đổi  nhiệt năng của hệ đó. Nói cách khác, nếu ta cho thêm một lượng nhiệt năng \delta q vào một vật nào đó đang ở nhiệt độ T, thì entropy của nó sẽ tăng lên một lượng là \frac{\delta q}{ T } . Ngược lại, nếu ta hút đi một lượng nhiệt năng là \delta q, thì entropy của vật cũng giảm đi một lượng là  \frac{\delta q}{ T } .

Công thức trên cũng cho thấy, đơn vị đo của entropy là đơn vị năng lượng chia cho nhiệt độ. Người ta thường viết đơn vị của entropy là J/K, trong đó J là Joule là đơn vị năng lượng dùng để đo nhiệt năng, con K là đơn vị độ Kelvin để đo nhiệt độ.

Theo công thức phía trên, để giảm entropy của một vật, cần rút bớt nhiệt ra. Nhưng nhiệt rút ra đó đi vào chỗ nào ? Theo một định luật vật lý (gọi là định luật nhiệt động học thứ hai), chỗ nhận được nhiệt đó phải lạnh hơn là vật ban đầu nếu ta không muốn tiêu thêm năng lượng vào đó. (Khi Bác Hồ ôm cục gạch nóng, thì là gạch sưởi cho Bác chứ không phải Bác sưởi cho gạch). Chẳng hạn chỗ đó có nhiệt độ T_1 < T. Khi đó phần được truyền nhiệt sang sẽ có entropy S_1 tăng lên một lượng bằng

dS_1 = \frac{\delta q}{ T_1 }

trong đó \delta q là lượng nhiệt chuyển từ vật nóng sang vật lạnh. Vật nóng thì có entropy giảm đi một lượng bằng dS = - \frac{\delta q}{ T } . Công lại ta có

dS + dS_1 = \frac{\delta q}{ T_1 } - \frac{\delta q}{ T} > 0

(vì T_1 < T_0\delta q > 0). Có nghĩa là entropy của tổng hai vật tăng lên! Đây chính là định luật:

Ên Trô Pỳ làm gì cũng đúng

Theo định luật này, thì entropy của thế giới không thể giảm đi, mà chỉ có thể tăng lên theo thời gian. Nếu entropy ở chỗ nào đó giảm đi, thì ở các chỗ xung quanh sẽ phải tăng lên một lượng nhiều hơn lượng giảm đi đó để bù lại, và tính tổng cộng thì vẫn là tăng lên. Định luật Ên Trô Pỳ làm gì cũng đúng chẳng qua là một cách phát biểu khác của định luật nhiệt động học thứ hai.

Chính vì sự tăng lên không ngừng theo thời gian của entropy, nên thời gian không đảo nghịch được, và không thể có các chuyến “du hành vũ trụ” đi ngược lại thời gian được! Giá ta có thể đi về thế kỷ 17 tán phét với cụ Newton một lúc rồi quay lại thế kỷ 21 thì vui biết mấy. Nhưng quỉ sứ entropy không cho ta làm điều đó!

Có thể nói, thằng entropy ngày càng béo ra bằng cách ăn vào năng lượng hữu ích biến thành năng lượng vô ích để rồi làm loạn thế giới, nhưng ta không có cách nào “chọc mỡ” nó cả!

Nếu đến một lúc nào đó, thằng En Trô Pỳ ăn hết năng lượng của thế giới này thì sao? Lúc đó thì nó đạt đến mức béo nhất có thể (gọi là maximal entropy). Nhưng lúc đó cũng sẽ không còn năng lượng có thể sử dụng được nữa, và đó sẽ là ngày tận thế của thế giới. Mấy ông hủ lý thì gọi đó là ngày của cái chết nhiệt (heat death hay thermal death). Nhưng ngày đó nếu có xảy ra, cũng còn phải hàng ty tỷ năm nữa, ta chưa vội gì mà phải “mặt ủ mày chau”!

Một mình chống lại Ên Trô Pỳ

Tuy Ên Trô Pỳ làm gì cũng đúng, nhưng thỉnh thoảng vẫn có các anh hùng hảo hớn dám ra đương đầu với nó. Một trong các anh hùng hảo hớn đó là thần đồng Ludwig Boltzmann (1844-1906), một nhà toán học mà khi 25 tuổi đã là giáo sư (full professor) ở nước Áo. Từ những năm 1870, Boltzmann đã tìm cách vạch mặt bản chất chân tướng của thằng Ên Trô Pỳ bằng cơ học thống kê, và đi đến công thức sau:

S = k. \ln W

trong đó k = 1.38 \times 10^{-23} J/K là một hằng số (gọi là hằng số Boltzmann), còn W là số trạng thái vi mô (microstate) khác nhau mà nhìn vào hệ ta không phân biệt được (tức là cho cùng một trạng thái vĩ mô của vật).  Trong suốt hơn 30 năm từ khi Boltzmann nghĩ ra công thức trên, thì bị thằng Ên Trô Pỳ trả thù bằng cách xúi giục các nhà khoa học lớn khác (như Planck, Poincaré) chế diễu công thức này, coi nó lẩm cẩm, khiến cho Boltmann uất chí đến mức tự tử ở Duino (Italia) vào năm 1906.

Ngày nay các nhà hủ lý đều chấp nhận công thức trên của Boltzmann, và trên bia mộ của ông ta có khắc nó.

Theo công thức Boltzmann, thì càng nhiều khả năng (nhiều microstate có thể) càng lắm hỗn loạn (entropy càng cao). Khi ta ghép 2 hệ với nhau, thì số khả năng của tổng bằng tích của các số khả năng, trong khi entropy của tổng chỉ là tổng của các entropy. Bởi vậy để chuyển từ số khả năng sang entropy phải lấy log.

Làm sao để tính entropy ?

Đây có vẻ là vấn đề rất khó khăn. Đối với các vật đơn giản, ví dụ nhưng một lượng nguyên chất của một loại phân tử nào đó, thì có thể dùng công thức của Clausius để mà tính: Khi nhiệt độ bằng 0K (= – 273 độ C), thì các phân tử cũng đứng im không có thể nhúc nhích gì hết, bởi vậy coi như là “có trật tự”, và entropy của nguyên chất  khi nhiệt độ bằng 0 (độ Kelvin) được coi là bằng 0. (Đây là định luật thứ 3 của nhiệt động học). Từ mức nhiệt độ sát 0, ta nhồi nhiệt năng từng ít một vào vào để nhiệt độ tăng lên dần đến mức ta muốn, và trong quá trình nhồi đó đo nhiệt độ, rồi lấy các lượng nhiệt năng cho vào chia cho nhiệt độ để ra các độ tăng của entropy, rồi cộng chúng lại với nhau. (Nói một cách toán học hơn, thì là lấy tích phân của dạng vi phân \delta q / T). Ví dụ, người ta tính ra được rằng 1kg nước (H2O) ở nhiệt độ 25 độ C có entropy bằng 367 J/K [edit: đây là con số tương đối tính từ 1 mốc nào đó, còn con số tuyệt đối, theo GS Đàm Thanh Sơn, là những 3890 J/K]. Tất nhiên, đây chỉ là một trong các cách tính, và các hủ lý có thể còn sáng tạo ra nhiều cách khác.  (Xem chẳng hạn: R.K. Rajput, A textbook of engineering thermodynamics).

Tại sao tủ lạnh lại lạnh ?

Bình thường, theo định luật thứ hai của nhiệt học, nhiệt phải truyền từ chỗ nóng sang chỗ lạnh (và trong quá trình truyền nhiệt đó thì entropy tăng lên). Thế nhưng tủ lạnh mà máy điều hòa nhiệt độ có vẻ làm ngược lại: tủ lạnh hút nhiệt bên trong tủ thổi ra ngoài, làm bên trong thì lạnh đi, còn bên ngoài nóng lên. Có sự mâu thuẫn nào ở đây không ? Tất nhiên là không, vì thằng Ên Trô Pỳ làm gì cũng đúng, đời nào chịu thua thiệt. Nó chỉ cho phép tủ lạnh hay máy điều hòa làm lạnh với điều kiện là phải xì cho nó năng lượng: khi máy điều hòa làm giảm nhiệt năng trong phòng, thì làm tăng nhiệt năng ngoài trời một lượng nhiều hơn là lượng giảm đi trong phòng, và độ chênh lệch giữa hai lượng chính là lượng điện năng mà máy tiêu thụ. Nhiệt độ ngoài trời mà càng cao hơn bên trong nhà, thì càng phải cúng nhiều điện năng cho thằng Ên Trô Py nó mới cho phép thổi nhiệt ngược từ chỗ lạnh trong nhà ra chỗ nóng ngoài trời ! Điện có thể được dùng để hút nhiệt qua hiệu ứng Peltier, hoặc qua cách nén khí bằng compressor rồi sử dụng hiệu hứng thay đổi áp suất dẫn đến thay đổi nhiệt sau đó, hoặc là các cách khác, nhưng kiểu gì thì cũng phải nộp cống cho thằng Ên Trô Pỳ.

Những kẻ “ăn theo”

Như người ta thường nói “không chống được chúng, thì hãy theo chúng”.  Có những kẻ đã khôn ngoan đi ăn theo, mượn vía Ên Trô Pỳ. Đầu tiên có thể kể đến Claude Shannon (1916-2001), cha đẻ của lý thuyết thông tin. Khi Shannon nghĩ ra công thức đo lượng thông tin (hay là lượng thông tin bị mất mát đi khi truyền tin) vào quãng những năm 1944-1948, định gọi nó là “độ bất xác định”, nhưng John von Neumann đã khuyên nên đặt tên nó là entropy, với hai lý do: một là công thức của Shannon trông giống y chang công thức entropy trong vật lý thống kê (như kiểu công thức của Boltzmann), và hai là “không ai thực sự biết entropy là gì, nên cậu gọi như vậy thì sẽ lợi thế khi tranh luận!”.

Nếu không gian xác  suất chia làm n tập con với các xác suất p_1, \hdots, p_n tương ứng (\sum p_i = 1), thì entropy của phép chia này bằng

- \sum p_i \log_2 p_i

Hiểu công thức trên như thế nào ? Để cho đơn giản, hình dung là chia đều thành 8 phần, mỗi phần xác suất 1/8, khi đó entropy bằng 3. Số 3 ở đây hiểu là “3 bit thông tin”: Xét 8 số nhị phân có 3 chữ số: 000, 001, 010, 011, 100, 101, 110, 111. Giả sử cần lấy ra 1 số trong 8 số đó. Để biết là cần lấy ra số nào, thì cần có 3 bit thông tin: chữ số đầu là gì, 0 hay 1, là 1 bit thông tin, chữ số thứ 2 cũng ứng với 1 bit, và chữ số thứ 3 cũng 1 bit.

Sau khi Shannon “ăn theo” thì tiếp ngay đến Kolmogorov, với định nghĩa “metric entropy” cho các hệ động lực, vào đầu những năm 1950. Tiếp theo đó là một loạt các nhà toán học khác như Sinai, Adler, Dinaburg, Bowen, … nghiên cứu metric entropy rồi topological entropy cho các hệ động lực, rồi tiếp đến Ghys, Walczak, Langevin xét entropy hình học cho các phân thới, v.v. Đấy mới chỉ là tụi “làm toán ăn theo” không kể các hội vật lý, tin học, v.v. khác ăn theo entropy.

Kẻ thừa giấy vẽ con voi này cũng đang đi ăn theo với “entropy của các cấu trúc hình học”, mà trường hợp riêng là các đa tạp Poisson, hay các singular distributions nào đó. Việc nó liên quan đến quỉ sử Ên Trô Pỳ (trong tự nhiên) thế nào thì chưa hề rõ.

Trong kinh tế, những kẻ ăn theo cũng đưa vào khái niệm corporate entropy, để chỉ sự rắm rối của các doanh nghiệp dẫn đến giảm hiệu quả lao động.

Entropy của thức ăn

Một lần kẻ thừa giấy vẽ voi này có được hầu chuyện Alain Connes trong một bữa đánh chén. Câu chuyện huyên thuyên một lúc không hiểu sao lại nhảy sang entropy. Connes say sưa với lý thuyết entropy về thức ăn của mình: thức ăn vào bụng thì kiểu gì cũng sẽ phải đạt mức entropy nào đó. Hãy để cho dạ dày và ruột của ta làm việc đó (tăng entropy của thức ăn lên, là một cách làm giảm entropy của bản thân chúng ta, giúp ta khỏe lên). Đừng ăn thức ăn có entropy cao sẵn (khi đó cơ thể người còn ít việc để làm, không làm giảm entropy của người đi được). Hẵy học tập người Nhật: đồ ăn của họ thường ở dạng entropy thấp (ví dụ như ăn cá sống). Đừng có ăn nhiều đồ đã băm nát trộn lẫn xào xáo nhiều … Cũng có thể đồ ăn có entropy thấp là một trong các bí quyết sống lâu của người Nhật thật.

Entropy âm ?

Trong lúc Connes kể chuyện về entropy của thức ăn, thì kẻ này có liều mình hỏi một câu provocative: thế entropy có âm được không ? Connes liền kể chuyện Boltzmann bị người đời không hiểu dẫn đến chán đời tự tử ra sao.

Tất nhiên theo các công thức của Boltzmann hay Shannon hay này nọ, thì entropy không thể âm. Thế nhưng câu hỏi “triết học” vì sao entropy lại phải dương không hẳn là câu hỏi dở hơi, đặc biệt khi ta coi mọi thứ chỉ là tương đối. Năng lượng có thể âm thoải mái không sao, vì nếu lấy hàm năng lượng trừ đi một hằng số, thì không hề ảnh hưởng đến phương trình chuyển động. (Hay như Dirac nghĩ ra các phản hạt xả láng, âm có làm sao đâu ?!) Entropy cũng vậy, nếu trừ đi một hằng số thì có lẽ chẳng ảnh hưởng gì hết đến các lý thuyết, vì cái người ta đo thực ra là độ thay đổi entropy, chứ không phải entropy tuyệt đối.

Kẻ vẽ voi này đi tìm hiều về “entropy âm”, thì phát hiện ra có khái niệm đó thật! Chính Schroedinger đưa ra khái niệm “negative entropy”, hay còn gọi là negentropy, trong quyển sách What is life. Thực ra thì cũng không có gì dám “báng bổ” quỉ sử Ên Trô Pỳ về bản chất. Có thể coi entropy + negentropy là hằng số, tức là negentropy là phần “dư ra” chưa bị entropy chén mất, và phần này ứng với phần năng lượng còn dùng được. Sự sống có được là nhờ có negentropy.

Entropy của các cấu trúc tổ chức xã hội ?

Một câu hỏi thú vị đặt ra với các nhà xã hội học: các mô hình, cơ chế xã hội nào tạo entropy cao nhất, làm tăng entropy nhanh nhất ?

Câu hỏi này rất khó, kẻ vẽ voi không dám vẽ bậy ở đây. Nhưng trộm nghĩ rằng các cơ chế “cào bằng”, “xin cho”, tham nhũng v.v. ắt hẳn dẫn đến entropy cao ?!

——————&&—————-

Entropy thông tin

Entropy thông tin

(Nguồn: wikipedia)

Entropy thông tin là một khái niệm mở rộng của entropy trong nhiệt động lực họccơ 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“, năm 1948. Trước đó von Neumann đã dùng đến công thức có entropy vào năm 1927.

Mục lục

Đị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}^np(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}^np(i)\log_2 \left(\frac{1}{p(i)}\right)=-\sum_{i=1}^np(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ị mong đợi 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 xsố 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 fhà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 pixá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ê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.

Xem thêm

Liên kết ngoài

Công cụ tính toán online

 

—————&&————–

TỪ VĂN HỌC DÂN GIAN ĐẾN TOÁN HỌC HIỆN ĐẠI

TỪ VĂN HỌC DÂN GIAN ĐẾN TOÁN HỌC HIỆN ĐẠI

(Tác giả: Hà Huy Khoái – Nguồn: hahuykhoai.wordpress.com)

Có nhiều vấn đề lớn của toán học hiện đại thực ra đã xuất hiện trong những chuyện dân gian. Chẳng hạn, câu chuyện vui  anh chồng tham ăn  được bà vợ dùng sợi dây điều khiển, mà hầu như người Việt Nam nào cũng đã từng ít nhất một lần nghe kể,  nếu phân tích kĩ  sẽ thấy  là một bài giảng nhập môn tuyệt vời về Lí thuyết thông tin.

Xưa, một bà vợ có anh chồng rất tham ăn. Tính tham ăn của anh chồng khiến chị vợ nhiều phen xấu hổ. Chị bèn nghĩ ra một kế. Nhân ngày Tết về bên ngoại ăn cỗ, chị ngồi dưới bếp, buộc một sợi dây vào tay chồng và dặn rằng, khi nào chị giật dây một cái thì mới được gắp một miếng. Hôm đó, mọi người ngạc nhiên vì thấy anh chồng ăn uống rất từ tốn. Nào ngờ, chỉ được chừng nửa bữa thì có một chú gà trống chạy qua, mắc chân vào dây. Anh chồng  tham ăn được thể gắp lia lịa ( theo nhịp dãy chân của chú gà) ! Mẹo hay của chị vợ thế là bị hỏng.

Vấn đề của Lí thuyết thông tin đặt ra trong câu chuyện này là: làm thế nào để mưu kế của chị vợ  thành công ngay cả khi không may có chú gà mắc vào dây? Đó chính là một trong những bài toán khó nhất của toán học hiện đại.

Ta thử hình dung một hệ thống điển hình của lí thuyết thông tin: trước hết, ta có một trung tâm điều khiển, trong trường hợp này là chị vợ. Sau đó là một trung tâm nhận thông tin, chính là chàng tham ăn. Thông tin được truyền qua một kênh truyền tin,  chính là sợi dây. Các thông tin được truyền qua kênh truyền tin bằng các tín hiệu, trong trường hợp này là giật dây. Thông tin luôn được truyền dưới dạng mã hoá, ở đây chị vợ đã mã hoá thông tin như sau: giật một cái- gắp một miếng.

Nhưng, một kênh truyền tin, dù hiện đại đến đâu, cũng không thể tuyệt đối chính xác: trung tâm thu nhận thông tin không bao giờ nhận được hoàn toàn chính xác thông tin mà trung tâm điều khiển truyền đi, mà thường bị một nhiễu nào đó. Cái nhiễu mà kênh truyền tin của chị vợ mắc phải chính là con gà tai hại! Vấn đề đặt ra cho chị vợ, cũng như cho lí thuyết thông tin là: làm thế nào để ngay cả khi bị nhiễu, ta vẫn không đi đến kết quả quá tồi tệ? Nói một cách “hàn lâm” là: làm thế nào để tăng độ tin cậy của kênh truyền tin?

Nếu như quy định của chị vợ không phải là “giật một cái – gắp một miếng” mà là “giật 20 cái – gắp một miếng” thì dù có cái nhiễu là con gà, anh chồng chắc cũng không đến nỗi mang tiếng  quá tham ăn!  Làm như thế,  trong lí thuyết thông tin gọi là tăng độ thừa để bảo đảm độ tin cậy. Độ thừa ở đây là: lẽ ra chỉ cần giật dây một lần là đủ truyền lệnh gắp một miếng, thì ta phải giật những 20 lần! Nếu chị vợ quá cẩn thận đến mức quy định: giật 100 lần mới gắp một miếng, thì chắc anh chồng được tiếng rất lịch sự, nhưng cũng sẽ mang bụng đói về nhà. Vấn đề nan giải của lí thuyết thông tin chính là ở chỗ đó: nếu tăng độ thừa để đảm bảo độ tin cậy, thì sẽ bị ảnh hưởng đến tốc độ truyền tin. Trong thực tế, một thông tin chính xác nhưng đến quá muộn có thể là một thông tin vô ích. Vậy, chị vợ nên quy định giật bao nhiêu lần thì anh chồng được gắp một miếng, để sao cho anh ta vừa no bụng, lại vừa được tiếng lịch sự, hay ít nhất là không mang tiếng quá tham ăn, ngay cả khi bị chú gà làm nhiễu kênh truyền tin? Đó chính là bài toán điển hình không chỉ của lí thuyết thông tin, mà của hầu hết các ngành của Toán học hiện đại: nếu xem mỗi yêu cầu lập thành một miền nào đó, thì phải tìm ra đường biên giới phân chia các miền, sao cho mọi yêu cầu đều được thoả mãn trong một chừng mực chấp nhận được.( Bài toán này chắc không chỉ khó trong toán học, mà cả trong cuộc đời: không thể hy vọng đạt được một cách cao nhất mọi mục tiêu, mà vấn đề là phải làm sao cho hài hoà các mục tiêu đó!).

Để  giải bài toán đặt ra, trong những năm gần đây đã xuất hiện nhiều kết quả khá thú vị.  Một trong những phương pháp mới  là dùng các mã hình học đại số vào  lí thuyết thông tin. Phương pháp này thực sự bất ngờ vì xưa nay, hình học đại số là ngành trừu tượng nhất trong toán học, và ít ai nghĩ lại có thể dùng nó vào một vấn đề rất thực tiễn. Việc dùng hình học đại số để tìm ra biên giới thích hợp trong lí thuyết thông tin đã góp phần xoá đi biên giới giữa toán học lí thuyết và toán học ứng dụng.

Còn một điều nữa mà tôi chưa nói đến khi kể về hệ thống truyền tin của bà vợ nói trên , đó là vấn đề bảo mật. Nếu có anh chàng nào  đó biết được điều giao hẹn của vợ chồng nhà kia và  muốn phá vỡ hạnh phúc của họ, hay ít ra chỉ là để trêu chọc thôi, thì anh ta có thể gây nhiễu bằng cách giật dây thật nhanh, để dù bà vợ có “tăng độ thừa” đến đâu, vẫn không thể dứt bỏ được tiếng xấu tham ăn của chồng mình. Vì thế, trong khi truyền tin, nhất thiết phải đặt ra vấn đề bảo mật. Một lần nữa, toán học hiện đại lại có thể giúp ích cho bà vợ bằng cách cung cấp những phương pháp mã hoá hiện đại.  Một lúc nào đó, ta sẽ trở lại chủ đề này.

Kho tàng văn học dân gian vô cùng phong phú. Trên đây chỉ là một trong rất nhiều ví dụ về mối liên hệ giữa văn học dân gian và toán học hiện đại. Các bạn thử tìm thêm ví dụ khác nhé!

————–&&————-

Lý thuyết thông tin

Lý thuyết thông tin

(Nguồn: wikipedia)

Lý thuyết thông tin là một nhánh của toán học ứng dụngkĩ thuật điện nghiên cứu về đo đạc lượng thông tin. Lý thuyết thông tin được xây dựng bởi Claude E. Shannon để xác định giới hạn cơ bản trong các hoạt động xử lý tín hiệu chẳng hạn như nén dữ liệu hay lưu trữtruyền dẫn dữ liệu. Ngay từ những ngày đầu, nó đã mở rộng phạm vi ứng dụng ra nhiều lĩnh vực khác, bao gồm suy luận thống kê, xử lý ngôn ngữ tự nhiên, mật mã học, các mạng lưới bên cạnh mạng lưới viễn thông – chẳng hạn như trong thần kinh[1], sự tiến hóa[2] và chức năng[3] của các mã phân tử, lựa chọn mô hình[4] trong sinh thái học, vật lý nhiệt, máy tính lượng tử[5], phát hiện sao chép[6] và các hình thức phân tích dữ liệu khác.[7]

Một độ đo cơ bản của thông tin là entropy, thường được diễn đạt dưới dạng số lượng bit cần thiết trung bình để lưu trữ hoặc dẫn truyền. Entropy lượng hóa sự không chắc chắn trong việc dự đoán giá trị của một biến ngẫu nhiên. Ví dụ như, xác định kết quả của một lần tung đồng xu công bằng (hai kết quả có khả năng như nhau) cho ít thông tin hơn (entropy nhỏ hơn) là xác định kết quả của một lần tung xúc sắc (sáu kết quả có khả năng như nhau).

Các ứng dụng cơ bản của lý thuyết thông tin bao gồm nén không mất dữ liệu (chẳng hạn như ZIP), nén mất dữ liệu (chẳng hạn MP3, JPG), mã hóa kênh (chẳng hạn như trong DSL). Lý thuyết thông tin nằm ở phần giao nhau giữa toán học, thống kê, khoa học máy tính, vật lý, thần kinh, và kĩ thuật điện. Các ngành hẹp quan trọng của lý thuyết thông tin bao gồm mã hóa nguồn, mã hóa kênh, lý thuyết thông tin thuật toán, bảo mật theo lý thuyết thông tin.

Mục lục

Tổng quan

Khái niệm cơ bản của lý thuyết thông tin có thể được nắm bắt thông qua việc xem xét hình thức liên lạc phổ biến nhất của con người: ngôn ngữ. Hai yếu tố quan trọng của một ngôn ngữ ngắn gọn là: các từ thông dụng (như “một”, “cái”, “tôi”) nên ngắn gọn hơn các từ kém thông dụng hơn (như “thông tin”, “thợ thủ công”) để các câu không bị quá dài. Sự cân bằng độ dài các từ như vậy cũng tương tự như trong nén dữ liệu và là một thành phần cơ bản của mã hóa nguồn. Ngoài ra, nếu một phần của câu không nghe được hoặc bị nghe nhầm do tiếng ồn, chẳng hạn như do có ô tô chạy qua, thì người nghe vẫn có thể đoán ra ý nghĩa của câu. Sự vững chắc đó là một thành phần thiết yếu cho hệ thống liên lạc điện tử cũng như cho ngôn ngữ. Tính chất đó trong truyền thông được đảm bảo bởi mã hóa kênh. Mã hóa nguồn và mã hóa kênh là những mối quan tâm chính của lý thuyết thông tin.

Lý thuyết thông tin thường được xem là xuất phát từ bài báo quan trọng của Shannon (1948) mang tên “A Mathematical Theory of Communication”. Mô hình trung tâm của lý thuyết thông tin cổ điển là vấn đề kĩ thuật của việc truyền dẫn thông tin trên một kênh nhiễu. Kết quả cơ bản trong lý thuyết này là định lý mã hóa nguồn của Shannon, khẳng định rằng tính trung bình, số bit cần dùng để mô tả kết quả của một sự kiện ngẫu nhiên chính là entropy của nó, và định lý mã hóa trên kênh nhiễu cũng của Shannon, khẳng định rằng việc liên lạc không lỗi trên một kênh nhiễu là có thể miễn là tốc độ truyền dữ liệu là nhỏ hơn một giới hạn nhất định, gọi là dung lượng kênh. Có thể đạt đến gần dung lượng kênh trong thực tế bằng cách sử dụng các hệ thống mã hóa và giải mã thích hợp.

Bối cảnh lịch sử

Sự kiện nổi bật đánh dấu sự khởi đầu của lý thuyết thông tin là bài báo của Claude E. ShannonA Mathematical Theory of Communication” ở Bell System Technical Journal vào tháng 7 và tháng 10 năm 1948.

Trước bài báo này, một số ý tưởng về lý thuyết thông tin đã được phát triển tại Bell Labs, trong trường hợp đặc biệt khi tất cả các sự kiện đều có cùng xác suất. Bài báo năm 1924 của Harry Nyquist, “Certain Factors Affecting Telegraph Speed”, chứa một phần lý thuyết định lượng “tri thức” (intelligence) và “tốc độ đường truyền” (line speed), đưa ra mối liên hệ W = Klogm, trong đó W là tốc độ dẫn truyền tri thức, m là số cấp điện áp có thể sử dụng tại mỗi bước và K là một hằng số. Bài báo năm 1928 của Ralph Hartley, “Transmission of Information”, sử dụng thuật ngữ “thông tin” (information) như một đại lượng đo được, thể hiện khả năng phân biệt giữa các dãy kí hiệu của người nhận, do đó lượng hóa thông tin bởi H = logSn = nlogS, trong đó S là số kí hiệu có thể sử dụng, và n là số kí hiệu được truyền đi. Đơn vị tự nhiên của thông tin do đó là một chữ số thập phân, sau này được đổi tên là hartley để ghi danh đóng góp của ông, là một đơn vị đo thông tin. Năm 1940, Alan Turing đã sử dụng những ý tưởng tương tự cho phân tích thông kê để phá bộ mã Enigma của Đức trong chiến tranh thế giới thứ hai.

Phần lớn lý thuyết toán học đằng sau lý thuyết thông tin với các sự kiện có xác suất khác nhau được xây dựng trong ngành nhiệt động học bởi Ludwig BoltzmannJ. Willard Gibbs. Mối liên hệ giữa entropy thông tin và entropy nhiệt động học, bao gồm đóng góp quan trọng của Rolf Landauer trong thập kỉ 1960, được mô tả trong trang Entropy trong nhiệt động học và lý thuyết thông tin.

Đo lường thông tin

Bài chi tiết: Đo lường thông tin

Lý thuyết thông tin được xây dựng dựa trên lý thuyết xác suấtthống kê. Thông số quan trọng nhất của thông tin là entropy, lượng thông tin trong một biến ngẫu nhiên, và thông tin tương hỗ, lượng thông tin chung giữa hai biến ngẫu nhiên.

Entropy

Entropy của một phép thử Bernoulli dưới dạng hàm số của xác suất thành công, thường gọi là hàm entropy nhị phân, Hb(p). Entropy mỗi lần thử tối đa là 1 bit khi hai kết quả có cùng khả năng xảy ra, như trong một lần tung đồng xu công bằng.

Nếu \mathbb{X} là tập hợp tất cả các thông điệp {x1,…,xn} mà X có thể nhận giá trị, và p(x) là xác suất X nhận giá trị x \in \mathbb X, thì entropy của X được định nghĩa như sau:[8]

 H(X) = \mathbb{E}_{X} [I(x)] = -\sum_{x \in \mathbb{X}} p(x) \log p(x).

Trường hợp đặc biệt của entropy thông tin cho biến ngẫu nhiên với đúng hai khả năng gọi là hàm entropy nhị phân, thường được tính theo lôgarit cơ số 2:

H_\mbox{b}(p) = - p \log_2 p - (1-p)\log_2 (1-p).\,

Entropy hợp

Entropy hợp của hai biến ngẫu nhiên rời rạc XY là entropy của cặp (X, Y). Có nghĩa là nếu XYđộc lập thì entropy hợp là tổng của entropy của mỗi biến.

H(X, Y) = \mathbb{E}_{X,Y} [-\log p(x,y)] = - \sum_{x, y} p(x, y) \log p(x, y) \,

Entropy có điều kiện

Entropy có điều kiện của X cho trước Y là giá trị kì vọng của entropy của X theo phân bố của Y.

H(X|Y) = \mathbb E_Y [H(X|y)] = -\sum_{y \in Y} p(y) \sum_{x \in X} p(x|y) \log p(x|y) = -\sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(y)}.

Một tính chất cơ bản của entropy có điều kiện là

H(X|Y) = H(X,Y) - H(Y) .\,

Thông tin tương hỗ

Thông tin tương hỗ đo lượng thông tin thu được về một biến ngẫu nhiên thông qua giá trị của một biến ngẫu nhiên khác.

I(X;Y) = \mathbb{E}_{X,Y} [SI(x,y)] = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)\, p(y)}

Một tính chất cơ bản của thông tin tương hỗ là

I(X;Y) = H(X) - H(X|Y).\,

Thông tin tương hỗ có tính chất đối xứng:

I(X;Y) = I(Y;X) = H(X) + H(Y) - H(X,Y).\,

Thông tin tương hỗ có thể được biểu diễn dưới dạng khoảng cách Kullback-Leibler của phân bố hậu nghiệm của X nếu biết giá trị của Yphân bố tiền nghiệm của X:

I(X;Y) = \mathbb E_{p(y)} [D_{\mathrm{KL}}( p(X|Y=y) \| p(X) )].

Nói cách khác, độ đo này xác định, về mặt trung bình, sự thay đổi của phân bố của X nếu biết giá trị của Y. Giá trị này còn có thể tính bằng khoảng cách giữa tích của các phân bố biên với phân bố hợp:

I(X; Y) = D_{\mathrm{KL}}(p(X,Y) \| p(X)p(Y)).

Khoảng cách Kullback-Leibler

Khoảng cách Kullback-Leibler (hoặc entropy tương đối) là một cách so sánh hai phân bố: phân bố “thật” p(x) và một phân bố bất kì q(x). Nó được định nghĩa như sau:

D_{\mathrm{KL}}(p(X) \| q(X)) = \sum_{x \in X} -p(x) \log {q(x)} \, - \, \left( -p(x) \log {p(x)}\right) = \sum_{x \in X} p(x) \log \frac{p(x)}{q(x)}.

Mặc dù đôi khi nó được sử dụng như một “khoảng cách metric”, khoảng cách Kullback-Leibler không phải là một metric do nó không đối xứng và không thỏa mãn bất đẳng thức tam giác.

Các thông số khác

Một vài thông số khác trong lý thuyết thông tin bao gồm entropy Rényi, entropy vi phân, thông tin tương hỗ có điều kiện.

Lý thuyết mã hóa

Bài chi tiết: Lý thuyết mã hóa

Một bức ảnh các vết xước trên bề mặt của một đĩa CD-R. Nhạc và dữ liệu lưu trên CD được mã hóa bằng mã tự sửa lỗi và do đó vẫn có thể đọc được ngay cả khi có những vết xước nhỏ, bằng cách sử dụng kĩ thuật phát hiện và sửa lỗi.

Lý thuyết mã hóa là một trong những ứng dụng quan trọng và trực tiếp nhất của lý thuyết thông tin. Nó có thể được chia làm lý thuyết mã hóa nguồn và lý thuyết mã hóa kênh. Sử dụng kết quả thống kê cho dữ liệu, lý thuyết thông tin định lượng số bit cần thiết để lưu trữ dữ liệu (chính là entropy thông tin của dữ liệu).

  • Nén dữ liệu (mã hóa nguồn): Có hai hình thức nén dữ liệu:
  1. Nén không mất dữ liệu: dữ liệu phải được khôi phục chính xác
  2. Nén mất dữ liệu: phân bổ đủ số bit cần thiết để khôi phục dữ liệu, trong một độ chính xác định trước, đo bởi một hàm biến dạng.
  • Mã sửa lỗi (mã hóa kênh): Khi nén dữ liệu đã loại bỏ hoàn toàn phần dữ liệu thừa, một mã sửa lỗi thêm vào một số thông tin dự phòng để có thể truyền dữ liệu một cách hiệu quả và trung thực qua một kênh nhiễu.

Cách phân chia lý thuyết mã hóa thành nén và truyền được giải thích bởi các định lý truyền thông tin, hoặc các định lý phân chia nguồn-kênh, trong đó lý giải việc sử dụng bit làm đơn vị chung cho thông tin trong nhiều bối cảnh khác nhau. Tuy nhiên các định lý này chỉ đúng trong trường hợp một người gửi muốn truyền thông tin cho đúng một người nhận. Trong trường hợp có nhiều người gửi (kênh đa truy cập), hoặc nhiều người nhận (kênh phát sóng), hoặc có người trung gian giúp đỡ (kênh tiếp sức), hoặc tổng quát hơn, trong mạng máy tính, việc nén rồi truyền có thể không còn tối ưu. Lý thuyết thông tin trên mạng nghiên cứu về những mô hình truyền thông nhiều đối tượng.

Ghi chú

  1. ^ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code. The MIT press (1997).
  2. ^ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
  3. ^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
  4. ^ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
  5. ^ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620
  6. ^ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories
  7. ^ David R. Anderson (1 tháng 11 năm 2003). “Some background on why people in the empirical sciences may want to better understand the information-theoretic methods” định dạng (pdf). Truy cập 23 tháng 6 năm 2010.
  8. ^ Fazlollah M. Reza (1961, 1994). An Introduction to Information Theory. Dover Publications, Inc., New York. ISBN 0-486-68210-2.

Các công trình cổ điển

—————–&&—————–