18.9. Bộ phân loại Naive Bayes

Trong các phần trước, ta đã học lý thuyết về xác suất và biến ngẫu nhiên. Để áp dụng lý thuyết này, ta sẽ lấy một ví dụ sử dụng bộ phân loại naive Bayes cho bài toán phân loại chữ số. Phương pháp này không sử dụng bất kỳ điều gì khác ngoài các lý thuyết căn bản về xác suất.

Quá trình học hoàn toàn xoay quanh việc đưa ra các giả định. Nếu muốn phân loại một mẫu dữ liệu mới chưa thấy bao giờ, ta cần phải đưa ra một giả định nào đó về sự tương đồng giữa các mẫu dữ liệu. Bộ phân loại Naive Bayes, một thuật toán thông dụng và dễ hiểu, giả định rằng tất cả các đặc trưng đều độc lập với nhau nhằm đơn giản hóa việc tính toán. Trong phần này, chúng tôi sẽ sử dụng mô hình này để nhận dạng ký tự trong ảnh.

%matplotlib inline
from d2l import mxnet as d2l
import math
from mxnet import gluon, np, npx
npx.set_np()
d2l.use_svg_display()

18.9.1. Nhận diện Ký tự Quang học

MNIST [LeCun et al., 1998] là một trong những tập dữ liệu được sử dụng rộng rãi. Nó chứa 60.000 ảnh để huấn luyện và 10.000 ảnh để kiểm định. Mỗi ảnh chứa một chữ số viết tay từ 0 đến 9. Nhiệm vụ là phân loại từng ảnh theo chữ số tương ứng.

Gluon cung cấp lớp MNIST trong mô-đun data.vision để tự động lấy dữ liệu từ Internet. Sau đó, Gluon sẽ sử dụng dữ liệu đã được tải xuống. Chúng ta xác định rằng ta đang yêu cầu tập huấn luyện hay tập kiểm tra bằng cách đặt giá trị tham số train thànhTrue hoặc False tương ứng. Mỗi hình ảnh là một ảnh xám có cả chiều rộng và chiều cao là \(28\), kích thước (\(28\),\(28\),\(1\)). Ta sẽ sử dụng một phép biến đổi được tùy chỉnh để loại bỏ chiều của kênh cuối cùng. Ngoài ra, tập dữ liệu biểu diễn mỗi điểm ảnh bằng một số nguyên \(8\)-bit không âm. Ta lượng tử hóa (quantize) chúng thành các đặc trưng nhị phân để đơn giản hóa bài toán.

def transform(data, label):
    return np.floor(data.astype('float32') / 128).squeeze(axis=-1), label

mnist_train = gluon.data.vision.MNIST(train=True, transform=transform)
mnist_test = gluon.data.vision.MNIST(train=False, transform=transform)
Downloading /home/tiepvu/.mxnet/datasets/mnist/train-images-idx3-ubyte.gz from https://apache-mxnet.s3-accelerate.dualstack.amazonaws.com/gluon/dataset/mnist/train-images-idx3-ubyte.gz...
Downloading /home/tiepvu/.mxnet/datasets/mnist/train-labels-idx1-ubyte.gz from https://apache-mxnet.s3-accelerate.dualstack.amazonaws.com/gluon/dataset/mnist/train-labels-idx1-ubyte.gz...
Downloading /home/tiepvu/.mxnet/datasets/mnist/t10k-images-idx3-ubyte.gz from https://apache-mxnet.s3-accelerate.dualstack.amazonaws.com/gluon/dataset/mnist/t10k-images-idx3-ubyte.gz...
Downloading /home/tiepvu/.mxnet/datasets/mnist/t10k-labels-idx1-ubyte.gz from https://apache-mxnet.s3-accelerate.dualstack.amazonaws.com/gluon/dataset/mnist/t10k-labels-idx1-ubyte.gz...

Ta có thể truy cập vào từng mẫu cụ thể có chứa ảnh và nhãn tương ứng.

image, label = mnist_train[2]
image.shape, label
((28, 28), array(4, dtype=int32))

Mẫu được lưu trữ trong biến image trên tương ứng với một ảnh có chiều cao và chiều rộng là \(28\) pixel.

image.shape, image.dtype
((28, 28), dtype('float32'))

Đoạn mã lưu nhãn của từng ảnh dưới dạng số nguyên \(32\)-bit.

label, type(label), label.dtype
(array(4, dtype=int32), mxnet.numpy.ndarray, dtype('int32'))

Ta cũng có thể truy cập vào nhiều mẫu cùng một lúc.

images, labels = mnist_train[10:38]
images.shape, labels.shape
((28, 28, 28), (28,))

Hãy cùng minh họa các mẫu trên.

d2l.show_images(images, 2, 9);
../_images/output_naive-bayes_vn_f35993_13_0.svg

18.9.2. Mô hình xác suất để Phân loại

Trong tác vụ phân loại, ta ánh xạ một mẫu tới một hạng mục. Ví dụ, ở đây ta ánh xạ một ảnh xám kích thước \(28\times 28\) tới hạng mục là một chữ số. (Tham khảo Section 3.4 để xem giải thích chi tiết hơn.) Một cách diễn đạt tự nhiên về tác vụ phân loại là câu hỏi xác suất: nhãn nào là hợp lý nhất với các đặc trưng cho trước (tức là các pixel trong ảnh)? Ký hiệu \(\mathbf x\in\mathbb R^d\) là các đặc trưng và \(y\in\mathbb R\) là nhãn của một mẫu. Đặc trưng ở đây là các pixel trong ảnh \(2\) chiều mà ta có thể biến đổi thành vector kích thước \(d=28^2=784\), và nhãn là các chữ số. Xác suất của nhãn khi biết trước đặc trưng là \(p(y \mid \mathbf{x})\). Trong ví dụ của ta, nếu có thể tính toán các xác suất \(p(y \mid \mathbf{x})\) với \(y=0, \ldots,9\), bộ phân loại sẽ đưa ra dự đoán \(\hat{y}\) theo công thức:

(18.9.1)\[\hat{y} = \mathrm{argmax} \> p(y \mid \mathbf{x}).\]

Không may là việc này yêu cầu ước lượng \(p(y \mid \mathbf{x})\) cho mọi giá trị \(\mathbf{x} = x_1, ..., x_d\). Hãy tưởng tượng mỗi đặc trưng nhận một giá trị nhị phân, ví dụ, đặc trưng \(x_1 = 1\) cho biết từ “quả táo” xuất hiện trong văn bản cho trước và \(x_1 = 0\) biểu thị ngược lại. Nếu có \(30\) đặc trưng nhị phân như vậy, ta cần phân loại \(2^{30}\) (hơn 1 tỷ!) vector đầu vào khả dĩ của \(\mathbf{x}\).

Hơn nữa, như vậy không phải là học. Nếu cần xem qua toàn bộ các ví dụ khả dĩ để dự đoán nhãn tương ứng thì chúng ta không thực sự đang học một khuôn mẫu nào mà chỉ là đang ghi nhớ tập dữ liệu.

18.9.3. Bộ phân loại Naive Bayes

May mắn thay, bằng cách đưa ra một số giả định về tính độc lập có điều kiện, ta có thể đưa vào một số thiên kiến quy nạp và xây dựng một mô hình có khả năng tổng quát hóa từ một nhóm các mẫu huấn luyện với kích thước tương đối khiêm tốn. Để bắt đầu, hãy sử dụng định lý Bayes để biểu diễn bộ phân loại bằng biểu thức sau

(18.9.2)\[\hat{y} = \mathrm{argmax}_y \> p(y \mid \mathbf{x}) = \mathrm{argmax}_y \> \frac{p( \mathbf{x} \mid y) p(y)}{p(\mathbf{x})}.\]

Lưu ý rằng mẫu số là số hạng chuẩn hóa \(p(\mathbf{x})\) không phụ thuộc vào giá trị của nhãn \(y\). Do đó, chúng ta chỉ cần quan tâm tới việc so sánh tử số giữa các giá trị \(y\) khác nhau. Ngay cả khi việc tính toán mẫu số hóa ra là không thể, ta cũng có thể bỏ qua nó, miễn là ta có thể tính được tử số. May mắn thay, ta vẫn có thể khôi phục lại hằng số chuẩn hóa nếu muốn. Ta luôn có thể khôi phục số hạng chuẩn hóa vì \(\sum_y p(y \mid \mathbf{x}) = 1\).

Bây giờ, hãy tập trung vào biểu thức \(p( \mathbf{x} \mid y)\). Sử dụng quy tắc dây chuyền cho xác suất, chúng ta có thể biểu diễn số hạng \(p( \mathbf{x} \mid y)\) dưới dạng

(18.9.3)\[p(x_1 \mid y) \cdot p(x_2 \mid x_1, y) \cdot ... \cdot p( x_d \mid x_1, ..., x_{d-1}, y).\]

Biểu thức này tự nó không giúp ta được thêm điều gì. Ta vẫn phải ước lượng khoảng \(2^d\) các tham số. Tuy nhiên, nếu chúng ta giả định rằng các đặc trưng khi biết nhãn cho trước là độc lập với nhau, thì số hạng này đơn giản hóa thành \(\prod_i p(x_i \mid y)\), và ta có hàm dự đoán:

(18.9.4)\[\hat{y} = \mathrm{argmax}_y \> \prod_{i=1}^d p(x_i \mid y) p(y).\]

Ta có thể ước lượng \(\prod_i p(x_i=1 \mid y)\) với mỗi \(i\)\(y\), và lưu giá trị của nó trong \(P_{xy}[i, y]\), ở đây \(P_{xy}\) là một ma trận có kích thước \(d\times n\) với \(n\) là số lượng các lớp và \(y\in\{1, \ldots, n\}\). Cùng với đó, ta ước lượng \(p(y)\) cho mỗi \(y\) và lưu trong \(P_y[y]\), với \(P_y\) là một vector có độ dài \(n\). Sau đó, đối với bất kỳ mẫu mới \(\mathbf x\) nào, ta có thể tính:

(18.9.5)\[\hat{y} = \mathrm{argmax}_y \> \prod_{i=1}^d P_{xy}[x_i, y]P_y[y],\]

cho \(y\) bất kỳ. Vì vậy, giả định của chúng ta về sự độc lập có điều kiện đã làm giảm độ phức tạp của mô hình từ phụ thuộc theo cấp số nhân vào số lượng các đặc trưng \(\mathcal{O}(2^dn)\) thành phụ thuộc tuyến tính, tức là \(\mathcal{O}(dn)\).

18.9.4. Huấn luyện

Vấn đề bây giờ là ta không biết \(P_{xy}\)\(P_y\). Vì vậy, ta trước tiên cần ước lượng giá trị của chúng với dữ liệu huấn luyện. Đây là việc huấn luyện mô hình. Ước lượng \(P_y\) không quá khó. Do chỉ đang làm việc với \(10\) lớp, ta có thể đếm số lần xuất hiện \(n_y\) của mỗi chữ số và chia nó cho tổng số dữ liệu \(n\). Chẳng hạn, nếu chữ số 8 xuất hiện \(n_8 = 5,800\) lần và ta có tổng số hình ảnh là \(n = 60.000\), xác suất ước lượng sẽ là \(p(y=8) = 0.0967\).

X, Y = mnist_train[:]  # All training examples

n_y = np.zeros((10))
for y in range(10):
    n_y[y] = (Y == y).sum()
P_y = n_y / n_y.sum()
P_y
array([0.09871667, 0.11236667, 0.0993    , 0.10218333, 0.09736667,
       0.09035   , 0.09863333, 0.10441667, 0.09751666, 0.09915   ])

Giờ hãy chuyển sang vấn đề khó hơn một chút là tính \(P_{xy}\). Vì ta lấy các ảnh đen trắng, \(p(x_i \mid y)\) biểu thị xác suất điểm ảnh \(i\) mang nhãn \(y\). Đơn giản giống như trên, ta có thể duyệt và đếm số lần \(n_{iy}\) mà điểm ảnh \(i\) mang nhãn \(y\) và chia nó cho tổng số lần xuất hiện \(n_y\) của \(y\). Nhưng có một điểm hơi rắc rối: một số điểm ảnh nhất định có thể không bao giờ có màu đen (ví dụ, đối với các ảnh được cắt xén tốt, các điểm ảnh ở góc có thể luôn là màu trắng). Một cách thuận tiện cho các nhà thống kê học để giải quyết vấn đề này là cộng thêm một số đếm giả vào tất cả các lần xuất hiện. Do đó, thay vì $n_{iy} $, ta dùng \(n_{iy} + 1\) và thay vì \(n_y\), ta dùng $n_{y} + 1 $. Phương pháp này còn được gọi là Làm mượt Laplace (Laplace Smoothing), có vẻ không chính thống nhưng hợp với quan điểm Bayes.

n_x = np.zeros((10, 28, 28))
for y in range(10):
    n_x[y] = np.array(X.asnumpy()[Y.asnumpy() == y].sum(axis=0))
P_xy = (n_x + 1) / (n_y + 1).reshape(10, 1, 1)

d2l.show_images(P_xy, 2, 5);
../_images/output_naive-bayes_vn_f35993_17_0.svg

Bằng cách trực quan hóa các xác suất \(10\times 28\times 28\) này (cho mỗi điểm ảnh đối với mỗi lớp), ta có thể lấy được hình ảnh trung bình của các chữ số.

Giờ ta có thể sử dụng (18.9.5) để dự đoán một hình ảnh mới. Cho \(\mathbf x\), hàm sau sẽ tính \(p(\mathbf x \mid y)p(y)\) với mỗi \(y\).

def bayes_pred(x):
    x = np.expand_dims(x, axis=0)  # (28, 28) -> (1, 28, 28)
    p_xy = P_xy * x + (1 - P_xy)*(1 - x)
    p_xy = p_xy.reshape(10, -1).prod(axis=1)  # p(x|y)
    return np.array(p_xy) * P_y

image, label = mnist_test[0]
bayes_pred(image)
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])

Điều này đã dẫn tới sai lầm khủng khiếp! Để tìm hiểu lý do tại sao, ta hãy xem xét xác suất trên mỗi điểm ảnh. Chúng thường mang giá trị từ \(0.001\) đến \(1\) và ta đang nhân \(784\) con số như vậy. Ta đang tính những con số này trên máy tính, do đó sẽ có một phạm vi cố định cho số mũ. Ta đã gặp vấn đề tràn số dưới (underflow), tức là tích tất cả các số nhỏ hơn một sẽ dẫn đến một số nhỏ dần cho đến khi kết quả được làm tròn thành 0. Ta đã thảo luận lý thuyết về vấn đề này trong Section 18.7, và ở đây ta thấy hiện tượng này trong thực tế một cách rõ ràng.

Như đã thảo luận trong phần đó, ta khắc phục điều này bằng cách sử dụng tính chất \(\log a b = \log a + \log b\), cụ thể là ta chuyển sang tính tổng các logarit. Nhờ vậy ngay cả khi cả \(a\)\(b\) đều là các số nhỏ, giá trị các logarit vẫn sẽ nằm trong miền thích hợp.

a = 0.1
print('underflow:', a**784)
print('logarithm is normal:', 784*math.log(a))
underflow: 0.0
logarithm is normal: -1805.2267129073316

Vì logarit là một hàm tăng dần, ta có thể viết lại (18.9.5) thành

(18.9.6)\[\hat{y} = \mathrm{argmax}_y \> \sum_{i=1}^d \log P_{xy}[x_i, y] + \log P_y[y].\]

Ta có thể lập trình phiên bản ổn định sau:

log_P_xy = np.log(P_xy)
log_P_xy_neg = np.log(1 - P_xy)
log_P_y = np.log(P_y)

def bayes_pred_stable(x):
    x = np.expand_dims(x, axis=0)  # (28, 28) -> (1, 28, 28)
    p_xy = log_P_xy * x + log_P_xy_neg * (1 - x)
    p_xy = p_xy.reshape(10, -1).sum(axis=1)  # p(x|y)
    return p_xy + log_P_y

py = bayes_pred_stable(image)
py
array([-269.0042 , -301.73447, -245.21458, -218.8941 , -193.46907,
       -206.10315, -292.54315, -114.62834, -220.35619, -163.18881])

Bây giờ ta có thể kiểm tra liệu dự đoán này có đúng hay không.

# Convert label which is a scalar tensor of int32 dtype
# to a Python scalar integer for comparison
py.argmax(axis=0) == int(label)
array(True)

Nếu dự đoán một vài mẫu kiểm định, ta có thể thấy bộ phân loại Bayes hoạt động khá tốt.

def predict(X):
    return [bayes_pred_stable(x).argmax(axis=0).astype(np.int32) for x in X]

X, y = mnist_test[:18]
preds = predict(X)
d2l.show_images(X, 2, 9, titles=[str(d) for d in preds]);
../_images/output_naive-bayes_vn_f35993_27_0.svg

Cuối cùng, hãy cùng tính toán độ chính xác tổng thể của bộ phân loại.

X, y = mnist_test[:]
preds = np.array(predict(X), dtype=np.int32)
float((preds == y).sum()) / len(y)  # Validation accuracy
0.8426

Các mạng sâu hiện đại đạt tỷ lệ lỗi dưới \(0,01\). Hiệu suất tương đối kém ở đây là do các giả định thống kê không chính xác mà ta đã đưa vào trong mô hình: ta đã giả định rằng mỗi và mọi pixel được tạo một cách độc lập, chỉ phụ thuộc vào nhãn. Đây rõ ràng không phải là cách con người viết các chữ số, và giả định sai lầm này đã dẫn đến sự kém hiệu quả của bộ phân loại ngây thơ (naive Bayes) của chúng ta.

18.9.5. Tóm tắt

  • Sử dụng quy tắc Bayes, một bộ phân loại có thể được tạo ra bằng cách giả định tất cả các đặc trưng quan sát được là độc lập.
  • Bộ phân loại này có thể được huấn luyện trên tập dữ liệu bằng cách đếm số lần xuất hiện của các tổ hợp nhãn và giá trị điểm ảnh.
  • Bộ phân loại này là tiêu chuẩn vàng trong nhiều thập kỷ cho các tác vụ như phát hiện thư rác.

18.9.6. Bài tập

  1. Xem xét tập dữ liệu \([[0,0], [0,1], [1,0], [1,1]]\) với các nhãn tương ứng là kết quả phép XOR của cặp số trong mỗi mẫu, tức \([0,1,1,0]\). Các xác suất cho bộ phân loại Naive Bayes được xây dựng trên tập dữ liệu này là bao nhiêu? Nó có phân loại thành công các điểm dữ liệu không? Nếu không, những giả định nào bị vi phạm?
  2. Giả sử ta không sử dụng làm mượt Laplace khi ước lượng xác suất và có một mẫu dữ liệu tại thời điểm kiểm tra chứa một giá trị chưa bao giờ được quan sát trong quá trình huấn luyện. Lúc này mô hình sẽ trả về giá trị gì?
  3. Bộ phân loại Naive Bayes là một ví dụ cụ thể của mạng Bayes, trong đó sự phụ thuộc của các biến ngẫu nhiên được mã hóa bằng cấu trúc đồ thị. Mặc dù lý thuyết đầy đủ nằm ngoài phạm vi của phần này (xem [Koller & Friedman, 2009] để biết chi tiết), hãy giải thích tại sao việc đưa sự phụ thuộc tường minh giữa hai biến đầu vào trong mô hình XOR lại có thể tạo ra một bộ phân loại thành công.

18.9.7. Thảo luận

18.9.8. 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
  • Lê Khắc Hồng Phúc
  • Phạm Minh Đức
  • Trần Yến Thy
  • Phạm Hồng Vinh
  • Nguyễn Văn Cường
  • Đỗ Trường Giang
  • Nguyễn Mai Hoàng Long