Entropy trong xử lý ảnh
Đóng góp: Ngô Hoàng Anh, École Polytechnique, Institut Polytechnique de Paris, Cộng hoà Pháp Show
Lý thuyết thông tin nghiên cứu về đo đạc lượng, lưu trữ và truyền dẫn thông tin. Khái niệm về lý thuyết thông tin cũng như nền móng của lĩnh vực này được xây dựng bởi công trình của Harry Nyquist và Ralph Hartley vào những năm 1920, và sau này là Claude Shannon vào những năm 1940. Lý thuyết này là “nút giao” của nhiều lĩnh vực khác nhau như xác suất thống kê, khoa học máy tính, cơ học thống kê, kĩ thuật thông tin và kĩ thuật điện, dùng để xác định giới hạn cơ bản trong các hoạt động xử lý dữ liệu. Ứng dụng của nó đã rất phong phú ngay từ những ngày đầu tiên, ví dụ như xử lý ngôn ngữ tự nhiên, mật mã học, mạng lưới thần kinh, sự tiến hoá và chức năng của các mã phân tử, sinh thái học, vật lý nhiệt, máy tính lượng tử và rất nhiều những hình thức phân tích dữ liệu khác. Những ứng dụng thực tiễn cơ bản của lý thuyết thông tin bao gồm: nén không mất dữ liệu (ZIP), nét mất dữ liệu (MP3, JPG), hay mã hoá kênh (DSL). Đầu tiên, chúng ta quy ước
1. Sơ lược về thông tin và lượng tin¶Đối tượng nghiên cứu chính của lý thuyết thông tin chính là “thông tin”. Thông tin này có thể được mã hoá bằng bất kì điều gì, với một hay nhiều định dạng khác nhau. Như vậy, làm cách nào để định lượng thông tin? Trong bài báo kinh điển của mình vào năm 1948, Claude Shannon đã lần đầu giới thiệu thuật ngữ “bit” để làm đơn vị đo lường thông tin, mà đơn vị này ban đầu cũng đã được đề xuất bởi John Tukey. Lý do “bit” được sử dụng đơn giản là vì các máy thu phát tín hiệu, hay kể cả các hệ thống máy tính hiện đại mà chúng ta làm việc ngày nay, bất kì thông tin nào đều được mã hoá bởi một chuỗi nhị phân các số \(0\) và \(1\). Như vậy, một chuỗi nhị phân độ dài \(n\) sẽ có \(n\) bit thông tin. Để “lượng hoá” lượng thông tin này thành số lượng bit, Shannon đề xuất một hàm “lượng tin”, hay sẽ chủ yếu đề cập đến với tên entropy, nhằm tính toán số “bit” thông tin nhận được ứng với một (nhóm) sự kiện \(X\) nào đó. \[ I(X) = -\log_2 p(X) \] Lấy ví dụ đơn giản, giả sử chúng ta có một mã là một chuỗi nhị phân độ dài 5, chẳng hạn như “10001”. Khi đó, lượng tin của mã này sẽ là \[ I("10001") = -\log_2 p("10001") = -\log_2 \frac{1}{2^5} = -(-5) = 5 (\text{bits}) \] 2. Entropy¶Như đã đề cập ở trên, lý thuyết thông tin được xây dựng dựa trên nền tảng xác suất thống kê. Thông số quan trọng nhất của thông tin là entropy (lượng thông tin chứa trong một biến ngẫu nhiên). Từ entropy, các khái niệm entropy hợp hay entropy có điều kiện cũng được hình thành để đo lường thông tin tương hỗ (lượng thông tin chung giữa hai biến ngẫu nhiên). Entropy của biến \(X\), \(H(X)\), được tính bằng \[ H(X) = \mathbf{E}[I(x)] = - \sum_{x \in \mathcal{X}} p(x) \log p(x) \] Một trong những trường hợp thường gặp nhất của entropy cho biến ngẫu nhiên là hàm entropy nhị phân .tức là entropy cho biến ngẫu nhiên \(X\) có phân phối xác suất \(p(x)\) với duy nhất hai khả năng \(\{0, 1\}\). \[ H_{\mathbb{b}} (X) = \sum_{x \in \mathcal{X}} - p(x) \log p(x) - (1-p(x)) \log (1-p(x)) \] Trong trường hợp \(X\) là một biến ngẫu nhiên liên tục, entropy của \(X\) sẽ được tính theo công thức tích phân: \[ H(X) = - \int_{x \in \mathcal{X}} p(x) \log p(x) dx \] Từ công thức biểu diễn, chúng ta có thể rút ra một số tính chất cơ bản của entropy như sau
3. Thông tin tương hỗ¶Entropy đã cung cấp cho chúng ta định lượng thông tin của một biễn ngẫu nhiên duy nhất; tuy nhiên, chuyện gì sẽ xảy ra nếu có hai biến ngẫu nhiên (rời rạc hoặc liên tục)? Những khái niệm được đề cập tới trong phần này sẽ giúp thể hiện những khía cạnh khác nhau của câu hỏi “Thông tin của cả hai biến \(X\) và \(Y\) sẽ như thế nào so với thông tin được chứa trong từng biến riêng lẻ? Có thông tin nào bị thừa, thiếu, hay đều phân biệt và độc nhất?” 3.1. Entropy hợp (Joint Entropy)¶Entropy hợp của hai biến ngẫu nhiên \((X, Y)\) là entropy dựa trên phân phối xác suất đồng thời (join distribution) của hai biến \((X, Y)\). Ví dụ, nếu cặp \((X,Y)\) biểu diễn vị trí của một quân cờ trên bàn cờ vua, với \(X\) là toạ độ hàng và \(Y\) là toạ độ cột, khi đó, entropy hợp của toạ độ hàng và toạ độ cột của con cờ sẽ là entropy của cặp toạ độ của quân cờ. Entropy hợp của cặp \((X,Y)\) được biểu diễn như sau \[ H(X,Y) = \mathbf{E}_{X,Y} [- \log p(x,y)] = - \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log p(x, y) \] Trong trường hợp \((X,Y)\) là một cặp biến ngẫu nhiên liên tục, entropy hợp của cặp này cũng sẽ được tính tương tự như sau \[ H(X, Y)= - \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x, y) \log p(x, y) dx dy \] 3.2. Entropy có điều kiện (Conditional entropy)¶Entropy có điều kiện, hay điều kiện không chắc chắn (conditional uncertainty), của \(X\) với một biến ngẫu nhiên cho trước \(Y\) (hay còn gọi là độ mờ của \(X\) đối với \(Y\)) là giá trị kì vọng của entropy của \(X\) theo phân bố của \(Y\) \[\begin{split} \begin{eqnarray}H(X|Y) & = & \mathbf{E}_{Y} [H(X|y)] \\ & = & - \sum_{y \in \mathcal{Y}} p(y) \sum_{x \in \mathcal{X}} p(x|y) \log p(x|y) \\ & = & - \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log p(x|y) \\ & = & - \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y)\log \frac{p(x,y)}{p(y)} \\ & = & - [\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y)\log p(x,y) - \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}}{p(x, y) \log p(y)}] \\ & = & - [\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y)\log p(x,y) - \sum_{y \in \mathcal{Y}}{p(y) \log p(y)}] \\ & = & H(X, Y) - H(Y) \end{eqnarray} \end{split}\] Nếu \(X, Y\) là các biến liên tục, entropy có điều kiện sẽ được tính tương tự như sau \[\begin{split} \begin{eqnarray} H(X|Y) & = & - \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x,y) \log p(x|y) dx dy \\ & = & - \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x,y) \log \frac{p(x,y)}{p(y)} dx dy \\ & = & - \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x,y) [\log p(x,y) - \log p(y)] dx dy \\ & = & - \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x,y) \log p(x,y) dx dy + \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x,y) \log p(y) dx dy \\ & = & - \int_{\mathcal{Y}} \int_{\mathcal{X}} p(x,y) \log p(x,y) dx dy + \int_{\mathcal{Y}} p(y) \log p(y) dy \\ & = & H(X, Y) - H(Y) \end{eqnarray} \end{split}\] Như vậy cả hai trường hợp biến liên tục và biến rời rạc đều dẫn tới một kết quả quan trọng đó là: \[ H(X|Y) = H(X,Y) - H(Y) \] 3.3. Thông tin tương hỗ (Mutual Information)¶Từ những định nghĩa trên, chúng ta thấy:
Chúng ta có thể trả lời câu hỏi sau đây: “Lượng thông tin giống nhau, tức là cùng được biết bởi cả hai biến \(X\) và \(Y\), là bao nhiêu?”. Một cách rất trực quan, chúng ta xây dựng khái niệm thông tin tương hỗ như sau \[ I(X,Y) = H(X,Y) - H(X|Y) - H(Y|X) \] Như vậy, thông tin tương hỗ là lượng thông tin thu được từ một biến ngẫu nhiên thông qua việc quan sát giá trị của một biến ngẫu nhiên khác. \[ I(X;Y) = \mathbf{E}_{X,Y} [I(x \in \mathcal{X},y \in \mathcal{Y})] = \sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}} p(x,y) \log \frac{p(x,y)}{p(x) p(y)} \] Hai công thức trên cho chúng ta một tính chất quan trọng của thông tin tương hỗ, tính đối xứng \[ I(X;Y) = I(Y;X). \] Ngoài ra, dựa vào mối quan hệ của entropy hợp và entropy có điều kiện, các biểu thức sau đây đều tương đương với thông tin tương hỗ \[\begin{split}\begin{eqnarray} I(X;Y) & = & I(Y;X) \\ & = & H(X,Y) - H(X|Y) - H(Y|X) \\ & = & H(X) - H(X|Y) \\ & = & H(Y) - H(Y|X) \\ & = & H(X) + H(Y) - H(X,Y) \end{eqnarray} \end{split}\] Từ đây, chúng ta thấy rằng thông tin tương hỗ luôn nhận giá trị không âm (tức là \(H(X,Y) \geq 0\)), và dấu \("="\) xảy ra khi và chỉ khi \(X\) và \(Y\) là hai biến ngẫu nhiên hoàn toàn độc lập. Khi đó, việc biết thông tin của một biến không cho chúng ta bất cứ thông tin gì về biến còn lại, và ngược lại. 4. Phân kì Kullback - Leibler (Kullback - Leibler divergence)¶Nếu như norm có thể được sử dụng để đo khoảng cách giữa hai điểm trong không gian với số chiều bất kì, chúng ta cũng có thể tìm cách thực hiện tương tự với các phân phối xác suất. Để xác định hai phân phối có gần nhau hay không, phân kì Kullback - Leibler là phương pháp đo tốt nhất, sử dụng lý thuyết thông tin, để thực hiện công việc này. Giả sử chúng ta có hai hàm mật độ/hàm khối xác suất khác nhau cho cùng một biến ngẫu nhiên \(X\): một hàm “thật” \(p(x)\) cho phân phối xác suất \(P\) và một hàm ước lượng bất kì \(q(x)\) cho phân phối xác suất \(Q\). Khi đó, phân kì Kullback - Leibler (hay entropy tương đối) được tính bằng \[ D_{KL} (p(X) || q(X)) = \mathbf{E}_{P} \left[ \log \frac{p(x)}{q(x)} \right] \] Khi sử dụng công thức thông tin tương hỗ cho phân phối rời rạc tại từng điểm, chúng ta có thể viết lại công thức trên như sau \[ D_{KL} (p(X) || q(X)) = \sum_{x \in \mathcal{X}} p(x) \log \frac{p(x)}{q(x)} = \sum_{x \in \mathcal{X}}[-p(x) \log q(x)] - \sum_{x \in \mathcal{X}} [-p(x) \log p(x))] \] Như vậy, nếu \(x\) xuất hiện thường xuyên hơn trong phân phối của \(P\) so với mức ta kì vọng ban đầu cho phân phối \(Q\), phân kì Kullback - Leibler sẽ lớn hơn và dương; ngược lại, nếu sự xuất hiện đó ít hơn nhiều so với kì vọng ban đầu, phân kì sẽ nhỏ hơn và âm. Như vậy, phân kì Kullback - Leibler là mức độ ngạc nhiên “tương đối” khi quan sát một phân phối mục tiêu, so với phân bố được chọn làm tham chiếu. Với định nghĩa của phân kì Kullback - Leibler, chúng ta có thể biểu diễn thông tin tương hỗ dưới dạng phân bố hậu nghiệm của \(X\) nếu biết giá trị của \(Y\) và phân bố tiền nghiệm của \(X\), hoặc ngược lại. \[ I(X;Y) =\mathbf{E}_{Y} [D_{KL} p(X|Y = y) || p(X)] = \mathbf{E}_{X} [D_{KL} p(Y|X = x) || p(Y)] \] Nói một cách khác, phân kì Kullback - Leibler xác định, về mặt trung bình, sự thay đổi của phân bố \(X\) nếu biết giá trị tiền nghiệm của \(Y\). Giá trị này là 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. \[ I(X;Y) = D_{KL} \left( p(X,Y) || p(X) p(Y) \right) \] Phân kì Kullback - Leibler còn có thể được diễn giải “đơn giản” như là một sự “bất ngờ không cần thiết” đến từ giá trị thật tiền nghiệm. Giả sử rằng chúng ta có một số \(X\) được chọn ngẫu nhiên từ một tập rời rạc với hàm phân bố xác suất \(p(x)\). Ví dụ, nếu An biết được phân phối thực sự là \(p(x)\), trong khi Bình tin rằng phân phối tiền nghiệm là \(q(x)\). Khi đó, nhìn chung, Bình sẽ “bất ngờ” hơn An rất nhiều khi biết được phân phối thật sự của \(X\). Phân kì Kullback - Leibler là giá trị kì vọng của sự chênh lệch về độ bất ngờ giữa An và Bình, đo bằng bits nếu logarithm ở cơ số 2. Bằng cách này, phân phối tiền nghiệm của Bình sẽ được định lượng là “lệch” đến mức độ nào bằng độ “bất ngờ không cần thiết” anh ta nhận được. Mặc dù được thường xuyên sử dụng như một “khoảng cách metric” với giá trị luôn không âm, phân kì Kullback - Leibler không thực sự là một metric do nó không có hai yếu tố cơ bản sau đây: không đối xứng, và không thoả mãn bất đẳng thức tam giác. Chứng minh tính không âm. Một bài toán thú vị liên quan đến phân kì Kullback - Leibler chính là chứng minh tính không âm của nó cho mọi phân phối \(p\), \(q\). Để chứng minh điều này, chúng ta áp dụng bất đẳng thức Jensen cho biểu thức của phân kì, dựa trên dữ kiện \(f(x) = - \log(x)\) là một hàm lồi. Chứng minh chi tiết được dành lại như một bài tập nhỏ cho bạn đọc. Chúng ta xét ví dụ sau đây để thấy rõ hơn các tính chất của phân kì Kullback - Leibler. Đầu tiên, chúng ta tạo 3 tensor có độ dài 10000
import random import numpy as np from scipy.stats import norm, logistic import matplotlib.pyplot as plt %matplotlib inline # định nghĩa hàm phân kì Kullback - Leibler def kl_divergence(p, q): return np.sum(np.where(p != 0, x * np.log2(p / q), 0)) # định nghĩa khoảng để viết các hàm mật độ xác suất (PDF) x_range = np.arange(-10, 10, 0.0001) # định nghĩa hàm mật độ xác suất (PDF) của các biến tương ứng x = norm.pdf(x_range, loc=0, scale=1) y1 = logistic.pdf(x_range, loc=0, scale=1) y2 = norm.pdf(x_range, loc=0.5, scale=1) y3 = norm.pdf(x_range, loc=-0.5, scale=1) # vẽ tất cả các hàm PDF trên cùng một plot plt.figure() plt.title('PDF of all random variables') plt.plot(x_range, x, label = "N(0,1)") plt.plot(x_range, y1, label = "Logistic(0,1)") plt.plot(x_range, y2, label = "N(0.5,1)") plt.plot(x_range, y3, label = "N(-0.5,1)") plt.legend(loc = "best") plt.show() # In các giá trị của phân kì Kullback - Leibler giữa biểu diễn thực và các biểu diễn dự đoán print("The Kullback - Leibler divergence between N(0,1) and Logistic(0,1) is %.3f"% kl_divergence(x, y1)) print("The Kullback - Leibler divergence between N(0,1) and N(-0.5,1) is %.3f"% kl_divergence(x, y2)) print("The Kullback - Leibler divergence between N(0,1) and N(0.5,1) is %.3f"% kl_divergence(x, y3)) The Kullback - Leibler divergence between N(0,1) and Logistic(0,1) is 2786.996 The Kullback - Leibler divergence between N(0,1) and N(-0.5,1) is 1803.369 The Kullback - Leibler divergence between N(0,1) and N(0.5,1) is 1803.369 assert kl_divergence(x, y1) != kl_divergence(y1, x) assert kl_divergence(x, y2) != kl_divergence(y2, x) assert kl_divergence(x, y3) != kl_divergence(y3, x) Qua ví dụ trên, chúng ta thấy hai tính chất cơ bản như sau:
5. Entropy chéo (Cross entropy)¶5.1. Giới thiệu vấn đề¶Đầu tiên, chúng ta xét bài toán đơn giản như sau. Giả sử chúng ta có \(n\) điểm dữ liệu cho trước \(\{ x_1, x_2, ..., x_n\}\) và một yêu cầu phân loại nhị phân sử dụng mạng neuron với tham số \(\theta\). Khi đó, chúng ta tìm \(\theta\) tốt nhất để sinh ra các kết quả \(\hat{y_i} = p_{\theta} (y_i | x_i)\) tốt nhất. Với \(\pi_i = p_{\theta} (y_i = 1 | x_i)\) và \(1 - p_i = p_{\theta} (y_i = 0 | x_i)\), chúng ta viết được hàm log hợp lý như sau \[\begin{align*} 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{align*}\] Như vậy, cực đại hoá hàm log hợp lý \(l(\theta)\) chính là cực tiểu hoá hàm \(-l(\theta)\). Để tăng tính khái quát cho tất cả mọi bài toán nhị phân hay đa nhãn, chúng ta gọi \(-l(\theta)\) là hàm mất mát entropy chéo (Cross entropy loss), được kí hiệu là \(CE(\mathbf{y}, \hat{\mathbf{y}})\), với \(\mathbf{y}\) tuân theo phân phối “thật” \(P\) và \(\hat{\mathbf{y}}\) tuân theo phân phối dự đoán \(Q\). 5.2. Định nghĩa Entropy chéo¶Một lần nữa, chúng ta giả sử rằng tồn tại hai hàm mật độ/khối xác suất cho cùng một biến ngẫu nhiên \(X\): \(p(x)\) là hàm “thật” ứng với phân phối xác suất \(P\) và \(q(x)\) là hàm dự đoán với phân phối xác suất \(Q\) bất kì. Hàm entropy chéo của phân phối \(Q\) tương ứng với phân phối \(P\) được tính như sau \[ CE(p,q) = - \mathbf{E}_{p} [\log q], \] với \(\mathbf{E}_p\) là hàm kì vọng trên phân phối \(p\). Sử dụng các công thức tính entropy và phân kì Kullback - Leibler \(D_{KL} (p||q)\), chúng ta có thể viết lại công thức tính entropy chéo như sau \[ CE(p,q) = H(p) + D_{KL} (p || q) \] Với \(p, q\) là các hàm phân phối xác suất rời rạc trên cùng một không gian mẫu \(X\), công thức này đồng nghĩa với \[ CE(p,q) = - \sum_{x \in \mathcal{X}} p(x) \log q(x) \] Trường hợp \(p\) và \(q\) là các phân phối xác suất liên tục, công thức trên được định nghĩa tương tự. Đầu tiên, chúng ta phải giả sử rằng \(p\) và \(q\) đều liên tục tuyệt đối với một độ đo tham chiếu \(r(x)\) (thông thường, \(r(x)\) sẽ là một độ đo Lebesgue hoặc một Borel \(\sigma\)-algebra). Khi đó, nếu gọi \(P(x)\) và \(Q(x)\) lần lượt là hàm mật độ xác suất của \(p\) với \(q\) tương ứng với \(r\), chúng ta sẽ có \[ CE(p,q) = - E_{p} [\log Q] = E_{p} [- \log Q] = - \int_{\mathcal{X}} P(x) \log Q(x) d r(x). \] Với định nghĩa của entropy chéo, chúng ta có thể nói rằng việc thực hiện những mục tiêu sau là tương đương với nhau:
5.3. Hàm mất mát Entropy chéo (Cross entropy loss) trong bài toán Phân loại Đa lớp¶Trong phần này, chúng ta sẽ chứng minh được tại sao cực tiểu hoá hàm mất mát entropy chéo lại hương đương với việc cực đại hoá hàm log hợp lý \(l\). Chúng ta xét bài toán như sau. Giả sử chúng ta có tập dữ liệu \(\mathbf{x}_i, i = 1, 2, ..., n\) với \(n\) mẫu khác nhau được phân vào \(k\) tập hợp. Với mỗi phần tử \(\mathbf{x}_i\) của dữ liệu, chúng ta lại biểu diễn nhãn của nó dưới dạng \(\mathbf{y}_i = (y_{i1}, y_{i2}, ..., y_{in})\) bằng mã hoá one-hot. Giả sử chúng ta tham số hoá bài toán được giải bằng mạng neuron với tham số \(\theta\). Khi đó, dự đoán \(\hat{\mathbf{y}_i}\) sẽ bầng \[ \hat{\mathbf{y}_i} = p_{\theta} (\mathbf{y}_i | \mathbf{x}_i) = \sum_{j=1}^k y_{ij} p_{\theta} (y_{ij} | \mathbf{x}_i) \] Như vậy, khi đó, hàm entropy chéo giữa giá trị thực và giá trị dự đoán là \[ 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} | \mathbf{x}_i) \] Tương tự với phần giới thiệu vấn đề, giá trị của hàm entropy chéo này chính là nghịch đảo của hàm ước lượng hợp lý cực đại \(l(\theta)\) khi giả sử \(\mathbf{y}_i\) tuân theo phân phối đa thức \(k\) lớp. Như vậy, việc cực đại hoá hàm log hợp lý \(l(\theta)\) chính là cực tiểu hoá hàm entropy chéo nêu trên. Hàm mất mát entropy chéo cho bài toán phân loại đa nhãn có thể được tính trực tiếp, sử dụng hàm from sklearn.metrics import log_loss true_labels = ["cat", "dog", "dog", "cat"] pred_proba = [[0.2, 0.8], [0.6, 0.4], [0.75, 0.25], [0.45, 0.55]] log_loss(true_labels, pred_proba, eps=1e-15) 6. Ứng dụng của lý thuyết thông tin trong các chỉ số đánh giá (metric) cho mô hình phân nhóm (clustering)¶Như đã nói, lý thuyết thông tin có rất nhiều ứng dụng trong các lĩnh vực khác nhau, một trong số đó là trong việc xây dựng các chỉ số đánh giá cho các mô hình phân nhóm (clustering) hay đa nhãn (classification). Trong các mô hình học không giám sát (unsupervised learning), có hai loại chỉ số đánh giá được sử dụng, bao gồm
Như vậy, để giải quyết vấn đề của các chỉ số đánh giá thuộc nhóm external, một lớp các chỉ số dựa vào ý tưởng của entropy, hay lý thuyết thông tin nói chung, đã được đề xuất. Những chỉ số thuộc lớp này bao gồm:
Trước tiên, trước khi bắt đầu đi vào tính toán các chỉ số đánh giá, chúng ta quy ước như sau:
Khi đó, entropy và entropy có điều kiện của các phân phối sẽ được tính như sau
\[ H(C) = - \sum_{c = 1}^{|C|} \frac{\sum_{k=1}^{|K|} a_{ck}}{n} \log \frac{\sum_{k=1}^{|K|} a_{ck}}{n} \]
\[ H(K) = - \sum_{k = 1}^{|K|} \frac{\sum_{c=1}^{|C|} a_{ck}}{n} \log \frac{\sum_{c=1}^{|C|} a_{ck}}{n} \]
\[ H(C|K) = - \sum_{k=1}^{|K|} \sum_{c=1}^{|C|} \frac{a_{ck}}{N} \log \frac{a_{ck}}{\sum_{c=1}^{|C|} a_{ck}} \]
\[ H(K|C) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{a_{ck}}{N} \log \frac{a_{ck}}{\sum_{k=1}^{|K|} a_{ck}} \] 6.1. Độ hoàn chỉnh, Độ thống nhất và VBeta¶Như đã đề cập ở trên, việc định lượng độ không chính xác của kết quả phân nhóm là một bài toán khó. Chính vì vậy, VBeta, được đề xuất bởi Andrew Rosenberg và Julia Hirschberg (2007), là một giải pháp tinh tế cho những vấn đề như sau
Hai khái niệm mới, bao gồm độ đồng nhất và độ hoàn chỉnh, đã được đề xuất để đi đến việc tính toán V-Measure. Độ đồng nhất (Homogeneity)¶Để thoả mãn tiêu chí về độ đồng nhất, một phân nhóm dự đoán chỉ được nhóm các điểm trong cùng một nhóm ở phân loại “thật”. Tức là, sự phân bố của các nhóm “thật” trong một nhóm được dự đoán phải nghiêng hẳn về một nhóm “thật” nào đó, hay nói cách khác, entropy tiến đến 0. Chúng ta định nghĩa một phân nhóm dự đoán gần với điều kiện lý tưởng nêu trên như thế nào bằng cách tính entropy có điều kiện của phân nhóm “thật”, giả sử phân nhóm dự đoán được biết trước \(H(C|K)\). Tuy nhiên, do giá trị này phụ thuộc vào độ lớn của dữ liệu ban đầu và phân phối của phân loại “thật”, chúng ta sẽ chuẩn hoá giá trị này bằng lượng giảm tối đa thông tin về phân nhóm có thể sản sinh ra, hay \(H(C)\). \[\begin{align*} h = \begin{cases} 1 & \text{ if } H(C,K) = 0 \\ 1 - \frac{H(C|K)}{H(C)} & \text{ else} \end{cases} \end{align*}\] Độ hoàn chỉnh (Completeness)¶Độ hoàn chỉnh là một chỉ số đối xứng với độ đồng nhất. Để thoả mãn tiêu chí về độ hoàn chỉnh, một phân nhóm dự đoán phải cố gắng nhóm tất cả các điểm thuộc cùng một nhóm “thật”. Tương tự như trên, để tính độ hoàn chỉnh, chúng ta xem xét sự phân bố của các phân nhóm dự đoán trong một phân nhóm thật. Tuy nhiên, trong trường hợp xấu nhất, mỗi nhóm thật sẽ được biểu diễn bằng một phân nhóm dự đoán với phân bố giống với phân bố về kích thước của các nhóm, tức là \(H(K)\), và chúng ta phải chuẩn hoá độ hoàn chỉnh bằng giá trị này. \[\begin{align*} c = \begin{cases} 1 & \text{ if } H(K,C) = 0 \\ 1 - \frac{H(K|C)}{H(K)} & \text{ else} \end{cases} \end{align*}\] VBeta¶V, viết tắt của “validity” (hợp lệ) trong tiếng Anh, là một thuật ngữ thường được dùng để miêu tả độ chính xác của một kết quả cho bài toán phân nhóm. Như vậy, dựa trên việc tính toán độ đồng nhất và độ hoàn chỉnh ở phía trên, chúng ta tính toán được phép đo độ hợp lý VBeta bằng một hàm trung bình điều hoà (harmonic mean) của hai chỉ số trên như sau \[ V_{\beta} = \frac{(1 + \beta) \times h \times c}{\beta \times h + c} \] Như vậy, tương tự như một chỉ số khác là phép đo F (F-Measure), nếu \(\beta > 1\), độ hoàn chỉnh sẽ góp phần quan trọng hơn trong phép tính; và ngược lại, nếu \(\beta < 1\), độ đồng nhất sẽ đóng vai trò lớn hơn. Để tính toán độ hoàn chỉnh, độ đồng nhất hay VBeta giữa hai kết quả phân nhóm, chúng ta có thể sử dụng hàm from sklearn.metrics import homogeneity_completeness_v_measure, \ homogeneity_score, \ completeness_score, \ v_measure_score \ # tạo các nhãn dãn giả thuyết (nhãn dán "thật" và nhãn dán dự đoán) y_true = [0,0,1,1,2,2] y_pred = [0,0,0,1,1,2] # tính toán các chỉ số đánh giá homogeneity_completeness_v_measure(y_true, y_pred) # kiểm tra chéo kết quả của các hàm khác nhau assert homogeneity_completeness_v_measure(y_true, y_pred)[0] == homogeneity_score(y_true, y_pred) assert homogeneity_completeness_v_measure(y_true, y_pred)[1] == completeness_score(y_true, y_pred) assert homogeneity_completeness_v_measure(y_true, y_pred)[2] == v_measure_score(y_true, y_pred) print('Homogeneity score of y_true and y_pred is %.5f' % homogeneity_score(y_true, y_pred)) print('Completeness score of y_true and y_pred is %.5f' % completeness_score(y_true, y_pred)) print('The VBeta score of y_true and y_pred with weight 1.0 is %.5f' % v_measure_score(y_true, y_pred)) Homogeneity score of y_true and y_pred is 0.50000 Completeness score of y_true and y_pred is 0.54311 The VBeta score of y_true and y_pred with weight 1.0 is 0.52067 6.2. Thông tin tương hỗ và các biến thể¶Thông tin tương hỗ được chuẩn hoá (Normalized Mutual Information Score)¶Thông tin tương hỗ được chuẩn hoá, nói đơn giản, là lượng thông tin tương hỗ được chuẩn hoá để kết quả nhận được nằm trong khoảng 0 (không có thông tin tương hỗ) và 1 (thông tin hoàn toàn trùng khớp). Trong
cách tính của chỉ số này, thông tin tương hỗ sẽ được chuẩn hoá bằng một hàm trung bình tổng quát giữa \(H(C)\) và \(H(K)\), được định nghĩa bởi tham số \[ NMI = \frac{MI}{\text{generalized_average}(H(C), H(K))} \] Tuy nhiên, một trong những nhược điểm của chỉ số này là không được hiệu chỉnh với các giá trị ngẫu nhiên (adjusted for chance). Khi đó, hàm thông tin tương hỗ được hiệu chỉnh sẽ được sử dụng thường xuyên hơn. Ngoài ra, chỉ số này còn có tính đối xứng, tức là thay đổi vị trí của Thông tin tương hỗ được hiệu chỉnh (Adjusted Mutual Information Score)¶Thông tin tương hỗ được hiểu chỉnh là một phiên bản khác của thông tin tương hỗ, nhằm để hiệu chỉnh với những giá trị ngẫu nhiên. Chúng ta dễ dàng nhận thấy rằng giá trị của Thông tin tương hỗ với hai kết quả phân nhóm khác nhau có số lượng các phân nhóm cao hơn, không quan trọng việc chúng có chia sẻ nhiều thông tin với nhau hay không. Như vậy, chỉ số đánh giá này sẽ được tính như sau \[ AMI = \frac{MI - \textbf{E}[MI]}{\text{generalized_average}(H(C), H(K)) - \textbf{E}[MI]} \] Với \(\textbf{E}(MI)\), hay giá trị kì vọng của Thông tin tương hỗ, là giá trị cơ sở của lượng thông tin tương hỗ giữa hai kết quả phân nhóm bất kì. Giá trị cơ sở này không nhất thiết phải là một hằng số, và như đã đề cập, sẽ càng cao hơn khi kết quả có càng nhiều phân nhóm. Như vậy, sử dụng một mô hình ngẫu nhiên hyper-geometric, giá trị kì vọng này được tính bằng cách \[\begin{align*} \mathbf{E}(MI) & = \sum_{i=1}^{|K|} \sum_{i=1}^{|C|} \sum_{n_{ij}=(a_i+b_j-N)^+}^{\min(a_i,b_j)} \frac{n_{ij}}{N} \log \left(\frac{N n_{ij}}{a_i b_j} \right) \\ & \times \frac{a_i! b_j! (N-a_i)! (N-b_j)!}{N! n_{ij}! (a_i - n_{ij})! (b_j - n_{ij})! (N - a_i - b_j + n_{ij})!} \end{align*}\] với
6.3. Q0 và Q0 được chuẩn hoá (Q2)¶Q0¶\(Q_0\), tương tự như các chỉ số đánh giá khác, cũng sử dụng đại lượng entropy có điều kiện \(H(C|K)\) để đo độ tốt của kết quả. Tuy nhiên, như đã được đề cập, đại lượng này chỉ biểu diễn độ đồng nhất của kết quả. Để đánh giá thêm độ hoàn thiện, Dom thêm vào một mô hình hàm giá (model cost term), được tính bằng lập luận của lý thuyết mã hoá. Biểu thức hoàn chỉnh của đại lượng này chính là tổng của hàm entropy có điều kiện và hàm biểu diễn mô hình. Ý tưởng đằng sau của đánh giá này khá cẩn thận và chi tiết: Với cùng một đại lượng cho enotrpy có điều kiện, kết quả phân nhóm nào sinh ra ít nhóm nhất sẽ được ưu tiên. $\( Q_0(C,K) = H(C|K) + \frac{1}{n} \sum_{k=1}^{|K|} \log \binom{h(K) + |C| - 1}{|C| - 1} \)$ Q2¶\(Q_2\) là phiên bản được chuẩn hoá của \(Q_0\) nhằm mục đích đưa giá trị của chỉ số đánh giá này về nằm trong khoảng \((0,1]\). Chỉ số đánh giá này càng lớn, kết quả của bài toán phân nhóm càng chính xác và ngược lại. \[ Q_2(C,K) = \frac{\frac{1}{n} \sum_{c=1}^{|C|} \log \binom{h(C) + |C| - 1}{|C| - 1} }{Q_0(C,K)} \] 7. Bài tập¶
8. Tài liệu tham khảo¶[1] C. E., Shannon. A Mathematical Theory of Communication, Bell System Technical Journal, 27, pp. 379-423 & 623-656, July & October, 1948. [2] R. V. L., Hartley, Transmission of Information, Bell System Technical Journal, July 1928. [3] K. P., Burnham, D. R., Anderson. Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York). ISBN: 978-0-387-95364-9. [4] H.-A., NGO. Investigation and Implementation of Incremental Clustering Algorithms and Metrics in River, BSc. Thesis at École Polytechnique, IP Paris, France, 2021. [5] A., Rosenberg, J., Hirschberg. V-Measure: A conditional entropy-based external cluster evaluation measure, Processdings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 410-420, Prague, June 2007. URL: https://www.aclweb.org/anthology/D07-1043.pdf [6] F., Pedregosa et al. Scikit-learn: Machine Learning in Python, JMLR 12, pp. 2825-2830, 2011. [7] University of Cincinnati Business Analytics. K-Means Cluster Analysis. In: UC Business Analytics R Programming Guide. URL: https://uc-r.github.io/kmeans_clustering |