18.11. Lý thuyết Thông tin

Vũ trụ mà chúng ta đang sống thì tràn ngập với thông tin. Thông tin cung cấp một ngôn ngữ chung giúp vượt qua rào cản ngăn cách nhiều lĩnh vực riêng biệt: từ thơ của Shakespeare đến các bài báo khoa học của các nhà nghiên cứu trên Cornell ArXiv, từ bản in Đêm Đầy Sao của Van Gogh đến Bản Giao Hưởng Số 5 của Beethoven, từ ngôn ngữ lập trình đầu tiên Plankalkül đến các thuật toán học máy hiện đại nhất. Mọi thứ phải tuân theo các quy tắc của lý thuyết thông tin, bất kể chúng ở định dạng nào. Với lý thuyết thông tin, chúng ta có thể đo lường và so sánh lượng thông tin có trong các tín hiệu khác nhau. Trong phần này, chúng ta sẽ nghiên cứu các khái niệm cơ bản của lý thuyết thông tin và các ứng dụng của lý thuyết thông tin trong học máy.

Trước khi bắt đầu, chúng ta hãy phác thảo mối quan hệ giữa học máy và lý thuyết thông tin. Mục tiêu của học máy là trích xuất các đặc trưng đáng chú ý từ dữ liệu và đưa ra các dự đoán quan trọng. Mặt khác, lý thuyết thông tin nghiên cứu vấn đề mã hóa, giải mã, truyền và thao tác với thông tin. Do vậy, lý thuyết thông tin cung cấp ngôn ngữ cơ bản để thảo luận về việc xử lý thông tin trong các hệ thống học máy. Ví dụ: nhiều ứng dụng học máy sử dụng mất mát entropy chéo như được mô tả trong Section 3.4. Mất mát này có thể được trực tiếp rút ra từ các quan điểm từ góc nhìn lý thuyết thông tin.

18.11.1. Thông tin

Ta hãy bắt đầu với “linh hồn” của lý thuyết thông tin: thông tin. Thông tin có thể được mã hóa trong bất kỳ thứ gì với một hoặc nhiều chuỗi định dạng mã hóa. Ta giả sử thử chính mình đưa ra một định nghĩa cho khái niệm thông tin. Ta có thể bắt đầu từ đâu?

Hãy xem thí nghiệm tưởng tượng sau đây. Ta có một người bạn với một bộ bài. Họ sẽ xáo trộn bộ bài, lật qua một số lá bài và cho chúng ta biết vài điều về các quân bài. Chúng ta sẽ thử đánh giá nội dung thông tin của từng phát biểu sau đây.

Đầu tiên, họ lật một lá và nói, “Tôi thấy một lá bài.” Điều này không cung cấp cho ta thông tin nào. Rõ ràng là trong trường hợp này chúng ta đã biết chắc chắn mệnh đề trên là đúng nên lượng thông tin mà nó chứa sẽ là 0.

Tiếp theo, họ lật một lá khác và nói, “Tôi thấy một lá cơ.” Điều này cung cấp cho ta một chút thông tin, mà trên thực tế chỉ có thể có \(4\) loại chất khác nhau, mỗi chất đều có khả năng như nhau, vì vậy ta không ngạc nhiên trước kết quả này. Ta hy vọng rằng dù thông tin được đo đạc dưới bất kể hình thức nào, sự kiện này nên có hàm lượng thông tin thấp.

Tiếp theo, họ lật một lá và nói, “Đây là quân \(3\) bích.”. Câu trên chứa nhiều thông tin hơn. Quả thực có \(52\) kết quả tương đương có thể xảy ra, và ta đã được cho biết đó là lá bài nào. Đây là một lượng thông tin trung bình.

Hãy đi đến cực hạn. Giả sử rằng cuối cùng họ lật từng lá bài từ bộ bài và đọc ra toàn bộ trình tự của bộ bài đã bị xáo trộn đó. Có \(52!\) các thứ tự khác nhau cho bộ bài với khả năng như nhau, vì vậy chúng ta cần rất nhiều thông tin để biết được chính xác trình tự rút bài.

Bất kỳ khái niệm thông tin nào chúng ta phát triển phải phù hợp với trực giác này. Thật vậy, trong phần tiếp theo, chúng ta sẽ học cách tính toán rằng các sự kiện trên có tương ứng \(0\text{ bit}\), \(2\text{ bit}\), \(~5.7\text{ bit}\), và \(~225.6\text{ bit}\) thông tin.

Nếu đọc hết những thí nghiệm tưởng tượng này, chúng ta thấy một ý tưởng tự nhiên. Để khởi đầu, thay vì quan tâm đến kiến thức đã biết, chúng ta có thể xây dựng ý tưởng là thông tin đại diện cho mức độ bất ngờ hoặc xác suất trừu tượng của sự kiện. Ví dụ, nếu chúng ta muốn mô tả một sự kiện hiếm gặp, chúng ta cần rất nhiều thông tin. Đối với một sự kiện phổ biến, chúng ta có thể không cần nhiều thông tin.

Năm 1948, Claude E. Shannon thiết lập lĩnh vực lý thuyết thông tin qua bài báo khoa học Lý thuyết Toán cho Truyền tải Thông tin - A Mathematical Theory of Communication [Shannon, 1948]. Trong bài báo của mình, Shannon đưa ra khái niệm entropy thông tin. Chúng ta sẽ bắt đầu từ đây.

18.11.1.1. Lượng tin

Vì thông tin biểu diễn xác suất trừu tượng của một sự kiện, làm thế nào để chúng ta ánh xạ xác suất đó thành số lượng bit? Shannon đã giới thiệu thuật ngữ bit làm đơn vị thông tin, mà ban đầu được đề xuất bởi John Tukey. Vậy “bit” là gì và tại sao ta sử dụng nó để đo lường thông tin? Trong quá khứ, một máy phát tín hiệu chỉ có thể gửi hoặc nhận hai loại mã: \(0\) và \(1\). Mà thật ra mã hóa nhị phân vẫn được sử dụng phổ biến trên tất cả các máy tính kỹ thuật số hiện đại. Bằng cách này, bất kỳ thông tin nào cũng được mã hóa bởi một chuỗi \(0\) và \(1\). Và do đó, một chuỗi các chữ số nhị phân (binary) có độ dài \(n\) chứa \(n\) bit thông tin.

Bây giờ, giả sử rằng đối với bất kỳ chuỗi mã nào, mỗi giá trị \(0\) hoặc \(1\) xuất hiện với xác suất là \(\frac{1}{2}\). Do đó, sự kiện \(X\) với một chuỗi mã có độ dài \(n\), xảy ra với xác suất \(\frac{1}{2^n}\). Đồng thời, như chúng tôi đã đề cập trước đây, chuỗi số này chứa \(n\) bit thông tin. Vì vậy, liệu có thể tổng quát hóa thành một hàm toán học chuyển xác suất \(p\) thành số lượng bit không? Shannon đưa ra câu trả lời bằng cách định nghĩa lượng tin

(18.11.1)\[I(X) = - \log_2 (p),\]

là số bit thông tin ta đã nhận cho sự kiện \(X\) này. Lưu ý rằng ta sẽ luôn sử dụng logarit cơ số 2 trong phần này. Để đơn giản, phần còn lại của phần này sẽ bỏ qua cơ số 2 trong ký hiệu logarit, tức là \(\log(.)\) luôn có nghĩa là \(\log_2(.)\). Ví dụ: mã “0010” có lượng tin là

(18.11.2)\[I(\text{"0010"}) = - \log (p(\text{"0010"})) = - \log \left( \frac{1}{2^4} \right) = 4 \text{ bits}.\]

Chúng ta có thể tính toán lượng tin như phần dưới đây. Trước đó, hãy nhập tất cả các gói cần thiết trong phần này.

from mxnet import np
from mxnet.metric import NegativeLogLikelihood
from mxnet.ndarray import nansum
import random

def self_information(p):
    return -np.log2(p)

self_information(1 / 64)

6.0

18.11.2. Entropy

Do lượng tin chỉ đo lường thông tin từ một biến cố rời rạc đơn lẻ, chúng ta cần một thước đo khái quát hơn cho cả biến ngẫu nhiên có phân bố rời rạc và liên tục.

18.11.2.1. Phát triển Lý thuyết Entropy

Hãy phân tích cụ thể hơn. Dưới đây là các phát biểu không chính thức của các tiên đề Shannon về entropy. Chúng buộc ta đi tới một định nghĩa độc nhất về thông tin. Một phiên bản chính quy của những tiên đề này cùng với một số tiên đề khác có thể được tìm thấy trong [Csiszar, 2008].

1. Thông tin thu được bằng cách quan sát một biến ngẫu nhiên không phụ thuộc vào các yếu tố, hay sự xuất hiện của các yếu tố bổ sung mà có xác suất bằng 0.
2. Thông tin thu được bằng cách quan sát hai biến ngẫu nhiên không lớn hơn tổng thông tin thu được khi quan sát chúng một cách riêng rẽ. Nếu hai biến ngẫu nhiên là độc lập thì thông tin thu được từ hai cách bằng nhau.
3. Thông tin thu được khi quan sát những biến cố (gần như) chắc chắn thì (gần như) bằng 0.

Việc chứng minh các tiên đề trên nằm ngoài phạm vi của cuốn sách, điều quan trọng cần nhớ là chúng xác định một cách độc nhất hình thái mà entropy phải có. Chỉ có duy nhất một điều chưa xác định từ những phát biểu trên là về việc chọn đơn vị cho entropy, mà điều này thường được chuẩn hóa bằng cách đặt thông tin cung cấp bởi một lần lật đồng xu cân đối đồng chất là một bit, như đã thấy trước đó.

18.11.2.2. Định nghĩa

Cho một biến ngẫu nhiên \(X\) bất kỳ tuân theo phân phối xác suất \(P\) với hàm mật độ xác suất (p.d.f) hoặc hàm khối xác suất (p.m.f) \(p(x)\), ta đo lượng thông tin kỳ vọng thu được thông qua entropy (hoặc entropy Shannon):

(18.11.3)\[H(X) = - E_{x \sim P} [\log p(x)].\]

Cụ thể hơn, nếu \(X\) rời rạc:

(18.11.4)\[H(X) = - \sum_i p_i \log p_i \text{, where } p_i = P(X_i).\]

Ngược lại, nếu \(X\) liên tục, ta gọi là entropy vi phân (differential entropy):

(18.11.5)\[H(X) = - \int_x p(x) \log p(x) \; dx.\]

Chúng ta có thể định nghĩa entropy như sau.

def entropy(p):
    entropy = - p * np.log2(p)
    # Operator nansum will sum up the non-nan number
    out = nansum(entropy.as_nd_ndarray())
    return out

entropy(np.array([0.1, 0.5, 0.1, 0.3]))

[1.6854753]
<NDArray 1 @cpu(0)>

18.11.2.3. Diễn giải

Bạn có thể thắc mắc: trong định nghĩa entropy (18.11.3), tại sao chúng ta sử dụng kỳ vọng của logarit âm? Dưới đây là một số cách giải thích trực quan.

Đầu tiên, tại sao chúng ta sử dụng hàm logarit \(\log\)? Giả sử \(p(x) = f_1(x) f_2(x) \ldots, f_n(x)\), khi mỗi hàm thành tố \(f_i(x)\) độc lập lẫn nhau. Điều này nghĩa là mỗi \(f_i(x)\) đóng góp một cách độc lập vào tổng thông tin thu được từ \(p(x)\). Như đã thảo luận ở trên, ta muốn công thức entropy là phép cộng trên các biến ngẫu nhiên độc lập. May mắn thay, hàm \(\log\) có thể chuyển tích thành tổng.

Tiếp theo, tại sao chúng ta sử dụng \(\log\) âm? Một cách trực quan, những biến cố xảy ra thường xuyên sẽ chứa ít thông tin hơn những biến cố hiếm vì ta thường thu được nhiều thông tin hơn từ những trường hợp bất thường. Do đó, ta cần thiết lập mối quan hệ đơn điệu giảm giữa xác suất của biến cố và entropy của chúng, và muốn entropy luôn dương (vì các quan sát mới không nên buộc ta quên đi những gì đã biết). Tuy nhiên, hàm \(\log\) lại là đơn điệu tăng, và có giá trị âm với xác suất trong đoạn \([0, 1]\). Vậy nên ta thêm dấu âm vào trước hàm \(\log\).

Cuối cùng, hàm kỳ vọng đến từ đâu? Xét một biến ngẫu nhiên \(X\). Ta có thể diễn giải lượng tin (self-information) (\(-\log(p)\)) như mức độ bất ngờ khi quan sát được một kết quả cụ thể nào đó. Thật vậy, khi xác suất xấp xỉ bằng 0, mức độ bất ngờ tiến tới vô cùng. Tương tự, chúng ta có thể diễn giải entropy như mức độ bất ngờ trung bình từ việc quan sát \(X\). Ví dụ, tưởng tượng một hệ thống máy đánh bạc đưa ra các ký hiệu độc lập \({s_1, \ldots, s_k}\) với xác suất lần lượt là \({p_1, \ldots, p_k}\). Khi đó, entropy của hệ thống này bằng với lượng tin trung bình thu được từ việc quan sát mỗi kết quả, tức:

(18.11.6)\[H(S) = \sum_i {p_i \cdot I(s_i)} = - \sum_i {p_i \cdot \log p_i}.\]

18.11.2.4. Tính chất của Entropy

Bằng các ví dụ và diễn giải phía trên, ta có thể rút ra các tính chất sau của entropy (18.11.3). Ở đây, ta xem \(X\) là một biến cố và \(P\) là phân phối xác suất của \(X\).

• Entropy có giá trị không âm, tức \(H(X) \geq 0, \forall X\).

• Nếu \(X \sim P\) có hàm mật độ xác suất hoặc hàm khối xác suất \(p(x)\), và ta muốn ước lượng \(P\) bằng một phân phối xác suất mới \(Q\) với hàm mật độ xác suất hoặc hàm khối xác suất \(q(x)\), ta có:

  (18.11.7)\[ \begin{align}\begin{aligned}H(X) = - E_{x \sim P} [\log p(x)] \leq - E_{x \sim P} [\log q(x)], \text{ dấu bằng xảy ra khi và chỉ khi } P = Q.\\Ngoài ra, :math:`H(X)` cho biết cận dưới của số bit trung bình cần\end{aligned}\end{align} \]

  dùng để mã hóa các giá trị lấy từ \(P\).

• Nếu \(X \sim P\), \(x\) sẽ chứa lượng thông tin cực đại nếu mọi biến cố khả dĩ chứa lượng thông tin như nhau. Cụ thể, nếu \(P\) là phân phối rời rạc với \(k\) lớp \(\{p_1, \ldots, p_k \}\):

  (18.11.8)\[ \begin{align}\begin{aligned}H(X) \leq \log(k), \text{ dấu bằng xảy ra khi và chỉ khi } p_i = \frac{1}{k}, \forall i.\\Nếu :math:`P` là phân phối liên tục thì sẽ phức tạp hơn. Tuy nhiên,\end{aligned}\end{align} \]

  nếu ta giả sử thêm rằng \(P\) có miền giá trị nằm trong một khoảng hữu hạn (với tất cả giá trị nằm trong khoảng \(0\) và \(1\)), \(P\) sẽ có entropy cực đại nếu nó là phân phối đều trong khoảng đó.

18.11.3. Thông tin Tương hỗ

Ta đã định nghĩa entropy của một biễn ngẫu nhiên \(X\) duy nhất, vậy còn entropy của một cặp biến ngẫu nhiên \((X,Y)\) thì sao? Ta xem xét khái niệm này để trả lời các câu hỏi: “Thông tin chứa trong cả \(X\) và \(Y\) sẽ trông như thế nào so với thông tin trong từng biến? Có thông tin thừa không, hay chúng đều độc nhất?”

Trong phần thảo luận dưới đây, chúng tôi sẽ luôn dùng \((X,Y)\) để ký hiệu một cặp biễn ngẫu nhiên tuân theo phân phối xác suất kết hợp \(P\) với hàm mật độ xác suất hoặc hàm khối xác suất \(p_{X,Y}(x,y)\), còn \(X\) và \(Y\) lần lượt tuân theo phân phối xác suất \(p_X(x)\) và \(p_Y(y)\).

18.11.3.1. Entropy Kết hợp

Tương tự như entropy của một biến ngẫu nhiên (18.11.3), ta định nghĩa entropy kết hợp (joint entropy) \(H(X,Y)\) của cặp biến ngẫu nhiên \((X,Y)\) như sau

(18.11.9)\[H(X, Y) = −E_{(x, y) \sim P} [\log p_{X, Y}(x, y)].\]

Nếu \((X,Y)\) là rời rạc:

(18.11.10)\[H(X, Y) = - \sum_{x} \sum_{y} p_{X, Y}(x, y) \log p_{X, Y}(x, y).\]

Mặt khác, nếu \((X,Y)\) là liên tục, ta định nghĩa entropy kết hợp vi phân (differential joint entropy) như sau:

(18.11.11)\[H(X, Y) = - \int_{x, y} p_{X, Y}(x, y) \ \log p_{X, Y}(x, y) \;dx \;dy.\]

Ta có thể xem (18.11.9) như tổng mức độ ngẫu nhiên của cặp biến ngẫu nhiên. Ở một cực trị, nếu chúng giống hệt nhau (\(X = Y\)), thông tin của cặp biến này chính là thông tin của từng biến: \(H(X,Y) = H(X) = H(Y)\). Ở cực trị còn lại, nếu \(X\) và \(Y\) độc lập thì \(H(X,Y) = H(X) + H(Y)\). Tất nhiên, thông tin chứa trong một cặp biến ngẫu nhiên sẽ không thể nhỏ hơn entropy của từng biến ngẫu nhiên và không thể lớn hơn tổng entropy của chúng.

(18.11.12)\[H(X), H(Y) \le H(X, Y) \le H(X) + H(Y).\]

Hãy cùng lập trình entropy kết hợp từ đầu.

def joint_entropy(p_xy):
    joint_ent = -p_xy * np.log2(p_xy)
    # Operator nansum will sum up the non-nan number
    out = nansum(joint_ent.as_nd_ndarray())
    return out

joint_entropy(np.array([[0.1, 0.5], [0.1, 0.3]]))

[1.6854753]
<NDArray 1 @cpu(0)>

Hãy để ý rằng đây chính là đoạn mã từ trước, nhưng giờ ta hiểu nó theo cách khác khi làm việc với phân phối kết hợp của hai biến ngẫu nhiên.

18.11.3.2. Entropy có Điều kiện

Entropy kết hợp định nghĩa phía trên là lượng thông tin chứa trong một cặp biến ngẫu nhiên. Đại lượng này khá hữu ích, nhưng thường nó không phải là thứ mà ta quan tâm. Hãy xem xét trong ngữ cảnh học máy. Gọi \(X\) là biến ngẫu nhiên (hoặc vector biến ngẫu nhiên) mô tả giá trị các điểm ảnh trong một bức ảnh, và \(Y\) là biến ngẫu nhiên mô tả nhãn lớp. \(X\) chứa một lượng thông tin rất lớn — do một bức ảnh tự nhiên khá phức tạp. Tuy nhiên, lượng thông tin trong \(Y\) khi ta đã thấy bức ảnh nên là nhỏ. Tất nhiên, bức ảnh chứa một chữ số cũng nên chứa thông tin đó là chữ số nào, trừ khi chữ số trong ảnh không thể đọc được. Vì vậy, để tiếp tục mở rộng lý thuyết thông tin, ta cần suy luận được lượng thông tin trong một biến ngẫu nhiên khi nó phụ thuộc vào một biến khác.

Trong lý thuyết xác suất, xác suất có điều kiện đo mối quan hệ giữa các biến. Bây giờ ta muốn định nghĩa entropy có điều kiện (conditional entropy) \(H(Y \mid X)\) theo cách tương tự dưới dạng:

(18.11.13)\[H(Y \mid X) = - E_{(x, y) \sim P} [\log p(y \mid x)],\]

trong đó \(p(y \mid x) = \frac{p_{X, Y}(x, y)}{p_X(x)}\) là xác suất có điều kiện. Cụ thể, nếu \((X,Y)\) là rời rạc, ta có:

(18.11.14)\[H(Y \mid X) = - \sum_{x} \sum_{y} p(x, y) \log p(y \mid x).\]

Nếu \((X,Y)\) là liên tục, entropy có điều kiện vi phân được định nghĩa tương tự như sau:

(18.11.15)\[H(Y \mid X) = - \int_x \int_y p(x, y) \ \log p(y \mid x) \;dx \;dy.\]

Bây giờ một câu hỏi tự nhiên là: entropy có điều kiện \(H(Y \mid X)\) có mối quan hệ gì với entropy \(H(X)\) và entropy kết hợp \(H(X,Y)\)? Sử dụng các định nghĩa ở trên, ta có thể biểu diễn mối quan hệ đó một cách gọn gàng:

(18.11.16)\[H(Y \mid X) = H(X, Y) - H(X).\]

Điều này có thể được giải thích một cách trực quan như sau: thông tin trong \(Y\) khi biết \(X\) (\(H(Y \mid X)\)) bằng với thông tin trong cả \(X\) và \(Y\) (\(H(X, Y)\)) trừ đi thông tin đã có trong \(X\). Nó cho ta biết thông tin có trong \(Y\) mà không chứa trong \(X\).

Bây giờ, hãy cùng lập trình entropy có điều kiện (18.11.13) từ đầu.

def conditional_entropy(p_xy, p_x):
    p_y_given_x = p_xy/p_x
    cond_ent = -p_xy * np.log2(p_y_given_x)
    # Operator nansum will sum up the non-nan number
    out = nansum(cond_ent.as_nd_ndarray())
    return out

conditional_entropy(np.array([[0.1, 0.5], [0.2, 0.3]]), np.array([0.2, 0.8]))

[0.8635472]
<NDArray 1 @cpu(0)>

18.11.3.3. Thông tin Tương hỗ

Với định nghĩa trước đó về các biến ngẫu nhiên \((X, Y)\), bạn có thể tự hỏi:” Ta đã biết có bao nhiêu thông tin nằm trong Y nhưng không nằm ở trong X, liệu có thể biết được có bao nhiêu thông tin giống nhau giữa \(X\) và \(Y\) không?”. Đại lượng đó là thông tin tương hỗ của \((X, Y)\), ký hiệu là \(I(X, Y)\).

Thay vì đề cập ngay đến định nghĩa chính thức, hãy cùng luyện tập trực giác bằng cách suy luận biểu thức thông tin tương hỗ dựa trên những khái niệm mà chúng ta đã xây dựng trước đó. Mục tiêu của chúng ta là tìm được thông tin giống nhau giữa hai biến ngẫu nhiên. Ta có thể thử bắt đầu với thông tin chứa trong cả \(X\) và \(Y\), sau đó bỏ đi những thông tin không giống nhau. Thông tin chứa trong cả \(X\) và \(Y\) là \(H(X, Y)\). Thông tin nằm trong \(X\) nhưng không nằm trong \(Y\) là H(X :raw-latex:`\mid `Y)$, tương tự, thông tin nằm trong :math:`Y` nhưng không nằm trong \(X\) là \(H(Y \mid X)\). Do đó, ta có thông tin tương hỗ như sau:

(18.11.17)\[I(X, Y) = H(X, Y) - H(Y \mid X) − H(X \mid Y).\]

Thật vậy, đây là định nghĩa hợp lệ của thông tin tương hỗ. Nếu ta thay các số hạng trên bằng định nghĩa của chúng, tổng hợp lại, rồi biến đổi đại số một chút, ta sẽ có:

(18.11.18)\[I(X, Y) = E_{x} E_{y} \left\{ p_{X, Y}(x, y) \log\frac{p_{X, Y}(x, y)}{p_X(x) p_Y(y)} \right\}.\]

Ta có thể tóm tắt tất cả những mối quan hệ nêu trên ở hình Fig. 18.11.1. Đây là một minh họa trực quan tuyệt vời để hiểu tại sao các mệnh đề sau đây đều tương đương với \(I(X, Y)\).

• \(H(X) − H(X \mid Y)\)
• \(H(Y) − H(Y \mid X)\)
• \(H(X) + H(Y) − H(X, Y)\)

Fig. 18.11.1 Mối quan hệ giữa thông tin tương hỗ với entropy kết hợp và entropy có điều kiện.

Theo nhiều cách ta có thể xem thông tin tương hỗ (18.11.18) như là phần mở rộng của hệ số tương quan trong Section 18.6. Đại lượng này cho phép chúng ta hiểu không chỉ về mối quan hệ tuyến tính của các biến, mà còn cả lượng thông tin tối đa mà hai biến chia sẻ với nhau.

Bây giờ, hãy cùng lập trình thông tin tương hỗ từ đầu.

def mutual_information(p_xy, p_x, p_y):
    p = p_xy / (p_x * p_y)
    mutual = p_xy * np.log2(p)
    # Operator nansum will sum up the non-nan number
    out = nansum(mutual.as_nd_ndarray())
    return out

mutual_information(np.array([[0.1, 0.5], [0.1, 0.3]]),
                   np.array([0.2, 0.8]), np.array([[0.75, 0.25]]))

[0.7194603]
<NDArray 1 @cpu(0)>

18.11.3.4. Tính chất của Thông tin Tương Hỗ

Thay vì ghi nhớ định nghĩa thông tin tương hỗ (18.11.18), bạn chỉ cần lưu ý những tính chất nổi trội của nó:

• Thông tin tương hỗ có tính đối xứng: \(I(X, Y) = I(Y, X)\).

• Thông tin tương hỗ có giá trị không âm: \(I(X, Y) \geq 0\).

• \(I(X, Y) = 0\) khi và chỉ khi \(X\) và \(Y\) là hai biến độc lập. Ví dụ, nếu \(X\) và \(Y\) độc lập thì việc biết thông tin của \(Y\) không cho ta thông tin của \(X\) và ngược lại, do đó thông tin tương hỗ của chúng bằng 0.

• Ngoài ra, nếu \(X\) là hàm nghịch đảo của \(Y\), thì \(Y\) và \(X\) có chung toàn bộ thông tin và

  (18.11.19)\[I(X, Y) = H(Y) = H(X).\]

18.11.3.5. Thông tin Tương hỗ theo từng Điểm

Khi bắt đầu tìm hiểu về entropy ở đầu chương này, ta đã diễn giải \(-\log(p_X(x))\) như mức độ ngạc nhiên với kết quả cụ thể của biến ngẫu nhiên. Ta có thể diễn giải tương tự với logarit trong thông tin tương hỗ, thường được biết đến với cái tên thông tin tương hỗ theo từng điểm (pointwise mutual information):

(18.11.20)\[\mathrm{pmi}(x, y) = \log\frac{p_{X, Y}(x, y)}{p_X(x) p_Y(y)}.\]

(18.11.20) so sánh xác suất \(x\) và \(y\) xảy ra đồng thời qua phân phối kết hợp với khi chúng cùng xảy ra qua 2 phân phối ngẫu nhiên độc lập. Nếu kết quả lớn và dương, thì \(x\) và \(y\) có xác suất xảy ra đồng thời qua phân phối kết hợp cao hơn nhiều. (chú ý: mẫu số :math:`p_X(x) p_Y(y)` là xác suất của hai đầu ra độc lập), ngược lại nếu kết quả lớn và âm, thì xác suất xảy ra đồng thời qua phân phối kết hợp sẽ rất thấp.

Điều này cho phép ta diễn giải thông tin tương hỗ (18.11.18) như độ ngạc nhiên trung bình khi hai biến cố xảy ra đồng thời so với độ ngạc nhiên khi chúng là hai biến độc lập.

18.11.3.6. Ứng dụng Thông tin Tương hỗ

Thông tin tương hỗ có thể hơi trừu tượng theo định nghĩa thuần túy, vậy nó liên quan như thế nào đến học máy? Trong xử lý ngôn ngữ tự nhiên, một trong những vấn đề khó khăn nhất là giải quyết sự mơ hồ, tức nghĩa của từ đang không rõ ràng trong ngữ cảnh. Ví dụ, gần đây có một tiêu đề trong bản tin thông báo rằng “Amazon đang cháy”. Bạn có thể tự hỏi là liệu công ty Amazon có một tòa nhà bị cháy, hay rừng Amazon đang cháy.

Thông tin tương hỗ có thể giúp ta giải quyết sự mơ hồ này. Đầu tiên, ta tìm nhóm từ có thông tin tương hỗ tương đối lớn tới công ty Amazon, chẳng hạn như thương mại điện tử, công nghệ và trực tuyến. Thứ hai, ta tìm một nhóm từ khác có một thông tin tương hỗ tương đối lớn tới rừng mưa Amazon, chẳng hạn như mưa, rừng và nhiệt đới. Khi cần phân biệt “Amazon”, ta có thể so sánh nhóm nào xuất hiện nhiều hơn trong ngữ cảnh của từ này. Trong trường hợp này, bài báo sẽ tiếp tục mô tả khu rừng và ngữ cảnh sẽ được làm rõ.

18.11.4. Phân kỳ Kullback–Leibler

Như đã thảo luận trong Section 2.3, ta có thể sử dụng chuẩn (norms) để đo khoảng cách giữa hai điểm trong không gian với số chiều bất kỳ. Ta muốn thực hiện công việc tương tự với các phân phối xác suất. Có nhiều cách để giải quyết vấn đề này, nhưng lý thuyết thông tin cung cấp một trong những cách tốt nhất. Bây giờ ta sẽ tìm hiểu về phân kỳ Kullback–Leibler (KL) (Kullback–Leibler divergence), là phương pháp đo lường xem hai phân phối có gần nhau hay không.

18.11.4.1. Định nghĩa

Cho một biến ngẫu nhiên \(X\) tuân theo phân phối xác suất \(P\) với hàm mật độ xác suất hay hàm khối xác suất là \(p(x)\), và ta ước lượng \(P\) bằng một phân phối xác suất \(Q\) khác với hàm mật độ xác suất hoặc hàm khối xác suất \(q(x)\). Khi đó, phân kỳ Kullback–Leibler (hoặc entropy tương đối) giữa \(P\) và \(Q\) là

(18.11.21)\[D_{\mathrm{KL}}(P\|Q) = E_{x \sim P} \left[ \log \frac{p(x)}{q(x)} \right].\]

Như với thông tin tương hỗ theo từng điểm (18.11.20), ta lại có thể diễn giải hạng tử logarit: \(-\log \frac{q (x)}{p (x)} = -\log(q(x)) - (-\log(p(x)))\) sẽ lớn và dương nếu ta thấy \(x\) xuất hiện thường xuyên hơn theo phân phối \(P\) so với mức ta kỳ vọng cho phân phối \(Q\), và lớn và âm nếu chúng ta thấy kết quả ít hơn nhiều so với kỳ vọng. Theo cách này, ta có thể hiểu nó là mức độ ngạc nhiên tương đối khi quan sát phân phối mục tiêu so với phân phối tham chiếu.

Ta hãy thực hiện tính phân kỳ KL từ đầu.

def kl_divergence(p, q):
    kl = p * np.log2(p / q)
    out = nansum(kl.as_nd_ndarray())
    return out.abs().asscalar()

18.11.4.2. Các tính chất của Phân kỳ KL

Hãy cùng xem xét một số tính chất của phân kỳ KL (18.11.21).

• Phân kỳ KL là bất đối xứng, tức tồn tại \(P,Q\) sao cho

  (18.11.22)\[D_{\mathrm{KL}}(P\|Q) \neq D_{\mathrm{KL}}(Q\|P).\]

• Phân kỳ KL có giá trị không âm, tức

  (18.11.23)\[D_{\mathrm{KL}}(P\|Q) \geq 0.\]

  Chú ý rằng dấu bằng xảy ra chỉ khi \(P = Q\).

• Nếu tồn tại \(x\) sao cho \(p(x) > 0\) và \(q(x) = 0\) thì \(D_{\mathrm{KL}}(P\|Q) = \infty\).

• Phân kỳ KL có mối quan hệ mật thiết với thông tin tương hỗ. Ngoài các dạng trong Fig. 18.11.1, thông tin tương hỗ \(I(X, Y)\) về mặt số học cũng tương đương với các dạng sau:

  1. \(D_{\mathrm{KL}}(P(X, Y) \ \| \ P(X)P(Y))\);
  2. \(E_Y \{ D_{\mathrm{KL}}(P(X \mid Y) \ \| \ P(X)) \}\);
  3. \(E_X \{ D_{\mathrm{KL}}(P(Y \mid X) \ \| \ P(Y)) \}\).

  Với dạng đầu tiên, ta diễn giải thông tin tương hỗ dưới dạng phân kỳ KL giữa \(P(X, Y)\) và tích của \(P(X)\) và \(P(Y)\), đây là phép đo mức độ khác nhau của phân phối kết hợp so với phân phối khi hai biến là độc lập. Với dạng thứ hai, thông tin tương hỗ cho ta biết mức giảm trung bình trong độ bất định của \(Y\) xảy ra do việc biết được giá trị trong phân phối của \(X\). Dạng thứ ba cũng tương tự.

18.11.4.3. Ví dụ

Hãy cùng xét một ví dụ đơn giản để thấy rõ hơn tính bất đối xứng.

Đầu tiên, ta sinh ba tensor có độ dài \(10,000\) và sắp xếp chúng: một tensor mục tiêu \(p\) tuân theo phân phối chuẩn \(N(0, 1)\), và hai tensor tiềm năng \(q_1\) và \(q_2\) lần lượt tuân theo phân phối chuẩn \(N(-1, 1)\) và \(N(1, 1)\).

random.seed(1)

nd_len = 10000
p = np.random.normal(loc=0, scale=1, size=(nd_len, ))
q1 = np.random.normal(loc=-1, scale=1, size=(nd_len, ))
q2 = np.random.normal(loc=1, scale=1, size=(nd_len, ))

p = np.array(sorted(p.asnumpy()))
q1 = np.array(sorted(q1.asnumpy()))
q2 = np.array(sorted(q2.asnumpy()))

Do \(q_1\) và \(q_2\) đối xứng qua trục y (có \(x=0\)), ta kỳ vọng giá trị phân kỳ KL giữa \(D_{\mathrm{KL}}(p\|q_1)\) và \(D_{\mathrm{KL}}(p\|q_2)\) là như nhau. Như có thể thấy, \(D_{\mathrm{KL}}(p\|q_1)\) và \(D_{\mathrm{KL}}(p\|q_2)\) chỉ chênh nhau không đến 3%.

kl_pq1 = kl_divergence(p, q1)
kl_pq2 = kl_divergence(p, q2)
similar_percentage = abs(kl_pq1 - kl_pq2) / ((kl_pq1 + kl_pq2) / 2) * 100

kl_pq1, kl_pq2, similar_percentage

(8470.638, 8664.998, 2.268492904612395)

Trái lại, giá trị \(D_{\mathrm{KL}}(q_2 \|p)\) và \(D_{\mathrm{KL}}(p \| q_2)\) chênh nhau khá nhiều, với sai khác tới khoảng 40% như dưới đây.

kl_q2p = kl_divergence(q2, p)
differ_percentage = abs(kl_q2p - kl_pq2) / ((kl_q2p + kl_pq2) / 2) * 100

kl_q2p, differ_percentage

(13536.835, 43.88680093791528)

18.11.5. Entropy Chéo

Nếu bạn tò mò về ứng dụng của lý thuyết thông tin trong học sâu, đây là một ví dụ nhanh. Ta định nghĩa phân phối thực là \(P\) với phân phối xác suất \(p(x)\), và phân phối xấp xỉ là \(Q\) với phân phối xác suất \(q(x)\). Ta sẽ sử dụng các định nghĩa này trong suốt phần còn lại.

Giả sử ta cần giải bài toán phân loại nhị phân dựa vào \(n\) điểm dữ liệu cho trước {\(x_1, \ldots, x_n\)}. Ta mã hóa \(1\) và \(0\) lần lượt là lớp dương tính và âm tính cho nhãn \(y_i\), và mạng nơ-ron được tham số hóa bởi \(\theta\). Nếu ta tập trung vào việc tìm \(\theta\) tốt nhất sao cho \(\hat{y}_i= p_{\theta}(y_i \mid x_i)\), việc áp dụng hướng tiếp cận log hợp lý cực đại (maximum log-likelihood) là hoàn toàn tự nhiên như ta thấy trong Section 18.7. Cụ thể hơn, với nhãn thực \(y_i\) và các dự đoán \(\hat{y}_i= p_{\theta}(y_i \mid x_i)\), xác suất được phân loại thành nhãn dương là \(\pi_i= p_{\theta}(y_i = 1 \mid x_i)\). Do đó, hàm log hợp lý sẽ là

(18.11.24)\[\begin{split}\begin{aligned} l(\theta) &= \log L(\theta) \\ &= \log \prod_{i=1}^n \pi_i^{y_i} (1 - \pi_i)^{1 - y_i} \\ &= \sum_{i=1}^n y_i \log(\pi_i) + (1 - y_i) \log (1 - \pi_i). \\ \end{aligned}\end{split}\]

Việc cực đại hóa hàm log hợp lý \(l(\theta)\) giống hệt với việc cực tiểu hóa \(- l(\theta)\), và do đó ta có thể tìm \(\theta\) tốt nhất từ đây. Để khái quát hóa hàm mất mát trên với mọi phân phối, ta gọi \(-l(\theta)\) là mất mát entropy chéo (cross entropy loss) \(\mathrm{CE}(y, \hat{y})\), trong đó \(y\) tuân theo phân phối thực \(P\) và \(\hat{y}\) tuân theo phân phối ước lượng \(Q\).

Điều này được suy ra theo góc nhìn của hợp lý cực đại. Tuy nhiên, nếu quan sát kỹ hơn ta có thể thấy rằng các số hạng như \(\log(\pi_i)\) có tham gia vào phép tính, và đây là một dấu hiệu cho thấy ta có thể hiểu được biểu thức theo góc nhìn của lý thuyết thông tin.

18.11.5.1. Định nghĩa Chuẩn

Giống với phân kỳ KL, với biến ngẫu nhiên \(X\), ta cũng có thể đo được độ phân kỳ giữa phân phối ước lượng \(Q\) và phân phối thực \(P\) thông qua entropy chéo,

(18.11.25)\[\mathrm{CE}(P, Q) = - E_{x \sim P} [\log(q(x))].\]

Bằng cách sử dụng các tính chất của entropy đã liệt kê ở trên, ta có thể viết lại công thức trên dưới dạng tổng giữa entropy \(H(P)\) và phân kỳ KL giữa \(P\) và \(Q\), tức

(18.11.26)\[\mathrm{CE} (P, Q) = H(P) + D_{\mathrm{KL}}(P\|Q).\]

Ta có thể lập trình mất mát entropy chéo như dưới đây.

def cross_entropy(y_hat, y):
    ce = -np.log(y_hat[range(len(y_hat)), y])
    return ce.mean()

Giờ ta định nghĩa hai tensor cho nhãn và giá trị dự đoán, và tính mất mát entropy chéo của chúng.

labels = np.array([0, 2])
preds = np.array([[0.3, 0.6, 0.1], [0.2, 0.3, 0.5]])

cross_entropy(preds, labels)

array(0.94856)

18.11.5.2. Tính chất

Như đã ám chỉ ở đoạn đầu của phần này, entropy chéo (18.11.25) có thể được sử dụng để định nghĩa hàm mất mát trong bài toán tối ưu. Các mục tiêu sau là tương đương:

1. Cực đại hóa xác suất dự đoán của \(Q\) cho phân phối \(P\), tức \(E_{x \sim P} [\log (q(x))]\));
2. Cực tiểu hóa entropy chéo \(\mathrm{CE} (P, Q)\);
3. Cực tiểu hóa phân kỳ KL \(D_{\mathrm{KL}}(P\|Q)\).

Định nghĩa của entropy chéo gián tiếp chứng minh mối quan hệ tương đồng giữa mục tiêu 2 và mục tiêu 3, miễn là entropy của dữ liệu thực \(H(P)\) là hằng số.

18.11.5.3. Hàm Mục tiêu Entropy Chéo khi Phân loại Đa lớp

Nếu đi sâu vào hàm mục tiêu mất mát entropy chéo \(\mathrm{CE}\) cho bài toán phân loại, ta sẽ thấy rằng cực tiểu hóa \(\mathrm{CE}\) tương đương với cực đại hóa hàm log hợp lý \(L\).

Đề bắt đầu, giả sử ta có tập dữ liệu với \(n\) mẫu, được phân loại thành \(k\) lớp. Với mỗi mẫu dữ liệu \(i\), ta biểu diễn nhãn lớp \(k\) bất kì \(\mathbf{y}_i = (y_{i1}, \ldots, y_{ik})\) bằng biểu diễn one-hot. Cụ thể, nếu mẫu \(i\) thuộc về lớp \(j\) thì ta đặt phần tử thứ \(j\) bằng \(1\), và tất cả các phần tử khác bằng \(0\), tức

(18.11.27)\[\begin{split}y_{ij} = \begin{cases}1 & j \in J; \\ 0 &\text{otherwise.}\end{cases}\end{split}\]

Ví dụ, nếu một bài toán phân loại gồm có ba lớp \(A\), \(B\), và \(C\), thì các nhãn \(\mathbf{y}_i\) có thể được mã hóa thành {\(A: (1, 0, 0); B: (0, 1, 0); C: (0, 0, 1)\)}.

Giả sử mạng nơ-ron được tham số hóa bởi \(\theta\). Với vector nhãn gốc \(\mathbf{y}_i\) và dự đoán

(18.11.28)\[\hat{\mathbf{y}}_i= p_{\theta}(\mathbf{y}_i \mid \mathbf{x}_i) = \sum_{j=1}^k y_{ij} p_{\theta} (y_{ij} \mid \mathbf{x}_i).\]

Từ đó, mất mát entropy chéo sẽ là

(18.11.29)\[\begin{split}\mathrm{CE}(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{i=1}^n \mathbf{y}_i \log \hat{\mathbf{y}}_i = - \sum_{i=1}^n \sum_{j=1}^k y_{ij} \log{p_{\theta} (y_{ij} \mid \mathbf{x}_i)}.\\\end{split}\]

Mặt khác, ta cũng có thể tiếp cận bài toán thông qua ước lượng hợp lý cực đại. Đề bắt đầu, chúng tôi sẽ giới thiệu nhanh về phân phối đa thức (multinoulli distribution) \(k\) lớp. Đây là dạng mở rộng của phân phối Bernoulli từ hai lớp thành nhiều lớp. Nếu một biến ngẫu nhiên \(\mathbf{z} = (z_{1}, \ldots, z_{k})\) tuân theo phân phối đa thức \(k\) lớp với xác suất \(\mathbf{p} =\) (\(p_{1}, \ldots, p_{k}\)), tức

(18.11.30)\[ \begin{align}\begin{aligned}p(\mathbf{z}) = p(z_1, \ldots, z_k) = \mathrm{Multi} (p_1, \ldots, p_k), \text{ với } \sum_{i=1}^k p_i = 1,\\thì hàm khối xác suất (*probability mass function - p.m.f*) kết hợp của\end{aligned}\end{align} \]

\(\mathbf{z}\) bằng

(18.11.31)\[\mathbf{p}^\mathbf{z} = \prod_{j=1}^k p_{j}^{z_{j}}.\]

Có thể thấy nhãn của từng mẫu dữ liệu, \(\mathbf{y}_i\), tuân theo một phân phối đa thức \(k\) lớp với xác suất \(\boldsymbol{\pi} =\) (\(\pi_{1}, \ldots, \pi_{k}\)). Do đó, hàm khối xác suất kết hợp của mỗi mẫu dữ liệu là \(\mathbf{y}_i\) is \(\mathbf{\pi}^{\mathbf{y}_i} = \prod_{j=1}^k \pi_{j}^{y_{ij}}.\) Từ đây, hàm log hợp lý sẽ là

(18.11.32)\[\begin{split}\begin{aligned} l(\theta) = \log L(\theta) = \log \prod_{i=1}^n \boldsymbol{\pi}^{\mathbf{y}_i} = \log \prod_{i=1}^n \prod_{j=1}^k \pi_{j}^{y_{ij}} = \sum_{i=1}^n \sum_{j=1}^k y_{ij} \log{\pi_{j}}.\\ \end{aligned}\end{split}\]

Do trong ước lượng hợp lý cực đại, ta cực đại hóa hàm mục tiêu \(l(\theta)\) với \(\pi_{j} = p_{\theta} (y_{ij} \mid \mathbf{x}_i)\). Vậy nên với bài toán phân loại đa lớp bất kỳ, việc cực đại hóa hàm log hợp lý trên \(l(\theta)\) tương đương với việc cực tiểu hóa hàm mất mát CE \(\mathrm{CE}(y, \hat{y})\).

Để kiểm tra chứng minh trên, hãy áp dụng phép đo NegativeLogLikelihood được tích hợp sẵn. Với việc sử dụng labels và preds giống như ví dụ trước, ta sẽ thu được mất mát xấp xỉ giống ví dụ trước tới 5 số thập phân sau dấu phẩy.

nll_loss = NegativeLogLikelihood()
nll_loss.update(labels.as_nd_ndarray(), preds.as_nd_ndarray())
nll_loss.get()

('nll-loss', 0.9485599994659424)

18.11.6. Tóm tắt

• Lý thuyết thông tin là một lĩnh vực nghiên cứu về mã hóa, giải mã, truyền phát và xử lý thông tin.
• Entropy là đơn vị đo lượng thông tin có trong các tín hiệu khác nhau.
• Phân kỳ KL có thể đo khoảng cách giữa hai phân phối.
• Entropy Chéo có thể được coi như một hàm mục tiêu trong phân loại đa lớp. Việc cực tiểu hóa mất mát entropy chéo tương đương với việc cực đại hóa hàm log hợp lý.

18.11.7. Bài tập

1. Kiểm chứng rằng ví dụ lá bài ở phần đầu quả thực có entropy như đã nhận định.

2. Chứng minh rằng phân kỳ KL \(D(p\|q)\) là không âm với mọi phân phối \(p\) và \(q\). Gợi ý: sử dụng bất đẳng thức Jensen, tức là sử dụng thực tế là \(-\log x\) là một hàm lồi.

3. Hãy tính entropy từ một số nguồn dữ liệu sau:

   • Giả sử bạn đang theo dõi văn bản sinh ra khi một con khỉ dùng máy đánh chữ. Con khỉ nhấn ngẫu nhiên bất kì phím nào trong \(44\) phím của máy đánh chữ (bạn có thể giả sử nó chưa phát hiện ra phím shift hay bất kì phím đặc biệt nào). Mỗi kí tự ngẫu nhiên bạn quan sát được chứa bao nhiêu bit?

   • Giả sử thay vì con khỉ, ta có một người đang say rượu đánh chữ. Người đó có thể tạo ra các từ ngẫu nhiên trong bảng từ vựng gồm \(2,000\) từ, mặc dù câu văn không được mạch lạc. Giả sử độ dài trung bình của một từ là \(4.5\) chữ cái Tiếng Anh. Lúc này mỗi ký tự ngẫu nhiên bạn quan sát được chứa bao nhiêu bit?

   • Vẫn không hài lòng với kết quả, bạn dùng một mô hình ngôn ngữ chất lượng cao, có perplexity chỉ cỡ \(15\) điểm cho mỗi từ. Perplexity mức ký tự của một mô hình ngôn ngữ trên một từ được định nghĩa là tích của nghịch đảo xác suất của mỗi ký tự xuất hiện trong từ đó, rồi được chuẩn hóa bằng độ dài của từ như sau

     (18.11.33)\[ \begin{align}\begin{aligned}PPL(\text{từ}) = \left[\prod_i p(\text{ký tự}_i)\right]^{ -\frac{1}{\text{length(từ)}} }.\\Giả sử từ kiểm tra có :math:`4.5` chữ cái, lúc này mỗi ký tự ngẫu\end{aligned}\end{align} \]

     nhiên bạn quan sát được chứa bao nhiêu bit?

4. Giải thích một cách trực quan tại sao \(I(X, Y) = H(X) - H(X|Y)\). Sau đó, chứng minh biểu thức này đúng bằng cách biểu diễn hai vế theo kỳ vọng của phân phối kết hợp.

5. Phân kỳ KL giữa hai phân phối Gauss \(\mathcal{N}(\mu_1, \sigma_1^2)\) và \(\mathcal{N}(\mu_2, \sigma_2^2)\) là gì?

18.11.8. Thảo luận

• Tiếng Anh: MXNet
• Tiếng Việt: Diễn đàn Machine Learning Cơ Bản

18.11.9. Những người thực hiện

Bản dịch trong trang này được thực hiện bởi:

• Đoàn Võ Duy Thanh
• Trần Yến Thy
• Nguyễn Thanh Hòa
• Lê Khắc Hồng Phúc
• Nguyễn Lê Quang Nhật
• Phạm Hồng Vinh
• Phạm Minh Đức
• Nguyễn Mai Hoàng Long
• Đỗ Trường Giang
• Nguyễn Văn Cường